[PATCH 5/5] erofs-utils: lib: use bitmaps to accelerate bucket selection
Gao Xiang
hsiangkao at linux.alibaba.com
Fri Jan 3 20:03:38 AEDT 2025
Instead of looping over bucket lists directly, maintain bitmaps
for more efficient greedy selection.
ILSVRC2012_img_train.tar (1,281,168 inodes) [1]
uncompressed EROFS (vanilla): 147,059,949,568B 36m29.529s
uncompressed EROFS (patched): 147,059,511,296B 1m14.920s
ILSVRC2012_img_val.tar (50,001 inodes) 6,744,924,160B [2]
uncompressed EROFS (vanilla): 6,713,278,464B 29.998s
uncompressed EROFS (patched): 6,713,188,352B 23.753s
[1] https://image-net.org/data/ILSVRC/2012/ILSVRC2012_img_train.tar
$ tar -xvf ILSVRC2012_img_train.tar; rm -f ILSVRC2012_img_train.tar
$ find . -name "*.tar" | while read NAME ; do tar -xvf "${NAME}"; rm -f "${NAME}"; done
[2] https://image-net.org/data/ILSVRC/2012/ILSVRC2012_img_vol.tar
$ mkfs.erofs --tar=f --sort none foo.erofs ILSVRC2012_img_vol.tar
Signed-off-by: Gao Xiang <hsiangkao at linux.alibaba.com>
---
include/erofs/cache.h | 1 +
lib/cache.c | 119 +++++++++++++++++++++++++++++++++---------
2 files changed, 94 insertions(+), 26 deletions(-)
diff --git a/include/erofs/cache.h b/include/erofs/cache.h
index 76c5671..87d743a 100644
--- a/include/erofs/cache.h
+++ b/include/erofs/cache.h
@@ -61,6 +61,7 @@ struct erofs_bufmgr {
/* buckets for all buffer blocks to boost up allocation */
struct list_head watermeter[META + 1][2][EROFS_MAX_BLOCK_SIZE];
+ unsigned long bktmap[META + 1][2][EROFS_MAX_BLOCK_SIZE / BITS_PER_LONG];
struct erofs_buffer_block blkh;
erofs_blk_t tail_blkaddr, metablkcnt;
diff --git a/lib/cache.c b/lib/cache.c
index 2e758ba..ca1061b 100644
--- a/lib/cache.c
+++ b/lib/cache.c
@@ -7,6 +7,7 @@
*/
#include <stdlib.h>
#include <erofs/cache.h>
+#include <erofs/bitops.h>
#include "erofs/print.h"
static int erofs_bh_flush_drop_directly(struct erofs_buffer_head *bh)
@@ -30,36 +31,72 @@ const struct erofs_bhops erofs_skip_write_bhops = {
struct erofs_bufmgr *erofs_buffer_init(struct erofs_sb_info *sbi,
erofs_blk_t startblk)
{
- struct erofs_bufmgr *bufmgr;
+ unsigned int blksiz = erofs_blksiz(sbi);
+ struct erofs_bufmgr *bmgr;
int i, j, k;
- bufmgr = malloc(sizeof(struct erofs_bufmgr));
- if (!bufmgr)
+ bmgr = malloc(sizeof(struct erofs_bufmgr));
+ if (!bmgr)
return NULL;
- init_list_head(&bufmgr->blkh.list);
- bufmgr->blkh.blkaddr = NULL_ADDR;
- bufmgr->last_mapped_block = &bufmgr->blkh;
-
- for (i = 0; i < ARRAY_SIZE(bufmgr->watermeter); i++)
- for (j = 0; j < ARRAY_SIZE(bufmgr->watermeter[0]); j++)
- for (k = 0; k < (1 << sbi->blkszbits); k++)
- init_list_head(&bufmgr->watermeter[i][j][k]);
- bufmgr->tail_blkaddr = startblk;
- bufmgr->sbi = sbi;
- return bufmgr;
+ bmgr->sbi = sbi;
+ for (i = 0; i < ARRAY_SIZE(bmgr->watermeter); i++) {
+ for (j = 0; j < ARRAY_SIZE(bmgr->watermeter[0]); j++) {
+ for (k = 0; k < blksiz; k++)
+ init_list_head(&bmgr->watermeter[i][j][k]);
+ memset(bmgr->bktmap[i][j], 0, blksiz / BITS_PER_LONG);
+ }
+ }
+ init_list_head(&bmgr->blkh.list);
+ bmgr->blkh.blkaddr = NULL_ADDR;
+ bmgr->tail_blkaddr = startblk;
+ bmgr->last_mapped_block = &bmgr->blkh;
+ return bmgr;
+}
+
+static void erofs_clear_bbktmap(struct erofs_bufmgr *bmgr, int type,
+ bool mapped, int nr)
+{
+ int bit = erofs_blksiz(bmgr->sbi) - (nr + 1);
+
+ DBG_BUGON(bit < 0);
+ __erofs_clear_bit(bit, bmgr->bktmap[type][mapped]);
}
-static void erofs_update_bwatermeter(struct erofs_buffer_block *bb)
+static void erofs_set_bbktmap(struct erofs_bufmgr *bmgr, int type,
+ bool mapped, int nr)
+{
+ int bit = erofs_blksiz(bmgr->sbi) - (nr + 1);
+
+ DBG_BUGON(bit < 0);
+ __erofs_set_bit(bit, bmgr->bktmap[type][mapped]);
+}
+
+static void erofs_update_bwatermeter(struct erofs_buffer_block *bb, bool free)
{
struct erofs_bufmgr *bmgr = bb->buffers.fsprivate;
struct erofs_sb_info *sbi = bmgr->sbi;
- struct list_head *bkt;
-
- bkt = bmgr->watermeter[bb->type][bb->blkaddr != NULL_ADDR] +
- (bb->buffers.off & (erofs_blksiz(sbi) - 1));
+ unsigned int blksiz = erofs_blksiz(sbi);
+ bool mapped = bb->blkaddr != NULL_ADDR;
+ struct list_head *h = bmgr->watermeter[bb->type][mapped];
+ unsigned int nr;
+
+ if (bb->sibling.next == bb->sibling.prev) {
+ if ((uintptr_t)(bb->sibling.next - h) < blksiz) {
+ nr = bb->sibling.next - h;
+ erofs_clear_bbktmap(bmgr, bb->type, mapped, nr);
+ } else if (bb->sibling.next != &bb->sibling) {
+ nr = bb->sibling.next -
+ bmgr->watermeter[bb->type][!mapped];
+ erofs_clear_bbktmap(bmgr, bb->type, !mapped, nr);
+ }
+ }
list_del(&bb->sibling);
- list_add_tail(&bb->sibling, bkt);
+ if (free)
+ return;
+ nr = bb->buffers.off & (blksiz - 1);
+ list_add_tail(&bb->sibling, h + nr);
+ erofs_set_bbktmap(bmgr, bb->type, mapped, nr);
}
/* return occupied bytes in specific buffer block if succeed */
@@ -114,7 +151,7 @@ static int __erofs_battach(struct erofs_buffer_block *bb,
/* need to update the tail_blkaddr */
if (tailupdate)
bmgr->tail_blkaddr = blkaddr + bb->buffers.nblocks;
- erofs_update_bwatermeter(bb);
+ erofs_update_bwatermeter(bb, false);
}
return ((alignedoffset + incr + blkmask) & blkmask) + 1;
}
@@ -130,6 +167,36 @@ int erofs_bh_balloon(struct erofs_buffer_head *bh, erofs_off_t incr)
return __erofs_battach(bb, NULL, incr, 1, 0, false);
}
+static bool __find_next_bucket(struct erofs_bufmgr *bmgr, int type, bool mapped,
+ unsigned int *index, unsigned int end)
+{
+ const unsigned int blksiz = erofs_blksiz(bmgr->sbi);
+ const unsigned int blkmask = blksiz - 1;
+ unsigned int l = *index, r;
+
+ if (l <= end) {
+ DBG_BUGON(l < end);
+ return false;
+ }
+
+ l = blkmask - (l & blkmask);
+ r = blkmask - (end & blkmask);
+ if (l >= r) {
+ l = erofs_find_next_bit(bmgr->bktmap[type][mapped], blksiz, l);
+ if (l < blksiz) {
+ *index = round_down(*index, blksiz) + blkmask - l;
+ return true;
+ }
+ l = 0;
+ *index -= blksiz;
+ }
+ l = erofs_find_next_bit(bmgr->bktmap[type][mapped], r, l);
+ if (l >= r)
+ return false;
+ *index = round_down(*index, blksiz) + blkmask - l;
+ return true;
+}
+
static int erofs_bfind_for_attach(struct erofs_bufmgr *bmgr,
int type, erofs_off_t size,
unsigned int inline_ext,
@@ -163,13 +230,13 @@ static int erofs_bfind_for_attach(struct erofs_bufmgr *bmgr,
while (mapped) {
--mapped;
- for (; index > end; --index) {
+ for (; __find_next_bucket(bmgr, type, mapped, &index, end);
+ --index) {
struct list_head *bt;
used = index & blkmask;
bt = bmgr->watermeter[type][mapped] + used;
- if (list_empty(bt))
- continue;
+ DBG_BUGON(list_empty(bt));
cur = list_first_entry(bt, struct erofs_buffer_block,
sibling);
@@ -332,7 +399,7 @@ static void __erofs_mapbh(struct erofs_buffer_block *bb)
}
}
bmgr->last_mapped_block = bb;
- erofs_update_bwatermeter(bb);
+ erofs_update_bwatermeter(bb, false);
}
blkaddr = bb->blkaddr + bb->buffers.nblocks;
@@ -371,7 +438,7 @@ static void erofs_bfree(struct erofs_buffer_block *bb)
if (bb == bmgr->last_mapped_block)
bmgr->last_mapped_block = list_prev_entry(bb, list);
- list_del(&bb->sibling);
+ erofs_update_bwatermeter(bb, true);
list_del(&bb->list);
free(bb);
}
--
2.43.5
More information about the Linux-erofs
mailing list