erofs-utils: lib: use round_up() to avoid division
PATCH 1/5 erofs-utils: lib: use round_up() to avoid division
A hotspot identified by profiling.
--- lib/cache.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
lib/cache.c +2 -1
@@ -76,11 +76,12 @@ static int __erofs_battach(struct erofs_buffer_block *bb,struct erofs_sb_info *sbi = bmgr->sbi;const unsigned int blkmask =erofs_blksiz (sbi) -1 ;erofs_off_t boff = bb->buffers.off; -const erofs_off_t alignedoffset =roundup (boff, alignsize); +const erofs_off_t alignedoffset =round_up (boff, alignsize);bool tailupdate = false;erofs_blk_t blkaddr;int oob; +DBG_BUGON (alignsize & (alignsize -1 ));/* inline data must never span block boundaries */ if (erofs_blkoff (sbi, alignedoffset + incr + blkmask) + inline_ext > blkmask)
Signature · 1 line
2.43.5
PATCH 2/5 erofs-utils: lib: add some bit operations
From: Hongzhen Luo <[email protected]>
Introduce following bitmap helpers:
erofs_test_bit __erofs_set_bit __erofs_clear_bit erofs_find_next_bit
[1] https://lore.kernel.org/r/[email protected]
--- include/erofs/bitops.h | 40 ++++++++++++++++++++++++++++++++++++++++ include/erofs/defs.h | 5 +++++ lib/Makefile.am | 3 ++- lib/bitops.c | 30 ++++++++++++++++++++++++++++++ 4 files changed, 77 insertions(+), 1 deletion(-) create mode 100644 include/erofs/bitops.h create mode 100644 lib/bitops.c
include/erofs/bitops.h new file +40 -0
@@ -0,0 +1,40 @@ +/* SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0 */ +#ifndef __EROFS_BITOPS_H +#define __EROFS_BITOPS_H + +#ifdef __cplusplus +extern "C" +{ +#endif + +#include "defs.h" + +static inline void __erofs_set_bit (int nr,volatile unsigned long *addr) +{ +unsigned long mask =BIT_MASK (nr); +unsigned long *p = ((unsigned long *)addr) +BIT_WORD (nr); + + *p |= mask; +} + +static inline void __erofs_clear_bit (int nr,volatile unsigned long *addr) +{ +unsigned long mask =BIT_MASK (nr); +unsigned long *p = ((unsigned long *)addr) +BIT_WORD (nr); + + *p &= ~mask; +} + +static inline int __erofs_test_bit (int nr,const volatile unsigned long *addr) +{ +return 1UL & (addr[BIT_WORD (nr)] >> (nr & (BITS_PER_LONG -1 ))); +} + +unsigned long erofs_find_next_bit (const unsigned long *addr, +unsigned long nbits,unsigned long start); + +#ifdef __cplusplus +} +#endif + +#endif
include/erofs/defs.h +5 -0
@@ -286,6 +286,11 @@ static inline u32 get_unaligned_le64(const void *p) (n) & (1ULL << 1) ? 1 : 0 \ ) +static inline unsigned int ffs_long (unsigned long s) +{ +return __builtin_ctzl (s); +} +static inline unsigned int fls_long (unsigned long x) {return x ?sizeof (x) *8 -__builtin_clzl (x) :0 ;
lib/Makefile.am +2 -1
@@ -20,6 +20,7 @@ noinst_HEADERS = $(top_srcdir)/include/erofs_fs.h \ $(top_srcdir)/include/erofs/io.h \ $(top_srcdir)/include/erofs/list.h \ $(top_srcdir)/include/erofs/print.h \ + $(top_srcdir)/include/erofs/bitops.h \ $(top_srcdir)/include/erofs/tar.h \ $(top_srcdir)/include/erofs/trace.h \ $(top_srcdir)/include/erofs/xattr.h \
@@ -34,7 +35,7 @@ liberofs_la_SOURCES = config.c io.c cache.c super.c inode.c xattr.c exclude.c \ namei.c data.c compress.c compressor.c zmap.c decompress.c \ compress_hints.c hashmap.c sha256.c blobchunk.c dir.c \ fragments.c dedupe.c uuid_unparse.c uuid.c tar.c \ - block_list.c rebuild.c diskbuf.c + block_list.c rebuild.c diskbuf.c bitops.c liberofs_la_CFLAGS = -Wall ${libuuid_CFLAGS} -I$(top_srcdir)/include if ENABLE_LZ4
lib/bitops.c new file +30 -0
@@ -0,0 +1,30 @@ +// SPDX-License-Identifier: GPL-2.0+ OR Apache-2.0 +/* +* erofs-utils/lib/bitops.c +* +* Copyright (C) 2025, Alibaba Cloud +*/ +#include <erofs/bitops.h> + +unsigned long erofs_find_next_bit (const unsigned long *addr, +unsigned long nbits,unsigned long start) +{ +unsigned long tmp; + +if (__erofs_unlikely (start >= nbits)) +return nbits; + + tmp = addr[start /BITS_PER_LONG ]; + + tmp &= ~0UL << ((start) & (BITS_PER_LONG -1 )); + start =round_down (start,BITS_PER_LONG ); + +while (!tmp) { + start +=BITS_PER_LONG ; +if (start >= nbits) +return nbits; + + tmp = addr[start /BITS_PER_LONG ]; + } +return min (start +ffs_long (tmp), nbits); +}
Signature · 1 line
2.43.5
PATCH 3/5 erofs-utils: lib: rename `mapped_buckets` to `watermeter`
In reply to Gao XiangIn order to prepare for the upcoming space allocation speedup.
--- include/erofs/cache.h | 4 ++-- lib/cache.c | 27 +++++++++++++-------------- 2 files changed, 15 insertions(+), 16 deletions(-)
include/erofs/cache.h +2 -2
@@ -48,7 +48,7 @@ struct erofs_buffer_head {struct erofs_buffer_block {struct list_head list; -struct list_head mapped_list; +struct list_head sibling;/* blocks of the same waterline */ erofs_blk_t blkaddr;int type;
@@ -60,7 +60,7 @@ struct erofs_bufmgr {struct erofs_sb_info *sbi;/* buckets for all mapped buffer blocks to boost up allocation */ -struct list_head mapped_buckets[META +1 ][EROFS_MAX_BLOCK_SIZE ]; +struct list_head watermeter[META +1 ][EROFS_MAX_BLOCK_SIZE ];struct erofs_buffer_block blkh;erofs_blk_t tail_blkaddr, metablkcnt;
lib/cache.c +13 -14
@@ -41,15 +41,15 @@ struct erofs_bufmgr *erofs_buffer_init(struct erofs_sb_info *sbi, bufmgr->blkh.blkaddr =NULL_ADDR ; bufmgr->last_mapped_block = &bufmgr->blkh; -for (i =0 ; i <ARRAY_SIZE (bufmgr->mapped_buckets); i++) -for (j =0 ; j <ARRAY_SIZE (bufmgr->mapped_buckets[0 ]); j++) -init_list_head (&bufmgr->mapped_buckets[i][j]); +for (i =0 ; i <ARRAY_SIZE (bufmgr->watermeter); i++) +for (j =0 ; j < (1 << sbi->blkszbits); j++) +init_list_head (&bufmgr->watermeter[i][j]); bufmgr->tail_blkaddr = startblk; bufmgr->sbi = sbi;return bufmgr; } -static void erofs_bupdate_mapped (struct erofs_buffer_block *bb) +static void erofs_update_bwatermeter (struct erofs_buffer_block *bb) {struct erofs_bufmgr *bmgr = bb->buffers.fsprivate;struct erofs_sb_info *sbi = bmgr->sbi;
@@ -58,10 +58,10 @@ static void erofs_bupdate_mapped(struct erofs_buffer_block *bb)if (bb->blkaddr ==NULL_ADDR )return ; - bkt = bmgr->mapped_buckets[bb->type] + + bkt = bmgr->watermeter[bb->type] + (bb->buffers.off & (erofs_blksiz (sbi) -1 )); -list_del (&bb->mapped_list); -list_add_tail (&bb->mapped_list, bkt); +list_del (&bb->sibling); +list_add_tail (&bb->sibling, bkt); }/* return occupied bytes in specific buffer block if succeed */
@@ -116,7 +116,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_bupdate_mapped (bb); +erofs_update_bwatermeter (bb); }return ((alignedoffset + incr + blkmask) & blkmask) +1 ; }
@@ -165,12 +165,11 @@ static int erofs_bfind_for_attach(struct erofs_bufmgr *bmgr, used_before =rounddown (blksiz - (size + inline_ext), alignsize);for (; used_before; --used_before) { -struct list_head *bt = bmgr->mapped_buckets[type] + used_before; +struct list_head *bt = bmgr->watermeter[type] + used_before;if (list_empty (bt))continue ; - cur = list_first_entry(bt, struct erofs_buffer_block, - mapped_list); + cur = list_first_entry(bt, struct erofs_buffer_block, sibling);/* last mapped block can be expended, don't handle it here */ if (list_next_entry (cur, list)->blkaddr ==NULL_ADDR ) {
@@ -279,7 +278,7 @@ struct erofs_buffer_head *erofs_balloc(struct erofs_bufmgr *bmgr, &bmgr->last_mapped_block->list); else list_add_tail(&bb->list, &bmgr->blkh.list); -init_list_head (&bb->mapped_list); +init_list_head (&bb->sibling); bh =malloc (sizeof (struct erofs_buffer_head ));if (!bh) {
@@ -343,7 +342,7 @@ static void __erofs_mapbh(struct erofs_buffer_block *bb) } } bmgr->last_mapped_block = bb; -erofs_bupdate_mapped (bb); +erofs_update_bwatermeter (bb); } blkaddr = bb->blkaddr + bb->buffers.nblocks;
@@ -382,7 +381,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->mapped_list); +list_del (&bb->sibling);list_del (&bb->list);free (bb); }
Signature · 1 line
2.43.5
PATCH 4/5 erofs-utils: lib: optimize space allocation
In reply to Gao XiangPreviously, only mapped buffers were kept in the form of bucket lists for each type and for each possible used bytes in the last block.
Apply this to unmapped buffers as well for faster greedy selection.
--- include/erofs/cache.h | 4 +- lib/cache.c | 152 ++++++++++++++++++++---------------------- 2 files changed, 73 insertions(+), 83 deletions(-)
include/erofs/cache.h +2 -2
@@ -59,8 +59,8 @@ struct erofs_buffer_block {struct erofs_bufmgr {struct erofs_sb_info *sbi; -/* buckets for all mapped buffer blocks to boost up allocation */ -struct list_head watermeter[META +1 ][EROFS_MAX_BLOCK_SIZE ]; +/* buckets for all buffer blocks to boost up allocation */ +struct list_head watermeter[META +1 ][2 ][EROFS_MAX_BLOCK_SIZE ];struct erofs_buffer_block blkh;erofs_blk_t tail_blkaddr, metablkcnt;
lib/cache.c +71 -81
192 lines not on this page · raw message
Signature · 1 line
2.43.5
PATCH 5/5 erofs-utils: lib: use bitmaps to accelerate bucket selection
In reply to Gao XiangInstead 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
--- include/erofs/cache.h | 1 + lib/cache.c | 119 +++++++++++++++++++++++++++++++++--------- 2 files changed, 94 insertions(+), 26 deletions(-)
include/erofs/cache.h +1 -0
@@ -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;
lib/cache.c +93 -26
175 lines not on this page · raw message
Signature · 1 line
2.43.5