[v4,2/2] erofs: boost negative xattr lookup with bloom filter
Commit Message
Optimise the negative xattr lookup with bloom filter.
The bit value for the bloom filter map has a reverse semantics for
compatibility. That is, the bit value of 0 indicates existence, while
the bit value of 1 indicates the absence of corresponding xattr.
This feature is enabled only when xattr_filter_reserved is non-zero.
The on-disk format for the filter map may change in the future, in which
case the reserved flag will be set non-zero and we don't need bothering
the compatible bits again at that time. For now disable the optimization
if this reserved flag is non-zero.
Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
---
fs/erofs/Kconfig | 1 +
fs/erofs/internal.h | 3 +++
fs/erofs/super.c | 1 +
fs/erofs/xattr.c | 13 +++++++++++++
4 files changed, 18 insertions(+)
Comments
On 2023/7/14 11:10, Jingbo Xu wrote:
> Optimise the negative xattr lookup with bloom filter.
>
> The bit value for the bloom filter map has a reverse semantics for
> compatibility. That is, the bit value of 0 indicates existence, while
> the bit value of 1 indicates the absence of corresponding xattr.
>
> This feature is enabled only when xattr_filter_reserved is non-zero.
The initial version is _only_ enabled when xattr_filter_reserved is zero.
> The on-disk format for the filter map may change in the future, in which
> case the reserved flag will be set non-zero and we don't need bothering
> the compatible bits again at that time. For now disable the optimization
> if this reserved flag is non-zero.
The filter map internals may may change in the future, ...
>
> Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
> ---
> fs/erofs/Kconfig | 1 +
> fs/erofs/internal.h | 3 +++
> fs/erofs/super.c | 1 +
> fs/erofs/xattr.c | 13 +++++++++++++
> 4 files changed, 18 insertions(+)
>
> diff --git a/fs/erofs/Kconfig b/fs/erofs/Kconfig
> index f259d92c9720..f49669def828 100644
> --- a/fs/erofs/Kconfig
> +++ b/fs/erofs/Kconfig
> @@ -38,6 +38,7 @@ config EROFS_FS_DEBUG
> config EROFS_FS_XATTR
> bool "EROFS extended attributes"
> depends on EROFS_FS
> + select XXHASH
> default y
> help
> Extended attributes are name:value pairs associated with inodes by
> diff --git a/fs/erofs/internal.h b/fs/erofs/internal.h
> index 36e32fa542f0..ebcad25e3750 100644
> --- a/fs/erofs/internal.h
> +++ b/fs/erofs/internal.h
> @@ -151,6 +151,7 @@ struct erofs_sb_info {
> u32 xattr_prefix_start;
> u8 xattr_prefix_count;
> struct erofs_xattr_prefix_item *xattr_prefixes;
> + unsigned int xattr_filter_reserved;
> #endif
> u16 device_id_mask; /* valid bits of device id to be used */
>
> @@ -251,6 +252,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)
>
> /* atomic flag definitions */
> #define EROFS_I_EA_INITED_BIT 0
> @@ -270,6 +272,7 @@ struct erofs_inode {
> unsigned char inode_isize;
> unsigned int xattr_isize;
>
> + unsigned long xattr_name_filter;
unsigned int xattr_name_filter or
u32 xattr_name_filter?
no need to use unsinged long here.
> unsigned int xattr_shared_count;
> unsigned int *xattr_shared_xattrs;
>
> diff --git a/fs/erofs/super.c b/fs/erofs/super.c
> index 9d6a3c6158bd..72122323300e 100644
> --- a/fs/erofs/super.c
> +++ b/fs/erofs/super.c
> @@ -388,6 +388,7 @@ static int erofs_read_superblock(struct super_block *sb)
> sbi->xattr_blkaddr = le32_to_cpu(dsb->xattr_blkaddr);
> sbi->xattr_prefix_start = le32_to_cpu(dsb->xattr_prefix_start);
> sbi->xattr_prefix_count = dsb->xattr_prefix_count;
> + sbi->xattr_filter_reserved = dsb->xattr_filter_reserved;
> #endif
> sbi->islotbits = ilog2(sizeof(struct erofs_inode_compact));
> sbi->root_nid = le16_to_cpu(dsb->root_nid);
> diff --git a/fs/erofs/xattr.c b/fs/erofs/xattr.c
> index 40178b6e0688..eb1d1974d4b3 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_name_filter = le32_to_cpu(ih->h_name_filter);
> vi->xattr_shared_count = ih->h_shared_count;
> vi->xattr_shared_xattrs = kmalloc_array(vi->xattr_shared_count,
> sizeof(uint), GFP_KERNEL);
> @@ -392,7 +394,10 @@ int erofs_getxattr(struct inode *inode, int index, const char *name,
> void *buffer, size_t buffer_size)
> {
> int ret;
> + uint32_t bit;
uint32_t hashbit; ?
Thanks,
Gao Xiang
@@ -38,6 +38,7 @@ config EROFS_FS_DEBUG
config EROFS_FS_XATTR
bool "EROFS extended attributes"
depends on EROFS_FS
+ select XXHASH
default y
help
Extended attributes are name:value pairs associated with inodes by
@@ -151,6 +151,7 @@ struct erofs_sb_info {
u32 xattr_prefix_start;
u8 xattr_prefix_count;
struct erofs_xattr_prefix_item *xattr_prefixes;
+ unsigned int xattr_filter_reserved;
#endif
u16 device_id_mask; /* valid bits of device id to be used */
@@ -251,6 +252,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)
/* atomic flag definitions */
#define EROFS_I_EA_INITED_BIT 0
@@ -270,6 +272,7 @@ struct erofs_inode {
unsigned char inode_isize;
unsigned int xattr_isize;
+ unsigned long xattr_name_filter;
unsigned int xattr_shared_count;
unsigned int *xattr_shared_xattrs;
@@ -388,6 +388,7 @@ static int erofs_read_superblock(struct super_block *sb)
sbi->xattr_blkaddr = le32_to_cpu(dsb->xattr_blkaddr);
sbi->xattr_prefix_start = le32_to_cpu(dsb->xattr_prefix_start);
sbi->xattr_prefix_count = dsb->xattr_prefix_count;
+ sbi->xattr_filter_reserved = dsb->xattr_filter_reserved;
#endif
sbi->islotbits = ilog2(sizeof(struct erofs_inode_compact));
sbi->root_nid = le16_to_cpu(dsb->root_nid);
@@ -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_name_filter = le32_to_cpu(ih->h_name_filter);
vi->xattr_shared_count = ih->h_shared_count;
vi->xattr_shared_xattrs = kmalloc_array(vi->xattr_shared_count,
sizeof(uint), GFP_KERNEL);
@@ -392,7 +394,10 @@ int erofs_getxattr(struct inode *inode, int index, const char *name,
void *buffer, size_t buffer_size)
{
int ret;
+ uint32_t bit;
struct erofs_xattr_iter it;
+ struct erofs_inode *vi = EROFS_I(inode);
+ struct erofs_sb_info *sbi = EROFS_SB(inode->i_sb);
if (!name)
return -EINVAL;
@@ -401,6 +406,14 @@ int erofs_getxattr(struct inode *inode, int index, const char *name,
if (ret)
return ret;
+ /* reserved flag is non-zero if there's any change of on-disk format */
+ if (erofs_sb_has_xattr_filter(sbi) && !sbi->xattr_filter_reserved) {
+ bit = xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index);
+ bit &= EROFS_XATTR_FILTER_BITS - 1;
+ if (test_bit(bit, &vi->xattr_name_filter))
+ return -ENOATTR;
+ }
+
it.index = index;
it.name = (struct qstr)QSTR_INIT(name, strlen(name));
if (it.name.len > EROFS_NAME_LEN)