Skip to contentSkip to conversation

erofs-utils:code for detecting and tracking holes in uncompressed sparse files.

RFC Superseded Pratik Shinde 2 participants 9 messages Dec 3, 2019 – Dec 18, 2019 Library code

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

RFC 1/1 erofs-utils:code for detecting and tracking holes in uncompressed sparse files.

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.

---
 lib/inode.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 66 insertions(+), 1 deletion(-)
lib/inode.c +66 -1
index 0e19b11..af31949 100644
@@ -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);
 }
 
+
Signature · 1 line
2.9.3
#1 lore raw

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...

Quoted 19 lines · Pratik Shinde

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)

Quoted 8 lines

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

Quoted 112 lines
---
 lib/inode.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 66 insertions(+), 1 deletion(-)
lib/inode.c +66 -1
index 0e19b11..af31949 100644
@@ -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);
 }
 
+
Signature · 1 line
2.9.3
#2 lore raw

Hello Gao,

Did you get any chance to look at this in detail.

--Pratik.

Quoted 171 lines · Gao Xiang

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...

Quoted 8 lines · Pratik Shinde

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)

Quoted 1 line

The array basically tracks number of holes before a particular logical

file block.

Quoted 9 lines

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)

Quoted 2 lines

3) If a read offset falls inside a hole (which can be found using above

array). We

Quoted 5 lines

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

Quoted 1 line

array for every file to the disk.Which doesn't seems to be practical.we

can use a linkedlist,

Quoted 1 line

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

Quoted 4 lines
---
 lib/inode.c | 67

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

lib/inode.c static unsigned char erofs_type_by_mode[S_IFMT >>

Quoted 7 lines
 1 file changed, 66 insertions(+), 1 deletion(-)
lib/inode.c +0 -0
index 0e19b11..af31949 100644
@@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT >>

S_SHIFT] = {

lib/inode.c static unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {

Quoted 5 lines
lib/inode.c +2 -0
 struct list_head inode_hashtable[NR_INODE_HASHTABLE];
 
+
+#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) == start &&
      \

lib/inode.c static bool erofs_file_is_compressible(struct

Quoted 57 lines
lib/inode.c +53 -0
+                          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)

lib/inode.c struct erofs_inode

Quoted 32 lines
lib/inode.c +10 -1
 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,

Quoted 7 lines
lib/inode.c +1 -1
      return erofs_mkfs_build_tree(inode);
 }
 
+
--

2.9.3

#3 lore raw

Hi Pratik,

Quoted 3 lines · Pratik Shinde

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.

Quoted 9 lines
Quoted 9 lines

"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

Quoted 176 lines

--Pratik.

Quoted 171 lines · Gao Xiang

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...

Quoted 8 lines · Pratik Shinde

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)

Quoted 1 line

The array basically tracks number of holes before a particular logical

file block.

Quoted 9 lines

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)

Quoted 2 lines

3) If a read offset falls inside a hole (which can be found using above

array). We

Quoted 5 lines

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

Quoted 1 line

array for every file to the disk.Which doesn't seems to be practical.we

can use a linkedlist,

Quoted 1 line

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

Quoted 4 lines
---
 lib/inode.c | 67

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

lib/inode.c static unsigned char erofs_type_by_mode[S_IFMT >>

Quoted 7 lines
 1 file changed, 66 insertions(+), 1 deletion(-)
lib/inode.c +0 -0
index 0e19b11..af31949 100644
@@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT >>

S_SHIFT] = {

lib/inode.c static unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {

Quoted 5 lines
lib/inode.c +2 -0
 struct list_head inode_hashtable[NR_INODE_HASHTABLE];
 
+
+#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) == start &&
      \

lib/inode.c static bool erofs_file_is_compressible(struct

Quoted 57 lines
lib/inode.c +53 -0
+                          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)

lib/inode.c struct erofs_inode

Quoted 32 lines
lib/inode.c +10 -1
 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,

Quoted 7 lines
lib/inode.c +1 -1
      return erofs_mkfs_build_tree(inode);
 }
 
+
--

2.9.3

#4 lore raw
Quoted 5 lines · Gao Xiang

Hi Pratik,

Quoted 2 lines · Pratik Shinde

Hello Gao,

Quoted 17 lines
Quoted 1 line

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.

Quoted 9 lines
Quoted 9 lines

"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

Quoted 180 lines

Thanks,
Gao Xiang

Quoted 176 lines

--Pratik.

Quoted 171 lines · Gao Xiang

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...

Quoted 8 lines · Pratik Shinde

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)

Quoted 1 line

The array basically tracks number of holes before a particular logical

file block.

Quoted 9 lines

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)

Quoted 2 lines

3) If a read offset falls inside a hole (which can be found using above

array). We

Quoted 5 lines

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

Quoted 1 line

array for every file to the disk.Which doesn't seems to be practical.we

can use a linkedlist,

Quoted 1 line

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

Quoted 4 lines
---
 lib/inode.c | 67

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

lib/inode.c static unsigned char erofs_type_by_mode[S_IFMT >>

Quoted 7 lines
 1 file changed, 66 insertions(+), 1 deletion(-)
lib/inode.c +0 -0
index 0e19b11..af31949 100644
@@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT >>

S_SHIFT] = {

lib/inode.c static unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {

Quoted 5 lines
lib/inode.c +2 -0
 struct list_head inode_hashtable[NR_INODE_HASHTABLE];
 
+
+#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) == start &&
      \

lib/inode.c static bool erofs_file_is_compressible(struct

Quoted 57 lines
lib/inode.c +53 -0
+                          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)

lib/inode.c struct erofs_inode

Quoted 32 lines
lib/inode.c +10 -1
 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,

Quoted 7 lines
lib/inode.c +1 -1
      return erofs_mkfs_build_tree(inode);
 }
 
+
--

2.9.3

#5 lore raw

Gao,

just returned from holidays. Let me rethink about this approach.

--Pratik

Quoted 229 lines · Gao Xiang
Quoted 10 lines · Gao Xiang

Hi Pratik,

Quoted 3 lines · Pratik Shinde

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?

Quoted 7 lines

Kernel emails are not top-posting so you could scroll down to the end.

Quoted 4 lines
Quoted 4 lines

"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

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

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

Quoted 16 lines

Thanks,
Gao Xiang

Quoted 12 lines

--Pratik.

Quoted 7 lines · Gao Xiang

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...

Quoted 1 line · Pratik Shinde

NOTE: The patch is not fully complete yet, with this patch I just

want to

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
Quoted 7 lines

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)

Quoted 1 line

The array basically tracks number of holes before a particular

logical

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

file block.

Quoted 7 lines

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:

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 2 lines

blkno = start_block + (offset >> block_size_shift) - (number of
holes before

block in which offset falls)

Quoted 2 lines

3) If a read offset falls inside a hole (which can be found using

above

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

array). We

Quoted 3 lines

fill the user buffer with '\0' on the fly.

through this,block no. lookup would still be performed in constant

time.

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

The biggest problem with this approach is - we have to store the

hole

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

tracking

Quoted 1 line

array for every file to the disk.Which doesn't seems to be

practical.we

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

can use a linkedlist,

Quoted 1 line

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

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

Quoted 19 lines
Quoted 19 lines
Quoted 18 lines

data
and then metadata in erofs-utils so it looks practical.)

Thanks,
Gao Xiang

Quoted 4 lines
---
 lib/inode.c | 67

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

Quoted 7 lines
 1 file changed, 66 insertions(+), 1 deletion(-)
lib/inode.c +0 -0
index 0e19b11..af31949 100644
@@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

S_SHIFT] = {

lib/inode.c static unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {

Quoted 5 lines
lib/inode.c +2 -0
 struct list_head inode_hashtable[NR_INODE_HASHTABLE];
 
+
+#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) ==

start &&

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
      \
Quoted 1 line
lib/inode.c +1 -0
+                          roundup(end, EROFS_BLKSIZ) == end &&

\

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

lib/inode.c static unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {

Quoted 3 lines
lib/inode.c +3 -0
+                         (end - start) % EROFS_BLKSIZ == 0)
+#define HOLE_BLK             -1
+unsigned int erofs_detect_holes(struct erofs_inode *inode, int

*blks)

Quoted 54 lines
Quoted 54 lines
Quoted 54 lines

lib/inode.c static bool erofs_file_is_compressible(struct

Quoted 53 lines
lib/inode.c +49 -0
+{
+     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)

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

lib/inode.c int erofs_write_file(struct erofs_inode

Quoted 8 lines
lib/inode.c +1 -0
 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)

Quoted 33 lines
Quoted 33 lines
Quoted 33 lines

lib/inode.c struct erofs_inode

Quoted 24 lines
lib/inode.c +9 -1
      /* 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,

Quoted 7 lines
lib/inode.c +1 -1
      return erofs_mkfs_build_tree(inode);
 }
 
+
--

2.9.3

#6 lore raw
Quoted 3 lines · Pratik Shinde

Gao,

just returned from holidays. Let me rethink about this approach.

Okay, no problem at all. :)

Thanks,
Gao Xiang

Quoted 235 lines

--Pratik

Quoted 229 lines · Gao Xiang
Quoted 10 lines · Gao Xiang

Hi Pratik,

Quoted 3 lines · Pratik Shinde

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?

Quoted 7 lines

Kernel emails are not top-posting so you could scroll down to the end.

Quoted 4 lines
Quoted 4 lines

"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

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

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

Quoted 16 lines

Thanks,
Gao Xiang

Quoted 12 lines

--Pratik.

Quoted 7 lines · Gao Xiang

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...

Quoted 1 line · Pratik Shinde

NOTE: The patch is not fully complete yet, with this patch I just

want to

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
Quoted 7 lines

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)

Quoted 1 line

The array basically tracks number of holes before a particular

logical

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

file block.

Quoted 7 lines

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:

Quoted 5 lines
Quoted 5 lines
Quoted 5 lines
Quoted 2 lines

blkno = start_block + (offset >> block_size_shift) - (number of
holes before

block in which offset falls)

Quoted 2 lines

3) If a read offset falls inside a hole (which can be found using

above

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

array). We

Quoted 3 lines

fill the user buffer with '\0' on the fly.

through this,block no. lookup would still be performed in constant

time.

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

The biggest problem with this approach is - we have to store the

hole

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

tracking

Quoted 1 line

array for every file to the disk.Which doesn't seems to be

practical.we

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

can use a linkedlist,

Quoted 1 line

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

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

Quoted 19 lines
Quoted 19 lines
Quoted 18 lines

data
and then metadata in erofs-utils so it looks practical.)

Thanks,
Gao Xiang

Quoted 4 lines
---
 lib/inode.c | 67

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

Quoted 7 lines
 1 file changed, 66 insertions(+), 1 deletion(-)
lib/inode.c +0 -0
index 0e19b11..af31949 100644
@@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMT
Quoted 6 lines
Quoted 6 lines
Quoted 6 lines

S_SHIFT] = {

lib/inode.c static unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {

Quoted 5 lines
lib/inode.c +2 -0
 struct list_head inode_hashtable[NR_INODE_HASHTABLE];
 
+
+#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) ==

start &&

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
      \
Quoted 1 line
lib/inode.c +1 -0
+                          roundup(end, EROFS_BLKSIZ) == end &&

\

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

lib/inode.c static unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {

Quoted 3 lines
lib/inode.c +3 -0
+                         (end - start) % EROFS_BLKSIZ == 0)
+#define HOLE_BLK             -1
+unsigned int erofs_detect_holes(struct erofs_inode *inode, int

*blks)

Quoted 54 lines
Quoted 54 lines
Quoted 54 lines

lib/inode.c static bool erofs_file_is_compressible(struct

Quoted 53 lines
lib/inode.c +49 -0
+{
+     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)

Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

lib/inode.c int erofs_write_file(struct erofs_inode

Quoted 8 lines
lib/inode.c +1 -0
 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)

Quoted 33 lines
Quoted 33 lines
Quoted 33 lines

lib/inode.c struct erofs_inode

Quoted 24 lines
lib/inode.c +9 -1
      /* 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,

Quoted 7 lines
lib/inode.c +1 -1
      return erofs_mkfs_build_tree(inode);
 }
 
+
--

2.9.3

#7 lore raw

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.

Quoted 260 lines · Gao Xiang
Quoted 3 lines · Pratik Shinde

Gao,

just returned from holidays. Let me rethink about this approach.

Okay, no problem at all. :)

Thanks,
Gao Xiang

Quoted 17 lines

--Pratik

Quoted 11 lines · Gao Xiang
Quoted 10 lines · Gao Xiang

Hi Pratik,

Quoted 3 lines · Pratik Shinde

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

Quoted 3 lines
Quoted 3 lines

out?

Quoted 2 lines

Kernel emails are not top-posting so you could scroll down to the

end.

Quoted 9 lines
Quoted 9 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

"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

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

Quoted 7 lines
Quoted 7 lines

firstly

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

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?

Quoted 13 lines
Quoted 13 lines

Thanks,
Gao Xiang

Quoted 8 lines

Thanks,
Gao Xiang

Quoted 4 lines

--Pratik.

On Wed, Dec 4, 2019, 7:52 AM Gao Xiang <[email protected]>

Quoted 8 lines · wrote:
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

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...

Quoted 1 line · Pratik Shinde

NOTE: The patch is not fully complete yet, with this patch I

just

Quoted 10 lines
Quoted 10 lines

want to

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
Quoted 7 lines

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)

Quoted 1 line

The array basically tracks number of holes before a particular

Quoted 8 lines
Quoted 8 lines

logical

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

file block.

Quoted 6 lines

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:

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

blkno = start_block + (offset >> block_size_shift) -

(number of

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

holes

before

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

block in which offset falls)

Quoted 2 lines

3) If a read offset falls inside a hole (which can be found

using

Quoted 5 lines
Quoted 5 lines

above

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

array). We

Quoted 3 lines

fill the user buffer with '\0' on the fly.

through this,block no. lookup would still be performed in

constant

Quoted 3 lines
Quoted 3 lines

time.

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

The biggest problem with this approach is - we have to store

the

Quoted 26 lines
Quoted 26 lines

hole

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

tracking

Quoted 1 line

array for every file to the disk.Which doesn't seems to be

practical.we

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

can use a linkedlist,

Quoted 1 line

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

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

Quoted 10 lines
Quoted 10 lines
Quoted 10 lines

data
and then metadata in erofs-utils so it looks practical.)

Thanks,
Gao Xiang

Quoted 4 lines
---
 lib/inode.c | 67
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

lib/inode.c static unsigned char

Quoted 7 lines
 1 file changed, 66 insertions(+), 1 deletion(-)
lib/inode.c +0 -0
index 0e19b11..af31949 100644
@@ -38,6 +38,61 @@ static unsigned char

erofs_type_by_mode[S_IFMT

Quoted 60 lines
Quoted 60 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

S_SHIFT] = {

lib/inode.c static unsigned char · line 41

Quoted 5 lines
lib/inode.c +2 -0
 struct list_head inode_hashtable[NR_INODE_HASHTABLE];
 
+
+#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) ==

start &&

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
      \
Quoted 1 line
lib/inode.c +1 -0
+                          roundup(end, EROFS_BLKSIZ) == end &&

\

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

lib/inode.c static unsigned char · line 45

Quoted 3 lines
lib/inode.c +3 -0
+                         (end - start) % EROFS_BLKSIZ == 0)
+#define HOLE_BLK             -1
+unsigned int erofs_detect_holes(struct erofs_inode *inode, int

*blks)

Quoted 45 lines
Quoted 45 lines
Quoted 45 lines
Quoted 45 lines
lib/inode.c +45 -0
+{
+     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;
+             }
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

lib/inode.c static bool

Quoted 8 lines
lib/inode.c +4 -0
+     }
+     return 0;
+}
+
 void erofs_inode_manager_init(void)
 {
      unsigned int i;
@@ -305,6 +360,7 @@ static bool

erofs_file_is_compressible(struct

Quoted 10 lines
Quoted 10 lines
Quoted 9 lines
Quoted 9 lines
Quoted 9 lines

erofs_inode *inode)

lib/inode.c int erofs_write_file(struct erofs_inode

Quoted 8 lines
lib/inode.c +1 -0
 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)

Quoted 15 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
lib/inode.c +3 -1
      /* 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)
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

lib/inode.c int erofs_write_file(struct erofs_inode

Quoted 8 lines
lib/inode.c +4 -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)

Quoted 19 lines
Quoted 19 lines
Quoted 18 lines
Quoted 18 lines
Quoted 18 lines

lib/inode.c struct erofs_inode

Quoted 9 lines
lib/inode.c +2 -0
              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,

Quoted 7 lines
lib/inode.c +1 -1
      return erofs_mkfs_build_tree(inode);
 }
 
+
--

2.9.3

#8 lore raw

Hi Pratik,

I write all comments inline as before.

Quoted 10 lines · Pratik Shinde

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. :)

Quoted 6 lines

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...

Quoted 3 lines

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.

Quoted 2 lines

Let me know your thoughts.
I will start shaping my RFC patch accordingly.

Thanks for taking time on this.

Thanks,
Gao Xiang

Quoted 263 lines · Gao Xiang
Quoted 261 lines · Pratik Shinde
Quoted 3 lines

Gao,

just returned from holidays. Let me rethink about this approach.

Okay, no problem at all. :)

Thanks,
Gao Xiang

Quoted 17 lines

--Pratik

Quoted 11 lines · Gao Xiang
Quoted 10 lines · Gao Xiang

Hi Pratik,

Quoted 3 lines · Pratik Shinde

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

Quoted 3 lines
Quoted 3 lines

out?

Quoted 2 lines

Kernel emails are not top-posting so you could scroll down to the

end.

Quoted 9 lines
Quoted 9 lines
Quoted 5 lines
Quoted 5 lines
Quoted 5 lines

"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

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

Quoted 7 lines
Quoted 7 lines

firstly

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

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?

Quoted 13 lines
Quoted 13 lines

Thanks,
Gao Xiang

Quoted 8 lines

Thanks,
Gao Xiang

Quoted 4 lines

--Pratik.

On Wed, Dec 4, 2019, 7:52 AM Gao Xiang <[email protected]>

Quoted 8 lines · wrote:
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

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...

Quoted 1 line · Pratik Shinde

NOTE: The patch is not fully complete yet, with this patch I

just

Quoted 10 lines
Quoted 10 lines

want to

Quoted 9 lines
Quoted 9 lines
Quoted 9 lines
Quoted 7 lines

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)

Quoted 1 line

The array basically tracks number of holes before a particular

Quoted 8 lines
Quoted 8 lines

logical

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

file block.

Quoted 6 lines

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:

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

blkno = start_block + (offset >> block_size_shift) -

(number of

Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line
Quoted 1 line

holes

before

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

block in which offset falls)

Quoted 2 lines

3) If a read offset falls inside a hole (which can be found

using

Quoted 5 lines
Quoted 5 lines

above

Quoted 4 lines
Quoted 4 lines
Quoted 4 lines

array). We

Quoted 3 lines

fill the user buffer with '\0' on the fly.

through this,block no. lookup would still be performed in

constant

Quoted 3 lines
Quoted 3 lines

time.

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

The biggest problem with this approach is - we have to store

the

Quoted 26 lines
Quoted 26 lines

hole

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines

tracking

Quoted 1 line

array for every file to the disk.Which doesn't seems to be

practical.we

Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

can use a linkedlist,

Quoted 1 line

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

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

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

Quoted 10 lines
Quoted 10 lines
Quoted 10 lines

data
and then metadata in erofs-utils so it looks practical.)

Thanks,
Gao Xiang

Quoted 4 lines
---
 lib/inode.c | 67
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-

lib/inode.c static unsigned char

Quoted 7 lines
 1 file changed, 66 insertions(+), 1 deletion(-)
lib/inode.c +0 -0
index 0e19b11..af31949 100644
@@ -38,6 +38,61 @@ static unsigned char

erofs_type_by_mode[S_IFMT

Quoted 60 lines
Quoted 60 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines

S_SHIFT] = {

lib/inode.c static unsigned char · line 41

Quoted 5 lines
lib/inode.c +2 -0
 struct list_head inode_hashtable[NR_INODE_HASHTABLE];
 
+
+#define IS_HOLE(start, end) (roundup(start, EROFS_BLKSIZ) ==

start &&

Quoted 2 lines
Quoted 2 lines
Quoted 2 lines
      \
Quoted 1 line
lib/inode.c +1 -0
+                          roundup(end, EROFS_BLKSIZ) == end &&

\

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines

lib/inode.c static unsigned char · line 45

Quoted 3 lines
lib/inode.c +3 -0
+                         (end - start) % EROFS_BLKSIZ == 0)
+#define HOLE_BLK             -1
+unsigned int erofs_detect_holes(struct erofs_inode *inode, int

*blks)

Quoted 45 lines
Quoted 45 lines
Quoted 45 lines
Quoted 45 lines
lib/inode.c +45 -0
+{
+     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;
+             }
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

lib/inode.c static bool

Quoted 8 lines
lib/inode.c +4 -0
+     }
+     return 0;
+}
+
 void erofs_inode_manager_init(void)
 {
      unsigned int i;
@@ -305,6 +360,7 @@ static bool

erofs_file_is_compressible(struct

Quoted 10 lines
Quoted 10 lines
Quoted 9 lines
Quoted 9 lines
Quoted 9 lines

erofs_inode *inode)

lib/inode.c int erofs_write_file(struct erofs_inode

Quoted 8 lines
lib/inode.c +1 -0
 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)

Quoted 15 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
Quoted 7 lines
lib/inode.c +3 -1
      /* 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)
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines
Quoted 8 lines

lib/inode.c int erofs_write_file(struct erofs_inode

Quoted 8 lines
lib/inode.c +4 -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)

Quoted 19 lines
Quoted 19 lines
Quoted 18 lines
Quoted 18 lines
Quoted 18 lines

lib/inode.c struct erofs_inode

Quoted 9 lines
lib/inode.c +2 -0
              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,

Quoted 7 lines
lib/inode.c +1 -1
      return erofs_mkfs_build_tree(inode);
 }
 
+
--

2.9.3