* [PATCH v5 2/2] erofs-utils: optimize buffer allocation logic
2021-01-16 6:31 ` [PATCH v4 2/2] erofs-utils: optimize buffer allocation logic Gao Xiang via Linux-erofs
@ 2021-01-18 12:34 ` Hu Weiwen
2021-01-18 13:02 ` [PATCH v4 " 胡玮文
2021-01-19 5:49 ` [PATCH v6 " Hu Weiwen
2 siblings, 0 replies; 11+ messages in thread
From: Hu Weiwen @ 2021-01-18 12:34 UTC (permalink / raw)
To: Gao Xiang; +Cc: Hu Weiwen, linux-erofs
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
^ permalink raw reply related [flat|nested] 11+ messages in thread* Re: [PATCH v4 2/2] erofs-utils: optimize buffer allocation logic
2021-01-16 6:31 ` [PATCH v4 2/2] erofs-utils: optimize buffer allocation logic Gao Xiang via Linux-erofs
2021-01-18 12:34 ` [PATCH v5 " Hu Weiwen
@ 2021-01-18 13:02 ` 胡玮文
2021-01-18 14:06 ` Gao Xiang
2021-01-19 5:49 ` [PATCH v6 " Hu Weiwen
2 siblings, 1 reply; 11+ messages in thread
From: 胡玮文 @ 2021-01-18 13:02 UTC (permalink / raw)
To: Gao Xiang; +Cc: linux-erofs
> 在 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
>
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: [PATCH v4 2/2] erofs-utils: optimize buffer allocation logic
2021-01-18 13:02 ` [PATCH v4 " 胡玮文
@ 2021-01-18 14:06 ` Gao Xiang
0 siblings, 0 replies; 11+ messages in thread
From: Gao Xiang @ 2021-01-18 14:06 UTC (permalink / raw)
To: 胡玮文; +Cc: linux-erofs
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
^ permalink raw reply [flat|nested] 11+ messages in thread
* [PATCH v6 2/2] erofs-utils: optimize buffer allocation logic
2021-01-16 6:31 ` [PATCH v4 2/2] erofs-utils: optimize buffer allocation logic Gao Xiang via Linux-erofs
2021-01-18 12:34 ` [PATCH v5 " Hu Weiwen
2021-01-18 13:02 ` [PATCH v4 " 胡玮文
@ 2021-01-19 5:49 ` Hu Weiwen
2021-01-22 13:14 ` Gao Xiang
2 siblings, 1 reply; 11+ messages in thread
From: Hu Weiwen @ 2021-01-19 5:49 UTC (permalink / raw)
To: linux-erofs
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
^ permalink raw reply related [flat|nested] 11+ messages in thread* Re: [PATCH v6 2/2] erofs-utils: optimize buffer allocation logic
2021-01-19 5:49 ` [PATCH v6 " Hu Weiwen
@ 2021-01-22 13:14 ` Gao Xiang
2021-01-22 13:21 ` Gao Xiang
0 siblings, 1 reply; 11+ messages in thread
From: Gao Xiang @ 2021-01-22 13:14 UTC (permalink / raw)
To: Hu Weiwen; +Cc: linux-erofs
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
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: [PATCH v6 2/2] erofs-utils: optimize buffer allocation logic
2021-01-22 13:14 ` Gao Xiang
@ 2021-01-22 13:21 ` Gao Xiang
2021-01-22 15:57 ` Huang Jianan
0 siblings, 1 reply; 11+ messages in thread
From: Gao Xiang @ 2021-01-22 13:21 UTC (permalink / raw)
To: Hu Weiwen; +Cc: linux-erofs
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
>
^ permalink raw reply [flat|nested] 11+ messages in thread* Re: [PATCH v6 2/2] erofs-utils: optimize buffer allocation logic
2021-01-22 13:21 ` Gao Xiang
@ 2021-01-22 15:57 ` Huang Jianan
0 siblings, 0 replies; 11+ messages in thread
From: Huang Jianan @ 2021-01-22 15:57 UTC (permalink / raw)
To: Gao Xiang, Hu Weiwen; +Cc: guoweichao, linux-erofs, zhangshiming
[-- 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 --]
^ permalink raw reply [flat|nested] 11+ messages in thread