Skip to contentSkip to conversation

erofs-utils: lib: treat data blocks filled with 0s as a hole

PATCH Superseded Sandeep Dhavale via Linux-erofs 2 participants 3 messages Apr 9, 2024 – Apr 13, 2024 Library code

v2 of 3 Superseded Latest is v3 →

lore
Share & tools
lore
#0 lore raw

PATCH v2 1/1 erofs-utils: lib: treat data blocks filled with 0s as a hole

Add optimization to treat data blocks filled with 0s as a hole. Even though diskspace savings are comparable to chunk based or dedupe, having no block assigned saves us redundant disk IOs during read.

To detect blocks filled with zeros during chunking, we insert block filled with zeros (zerochunk) in the hashmap. If we detect a possible dedupe, we map it to the hole so there is no physical block assigned.

---
Changes since v1:
- Instead of checking every block for 0s word by word, add a zerochunk in blobs during init. So we effectively detect the zero blocks by comparing the hash.

 include/erofs/blobchunk.h |  2 +-
 lib/blobchunk.c           | 41 ++++++++++++++++++++++++++++++++++++---
 mkfs/main.c               |  2 +-
 3 files changed, 40 insertions(+), 5 deletions(-)
include/erofs/blobchunk.h +1 -1
index a674640..ebe2efe 100644
@@ -23,7 +23,7 @@ int erofs_write_zero_inode(struct erofs_inode *inode);
 int tarerofs_write_chunkes(struct erofs_inode *inode, erofs_off_t data_offset);
 int erofs_mkfs_dump_blobs(struct erofs_sb_info *sbi);
 void erofs_blob_exit(void);
-int erofs_blob_init(const char *blobfile_path);
+int erofs_blob_init(const char *blobfile_path, erofs_off_t chunksize);
 int erofs_mkfs_init_devices(struct erofs_sb_info *sbi, unsigned int devices);
 
 #ifdef __cplusplus
lib/blobchunk.c +38 -3

65 lines not on this page · raw message

mkfs/main.c +1 -1
index 2fb4a57..d632f74 100644
@@ -1255,7 +1255,7 @@ int main(int argc, char **argv)
 	}
 
 	if (cfg.c_chunkbits) {
-		err = erofs_blob_init(cfg.c_blobdev_path);
+		err = erofs_blob_init(cfg.c_blobdev_path, 1 << cfg.c_chunkbits);
 		if (err)
 			return 1;
 	}
Signature · 1 line
2.44.0.478.gd926399ef9-goog
#1 lore raw

Hi Sandeep,

Quoted 37 lines · Sandeep Dhavale

Add optimization to treat data blocks filled with 0s as a hole. Even though diskspace savings are comparable to chunk based or dedupe, having no block assigned saves us redundant disk IOs during read.

To detect blocks filled with zeros during chunking, we insert block filled with zeros (zerochunk) in the hashmap. If we detect a possible dedupe, we map it to the hole so there is no physical block assigned.

---
Changes since v1:
- Instead of checking every block for 0s word by word, add a zerochunk in blobs during init. So we effectively detect the zero blocks by comparing the hash.

  include/erofs/blobchunk.h |  2 +-
  lib/blobchunk.c           | 41 ++++++++++++++++++++++++++++++++++++---
  mkfs/main.c               |  2 +-
  3 files changed, 40 insertions(+), 5 deletions(-)
include/erofs/blobchunk.h +1 -1
index a674640..ebe2efe 100644
@@ -23,7 +23,7 @@ int erofs_write_zero_inode(struct erofs_inode *inode);
  int tarerofs_write_chunkes(struct erofs_inode *inode, erofs_off_t data_offset);
  int erofs_mkfs_dump_blobs(struct erofs_sb_info *sbi);
  void erofs_blob_exit(void);
-int erofs_blob_init(const char *blobfile_path);
+int erofs_blob_init(const char *blobfile_path, erofs_off_t chunksize);
  int erofs_mkfs_init_devices(struct erofs_sb_info *sbi, unsigned int devices);
 
  #ifdef __cplusplus
lib/blobchunk.c +0 -0
index 641e3d4..87c153f 100644

lib/blobchunk.c int erofs_blob_write_chunked_file(struct erofs_inode *inode, int fd, · line 330

Quoted 9 lines
lib/blobchunk.c +0 -1
@@ -323,13 +323,21 @@ int erofs_blob_write_chunked_file(struct erofs_inode *inode, int fd,
  			ret = -EIO;
  			goto err;
  		}
-
  		chunk = erofs_blob_getchunk(sbi, chunkdata, len);
  		if (IS_ERR(chunk)) {
  			ret = PTR_ERR(chunk);
  			goto err;
  		}

Sorry for late reply since I'm working on multi-threaded mkfs.

Can erofs_blob_getchunk directly return &erofs_holechunk? I mean,

static struct erofs_blobchunk *erofs_blob_getchunk(struct erofs_sb_info *sbi,
u8 *buf, erofs_off_t chunksize)
{
...

	chunk = hashmap_get_from_hash(&blob_hashmap, hash, sha256);
	if (chunk) {
		DBG_BUGON(chunksize != chunk->chunksize);

		if (chunk->blkaddr == erofs_holechunk.blkaddr)
			chunk = &erofs_holechunk;

		sbi->saved_by_deduplication += chunksize;
		erofs_dbg("Found duplicated chunk at %u", chunk->blkaddr);
		return chunk;
	}

...
}

lib/blobchunk.c int erofs_blob_write_chunked_file(struct erofs_inode *inode, int fd, · line 336

Quoted 6 lines
lib/blobchunk.c +5 -0
+		if (chunk->blkaddr == erofs_holechunk.blkaddr) {
+			*(void **)idx++ = &erofs_holechunk;
+			erofs_update_minextblks(sbi, interval_start, pos,
+						&minextblks);
+			interval_start = pos + len;

I guess several zerochunks can also be merged? is this line an expected behavior?

lib/blobchunk.c int erofs_blob_write_chunked_file(struct erofs_inode *inode, int fd, · line 343

Quoted 7 lines
lib/blobchunk.c +4 -0
+			lastch = NULL;
+			continue;
+		}
+
  		if (lastch && (lastch->device_id != chunk->device_id ||
  		    erofs_pos(sbi, lastch->blkaddr) + lastch->chunksize !=
  		    erofs_pos(sbi, chunk->blkaddr))) {

I guess we could form a helper like
static bool erofs_blob_can_merge(struct erofs_sb_info *sbi,
struct erofs_blobchunk *lastch, struct erofs_blobchunk *chunk)

{
	if (lastch == &erofs_holechunk && chunk == &erofs_holechunk)
		return true;
	if (lastch->device_id == chunk->device_id &&
	    erofs_pos(sbi, lastch->blkaddr) + lastch->chunksize ==
	    erofs_pos(sbi, chunk->blkaddr))
		return true;
	return false;
}
		if (lastch && erofs_blob_can_merge(sbi, lastch, chunk)) {
			...
		}
Quoted 8 lines
lib/blobchunk.c +3 -1
@@ -540,7 +548,34 @@ void erofs_blob_exit(void)
  	}
  }
 
-int erofs_blob_init(const char *blobfile_path)
+static int erofs_insert_zerochunk(erofs_off_t chunksize)
+{
+	u8 *zeros;

lib/blobchunk.c void erofs_blob_exit(void) · line 563

Quoted 10 lines
lib/blobchunk.c +10 -0
+	struct erofs_blobchunk *chunk;
+	u8 sha256[32];
+	unsigned int hash;
+
+	zeros = calloc(1, chunksize);
+	if (!zeros)
+		return -ENOMEM;
+
+	erofs_sha256(zeros, chunksize, sha256);
+	hash = memhash(sha256, sizeof(sha256));

zeros needs to be freed here I guess:

	free(zeros);

Thanks,
Gao Xiang

Quoted 13 lines
lib/blobchunk.c +13 -0
+	chunk = malloc(sizeof(struct erofs_blobchunk));
+	if (!chunk)
+		return -ENOMEM;> +
+	chunk->chunksize = chunksize;
+	/* treat chunk filled with zeros as hole */
+	chunk->blkaddr = erofs_holechunk.blkaddr;
+	memcpy(chunk->sha256, sha256, sizeof(sha256));
+
+	hashmap_entry_init(&chunk->ent, hash);
+	hashmap_add(&blob_hashmap, chunk);
+	return 0;
+}
+
#2 lore raw
Quoted 45 lines · Gao Xiang

Hi Sandeep,

Quoted 41 lines · Sandeep Dhavale

Add optimization to treat data blocks filled with 0s as a hole. Even though diskspace savings are comparable to chunk based or dedupe, having no block assigned saves us redundant disk IOs during read.

To detect blocks filled with zeros during chunking, we insert block filled with zeros (zerochunk) in the hashmap. If we detect a possible dedupe, we map it to the hole so there is no physical block assigned.

---
Changes since v1:
- Instead of checking every block for 0s word by word, add a zerochunk in blobs during init. So we effectively detect the zero blocks by comparing the hash.

  include/erofs/blobchunk.h |  2 +-
  lib/blobchunk.c           | 41 ++++++++++++++++++++++++++++++++++++---
  mkfs/main.c               |  2 +-
  3 files changed, 40 insertions(+), 5 deletions(-)
include/erofs/blobchunk.h +1 -1
index a674640..ebe2efe 100644
@@ -23,7 +23,7 @@ int erofs_write_zero_inode(struct erofs_inode *inode);
  int tarerofs_write_chunkes(struct erofs_inode *inode, erofs_off_t data_offset);
  int erofs_mkfs_dump_blobs(struct erofs_sb_info *sbi);
  void erofs_blob_exit(void);
-int erofs_blob_init(const char *blobfile_path);
+int erofs_blob_init(const char *blobfile_path, erofs_off_t chunksize);
  int erofs_mkfs_init_devices(struct erofs_sb_info *sbi, unsigned int devices);
 
  #ifdef __cplusplus
lib/blobchunk.c +0 -1
index 641e3d4..87c153f 100644
@@ -323,13 +323,21 @@ int erofs_blob_write_chunked_file(struct erofs_inode *inode, int fd,
                      ret = -EIO;
                      goto err;
              }
-
Quoted 9 lines

lib/blobchunk.c int erofs_blob_write_chunked_file(struct erofs_inode *inode, int fd, · line 330

Quoted 5 lines
lib/blobchunk.c +0 -0
              chunk = erofs_blob_getchunk(sbi, chunkdata, len);
              if (IS_ERR(chunk)) {
                      ret = PTR_ERR(chunk);
                      goto err;
              }

Sorry for late reply since I'm working on multi-threaded mkfs.

Hi Gao,
Thank you for the feedback!

Quoted 1 line

Can erofs_blob_getchunk directly return &erofs_holechunk? I mean,

Ok, I will re-work this part.

Quoted 27 lines

static struct erofs_blobchunk *erofs_blob_getchunk(struct erofs_sb_info *sbi,
u8 *buf, erofs_off_t chunksize)
{
...

        chunk = hashmap_get_from_hash(&blob_hashmap, hash, sha256);
        if (chunk) {
                DBG_BUGON(chunksize != chunk->chunksize);

                if (chunk->blkaddr == erofs_holechunk.blkaddr)
                        chunk = &erofs_holechunk;

                sbi->saved_by_deduplication += chunksize;
                erofs_dbg("Found duplicated chunk at %u", chunk->blkaddr);
                return chunk;
        }

...
}

lib/blobchunk.c int erofs_blob_write_chunked_file(struct erofs_inode *inode, int fd, · line 336

Quoted 6 lines
lib/blobchunk.c +5 -0
+             if (chunk->blkaddr == erofs_holechunk.blkaddr) {
+                     *(void **)idx++ = &erofs_holechunk;
+                     erofs_update_minextblks(sbi, interval_start, pos,
+                                             &minextblks);
+                     interval_start = pos + len;
Quoted 3 lines

I guess several zerochunks can also be merged? is this line an expected behavior?

My understanding was for minextblks we need to consider only contiguous physical, in other words, assigned blocks. Let me think more about it.

Quoted 49 lines

lib/blobchunk.c int erofs_blob_write_chunked_file(struct erofs_inode *inode, int fd, · line 343

Quoted 7 lines
lib/blobchunk.c +4 -0
+                     lastch = NULL;
+                     continue;
+             }
+
              if (lastch && (lastch->device_id != chunk->device_id ||
                  erofs_pos(sbi, lastch->blkaddr) + lastch->chunksize !=
                  erofs_pos(sbi, chunk->blkaddr))) {

I guess we could form a helper like
static bool erofs_blob_can_merge(struct erofs_sb_info *sbi,
struct erofs_blobchunk *lastch, struct erofs_blobchunk *chunk)

{
        if (lastch == &erofs_holechunk && chunk == &erofs_holechunk)
                return true;
        if (lastch->device_id == chunk->device_id &&
            erofs_pos(sbi, lastch->blkaddr) + lastch->chunksize ==
            erofs_pos(sbi, chunk->blkaddr))
                return true;
        return false;
}
                if (lastch && erofs_blob_can_merge(sbi, lastch, chunk)) {
                        ...
                }
Quoted 8 lines
lib/blobchunk.c +3 -1
@@ -540,7 +548,34 @@ void erofs_blob_exit(void)
      }
  }
 
-int erofs_blob_init(const char *blobfile_path)
+static int erofs_insert_zerochunk(erofs_off_t chunksize)
+{
+     u8 *zeros;

lib/blobchunk.c void erofs_blob_exit(void) · line 563

Quoted 10 lines
lib/blobchunk.c +10 -0
+     struct erofs_blobchunk *chunk;
+     u8 sha256[32];
+     unsigned int hash;
+
+     zeros = calloc(1, chunksize);
+     if (!zeros)
+             return -ENOMEM;
+
+     erofs_sha256(zeros, chunksize, sha256);
+     hash = memhash(sha256, sizeof(sha256));

zeros needs to be freed here I guess:

Quoted 1 line
        free(zeros);

That's oversight on my part, thanks for the catch!

Thanks,
Sandeep.

Quoted 17 lines

Thanks,
Gao Xiang

Quoted 13 lines
lib/blobchunk.c +13 -0
+     chunk = malloc(sizeof(struct erofs_blobchunk));
+     if (!chunk)
+             return -ENOMEM;> +
+     chunk->chunksize = chunksize;
+     /* treat chunk filled with zeros as hole */
+     chunk->blkaddr = erofs_holechunk.blkaddr;
+     memcpy(chunk->sha256, sha256, sizeof(sha256));
+
+     hashmap_entry_init(&chunk->ent, hash);
+     hashmap_add(&blob_hashmap, chunk);
+     return 0;
+}
+