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). Signed-off-by: Jingbo Xu <[email protected]> --- include/erofs_fs.h | 10 +++++++++- 1 file changed, 9 insertions(+), 1 deletion(-) diff --git a/include/erofs_fs.h b/include/erofs_fs.h index 9107cc5..4f79e59 100644 --- a/include/erofs_fs.h +++ b/include/erofs_fs.h @@ -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 */ -- 2.19.1.6.gb485710b
