Skip to contentSkip to conversation

erofs-utils: lib: use round_up() to avoid division

PATCH New Gao Xiang 1 participant 5 messages Jan 3, 2025 Library code

lore
Share & tools
lore

Gao Xiang

author
#0 lore raw

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
index 5b2cc45..f9aa6eb 100644
@@ -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
author
#1 lore raw

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
new file mode 100644
index 0000000..058642f
@@ -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
index e462338..051a270 100644
@@ -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
index ef98377..9cddc92 100644
@@ -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
new file mode 100644
index 0000000..bb0c9ee
@@ -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
author
#2 lore raw

PATCH 3/5 erofs-utils: lib: rename `mapped_buckets` to `watermeter`

In reply to Gao Xiang

In 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
index 6ff80ab..bdf6460 100644
@@ -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
index f9aa6eb..c7243b5 100644
@@ -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
author
#3 lore raw

PATCH 4/5 erofs-utils: lib: optimize space allocation

In reply to Gao Xiang

Previously, 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
index bdf6460..76c5671 100644
@@ -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
author
#4 lore raw

PATCH 5/5 erofs-utils: lib: use bitmaps to accelerate bucket selection

In reply to Gao Xiang

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
---
 include/erofs/cache.h |   1 +
 lib/cache.c           | 119 +++++++++++++++++++++++++++++++++---------
 2 files changed, 94 insertions(+), 26 deletions(-)
include/erofs/cache.h +1 -0
index 76c5671..87d743a 100644
@@ -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