[v5,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.
The initial version is _only_ enabled when xattr_filter_reserved is
zero. The filter map internals 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 | 14 ++++++++++++++
4 files changed, 19 insertions(+)
Comments
On Fri, Jul 21, 2023 at 06:49:23PM +0800, 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.
>
> The initial version is _only_ enabled when xattr_filter_reserved is
> zero. The filter map internals 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 | 14 ++++++++++++++
> 4 files changed, 19 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..3c1f89d8421b 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 int xattr_name_filter;
> 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..e9b9ed6b28d2 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 hashbit;
Why using `uint32_t` here rather than `unsigned int`? We don't use
`uint32_t` in the kernel codebase.
Thanks,
Gao Xiang
On 7/22/23 3:05 PM, Gao Xiang wrote:
> On Fri, Jul 21, 2023 at 06:49:23PM +0800, 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.
>>
>> The initial version is _only_ enabled when xattr_filter_reserved is
>> zero. The filter map internals 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 | 14 ++++++++++++++
>> 4 files changed, 19 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..3c1f89d8421b 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 int xattr_name_filter;
>> 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..e9b9ed6b28d2 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 hashbit;
>
> Why using `uint32_t` here rather than `unsigned int`? We don't use
> `uint32_t` in the kernel codebase.
>
xxh32() returns uint32_t.
On Sat, Jul 22, 2023 at 03:33:11PM +0800, Jingbo Xu wrote:
...
> >> + uint32_t hashbit;
> >
> > Why using `uint32_t` here rather than `unsigned int`? We don't use
> > `uint32_t` in the kernel codebase.
> >
>
> xxh32() returns uint32_t.
we never use (u)intxx_t in the native kernel code.
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 int 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 hashbit;
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,15 @@ 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) {
+ hashbit = xxh32(name, strlen(name),
+ EROFS_XATTR_FILTER_SEED + index);
+ hashbit &= EROFS_XATTR_FILTER_BITS - 1;
+ if (vi->xattr_name_filter & (1U << hashbit))
+ return -ENOATTR;
+ }
+
it.index = index;
it.name = (struct qstr)QSTR_INIT(name, strlen(name));
if (it.name.len > EROFS_NAME_LEN)