[PATCH v5 3/3] erofs-utils: mkfs: enable xattr name filter

[Jingbo Xu]

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

Signed-off-by: Jingbo Xu <jefflexu at linux.alibaba.com>
---
 include/erofs/config.h   |  1 +
 include/erofs/internal.h |  1 +
 lib/xattr.c              | 88 ++++++++++++++++++++++++++++++++++++----
 mkfs/main.c              |  7 ++++
 4 files changed, 89 insertions(+), 8 deletions(-)

diff --git a/include/erofs/config.h b/include/erofs/config.h
index 8f52d2c..c51f0cd 100644
--- a/include/erofs/config.h
+++ b/include/erofs/config.h
@@ -53,6 +53,7 @@ struct erofs_configure {
 	bool c_ignore_mtime;
 	bool c_showprogress;
 	bool c_extra_ea_name_prefixes;
+	bool c_xattr_name_filter;
 
 #ifdef HAVE_LIBSELINUX
 	struct selabel_handle *sehnd;
diff --git a/include/erofs/internal.h b/include/erofs/internal.h
index ab964d4..1d7ef73 100644
--- a/include/erofs/internal.h
+++ b/include/erofs/internal.h
@@ -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)
diff --git a/lib/xattr.c b/lib/xattr.c
index 7d7dc54..5870601 100644
--- a/lib/xattr.c
+++ b/lib/xattr.c
@@ -18,6 +18,7 @@
 #include "erofs/cache.h"
 #include "erofs/io.h"
 #include "erofs/fragments.h"
+#include "erofs/xxhash.h"
 #include "liberofs_private.h"
 
 #define EA_HASHTABLE_BITS 16
@@ -137,27 +138,35 @@ static struct xattr_item *get_xattritem(u8 prefix, char *kvbuf,
 	return item;
 }
 
-static bool match_prefix(const char *key, u8 *index, u16 *len)
+static bool match_short_prefix(const char *key, u8 *index, u16 *len)
 {
 	struct xattr_prefix *p;
-	struct ea_type_node *tnode;
 
-	list_for_each_entry(tnode, &ea_name_prefixes, list) {
-		p = &tnode->type;
+	for (p = xattr_types; p < xattr_types + ARRAY_SIZE(xattr_types); ++p) {
 		if (p->prefix && !strncmp(p->prefix, key, p->prefix_len)) {
 			*len = p->prefix_len;
-			*index = tnode->index;
+			*index = p - xattr_types;
 			return true;
 		}
 	}
-	for (p = xattr_types; p < xattr_types + ARRAY_SIZE(xattr_types); ++p) {
+	return false;
+}
+
+static bool match_prefix(const char *key, u8 *index, u16 *len)
+{
+	struct xattr_prefix *p;
+	struct ea_type_node *tnode;
+
+	list_for_each_entry(tnode, &ea_name_prefixes, list) {
+		p = &tnode->type;
 		if (p->prefix && !strncmp(p->prefix, key, p->prefix_len)) {
 			*len = p->prefix_len;
-			*index = p - xattr_types;
+			*index = tnode->index;
 			return true;
 		}
 	}
-	return false;
+
+	return match_short_prefix(key, index, len);
 }
 
 static struct xattr_item *parse_one_xattr(const char *path, const char *key,
@@ -740,6 +749,64 @@ out:
 	return ret;
 }
 
+
+static int erofs_xattr_filter_hashbit(struct xattr_item *item)
+{
+	u8 prefix = item->prefix;
+	const char *key = item->kvbuf;
+	unsigned int len = item->len[0];
+	char *name = NULL;
+	uint32_t hashbit;
+
+	if (prefix & EROFS_XATTR_LONG_PREFIX) {
+		struct ea_type_node *tnode;
+		u16 prefix_len;
+		int ret;
+
+		list_for_each_entry(tnode, &ea_name_prefixes, list) {
+			if (tnode->index == item->prefix) {
+				ret = asprintf(&name, "%s%.*s",
+					       tnode->type.prefix, len, key);
+				if (ret < 0)
+					return -ENOMEM;
+				break;
+			}
+		}
+		if (!name)
+			return -ENOENT;
+
+		if (!match_short_prefix(name, &prefix, &prefix_len)) {
+			free(name);
+			return -ENOENT;
+		}
+		key = name + prefix_len;
+		len = strlen(name) - prefix_len;
+	}
+
+	hashbit = xxh32(key, len, EROFS_XATTR_FILTER_SEED + prefix);
+	hashbit &= (EROFS_XATTR_FILTER_BITS - 1);
+
+	if (name)
+		free(name);
+	return hashbit;
+}
+
+static u32 erofs_xattr_filter_map(struct list_head *ixattrs)
+{
+	struct inode_xattr_node *node, *n;
+	u32 name_filter;
+	int hashbit;
+
+	name_filter = 0;
+	list_for_each_entry_safe(node, n, ixattrs, list) {
+		hashbit = erofs_xattr_filter_hashbit(node->item);
+		if (hashbit < 0)
+			return 0;
+		name_filter |= (1UL << hashbit);
+	}
+	return EROFS_XATTR_FILTER_DEFAULT & ~name_filter;
+}
+
 char *erofs_export_xattr_ibody(struct list_head *ixattrs, unsigned int size)
 {
 	struct inode_xattr_node *node, *n;
@@ -754,6 +821,11 @@ char *erofs_export_xattr_ibody(struct list_head *ixattrs, unsigned int size)
 	header = (struct erofs_xattr_ibody_header *)buf;
 	header->h_shared_count = 0;
 
+	if (cfg.c_xattr_name_filter) {
+		u32 name_filter = erofs_xattr_filter_map(ixattrs);
+		header->h_name_filter = cpu_to_le32(name_filter);
+	}
+
 	p = sizeof(struct erofs_xattr_ibody_header);
 	list_for_each_entry_safe(node, n, ixattrs, list) {
 		struct xattr_item *const item = node->item;
diff --git a/mkfs/main.c b/mkfs/main.c
index ac208e5..7db7847 100644
--- a/mkfs/main.c
+++ b/mkfs/main.c
@@ -241,6 +241,13 @@ handle_fragment:
 				return -EINVAL;
 			cfg.c_dedupe = true;
 		}
+
+		if (MATCH_EXTENTED_OPT("xattr-name-filter", token, keylen)) {
+			if (vallen)
+				return -EINVAL;
+			cfg.c_xattr_name_filter = true;
+			erofs_sb_set_xattr_filter();
+		}
 	}
 	return 0;
 }
-- 
2.19.1.6.gb485710b