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 <hsiang...@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
