[RFC 2/2] erofs: optimize getxattr with bloom filter

[Jingbo Xu]

Boost the negative xattr lookup with bloom filter.

The bit value for the bloom filter map has a reverse semantics for
compatibility.  That is, the mapped bits will be cleared to 0, while the
bit value of 1 indicates the absence of corresponding xattr.

Signed-off-by: Jingbo Xu <jeffl...@linux.alibaba.com>
---
 fs/erofs/internal.h |  2 ++
 fs/erofs/xattr.c    | 16 +++++++++++++++-
 2 files changed, 17 insertions(+), 1 deletion(-)

diff --git a/fs/erofs/internal.h b/fs/erofs/internal.h
index 1e39c03357d1..49b4b350af8a 100644
--- a/fs/erofs/internal.h
+++ b/fs/erofs/internal.h
@@ -285,6 +285,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)
 
 /* atomic flag definitions */
 #define EROFS_I_EA_INITED_BIT  0
@@ -304,6 +305,7 @@ struct erofs_inode {
        unsigned char inode_isize;
        unsigned int xattr_isize;
 
+       unsigned long xattr_bloom_map;
        unsigned int xattr_shared_count;
        unsigned int *xattr_shared_xattrs;
 
diff --git a/fs/erofs/xattr.c b/fs/erofs/xattr.c
index 4376f654474d..1ab481b46e8d 100644
--- a/fs/erofs/xattr.c
+++ b/fs/erofs/xattr.c
@@ -5,6 +5,7 @@
  * Copyright (C) 2021-2022, Alibaba Cloud
  */
 #include <linux/security.h>
+#include <linux/xxhash.h>
 #include "xattr.h"
 
 struct erofs_xattr_iter {
@@ -87,6 +88,7 @@ static int erofs_init_inode_xattrs(struct inode *inode)
        }
 
        ih = it.kaddr + erofs_blkoff(sb, it.pos);
+       vi->xattr_bloom_map = le32_to_cpu(ih->h_map);
        vi->xattr_shared_count = ih->h_shared_count;
        vi->xattr_shared_xattrs = kmalloc_array(vi->xattr_shared_count,
                                                sizeof(uint), GFP_KERNEL);
@@ -392,8 +394,11 @@ int erofs_getxattr(struct inode *inode, int index,
                   const char *name,
                   void *buffer, size_t buffer_size)
 {
-       int ret;
+       int i, ret;
+       uint32_t bit;
        struct erofs_xattr_iter it;
+       struct erofs_inode *const vi = EROFS_I(inode);
+       struct erofs_sb_info *sbi = EROFS_SB(inode->i_sb);
 
        if (!name)
                return -EINVAL;
@@ -402,6 +407,15 @@ int erofs_getxattr(struct inode *inode, int index,
        if (ret)
                return ret;
 
+       if (erofs_sb_has_xattr_bloom(sbi) && vi->xattr_bloom_map) {
+               for (i = 0; i < EROFS_XATTR_BLOOM_COUNTS; i++) {
+                       bit = xxh32(name, strlen(name), index + i);
+                       bit &= EROFS_XATTR_BLOOM_MASK;
+                       if (test_bit(bit, &vi->xattr_bloom_map))
+                               return -ENOATTR;
+               }
+       }
+
        it.index = index;
        it.name = (struct qstr)QSTR_INIT(name, strlen(name));
        if (it.name.len > EROFS_NAME_LEN)
-- 
2.19.1.6.gb485710b