Skip to contentSkip to conversation

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

RFC In review Pratik Shinde 2 participants 8 messages Dec 23, 2019 – Dec 26, 2019 Library code

lore
Share & tools
lore
#0 lore raw

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

Made some changes based on comments on previous patch :
1) defined an on disk structure for representing hole.
2) Maintain a list of this structure (per file) and dump this list to disk at the time of writing the inode to disk.

---
 include/erofs/internal.h |   8 +++-
 lib/inode.c              | 108 ++++++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 110 insertions(+), 6 deletions(-)
include/erofs/internal.h +7 -1
index e13adda..863ef8a 100644
@@ -63,7 +63,7 @@ struct erofs_sb_info {
 extern struct erofs_sb_info sbi;
 
 struct erofs_inode {
-	struct list_head i_hash, i_subdirs, i_xattrs;
+	struct list_head i_hash, i_subdirs, i_xattrs, i_holes;
 
 	unsigned int i_count;
 	struct erofs_inode *i_parent;
@@ -93,6 +93,7 @@ struct erofs_inode {
 
 	unsigned int xattr_isize;
 	unsigned int extent_isize;
+	unsigned int holes_isize;
 
 	erofs_nid_t nid;
 	struct erofs_buffer_head *bh;
@@ -139,5 +140,10 @@ static inline const char *erofs_strerror(int err)
 	return msg;
 }
 
+struct erofs_hole {
+	erofs_blk_t st;
+	u32 len;
+	struct list_head next;
+};
 #endif
 
lib/inode.c +103 -5

150 lines not on this page · raw message

Signature · 1 line
2.9.3
#1 lore raw

Hi Pratik,

Thanks for keeping the work. :)
Some inlined comments below as before.

Quoted 31 lines · Pratik Shinde

Made some changes based on comments on previous patch :
1) defined an on disk structure for representing hole.
2) Maintain a list of this structure (per file) and dump this list to disk at the time of writing the inode to disk.

---
 include/erofs/internal.h |   8 +++-
 lib/inode.c              | 108 ++++++++++++++++++++++++++++++++++++++++++++---
 2 files changed, 110 insertions(+), 6 deletions(-)
include/erofs/internal.h +2 -1
index e13adda..863ef8a 100644
@@ -63,7 +63,7 @@ struct erofs_sb_info {
 extern struct erofs_sb_info sbi;
 
 struct erofs_inode {
-	struct list_head i_hash, i_subdirs, i_xattrs;
+	struct list_head i_hash, i_subdirs, i_xattrs, i_holes;
 
 	unsigned int i_count;
 	struct erofs_inode *i_parent;
@@ -93,6 +93,7 @@ struct erofs_inode {
 
 	unsigned int xattr_isize;
 	unsigned int extent_isize;
+	unsigned int holes_isize;
 
 	erofs_nid_t nid;
 	struct erofs_buffer_head *bh;

include/erofs/internal.h static inline const char *erofs_strerror(int err) · line 147

Quoted 8 lines
include/erofs/internal.h +5 -0
@@ -139,5 +140,10 @@ static inline const char *erofs_strerror(int err)
 	return msg;
 }
 
+struct erofs_hole {
+	erofs_blk_t st;
+	u32 len;
+	struct list_head next;
+};

How about recording all extents rather than holes? since it's more useful for later random read access.

struct erofs_extent_node {
struct list_head next;

erofs_blk_t lblk; /* logical start address */
erofs_blk_t pblk; /* physical start address */
u32 len; /* extent length in blocks */
};

Quoted 76 lines
include/erofs/internal.h +0 -0
 #endif
 
lib/inode.c +66 -0
index 0e19b11..20bbf06 100644
@@ -38,6 +38,85 @@ 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,
+				struct list_head *holes, unsigned int *htimes)
+{
+	int fd, st, en;
+	unsigned int nholes = 0;
+	erofs_off_t data, hole, len;
+	struct erofs_hole *eh;
+
+	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;
+			eh = malloc(sizeof(struct erofs_hole));
+			if (eh == NULL)
+				return -ENOMEM;
+			eh->st = st;
+			eh->len = (en - st);
+			list_add_tail(&eh->next, holes);
+			nholes += eh->len;
+			*htimes += 1;
+		}
+	}
+	return nholes;
+}
+
+bool erofs_ishole(erofs_blk_t blk, struct list_head holes)
+{
+	if (list_empty(&holes))
+		return false;
+	struct erofs_hole *eh;
+	list_for_each_entry(eh, &holes, next) {
+		if (eh->st > blk)
+			return false;
+		if (eh->st <= blk && (eh->st + eh->len - 1) >= blk)
+			return true;
+	}
+	return false;
+}
+
+char *erofs_create_holes_buffer(struct list_head *holes, unsigned int size)
+{
+	struct erofs_hole *eh;
+	char *buf;
+	unsigned int p = 0;
+
+	buf = malloc(size);

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

Quoted 10 lines
lib/inode.c +10 -0
+	if (buf == NULL)
+		return ERR_PTR(-ENOMEM);
+	list_for_each_entry(eh, holes, next) {
+		*(__le32 *)(buf + p) = cpu_to_le32(eh->st);
+		p += sizeof(__le32);
+		*(__le32 *)(buf + p) = cpu_to_le32(eh->len);
+		p += sizeof(__le32);
+		list_del(&eh->next);
+		free(eh);
+	}

How about introducing some extent header

/* 12-byte alignment */

struct erofs_inline_extent_header {
	/* e.g. we need to record how many total extents here at least. */
	...
};

and some ondisk extent representation.

struct erofs_extent {
	__le32 ee_lblk;
	__le32 ee_pblk;
	/*
	 * most significant 4 bits reserved for flags and should be 0
	 * now, maximum 256M blocks (8TB) for an extent.
	 */
	__le32 ee_len;
};

(see fs/ext4/ext4_extents.h for ext4 ondisk definitions)

And I'd like to call this inline extent representation (for limited extents) since we could consider some powerful representation (e.g. using B+ tree) in the future for complicated requirement, so we have to reserve i_u.raw_blkaddr in erofs_inode to 0 for now (in order to indicate extra B+-tree blocks).

Quoted 7 lines
lib/inode.c +3 -0
+	return buf;
+}
+
 void erofs_inode_manager_init(void)
 {
 	unsigned int i;

lib/inode.c static bool erofs_file_is_compressible(struct erofs_inode *inode) · line 389

Quoted 8 lines
lib/inode.c +1 -1
@@ -304,7 +383,7 @@ static bool erofs_file_is_compressible(struct erofs_inode *inode)
 
 int erofs_write_file(struct erofs_inode *inode)
 {
-	unsigned int nblocks, i;
+	unsigned int nblocks, i, nholes, hitems = 0;
 	int ret, fd;
 
 	if (!inode->i_size) {

The fallback condition from compress file to uncompress file should be updated and give a new data_mapping for this mode as well, but that is minor for now.

Thanks,
Gao Xiang

Quoted 64 lines
lib/inode.c +23 -4
@@ -322,16 +401,24 @@ 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;
-
-	ret = __allocate_inode_bh_data(inode, nblocks);
+	nholes = erofs_detect_holes(inode, &inode->i_holes, &hitems);
+	if (nholes < 0)
+		return nholes;
+	inode->holes_isize = (sizeof(struct erofs_hole) -
+			      sizeof(struct list_head)) * hitems;
+	if (nblocks < 0)
+		return nblocks;
+	ret = __allocate_inode_bh_data(inode, nblocks - nholes);
 	if (ret)
 		return ret;
-
 	fd = open(inode->i_srcpath, O_RDONLY | O_BINARY);
 	if (fd < 0)
 		return -errno;
 
 	for (i = 0; i < nblocks; ++i) {
+		if (erofs_ishole(i, inode->i_holes)) {
+			continue;
+		}
 		char buf[EROFS_BLKSIZ];
 
 		ret = read(fd, buf, EROFS_BLKSIZ);
@@ -479,8 +566,19 @@ static bool erofs_bh_flush_write_inode(struct erofs_buffer_head *bh)
 		if (ret)
 			return false;
 		free(inode->compressmeta);
+		off += inode->extent_isize;
 	}
 
+	if (inode->holes_isize) {
+		char *holes = erofs_create_holes_buffer(&inode->i_holes,
+							inode->holes_isize);
+		if (IS_ERR(holes))
+			return false;
+		ret = dev_write(holes, off, inode->holes_isize);
+		free(holes);
+		if (ret)
+			return false;
+	}
 	inode->bh = NULL;
 	erofs_iput(inode);
 	return erofs_bh_flush_generic_end(bh);
@@ -737,6 +835,7 @@ struct erofs_inode *erofs_new_inode(void)
 
 	init_list_head(&inode->i_subdirs);
 	init_list_head(&inode->i_xattrs);
+	init_list_head(&inode->i_holes);
 
 	inode->idata_size = 0;
 	inode->xattr_isize = 0;
@@ -961,4 +1060,3 @@ 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,

Thanks for the review.
If I understand correctly , you wish to keep track of every extent assigned to the file.
in case of file without any holes in it, there will single extent representing the entire file.

Also, the current block no. lookup happens in constant time. (since we only record the start blk no.)
If we use extent record for finding given block no. it can't be done in constant time correct ? (maybe in LogN)

I think I don't fully understand reason for recording extents assigned to a file.Since the current design
is already time and space optimized & there are no deletions happening. Is it for some future requirement ?

--Pratik.

Quoted 275 lines · Gao Xiang

Hi Pratik,

Thanks for keeping the work. :)
Some inlined comments below as before.

Quoted 7 lines · Pratik Shinde

Made some changes based on comments on previous patch :
1) defined an on disk structure for representing hole.
2) Maintain a list of this structure (per file) and dump this list to disk at the time of writing the inode to disk.

---
 include/erofs/internal.h |   8 +++-
 lib/inode.c              | 108

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

Quoted 24 lines
 2 files changed, 110 insertions(+), 6 deletions(-)
include/erofs/internal.h +2 -1
index e13adda..863ef8a 100644
@@ -63,7 +63,7 @@ struct erofs_sb_info {
 extern struct erofs_sb_info sbi;
 
 struct erofs_inode {
-     struct list_head i_hash, i_subdirs, i_xattrs;
+     struct list_head i_hash, i_subdirs, i_xattrs, i_holes;
 
      unsigned int i_count;
      struct erofs_inode *i_parent;
@@ -93,6 +93,7 @@ struct erofs_inode {
 
      unsigned int xattr_isize;
      unsigned int extent_isize;
+     unsigned int holes_isize;
 
      erofs_nid_t nid;
      struct erofs_buffer_head *bh;

include/erofs/internal.h static inline const char *erofs_strerror(int err) · line 147

Quoted 8 lines
include/erofs/internal.h +5 -0
@@ -139,5 +140,10 @@ static inline const char *erofs_strerror(int err)
      return msg;
 }
 
+struct erofs_hole {
+     erofs_blk_t st;
+     u32 len;
+     struct list_head next;
+};

How about recording all extents rather than holes? since it's more useful for later random read access.

struct erofs_extent_node {
struct list_head next;

erofs_blk_t lblk; /* logical start address */
erofs_blk_t pblk; /* physical start address */
u32 len; /* extent length in blocks */
};

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

Quoted 7 lines
include/erofs/internal.h +0 -0
 #endif
 
lib/inode.c +0 -0
index 0e19b11..20bbf06 100644
@@ -38,6 +38,85 @@ 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 unsigned char erofs_type_by_mode[S_IFMT >> S_SHIFT] = {

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

*htimes)

Quoted 43 lines
lib/inode.c +43 -0
+{
+     int fd, st, en;
+     unsigned int nholes = 0;
+     erofs_off_t data, hole, len;
+     struct erofs_hole *eh;
+
+     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;
+                     eh = malloc(sizeof(struct erofs_hole));
+                     if (eh == NULL)
+                             return -ENOMEM;
+                     eh->st = st;
+                     eh->len = (en - st);
+                     list_add_tail(&eh->next, holes);
+                     nholes += eh->len;
+                     *htimes += 1;
+             }
+     }
+     return nholes;
+}
+
+bool erofs_ishole(erofs_blk_t blk, struct list_head holes)
+{
+     if (list_empty(&holes))
+             return false;
+     struct erofs_hole *eh;

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

Quoted 10 lines
lib/inode.c +10 -0
+     list_for_each_entry(eh, &holes, next) {
+             if (eh->st > blk)
+                     return false;
+             if (eh->st <= blk && (eh->st + eh->len - 1) >= blk)
+                     return true;
+     }
+     return false;
+}
+
+char *erofs_create_holes_buffer(struct list_head *holes, unsigned int

size)

Quoted 6 lines
lib/inode.c +6 -0
+{
+     struct erofs_hole *eh;
+     char *buf;
+     unsigned int p = 0;
+
+     buf = malloc(size);

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

Quoted 10 lines
lib/inode.c +10 -0
+     if (buf == NULL)
+             return ERR_PTR(-ENOMEM);
+     list_for_each_entry(eh, holes, next) {
+             *(__le32 *)(buf + p) = cpu_to_le32(eh->st);
+             p += sizeof(__le32);
+             *(__le32 *)(buf + p) = cpu_to_le32(eh->len);
+             p += sizeof(__le32);
+             list_del(&eh->next);
+             free(eh);
+     }

How about introducing some extent header

/* 12-byte alignment */

struct erofs_inline_extent_header {
        /* e.g. we need to record how many total extents here at least. */
        ...
};

and some ondisk extent representation.

struct erofs_extent {
        __le32 ee_lblk;
        __le32 ee_pblk;
        /*
         * most significant 4 bits reserved for flags and should be 0
         * now, maximum 256M blocks (8TB) for an extent.
         */
        __le32 ee_len;
};

(see fs/ext4/ext4_extents.h for ext4 ondisk definitions)

And I'd like to call this inline extent representation (for limited extents) since we could consider some powerful representation (e.g. using B+ tree) in the future for complicated requirement, so we have to reserve i_u.raw_blkaddr in erofs_inode to 0 for now (in order to indicate extra B+-tree blocks).

lib/inode.c static bool erofs_file_is_compressible(struct

Quoted 7 lines
lib/inode.c +3 -0
+     return buf;
+}
+
 void erofs_inode_manager_init(void)
 {
      unsigned int i;
@@ -304,7 +383,7 @@ static bool erofs_file_is_compressible(struct

erofs_inode *inode)

lib/inode.c static bool erofs_file_is_compressible(struct erofs_inode *inode) · line 389

Quoted 8 lines
lib/inode.c +1 -1
 int erofs_write_file(struct erofs_inode *inode)
 {
-     unsigned int nblocks, i;
+     unsigned int nblocks, i, nholes, hitems = 0;
      int ret, fd;
 
      if (!inode->i_size) {

The fallback condition from compress file to uncompress file should be updated
and give a new data_mapping for this mode as well, but that is minor for now.

Thanks,
Gao Xiang

lib/inode.c static bool erofs_bh_flush_write_inode(struct

Quoted 29 lines
lib/inode.c +11 -3
@@ -322,16 +401,24 @@ 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;
-
-     ret = __allocate_inode_bh_data(inode, nblocks);
+     nholes = erofs_detect_holes(inode, &inode->i_holes, &hitems);
+     if (nholes < 0)
+             return nholes;
+     inode->holes_isize = (sizeof(struct erofs_hole) -
+                           sizeof(struct list_head)) * hitems;
+     if (nblocks < 0)
+             return nblocks;
+     ret = __allocate_inode_bh_data(inode, nblocks - nholes);
      if (ret)
              return ret;
-
      fd = open(inode->i_srcpath, O_RDONLY | O_BINARY);
      if (fd < 0)
              return -errno;
 
      for (i = 0; i < nblocks; ++i) {
+             if (erofs_ishole(i, inode->i_holes)) {
+                     continue;
+             }
              char buf[EROFS_BLKSIZ];
 
              ret = read(fd, buf, EROFS_BLKSIZ);
@@ -479,8 +566,19 @@ static bool erofs_bh_flush_write_inode(struct

erofs_buffer_head *bh)

lib/inode.c static bool erofs_bh_flush_write_inode(struct erofs_buffer_head *bh)

Quoted 9 lines
lib/inode.c +4 -0
              if (ret)
                      return false;
              free(inode->compressmeta);
+             off += inode->extent_isize;
      }
 
+     if (inode->holes_isize) {
+             char *holes = erofs_create_holes_buffer(&inode->i_holes,
+

inode->holes_isize);

lib/inode.c struct erofs_inode

Quoted 19 lines
lib/inode.c +8 -0
+             if (IS_ERR(holes))
+                     return false;
+             ret = dev_write(holes, off, inode->holes_isize);
+             free(holes);
+             if (ret)
+                     return false;
+     }
      inode->bh = NULL;
      erofs_iput(inode);
      return erofs_bh_flush_generic_end(bh);
@@ -737,6 +835,7 @@ struct erofs_inode *erofs_new_inode(void)
 
      init_list_head(&inode->i_subdirs);
      init_list_head(&inode->i_xattrs);
+     init_list_head(&inode->i_holes);
 
      inode->idata_size = 0;
      inode->xattr_isize = 0;
@@ -961,4 +1060,3 @@ struct erofs_inode

*erofs_mkfs_build_tree_from_path(struct erofs_inode *parent,

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

2.9.3

#3 lore raw

Hi Pratik,

Quoted 8 lines · Pratik Shinde

Hello Gao,

Thanks for the review.
If I understand correctly , you wish to keep track of every extent assigned to the file.
in case of file without any holes in it, there will single extent representing the entire file.

Quoted 4 lines

Also, the current block no. lookup happens in constant time. (since we only record the start blk no.)
If we use extent record for finding given block no. it can't be done in constant time correct ? (maybe in LogN)

Could I ask a question?
In short, how can we use the proposal approach to read random blocks in constant time O(1)?

e.g.
if you have two holes 2...4 7...10 in a file with 12 blocks.

if we want to random access block 11, only block number 1,5,6,11 were saved one by one (maybe p1,p2,p3,p4).

How can we get the physical address (p4) of block 11 directly without scanning the previous holes?

Thanks,
Gao Xiang

Quoted 7 lines

I think I don't fully understand reason for recording extents assigned to a file.Since the current design
is already time and space optimized & there are no deletions happening. Is it for some future requirement ?

--Pratik.

#4 lore raw

Hi Gao,

No no. What I am saying is - in the current code (excluding all my changes) the block lookup will happens in constant time. with only hole list it won't be O(1) time but rather we have to traverse the holes list. (say in binary search way).
what I don't understand is - what is the purpose of tracking data extents. hope you get it.

--Pratik.

Quoted 46 lines · Gao Xiang

Hi Pratik,

Quoted 4 lines · Pratik Shinde

Hello Gao,

Thanks for the review.
If I understand correctly , you wish to keep track of every extent

assigned

Quoted 5 lines

to the file.
in case of file without any holes in it, there will single extent representing the entire file.

Also, the current block no. lookup happens in constant time. (since we

only

Quoted 3 lines

record the start blk no.)
If we use extent record for finding given block no. it can't be done in constant time correct ? (maybe in LogN)

Could I ask a question?
In short, how can we use the proposal approach to read random blocks in constant time O(1)?

e.g.
if you have two holes 2...4 7...10 in a file with 12 blocks.

if we want to random access block 11, only block number 1,5,6,11 were saved one by one (maybe p1,p2,p3,p4).

How can we get the physical address (p4) of block 11 directly without scanning the previous holes?

Thanks,
Gao Xiang

Quoted 2 lines

I think I don't fully understand reason for recording extents assigned

to a

Quoted 5 lines

file.Since the current design
is already time and space optimized & there are no deletions happening. Is it for some future requirement ?

--Pratik.

#5 lore raw
Quoted 4 lines · Pratik Shinde

Hi Gao,

No no. What I am saying is - in the current code (excluding all my changes) the block lookup will happens in constant time. with only hole list it

Not only lookup but other interfaces such as fiemap, that is why called flat mode and fast path.

Quoted 4 lines

won't be O(1) time but rather we have to traverse the holes list. (say in binary search way).
what I don't understand is - what is the purpose of tracking data extents. hope you get it.

Mode plain and inline are called flat modes, which is the most common case of regular and dir files. You can see that's the fastest path for most file accesses (minimum metadata).

The reason why don't extend the flat modes but introduce another new sparse mode for 3 main reasons:
1) introduce a complete enhanced new extent table (or later B+-tree);
2) we don't even know how many holes in the file if we only read inode base metadata, some extra header (no matter extent or hole header) need to be readed in advance;
3) Old kernel backward compatibility need to be considered, not all files are sparsed, and we need to get them work properly, and rest files are sparsed, we need to block such files from accessed by old kernels;

Note that i_format is for such use, so we can introduce sparse mode with some enhanced on-disk representation (but with more metadata read amplification than flat modes).

So if files without holes it should be considered as flat modes (fast path), and then considering the slow path --- upcoming sparse mode.

The purpose of tracking data extents is we could then use it for deduping, repeated data or data redirect. Hole can only be 0 though.

Thanks,
Gao Xiang

Quoted 3 lines

--Pratik.

#6 lore raw

Thanks Gao.

Now I understand the purpose.
So with i_format we will be able to recognize which path to take. i.e fast path (flat mode) or slow path(i.e to search through extent list). I am working on it.

--Pratik.

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

Hi Gao,

No no. What I am saying is - in the current code (excluding all my

changes)

Quoted 1 line

the block lookup will happens in constant time. with only hole list it

Not only lookup but other interfaces such as fiemap, that is why called flat mode and fast path.

Quoted 3 lines

won't be O(1) time but rather we have to traverse the holes list. (say in binary search way).
what I don't understand is - what is the purpose of tracking data

extents.

Quoted 1 line

hope you get it.

Mode plain and inline are called flat modes, which is the most common case of regular and dir files. You can see that's the fastest path for most file accesses (minimum metadata).

The reason why don't extend the flat modes but introduce another new sparse mode for 3 main reasons:
1) introduce a complete enhanced new extent table (or later B+-tree);
2) we don't even know how many holes in the file if we only read inode base metadata, some extra header (no matter extent or hole header) need to be readed in advance;
3) Old kernel backward compatibility need to be considered, not all files are sparsed, and we need to get them work properly, and rest files are sparsed, we need to block such files from accessed by old kernels;

Note that i_format is for such use, so we can introduce sparse mode with some enhanced on-disk representation (but with more metadata read amplification than flat modes).

So if files without holes it should be considered as flat modes (fast path), and then considering the slow path --- upcoming sparse mode.

The purpose of tracking data extents is we could then use it for deduping, repeated data or data redirect. Hole can only be 0 though.

Thanks,
Gao Xiang

Quoted 3 lines

--Pratik.

#7 lore raw
Quoted 6 lines · Pratik Shinde

Thanks Gao.

Now I understand the purpose.
So with i_format we will be able to recognize which path to take. i.e fast path (flat mode) or slow path(i.e to search through extent list). I am working on it.

Thanks. Yes, that is the original consideration of i_format design and sorry for some misrepresentations in the previous email such as what I meant is "old kernel forward compatibility", etc..

But I think the final i_format new mode number is minor for now (I can also assign a new number based on your patch) because I'd like to rearrange this field for better scalability as an extra patch in advance together with your patch.

we can get the main new extent approach in shape first. :-)

Thanks,
Gao Xiang

Quoted 54 lines

--Pratik.

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

Hi Gao,

No no. What I am saying is - in the current code (excluding all my

changes)

Quoted 1 line

the block lookup will happens in constant time. with only hole list it

Not only lookup but other interfaces such as fiemap, that is why called flat mode and fast path.

Quoted 3 lines

won't be O(1) time but rather we have to traverse the holes list. (say in binary search way).
what I don't understand is - what is the purpose of tracking data

extents.

Quoted 1 line

hope you get it.

Mode plain and inline are called flat modes, which is the most common case of regular and dir files. You can see that's the fastest path for most file accesses (minimum metadata).

The reason why don't extend the flat modes but introduce another new sparse mode for 3 main reasons:
1) introduce a complete enhanced new extent table (or later B+-tree);
2) we don't even know how many holes in the file if we only read inode base metadata, some extra header (no matter extent or hole header) need to be readed in advance;
3) Old kernel backward compatibility need to be considered, not all files are sparsed, and we need to get them work properly, and rest files are sparsed, we need to block such files from accessed by old kernels;

Note that i_format is for such use, so we can introduce sparse mode with some enhanced on-disk representation (but with more metadata read amplification than flat modes).

So if files without holes it should be considered as flat modes (fast path), and then considering the slow path --- upcoming sparse mode.

The purpose of tracking data extents is we could then use it for deduping, repeated data or data redirect. Hole can only be 0 though.

Thanks,
Gao Xiang

Quoted 3 lines

--Pratik.