* [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
@ 2019-12-03 14:02 Pratik Shinde
2019-12-04 2:27 ` Gao Xiang
0 siblings, 1 reply; 9+ messages in thread
From: Pratik Shinde @ 2019-12-03 14:02 UTC (permalink / raw)
To: linux-erofs, bluce.liguifu, miaoxie, fangwei1
NOTE: The patch is not fully complete yet, with this patch I just want to
present rough idea of what I am trying to achieve.
The patch does following :
1) Detect holes (of size EROFS_BLKSIZ) in uncompressed files.
2) Keep track of holes per file.
In-order to track holes, I used an array of size = (file_size / blocksize)
The array basically tracks number of holes before a particular logical file block.
e.g blks[i] = 10 meaning ith block has 10 holes before it.
If a particular block is a hole we set the index to '-1'.
how read logic will change:
1) currently we simply map read offset to a fs block.
2) with holes in place the calculation of block number would be:
blkno = start_block + (offset >> block_size_shift) - (number of
holes before block in which offset falls)
3) If a read offset falls inside a hole (which can be found using above array). We
fill the user buffer with '\0' on the fly.
through this,block no. lookup would still be performed in constant time.
The biggest problem with this approach is - we have to store the hole tracking
array for every file to the disk.Which doesn't seems to be practical.we can use a linkedlist,
but that will make size of inode variable.
Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com>
---
lib/inode.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
1 file changed, 66 insertions(+), 1 deletion(-)
diff --git a/lib/inode.c b/lib/inode.c
index 0e19b11..af31949 100644
--- a/lib/inode.c
+++ b/lib/inode.c
@@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {
struct list_head inode_hashtable[NR_INODE_HASHTABLE];
+
+#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) == start && \
+ roundup(end, EROFS_BLKSIZ) == end && \
+ (end - start) % EROFS_BLKSIZ == 0)
+#define HOLE_BLK -1
+unsigned int erofs_detect_holes(struct erofs_inode *inode, int *blks)
+{
+ int i, fd, st, en;
+ unsigned int nblocks;
+ erofs_off_t data, hole, len;
+
+ nblocks = inode->i_size / EROFS_BLKSIZ;
+ for (i = 0; i < nblocks; i++)
+ blks[i] = 0;
+ fd = open(inode->i_srcpath, O_RDONLY);
+ if (fd < 0) {
+ return -errno;
+ }
+ len = lseek(fd, 0, SEEK_END);
+ if (lseek(fd, 0, SEEK_SET) == -1)
+ return -errno;
+ data = 0;
+ while (data < len) {
+ hole = lseek(fd, data, SEEK_HOLE);
+ if (hole == len)
+ break;
+ data = lseek(fd, hole, SEEK_DATA);
+ if (data < 0 || hole > data) {
+ return -EINVAL;
+ }
+ if (IS_HOLE(hole, data)) {
+ st = hole >> S_SHIFT;
+ en = data >> S_SHIFT;
+ nblocks -= (en - st);
+ for (i = st; i < en; i++)
+ blks[i] = HOLE_BLK;
+ }
+ }
+ return nblocks;
+}
+
+int erofs_fill_holedata(int *blks, unsigned int nblocks) {
+ int i, nholes = 0;
+ for (i = 0; i < nblocks; i++) {
+ if (blks[i] == -1)
+ nholes++;
+ else {
+ blks[i] = nholes;
+ if (nholes >= (i + 1))
+ return -EINVAL;
+ }
+ }
+ return 0;
+}
+
void erofs_inode_manager_init(void)
{
unsigned int i;
@@ -305,6 +360,7 @@ static bool erofs_file_is_compressible(struct erofs_inode *inode)
int erofs_write_file(struct erofs_inode *inode)
{
unsigned int nblocks, i;
+ int *blks;
int ret, fd;
if (!inode->i_size) {
@@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode *inode)
/* fallback to all data uncompressed */
inode->datalayout = EROFS_INODE_FLAT_INLINE;
nblocks = inode->i_size / EROFS_BLKSIZ;
-
+ blks = malloc(sizeof(int) * nblocks);
+ nblocks = erofs_detect_holes(inode, blks);
+ if (nblocks < 0)
+ return nblocks;
+ if ((ret = erofs_fill_holedata(blks, nblocks)) != 0) {
+ return ret;
+ }
ret = __allocate_inode_bh_data(inode, nblocks);
if (ret)
return ret;
@@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode *inode)
return -errno;
for (i = 0; i < nblocks; ++i) {
+ if (blks[i] == HOLE_BLK)
+ continue;
char buf[EROFS_BLKSIZ];
ret = read(fd, buf, EROFS_BLKSIZ);
@@ -962,3 +1026,4 @@ struct erofs_inode *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
return erofs_mkfs_build_tree(inode);
}
+
--
2.9.3
^ permalink raw reply related [flat|nested] 9+ messages in thread
* Re: [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
2019-12-03 14:02 [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files Pratik Shinde
@ 2019-12-04 2:27 ` Gao Xiang
2019-12-09 7:04 ` Pratik Shinde
0 siblings, 1 reply; 9+ messages in thread
From: Gao Xiang @ 2019-12-04 2:27 UTC (permalink / raw)
To: Pratik Shinde; +Cc: miaoxie, linux-erofs
Hi Pratik,
I'll give detailed words this weekend if you have more questions
since I'm busying in other stupid intra-company stuffs now...
On Tue, Dec 03, 2019 at 07:32:50PM +0530, Pratik Shinde wrote:
> NOTE: The patch is not fully complete yet, with this patch I just want to
> present rough idea of what I am trying to achieve.
>
> The patch does following :
> 1) Detect holes (of size EROFS_BLKSIZ) in uncompressed files.
> 2) Keep track of holes per file.
>
> In-order to track holes, I used an array of size = (file_size / blocksize)
> The array basically tracks number of holes before a particular logical file block.
> e.g blks[i] = 10 meaning ith block has 10 holes before it.
> If a particular block is a hole we set the index to '-1'.
>
> how read logic will change:
> 1) currently we simply map read offset to a fs block.
> 2) with holes in place the calculation of block number would be:
>
> blkno = start_block + (offset >> block_size_shift) - (number of
> holes before block in which offset falls)
>
> 3) If a read offset falls inside a hole (which can be found using above array). We
> fill the user buffer with '\0' on the fly.
>
> through this,block no. lookup would still be performed in constant time.
>
> The biggest problem with this approach is - we have to store the hole tracking
> array for every file to the disk.Which doesn't seems to be practical.we can use a linkedlist,
> but that will make size of inode variable.
"variable-sized inode" isn't a problem here, which can be handled
similar to the case of "compress indexes".
Probably no need to write linked list to the disk but generate linked list
in memory when writing data on the fly, and then transfer to a variable-sized
extent array at the time of writing inode metadata (The order is firstly data
and then metadata in erofs-utils so it looks practical.)
Thanks,
Gao Xiang
>
> Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com>
> ---
> lib/inode.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> 1 file changed, 66 insertions(+), 1 deletion(-)
>
> diff --git a/lib/inode.c b/lib/inode.c
> index 0e19b11..af31949 100644
> --- a/lib/inode.c
> +++ b/lib/inode.c
> @@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {
>
> struct list_head inode_hashtable[NR_INODE_HASHTABLE];
>
> +
> +#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) == start && \
> + roundup(end, EROFS_BLKSIZ) == end && \
> + (end - start) % EROFS_BLKSIZ == 0)
> +#define HOLE_BLK -1
> +unsigned int erofs_detect_holes(struct erofs_inode *inode, int *blks)
> +{
> + int i, fd, st, en;
> + unsigned int nblocks;
> + erofs_off_t data, hole, len;
> +
> + nblocks = inode->i_size / EROFS_BLKSIZ;
> + for (i = 0; i < nblocks; i++)
> + blks[i] = 0;
> + fd = open(inode->i_srcpath, O_RDONLY);
> + if (fd < 0) {
> + return -errno;
> + }
> + len = lseek(fd, 0, SEEK_END);
> + if (lseek(fd, 0, SEEK_SET) == -1)
> + return -errno;
> + data = 0;
> + while (data < len) {
> + hole = lseek(fd, data, SEEK_HOLE);
> + if (hole == len)
> + break;
> + data = lseek(fd, hole, SEEK_DATA);
> + if (data < 0 || hole > data) {
> + return -EINVAL;
> + }
> + if (IS_HOLE(hole, data)) {
> + st = hole >> S_SHIFT;
> + en = data >> S_SHIFT;
> + nblocks -= (en - st);
> + for (i = st; i < en; i++)
> + blks[i] = HOLE_BLK;
> + }
> + }
> + return nblocks;
> +}
> +
> +int erofs_fill_holedata(int *blks, unsigned int nblocks) {
> + int i, nholes = 0;
> + for (i = 0; i < nblocks; i++) {
> + if (blks[i] == -1)
> + nholes++;
> + else {
> + blks[i] = nholes;
> + if (nholes >= (i + 1))
> + return -EINVAL;
> + }
> + }
> + return 0;
> +}
> +
> void erofs_inode_manager_init(void)
> {
> unsigned int i;
> @@ -305,6 +360,7 @@ static bool erofs_file_is_compressible(struct erofs_inode *inode)
> int erofs_write_file(struct erofs_inode *inode)
> {
> unsigned int nblocks, i;
> + int *blks;
> int ret, fd;
>
> if (!inode->i_size) {
> @@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode *inode)
> /* fallback to all data uncompressed */
> inode->datalayout = EROFS_INODE_FLAT_INLINE;
> nblocks = inode->i_size / EROFS_BLKSIZ;
> -
> + blks = malloc(sizeof(int) * nblocks);
> + nblocks = erofs_detect_holes(inode, blks);
> + if (nblocks < 0)
> + return nblocks;
> + if ((ret = erofs_fill_holedata(blks, nblocks)) != 0) {
> + return ret;
> + }
> ret = __allocate_inode_bh_data(inode, nblocks);
> if (ret)
> return ret;
> @@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode *inode)
> return -errno;
>
> for (i = 0; i < nblocks; ++i) {
> + if (blks[i] == HOLE_BLK)
> + continue;
> char buf[EROFS_BLKSIZ];
>
> ret = read(fd, buf, EROFS_BLKSIZ);
> @@ -962,3 +1026,4 @@ struct erofs_inode *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
> return erofs_mkfs_build_tree(inode);
> }
>
> +
> --
> 2.9.3
>
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
2019-12-04 2:27 ` Gao Xiang
@ 2019-12-09 7:04 ` Pratik Shinde
2019-12-09 7:18 ` Gao Xiang
0 siblings, 1 reply; 9+ messages in thread
From: Pratik Shinde @ 2019-12-09 7:04 UTC (permalink / raw)
To: Gao Xiang; +Cc: miaoxie, linux-erofs
[-- Attachment #1: Type: text/plain, Size: 6094 bytes --]
Hello Gao,
Did you get any chance to look at this in detail.
--Pratik.
On Wed, Dec 4, 2019, 7:52 AM Gao Xiang <gaoxiang25@huawei.com> wrote:
> Hi Pratik,
>
> I'll give detailed words this weekend if you have more questions
> since I'm busying in other stupid intra-company stuffs now...
>
> On Tue, Dec 03, 2019 at 07:32:50PM +0530, Pratik Shinde wrote:
> > NOTE: The patch is not fully complete yet, with this patch I just want to
> > present rough idea of what I am trying to achieve.
> >
> > The patch does following :
> > 1) Detect holes (of size EROFS_BLKSIZ) in uncompressed files.
> > 2) Keep track of holes per file.
> >
> > In-order to track holes, I used an array of size = (file_size /
> blocksize)
> > The array basically tracks number of holes before a particular logical
> file block.
> > e.g blks[i] = 10 meaning ith block has 10 holes before it.
> > If a particular block is a hole we set the index to '-1'.
> >
> > how read logic will change:
> > 1) currently we simply map read offset to a fs block.
> > 2) with holes in place the calculation of block number would be:
> >
> > blkno = start_block + (offset >> block_size_shift) - (number of
> > holes before
> block in which offset falls)
> >
> > 3) If a read offset falls inside a hole (which can be found using above
> array). We
> > fill the user buffer with '\0' on the fly.
> >
> > through this,block no. lookup would still be performed in constant time.
> >
> > The biggest problem with this approach is - we have to store the hole
> tracking
> > array for every file to the disk.Which doesn't seems to be practical.we
> can use a linkedlist,
> > but that will make size of inode variable.
>
> "variable-sized inode" isn't a problem here, which can be handled
> similar to the case of "compress indexes".
>
> Probably no need to write linked list to the disk but generate linked list
> in memory when writing data on the fly, and then transfer to a
> variable-sized
> extent array at the time of writing inode metadata (The order is firstly
> data
> and then metadata in erofs-utils so it looks practical.)
>
> Thanks,
> Gao Xiang
>
> >
> > Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com>
> > ---
> > lib/inode.c | 67
> ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> > 1 file changed, 66 insertions(+), 1 deletion(-)
> >
> > diff --git a/lib/inode.c b/lib/inode.c
> > index 0e19b11..af31949 100644
> > --- a/lib/inode.c
> > +++ b/lib/inode.c
> > @@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT >>
> S_SHIFT] = {
> >
> > struct list_head inode_hashtable[NR_INODE_HASHTABLE];
> >
> > +
> > +#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) == start &&
> \
> > + roundup(end, EROFS_BLKSIZ) == end && \
> > + (end - start) % EROFS_BLKSIZ == 0)
> > +#define HOLE_BLK -1
> > +unsigned int erofs_detect_holes(struct erofs_inode *inode, int *blks)
> > +{
> > + int i, fd, st, en;
> > + unsigned int nblocks;
> > + erofs_off_t data, hole, len;
> > +
> > + nblocks = inode->i_size / EROFS_BLKSIZ;
> > + for (i = 0; i < nblocks; i++)
> > + blks[i] = 0;
> > + fd = open(inode->i_srcpath, O_RDONLY);
> > + if (fd < 0) {
> > + return -errno;
> > + }
> > + len = lseek(fd, 0, SEEK_END);
> > + if (lseek(fd, 0, SEEK_SET) == -1)
> > + return -errno;
> > + data = 0;
> > + while (data < len) {
> > + hole = lseek(fd, data, SEEK_HOLE);
> > + if (hole == len)
> > + break;
> > + data = lseek(fd, hole, SEEK_DATA);
> > + if (data < 0 || hole > data) {
> > + return -EINVAL;
> > + }
> > + if (IS_HOLE(hole, data)) {
> > + st = hole >> S_SHIFT;
> > + en = data >> S_SHIFT;
> > + nblocks -= (en - st);
> > + for (i = st; i < en; i++)
> > + blks[i] = HOLE_BLK;
> > + }
> > + }
> > + return nblocks;
> > +}
> > +
> > +int erofs_fill_holedata(int *blks, unsigned int nblocks) {
> > + int i, nholes = 0;
> > + for (i = 0; i < nblocks; i++) {
> > + if (blks[i] == -1)
> > + nholes++;
> > + else {
> > + blks[i] = nholes;
> > + if (nholes >= (i + 1))
> > + return -EINVAL;
> > + }
> > + }
> > + return 0;
> > +}
> > +
> > void erofs_inode_manager_init(void)
> > {
> > unsigned int i;
> > @@ -305,6 +360,7 @@ static bool erofs_file_is_compressible(struct
> erofs_inode *inode)
> > int erofs_write_file(struct erofs_inode *inode)
> > {
> > unsigned int nblocks, i;
> > + int *blks;
> > int ret, fd;
> >
> > if (!inode->i_size) {
> > @@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode *inode)
> > /* fallback to all data uncompressed */
> > inode->datalayout = EROFS_INODE_FLAT_INLINE;
> > nblocks = inode->i_size / EROFS_BLKSIZ;
> > -
> > + blks = malloc(sizeof(int) * nblocks);
> > + nblocks = erofs_detect_holes(inode, blks);
> > + if (nblocks < 0)
> > + return nblocks;
> > + if ((ret = erofs_fill_holedata(blks, nblocks)) != 0) {
> > + return ret;
> > + }
> > ret = __allocate_inode_bh_data(inode, nblocks);
> > if (ret)
> > return ret;
> > @@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode *inode)
> > return -errno;
> >
> > for (i = 0; i < nblocks; ++i) {
> > + if (blks[i] == HOLE_BLK)
> > + continue;
> > char buf[EROFS_BLKSIZ];
> >
> > ret = read(fd, buf, EROFS_BLKSIZ);
> > @@ -962,3 +1026,4 @@ struct erofs_inode
> *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
> > return erofs_mkfs_build_tree(inode);
> > }
> >
> > +
> > --
> > 2.9.3
> >
>
[-- Attachment #2: Type: text/html, Size: 8050 bytes --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
2019-12-09 7:04 ` Pratik Shinde
@ 2019-12-09 7:18 ` Gao Xiang
2019-12-11 5:49 ` Gao Xiang
0 siblings, 1 reply; 9+ messages in thread
From: Gao Xiang @ 2019-12-09 7:18 UTC (permalink / raw)
To: Pratik Shinde; +Cc: miaoxie, linux-erofs
Hi Pratik,
On Mon, Dec 09, 2019 at 12:34:50PM +0530, Pratik Shinde wrote:
> Hello Gao,
>
> Did you get any chance to look at this in detail.
I looked into your implementation weeks before.
As my reply in the previous email, did you see it and could you check it out?
Kernel emails are not top-posting so you could scroll down to the end.
> > "variable-sized inode" isn't a problem here, which can be handled
> > similar to the case of "compress indexes".
> >
> > Probably no need to write linked list to the disk but generate linked list
> > in memory when writing data on the fly, and then transfer to a
> > variable-sized
> > extent array at the time of writing inode metadata (The order is firstly
> > data
> > and then metadata in erofs-utils so it looks practical.)
Thanks,
Gao Xiang
>
> --Pratik.
>
> On Wed, Dec 4, 2019, 7:52 AM Gao Xiang <gaoxiang25@huawei.com> wrote:
>
> > Hi Pratik,
> >
> > I'll give detailed words this weekend if you have more questions
> > since I'm busying in other stupid intra-company stuffs now...
> >
> > On Tue, Dec 03, 2019 at 07:32:50PM +0530, Pratik Shinde wrote:
> > > NOTE: The patch is not fully complete yet, with this patch I just want to
> > > present rough idea of what I am trying to achieve.
> > >
> > > The patch does following :
> > > 1) Detect holes (of size EROFS_BLKSIZ) in uncompressed files.
> > > 2) Keep track of holes per file.
> > >
> > > In-order to track holes, I used an array of size = (file_size /
> > blocksize)
> > > The array basically tracks number of holes before a particular logical
> > file block.
> > > e.g blks[i] = 10 meaning ith block has 10 holes before it.
> > > If a particular block is a hole we set the index to '-1'.
> > >
> > > how read logic will change:
> > > 1) currently we simply map read offset to a fs block.
> > > 2) with holes in place the calculation of block number would be:
> > >
> > > blkno = start_block + (offset >> block_size_shift) - (number of
> > > holes before
> > block in which offset falls)
> > >
> > > 3) If a read offset falls inside a hole (which can be found using above
> > array). We
> > > fill the user buffer with '\0' on the fly.
> > >
> > > through this,block no. lookup would still be performed in constant time.
> > >
> > > The biggest problem with this approach is - we have to store the hole
> > tracking
> > > array for every file to the disk.Which doesn't seems to be practical.we
> > can use a linkedlist,
> > > but that will make size of inode variable.
> >
> > "variable-sized inode" isn't a problem here, which can be handled
> > similar to the case of "compress indexes".
> >
> > Probably no need to write linked list to the disk but generate linked list
> > in memory when writing data on the fly, and then transfer to a
> > variable-sized
> > extent array at the time of writing inode metadata (The order is firstly
> > data
> > and then metadata in erofs-utils so it looks practical.)
> >
> > Thanks,
> > Gao Xiang
> >
> > >
> > > Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com>
> > > ---
> > > lib/inode.c | 67
> > ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> > > 1 file changed, 66 insertions(+), 1 deletion(-)
> > >
> > > diff --git a/lib/inode.c b/lib/inode.c
> > > index 0e19b11..af31949 100644
> > > --- a/lib/inode.c
> > > +++ b/lib/inode.c
> > > @@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT >>
> > S_SHIFT] = {
> > >
> > > struct list_head inode_hashtable[NR_INODE_HASHTABLE];
> > >
> > > +
> > > +#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) == start &&
> > \
> > > + roundup(end, EROFS_BLKSIZ) == end && \
> > > + (end - start) % EROFS_BLKSIZ == 0)
> > > +#define HOLE_BLK -1
> > > +unsigned int erofs_detect_holes(struct erofs_inode *inode, int *blks)
> > > +{
> > > + int i, fd, st, en;
> > > + unsigned int nblocks;
> > > + erofs_off_t data, hole, len;
> > > +
> > > + nblocks = inode->i_size / EROFS_BLKSIZ;
> > > + for (i = 0; i < nblocks; i++)
> > > + blks[i] = 0;
> > > + fd = open(inode->i_srcpath, O_RDONLY);
> > > + if (fd < 0) {
> > > + return -errno;
> > > + }
> > > + len = lseek(fd, 0, SEEK_END);
> > > + if (lseek(fd, 0, SEEK_SET) == -1)
> > > + return -errno;
> > > + data = 0;
> > > + while (data < len) {
> > > + hole = lseek(fd, data, SEEK_HOLE);
> > > + if (hole == len)
> > > + break;
> > > + data = lseek(fd, hole, SEEK_DATA);
> > > + if (data < 0 || hole > data) {
> > > + return -EINVAL;
> > > + }
> > > + if (IS_HOLE(hole, data)) {
> > > + st = hole >> S_SHIFT;
> > > + en = data >> S_SHIFT;
> > > + nblocks -= (en - st);
> > > + for (i = st; i < en; i++)
> > > + blks[i] = HOLE_BLK;
> > > + }
> > > + }
> > > + return nblocks;
> > > +}
> > > +
> > > +int erofs_fill_holedata(int *blks, unsigned int nblocks) {
> > > + int i, nholes = 0;
> > > + for (i = 0; i < nblocks; i++) {
> > > + if (blks[i] == -1)
> > > + nholes++;
> > > + else {
> > > + blks[i] = nholes;
> > > + if (nholes >= (i + 1))
> > > + return -EINVAL;
> > > + }
> > > + }
> > > + return 0;
> > > +}
> > > +
> > > void erofs_inode_manager_init(void)
> > > {
> > > unsigned int i;
> > > @@ -305,6 +360,7 @@ static bool erofs_file_is_compressible(struct
> > erofs_inode *inode)
> > > int erofs_write_file(struct erofs_inode *inode)
> > > {
> > > unsigned int nblocks, i;
> > > + int *blks;
> > > int ret, fd;
> > >
> > > if (!inode->i_size) {
> > > @@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode *inode)
> > > /* fallback to all data uncompressed */
> > > inode->datalayout = EROFS_INODE_FLAT_INLINE;
> > > nblocks = inode->i_size / EROFS_BLKSIZ;
> > > -
> > > + blks = malloc(sizeof(int) * nblocks);
> > > + nblocks = erofs_detect_holes(inode, blks);
> > > + if (nblocks < 0)
> > > + return nblocks;
> > > + if ((ret = erofs_fill_holedata(blks, nblocks)) != 0) {
> > > + return ret;
> > > + }
> > > ret = __allocate_inode_bh_data(inode, nblocks);
> > > if (ret)
> > > return ret;
> > > @@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode *inode)
> > > return -errno;
> > >
> > > for (i = 0; i < nblocks; ++i) {
> > > + if (blks[i] == HOLE_BLK)
> > > + continue;
> > > char buf[EROFS_BLKSIZ];
> > >
> > > ret = read(fd, buf, EROFS_BLKSIZ);
> > > @@ -962,3 +1026,4 @@ struct erofs_inode
> > *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
> > > return erofs_mkfs_build_tree(inode);
> > > }
> > >
> > > +
> > > --
> > > 2.9.3
> > >
> >
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
2019-12-09 7:18 ` Gao Xiang
@ 2019-12-11 5:49 ` Gao Xiang
2019-12-13 7:05 ` Pratik Shinde
0 siblings, 1 reply; 9+ messages in thread
From: Gao Xiang @ 2019-12-11 5:49 UTC (permalink / raw)
To: Pratik Shinde; +Cc: linux-erofs, miaoxie
On Mon, Dec 09, 2019 at 03:18:17PM +0800, Gao Xiang wrote:
> Hi Pratik,
>
> On Mon, Dec 09, 2019 at 12:34:50PM +0530, Pratik Shinde wrote:
> > Hello Gao,
> >
> > Did you get any chance to look at this in detail.
>
> I looked into your implementation weeks before.
>
> As my reply in the previous email, did you see it and could you check it out?
>
> Kernel emails are not top-posting so you could scroll down to the end.
>
> > > "variable-sized inode" isn't a problem here, which can be handled
> > > similar to the case of "compress indexes".
> > >
> > > Probably no need to write linked list to the disk but generate linked list
> > > in memory when writing data on the fly, and then transfer to a
> > > variable-sized
> > > extent array at the time of writing inode metadata (The order is firstly
> > > data
> > > and then metadata in erofs-utils so it looks practical.)
Some feedback words here? Do you think it is unnecessary to use such
array for limited fragmented holes (either in-memory or ondisk) as well?
Thanks,
Gao Xiang
>
> Thanks,
> Gao Xiang
>
> >
> > --Pratik.
> >
> > On Wed, Dec 4, 2019, 7:52 AM Gao Xiang <gaoxiang25@huawei.com> wrote:
> >
> > > Hi Pratik,
> > >
> > > I'll give detailed words this weekend if you have more questions
> > > since I'm busying in other stupid intra-company stuffs now...
> > >
> > > On Tue, Dec 03, 2019 at 07:32:50PM +0530, Pratik Shinde wrote:
> > > > NOTE: The patch is not fully complete yet, with this patch I just want to
> > > > present rough idea of what I am trying to achieve.
> > > >
> > > > The patch does following :
> > > > 1) Detect holes (of size EROFS_BLKSIZ) in uncompressed files.
> > > > 2) Keep track of holes per file.
> > > >
> > > > In-order to track holes, I used an array of size = (file_size /
> > > blocksize)
> > > > The array basically tracks number of holes before a particular logical
> > > file block.
> > > > e.g blks[i] = 10 meaning ith block has 10 holes before it.
> > > > If a particular block is a hole we set the index to '-1'.
> > > >
> > > > how read logic will change:
> > > > 1) currently we simply map read offset to a fs block.
> > > > 2) with holes in place the calculation of block number would be:
> > > >
> > > > blkno = start_block + (offset >> block_size_shift) - (number of
> > > > holes before
> > > block in which offset falls)
> > > >
> > > > 3) If a read offset falls inside a hole (which can be found using above
> > > array). We
> > > > fill the user buffer with '\0' on the fly.
> > > >
> > > > through this,block no. lookup would still be performed in constant time.
> > > >
> > > > The biggest problem with this approach is - we have to store the hole
> > > tracking
> > > > array for every file to the disk.Which doesn't seems to be practical.we
> > > can use a linkedlist,
> > > > but that will make size of inode variable.
> > >
> > > "variable-sized inode" isn't a problem here, which can be handled
> > > similar to the case of "compress indexes".
> > >
> > > Probably no need to write linked list to the disk but generate linked list
> > > in memory when writing data on the fly, and then transfer to a
> > > variable-sized
> > > extent array at the time of writing inode metadata (The order is firstly
> > > data
> > > and then metadata in erofs-utils so it looks practical.)
> > >
> > > Thanks,
> > > Gao Xiang
> > >
> > > >
> > > > Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com>
> > > > ---
> > > > lib/inode.c | 67
> > > ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> > > > 1 file changed, 66 insertions(+), 1 deletion(-)
> > > >
> > > > diff --git a/lib/inode.c b/lib/inode.c
> > > > index 0e19b11..af31949 100644
> > > > --- a/lib/inode.c
> > > > +++ b/lib/inode.c
> > > > @@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT >>
> > > S_SHIFT] = {
> > > >
> > > > struct list_head inode_hashtable[NR_INODE_HASHTABLE];
> > > >
> > > > +
> > > > +#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) == start &&
> > > \
> > > > + roundup(end, EROFS_BLKSIZ) == end && \
> > > > + (end - start) % EROFS_BLKSIZ == 0)
> > > > +#define HOLE_BLK -1
> > > > +unsigned int erofs_detect_holes(struct erofs_inode *inode, int *blks)
> > > > +{
> > > > + int i, fd, st, en;
> > > > + unsigned int nblocks;
> > > > + erofs_off_t data, hole, len;
> > > > +
> > > > + nblocks = inode->i_size / EROFS_BLKSIZ;
> > > > + for (i = 0; i < nblocks; i++)
> > > > + blks[i] = 0;
> > > > + fd = open(inode->i_srcpath, O_RDONLY);
> > > > + if (fd < 0) {
> > > > + return -errno;
> > > > + }
> > > > + len = lseek(fd, 0, SEEK_END);
> > > > + if (lseek(fd, 0, SEEK_SET) == -1)
> > > > + return -errno;
> > > > + data = 0;
> > > > + while (data < len) {
> > > > + hole = lseek(fd, data, SEEK_HOLE);
> > > > + if (hole == len)
> > > > + break;
> > > > + data = lseek(fd, hole, SEEK_DATA);
> > > > + if (data < 0 || hole > data) {
> > > > + return -EINVAL;
> > > > + }
> > > > + if (IS_HOLE(hole, data)) {
> > > > + st = hole >> S_SHIFT;
> > > > + en = data >> S_SHIFT;
> > > > + nblocks -= (en - st);
> > > > + for (i = st; i < en; i++)
> > > > + blks[i] = HOLE_BLK;
> > > > + }
> > > > + }
> > > > + return nblocks;
> > > > +}
> > > > +
> > > > +int erofs_fill_holedata(int *blks, unsigned int nblocks) {
> > > > + int i, nholes = 0;
> > > > + for (i = 0; i < nblocks; i++) {
> > > > + if (blks[i] == -1)
> > > > + nholes++;
> > > > + else {
> > > > + blks[i] = nholes;
> > > > + if (nholes >= (i + 1))
> > > > + return -EINVAL;
> > > > + }
> > > > + }
> > > > + return 0;
> > > > +}
> > > > +
> > > > void erofs_inode_manager_init(void)
> > > > {
> > > > unsigned int i;
> > > > @@ -305,6 +360,7 @@ static bool erofs_file_is_compressible(struct
> > > erofs_inode *inode)
> > > > int erofs_write_file(struct erofs_inode *inode)
> > > > {
> > > > unsigned int nblocks, i;
> > > > + int *blks;
> > > > int ret, fd;
> > > >
> > > > if (!inode->i_size) {
> > > > @@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode *inode)
> > > > /* fallback to all data uncompressed */
> > > > inode->datalayout = EROFS_INODE_FLAT_INLINE;
> > > > nblocks = inode->i_size / EROFS_BLKSIZ;
> > > > -
> > > > + blks = malloc(sizeof(int) * nblocks);
> > > > + nblocks = erofs_detect_holes(inode, blks);
> > > > + if (nblocks < 0)
> > > > + return nblocks;
> > > > + if ((ret = erofs_fill_holedata(blks, nblocks)) != 0) {
> > > > + return ret;
> > > > + }
> > > > ret = __allocate_inode_bh_data(inode, nblocks);
> > > > if (ret)
> > > > return ret;
> > > > @@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode *inode)
> > > > return -errno;
> > > >
> > > > for (i = 0; i < nblocks; ++i) {
> > > > + if (blks[i] == HOLE_BLK)
> > > > + continue;
> > > > char buf[EROFS_BLKSIZ];
> > > >
> > > > ret = read(fd, buf, EROFS_BLKSIZ);
> > > > @@ -962,3 +1026,4 @@ struct erofs_inode
> > > *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
> > > > return erofs_mkfs_build_tree(inode);
> > > > }
> > > >
> > > > +
> > > > --
> > > > 2.9.3
> > > >
> > >
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
2019-12-11 5:49 ` Gao Xiang
@ 2019-12-13 7:05 ` Pratik Shinde
2019-12-13 7:24 ` Gao Xiang
0 siblings, 1 reply; 9+ messages in thread
From: Pratik Shinde @ 2019-12-13 7:05 UTC (permalink / raw)
To: Gao Xiang; +Cc: linux-erofs, miaoxie
[-- Attachment #1: Type: text/plain, Size: 8404 bytes --]
Gao,
just returned from holidays. Let me rethink about this approach.
--Pratik
On Wed, Dec 11, 2019, 11:14 AM Gao Xiang <gaoxiang25@huawei.com> wrote:
> On Mon, Dec 09, 2019 at 03:18:17PM +0800, Gao Xiang wrote:
> > Hi Pratik,
> >
> > On Mon, Dec 09, 2019 at 12:34:50PM +0530, Pratik Shinde wrote:
> > > Hello Gao,
> > >
> > > Did you get any chance to look at this in detail.
> >
> > I looked into your implementation weeks before.
> >
> > As my reply in the previous email, did you see it and could you check it
> out?
> >
> > Kernel emails are not top-posting so you could scroll down to the end.
> >
> > > > "variable-sized inode" isn't a problem here, which can be handled
> > > > similar to the case of "compress indexes".
> > > >
> > > > Probably no need to write linked list to the disk but generate
> linked list
> > > > in memory when writing data on the fly, and then transfer to a
> > > > variable-sized
> > > > extent array at the time of writing inode metadata (The order is
> firstly
> > > > data
> > > > and then metadata in erofs-utils so it looks practical.)
>
>
> Some feedback words here? Do you think it is unnecessary to use such
> array for limited fragmented holes (either in-memory or ondisk) as well?
>
> Thanks,
> Gao Xiang
>
>
> >
> > Thanks,
> > Gao Xiang
> >
> > >
> > > --Pratik.
> > >
> > > On Wed, Dec 4, 2019, 7:52 AM Gao Xiang <gaoxiang25@huawei.com> wrote:
> > >
> > > > Hi Pratik,
> > > >
> > > > I'll give detailed words this weekend if you have more questions
> > > > since I'm busying in other stupid intra-company stuffs now...
> > > >
> > > > On Tue, Dec 03, 2019 at 07:32:50PM +0530, Pratik Shinde wrote:
> > > > > NOTE: The patch is not fully complete yet, with this patch I just
> want to
> > > > > present rough idea of what I am trying to achieve.
> > > > >
> > > > > The patch does following :
> > > > > 1) Detect holes (of size EROFS_BLKSIZ) in uncompressed files.
> > > > > 2) Keep track of holes per file.
> > > > >
> > > > > In-order to track holes, I used an array of size = (file_size /
> > > > blocksize)
> > > > > The array basically tracks number of holes before a particular
> logical
> > > > file block.
> > > > > e.g blks[i] = 10 meaning ith block has 10 holes before it.
> > > > > If a particular block is a hole we set the index to '-1'.
> > > > >
> > > > > how read logic will change:
> > > > > 1) currently we simply map read offset to a fs block.
> > > > > 2) with holes in place the calculation of block number would be:
> > > > >
> > > > > blkno = start_block + (offset >> block_size_shift) - (number of
> > > > > holes before
> > > > block in which offset falls)
> > > > >
> > > > > 3) If a read offset falls inside a hole (which can be found using
> above
> > > > array). We
> > > > > fill the user buffer with '\0' on the fly.
> > > > >
> > > > > through this,block no. lookup would still be performed in constant
> time.
> > > > >
> > > > > The biggest problem with this approach is - we have to store the
> hole
> > > > tracking
> > > > > array for every file to the disk.Which doesn't seems to be
> practical.we
> > > > can use a linkedlist,
> > > > > but that will make size of inode variable.
> > > >
> > > > "variable-sized inode" isn't a problem here, which can be handled
> > > > similar to the case of "compress indexes".
> > > >
> > > > Probably no need to write linked list to the disk but generate
> linked list
> > > > in memory when writing data on the fly, and then transfer to a
> > > > variable-sized
> > > > extent array at the time of writing inode metadata (The order is
> firstly
> > > > data
> > > > and then metadata in erofs-utils so it looks practical.)
> > > >
> > > > Thanks,
> > > > Gao Xiang
> > > >
> > > > >
> > > > > Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com>
> > > > > ---
> > > > > lib/inode.c | 67
> > > > ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> > > > > 1 file changed, 66 insertions(+), 1 deletion(-)
> > > > >
> > > > > diff --git a/lib/inode.c b/lib/inode.c
> > > > > index 0e19b11..af31949 100644
> > > > > --- a/lib/inode.c
> > > > > +++ b/lib/inode.c
> > > > > @@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT
> >>
> > > > S_SHIFT] = {
> > > > >
> > > > > struct list_head inode_hashtable[NR_INODE_HASHTABLE];
> > > > >
> > > > > +
> > > > > +#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) ==
> start &&
> > > > \
> > > > > + roundup(end, EROFS_BLKSIZ) == end &&
> \
> > > > > + (end - start) % EROFS_BLKSIZ == 0)
> > > > > +#define HOLE_BLK -1
> > > > > +unsigned int erofs_detect_holes(struct erofs_inode *inode, int
> *blks)
> > > > > +{
> > > > > + int i, fd, st, en;
> > > > > + unsigned int nblocks;
> > > > > + erofs_off_t data, hole, len;
> > > > > +
> > > > > + nblocks = inode->i_size / EROFS_BLKSIZ;
> > > > > + for (i = 0; i < nblocks; i++)
> > > > > + blks[i] = 0;
> > > > > + fd = open(inode->i_srcpath, O_RDONLY);
> > > > > + if (fd < 0) {
> > > > > + return -errno;
> > > > > + }
> > > > > + len = lseek(fd, 0, SEEK_END);
> > > > > + if (lseek(fd, 0, SEEK_SET) == -1)
> > > > > + return -errno;
> > > > > + data = 0;
> > > > > + while (data < len) {
> > > > > + hole = lseek(fd, data, SEEK_HOLE);
> > > > > + if (hole == len)
> > > > > + break;
> > > > > + data = lseek(fd, hole, SEEK_DATA);
> > > > > + if (data < 0 || hole > data) {
> > > > > + return -EINVAL;
> > > > > + }
> > > > > + if (IS_HOLE(hole, data)) {
> > > > > + st = hole >> S_SHIFT;
> > > > > + en = data >> S_SHIFT;
> > > > > + nblocks -= (en - st);
> > > > > + for (i = st; i < en; i++)
> > > > > + blks[i] = HOLE_BLK;
> > > > > + }
> > > > > + }
> > > > > + return nblocks;
> > > > > +}
> > > > > +
> > > > > +int erofs_fill_holedata(int *blks, unsigned int nblocks) {
> > > > > + int i, nholes = 0;
> > > > > + for (i = 0; i < nblocks; i++) {
> > > > > + if (blks[i] == -1)
> > > > > + nholes++;
> > > > > + else {
> > > > > + blks[i] = nholes;
> > > > > + if (nholes >= (i + 1))
> > > > > + return -EINVAL;
> > > > > + }
> > > > > + }
> > > > > + return 0;
> > > > > +}
> > > > > +
> > > > > void erofs_inode_manager_init(void)
> > > > > {
> > > > > unsigned int i;
> > > > > @@ -305,6 +360,7 @@ static bool erofs_file_is_compressible(struct
> > > > erofs_inode *inode)
> > > > > int erofs_write_file(struct erofs_inode *inode)
> > > > > {
> > > > > unsigned int nblocks, i;
> > > > > + int *blks;
> > > > > int ret, fd;
> > > > >
> > > > > if (!inode->i_size) {
> > > > > @@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode
> *inode)
> > > > > /* fallback to all data uncompressed */
> > > > > inode->datalayout = EROFS_INODE_FLAT_INLINE;
> > > > > nblocks = inode->i_size / EROFS_BLKSIZ;
> > > > > -
> > > > > + blks = malloc(sizeof(int) * nblocks);
> > > > > + nblocks = erofs_detect_holes(inode, blks);
> > > > > + if (nblocks < 0)
> > > > > + return nblocks;
> > > > > + if ((ret = erofs_fill_holedata(blks, nblocks)) != 0) {
> > > > > + return ret;
> > > > > + }
> > > > > ret = __allocate_inode_bh_data(inode, nblocks);
> > > > > if (ret)
> > > > > return ret;
> > > > > @@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode *inode)
> > > > > return -errno;
> > > > >
> > > > > for (i = 0; i < nblocks; ++i) {
> > > > > + if (blks[i] == HOLE_BLK)
> > > > > + continue;
> > > > > char buf[EROFS_BLKSIZ];
> > > > >
> > > > > ret = read(fd, buf, EROFS_BLKSIZ);
> > > > > @@ -962,3 +1026,4 @@ struct erofs_inode
> > > > *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
> > > > > return erofs_mkfs_build_tree(inode);
> > > > > }
> > > > >
> > > > > +
> > > > > --
> > > > > 2.9.3
> > > > >
> > > >
>
[-- Attachment #2: Type: text/html, Size: 12342 bytes --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
2019-12-13 7:05 ` Pratik Shinde
@ 2019-12-13 7:24 ` Gao Xiang
2019-12-17 18:06 ` Pratik Shinde
0 siblings, 1 reply; 9+ messages in thread
From: Gao Xiang @ 2019-12-13 7:24 UTC (permalink / raw)
To: Pratik Shinde; +Cc: linux-erofs, miaoxie
On Fri, Dec 13, 2019 at 12:35:00PM +0530, Pratik Shinde wrote:
> Gao,
>
> just returned from holidays. Let me rethink about this approach.
Okay, no problem at all. :)
Thanks,
Gao Xiang
>
> --Pratik
>
>
> On Wed, Dec 11, 2019, 11:14 AM Gao Xiang <gaoxiang25@huawei.com> wrote:
>
> > On Mon, Dec 09, 2019 at 03:18:17PM +0800, Gao Xiang wrote:
> > > Hi Pratik,
> > >
> > > On Mon, Dec 09, 2019 at 12:34:50PM +0530, Pratik Shinde wrote:
> > > > Hello Gao,
> > > >
> > > > Did you get any chance to look at this in detail.
> > >
> > > I looked into your implementation weeks before.
> > >
> > > As my reply in the previous email, did you see it and could you check it
> > out?
> > >
> > > Kernel emails are not top-posting so you could scroll down to the end.
> > >
> > > > > "variable-sized inode" isn't a problem here, which can be handled
> > > > > similar to the case of "compress indexes".
> > > > >
> > > > > Probably no need to write linked list to the disk but generate
> > linked list
> > > > > in memory when writing data on the fly, and then transfer to a
> > > > > variable-sized
> > > > > extent array at the time of writing inode metadata (The order is
> > firstly
> > > > > data
> > > > > and then metadata in erofs-utils so it looks practical.)
> >
> >
> > Some feedback words here? Do you think it is unnecessary to use such
> > array for limited fragmented holes (either in-memory or ondisk) as well?
> >
> > Thanks,
> > Gao Xiang
> >
> >
> > >
> > > Thanks,
> > > Gao Xiang
> > >
> > > >
> > > > --Pratik.
> > > >
> > > > On Wed, Dec 4, 2019, 7:52 AM Gao Xiang <gaoxiang25@huawei.com> wrote:
> > > >
> > > > > Hi Pratik,
> > > > >
> > > > > I'll give detailed words this weekend if you have more questions
> > > > > since I'm busying in other stupid intra-company stuffs now...
> > > > >
> > > > > On Tue, Dec 03, 2019 at 07:32:50PM +0530, Pratik Shinde wrote:
> > > > > > NOTE: The patch is not fully complete yet, with this patch I just
> > want to
> > > > > > present rough idea of what I am trying to achieve.
> > > > > >
> > > > > > The patch does following :
> > > > > > 1) Detect holes (of size EROFS_BLKSIZ) in uncompressed files.
> > > > > > 2) Keep track of holes per file.
> > > > > >
> > > > > > In-order to track holes, I used an array of size = (file_size /
> > > > > blocksize)
> > > > > > The array basically tracks number of holes before a particular
> > logical
> > > > > file block.
> > > > > > e.g blks[i] = 10 meaning ith block has 10 holes before it.
> > > > > > If a particular block is a hole we set the index to '-1'.
> > > > > >
> > > > > > how read logic will change:
> > > > > > 1) currently we simply map read offset to a fs block.
> > > > > > 2) with holes in place the calculation of block number would be:
> > > > > >
> > > > > > blkno = start_block + (offset >> block_size_shift) - (number of
> > > > > > holes before
> > > > > block in which offset falls)
> > > > > >
> > > > > > 3) If a read offset falls inside a hole (which can be found using
> > above
> > > > > array). We
> > > > > > fill the user buffer with '\0' on the fly.
> > > > > >
> > > > > > through this,block no. lookup would still be performed in constant
> > time.
> > > > > >
> > > > > > The biggest problem with this approach is - we have to store the
> > hole
> > > > > tracking
> > > > > > array for every file to the disk.Which doesn't seems to be
> > practical.we
> > > > > can use a linkedlist,
> > > > > > but that will make size of inode variable.
> > > > >
> > > > > "variable-sized inode" isn't a problem here, which can be handled
> > > > > similar to the case of "compress indexes".
> > > > >
> > > > > Probably no need to write linked list to the disk but generate
> > linked list
> > > > > in memory when writing data on the fly, and then transfer to a
> > > > > variable-sized
> > > > > extent array at the time of writing inode metadata (The order is
> > firstly
> > > > > data
> > > > > and then metadata in erofs-utils so it looks practical.)
> > > > >
> > > > > Thanks,
> > > > > Gao Xiang
> > > > >
> > > > > >
> > > > > > Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com>
> > > > > > ---
> > > > > > lib/inode.c | 67
> > > > > ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> > > > > > 1 file changed, 66 insertions(+), 1 deletion(-)
> > > > > >
> > > > > > diff --git a/lib/inode.c b/lib/inode.c
> > > > > > index 0e19b11..af31949 100644
> > > > > > --- a/lib/inode.c
> > > > > > +++ b/lib/inode.c
> > > > > > @@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT
> > >>
> > > > > S_SHIFT] = {
> > > > > >
> > > > > > struct list_head inode_hashtable[NR_INODE_HASHTABLE];
> > > > > >
> > > > > > +
> > > > > > +#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) ==
> > start &&
> > > > > \
> > > > > > + roundup(end, EROFS_BLKSIZ) == end &&
> > \
> > > > > > + (end - start) % EROFS_BLKSIZ == 0)
> > > > > > +#define HOLE_BLK -1
> > > > > > +unsigned int erofs_detect_holes(struct erofs_inode *inode, int
> > *blks)
> > > > > > +{
> > > > > > + int i, fd, st, en;
> > > > > > + unsigned int nblocks;
> > > > > > + erofs_off_t data, hole, len;
> > > > > > +
> > > > > > + nblocks = inode->i_size / EROFS_BLKSIZ;
> > > > > > + for (i = 0; i < nblocks; i++)
> > > > > > + blks[i] = 0;
> > > > > > + fd = open(inode->i_srcpath, O_RDONLY);
> > > > > > + if (fd < 0) {
> > > > > > + return -errno;
> > > > > > + }
> > > > > > + len = lseek(fd, 0, SEEK_END);
> > > > > > + if (lseek(fd, 0, SEEK_SET) == -1)
> > > > > > + return -errno;
> > > > > > + data = 0;
> > > > > > + while (data < len) {
> > > > > > + hole = lseek(fd, data, SEEK_HOLE);
> > > > > > + if (hole == len)
> > > > > > + break;
> > > > > > + data = lseek(fd, hole, SEEK_DATA);
> > > > > > + if (data < 0 || hole > data) {
> > > > > > + return -EINVAL;
> > > > > > + }
> > > > > > + if (IS_HOLE(hole, data)) {
> > > > > > + st = hole >> S_SHIFT;
> > > > > > + en = data >> S_SHIFT;
> > > > > > + nblocks -= (en - st);
> > > > > > + for (i = st; i < en; i++)
> > > > > > + blks[i] = HOLE_BLK;
> > > > > > + }
> > > > > > + }
> > > > > > + return nblocks;
> > > > > > +}
> > > > > > +
> > > > > > +int erofs_fill_holedata(int *blks, unsigned int nblocks) {
> > > > > > + int i, nholes = 0;
> > > > > > + for (i = 0; i < nblocks; i++) {
> > > > > > + if (blks[i] == -1)
> > > > > > + nholes++;
> > > > > > + else {
> > > > > > + blks[i] = nholes;
> > > > > > + if (nholes >= (i + 1))
> > > > > > + return -EINVAL;
> > > > > > + }
> > > > > > + }
> > > > > > + return 0;
> > > > > > +}
> > > > > > +
> > > > > > void erofs_inode_manager_init(void)
> > > > > > {
> > > > > > unsigned int i;
> > > > > > @@ -305,6 +360,7 @@ static bool erofs_file_is_compressible(struct
> > > > > erofs_inode *inode)
> > > > > > int erofs_write_file(struct erofs_inode *inode)
> > > > > > {
> > > > > > unsigned int nblocks, i;
> > > > > > + int *blks;
> > > > > > int ret, fd;
> > > > > >
> > > > > > if (!inode->i_size) {
> > > > > > @@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode
> > *inode)
> > > > > > /* fallback to all data uncompressed */
> > > > > > inode->datalayout = EROFS_INODE_FLAT_INLINE;
> > > > > > nblocks = inode->i_size / EROFS_BLKSIZ;
> > > > > > -
> > > > > > + blks = malloc(sizeof(int) * nblocks);
> > > > > > + nblocks = erofs_detect_holes(inode, blks);
> > > > > > + if (nblocks < 0)
> > > > > > + return nblocks;
> > > > > > + if ((ret = erofs_fill_holedata(blks, nblocks)) != 0) {
> > > > > > + return ret;
> > > > > > + }
> > > > > > ret = __allocate_inode_bh_data(inode, nblocks);
> > > > > > if (ret)
> > > > > > return ret;
> > > > > > @@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode *inode)
> > > > > > return -errno;
> > > > > >
> > > > > > for (i = 0; i < nblocks; ++i) {
> > > > > > + if (blks[i] == HOLE_BLK)
> > > > > > + continue;
> > > > > > char buf[EROFS_BLKSIZ];
> > > > > >
> > > > > > ret = read(fd, buf, EROFS_BLKSIZ);
> > > > > > @@ -962,3 +1026,4 @@ struct erofs_inode
> > > > > *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
> > > > > > return erofs_mkfs_build_tree(inode);
> > > > > > }
> > > > > >
> > > > > > +
> > > > > > --
> > > > > > 2.9.3
> > > > > >
> > > > >
> >
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
2019-12-13 7:24 ` Gao Xiang
@ 2019-12-17 18:06 ` Pratik Shinde
2019-12-18 1:25 ` Gao Xiang
0 siblings, 1 reply; 9+ messages in thread
From: Pratik Shinde @ 2019-12-17 18:06 UTC (permalink / raw)
To: Gao Xiang; +Cc: linux-erofs, miaoxie
[-- Attachment #1: Type: text/plain, Size: 10418 bytes --]
Hello Gao,
I went through my approach one more. I think maintaining an array for
tracking state of blocks (HOLE or DATA) is unnecessary. Instead We can
represent a HOLE using some structure e.g
struct hole {
start_block;
length;
}
and generate list of above type on the fly while writing a file.
Now coming to what can be store on disk for tracking hole information:
1) We can convert above generated list to a dynamic sized array & write the
array to disk. (Array can be made part of erofs_inode).
2) More memory efficient approach would be to maintain a bitmap to
represent the state of block.(one bit per block).
Along with this we can have some flags which can tell whether given file
has any holes OR not.based on that read logic can be handled.
Let me know your thoughts.
I will start shaping my RFC patch accordingly.
On Fri, Dec 13, 2019 at 12:54 PM Gao Xiang <gaoxiang25@huawei.com> wrote:
> On Fri, Dec 13, 2019 at 12:35:00PM +0530, Pratik Shinde wrote:
> > Gao,
> >
> > just returned from holidays. Let me rethink about this approach.
>
> Okay, no problem at all. :)
>
> Thanks,
> Gao Xiang
>
> >
> > --Pratik
> >
> >
> > On Wed, Dec 11, 2019, 11:14 AM Gao Xiang <gaoxiang25@huawei.com> wrote:
> >
> > > On Mon, Dec 09, 2019 at 03:18:17PM +0800, Gao Xiang wrote:
> > > > Hi Pratik,
> > > >
> > > > On Mon, Dec 09, 2019 at 12:34:50PM +0530, Pratik Shinde wrote:
> > > > > Hello Gao,
> > > > >
> > > > > Did you get any chance to look at this in detail.
> > > >
> > > > I looked into your implementation weeks before.
> > > >
> > > > As my reply in the previous email, did you see it and could you
> check it
> > > out?
> > > >
> > > > Kernel emails are not top-posting so you could scroll down to the
> end.
> > > >
> > > > > > "variable-sized inode" isn't a problem here, which can be handled
> > > > > > similar to the case of "compress indexes".
> > > > > >
> > > > > > Probably no need to write linked list to the disk but generate
> > > linked list
> > > > > > in memory when writing data on the fly, and then transfer to a
> > > > > > variable-sized
> > > > > > extent array at the time of writing inode metadata (The order is
> > > firstly
> > > > > > data
> > > > > > and then metadata in erofs-utils so it looks practical.)
> > >
> > >
> > > Some feedback words here? Do you think it is unnecessary to use such
> > > array for limited fragmented holes (either in-memory or ondisk) as
> well?
> > >
> > > Thanks,
> > > Gao Xiang
> > >
> > >
> > > >
> > > > Thanks,
> > > > Gao Xiang
> > > >
> > > > >
> > > > > --Pratik.
> > > > >
> > > > > On Wed, Dec 4, 2019, 7:52 AM Gao Xiang <gaoxiang25@huawei.com>
> wrote:
> > > > >
> > > > > > Hi Pratik,
> > > > > >
> > > > > > I'll give detailed words this weekend if you have more questions
> > > > > > since I'm busying in other stupid intra-company stuffs now...
> > > > > >
> > > > > > On Tue, Dec 03, 2019 at 07:32:50PM +0530, Pratik Shinde wrote:
> > > > > > > NOTE: The patch is not fully complete yet, with this patch I
> just
> > > want to
> > > > > > > present rough idea of what I am trying to achieve.
> > > > > > >
> > > > > > > The patch does following :
> > > > > > > 1) Detect holes (of size EROFS_BLKSIZ) in uncompressed files.
> > > > > > > 2) Keep track of holes per file.
> > > > > > >
> > > > > > > In-order to track holes, I used an array of size = (file_size /
> > > > > > blocksize)
> > > > > > > The array basically tracks number of holes before a particular
> > > logical
> > > > > > file block.
> > > > > > > e.g blks[i] = 10 meaning ith block has 10 holes before it.
> > > > > > > If a particular block is a hole we set the index to '-1'.
> > > > > > >
> > > > > > > how read logic will change:
> > > > > > > 1) currently we simply map read offset to a fs block.
> > > > > > > 2) with holes in place the calculation of block number would
> be:
> > > > > > >
> > > > > > > blkno = start_block + (offset >> block_size_shift) -
> (number of
> > > > > > > holes
> before
> > > > > > block in which offset falls)
> > > > > > >
> > > > > > > 3) If a read offset falls inside a hole (which can be found
> using
> > > above
> > > > > > array). We
> > > > > > > fill the user buffer with '\0' on the fly.
> > > > > > >
> > > > > > > through this,block no. lookup would still be performed in
> constant
> > > time.
> > > > > > >
> > > > > > > The biggest problem with this approach is - we have to store
> the
> > > hole
> > > > > > tracking
> > > > > > > array for every file to the disk.Which doesn't seems to be
> > > practical.we
> > > > > > can use a linkedlist,
> > > > > > > but that will make size of inode variable.
> > > > > >
> > > > > > "variable-sized inode" isn't a problem here, which can be handled
> > > > > > similar to the case of "compress indexes".
> > > > > >
> > > > > > Probably no need to write linked list to the disk but generate
> > > linked list
> > > > > > in memory when writing data on the fly, and then transfer to a
> > > > > > variable-sized
> > > > > > extent array at the time of writing inode metadata (The order is
> > > firstly
> > > > > > data
> > > > > > and then metadata in erofs-utils so it looks practical.)
> > > > > >
> > > > > > Thanks,
> > > > > > Gao Xiang
> > > > > >
> > > > > > >
> > > > > > > Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com>
> > > > > > > ---
> > > > > > > lib/inode.c | 67
> > > > > > ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> > > > > > > 1 file changed, 66 insertions(+), 1 deletion(-)
> > > > > > >
> > > > > > > diff --git a/lib/inode.c b/lib/inode.c
> > > > > > > index 0e19b11..af31949 100644
> > > > > > > --- a/lib/inode.c
> > > > > > > +++ b/lib/inode.c
> > > > > > > @@ -38,6 +38,61 @@ static unsigned char
> erofs_type_by_mode[S_IFMT
> > > >>
> > > > > > S_SHIFT] = {
> > > > > > >
> > > > > > > struct list_head inode_hashtable[NR_INODE_HASHTABLE];
> > > > > > >
> > > > > > > +
> > > > > > > +#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) ==
> > > start &&
> > > > > > \
> > > > > > > + roundup(end, EROFS_BLKSIZ) == end &&
> > > \
> > > > > > > + (end - start) % EROFS_BLKSIZ == 0)
> > > > > > > +#define HOLE_BLK -1
> > > > > > > +unsigned int erofs_detect_holes(struct erofs_inode *inode, int
> > > *blks)
> > > > > > > +{
> > > > > > > + int i, fd, st, en;
> > > > > > > + unsigned int nblocks;
> > > > > > > + erofs_off_t data, hole, len;
> > > > > > > +
> > > > > > > + nblocks = inode->i_size / EROFS_BLKSIZ;
> > > > > > > + for (i = 0; i < nblocks; i++)
> > > > > > > + blks[i] = 0;
> > > > > > > + fd = open(inode->i_srcpath, O_RDONLY);
> > > > > > > + if (fd < 0) {
> > > > > > > + return -errno;
> > > > > > > + }
> > > > > > > + len = lseek(fd, 0, SEEK_END);
> > > > > > > + if (lseek(fd, 0, SEEK_SET) == -1)
> > > > > > > + return -errno;
> > > > > > > + data = 0;
> > > > > > > + while (data < len) {
> > > > > > > + hole = lseek(fd, data, SEEK_HOLE);
> > > > > > > + if (hole == len)
> > > > > > > + break;
> > > > > > > + data = lseek(fd, hole, SEEK_DATA);
> > > > > > > + if (data < 0 || hole > data) {
> > > > > > > + return -EINVAL;
> > > > > > > + }
> > > > > > > + if (IS_HOLE(hole, data)) {
> > > > > > > + st = hole >> S_SHIFT;
> > > > > > > + en = data >> S_SHIFT;
> > > > > > > + nblocks -= (en - st);
> > > > > > > + for (i = st; i < en; i++)
> > > > > > > + blks[i] = HOLE_BLK;
> > > > > > > + }
> > > > > > > + }
> > > > > > > + return nblocks;
> > > > > > > +}
> > > > > > > +
> > > > > > > +int erofs_fill_holedata(int *blks, unsigned int nblocks) {
> > > > > > > + int i, nholes = 0;
> > > > > > > + for (i = 0; i < nblocks; i++) {
> > > > > > > + if (blks[i] == -1)
> > > > > > > + nholes++;
> > > > > > > + else {
> > > > > > > + blks[i] = nholes;
> > > > > > > + if (nholes >= (i + 1))
> > > > > > > + return -EINVAL;
> > > > > > > + }
> > > > > > > + }
> > > > > > > + return 0;
> > > > > > > +}
> > > > > > > +
> > > > > > > void erofs_inode_manager_init(void)
> > > > > > > {
> > > > > > > unsigned int i;
> > > > > > > @@ -305,6 +360,7 @@ static bool
> erofs_file_is_compressible(struct
> > > > > > erofs_inode *inode)
> > > > > > > int erofs_write_file(struct erofs_inode *inode)
> > > > > > > {
> > > > > > > unsigned int nblocks, i;
> > > > > > > + int *blks;
> > > > > > > int ret, fd;
> > > > > > >
> > > > > > > if (!inode->i_size) {
> > > > > > > @@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode
> > > *inode)
> > > > > > > /* fallback to all data uncompressed */
> > > > > > > inode->datalayout = EROFS_INODE_FLAT_INLINE;
> > > > > > > nblocks = inode->i_size / EROFS_BLKSIZ;
> > > > > > > -
> > > > > > > + blks = malloc(sizeof(int) * nblocks);
> > > > > > > + nblocks = erofs_detect_holes(inode, blks);
> > > > > > > + if (nblocks < 0)
> > > > > > > + return nblocks;
> > > > > > > + if ((ret = erofs_fill_holedata(blks, nblocks)) != 0) {
> > > > > > > + return ret;
> > > > > > > + }
> > > > > > > ret = __allocate_inode_bh_data(inode, nblocks);
> > > > > > > if (ret)
> > > > > > > return ret;
> > > > > > > @@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode
> *inode)
> > > > > > > return -errno;
> > > > > > >
> > > > > > > for (i = 0; i < nblocks; ++i) {
> > > > > > > + if (blks[i] == HOLE_BLK)
> > > > > > > + continue;
> > > > > > > char buf[EROFS_BLKSIZ];
> > > > > > >
> > > > > > > ret = read(fd, buf, EROFS_BLKSIZ);
> > > > > > > @@ -962,3 +1026,4 @@ struct erofs_inode
> > > > > > *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
> > > > > > > return erofs_mkfs_build_tree(inode);
> > > > > > > }
> > > > > > >
> > > > > > > +
> > > > > > > --
> > > > > > > 2.9.3
> > > > > > >
> > > > > >
> > >
>
[-- Attachment #2: Type: text/html, Size: 15987 bytes --]
^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
2019-12-17 18:06 ` Pratik Shinde
@ 2019-12-18 1:25 ` Gao Xiang
0 siblings, 0 replies; 9+ messages in thread
From: Gao Xiang @ 2019-12-18 1:25 UTC (permalink / raw)
To: Pratik Shinde; +Cc: linux-erofs, miaoxie
Hi Pratik,
I write all comments inline as before.
On Tue, Dec 17, 2019 at 11:36:19PM +0530, Pratik Shinde wrote:
> Hello Gao,
>
> I went through my approach one more. I think maintaining an array for
> tracking state of blocks (HOLE or DATA) is unnecessary. Instead We can
> represent a HOLE using some structure e.g
> struct hole {
> start_block;
> length;
> }
> and generate list of above type on the fly while writing a file.
Yes, that is what I mean. :)
>
> Now coming to what can be store on disk for tracking hole information:
> 1) We can convert above generated list to a dynamic sized array & write the
> array to disk. (Array can be made part of erofs_inode).
> 2) More memory efficient approach would be to maintain a bitmap to
> represent the state of block.(one bit per block).
I tend to use 1), because even holes are exist, they could
not be fragmented.
In addition, Using bitmap only will take more time to calc
runtimely than dynamic sized array (we could use binary search
for dynamic sized array), e.g.
12 x 13 x x x 14
if we only know the start address is 12 and we will access 14,
we need to linearly scan the bitmap in order to know how many
non-holes in advance.... It could take much time and I/O...
>
> Along with this we can have some flags which can tell whether given file
> has any holes OR not.based on that read logic can be handled.
Yes, we could use a new data mapping (in i_format)
in order to distinguish.
> Let me know your thoughts.
> I will start shaping my RFC patch accordingly.
Thanks for taking time on this.
Thanks,
Gao Xiang
>
> On Fri, Dec 13, 2019 at 12:54 PM Gao Xiang <gaoxiang25@huawei.com> wrote:
>
> > On Fri, Dec 13, 2019 at 12:35:00PM +0530, Pratik Shinde wrote:
> > > Gao,
> > >
> > > just returned from holidays. Let me rethink about this approach.
> >
> > Okay, no problem at all. :)
> >
> > Thanks,
> > Gao Xiang
> >
> > >
> > > --Pratik
> > >
> > >
> > > On Wed, Dec 11, 2019, 11:14 AM Gao Xiang <gaoxiang25@huawei.com> wrote:
> > >
> > > > On Mon, Dec 09, 2019 at 03:18:17PM +0800, Gao Xiang wrote:
> > > > > Hi Pratik,
> > > > >
> > > > > On Mon, Dec 09, 2019 at 12:34:50PM +0530, Pratik Shinde wrote:
> > > > > > Hello Gao,
> > > > > >
> > > > > > Did you get any chance to look at this in detail.
> > > > >
> > > > > I looked into your implementation weeks before.
> > > > >
> > > > > As my reply in the previous email, did you see it and could you
> > check it
> > > > out?
> > > > >
> > > > > Kernel emails are not top-posting so you could scroll down to the
> > end.
> > > > >
> > > > > > > "variable-sized inode" isn't a problem here, which can be handled
> > > > > > > similar to the case of "compress indexes".
> > > > > > >
> > > > > > > Probably no need to write linked list to the disk but generate
> > > > linked list
> > > > > > > in memory when writing data on the fly, and then transfer to a
> > > > > > > variable-sized
> > > > > > > extent array at the time of writing inode metadata (The order is
> > > > firstly
> > > > > > > data
> > > > > > > and then metadata in erofs-utils so it looks practical.)
> > > >
> > > >
> > > > Some feedback words here? Do you think it is unnecessary to use such
> > > > array for limited fragmented holes (either in-memory or ondisk) as
> > well?
> > > >
> > > > Thanks,
> > > > Gao Xiang
> > > >
> > > >
> > > > >
> > > > > Thanks,
> > > > > Gao Xiang
> > > > >
> > > > > >
> > > > > > --Pratik.
> > > > > >
> > > > > > On Wed, Dec 4, 2019, 7:52 AM Gao Xiang <gaoxiang25@huawei.com>
> > wrote:
> > > > > >
> > > > > > > Hi Pratik,
> > > > > > >
> > > > > > > I'll give detailed words this weekend if you have more questions
> > > > > > > since I'm busying in other stupid intra-company stuffs now...
> > > > > > >
> > > > > > > On Tue, Dec 03, 2019 at 07:32:50PM +0530, Pratik Shinde wrote:
> > > > > > > > NOTE: The patch is not fully complete yet, with this patch I
> > just
> > > > want to
> > > > > > > > present rough idea of what I am trying to achieve.
> > > > > > > >
> > > > > > > > The patch does following :
> > > > > > > > 1) Detect holes (of size EROFS_BLKSIZ) in uncompressed files.
> > > > > > > > 2) Keep track of holes per file.
> > > > > > > >
> > > > > > > > In-order to track holes, I used an array of size = (file_size /
> > > > > > > blocksize)
> > > > > > > > The array basically tracks number of holes before a particular
> > > > logical
> > > > > > > file block.
> > > > > > > > e.g blks[i] = 10 meaning ith block has 10 holes before it.
> > > > > > > > If a particular block is a hole we set the index to '-1'.
> > > > > > > >
> > > > > > > > how read logic will change:
> > > > > > > > 1) currently we simply map read offset to a fs block.
> > > > > > > > 2) with holes in place the calculation of block number would
> > be:
> > > > > > > >
> > > > > > > > blkno = start_block + (offset >> block_size_shift) -
> > (number of
> > > > > > > > holes
> > before
> > > > > > > block in which offset falls)
> > > > > > > >
> > > > > > > > 3) If a read offset falls inside a hole (which can be found
> > using
> > > > above
> > > > > > > array). We
> > > > > > > > fill the user buffer with '\0' on the fly.
> > > > > > > >
> > > > > > > > through this,block no. lookup would still be performed in
> > constant
> > > > time.
> > > > > > > >
> > > > > > > > The biggest problem with this approach is - we have to store
> > the
> > > > hole
> > > > > > > tracking
> > > > > > > > array for every file to the disk.Which doesn't seems to be
> > > > practical.we
> > > > > > > can use a linkedlist,
> > > > > > > > but that will make size of inode variable.
> > > > > > >
> > > > > > > "variable-sized inode" isn't a problem here, which can be handled
> > > > > > > similar to the case of "compress indexes".
> > > > > > >
> > > > > > > Probably no need to write linked list to the disk but generate
> > > > linked list
> > > > > > > in memory when writing data on the fly, and then transfer to a
> > > > > > > variable-sized
> > > > > > > extent array at the time of writing inode metadata (The order is
> > > > firstly
> > > > > > > data
> > > > > > > and then metadata in erofs-utils so it looks practical.)
> > > > > > >
> > > > > > > Thanks,
> > > > > > > Gao Xiang
> > > > > > >
> > > > > > > >
> > > > > > > > Signed-off-by: Pratik Shinde <pratikshinde320@gmail.com>
> > > > > > > > ---
> > > > > > > > lib/inode.c | 67
> > > > > > > ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
> > > > > > > > 1 file changed, 66 insertions(+), 1 deletion(-)
> > > > > > > >
> > > > > > > > diff --git a/lib/inode.c b/lib/inode.c
> > > > > > > > index 0e19b11..af31949 100644
> > > > > > > > --- a/lib/inode.c
> > > > > > > > +++ b/lib/inode.c
> > > > > > > > @@ -38,6 +38,61 @@ static unsigned char
> > erofs_type_by_mode[S_IFMT
> > > > >>
> > > > > > > S_SHIFT] = {
> > > > > > > >
> > > > > > > > struct list_head inode_hashtable[NR_INODE_HASHTABLE];
> > > > > > > >
> > > > > > > > +
> > > > > > > > +#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) ==
> > > > start &&
> > > > > > > \
> > > > > > > > + roundup(end, EROFS_BLKSIZ) == end &&
> > > > \
> > > > > > > > + (end - start) % EROFS_BLKSIZ == 0)
> > > > > > > > +#define HOLE_BLK -1
> > > > > > > > +unsigned int erofs_detect_holes(struct erofs_inode *inode, int
> > > > *blks)
> > > > > > > > +{
> > > > > > > > + int i, fd, st, en;
> > > > > > > > + unsigned int nblocks;
> > > > > > > > + erofs_off_t data, hole, len;
> > > > > > > > +
> > > > > > > > + nblocks = inode->i_size / EROFS_BLKSIZ;
> > > > > > > > + for (i = 0; i < nblocks; i++)
> > > > > > > > + blks[i] = 0;
> > > > > > > > + fd = open(inode->i_srcpath, O_RDONLY);
> > > > > > > > + if (fd < 0) {
> > > > > > > > + return -errno;
> > > > > > > > + }
> > > > > > > > + len = lseek(fd, 0, SEEK_END);
> > > > > > > > + if (lseek(fd, 0, SEEK_SET) == -1)
> > > > > > > > + return -errno;
> > > > > > > > + data = 0;
> > > > > > > > + while (data < len) {
> > > > > > > > + hole = lseek(fd, data, SEEK_HOLE);
> > > > > > > > + if (hole == len)
> > > > > > > > + break;
> > > > > > > > + data = lseek(fd, hole, SEEK_DATA);
> > > > > > > > + if (data < 0 || hole > data) {
> > > > > > > > + return -EINVAL;
> > > > > > > > + }
> > > > > > > > + if (IS_HOLE(hole, data)) {
> > > > > > > > + st = hole >> S_SHIFT;
> > > > > > > > + en = data >> S_SHIFT;
> > > > > > > > + nblocks -= (en - st);
> > > > > > > > + for (i = st; i < en; i++)
> > > > > > > > + blks[i] = HOLE_BLK;
> > > > > > > > + }
> > > > > > > > + }
> > > > > > > > + return nblocks;
> > > > > > > > +}
> > > > > > > > +
> > > > > > > > +int erofs_fill_holedata(int *blks, unsigned int nblocks) {
> > > > > > > > + int i, nholes = 0;
> > > > > > > > + for (i = 0; i < nblocks; i++) {
> > > > > > > > + if (blks[i] == -1)
> > > > > > > > + nholes++;
> > > > > > > > + else {
> > > > > > > > + blks[i] = nholes;
> > > > > > > > + if (nholes >= (i + 1))
> > > > > > > > + return -EINVAL;
> > > > > > > > + }
> > > > > > > > + }
> > > > > > > > + return 0;
> > > > > > > > +}
> > > > > > > > +
> > > > > > > > void erofs_inode_manager_init(void)
> > > > > > > > {
> > > > > > > > unsigned int i;
> > > > > > > > @@ -305,6 +360,7 @@ static bool
> > erofs_file_is_compressible(struct
> > > > > > > erofs_inode *inode)
> > > > > > > > int erofs_write_file(struct erofs_inode *inode)
> > > > > > > > {
> > > > > > > > unsigned int nblocks, i;
> > > > > > > > + int *blks;
> > > > > > > > int ret, fd;
> > > > > > > >
> > > > > > > > if (!inode->i_size) {
> > > > > > > > @@ -322,7 +378,13 @@ int erofs_write_file(struct erofs_inode
> > > > *inode)
> > > > > > > > /* fallback to all data uncompressed */
> > > > > > > > inode->datalayout = EROFS_INODE_FLAT_INLINE;
> > > > > > > > nblocks = inode->i_size / EROFS_BLKSIZ;
> > > > > > > > -
> > > > > > > > + blks = malloc(sizeof(int) * nblocks);
> > > > > > > > + nblocks = erofs_detect_holes(inode, blks);
> > > > > > > > + if (nblocks < 0)
> > > > > > > > + return nblocks;
> > > > > > > > + if ((ret = erofs_fill_holedata(blks, nblocks)) != 0) {
> > > > > > > > + return ret;
> > > > > > > > + }
> > > > > > > > ret = __allocate_inode_bh_data(inode, nblocks);
> > > > > > > > if (ret)
> > > > > > > > return ret;
> > > > > > > > @@ -332,6 +394,8 @@ int erofs_write_file(struct erofs_inode
> > *inode)
> > > > > > > > return -errno;
> > > > > > > >
> > > > > > > > for (i = 0; i < nblocks; ++i) {
> > > > > > > > + if (blks[i] == HOLE_BLK)
> > > > > > > > + continue;
> > > > > > > > char buf[EROFS_BLKSIZ];
> > > > > > > >
> > > > > > > > ret = read(fd, buf, EROFS_BLKSIZ);
> > > > > > > > @@ -962,3 +1026,4 @@ struct erofs_inode
> > > > > > > *erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,
> > > > > > > > return erofs_mkfs_build_tree(inode);
> > > > > > > > }
> > > > > > > >
> > > > > > > > +
> > > > > > > > --
> > > > > > > > 2.9.3
> > > > > > > >
> > > > > > >
> > > >
> >
^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2019-12-18 1:26 UTC | newest]
Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-12-03 14:02 [RFC] erofs-utils:code for detecting and tracking holes in uncompressed sparse files Pratik Shinde
2019-12-04 2:27 ` Gao Xiang
2019-12-09 7:04 ` Pratik Shinde
2019-12-09 7:18 ` Gao Xiang
2019-12-11 5:49 ` Gao Xiang
2019-12-13 7:05 ` Pratik Shinde
2019-12-13 7:24 ` Gao Xiang
2019-12-17 18:06 ` Pratik Shinde
2019-12-18 1:25 ` Gao Xiang
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).