Skip to contentSkip to conversation

erofs-utils: introduce xattr name bloom filter

PATCH Superseded Jingbo Xu 2 participants 6 messages Jul 5, 2023 – Jul 12, 2023 Library code

v2 of 7 Superseded Latest is v7 →

lore
Share & tools
lore

Jingbo Xu

author
#0 lore raw

v2 cover erofs-utils: introduce xattr name bloom filter

changes since RFC:
- the number of hash functions is 1, and now it's implemented as:
xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index),
where the constant magic number EROFS_XATTR_FILTER_SEED [*] is used to give a better spread for the mapping. (Alexander Larsson)
- fix the value of EROFS_FEATURE_COMPAT_XATTR_FILTER; rename EROFS_XATTR_BLOOM_* to EROFS_XATTR_FILTER_* (Gao Xiang)

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

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

Refer to the kernel patch set [*] for more details.

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

Jingbo Xu (3):
erofs-utils: add xxh32 library
erofs-utils: update on-disk format for xattr name filter
erofs-utils: mkfs: enable xattr name 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              | 74 ++++++++++++++++++++++++++--------
 lib/xxhash.c             | 85 ++++++++++++++++++++++++++++++++++++++++
 mkfs/main.c              |  6 +++
 8 files changed, 197 insertions(+), 18 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

PATCH v2 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
#3 lore raw

Re: [PATCH v2 1/3] erofs-utils: add xxh32 library

Quoted 6 lines · Gao Xiang
Quoted 3 lines · Jingbo Xu

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

Quoted 6 lines
Quoted 1 line

I'd suggest using the original xxhash library instead of copying an simplified implementation here since we don't touch the implementation.

https://rpmfind.net/linux/rpm2html/search.php?query=xxhash

Yeah. I think xxhash-devel is available in most distributions. XXH32() could be used directly here and configure.ac needs to be updated to reflect the package dependency.

As I'm not quite familiar with autoconf/automake, later in v3 I will still attach the self-implemented xxh32() in erofs-utils. Maybe later we could change to use libxxhash directly.

Signature · 2 lines
Thanks,
Jingbo
author
#4 lore raw

PATCH v2 2/3 erofs-utils: update on-disk format for xattr name filter

In reply to Jingbo Xu

The xattr name 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 extended attributes (n) is approximately 30.

trusted.overlay.opaque
trusted.overlay.redirect
trusted.overlay.origin
trusted.overlay.impure
trusted.overlay.nlink
trusted.overlay.upper
trusted.overlay.metacopy
trusted.overlay.protattr
user.overlay.opaque
user.overlay.redirect
user.overlay.origin
user.overlay.impure
user.overlay.nlink
user.overlay.upper
user.overlay.metacopy
user.overlay.protattr
security.evm
security.ima
security.selinux
security.SMACK64
security.SMACK64IPIN
security.SMACK64IPOUT
security.SMACK64EXEC
security.SMACK64TRANSMUTE
security.SMACK64MMAP
security.apparmor
security.capability
system.posix_acl_access
system.posix_acl_default
user.mime_type

Given the number of bits of the bloom filter (m) is 32, the optimal value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).

The single hash function is implemented as:

xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)

where index represents the index of corresponding predefined short name prefix, while name represents the name string after stripping the above predefined name prefix.

The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is used to give a better spread when mapping these 30 extended attributes into 32-bit bloom filter as:

	bit  0: security.ima
	bit  1:
	bit  2: trusted.overlay.nlink
	bit  3:
	bit  4: user.overlay.nlink
	bit  5: trusted.overlay.upper
	bit  6: user.overlay.origin
	bit  7: trusted.overlay.protattr
	bit  8: security.apparmor
	bit  9: user.overlay.protattr

bit 10: user.overlay.opaque
bit 11: security.selinux
bit 12: security.SMACK64TRANSMUTE
bit 13: security.SMACK64
bit 14: security.SMACK64MMAP
bit 15: user.overlay.impure
bit 16: security.SMACK64IPIN
bit 17: trusted.overlay.redirect
bit 18: trusted.overlay.origin
bit 19: security.SMACK64IPOUT
bit 20: trusted.overlay.opaque
bit 21: system.posix_acl_default
bit 22:
bit 23: user.mime_type
bit 24: trusted.overlay.impure
bit 25: security.SMACK64EXEC
bit 26: user.overlay.redirect
bit 27: user.overlay.upper
bit 28: security.evm
bit 29: security.capability
bit 30: system.posix_acl_access
bit 31: trusted.overlay.metacopy, user.overlay.metacopy

The h_name_filter field is introduced to the on-disk per-inode xattr header to place the corresponding xattr name filter, where bit value 1 indicates non-existence for compatibility.

This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER compatible feature bit.

---
 include/erofs_fs.h | 10 +++++++++-
 1 file changed, 9 insertions(+), 1 deletion(-)
include/erofs_fs.h +9 -1
index 3697882..1ffaaef 100644
@@ -14,6 +14,7 @@
 
 #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
 #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
+#define EROFS_FEATURE_COMPAT_XATTR_FILTER	0x00000004
 
 /*
  * Any bits that aren't in EROFS_ALL_FEATURE_INCOMPAT should
@@ -201,7 +202,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_name_filter;		/* bit value 1 indicates not-present */
 	__u8   h_shared_count;
 	__u8   h_reserved2[7];
 	__le32 h_shared_xattrs[0];      /* shared xattr id array */
@@ -222,6 +223,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_FILTER_BITS		32
+#define EROFS_XATTR_FILTER_MASK		(EROFS_XATTR_FILTER_BITS - 1)
+#define EROFS_XATTR_FILTER_DEFAULT	UINT32_MAX
+#define EROFS_XATTR_FILTER_SEED		0x25BBE08F
+
 /* 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
#5 lore raw

PATCH v2 3/3 erofs-utils: mkfs: enable xattr name filter

In reply to Jingbo Xu

Introduce "--xattr-filter" option to enable the xattr name bloom filter feature.

---
 include/erofs/config.h   |  1 +
 include/erofs/internal.h |  1 +
 lib/xattr.c              | 74 +++++++++++++++++++++++++++++++---------
 mkfs/main.c              |  6 ++++
 4 files changed, 66 insertions(+), 16 deletions(-)
include/erofs/config.h +1 -0
index 8f52d2c..2803f37 100644
@@ -53,6 +53,7 @@ struct erofs_configure {
 	bool c_ignore_mtime;
 	bool c_showprogress;
 	bool c_extra_ea_name_prefixes;
+	bool c_xattr_filter;
 
 #ifdef HAVE_LIBSELINUX
 	struct selabel_handle *sehnd;
include/erofs/internal.h +1 -0
index ab964d4..1d7ef73 100644
@@ -133,6 +133,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_filter, compat, COMPAT_XATTR_FILTER)
 
 #define EROFS_I_EA_INITED	(1 << 0)
 #define EROFS_I_Z_INITED	(1 << 1)
lib/xattr.c +58 -16

164 lines not on this page · raw message

mkfs/main.c +6 -0
index ac208e5..84d4414 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-filter", 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-filter	      enable xattr name 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_filter = true;
+			erofs_sb_set_xattr_filter();
+			break;
 		case 1:
 			usage();
 			exit(0);
Signature · 1 line
2.19.1.6.gb485710b