erofs-utils:code for detecting and tracking holes in uncompressed sparse files.
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
@@ -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
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 sizeEROFS_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
Signed-off-by Pratik Shinde <[email protected]>--- lib/inode.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 66 insertions(+), 1 deletion(-)lib/inode.c +66
-1@@ -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
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 sizeEROFS_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 beforeblock 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 XiangQuoted 4 lines
Signed-off-by Pratik Shinde <[email protected]>--- 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@@ -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
-0struct 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
-1int 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
-1return erofs_mkfs_build_tree (inode); } + --2.9.3
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 sizeEROFS_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 beforeblock 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 XiangQuoted 4 lines
Signed-off-by Pratik Shinde <[email protected]>--- 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@@ -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
-0struct 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
-1int 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
-1return erofs_mkfs_build_tree (inode); } + --2.9.3
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 XiangQuoted 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 sizeEROFS_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 beforeblock 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 XiangQuoted 4 lines
Signed-off-by Pratik Shinde <[email protected]>--- 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@@ -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
-0struct 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
-1int 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
-1return erofs_mkfs_build_tree (inode); } + --2.9.3
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 isfirstly
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 XiangQuoted 16 lines
Thanks,
Gao XiangQuoted 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 sizeEROFS_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 beforeblock 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 isfirstly
Quoted 19 lines
Quoted 19 lines
Quoted 18 lines
data
and then metadata in erofs-utils so it looks practical.)Thanks,
Gao XiangQuoted 4 lines
Signed-off-by Pratik Shinde <[email protected]>--- lib/inode.c | 67++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
Quoted 7 lines
1 file changed, 66 insertions(+), 1 deletion(-)lib/inode.c +0
-0@@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMTQuoted 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
-0struct 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
-0int 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
-1return erofs_mkfs_build_tree (inode); } + --2.9.3
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 isfirstly
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 XiangQuoted 16 lines
Thanks,
Gao XiangQuoted 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 sizeEROFS_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 beforeblock 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 isfirstly
Quoted 19 lines
Quoted 19 lines
Quoted 18 lines
data
and then metadata in erofs-utils so it looks practical.)Thanks,
Gao XiangQuoted 4 lines
Signed-off-by Pratik Shinde <[email protected]>--- lib/inode.c | 67++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-
Quoted 7 lines
1 file changed, 66 insertions(+), 1 deletion(-)lib/inode.c +0
-0@@ -38,6 +38,61 @@ static unsigned char erofs_type_by_mode[S_IFMTQuoted 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
-0struct 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
-0int 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
-1return erofs_mkfs_build_tree (inode); } + --2.9.3
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 XiangQuoted 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 isQuoted 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 XiangQuoted 8 lines
Thanks,
Gao XiangQuoted 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 sizeEROFS_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 wouldbe:
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 isfirstly
Quoted 10 lines
Quoted 10 lines
Quoted 10 lines
data
and then metadata in erofs-utils so it looks practical.)Thanks,
Gao XiangQuoted 4 lines
Signed-off-by Pratik Shinde <[email protected]>--- lib/inode.c | 67Quoted 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@@ -38,6 +38,61 @@ static unsigned charerofs_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
-0struct 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 boolerofs_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
-0int 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
-0return -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
-1return erofs_mkfs_build_tree (inode); } + --2.9.3
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 oferofs_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 XiangQuoted 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 isQuoted 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 XiangQuoted 8 lines
Thanks,
Gao XiangQuoted 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 sizeEROFS_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 wouldbe:
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 isfirstly
Quoted 10 lines
Quoted 10 lines
Quoted 10 lines
data
and then metadata in erofs-utils so it looks practical.)Thanks,
Gao XiangQuoted 4 lines
Signed-off-by Pratik Shinde <[email protected]>--- lib/inode.c | 67Quoted 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@@ -38,6 +38,61 @@ static unsigned charerofs_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
-0struct 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 boolerofs_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
-0int 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
-0return -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
-1return erofs_mkfs_build_tree (inode); } + --2.9.3