Skip to contentSkip to conversation

erofs-utils: introduce xattr bloom filter feature

RFC Superseded Jingbo Xu 1 participant 4 messages Jun 21, 2023 Library code

v1 of 7 Superseded Latest is v7 →

lore
Share & tools
lore

Jingbo Xu

author
#0 lore raw

cover erofs-utils: introduce xattr bloom filter feature

The xattr bloom filter feature is used to boost the negative xattr lookup.

Refer to the kernel patches [1] for more details.

[1] https://lore.kernel.org/all/[email protected]/

Jingbo Xu (3):
erofs-utils: add xxh32 library
erofs-utils: update on-disk format for xattr bloom filter
erofs-utils: mkfs: enable xattr bloom filter

 include/erofs/config.h   |  1 +
 include/erofs/internal.h |  1 +
 include/erofs/xxhash.h   | 35 +++++++++++++++++
 include/erofs_fs.h       | 10 ++++-
 lib/Makefile.am          |  3 +-
 lib/xattr.c              | 62 +++++++++++++++++++++++++++--
 lib/xxhash.c             | 85 ++++++++++++++++++++++++++++++++++++++++
 mkfs/main.c              |  6 +++
 8 files changed, 198 insertions(+), 5 deletions(-)
 create mode 100644 include/erofs/xxhash.h
 create mode 100644 lib/xxhash.c
Signature · 1 line
2.19.1.6.gb485710b
author
#1 lore raw

RFC 1/3 erofs-utils: add xxh32 library

Add xxh32 library which could be used by following xattr bloom filter feature.

---
 include/erofs/xxhash.h | 35 +++++++++++++++++
 lib/Makefile.am        |  3 +-
 lib/xxhash.c           | 85 ++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 122 insertions(+), 1 deletion(-)
 create mode 100644 include/erofs/xxhash.h
 create mode 100644 lib/xxhash.c
include/erofs/xxhash.h new file +35 -0
new file mode 100644
index 0000000..fd9384e
@@ -0,0 +1,35 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+#ifndef __EROFS_XXHASH_H
+#define __EROFS_XXHASH_H
+
+#ifdef __cplusplus
+extern "C"
+{
+#endif
+
+#include "defs.h"
+
+/*
+ * Copied from
+ * 	https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git
+ * xxHash - Extremely Fast Hash algorithm
+ */
+
+/**
+ * xxh32() - calculate the 32-bit hash of the input with a given seed.
+ *
+ * @input:  The data to hash.
+ * @length: The length of the data to hash.
+ * @seed:   The seed can be used to alter the result predictably.
+ *
+ * Speed on Core 2 Duo @ 3 GHz (single thread, SMHasher benchmark) : 5.4 GB/s
+ *
+ * Return:  The 32-bit hash of the data.
+ */
+uint32_t xxh32(const void *input, size_t length, uint32_t seed);
+
+#ifdef __cplusplus
+}
+#endif
+
+#endif
lib/Makefile.am +2 -1
index faa7311..a049af6 100644
@@ -23,13 +23,14 @@ noinst_HEADERS = $(top_srcdir)/include/erofs_fs.h \
       $(top_srcdir)/include/erofs/xattr.h \
       $(top_srcdir)/include/erofs/compress_hints.h \
       $(top_srcdir)/include/erofs/fragments.h \
+      $(top_srcdir)/include/erofs/xxhash.h \
       $(top_srcdir)/lib/liberofs_private.h
 
 noinst_HEADERS += compressor.h
 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 rb_tree.c dedupe.c
+		      fragments.c rb_tree.c dedupe.c xxhash.c
 
 liberofs_la_CFLAGS = -Wall -I$(top_srcdir)/include
 if ENABLE_LZ4
lib/xxhash.c new file +85 -0

85 lines not on this page · raw message

Signature · 1 line
2.19.1.6.gb485710b
author
#2 lore raw

RFC 2/3 erofs-utils: update on-disk format for xattr bloom filter

In reply to Jingbo Xu

The xattr bloom filter feature is going to be introduced to speed up the negative xattr lookup, e.g. system.posix_acl_[access|default] lookup when running "ls -lR" workload.

The number of common used xattr (n) is approximately 8, including system.[posix_acl_access|posix_acl_default], security.[capability|selinux] and security.[SMACK64|SMACK64TRANSMUTE|SMACK64EXEC|SMACK64MMAP]. Given the number of bits of the bloom filter (m) is 32, the optimal value for the number of the hash functions (k) is 2 (ln2 * m/n = 2.7).

---
 include/erofs_fs.h | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
include/erofs_fs.h +9 -1
index 9107cc5..4f79e59 100644
@@ -14,6 +14,7 @@
 
 #define EROFS_FEATURE_COMPAT_SB_CHKSUM		0x00000001
 #define EROFS_FEATURE_COMPAT_MTIME		0x00000002
+#define EROFS_FEATURE_COMPAT_XATTR_BLOOM	0x00000003
 
 /*
  * Any bits that aren't in EROFS_ALL_FEATURE_INCOMPAT should
@@ -218,7 +219,7 @@ struct erofs_inode_extended {
  * for read-only fs, no need to introduce h_refcount
  */
 struct erofs_xattr_ibody_header {
-	__le32 h_reserved;
+	__le32 h_map;	/* bloom filter, bit value 1 indicates not-present */
 	__u8   h_shared_count;
 	__u8   h_reserved2[7];
 	__le32 h_shared_xattrs[0];      /* shared xattr id array */
@@ -239,6 +240,13 @@ struct erofs_xattr_ibody_header {
 #define EROFS_XATTR_LONG_PREFIX		0x80
 #define EROFS_XATTR_LONG_PREFIX_MASK	0x7f
 
+#define EROFS_XATTR_NAME_LEN_MAX	UCHAR_MAX
+
+#define EROFS_XATTR_BLOOM_BITS		32
+#define EROFS_XATTR_BLOOM_MASK		(EROFS_XATTR_BLOOM_BITS - 1)
+#define EROFS_XATTR_BLOOM_DEFAULT	UINT32_MAX
+#define EROFS_XATTR_BLOOM_COUNTS	2
+
 /* xattr entry (for both inline & shared xattrs) */
 struct erofs_xattr_entry {
 	__u8   e_name_len;      /* length of name */
Signature · 1 line
2.19.1.6.gb485710b
author
#3 lore raw

RFC 3/3 erofs-utils: mkfs: enable xattr bloom filter

In reply to Jingbo Xu

Introduce --xattr-bloom option to enable this feature.

Be noted that for xattrs with long xattr name prefixes, the corresponding bloom filter is calculated upon the xattr name after stripping the corresponding short predefined xattr name prefix rather than the long xattr name prefix, to cater to kernel's processing procedure for xattr.

---
 include/erofs/config.h   |  1 +
 include/erofs/internal.h |  1 +
 lib/xattr.c              | 62 ++++++++++++++++++++++++++++++++++++++--
 mkfs/main.c              |  6 ++++
 4 files changed, 67 insertions(+), 3 deletions(-)
include/erofs/config.h +1 -0
index 8f52d2c..d22e2e5 100644
@@ -53,6 +53,7 @@ struct erofs_configure {
 	bool c_ignore_mtime;
 	bool c_showprogress;
 	bool c_extra_ea_name_prefixes;
+	bool c_xattr_bloom;
 
 #ifdef HAVE_LIBSELINUX
 	struct selabel_handle *sehnd;
include/erofs/internal.h +1 -0
index b3d04be..41c4083 100644
@@ -139,6 +139,7 @@ EROFS_FEATURE_FUNCS(fragments, incompat, INCOMPAT_FRAGMENTS)
 EROFS_FEATURE_FUNCS(dedupe, incompat, INCOMPAT_DEDUPE)
 EROFS_FEATURE_FUNCS(xattr_prefixes, incompat, INCOMPAT_XATTR_PREFIXES)
 EROFS_FEATURE_FUNCS(sb_chksum, compat, COMPAT_SB_CHKSUM)
+EROFS_FEATURE_FUNCS(xattr_bloom, compat, COMPAT_XATTR_BLOOM)
 
 #define EROFS_I_EA_INITED	(1 << 0)
 #define EROFS_I_Z_INITED	(1 << 1)
lib/xattr.c +59 -3

138 lines not on this page · raw message

mkfs/main.c +6 -0
index 3ec4903..08619f0 100644
@@ -58,6 +58,7 @@ static struct option long_options[] = {
 	{"gid-offset", required_argument, NULL, 17},
 	{"mount-point", required_argument, NULL, 512},
 	{"xattr-prefix", required_argument, NULL, 19},
+	{"xattr-bloom", no_argument, NULL, 20},
 #ifdef WITH_ANDROID
 	{"product-out", required_argument, NULL, 513},
 	{"fs-config-file", required_argument, NULL, 514},
@@ -118,6 +119,7 @@ static void usage(void)
 	      " --random-algorithms   randomize per-file algorithms (debugging only)\n"
 #endif
 	      " --xattr-prefix=X      X=extra xattr name prefix\n"
+	      " --xattr-bloom	      enable xattr bloom filter\n"
 	      " --mount-point=X       X=prefix of target fs path (default: /)\n"
 #ifdef WITH_ANDROID
 	      "\nwith following android-specific options:\n"
@@ -482,6 +484,10 @@ static int mkfs_parse_options_cfg(int argc, char *argv[])
 			}
 			cfg.c_extra_ea_name_prefixes = true;
 			break;
+		case 20:
+			cfg.c_xattr_bloom = true;
+			erofs_sb_set_xattr_bloom();
+			break;
 		case 1:
 			usage();
 			exit(0);
Signature · 1 line
2.19.1.6.gb485710b