[PATCH v3 1/2] erofs-utils: get rid of `end' argument from erofs_mapbh()

[PATCH v3 1/2] erofs-utils: get rid of `end' argument from erofs_mapbh()

[Gao Xiang via Linux-erofs]

From: Hu Weiwen <sehuww@mail.scut.edu.cn>

`end` arguement is completely broken now. Also, it could
be readded later if needed.

Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
Signed-off-by: Gao Xiang <hsiangkao@aol.com>
---
Hi Weiwen,
Sorry for late update. I've cleaned up the patchset (mainly [PATCH 2/2],
could you kindly recheck it on your side if it works, and help me update
the commit message of [PATCH 2/2] as well?

Thanks,
Gao Xiang

 include/erofs/cache.h |  2 +-
 lib/cache.c           |  6 ++----
 lib/compress.c        |  2 +-
 lib/inode.c           | 10 +++++-----
 lib/xattr.c           |  2 +-
 mkfs/main.c           |  2 +-
 6 files changed, 11 insertions(+), 13 deletions(-)

diff --git a/include/erofs/cache.h b/include/erofs/cache.h
index 8c171f5a130e..f8dff67b9736 100644
--- a/include/erofs/cache.h
+++ b/include/erofs/cache.h
@@ -95,7 +95,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 struct erofs_buffer_head *erofs_battach(struct erofs_buffer_head *bh,
 					int type, unsigned int size);
 
-erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb, bool end);
+erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb);
 bool erofs_bflush(struct erofs_buffer_block *bb);
 
 void erofs_bdrop(struct erofs_buffer_head *bh, bool tryrevoke);
diff --git a/lib/cache.c b/lib/cache.c
index 0d5c4a5d48de..32a58311f563 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -257,16 +257,14 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
 	return blkaddr;
 }
 
-erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb, bool end)
+erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb)
 {
 	struct erofs_buffer_block *t, *nt;
 
 	if (!bb || bb->blkaddr == NULL_ADDR) {
 		list_for_each_entry_safe(t, nt, &blkh.list, list) {
-			if (!end && (t == bb || nt == &blkh))
-				break;
 			(void)__erofs_mapbh(t);
-			if (end && t == bb)
+			if (t == bb)
 				break;
 		}
 	}
diff --git a/lib/compress.c b/lib/compress.c
index 86db940b6edd..2b1f93c389ff 100644
--- a/lib/compress.c
+++ b/lib/compress.c
@@ -416,7 +416,7 @@ int erofs_write_compressed_file(struct erofs_inode *inode)
 
 	memset(compressmeta, 0, Z_EROFS_LEGACY_MAP_HEADER_SIZE);
 
-	blkaddr = erofs_mapbh(bh->block, true);	/* start_blkaddr */
+	blkaddr = erofs_mapbh(bh->block);	/* start_blkaddr */
 	ctx.blkaddr = blkaddr;
 	ctx.metacur = compressmeta + Z_EROFS_LEGACY_MAP_HEADER_SIZE;
 	ctx.head = ctx.tail = 0;
diff --git a/lib/inode.c b/lib/inode.c
index d0b4d51f3e3d..4ed6aed25243 100644
--- a/lib/inode.c
+++ b/lib/inode.c
@@ -148,7 +148,7 @@ static int __allocate_inode_bh_data(struct erofs_inode *inode,
 	inode->bh_data = bh;
 
 	/* get blkaddr of the bh */
-	ret = erofs_mapbh(bh->block, true);
+	ret = erofs_mapbh(bh->block);
 	DBG_BUGON(ret < 0);
 
 	/* write blocks except for the tail-end block */
@@ -522,7 +522,7 @@ int erofs_prepare_tail_block(struct erofs_inode *inode)
 		bh->op = &erofs_skip_write_bhops;
 
 		/* get blkaddr of bh */
-		ret = erofs_mapbh(bh->block, true);
+		ret = erofs_mapbh(bh->block);
 		DBG_BUGON(ret < 0);
 		inode->u.i_blkaddr = bh->block->blkaddr;
 
@@ -632,7 +632,7 @@ int erofs_write_tail_end(struct erofs_inode *inode)
 		int ret;
 		erofs_off_t pos;
 
-		erofs_mapbh(bh->block, true);
+		erofs_mapbh(bh->block);
 		pos = erofs_btell(bh, true) - EROFS_BLKSIZ;
 		ret = dev_write(inode->idata, pos, inode->idata_size);
 		if (ret)
@@ -879,7 +879,7 @@ void erofs_fixup_meta_blkaddr(struct erofs_inode *rootdir)
 	struct erofs_buffer_head *const bh = rootdir->bh;
 	erofs_off_t off, meta_offset;
 
-	erofs_mapbh(bh->block, true);
+	erofs_mapbh(bh->block);
 	off = erofs_btell(bh, false);
 
 	if (off > rootnid_maxoffset)
@@ -898,7 +898,7 @@ erofs_nid_t erofs_lookupnid(struct erofs_inode *inode)
 	if (!bh)
 		return inode->nid;
 
-	erofs_mapbh(bh->block, true);
+	erofs_mapbh(bh->block);
 	off = erofs_btell(bh, false);
 
 	meta_offset = blknr_to_addr(sbi.meta_blkaddr);
diff --git a/lib/xattr.c b/lib/xattr.c
index 49ebb9c2f539..8b7bcb126fe9 100644
--- a/lib/xattr.c
+++ b/lib/xattr.c
@@ -575,7 +575,7 @@ int erofs_build_shared_xattrs_from_path(const char *path)
 	}
 	bh->op = &erofs_skip_write_bhops;
 
-	erofs_mapbh(bh->block, true);
+	erofs_mapbh(bh->block);
 	off = erofs_btell(bh, false);
 
 	sbi.xattr_blkaddr = off / EROFS_BLKSIZ;
diff --git a/mkfs/main.c b/mkfs/main.c
index abd48be0fa4f..d9c4c7fff5c1 100644
--- a/mkfs/main.c
+++ b/mkfs/main.c
@@ -304,7 +304,7 @@ int erofs_mkfs_update_super_block(struct erofs_buffer_head *bh,
 		round_up(EROFS_SUPER_END, EROFS_BLKSIZ);
 	char *buf;
 
-	*blocks         = erofs_mapbh(NULL, true);
+	*blocks         = erofs_mapbh(NULL);
 	sb.blocks       = cpu_to_le32(*blocks);
 	sb.root_nid     = cpu_to_le16(root_nid);
 	memcpy(sb.uuid, sbi.uuid, sizeof(sb.uuid));
-- 
2.24.0

[PATCH v3 2/2] erofs-utils: optimize mkfs to O(N), N = #files

[Gao Xiang via Linux-erofs]

From: Hu Weiwen <sehuww@mail.scut.edu.cn>

When using EROFS to pack our dataset which consists of millions of
files, mkfs.erofs is very slow compared with mksquashfs.

The bottleneck is `erofs_balloc` and `erofs_mapbh` function, which
iterate over all previously allocated buffer blocks, making the
complexity of the algrithm O(N^2) where N is the number of files.

With this patch:

* global `last_mapped_block` is mantained to avoid full scan in
  `erofs_mapbh` function.

* global `non_full_buffer_blocks` mantains a list of buffer block for
  each type and each possible remaining bytes in the block. Then it is
  used to identify the most suitable blocks in future `erofs_balloc`,
  avoiding full scan.

Some new data structure is allocated in this patch, more RAM usage is
expected, but not much. When I test it with ImageNet dataset (1.33M
files), 7GiB RAM is consumed, and it takes about 4 hours. Most time is
spent on IO.

Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
Signed-off-by: Gao Xiang <hsiangkao@aol.com>
---
 include/erofs/cache.h |  1 +
 lib/cache.c           | 97 ++++++++++++++++++++++++++++++++++++++-----
 2 files changed, 87 insertions(+), 11 deletions(-)

diff --git a/include/erofs/cache.h b/include/erofs/cache.h
index f8dff67b9736..611ca5b8432b 100644
--- a/include/erofs/cache.h
+++ b/include/erofs/cache.h
@@ -39,6 +39,7 @@ struct erofs_buffer_head {
 
 struct erofs_buffer_block {
 	struct list_head list;
+	struct list_head mapped_list;
 
 	erofs_blk_t blkaddr;
 	int type;
diff --git a/lib/cache.c b/lib/cache.c
index 32a58311f563..17b2b096632c 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -18,6 +18,11 @@ static struct erofs_buffer_block blkh = {
 };
 static erofs_blk_t tail_blkaddr;
 
+/* buckets for all mapped buffer blocks to boost up allocation */
+static struct list_head mapped_buckets[2][EROFS_BLKSIZ];
+/* last mapped buffer block to accelerate erofs_mapbh() */
+static struct erofs_buffer_block *last_mapped_block = &blkh;
+
 static bool erofs_bh_flush_drop_directly(struct erofs_buffer_head *bh)
 {
 	return erofs_bh_flush_generic_end(bh);
@@ -62,12 +67,17 @@ struct erofs_bhops erofs_buf_write_bhops = {
 /* return buffer_head of erofs super block (with size 0) */
 struct erofs_buffer_head *erofs_buffer_init(void)
 {
+	int i, j;
 	struct erofs_buffer_head *bh = erofs_balloc(META, 0, 0, 0);
 
 	if (IS_ERR(bh))
 		return bh;
 
 	bh->op = &erofs_skip_write_bhops;
+
+	for (i = 0; i < ARRAY_SIZE(mapped_buckets); i++)
+		for (j = 0; j < ARRAY_SIZE(mapped_buckets[0]); j++)
+			init_list_head(&mapped_buckets[i][j]);
 	return bh;
 }
 
@@ -132,20 +142,61 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 	struct erofs_buffer_block *cur, *bb;
 	struct erofs_buffer_head *bh;
 	unsigned int alignsize, used0, usedmax;
+	unsigned int used_before, used;
 
 	int ret = get_alignsize(type, &type);
 
 	if (ret < 0)
 		return ERR_PTR(ret);
+
+	DBG_BUGON(type < 0 || type > META);
 	alignsize = ret;
 
 	used0 = (size + required_ext) % EROFS_BLKSIZ + inline_ext;
 	usedmax = 0;
 	bb = NULL;
 
-	list_for_each_entry(cur, &blkh.list, list) {
-		unsigned int used_before, used;
+	if (used0 == 0 || alignsize == EROFS_BLKSIZ)
+		goto alloc;
+
+	/* Try find a most fit mapped buffer block first. */
+	for (used_before = 1; used_before < EROFS_BLKSIZ; ++used_before) {
+		struct list_head *bt = mapped_buckets[type] + used_before;
+
+		if (list_empty(bt))
+			continue;
+		cur = list_first_entry(bt, struct erofs_buffer_block,
+				       mapped_list);
+
+		ret = __erofs_battach(cur, NULL, size, alignsize,
+				      required_ext + inline_ext, true);
+		if (ret < 0)
+			continue;
+
+		used = (ret + required_ext) % EROFS_BLKSIZ + inline_ext;
+
+		/* should contain inline data in current block */
+		if (used > EROFS_BLKSIZ)
+			continue;
+
+		/*
+		 * remaining should be smaller than before or
+		 * larger than allocating a new buffer block
+		 */
+		if (used < used_before && used < used0)
+			continue;
+
+		if (usedmax < used) {
+			bb = cur;
+			usedmax = used;
+		}
+	}
 
+	/* try to start from the last mapped one, which can be extended */
+	cur = last_mapped_block;
+	if (cur == &blkh)
+		cur = list_next_entry(cur, list);
+	for (; cur != &blkh; cur = list_next_entry(cur, list)) {
 		used_before = cur->buffers.off % EROFS_BLKSIZ;
 
 		/* skip if buffer block is just full */
@@ -187,6 +238,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 		goto found;
 	}
 
+alloc:
 	/* allocate a new buffer block */
 	if (used0 > EROFS_BLKSIZ)
 		return ERR_PTR(-ENOSPC);
@@ -200,6 +252,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 	bb->buffers.off = 0;
 	init_list_head(&bb->buffers.list);
 	list_add_tail(&bb->list, &blkh.list);
+	init_list_head(&bb->mapped_list);
 
 	bh = malloc(sizeof(struct erofs_buffer_head));
 	if (!bh) {
@@ -214,6 +267,18 @@ found:
 	return bh;
 }
 
+static void erofs_bupdate_mapped(struct erofs_buffer_block *bb)
+{
+	struct list_head *bkt;
+
+	if (bb->blkaddr == NULL_ADDR)
+		return;
+
+	bkt = mapped_buckets[bb->type] + bb->buffers.off % EROFS_BLKSIZ;
+	list_del(&bb->mapped_list);
+	list_add_tail(&bb->mapped_list, bkt);
+}
+
 struct erofs_buffer_head *erofs_battach(struct erofs_buffer_head *bh,
 					int type, unsigned int size)
 {
@@ -239,6 +304,7 @@ struct erofs_buffer_head *erofs_battach(struct erofs_buffer_head *bh,
 		free(nbh);
 		return ERR_PTR(ret);
 	}
+	erofs_bupdate_mapped(bb);
 	return nbh;
 
 }
@@ -247,8 +313,11 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
 {
 	erofs_blk_t blkaddr;
 
-	if (bb->blkaddr == NULL_ADDR)
+	if (bb->blkaddr == NULL_ADDR) {
 		bb->blkaddr = tail_blkaddr;
+		last_mapped_block = bb;
+		erofs_bupdate_mapped(bb);
+	}
 
 	blkaddr = bb->blkaddr + BLK_ROUND_UP(bb->buffers.off);
 	if (blkaddr > tail_blkaddr)
@@ -259,15 +328,16 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
 
 erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb)
 {
-	struct erofs_buffer_block *t, *nt;
+	struct erofs_buffer_block *t = last_mapped_block;
 
-	if (!bb || bb->blkaddr == NULL_ADDR) {
-		list_for_each_entry_safe(t, nt, &blkh.list, list) {
-			(void)__erofs_mapbh(t);
-			if (t == bb)
-				break;
-		}
-	}
+	do {
+		t = list_next_entry(t, list);
+		if (t == &blkh)
+			break;
+
+		DBG_BUGON(t->blkaddr != NULL_ADDR);
+		(void)__erofs_mapbh(t);
+	} while (t != bb);
 	return tail_blkaddr;
 }
 
@@ -309,6 +379,7 @@ bool erofs_bflush(struct erofs_buffer_block *bb)
 
 		erofs_dbg("block %u to %u flushed", p->blkaddr, blkaddr - 1);
 
+		list_del(&p->mapped_list);
 		list_del(&p->list);
 		free(p);
 	}
@@ -332,6 +403,10 @@ void erofs_bdrop(struct erofs_buffer_head *bh, bool tryrevoke)
 	if (!list_empty(&bb->buffers.list))
 		return;
 
+	if (bb == last_mapped_block)
+		last_mapped_block = list_prev_entry(bb, list);
+
+	list_del(&bb->mapped_list);
 	list_del(&bb->list);
 	free(bb);
 
-- 
2.24.0

Re: [PATCH v3 2/2] erofs-utils: optimize mkfs to O(N), N = #files

[Gao Xiang]

Hi Weiwen,

On Sat, Jan 16, 2021 at 01:04:38PM +0800, Gao Xiang via Linux-erofs wrote:
> From: Hu Weiwen <sehuww@mail.scut.edu.cn>
> 
> When using EROFS to pack our dataset which consists of millions of
> files, mkfs.erofs is very slow compared with mksquashfs.
> 
> The bottleneck is `erofs_balloc` and `erofs_mapbh` function, which
> iterate over all previously allocated buffer blocks, making the
> complexity of the algrithm O(N^2) where N is the number of files.
> 
> With this patch:
> 
> * global `last_mapped_block` is mantained to avoid full scan in
>   `erofs_mapbh` function.
> 
> * global `non_full_buffer_blocks` mantains a list of buffer block for
>   each type and each possible remaining bytes in the block. Then it is
>   used to identify the most suitable blocks in future `erofs_balloc`,
>   avoiding full scan.
> 
> Some new data structure is allocated in this patch, more RAM usage is
> expected, but not much. When I test it with ImageNet dataset (1.33M
> files), 7GiB RAM is consumed, and it takes about 4 hours. Most time is
> spent on IO.
> 
> Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
> Signed-off-by: Gao Xiang <hsiangkao@aol.com>

Also, there are still some duplicated code in erofs_balloc(). Maybe we
need to split some into a new helper. Could you help if time permits?

I've updated some coding style cases. e.g. exceed max 80-character lines
and single statement braces...

Also I'm thinking if we need to add an command line argument for users to
disable such optmization until it can be firmly confirmed stably... is
that necessary? I'm not sure though...

Thanks,
Gao Xiang

> ---
>  include/erofs/cache.h |  1 +
>  lib/cache.c           | 97 ++++++++++++++++++++++++++++++++++++++-----
>  2 files changed, 87 insertions(+), 11 deletions(-)
> 
> diff --git a/include/erofs/cache.h b/include/erofs/cache.h
> index f8dff67b9736..611ca5b8432b 100644
> --- a/include/erofs/cache.h
> +++ b/include/erofs/cache.h
> @@ -39,6 +39,7 @@ struct erofs_buffer_head {
>  
>  struct erofs_buffer_block {
>  	struct list_head list;
> +	struct list_head mapped_list;
>  
>  	erofs_blk_t blkaddr;
>  	int type;
> diff --git a/lib/cache.c b/lib/cache.c
> index 32a58311f563..17b2b096632c 100644
> --- a/lib/cache.c
> +++ b/lib/cache.c
> @@ -18,6 +18,11 @@ static struct erofs_buffer_block blkh = {
>  };
>  static erofs_blk_t tail_blkaddr;
>  
> +/* buckets for all mapped buffer blocks to boost up allocation */
> +static struct list_head mapped_buckets[2][EROFS_BLKSIZ];
> +/* last mapped buffer block to accelerate erofs_mapbh() */
> +static struct erofs_buffer_block *last_mapped_block = &blkh;
> +
>  static bool erofs_bh_flush_drop_directly(struct erofs_buffer_head *bh)
>  {
>  	return erofs_bh_flush_generic_end(bh);
> @@ -62,12 +67,17 @@ struct erofs_bhops erofs_buf_write_bhops = {
>  /* return buffer_head of erofs super block (with size 0) */
>  struct erofs_buffer_head *erofs_buffer_init(void)
>  {
> +	int i, j;
>  	struct erofs_buffer_head *bh = erofs_balloc(META, 0, 0, 0);
>  
>  	if (IS_ERR(bh))
>  		return bh;
>  
>  	bh->op = &erofs_skip_write_bhops;
> +
> +	for (i = 0; i < ARRAY_SIZE(mapped_buckets); i++)
> +		for (j = 0; j < ARRAY_SIZE(mapped_buckets[0]); j++)
> +			init_list_head(&mapped_buckets[i][j]);
>  	return bh;
>  }
>  
> @@ -132,20 +142,61 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
>  	struct erofs_buffer_block *cur, *bb;
>  	struct erofs_buffer_head *bh;
>  	unsigned int alignsize, used0, usedmax;
> +	unsigned int used_before, used;
>  
>  	int ret = get_alignsize(type, &type);
>  
>  	if (ret < 0)
>  		return ERR_PTR(ret);
> +
> +	DBG_BUGON(type < 0 || type > META);
>  	alignsize = ret;
>  
>  	used0 = (size + required_ext) % EROFS_BLKSIZ + inline_ext;
>  	usedmax = 0;
>  	bb = NULL;
>  
> -	list_for_each_entry(cur, &blkh.list, list) {
> -		unsigned int used_before, used;
> +	if (used0 == 0 || alignsize == EROFS_BLKSIZ)
> +		goto alloc;
> +
> +	/* Try find a most fit mapped buffer block first. */
> +	for (used_before = 1; used_before < EROFS_BLKSIZ; ++used_before) {
> +		struct list_head *bt = mapped_buckets[type] + used_before;
> +
> +		if (list_empty(bt))
> +			continue;
> +		cur = list_first_entry(bt, struct erofs_buffer_block,
> +				       mapped_list);
> +
> +		ret = __erofs_battach(cur, NULL, size, alignsize,
> +				      required_ext + inline_ext, true);
> +		if (ret < 0)
> +			continue;
> +
> +		used = (ret + required_ext) % EROFS_BLKSIZ + inline_ext;
> +
> +		/* should contain inline data in current block */
> +		if (used > EROFS_BLKSIZ)
> +			continue;
> +
> +		/*
> +		 * remaining should be smaller than before or
> +		 * larger than allocating a new buffer block
> +		 */
> +		if (used < used_before && used < used0)
> +			continue;
> +
> +		if (usedmax < used) {
> +			bb = cur;
> +			usedmax = used;
> +		}
> +	}
>  
> +	/* try to start from the last mapped one, which can be extended */
> +	cur = last_mapped_block;
> +	if (cur == &blkh)
> +		cur = list_next_entry(cur, list);
> +	for (; cur != &blkh; cur = list_next_entry(cur, list)) {
>  		used_before = cur->buffers.off % EROFS_BLKSIZ;
>  
>  		/* skip if buffer block is just full */
> @@ -187,6 +238,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
>  		goto found;
>  	}
>  
> +alloc:
>  	/* allocate a new buffer block */
>  	if (used0 > EROFS_BLKSIZ)
>  		return ERR_PTR(-ENOSPC);
> @@ -200,6 +252,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
>  	bb->buffers.off = 0;
>  	init_list_head(&bb->buffers.list);
>  	list_add_tail(&bb->list, &blkh.list);
> +	init_list_head(&bb->mapped_list);
>  
>  	bh = malloc(sizeof(struct erofs_buffer_head));
>  	if (!bh) {
> @@ -214,6 +267,18 @@ found:
>  	return bh;
>  }
>  
> +static void erofs_bupdate_mapped(struct erofs_buffer_block *bb)
> +{
> +	struct list_head *bkt;
> +
> +	if (bb->blkaddr == NULL_ADDR)
> +		return;
> +
> +	bkt = mapped_buckets[bb->type] + bb->buffers.off % EROFS_BLKSIZ;
> +	list_del(&bb->mapped_list);
> +	list_add_tail(&bb->mapped_list, bkt);
> +}
> +
>  struct erofs_buffer_head *erofs_battach(struct erofs_buffer_head *bh,
>  					int type, unsigned int size)
>  {
> @@ -239,6 +304,7 @@ struct erofs_buffer_head *erofs_battach(struct erofs_buffer_head *bh,
>  		free(nbh);
>  		return ERR_PTR(ret);
>  	}
> +	erofs_bupdate_mapped(bb);
>  	return nbh;
>  
>  }
> @@ -247,8 +313,11 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
>  {
>  	erofs_blk_t blkaddr;
>  
> -	if (bb->blkaddr == NULL_ADDR)
> +	if (bb->blkaddr == NULL_ADDR) {
>  		bb->blkaddr = tail_blkaddr;
> +		last_mapped_block = bb;
> +		erofs_bupdate_mapped(bb);
> +	}
>  
>  	blkaddr = bb->blkaddr + BLK_ROUND_UP(bb->buffers.off);
>  	if (blkaddr > tail_blkaddr)
> @@ -259,15 +328,16 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
>  
>  erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb)
>  {
> -	struct erofs_buffer_block *t, *nt;
> +	struct erofs_buffer_block *t = last_mapped_block;
>  
> -	if (!bb || bb->blkaddr == NULL_ADDR) {
> -		list_for_each_entry_safe(t, nt, &blkh.list, list) {
> -			(void)__erofs_mapbh(t);
> -			if (t == bb)
> -				break;
> -		}
> -	}
> +	do {
> +		t = list_next_entry(t, list);
> +		if (t == &blkh)
> +			break;
> +
> +		DBG_BUGON(t->blkaddr != NULL_ADDR);
> +		(void)__erofs_mapbh(t);
> +	} while (t != bb);
>  	return tail_blkaddr;
>  }
>  
> @@ -309,6 +379,7 @@ bool erofs_bflush(struct erofs_buffer_block *bb)
>  
>  		erofs_dbg("block %u to %u flushed", p->blkaddr, blkaddr - 1);
>  
> +		list_del(&p->mapped_list);
>  		list_del(&p->list);
>  		free(p);
>  	}
> @@ -332,6 +403,10 @@ void erofs_bdrop(struct erofs_buffer_head *bh, bool tryrevoke)
>  	if (!list_empty(&bb->buffers.list))
>  		return;
>  
> +	if (bb == last_mapped_block)
> +		last_mapped_block = list_prev_entry(bb, list);
> +
> +	list_del(&bb->mapped_list);
>  	list_del(&bb->list);
>  	free(bb);
>  
> -- 
> 2.24.0
> 

[PATCH v4 2/2] erofs-utils: optimize buffer allocation logic

[Gao Xiang via Linux-erofs]

From: Hu Weiwen <sehuww@mail.scut.edu.cn>

When using EROFS to pack our dataset which consists of millions of
files, mkfs.erofs is very slow compared with mksquashfs.

The bottleneck is `erofs_balloc` and `erofs_mapbh` function, which
iterate over all previously allocated buffer blocks, making the
complexity of the algrithm O(N^2) where N is the number of files.

With this patch:

* global `last_mapped_block` is mantained to avoid full scan in
  `erofs_mapbh` function.

* global `non_full_buffer_blocks` mantains a list of buffer block for
  each type and each possible remaining bytes in the block. Then it is
  used to identify the most suitable blocks in future `erofs_balloc`,
  avoiding full scan.

Some new data structure is allocated in this patch, more RAM usage is
expected, but not much. When I test it with ImageNet dataset (1.33M
files), 7GiB RAM is consumed, and it takes about 4 hours. Most time is
spent on IO.

Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
Signed-off-by: Gao Xiang <hsiangkao@aol.com>
---

I've simplified the most-fit finding logic of v3... Since buffers.off
has to be aligned to alignsize, so I think it's better to use
buffers.off as the index of mapped_buckets compared to using remaining
size as it looks more straight-forward.

Also, I found the exist logic handling expended blocks might be
potential ineffective as well... we have to skip used < used0 only
after oob (extra blocks is allocated, so not expend such blocks but
allocate a new bb...) It might be more effective to reuse such
non-mapped buffer blocks...

Thanks,
Gao Xiang

 include/erofs/cache.h |  1 +
 lib/cache.c           | 91 +++++++++++++++++++++++++++++++++++++------
 2 files changed, 81 insertions(+), 11 deletions(-)

diff --git a/include/erofs/cache.h b/include/erofs/cache.h
index f8dff67b9736..611ca5b8432b 100644
--- a/include/erofs/cache.h
+++ b/include/erofs/cache.h
@@ -39,6 +39,7 @@ struct erofs_buffer_head {
 
 struct erofs_buffer_block {
 	struct list_head list;
+	struct list_head mapped_list;
 
 	erofs_blk_t blkaddr;
 	int type;
diff --git a/lib/cache.c b/lib/cache.c
index 32a58311f563..a44e140bc77b 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -18,6 +18,11 @@ static struct erofs_buffer_block blkh = {
 };
 static erofs_blk_t tail_blkaddr;
 
+/* buckets for all mapped buffer blocks to boost up allocation */
+static struct list_head mapped_buckets[2][EROFS_BLKSIZ];
+/* last mapped buffer block to accelerate erofs_mapbh() */
+static struct erofs_buffer_block *last_mapped_block = &blkh;
+
 static bool erofs_bh_flush_drop_directly(struct erofs_buffer_head *bh)
 {
 	return erofs_bh_flush_generic_end(bh);
@@ -62,12 +67,17 @@ struct erofs_bhops erofs_buf_write_bhops = {
 /* return buffer_head of erofs super block (with size 0) */
 struct erofs_buffer_head *erofs_buffer_init(void)
 {
+	int i, j;
 	struct erofs_buffer_head *bh = erofs_balloc(META, 0, 0, 0);
 
 	if (IS_ERR(bh))
 		return bh;
 
 	bh->op = &erofs_skip_write_bhops;
+
+	for (i = 0; i < ARRAY_SIZE(mapped_buckets); i++)
+		for (j = 0; j < ARRAY_SIZE(mapped_buckets[0]); j++)
+			init_list_head(&mapped_buckets[i][j]);
 	return bh;
 }
 
@@ -132,20 +142,55 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 	struct erofs_buffer_block *cur, *bb;
 	struct erofs_buffer_head *bh;
 	unsigned int alignsize, used0, usedmax;
+	unsigned int used_before, used;
 
 	int ret = get_alignsize(type, &type);
 
 	if (ret < 0)
 		return ERR_PTR(ret);
+
+	DBG_BUGON(type < 0 || type > META);
 	alignsize = ret;
 
 	used0 = (size + required_ext) % EROFS_BLKSIZ + inline_ext;
 	usedmax = 0;
 	bb = NULL;
 
-	list_for_each_entry(cur, &blkh.list, list) {
-		unsigned int used_before, used;
+	if (!used0 || alignsize == EROFS_BLKSIZ)
+		goto alloc;
+
+	/* try to find a most-fit mapped buffer block first */
+	for (used_before = EROFS_BLKSIZ; used_before > 1; ) {
+		struct list_head *bt = mapped_buckets[type] + --used_before;
+
+		if (list_empty(bt))
+			continue;
+		cur = list_first_entry(bt, struct erofs_buffer_block,
+				       mapped_list);
+
+		/* last mapped block can be expended, don't handle it here */
+		if (cur == last_mapped_block)
+			continue;
+
+		ret = __erofs_battach(cur, NULL, size, alignsize,
+				      required_ext + inline_ext, true);
+		if (ret < 0)
+			continue;
+
+		/* should contain all data in the current block */
+		used = ret + required_ext + inline_ext;
+		DBG_BUGON(used > EROFS_BLKSIZ);
+
+		bb = cur;
+		usedmax = used;
+		break;
+	}
 
+	/* try to start from the last mapped one, which can be expended */
+	cur = last_mapped_block;
+	if (cur == &blkh)
+		cur = list_next_entry(cur, list);
+	for (; cur != &blkh; cur = list_next_entry(cur, list)) {
 		used_before = cur->buffers.off % EROFS_BLKSIZ;
 
 		/* skip if buffer block is just full */
@@ -187,6 +232,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 		goto found;
 	}
 
+alloc:
 	/* allocate a new buffer block */
 	if (used0 > EROFS_BLKSIZ)
 		return ERR_PTR(-ENOSPC);
@@ -200,6 +246,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 	bb->buffers.off = 0;
 	init_list_head(&bb->buffers.list);
 	list_add_tail(&bb->list, &blkh.list);
+	init_list_head(&bb->mapped_list);
 
 	bh = malloc(sizeof(struct erofs_buffer_head));
 	if (!bh) {
@@ -214,6 +261,18 @@ found:
 	return bh;
 }
 
+static void erofs_bupdate_mapped(struct erofs_buffer_block *bb)
+{
+	struct list_head *bkt;
+
+	if (bb->blkaddr == NULL_ADDR)
+		return;
+
+	bkt = mapped_buckets[bb->type] + bb->buffers.off % EROFS_BLKSIZ;
+	list_del(&bb->mapped_list);
+	list_add_tail(&bb->mapped_list, bkt);
+}
+
 struct erofs_buffer_head *erofs_battach(struct erofs_buffer_head *bh,
 					int type, unsigned int size)
 {
@@ -239,6 +298,7 @@ struct erofs_buffer_head *erofs_battach(struct erofs_buffer_head *bh,
 		free(nbh);
 		return ERR_PTR(ret);
 	}
+	erofs_bupdate_mapped(bb);
 	return nbh;
 
 }
@@ -247,8 +307,11 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
 {
 	erofs_blk_t blkaddr;
 
-	if (bb->blkaddr == NULL_ADDR)
+	if (bb->blkaddr == NULL_ADDR) {
 		bb->blkaddr = tail_blkaddr;
+		last_mapped_block = bb;
+		erofs_bupdate_mapped(bb);
+	}
 
 	blkaddr = bb->blkaddr + BLK_ROUND_UP(bb->buffers.off);
 	if (blkaddr > tail_blkaddr)
@@ -259,15 +322,16 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
 
 erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb)
 {
-	struct erofs_buffer_block *t, *nt;
+	struct erofs_buffer_block *t = last_mapped_block;
 
-	if (!bb || bb->blkaddr == NULL_ADDR) {
-		list_for_each_entry_safe(t, nt, &blkh.list, list) {
-			(void)__erofs_mapbh(t);
-			if (t == bb)
-				break;
-		}
-	}
+	do {
+		t = list_next_entry(t, list);
+		if (t == &blkh)
+			break;
+
+		DBG_BUGON(t->blkaddr != NULL_ADDR);
+		(void)__erofs_mapbh(t);
+	} while (t != bb);
 	return tail_blkaddr;
 }
 
@@ -309,6 +373,7 @@ bool erofs_bflush(struct erofs_buffer_block *bb)
 
 		erofs_dbg("block %u to %u flushed", p->blkaddr, blkaddr - 1);
 
+		list_del(&p->mapped_list);
 		list_del(&p->list);
 		free(p);
 	}
@@ -332,6 +397,10 @@ void erofs_bdrop(struct erofs_buffer_head *bh, bool tryrevoke)
 	if (!list_empty(&bb->buffers.list))
 		return;
 
+	if (bb == last_mapped_block)
+		last_mapped_block = list_prev_entry(bb, list);
+
+	list_del(&bb->mapped_list);
 	list_del(&bb->list);
 	free(bb);
 
-- 
2.24.0

[PATCH v5 2/2] erofs-utils: optimize buffer allocation logic

[Hu Weiwen]

When using EROFS to pack our dataset which consists of millions of
files, mkfs.erofs is very slow compared with mksquashfs.

The bottleneck is `erofs_balloc' and `erofs_mapbh' function, which
iterate over all previously allocated buffer blocks, making the
complexity of the algrithm O(N^2) where N is the number of files.

With this patch:

* global `last_mapped_block' is mantained to avoid full scan in
`erofs_mapbh` function.

* global `mapped_buckets' maintains a list of already mapped buffer
blocks for each type and for each possible used bytes in the last
EROFS_BLKSIZ. Then it is used to identify the most suitable blocks in
future `erofs_balloc', avoiding full scan. Note that not-mapped (and the
last mapped) blocks can be expended, so we deal with them separately.

When I test it with ImageNet dataset (1.33M files, 147GiB), it takes
about 4 hours. Most time is spent on IO.

Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
Signed-off-by: Gao Xiang <hsiangkao@aol.com>
---
 include/erofs/cache.h |  1 +
 lib/cache.c           | 94 +++++++++++++++++++++++++++++++++++++------
 2 files changed, 83 insertions(+), 12 deletions(-)

diff --git a/include/erofs/cache.h b/include/erofs/cache.h
index f8dff67..611ca5b 100644
--- a/include/erofs/cache.h
+++ b/include/erofs/cache.h
@@ -39,6 +39,7 @@ struct erofs_buffer_head {
 
 struct erofs_buffer_block {
 	struct list_head list;
+	struct list_head mapped_list;
 
 	erofs_blk_t blkaddr;
 	int type;
diff --git a/lib/cache.c b/lib/cache.c
index 32a5831..9e65429 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -18,6 +18,11 @@ static struct erofs_buffer_block blkh = {
 };
 static erofs_blk_t tail_blkaddr;
 
+/* buckets for all mapped buffer blocks to boost up allocation */
+static struct list_head mapped_buckets[2][EROFS_BLKSIZ];
+/* last mapped buffer block to accelerate erofs_mapbh() */
+static struct erofs_buffer_block *last_mapped_block = &blkh;
+
 static bool erofs_bh_flush_drop_directly(struct erofs_buffer_head *bh)
 {
 	return erofs_bh_flush_generic_end(bh);
@@ -62,15 +67,32 @@ struct erofs_bhops erofs_buf_write_bhops = {
 /* return buffer_head of erofs super block (with size 0) */
 struct erofs_buffer_head *erofs_buffer_init(void)
 {
+	int i, j;
 	struct erofs_buffer_head *bh = erofs_balloc(META, 0, 0, 0);
 
 	if (IS_ERR(bh))
 		return bh;
 
 	bh->op = &erofs_skip_write_bhops;
+
+	for (i = 0; i < ARRAY_SIZE(mapped_buckets); i++)
+		for (j = 0; j < ARRAY_SIZE(mapped_buckets[0]); j++)
+			init_list_head(&mapped_buckets[i][j]);
 	return bh;
 }
 
+static void erofs_bupdate_mapped(struct erofs_buffer_block *bb)
+{
+	struct list_head *bkt;
+
+	if (bb->blkaddr == NULL_ADDR)
+		return;
+
+	bkt = mapped_buckets[bb->type] + bb->buffers.off % EROFS_BLKSIZ;
+	list_del(&bb->mapped_list);
+	list_add_tail(&bb->mapped_list, bkt);
+}
+
 /* return occupied bytes in specific buffer block if succeed */
 static int __erofs_battach(struct erofs_buffer_block *bb,
 			   struct erofs_buffer_head *bh,
@@ -110,6 +132,7 @@ static int __erofs_battach(struct erofs_buffer_block *bb,
 		/* need to update the tail_blkaddr */
 		if (tailupdate)
 			tail_blkaddr = blkaddr + BLK_ROUND_UP(bb->buffers.off);
+		erofs_bupdate_mapped(bb);
 	}
 	return (alignedoffset + incr) % EROFS_BLKSIZ;
 }
@@ -131,21 +154,57 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 {
 	struct erofs_buffer_block *cur, *bb;
 	struct erofs_buffer_head *bh;
-	unsigned int alignsize, used0, usedmax;
+	unsigned int alignsize, used0, usedmax, used;
+	int used_before;
 
 	int ret = get_alignsize(type, &type);
 
 	if (ret < 0)
 		return ERR_PTR(ret);
+
+	DBG_BUGON(type < 0 || type > META);
 	alignsize = ret;
 
 	used0 = (size + required_ext) % EROFS_BLKSIZ + inline_ext;
 	usedmax = 0;
 	bb = NULL;
 
-	list_for_each_entry(cur, &blkh.list, list) {
-		unsigned int used_before, used;
+	if (!used0 || alignsize == EROFS_BLKSIZ)
+		goto alloc;
+
+	/* try to find a most-fit mapped buffer block first */
+	used_before = EROFS_BLKSIZ -
+		round_up(size + required_ext + inline_ext, alignsize);
+	for (;used_before > 0; used_before--) {
+		struct list_head *bt = mapped_buckets[type] + used_before;
+
+		if (list_empty(bt))
+			continue;
+		cur = list_first_entry(bt, struct erofs_buffer_block,
+				       mapped_list);
+
+		/* last mapped block can be expended, don't handle it here */
+		if (cur == last_mapped_block)
+			continue;
+
+		ret = __erofs_battach(cur, NULL, size, alignsize,
+				      required_ext + inline_ext, true);
+		DBG_BUGON(ret < 0);
+
+		/* should contain all data in the current block */
+		used = ret + required_ext + inline_ext;
+		DBG_BUGON(used > EROFS_BLKSIZ);
+
+		bb = cur;
+		usedmax = used;
+		break;
+	}
 
+	/* try to start from the last mapped one, which can be expended */
+	cur = last_mapped_block;
+	if (cur == &blkh)
+		cur = list_next_entry(cur, list);
+	for (; cur != &blkh; cur = list_next_entry(cur, list)) {
 		used_before = cur->buffers.off % EROFS_BLKSIZ;
 
 		/* skip if buffer block is just full */
@@ -187,6 +246,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 		goto found;
 	}
 
+alloc:
 	/* allocate a new buffer block */
 	if (used0 > EROFS_BLKSIZ)
 		return ERR_PTR(-ENOSPC);
@@ -200,6 +260,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 	bb->buffers.off = 0;
 	init_list_head(&bb->buffers.list);
 	list_add_tail(&bb->list, &blkh.list);
+	init_list_head(&bb->mapped_list);
 
 	bh = malloc(sizeof(struct erofs_buffer_head));
 	if (!bh) {
@@ -247,8 +308,11 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
 {
 	erofs_blk_t blkaddr;
 
-	if (bb->blkaddr == NULL_ADDR)
+	if (bb->blkaddr == NULL_ADDR) {
 		bb->blkaddr = tail_blkaddr;
+		last_mapped_block = bb;
+		erofs_bupdate_mapped(bb);
+	}
 
 	blkaddr = bb->blkaddr + BLK_ROUND_UP(bb->buffers.off);
 	if (blkaddr > tail_blkaddr)
@@ -259,15 +323,16 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
 
 erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb)
 {
-	struct erofs_buffer_block *t, *nt;
+	struct erofs_buffer_block *t = last_mapped_block;
 
-	if (!bb || bb->blkaddr == NULL_ADDR) {
-		list_for_each_entry_safe(t, nt, &blkh.list, list) {
-			(void)__erofs_mapbh(t);
-			if (t == bb)
-				break;
-		}
-	}
+	do {
+		t = list_next_entry(t, list);
+		if (t == &blkh)
+			break;
+
+		DBG_BUGON(t->blkaddr != NULL_ADDR);
+		(void)__erofs_mapbh(t);
+	} while (t != bb);
 	return tail_blkaddr;
 }
 
@@ -309,6 +374,7 @@ bool erofs_bflush(struct erofs_buffer_block *bb)
 
 		erofs_dbg("block %u to %u flushed", p->blkaddr, blkaddr - 1);
 
+		list_del(&p->mapped_list);
 		list_del(&p->list);
 		free(p);
 	}
@@ -332,6 +398,10 @@ void erofs_bdrop(struct erofs_buffer_head *bh, bool tryrevoke)
 	if (!list_empty(&bb->buffers.list))
 		return;
 
+	if (bb == last_mapped_block)
+		last_mapped_block = list_prev_entry(bb, list);
+
+	list_del(&bb->mapped_list);
 	list_del(&bb->list);
 	free(bb);
 
-- 
2.30.0

Re: [PATCH v4 2/2] erofs-utils: optimize buffer allocation logic

[胡玮文]

> 在 2021年1月16日，14:41，Gao Xiang <hsiangkao@aol.com> 写道：
> 
> From: Hu Weiwen <sehuww@mail.scut.edu.cn>
> 
> When using EROFS to pack our dataset which consists of millions of
> files, mkfs.erofs is very slow compared with mksquashfs.
> 
> The bottleneck is `erofs_balloc` and `erofs_mapbh` function, which
> iterate over all previously allocated buffer blocks, making the
> complexity of the algrithm O(N^2) where N is the number of files.
> 
> With this patch:
> 
> * global `last_mapped_block` is mantained to avoid full scan in
>  `erofs_mapbh` function.
> 
> * global `non_full_buffer_blocks` mantains a list of buffer block for
>  each type and each possible remaining bytes in the block. Then it is
>  used to identify the most suitable blocks in future `erofs_balloc`,
>  avoiding full scan.
> 
> Some new data structure is allocated in this patch, more RAM usage is
> expected, but not much. When I test it with ImageNet dataset (1.33M
> files), 7GiB RAM is consumed, and it takes about 4 hours. Most time is
> spent on IO.
> 
> Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
> Signed-off-by: Gao Xiang <hsiangkao@aol.com>
> ---
> 
> I've simplified the most-fit finding logic of v3... Since buffers.off
> has to be aligned to alignsize, so I think it's better to use
> buffers.off as the index of mapped_buckets compared to using remaining
> size as it looks more straight-forward.
> 
> Also, I found the exist logic handling expended blocks might be
> potential ineffective as well... we have to skip used < used0 only
> after oob (extra blocks is allocated, so not expend such blocks but
> allocate a new bb...) It might be more effective to reuse such
> non-mapped buffer blocks...

I don’t get this. If not oob, then “used” should be larger than “used_before”, then we will not skip such block anyway, right?

> Thanks,
> Gao Xiang
> 
> include/erofs/cache.h |  1 +
> lib/cache.c           | 91 +++++++++++++++++++++++++++++++++++++------
> 2 files changed, 81 insertions(+), 11 deletions(-)
> 
> diff --git a/include/erofs/cache.h b/include/erofs/cache.h
> index f8dff67b9736..611ca5b8432b 100644
> --- a/include/erofs/cache.h
> +++ b/include/erofs/cache.h
> @@ -39,6 +39,7 @@ struct erofs_buffer_head {
> 
> struct erofs_buffer_block {
>    struct list_head list;
> +    struct list_head mapped_list;
> 
>    erofs_blk_t blkaddr;
>    int type;
> diff --git a/lib/cache.c b/lib/cache.c
> index 32a58311f563..a44e140bc77b 100644
> --- a/lib/cache.c
> +++ b/lib/cache.c
> @@ -18,6 +18,11 @@ static struct erofs_buffer_block blkh = {
> };
> static erofs_blk_t tail_blkaddr;
> 
> +/* buckets for all mapped buffer blocks to boost up allocation */
> +static struct list_head mapped_buckets[2][EROFS_BLKSIZ];
> +/* last mapped buffer block to accelerate erofs_mapbh() */
> +static struct erofs_buffer_block *last_mapped_block = &blkh;
> +
> static bool erofs_bh_flush_drop_directly(struct erofs_buffer_head *bh)
> {
>    return erofs_bh_flush_generic_end(bh);
> @@ -62,12 +67,17 @@ struct erofs_bhops erofs_buf_write_bhops = {
> /* return buffer_head of erofs super block (with size 0) */
> struct erofs_buffer_head *erofs_buffer_init(void)
> {
> +    int i, j;
>    struct erofs_buffer_head *bh = erofs_balloc(META, 0, 0, 0);
> 
>    if (IS_ERR(bh))
>        return bh;
> 
>    bh->op = &erofs_skip_write_bhops;
> +
> +    for (i = 0; i < ARRAY_SIZE(mapped_buckets); i++)
> +        for (j = 0; j < ARRAY_SIZE(mapped_buckets[0]); j++)
> +            init_list_head(&mapped_buckets[i][j]);
>    return bh;
> }
> 
> @@ -132,20 +142,55 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
>    struct erofs_buffer_block *cur, *bb;
>    struct erofs_buffer_head *bh;
>    unsigned int alignsize, used0, usedmax;
> +    unsigned int used_before, used;
> 
>    int ret = get_alignsize(type, &type);
> 
>    if (ret < 0)
>        return ERR_PTR(ret);
> +
> +    DBG_BUGON(type < 0 || type > META);
>    alignsize = ret;
> 
>    used0 = (size + required_ext) % EROFS_BLKSIZ + inline_ext;
>    usedmax = 0;
>    bb = NULL;
> 
> -    list_for_each_entry(cur, &blkh.list, list) {
> -        unsigned int used_before, used;
> +    if (!used0 || alignsize == EROFS_BLKSIZ)
> +        goto alloc;
> +
> +    /* try to find a most-fit mapped buffer block first */
> +    for (used_before = EROFS_BLKSIZ; used_before > 1; ) {
> +        struct list_head *bt = mapped_buckets[type] + --used_before;
> +
> +        if (list_empty(bt))
> +            continue;
> +        cur = list_first_entry(bt, struct erofs_buffer_block,
> +                       mapped_list);
> +
> +        /* last mapped block can be expended, don't handle it here */
> +        if (cur == last_mapped_block)
> +            continue;
> +
> +        ret = __erofs_battach(cur, NULL, size, alignsize,
> +                      required_ext + inline_ext, true);
> +        if (ret < 0)
> +            continue;
> +
> +        /* should contain all data in the current block */
> +        used = ret + required_ext + inline_ext;
> +        DBG_BUGON(used > EROFS_BLKSIZ);
> +
> +        bb = cur;
> +        usedmax = used;
> +        break;
> +    }
> 
> +    /* try to start from the last mapped one, which can be expended */
> +    cur = last_mapped_block;
> +    if (cur == &blkh)
> +        cur = list_next_entry(cur, list);
> +    for (; cur != &blkh; cur = list_next_entry(cur, list)) {
>        used_before = cur->buffers.off % EROFS_BLKSIZ;
> 
>        /* skip if buffer block is just full */
> @@ -187,6 +232,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
>        goto found;
>    }
> 
> +alloc:
>    /* allocate a new buffer block */
>    if (used0 > EROFS_BLKSIZ)
>        return ERR_PTR(-ENOSPC);
> @@ -200,6 +246,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
>    bb->buffers.off = 0;
>    init_list_head(&bb->buffers.list);
>    list_add_tail(&bb->list, &blkh.list);
> +    init_list_head(&bb->mapped_list);
> 
>    bh = malloc(sizeof(struct erofs_buffer_head));
>    if (!bh) {
> @@ -214,6 +261,18 @@ found:
>    return bh;
> }
> 
> +static void erofs_bupdate_mapped(struct erofs_buffer_block *bb)
> +{
> +    struct list_head *bkt;
> +
> +    if (bb->blkaddr == NULL_ADDR)
> +        return;
> +
> +    bkt = mapped_buckets[bb->type] + bb->buffers.off % EROFS_BLKSIZ;
> +    list_del(&bb->mapped_list);
> +    list_add_tail(&bb->mapped_list, bkt);
> +}
> +
> struct erofs_buffer_head *erofs_battach(struct erofs_buffer_head *bh,
>                    int type, unsigned int size)
> {
> @@ -239,6 +298,7 @@ struct erofs_buffer_head *erofs_battach(struct erofs_buffer_head *bh,
>        free(nbh);
>        return ERR_PTR(ret);
>    }
> +    erofs_bupdate_mapped(bb);
>    return nbh;
> 
> }
> @@ -247,8 +307,11 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
> {
>    erofs_blk_t blkaddr;
> 
> -    if (bb->blkaddr == NULL_ADDR)
> +    if (bb->blkaddr == NULL_ADDR) {
>        bb->blkaddr = tail_blkaddr;
> +        last_mapped_block = bb;
> +        erofs_bupdate_mapped(bb);
> +    }
> 
>    blkaddr = bb->blkaddr + BLK_ROUND_UP(bb->buffers.off);
>    if (blkaddr > tail_blkaddr)
> @@ -259,15 +322,16 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
> 
> erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb)
> {
> -    struct erofs_buffer_block *t, *nt;
> +    struct erofs_buffer_block *t = last_mapped_block;
> 
> -    if (!bb || bb->blkaddr == NULL_ADDR) {
> -        list_for_each_entry_safe(t, nt, &blkh.list, list) {
> -            (void)__erofs_mapbh(t);
> -            if (t == bb)
> -                break;
> -        }
> -    }
> +    do {
> +        t = list_next_entry(t, list);
> +        if (t == &blkh)
> +            break;
> +
> +        DBG_BUGON(t->blkaddr != NULL_ADDR);
> +        (void)__erofs_mapbh(t);
> +    } while (t != bb);
>    return tail_blkaddr;
> }
> 
> @@ -309,6 +373,7 @@ bool erofs_bflush(struct erofs_buffer_block *bb)
> 
>        erofs_dbg("block %u to %u flushed", p->blkaddr, blkaddr - 1);
> 
> +        list_del(&p->mapped_list);
>        list_del(&p->list);
>        free(p);
>    }
> @@ -332,6 +397,10 @@ void erofs_bdrop(struct erofs_buffer_head *bh, bool tryrevoke)
>    if (!list_empty(&bb->buffers.list))
>        return;
> 
> +    if (bb == last_mapped_block)
> +        last_mapped_block = list_prev_entry(bb, list);
> +
> +    list_del(&bb->mapped_list);
>    list_del(&bb->list);
>    free(bb);
> 
> -- 
> 2.24.0
> 

Re: [PATCH v4 2/2] erofs-utils: optimize buffer allocation logic

[Gao Xiang]

Hi Weiwen,

On Mon, Jan 18, 2021 at 09:02:16PM +0800, 胡玮文 wrote:
> 
> > 在 2021年1月16日，14:41，Gao Xiang <hsiangkao@aol.com> 写道：
> > 
> > From: Hu Weiwen <sehuww@mail.scut.edu.cn>
> > 
> > When using EROFS to pack our dataset which consists of millions of
> > files, mkfs.erofs is very slow compared with mksquashfs.
> > 
> > The bottleneck is `erofs_balloc` and `erofs_mapbh` function, which
> > iterate over all previously allocated buffer blocks, making the
> > complexity of the algrithm O(N^2) where N is the number of files.
> > 
> > With this patch:
> > 
> > * global `last_mapped_block` is mantained to avoid full scan in
> >  `erofs_mapbh` function.
> > 
> > * global `non_full_buffer_blocks` mantains a list of buffer block for
> >  each type and each possible remaining bytes in the block. Then it is
> >  used to identify the most suitable blocks in future `erofs_balloc`,
> >  avoiding full scan.
> > 
> > Some new data structure is allocated in this patch, more RAM usage is
> > expected, but not much. When I test it with ImageNet dataset (1.33M
> > files), 7GiB RAM is consumed, and it takes about 4 hours. Most time is
> > spent on IO.
> > 
> > Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
> > Signed-off-by: Gao Xiang <hsiangkao@aol.com>
> > ---
> > 
> > I've simplified the most-fit finding logic of v3... Since buffers.off
> > has to be aligned to alignsize, so I think it's better to use
> > buffers.off as the index of mapped_buckets compared to using remaining
> > size as it looks more straight-forward.
> > 
> > Also, I found the exist logic handling expended blocks might be
> > potential ineffective as well... we have to skip used < used0 only
> > after oob (extra blocks is allocated, so not expend such blocks but
> > allocate a new bb...) It might be more effective to reuse such
> > non-mapped buffer blocks...
> 
> I don’t get this. If not oob, then “used” should be larger than “used_before”, then we will not skip such block anyway, right?

Sorry, I think I was completely misleaded by the comment above the
code at that time. It's too far to get the original intention :(
I think you're right (anyway, I think the main purpose of this
condition was that I didn't want to introduce too many new bbs
with a lot of large unused space. But anyway such condition is
approximate since it's actually a 0-1 Knapsack problem). Please
ignore my previous words about this...

Thanks,
Gao Xiang

[PATCH v6 2/2] erofs-utils: optimize buffer allocation logic

[Hu Weiwen]

When using EROFS to pack our dataset which consists of millions of
files, mkfs.erofs is very slow compared with mksquashfs.

The bottleneck is `erofs_balloc' and `erofs_mapbh' function, which
iterate over all previously allocated buffer blocks, making the
complexity of the algrithm O(N^2) where N is the number of files.

With this patch:

* global `last_mapped_block' is mantained to avoid full scan in
`erofs_mapbh` function.

* global `mapped_buckets' maintains a list of already mapped buffer
blocks for each type and for each possible used bytes in the last
EROFS_BLKSIZ. Then it is used to identify the most suitable blocks in
future `erofs_balloc', avoiding full scan. Note that not-mapped (and the
last mapped) blocks can be expended, so we deal with them separately.

When I test it with ImageNet dataset (1.33M files, 147GiB), it takes
about 4 hours. Most time is spent on IO.

Signed-off-by: Hu Weiwen <sehuww@mail.scut.edu.cn>
Signed-off-by: Gao Xiang <hsiangkao@aol.com>
---
Compared with v5, this version return directly when erofs_mapbh() is called on
an already mapped bb, instead of map all allocated bb.

The fact that the v5 patch will map all allocated bb cause the bug reported in
https://lore.kernel.org/linux-erofs/20210118123945.23676-1-sehuww@mail.scut.edu.cn/
to reveal.

 include/erofs/cache.h |  1 +
 lib/cache.c           | 96 +++++++++++++++++++++++++++++++++++++------
 2 files changed, 85 insertions(+), 12 deletions(-)

diff --git a/include/erofs/cache.h b/include/erofs/cache.h
index f8dff67..611ca5b 100644
--- a/include/erofs/cache.h
+++ b/include/erofs/cache.h
@@ -39,6 +39,7 @@ struct erofs_buffer_head {

 struct erofs_buffer_block {
 	struct list_head list;
+	struct list_head mapped_list;

 	erofs_blk_t blkaddr;
 	int type;
diff --git a/lib/cache.c b/lib/cache.c
index 32a5831..c9a8c50 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -18,6 +18,11 @@ static struct erofs_buffer_block blkh = {
 };
 static erofs_blk_t tail_blkaddr;

+/* buckets for all mapped buffer blocks to boost up allocation */
+static struct list_head mapped_buckets[2][EROFS_BLKSIZ];
+/* last mapped buffer block to accelerate erofs_mapbh() */
+static struct erofs_buffer_block *last_mapped_block = &blkh;
+
 static bool erofs_bh_flush_drop_directly(struct erofs_buffer_head *bh)
 {
 	return erofs_bh_flush_generic_end(bh);
@@ -62,15 +67,32 @@ struct erofs_bhops erofs_buf_write_bhops = {
 /* return buffer_head of erofs super block (with size 0) */
 struct erofs_buffer_head *erofs_buffer_init(void)
 {
+	int i, j;
 	struct erofs_buffer_head *bh = erofs_balloc(META, 0, 0, 0);

 	if (IS_ERR(bh))
 		return bh;

 	bh->op = &erofs_skip_write_bhops;
+
+	for (i = 0; i < ARRAY_SIZE(mapped_buckets); i++)
+		for (j = 0; j < ARRAY_SIZE(mapped_buckets[0]); j++)
+			init_list_head(&mapped_buckets[i][j]);
 	return bh;
 }

+static void erofs_bupdate_mapped(struct erofs_buffer_block *bb)
+{
+	struct list_head *bkt;
+
+	if (bb->blkaddr == NULL_ADDR)
+		return;
+
+	bkt = mapped_buckets[bb->type] + bb->buffers.off % EROFS_BLKSIZ;
+	list_del(&bb->mapped_list);
+	list_add_tail(&bb->mapped_list, bkt);
+}
+
 /* return occupied bytes in specific buffer block if succeed */
 static int __erofs_battach(struct erofs_buffer_block *bb,
 			   struct erofs_buffer_head *bh,
@@ -110,6 +132,7 @@ static int __erofs_battach(struct erofs_buffer_block *bb,
 		/* need to update the tail_blkaddr */
 		if (tailupdate)
 			tail_blkaddr = blkaddr + BLK_ROUND_UP(bb->buffers.off);
+		erofs_bupdate_mapped(bb);
 	}
 	return (alignedoffset + incr) % EROFS_BLKSIZ;
 }
@@ -131,21 +154,57 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 {
 	struct erofs_buffer_block *cur, *bb;
 	struct erofs_buffer_head *bh;
-	unsigned int alignsize, used0, usedmax;
+	unsigned int alignsize, used0, usedmax, used;
+	int used_before;

 	int ret = get_alignsize(type, &type);

 	if (ret < 0)
 		return ERR_PTR(ret);
+
+	DBG_BUGON(type < 0 || type > META);
 	alignsize = ret;

 	used0 = (size + required_ext) % EROFS_BLKSIZ + inline_ext;
 	usedmax = 0;
 	bb = NULL;

-	list_for_each_entry(cur, &blkh.list, list) {
-		unsigned int used_before, used;
+	if (!used0 || alignsize == EROFS_BLKSIZ)
+		goto alloc;
+
+	/* try to find a most-fit mapped buffer block first */
+	used_before = EROFS_BLKSIZ -
+		round_up(size + required_ext + inline_ext, alignsize);
+	for (;used_before > 0; used_before--) {
+		struct list_head *bt = mapped_buckets[type] + used_before;
+
+		if (list_empty(bt))
+			continue;
+		cur = list_first_entry(bt, struct erofs_buffer_block,
+				       mapped_list);
+
+		/* last mapped block can be expended, don't handle it here */
+		if (cur == last_mapped_block)
+			continue;
+
+		ret = __erofs_battach(cur, NULL, size, alignsize,
+				      required_ext + inline_ext, true);
+		DBG_BUGON(ret < 0);
+
+		/* should contain all data in the current block */
+		used = ret + required_ext + inline_ext;
+		DBG_BUGON(used > EROFS_BLKSIZ);
+
+		bb = cur;
+		usedmax = used;
+		break;
+	}

+	/* try to start from the last mapped one, which can be expended */
+	cur = last_mapped_block;
+	if (cur == &blkh)
+		cur = list_next_entry(cur, list);
+	for (; cur != &blkh; cur = list_next_entry(cur, list)) {
 		used_before = cur->buffers.off % EROFS_BLKSIZ;

 		/* skip if buffer block is just full */
@@ -187,6 +246,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 		goto found;
 	}

+alloc:
 	/* allocate a new buffer block */
 	if (used0 > EROFS_BLKSIZ)
 		return ERR_PTR(-ENOSPC);
@@ -200,6 +260,7 @@ struct erofs_buffer_head *erofs_balloc(int type, erofs_off_t size,
 	bb->buffers.off = 0;
 	init_list_head(&bb->buffers.list);
 	list_add_tail(&bb->list, &blkh.list);
+	init_list_head(&bb->mapped_list);

 	bh = malloc(sizeof(struct erofs_buffer_head));
 	if (!bh) {
@@ -247,8 +308,11 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)
 {
 	erofs_blk_t blkaddr;

-	if (bb->blkaddr == NULL_ADDR)
+	if (bb->blkaddr == NULL_ADDR) {
 		bb->blkaddr = tail_blkaddr;
+		last_mapped_block = bb;
+		erofs_bupdate_mapped(bb);
+	}

 	blkaddr = bb->blkaddr + BLK_ROUND_UP(bb->buffers.off);
 	if (blkaddr > tail_blkaddr)
@@ -259,15 +323,18 @@ static erofs_blk_t __erofs_mapbh(struct erofs_buffer_block *bb)

 erofs_blk_t erofs_mapbh(struct erofs_buffer_block *bb)
 {
-	struct erofs_buffer_block *t, *nt;
+	struct erofs_buffer_block *t = last_mapped_block;

-	if (!bb || bb->blkaddr == NULL_ADDR) {
-		list_for_each_entry_safe(t, nt, &blkh.list, list) {
-			(void)__erofs_mapbh(t);
-			if (t == bb)
-				break;
-		}
-	}
+	if (bb && bb->blkaddr != NULL_ADDR)
+		return bb->blkaddr;
+	do {
+		t = list_next_entry(t, list);
+		if (t == &blkh)
+			break;
+
+		DBG_BUGON(t->blkaddr != NULL_ADDR);
+		(void)__erofs_mapbh(t);
+	} while (t != bb);
 	return tail_blkaddr;
 }

@@ -309,6 +376,7 @@ bool erofs_bflush(struct erofs_buffer_block *bb)

 		erofs_dbg("block %u to %u flushed", p->blkaddr, blkaddr - 1);

+		list_del(&p->mapped_list);
 		list_del(&p->list);
 		free(p);
 	}
@@ -332,6 +400,10 @@ void erofs_bdrop(struct erofs_buffer_head *bh, bool tryrevoke)
 	if (!list_empty(&bb->buffers.list))
 		return;

+	if (bb == last_mapped_block)
+		last_mapped_block = list_prev_entry(bb, list);
+
+	list_del(&bb->mapped_list);
 	list_del(&bb->list);
 	free(bb);

--
2.30.0

Re: [PATCH v6 2/2] erofs-utils: optimize buffer allocation logic

[Gao Xiang]

Hi Weiwen,

On Tue, Jan 19, 2021 at 01:49:51PM +0800, Hu Weiwen wrote:

...

>  	bb = NULL;
> 
> -	list_for_each_entry(cur, &blkh.list, list) {
> -		unsigned int used_before, used;
> +	if (!used0 || alignsize == EROFS_BLKSIZ)
> +		goto alloc;
> +
> +	/* try to find a most-fit mapped buffer block first */
> +	used_before = EROFS_BLKSIZ -
> +		round_up(size + required_ext + inline_ext, alignsize);

Honestly, after seen above I feel I'm not good at math now
since I smell somewhat strange of this, apart from the pending
patch you raised [1], the algebra is

/* since all buffers should be aligned with alignsize */
erofs_off_t alignedoffset = roundup(used_before, alignsize);

and (alignedoffset + size + required_ext + inline_ext <= EROFS_BLKSIZ)

and why it can be equal to
used_before = EROFS_BLKSIZ - round_up(size + required_ext + inline_ext, alignsize);

Could you explain this in detail if possible? for example,
size = 3
inline_ext = 62
alignsize = 32

so 4096 - roundup(3 + 62, 32) = 4096 - 96 = 4000
but, the real used_before can be even started at 4032, since
alignedoffset = roundup(4032, 32) = 4032
4032 + 62 = 4094 <= EROFS_BLKSIZ.

Am I stll missing something?

IMO, I don't want too hard on such math, I'd like to just use
used_before = EROFS_BLKSIZ - (size + required_ext + inline_ext);
and simply skip the bb if __erofs_battach is fail (as I said before,
the internal __erofs_battach can be changed, and I don't want to
imply that always succeed.)

If you also agree that, I'll send out a revised version along
with a cleanup patch to clean up erofs_balloc() as well, which
is more complicated than before.

[1] https://lore.kernel.org/r/20210121162606.8168-1-sehuww@mail.scut.edu.cn/

Thanks,
Gao Xiang

Re: [PATCH v6 2/2] erofs-utils: optimize buffer allocation logic

[Gao Xiang]

On Fri, Jan 22, 2021 at 09:14:08PM +0800, Gao Xiang wrote:
> Hi Weiwen,
> 
> On Tue, Jan 19, 2021 at 01:49:51PM +0800, Hu Weiwen wrote:
> 
> ...
> 
> >  	bb = NULL;
> > 
> > -	list_for_each_entry(cur, &blkh.list, list) {
> > -		unsigned int used_before, used;
> > +	if (!used0 || alignsize == EROFS_BLKSIZ)
> > +		goto alloc;
> > +
> > +	/* try to find a most-fit mapped buffer block first */
> > +	used_before = EROFS_BLKSIZ -
> > +		round_up(size + required_ext + inline_ext, alignsize);
> 
> Honestly, after seen above I feel I'm not good at math now
> since I smell somewhat strange of this, apart from the pending
> patch you raised [1], the algebra is
> 
> /* since all buffers should be aligned with alignsize */
> erofs_off_t alignedoffset = roundup(used_before, alignsize);
> 
> and (alignedoffset + size + required_ext + inline_ext <= EROFS_BLKSIZ)
> 
> and why it can be equal to
> used_before = EROFS_BLKSIZ - round_up(size + required_ext + inline_ext, alignsize);
> 
> Could you explain this in detail if possible? for example,
> size = 3
> inline_ext = 62
> alignsize = 32
> 
> so 4096 - roundup(3 + 62, 32) = 4096 - 96 = 4000
> but, the real used_before can be even started at 4032, since
> alignedoffset = roundup(4032, 32) = 4032
> 4032 + 62 = 4094 <= EROFS_BLKSIZ.
> 
> Am I stll missing something?
> 

Oh, the example itself is wrong, yet I still feel no good at
this formula, e.g I'm not sure if it works for alignsize which
cannot be divided by EROFS_BLKSIZ (although currently alignsize =
4 or 32)

Thanks,
Gao Xiang

> IMO, I don't want too hard on such math, I'd like to just use
> used_before = EROFS_BLKSIZ - (size + required_ext + inline_ext);
> and simply skip the bb if __erofs_battach is fail (as I said before,
> the internal __erofs_battach can be changed, and I don't want to
> imply that always succeed.)
> 
> If you also agree that, I'll send out a revised version along
> with a cleanup patch to clean up erofs_balloc() as well, which
> is more complicated than before.
> 
> [1] https://lore.kernel.org/r/20210121162606.8168-1-sehuww@mail.scut.edu.cn/
> 
> Thanks,
> Gao Xiang
> 

Re: [PATCH v6 2/2] erofs-utils: optimize buffer allocation logic

[Huang Jianan]

[-- Attachment #1: Type: text/plain, Size: 3485 bytes --]

Hi Weiwen, Xiang,

在 2021/1/22 21:21, Gao Xiang 写道:
> On Fri, Jan 22, 2021 at 09:14:08PM +0800, Gao Xiang wrote:
>> Hi Weiwen,
>>
>> On Tue, Jan 19, 2021 at 01:49:51PM +0800, Hu Weiwen wrote:
>>
>> ...
>>
>>>   	bb = NULL;
>>>
>>> -	list_for_each_entry(cur, &blkh.list, list) {
>>> -		unsigned int used_before, used;
>>> +	if (!used0 || alignsize == EROFS_BLKSIZ)
>>> +		goto alloc;
>>> +
>>> +	/* try to find a most-fit mapped buffer block first */
>>> +	used_before = EROFS_BLKSIZ -
>>> +		round_up(size + required_ext + inline_ext, alignsize);
>> Honestly, after seen above I feel I'm not good at math now
>> since I smell somewhat strange of this, apart from the pending
>> patch you raised [1], the algebra is
>>
>> /* since all buffers should be aligned with alignsize */
>> erofs_off_t alignedoffset = roundup(used_before, alignsize);
>>
>> and (alignedoffset + size + required_ext + inline_ext <= EROFS_BLKSIZ)
>>
>> and why it can be equal to
>> used_before = EROFS_BLKSIZ - round_up(size + required_ext + inline_ext, alignsize);
>>
>> Could you explain this in detail if possible? for example,
>> size = 3
>> inline_ext = 62
>> alignsize = 32
>>
>> so 4096 - roundup(3 + 62, 32) = 4096 - 96 = 4000
>> but, the real used_before can be even started at 4032, since
>> alignedoffset = roundup(4032, 32) = 4032
>> 4032 + 62 = 4094 <= EROFS_BLKSIZ.
>>
>> Am I stll missing something?
>>
> Oh, the example itself is wrong, yet I still feel no good at
> this formula, e.g I'm not sure if it works for alignsize which
> cannot be divided by EROFS_BLKSIZ (although currently alignsize =
> 4 or 32)
>
> Thanks,
> Gao Xiang


We can divide several parts of data in EROFS_BLKSIZ  as follows:

____________________________________________________________________________________

|||||

|  used_before |alignedoffset|   size + required_ext + inline_ext 
|tail_data |

|________________ 
|_________________|_____________________________________|___________|

Use alignsize to represent these data:

1) alignsize * num_x = used_before + alignedoffset
2) alignsize * num_y = size + required_ext + inline_ext + tail_data
3) alignsize * num_z = EROFS_BLKSIZ

So we can get,
4) num_x + num_y = num_z

If we use
used_before = EROFS_BLKSIZ - round_up(size + required_ext + inline_ext, alignsize);
here, num_y should be an integer.

Consider the following two situations:

1) If EROFS_BLKSIZ can be divisible by alignsize, num_z is an integer. so num_x is an integer.
    The following formula can be satisfied:
    erofs_off_t alignedoffset = roundup(used_before, alignsize);
    
2）If EROFS_BLKSIZ can't be divisible by alignsize, num_z isn't an integer and num_x won't be an integer.
    The formula can't be satisfied.

So I think it should be
used_before = round_down(EROFS_BLKSIZ - size-required_ext - inline_ext , alignsize);
here.

Sorry for my poor english and figure. . .


Thanks,
Jianan

>> IMO, I don't want too hard on such math, I'd like to just use
>> used_before = EROFS_BLKSIZ - (size + required_ext + inline_ext);
>> and simply skip the bb if __erofs_battach is fail (as I said before,
>> the internal __erofs_battach can be changed, and I don't want to
>> imply that always succeed.)
>>
>> If you also agree that, I'll send out a revised version along
>> with a cleanup patch to clean up erofs_balloc() as well, which
>> is more complicated than before.
>>
>> [1] https://lore.kernel.org/r/20210121162606.8168-1-sehuww@mail.scut.edu.cn/
>>
>> Thanks,
>> Gao Xiang
>>

[-- Attachment #2: Type: text/html, Size: 7091 bytes --]