[PATCH v2 0/2] erofs: introduce xattr name bloom filter

[PATCH v2 0/2] erofs: introduce xattr name bloom filter

[Jingbo Xu]

changes since RFC:
- the number of hash functions is 1, and now it's implemented as:
    xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index),
  where the constant magic number EROFS_XATTR_FILTER_SEED [*] is used to
  give a better spread for the mapping. (Alexander Larsson)
  Refer to patch 1 for more details.
- fix the value of EROFS_FEATURE_COMPAT_XATTR_BLOOM; rename
  EROFS_XATTR_BLOOM_* to EROFS_XATTR_FILTER_* (Gao Xiang)
- pass all tests in erofs-utils (MKFS_OPTIONS="--xattr-filter" make
  check)

[*] https://lore.kernel.org/all/74a8a369-c3b0-b338-fa8f-fdd7c252efaf@linux.alibaba.com/
RFC: https://lore.kernel.org/all/20230621083209.116024-1-jefflexu@linux.alibaba.com/


Background
==========
Filesystems with ACL enabled generally need to read
"system.posix_acl_access"/"system.posix_acl_default" xattr to get the
access and default ACL.  When filesystem is mounted with ACL enabled
while files in the system have not set access/default ACL, the getattr()
will run in vain while the round trip can decrease the performance in
workload like "ls -lR".

For example, there's a 12% performance boost if erofs is mounted with
"noacl" when running "ls -lR" workload on dataset [1] (given in [2]).

We'd better offer a fastpath to boost the above workload, as well as
other negative xattr lookup.


Proposal
========
Introduce a per-inode bloom filter for xattrs to boost the negative
xattr queries.

As following shows, a 32-bit bloom filter is introduced for each inode,
describing if a xattr with specific name exists on this inode.

```
 struct erofs_xattr_ibody_header {
-       __le32 h_reserved;
+       __le32 h_map; /* bloom filter */
	...
}
```

Following are some implementation details for bloom filter.

1. Reverse bit value
--------------------
The bloom filter structure describes if a given data is inside the set.
It will map the given data into several bits of the bloom filter map.
The data must not exist inside the set if any mapped bit is 0, while the
data may be not inside the set even if all mapped bits is 1.

While in our use case, as erofs_xattr_ibody_header.h_map is previously a
(all zero) reserved field, the bit value for the bloom filter has a
reverse semantics in consideration for compatibility.  That is, for a
given data, the mapped bits will be cleared to 0.  Thus for a previously
built image without support for bloom filter, the bloom filter is all
zero and when it's mounted by the new kernel with support for bloom
filter, it can not determine if the queried xattr exists on the inode and
thus will fallback to the original routine of iterating all on-disk
xattrs to determine if the queried xattr exists.


2. The number of hash functions
-------------------------------
The optimal value for the number of the hash functions (k) is (ln2 *
m/n), where m stands the number of bits of the bloom filter map, while n
stands the number of all candidates may be inside the set.

In our use case, 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).


3. The hash function
--------------------
xxh32() is chosen as the hash function.

Following are some tested statistics of several candidate hash
functions.  Listed are time (in millionsecond) consumed when these hash
functions process input data in chunks of 24, 32, 64 and 4096 bytes.

	| 24 B 	| 32 B	| 64 B	| 4 KB
--------+-------+-------+-------+------
jhash	| 1325	| 2041 	| 4016	|  2294
jhash2	| 1323	| 2035	| 4011	|  2310
crc16	| 7918	| 1056	| 2110	| 13784
crc32	| 1824	| 2436	| 4873	|  3107
crc32c	| 2120	| 2708	| 5142	|  3109
xxhash	| 1320	| 1967	| 2131	|   429
xxh32	| 1458	| 1358	| 1848	|   836
xxh64	| 1321	| 2081	| 2128	|   429


3.1. multiple hash functions with various seeds
-----------------------------------------------
As previously described, the given data will be mapped into several bits
of the bloom filter map with hash functions.  There could be several
hash functions (k), with each hash function mapping the given data into
one bit of the bloom filter map.  Thus given the number of hash
functions (k), each xattr name will be mapped into k bits of the bloom
filter map.

Here in our use case, k hash functions are all xxh32() but with
different seeds.  As following shows, the seed is (index + i), where i
stands the index of the current hash function among all hash functions.
In this way, each hash function is distinguishable with others.

```
for (i = 0; i < k; i++)
	bit = xxh32(name, strlen(name), index + i);
```

3.2. input of hash function
-------------------------
As previously described, each hash function will map the given data into
one bit of the bloom filter map.  In our use case, xattr name serves as
the key of hash function.

When .getxattr() gets called, only index (e.g. EROFS_XATTR_INDEX_USER)
and the remaining name apart from the prefix are handy.  To avoid
constructing the full xattr name, the above index and name are fed into
the hash function directly in the following way:

```
bit = xxh32(name, strlen(name), index + i);
```

where index serves as part of seed, so that it gets involved in the
calculation for the hash.

An alternative way is to calculate the hash from the full xattr name by
feeding the prefix string and the remaining name string separately in
the following way:

```
xxh32_reset()
xxh32_update(prefix string, ...)
xxh32_update(remaining name, ...)
xxh32_digest()
```

But I doubt if it really deserves to call multiple APIs instead of one
single xxh32().


Also be noted that for xattrs with long xattr name prefixes, the
above "name" is the xattr name after stripping the corresponding short
predefined xattr name prefix rather than the long xattr name prefix, as
only the former is handy in the kernel routine.


3.3. discussions
----------------
I think a wider discussion on the implementation details is needed,
including the number of the hash functions, and all other implementation
details mentioned above, as they are also part of the on-disk format.


Performance Improvement
=======================
The performance statistics are tested with 'ls -lR' workload upon the
dataset [1].
			| uncached(ms)  | cached(ms)
------------------------+---------------+----------
erofs.share		| 468		| 264
erofs.share.bloom	| 370		| 254
erofs.share.noacl	| 412		| 216
erofs.share.noacl.bloom	| 318		| 206

The tested erofs image is built in shared xattr layout.  It indicates
~20% performance improvement with bloom filter in uncached scenarios.


[1] https://my.owndrive.com/index.php/s/irHJXRpZHtT3a5i
[2] https://lore.kernel.org/all/071074ad149b189661681aada453995741f75039.camel@redhat.com/


Jingbo Xu (2):
  erofs: update on-disk format for xattr name filter
  erofs: boost negative xattr lookup with bloom filter

 fs/erofs/erofs_fs.h |  8 +++++++-
 fs/erofs/internal.h |  2 ++
 fs/erofs/xattr.c    | 12 ++++++++++++
 3 files changed, 21 insertions(+), 1 deletion(-)

-- 
2.19.1.6.gb485710b

[PATCH v2 1/2] erofs: update on-disk format for xattr name filter

[Jingbo Xu]

The xattr name 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 extended attributes (n) is approximately 30.

	trusted.overlay.opaque
	trusted.overlay.redirect
	trusted.overlay.origin
	trusted.overlay.impure
	trusted.overlay.nlink
	trusted.overlay.upper
	trusted.overlay.metacopy
	trusted.overlay.protattr
	user.overlay.opaque
	user.overlay.redirect
	user.overlay.origin
	user.overlay.impure
	user.overlay.nlink
	user.overlay.upper
	user.overlay.metacopy
	user.overlay.protattr
	security.evm
	security.ima
	security.selinux
	security.SMACK64
	security.SMACK64IPIN
	security.SMACK64IPOUT
	security.SMACK64EXEC
	security.SMACK64TRANSMUTE
	security.SMACK64MMAP
	security.apparmor
	security.capability
	system.posix_acl_access
	system.posix_acl_default
	user.mime_type

Given the number of bits of the bloom filter (m) is 32, the optimal
value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).

The single hash function is implemented as:

	xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)

where index represents the index of corresponding predefined short name
prefix, while name represents the name string after stripping the above
predefined name prefix.

The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
used to give a better spread when mapping these 30 extended attributes
into 32-bit bloom filter as:

	bit  0: security.ima
	bit  1:
	bit  2: trusted.overlay.nlink
	bit  3:
	bit  4: user.overlay.nlink
	bit  5: trusted.overlay.upper
	bit  6: user.overlay.origin
	bit  7: trusted.overlay.protattr
	bit  8: security.apparmor
	bit  9: user.overlay.protattr
	bit 10: user.overlay.opaque
	bit 11: security.selinux
	bit 12: security.SMACK64TRANSMUTE
	bit 13: security.SMACK64
	bit 14: security.SMACK64MMAP
	bit 15: user.overlay.impure
	bit 16: security.SMACK64IPIN
	bit 17: trusted.overlay.redirect
	bit 18: trusted.overlay.origin
	bit 19: security.SMACK64IPOUT
	bit 20: trusted.overlay.opaque
	bit 21: system.posix_acl_default
	bit 22:
	bit 23: user.mime_type
	bit 24: trusted.overlay.impure
	bit 25: security.SMACK64EXEC
	bit 26: user.overlay.redirect
	bit 27: user.overlay.upper
	bit 28: security.evm
	bit 29: security.capability
	bit 30: system.posix_acl_access
	bit 31: trusted.overlay.metacopy, user.overlay.metacopy

The h_name_filter field is introduced to the on-disk per-inode xattr
header to place the corresponding xattr name filter, where bit value 1
indicates non-existence for compatibility.

This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
compatible feature bit.

Suggested-by: Alexander Larsson <alexl@redhat.com>
Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
---
 fs/erofs/erofs_fs.h | 8 +++++++-
 1 file changed, 7 insertions(+), 1 deletion(-)

diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h
index 2c7b16e340fe..b4b6235fd720 100644
--- a/fs/erofs/erofs_fs.h
+++ b/fs/erofs/erofs_fs.h
@@ -13,6 +13,7 @@
 
 #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
 #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
+#define EROFS_FEATURE_COMPAT_XATTR_FILTER	0x00000004
 
 /*
  * Any bits that aren't in EROFS_ALL_FEATURE_INCOMPAT should
@@ -200,7 +201,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_name_filter;		/* bit value 1 indicates not-present */
 	__u8   h_shared_count;
 	__u8   h_reserved2[7];
 	__le32 h_shared_xattrs[];       /* shared xattr id array */
@@ -221,6 +222,11 @@ struct erofs_xattr_ibody_header {
 #define EROFS_XATTR_LONG_PREFIX		0x80
 #define EROFS_XATTR_LONG_PREFIX_MASK	0x7f
 
+#define EROFS_XATTR_FILTER_BITS		32
+#define EROFS_XATTR_FILTER_MASK		(EROFS_XATTR_FILTER_BITS - 1)
+#define EROFS_XATTR_FILTER_DEFAULT	UINT32_MAX
+#define EROFS_XATTR_FILTER_SEED		0x25BBE08F
+
 /* xattr entry (for both inline & shared xattrs) */
 struct erofs_xattr_entry {
 	__u8   e_name_len;      /* length of name */
-- 
2.19.1.6.gb485710b

[PATCH v2 2/2] erofs: boost negative xattr lookup with bloom filter

[Jingbo Xu]

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.

Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
---
 fs/erofs/internal.h |  2 ++
 fs/erofs/xattr.c    | 12 ++++++++++++
 2 files changed, 14 insertions(+)

diff --git a/fs/erofs/internal.h b/fs/erofs/internal.h
index 36e32fa542f0..7e447b48a46b 100644
--- a/fs/erofs/internal.h
+++ b/fs/erofs/internal.h
@@ -251,6 +251,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 +271,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;
 
diff --git a/fs/erofs/xattr.c b/fs/erofs/xattr.c
index 40178b6e0688..1137723303d3 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;
 	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,13 @@ int erofs_getxattr(struct inode *inode, int index, const char *name,
 	if (ret)
 		return ret;
 
+	if (erofs_sb_has_xattr_filter(sbi)) {
+		bit = xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index);
+		bit &= EROFS_XATTR_FILTER_MASK;
+		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)
-- 
2.19.1.6.gb485710b

Re: [PATCH v2 1/2] erofs: update on-disk format for xattr name filter

[Gao Xiang]

On 2023/7/5 15:04, Jingbo Xu wrote:
> The xattr name 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 extended attributes (n) is approximately 30.

There are some commonly used extended attributes (n) and the total number
of these is 31:

> 
> 	trusted.overlay.opaque
> 	trusted.overlay.redirect
> 	trusted.overlay.origin
> 	trusted.overlay.impure
> 	trusted.overlay.nlink
> 	trusted.overlay.upper
> 	trusted.overlay.metacopy
> 	trusted.overlay.protattr
> 	user.overlay.opaque
> 	user.overlay.redirect
> 	user.overlay.origin
> 	user.overlay.impure
> 	user.overlay.nlink
> 	user.overlay.upper
> 	user.overlay.metacopy
> 	user.overlay.protattr
> 	security.evm
> 	security.ima
> 	security.selinux
> 	security.SMACK64
> 	security.SMACK64IPIN
> 	security.SMACK64IPOUT
> 	security.SMACK64EXEC
> 	security.SMACK64TRANSMUTE
> 	security.SMACK64MMAP
> 	security.apparmor
> 	security.capability
> 	system.posix_acl_access
> 	system.posix_acl_default
> 	user.mime_type
> 
> Given the number of bits of the bloom filter (m) is 32, the optimal
> value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).
> 
> The single hash function is implemented as:
> 
> 	xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)
> 
> where index represents the index of corresponding predefined short name

where `index`...



> prefix, while name represents the name string after stripping the above
> predefined name prefix.
> 
> The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
> used to give a better spread when mapping these 30 extended attributes
> into 32-bit bloom filter as:
> 
> 	bit  0: security.ima
> 	bit  1:
> 	bit  2: trusted.overlay.nlink
> 	bit  3:
> 	bit  4: user.overlay.nlink
> 	bit  5: trusted.overlay.upper
> 	bit  6: user.overlay.origin
> 	bit  7: trusted.overlay.protattr
> 	bit  8: security.apparmor
> 	bit  9: user.overlay.protattr
> 	bit 10: user.overlay.opaque
> 	bit 11: security.selinux
> 	bit 12: security.SMACK64TRANSMUTE
> 	bit 13: security.SMACK64
> 	bit 14: security.SMACK64MMAP
> 	bit 15: user.overlay.impure
> 	bit 16: security.SMACK64IPIN
> 	bit 17: trusted.overlay.redirect
> 	bit 18: trusted.overlay.origin
> 	bit 19: security.SMACK64IPOUT
> 	bit 20: trusted.overlay.opaque
> 	bit 21: system.posix_acl_default
> 	bit 22:
> 	bit 23: user.mime_type
> 	bit 24: trusted.overlay.impure
> 	bit 25: security.SMACK64EXEC
> 	bit 26: user.overlay.redirect
> 	bit 27: user.overlay.upper
> 	bit 28: security.evm
> 	bit 29: security.capability
> 	bit 30: system.posix_acl_access
> 	bit 31: trusted.overlay.metacopy, user.overlay.metacopy
> 
> The h_name_filter field is introduced to the on-disk per-inode xattr
> header to place the corresponding xattr name filter, where bit value 1
> indicates non-existence for compatibility.
> 
> This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
> compatible feature bit.
> 
> Suggested-by: Alexander Larsson <alexl@redhat.com>
> Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
> ---
>   fs/erofs/erofs_fs.h | 8 +++++++-
>   1 file changed, 7 insertions(+), 1 deletion(-)
> 
> diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h
> index 2c7b16e340fe..b4b6235fd720 100644
> --- a/fs/erofs/erofs_fs.h
> +++ b/fs/erofs/erofs_fs.h
> @@ -13,6 +13,7 @@
>   
>   #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
>   #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
> +#define EROFS_FEATURE_COMPAT_XATTR_FILTER	0x00000004

I'd suggest that if we could leave one reserved byte in the
superblock for now (and checking if it's 0) since
   1) xattr filter feature is a compatible feature;
   2) I'm not sure if the implementation could be changed.

so that later implementation changes won't bother compat bits
again.

>   
>   /*
>    * Any bits that aren't in EROFS_ALL_FEATURE_INCOMPAT should
> @@ -200,7 +201,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_name_filter;		/* bit value 1 indicates not-present */
>   	__u8   h_shared_count;
>   	__u8   h_reserved2[7];
>   	__le32 h_shared_xattrs[];       /* shared xattr id array */
> @@ -221,6 +222,11 @@ struct erofs_xattr_ibody_header {
>   #define EROFS_XATTR_LONG_PREFIX		0x80
>   #define EROFS_XATTR_LONG_PREFIX_MASK	0x7f
>   
> +#define EROFS_XATTR_FILTER_BITS		32
> +#define EROFS_XATTR_FILTER_MASK		(EROFS_XATTR_FILTER_BITS - 1)

Is this useful, we could just replace it to
(EROFS_XATTR_FILTER_BITS - 1) directly.


Otherwise it looks good to me,

Thanks,
Gao Xiang

Re: [PATCH v2 1/2] erofs: update on-disk format for xattr name filter

[Alexander Larsson]

On Wed, Jul 5, 2023 at 9:25 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>
>
>
> On 2023/7/5 15:04, Jingbo Xu wrote:
> > The xattr name 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 extended attributes (n) is approximately 30.
>
> There are some commonly used extended attributes (n) and the total number
> of these is 31:
>
> >
> >       trusted.overlay.opaque
> >       trusted.overlay.redirect
> >       trusted.overlay.origin
> >       trusted.overlay.impure
> >       trusted.overlay.nlink
> >       trusted.overlay.upper
> >       trusted.overlay.metacopy
> >       trusted.overlay.protattr
> >       user.overlay.opaque
> >       user.overlay.redirect
> >       user.overlay.origin
> >       user.overlay.impure
> >       user.overlay.nlink
> >       user.overlay.upper
> >       user.overlay.metacopy
> >       user.overlay.protattr
> >       security.evm
> >       security.ima
> >       security.selinux
> >       security.SMACK64
> >       security.SMACK64IPIN
> >       security.SMACK64IPOUT
> >       security.SMACK64EXEC
> >       security.SMACK64TRANSMUTE
> >       security.SMACK64MMAP
> >       security.apparmor
> >       security.capability
> >       system.posix_acl_access
> >       system.posix_acl_default
> >       user.mime_type
> >
> > Given the number of bits of the bloom filter (m) is 32, the optimal
> > value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).
> >
> > The single hash function is implemented as:
> >
> >       xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)
> >
> > where index represents the index of corresponding predefined short name
>
> where `index`...
>
>
>
> > prefix, while name represents the name string after stripping the above
> > predefined name prefix.
> >
> > The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
> > used to give a better spread when mapping these 30 extended attributes
> > into 32-bit bloom filter as:
> >
> >       bit  0: security.ima
> >       bit  1:
> >       bit  2: trusted.overlay.nlink
> >       bit  3:
> >       bit  4: user.overlay.nlink
> >       bit  5: trusted.overlay.upper
> >       bit  6: user.overlay.origin
> >       bit  7: trusted.overlay.protattr
> >       bit  8: security.apparmor
> >       bit  9: user.overlay.protattr
> >       bit 10: user.overlay.opaque
> >       bit 11: security.selinux
> >       bit 12: security.SMACK64TRANSMUTE
> >       bit 13: security.SMACK64
> >       bit 14: security.SMACK64MMAP
> >       bit 15: user.overlay.impure
> >       bit 16: security.SMACK64IPIN
> >       bit 17: trusted.overlay.redirect
> >       bit 18: trusted.overlay.origin
> >       bit 19: security.SMACK64IPOUT
> >       bit 20: trusted.overlay.opaque
> >       bit 21: system.posix_acl_default
> >       bit 22:
> >       bit 23: user.mime_type
> >       bit 24: trusted.overlay.impure
> >       bit 25: security.SMACK64EXEC
> >       bit 26: user.overlay.redirect
> >       bit 27: user.overlay.upper
> >       bit 28: security.evm
> >       bit 29: security.capability
> >       bit 30: system.posix_acl_access
> >       bit 31: trusted.overlay.metacopy, user.overlay.metacopy
> >
> > The h_name_filter field is introduced to the on-disk per-inode xattr
> > header to place the corresponding xattr name filter, where bit value 1
> > indicates non-existence for compatibility.
> >
> > This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
> > compatible feature bit.
> >
> > Suggested-by: Alexander Larsson <alexl@redhat.com>
> > Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
> > ---
> >   fs/erofs/erofs_fs.h | 8 +++++++-
> >   1 file changed, 7 insertions(+), 1 deletion(-)
> >
> > diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h
> > index 2c7b16e340fe..b4b6235fd720 100644
> > --- a/fs/erofs/erofs_fs.h
> > +++ b/fs/erofs/erofs_fs.h
> > @@ -13,6 +13,7 @@
> >
> >   #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
> >   #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
> > +#define EROFS_FEATURE_COMPAT_XATTR_FILTER    0x00000004
>
> I'd suggest that if we could leave one reserved byte in the
> superblock for now (and checking if it's 0) since
>    1) xattr filter feature is a compatible feature;
>    2) I'm not sure if the implementation could be changed.
>
> so that later implementation changes won't bother compat bits
> again.

I would very much like to generate these bloom filters in composefs
right now, before the composefs v1 format is completely locked down,
and this should be fully possible given that this is a backwards
compat change. But this is only possible if it doesn't require a
feature flag like this that makes old erofs versions not mount the
image.


-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
 Alexander Larsson                                Red Hat, Inc
       alexl@redhat.com         alexander.larsson@gmail.com

Re: [PATCH v2 1/2] erofs: update on-disk format for xattr name filter

[Alexander Larsson]

On Wed, Jul 5, 2023 at 9:25 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>
>
>
> On 2023/7/5 15:04, Jingbo Xu wrote:
> > The xattr name 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 extended attributes (n) is approximately 30.
>
> There are some commonly used extended attributes (n) and the total number
> of these is 31:
>
> >
> >       trusted.overlay.opaque
> >       trusted.overlay.redirect
> >       trusted.overlay.origin
> >       trusted.overlay.impure
> >       trusted.overlay.nlink
> >       trusted.overlay.upper
> >       trusted.overlay.metacopy
> >       trusted.overlay.protattr
> >       user.overlay.opaque
> >       user.overlay.redirect
> >       user.overlay.origin
> >       user.overlay.impure
> >       user.overlay.nlink
> >       user.overlay.upper
> >       user.overlay.metacopy
> >       user.overlay.protattr
> >       security.evm
> >       security.ima
> >       security.selinux
> >       security.SMACK64
> >       security.SMACK64IPIN
> >       security.SMACK64IPOUT
> >       security.SMACK64EXEC
> >       security.SMACK64TRANSMUTE
> >       security.SMACK64MMAP
> >       security.apparmor
> >       security.capability
> >       system.posix_acl_access
> >       system.posix_acl_default
> >       user.mime_type
> >
> > Given the number of bits of the bloom filter (m) is 32, the optimal
> > value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).
> >
> > The single hash function is implemented as:
> >
> >       xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)
> >
> > where index represents the index of corresponding predefined short name
>
> where `index`...
>
>
>
> > prefix, while name represents the name string after stripping the above
> > predefined name prefix.
> >
> > The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
> > used to give a better spread when mapping these 30 extended attributes
> > into 32-bit bloom filter as:
> >
> >       bit  0: security.ima
> >       bit  1:
> >       bit  2: trusted.overlay.nlink
> >       bit  3:
> >       bit  4: user.overlay.nlink
> >       bit  5: trusted.overlay.upper
> >       bit  6: user.overlay.origin
> >       bit  7: trusted.overlay.protattr
> >       bit  8: security.apparmor
> >       bit  9: user.overlay.protattr
> >       bit 10: user.overlay.opaque
> >       bit 11: security.selinux
> >       bit 12: security.SMACK64TRANSMUTE
> >       bit 13: security.SMACK64
> >       bit 14: security.SMACK64MMAP
> >       bit 15: user.overlay.impure
> >       bit 16: security.SMACK64IPIN
> >       bit 17: trusted.overlay.redirect
> >       bit 18: trusted.overlay.origin
> >       bit 19: security.SMACK64IPOUT
> >       bit 20: trusted.overlay.opaque
> >       bit 21: system.posix_acl_default
> >       bit 22:
> >       bit 23: user.mime_type
> >       bit 24: trusted.overlay.impure
> >       bit 25: security.SMACK64EXEC
> >       bit 26: user.overlay.redirect
> >       bit 27: user.overlay.upper
> >       bit 28: security.evm
> >       bit 29: security.capability
> >       bit 30: system.posix_acl_access
> >       bit 31: trusted.overlay.metacopy, user.overlay.metacopy
> >
> > The h_name_filter field is introduced to the on-disk per-inode xattr
> > header to place the corresponding xattr name filter, where bit value 1
> > indicates non-existence for compatibility.
> >
> > This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
> > compatible feature bit.
> >
> > Suggested-by: Alexander Larsson <alexl@redhat.com>
> > Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
> > ---
> >   fs/erofs/erofs_fs.h | 8 +++++++-
> >   1 file changed, 7 insertions(+), 1 deletion(-)
> >
> > diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h
> > index 2c7b16e340fe..b4b6235fd720 100644
> > --- a/fs/erofs/erofs_fs.h
> > +++ b/fs/erofs/erofs_fs.h
> > @@ -13,6 +13,7 @@
> >
> >   #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
> >   #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
> > +#define EROFS_FEATURE_COMPAT_XATTR_FILTER    0x00000004
>
> I'd suggest that if we could leave one reserved byte in the
> superblock for now (and checking if it's 0) since
>    1) xattr filter feature is a compatible feature;
>    2) I'm not sure if the implementation could be changed.
>
> so that later implementation changes won't bother compat bits
> again.

I would very much like to generate these bloom filters in composefs
right now, before the composefs v1 format is completely locked down,
and this should be fully possible given that this is a backwards
compat change. But this is only possible if it doesn't require a
feature flag like this that makes old erofs versions not mount the
image.


-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
 Alexander Larsson                                Red Hat, Inc
       alexl@redhat.com         alexander.larsson@gmail.com

Re: [PATCH v2 2/2] erofs: boost negative xattr lookup with bloom filter

[Alexander Larsson]

On Wed, Jul 5, 2023 at 9:04 AM Jingbo Xu <jefflexu@linux.alibaba.com> wrote:
>
> 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.
>
> Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
> ---
>  fs/erofs/internal.h |  2 ++
>  fs/erofs/xattr.c    | 12 ++++++++++++
>  2 files changed, 14 insertions(+)
>
> diff --git a/fs/erofs/internal.h b/fs/erofs/internal.h
> index 36e32fa542f0..7e447b48a46b 100644
> --- a/fs/erofs/internal.h
> +++ b/fs/erofs/internal.h
> @@ -251,6 +251,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 +271,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;
>
> diff --git a/fs/erofs/xattr.c b/fs/erofs/xattr.c
> index 40178b6e0688..1137723303d3 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;
>         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,13 @@ int erofs_getxattr(struct inode *inode, int index, const char *name,
>         if (ret)
>                 return ret;
>
> +       if (erofs_sb_has_xattr_filter(sbi)) {

As I said in my other mail. I would really like this to just always do
the filter check. It should be safe as older fs:es have zero in place
here, and doing this allows me to create composefs images with the
bloom filters that also work with older kernels.

> +               bit = xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index);
> +               bit &= EROFS_XATTR_FILTER_MASK;
> +               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)
> --
> 2.19.1.6.gb485710b
>


-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
 Alexander Larsson                                Red Hat, Inc
       alexl@redhat.com         alexander.larsson@gmail.com

Re: [PATCH v2 2/2] erofs: boost negative xattr lookup with bloom filter

[Alexander Larsson]

On Wed, Jul 5, 2023 at 9:04 AM Jingbo Xu <jefflexu@linux.alibaba.com> wrote:
>
> 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.
>
> Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
> ---
>  fs/erofs/internal.h |  2 ++
>  fs/erofs/xattr.c    | 12 ++++++++++++
>  2 files changed, 14 insertions(+)
>
> diff --git a/fs/erofs/internal.h b/fs/erofs/internal.h
> index 36e32fa542f0..7e447b48a46b 100644
> --- a/fs/erofs/internal.h
> +++ b/fs/erofs/internal.h
> @@ -251,6 +251,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 +271,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;
>
> diff --git a/fs/erofs/xattr.c b/fs/erofs/xattr.c
> index 40178b6e0688..1137723303d3 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;
>         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,13 @@ int erofs_getxattr(struct inode *inode, int index, const char *name,
>         if (ret)
>                 return ret;
>
> +       if (erofs_sb_has_xattr_filter(sbi)) {

As I said in my other mail. I would really like this to just always do
the filter check. It should be safe as older fs:es have zero in place
here, and doing this allows me to create composefs images with the
bloom filters that also work with older kernels.

> +               bit = xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index);
> +               bit &= EROFS_XATTR_FILTER_MASK;
> +               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)
> --
> 2.19.1.6.gb485710b
>


-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
 Alexander Larsson                                Red Hat, Inc
       alexl@redhat.com         alexander.larsson@gmail.com

Re: [PATCH v2 1/2] erofs: update on-disk format for xattr name filter

[Gao Xiang]

On 2023/7/5 15:43, Alexander Larsson wrote:
> On Wed, Jul 5, 2023 at 9:25 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>>
>>
>>
>> On 2023/7/5 15:04, Jingbo Xu wrote:
>>> The xattr name 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 extended attributes (n) is approximately 30.
>>
>> There are some commonly used extended attributes (n) and the total number
>> of these is 31:
>>
>>>
>>>        trusted.overlay.opaque
>>>        trusted.overlay.redirect
>>>        trusted.overlay.origin
>>>        trusted.overlay.impure
>>>        trusted.overlay.nlink
>>>        trusted.overlay.upper
>>>        trusted.overlay.metacopy
>>>        trusted.overlay.protattr
>>>        user.overlay.opaque
>>>        user.overlay.redirect
>>>        user.overlay.origin
>>>        user.overlay.impure
>>>        user.overlay.nlink
>>>        user.overlay.upper
>>>        user.overlay.metacopy
>>>        user.overlay.protattr
>>>        security.evm
>>>        security.ima
>>>        security.selinux
>>>        security.SMACK64
>>>        security.SMACK64IPIN
>>>        security.SMACK64IPOUT
>>>        security.SMACK64EXEC
>>>        security.SMACK64TRANSMUTE
>>>        security.SMACK64MMAP
>>>        security.apparmor
>>>        security.capability
>>>        system.posix_acl_access
>>>        system.posix_acl_default
>>>        user.mime_type
>>>
>>> Given the number of bits of the bloom filter (m) is 32, the optimal
>>> value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).
>>>
>>> The single hash function is implemented as:
>>>
>>>        xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)
>>>
>>> where index represents the index of corresponding predefined short name
>>
>> where `index`...
>>
>>
>>
>>> prefix, while name represents the name string after stripping the above
>>> predefined name prefix.
>>>
>>> The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
>>> used to give a better spread when mapping these 30 extended attributes
>>> into 32-bit bloom filter as:
>>>
>>>        bit  0: security.ima
>>>        bit  1:
>>>        bit  2: trusted.overlay.nlink
>>>        bit  3:
>>>        bit  4: user.overlay.nlink
>>>        bit  5: trusted.overlay.upper
>>>        bit  6: user.overlay.origin
>>>        bit  7: trusted.overlay.protattr
>>>        bit  8: security.apparmor
>>>        bit  9: user.overlay.protattr
>>>        bit 10: user.overlay.opaque
>>>        bit 11: security.selinux
>>>        bit 12: security.SMACK64TRANSMUTE
>>>        bit 13: security.SMACK64
>>>        bit 14: security.SMACK64MMAP
>>>        bit 15: user.overlay.impure
>>>        bit 16: security.SMACK64IPIN
>>>        bit 17: trusted.overlay.redirect
>>>        bit 18: trusted.overlay.origin
>>>        bit 19: security.SMACK64IPOUT
>>>        bit 20: trusted.overlay.opaque
>>>        bit 21: system.posix_acl_default
>>>        bit 22:
>>>        bit 23: user.mime_type
>>>        bit 24: trusted.overlay.impure
>>>        bit 25: security.SMACK64EXEC
>>>        bit 26: user.overlay.redirect
>>>        bit 27: user.overlay.upper
>>>        bit 28: security.evm
>>>        bit 29: security.capability
>>>        bit 30: system.posix_acl_access
>>>        bit 31: trusted.overlay.metacopy, user.overlay.metacopy
>>>
>>> The h_name_filter field is introduced to the on-disk per-inode xattr
>>> header to place the corresponding xattr name filter, where bit value 1
>>> indicates non-existence for compatibility.
>>>
>>> This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
>>> compatible feature bit.
>>>
>>> Suggested-by: Alexander Larsson <alexl@redhat.com>
>>> Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
>>> ---
>>>    fs/erofs/erofs_fs.h | 8 +++++++-
>>>    1 file changed, 7 insertions(+), 1 deletion(-)
>>>
>>> diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h
>>> index 2c7b16e340fe..b4b6235fd720 100644
>>> --- a/fs/erofs/erofs_fs.h
>>> +++ b/fs/erofs/erofs_fs.h
>>> @@ -13,6 +13,7 @@
>>>
>>>    #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
>>>    #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
>>> +#define EROFS_FEATURE_COMPAT_XATTR_FILTER    0x00000004
>>
>> I'd suggest that if we could leave one reserved byte in the
>> superblock for now (and checking if it's 0) since
>>     1) xattr filter feature is a compatible feature;
>>     2) I'm not sure if the implementation could be changed.
>>
>> so that later implementation changes won't bother compat bits
>> again.
> 
> I would very much like to generate these bloom filters in composefs
> right now, before the composefs v1 format is completely locked down,
> and this should be fully possible given that this is a backwards
> compat change. But this is only possible if it doesn't require a
> feature flag like this that makes old erofs versions not mount the
> image.

EROFS has two types of feature bits:

  1) compat flags, which doesn't block mounting on old kernels;
  2) incompat flags, which will block mounting on old kernels.

here bloom filter use a new compat flag, so old kernels will just
ignore this and mount.  compat flags just indicates that "an image
with a feature, and you could use it or not".

Here I just meant the bloom filter internals are fixed for now,
so that we might reserve a byte in the on-disk super block for
later potential changes (if any).  And don't need to bother another
new compat flag.

Thanks,
Gao Xiang

Re: [PATCH v2 1/2] erofs: update on-disk format for xattr name filter

[Gao Xiang]

On 2023/7/5 15:43, Alexander Larsson wrote:
> On Wed, Jul 5, 2023 at 9:25 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>>
>>
>>
>> On 2023/7/5 15:04, Jingbo Xu wrote:
>>> The xattr name 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 extended attributes (n) is approximately 30.
>>
>> There are some commonly used extended attributes (n) and the total number
>> of these is 31:
>>
>>>
>>>        trusted.overlay.opaque
>>>        trusted.overlay.redirect
>>>        trusted.overlay.origin
>>>        trusted.overlay.impure
>>>        trusted.overlay.nlink
>>>        trusted.overlay.upper
>>>        trusted.overlay.metacopy
>>>        trusted.overlay.protattr
>>>        user.overlay.opaque
>>>        user.overlay.redirect
>>>        user.overlay.origin
>>>        user.overlay.impure
>>>        user.overlay.nlink
>>>        user.overlay.upper
>>>        user.overlay.metacopy
>>>        user.overlay.protattr
>>>        security.evm
>>>        security.ima
>>>        security.selinux
>>>        security.SMACK64
>>>        security.SMACK64IPIN
>>>        security.SMACK64IPOUT
>>>        security.SMACK64EXEC
>>>        security.SMACK64TRANSMUTE
>>>        security.SMACK64MMAP
>>>        security.apparmor
>>>        security.capability
>>>        system.posix_acl_access
>>>        system.posix_acl_default
>>>        user.mime_type
>>>
>>> Given the number of bits of the bloom filter (m) is 32, the optimal
>>> value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).
>>>
>>> The single hash function is implemented as:
>>>
>>>        xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)
>>>
>>> where index represents the index of corresponding predefined short name
>>
>> where `index`...
>>
>>
>>
>>> prefix, while name represents the name string after stripping the above
>>> predefined name prefix.
>>>
>>> The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
>>> used to give a better spread when mapping these 30 extended attributes
>>> into 32-bit bloom filter as:
>>>
>>>        bit  0: security.ima
>>>        bit  1:
>>>        bit  2: trusted.overlay.nlink
>>>        bit  3:
>>>        bit  4: user.overlay.nlink
>>>        bit  5: trusted.overlay.upper
>>>        bit  6: user.overlay.origin
>>>        bit  7: trusted.overlay.protattr
>>>        bit  8: security.apparmor
>>>        bit  9: user.overlay.protattr
>>>        bit 10: user.overlay.opaque
>>>        bit 11: security.selinux
>>>        bit 12: security.SMACK64TRANSMUTE
>>>        bit 13: security.SMACK64
>>>        bit 14: security.SMACK64MMAP
>>>        bit 15: user.overlay.impure
>>>        bit 16: security.SMACK64IPIN
>>>        bit 17: trusted.overlay.redirect
>>>        bit 18: trusted.overlay.origin
>>>        bit 19: security.SMACK64IPOUT
>>>        bit 20: trusted.overlay.opaque
>>>        bit 21: system.posix_acl_default
>>>        bit 22:
>>>        bit 23: user.mime_type
>>>        bit 24: trusted.overlay.impure
>>>        bit 25: security.SMACK64EXEC
>>>        bit 26: user.overlay.redirect
>>>        bit 27: user.overlay.upper
>>>        bit 28: security.evm
>>>        bit 29: security.capability
>>>        bit 30: system.posix_acl_access
>>>        bit 31: trusted.overlay.metacopy, user.overlay.metacopy
>>>
>>> The h_name_filter field is introduced to the on-disk per-inode xattr
>>> header to place the corresponding xattr name filter, where bit value 1
>>> indicates non-existence for compatibility.
>>>
>>> This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
>>> compatible feature bit.
>>>
>>> Suggested-by: Alexander Larsson <alexl@redhat.com>
>>> Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
>>> ---
>>>    fs/erofs/erofs_fs.h | 8 +++++++-
>>>    1 file changed, 7 insertions(+), 1 deletion(-)
>>>
>>> diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h
>>> index 2c7b16e340fe..b4b6235fd720 100644
>>> --- a/fs/erofs/erofs_fs.h
>>> +++ b/fs/erofs/erofs_fs.h
>>> @@ -13,6 +13,7 @@
>>>
>>>    #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
>>>    #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
>>> +#define EROFS_FEATURE_COMPAT_XATTR_FILTER    0x00000004
>>
>> I'd suggest that if we could leave one reserved byte in the
>> superblock for now (and checking if it's 0) since
>>     1) xattr filter feature is a compatible feature;
>>     2) I'm not sure if the implementation could be changed.
>>
>> so that later implementation changes won't bother compat bits
>> again.
> 
> I would very much like to generate these bloom filters in composefs
> right now, before the composefs v1 format is completely locked down,
> and this should be fully possible given that this is a backwards
> compat change. But this is only possible if it doesn't require a
> feature flag like this that makes old erofs versions not mount the
> image.

EROFS has two types of feature bits:

  1) compat flags, which doesn't block mounting on old kernels;
  2) incompat flags, which will block mounting on old kernels.

here bloom filter use a new compat flag, so old kernels will just
ignore this and mount.  compat flags just indicates that "an image
with a feature, and you could use it or not".

Here I just meant the bloom filter internals are fixed for now,
so that we might reserve a byte in the on-disk super block for
later potential changes (if any).  And don't need to bother another
new compat flag.

Thanks,
Gao Xiang

Re: [PATCH v2 2/2] erofs: boost negative xattr lookup with bloom filter

[Gao Xiang]

On 2023/7/5 15:44, Alexander Larsson wrote:
> On Wed, Jul 5, 2023 at 9:04 AM Jingbo Xu <jefflexu@linux.alibaba.com> wrote:

...

>> +       if (erofs_sb_has_xattr_filter(sbi)) {
> 
> As I said in my other mail. I would really like this to just always do
> the filter check. It should be safe as older fs:es have zero in place
> here, and doing this allows me to create composefs images with the
> bloom filters that also work with older kernels.

As my previous email, this flag is on-disk compatible which means old
unsupported kernels will just ignore this and go on mounting.

But this flag indicates a new on-disk feature in the image anyway,
users could know if an image uses the new feature rather than seek to
individual inodes.

Does it sound reasonable or some other consideration?

Thanks,
Gao Xiang

Re: [PATCH v2 2/2] erofs: boost negative xattr lookup with bloom filter

[Gao Xiang]

On 2023/7/5 15:44, Alexander Larsson wrote:
> On Wed, Jul 5, 2023 at 9:04 AM Jingbo Xu <jefflexu@linux.alibaba.com> wrote:

...

>> +       if (erofs_sb_has_xattr_filter(sbi)) {
> 
> As I said in my other mail. I would really like this to just always do
> the filter check. It should be safe as older fs:es have zero in place
> here, and doing this allows me to create composefs images with the
> bloom filters that also work with older kernels.

As my previous email, this flag is on-disk compatible which means old
unsupported kernels will just ignore this and go on mounting.

But this flag indicates a new on-disk feature in the image anyway,
users could know if an image uses the new feature rather than seek to
individual inodes.

Does it sound reasonable or some other consideration?

Thanks,
Gao Xiang

Re: [PATCH v2 1/2] erofs: update on-disk format for xattr name filter

[Alexander Larsson]

On Wed, Jul 5, 2023 at 9:51 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>
>
>
> On 2023/7/5 15:43, Alexander Larsson wrote:
> > On Wed, Jul 5, 2023 at 9:25 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
> >>
> >>
> >>
> >> On 2023/7/5 15:04, Jingbo Xu wrote:
> >>> The xattr name 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 extended attributes (n) is approximately 30.
> >>
> >> There are some commonly used extended attributes (n) and the total number
> >> of these is 31:
> >>
> >>>
> >>>        trusted.overlay.opaque
> >>>        trusted.overlay.redirect
> >>>        trusted.overlay.origin
> >>>        trusted.overlay.impure
> >>>        trusted.overlay.nlink
> >>>        trusted.overlay.upper
> >>>        trusted.overlay.metacopy
> >>>        trusted.overlay.protattr
> >>>        user.overlay.opaque
> >>>        user.overlay.redirect
> >>>        user.overlay.origin
> >>>        user.overlay.impure
> >>>        user.overlay.nlink
> >>>        user.overlay.upper
> >>>        user.overlay.metacopy
> >>>        user.overlay.protattr
> >>>        security.evm
> >>>        security.ima
> >>>        security.selinux
> >>>        security.SMACK64
> >>>        security.SMACK64IPIN
> >>>        security.SMACK64IPOUT
> >>>        security.SMACK64EXEC
> >>>        security.SMACK64TRANSMUTE
> >>>        security.SMACK64MMAP
> >>>        security.apparmor
> >>>        security.capability
> >>>        system.posix_acl_access
> >>>        system.posix_acl_default
> >>>        user.mime_type
> >>>
> >>> Given the number of bits of the bloom filter (m) is 32, the optimal
> >>> value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).
> >>>
> >>> The single hash function is implemented as:
> >>>
> >>>        xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)
> >>>
> >>> where index represents the index of corresponding predefined short name
> >>
> >> where `index`...
> >>
> >>
> >>
> >>> prefix, while name represents the name string after stripping the above
> >>> predefined name prefix.
> >>>
> >>> The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
> >>> used to give a better spread when mapping these 30 extended attributes
> >>> into 32-bit bloom filter as:
> >>>
> >>>        bit  0: security.ima
> >>>        bit  1:
> >>>        bit  2: trusted.overlay.nlink
> >>>        bit  3:
> >>>        bit  4: user.overlay.nlink
> >>>        bit  5: trusted.overlay.upper
> >>>        bit  6: user.overlay.origin
> >>>        bit  7: trusted.overlay.protattr
> >>>        bit  8: security.apparmor
> >>>        bit  9: user.overlay.protattr
> >>>        bit 10: user.overlay.opaque
> >>>        bit 11: security.selinux
> >>>        bit 12: security.SMACK64TRANSMUTE
> >>>        bit 13: security.SMACK64
> >>>        bit 14: security.SMACK64MMAP
> >>>        bit 15: user.overlay.impure
> >>>        bit 16: security.SMACK64IPIN
> >>>        bit 17: trusted.overlay.redirect
> >>>        bit 18: trusted.overlay.origin
> >>>        bit 19: security.SMACK64IPOUT
> >>>        bit 20: trusted.overlay.opaque
> >>>        bit 21: system.posix_acl_default
> >>>        bit 22:
> >>>        bit 23: user.mime_type
> >>>        bit 24: trusted.overlay.impure
> >>>        bit 25: security.SMACK64EXEC
> >>>        bit 26: user.overlay.redirect
> >>>        bit 27: user.overlay.upper
> >>>        bit 28: security.evm
> >>>        bit 29: security.capability
> >>>        bit 30: system.posix_acl_access
> >>>        bit 31: trusted.overlay.metacopy, user.overlay.metacopy
> >>>
> >>> The h_name_filter field is introduced to the on-disk per-inode xattr
> >>> header to place the corresponding xattr name filter, where bit value 1
> >>> indicates non-existence for compatibility.
> >>>
> >>> This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
> >>> compatible feature bit.
> >>>
> >>> Suggested-by: Alexander Larsson <alexl@redhat.com>
> >>> Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
> >>> ---
> >>>    fs/erofs/erofs_fs.h | 8 +++++++-
> >>>    1 file changed, 7 insertions(+), 1 deletion(-)
> >>>
> >>> diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h
> >>> index 2c7b16e340fe..b4b6235fd720 100644
> >>> --- a/fs/erofs/erofs_fs.h
> >>> +++ b/fs/erofs/erofs_fs.h
> >>> @@ -13,6 +13,7 @@
> >>>
> >>>    #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
> >>>    #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
> >>> +#define EROFS_FEATURE_COMPAT_XATTR_FILTER    0x00000004
> >>
> >> I'd suggest that if we could leave one reserved byte in the
> >> superblock for now (and checking if it's 0) since
> >>     1) xattr filter feature is a compatible feature;
> >>     2) I'm not sure if the implementation could be changed.
> >>
> >> so that later implementation changes won't bother compat bits
> >> again.
> >
> > I would very much like to generate these bloom filters in composefs
> > right now, before the composefs v1 format is completely locked down,
> > and this should be fully possible given that this is a backwards
> > compat change. But this is only possible if it doesn't require a
> > feature flag like this that makes old erofs versions not mount the
> > image.
>
> EROFS has two types of feature bits:
>
>   1) compat flags, which doesn't block mounting on old kernels;
>   2) incompat flags, which will block mounting on old kernels.
>
> here bloom filter use a new compat flag, so old kernels will just
> ignore this and mount.  compat flags just indicates that "an image
> with a feature, and you could use it or not".
>
> Here I just meant the bloom filter internals are fixed for now,
> so that we might reserve a byte in the on-disk super block for
> later potential changes (if any).  And don't need to bother another
> new compat flag.

Cool. Then we're all good!

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
 Alexander Larsson                                Red Hat, Inc
       alexl@redhat.com         alexander.larsson@gmail.com

Re: [PATCH v2 1/2] erofs: update on-disk format for xattr name filter

[Alexander Larsson]

On Wed, Jul 5, 2023 at 9:51 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>
>
>
> On 2023/7/5 15:43, Alexander Larsson wrote:
> > On Wed, Jul 5, 2023 at 9:25 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
> >>
> >>
> >>
> >> On 2023/7/5 15:04, Jingbo Xu wrote:
> >>> The xattr name 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 extended attributes (n) is approximately 30.
> >>
> >> There are some commonly used extended attributes (n) and the total number
> >> of these is 31:
> >>
> >>>
> >>>        trusted.overlay.opaque
> >>>        trusted.overlay.redirect
> >>>        trusted.overlay.origin
> >>>        trusted.overlay.impure
> >>>        trusted.overlay.nlink
> >>>        trusted.overlay.upper
> >>>        trusted.overlay.metacopy
> >>>        trusted.overlay.protattr
> >>>        user.overlay.opaque
> >>>        user.overlay.redirect
> >>>        user.overlay.origin
> >>>        user.overlay.impure
> >>>        user.overlay.nlink
> >>>        user.overlay.upper
> >>>        user.overlay.metacopy
> >>>        user.overlay.protattr
> >>>        security.evm
> >>>        security.ima
> >>>        security.selinux
> >>>        security.SMACK64
> >>>        security.SMACK64IPIN
> >>>        security.SMACK64IPOUT
> >>>        security.SMACK64EXEC
> >>>        security.SMACK64TRANSMUTE
> >>>        security.SMACK64MMAP
> >>>        security.apparmor
> >>>        security.capability
> >>>        system.posix_acl_access
> >>>        system.posix_acl_default
> >>>        user.mime_type
> >>>
> >>> Given the number of bits of the bloom filter (m) is 32, the optimal
> >>> value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).
> >>>
> >>> The single hash function is implemented as:
> >>>
> >>>        xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)
> >>>
> >>> where index represents the index of corresponding predefined short name
> >>
> >> where `index`...
> >>
> >>
> >>
> >>> prefix, while name represents the name string after stripping the above
> >>> predefined name prefix.
> >>>
> >>> The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
> >>> used to give a better spread when mapping these 30 extended attributes
> >>> into 32-bit bloom filter as:
> >>>
> >>>        bit  0: security.ima
> >>>        bit  1:
> >>>        bit  2: trusted.overlay.nlink
> >>>        bit  3:
> >>>        bit  4: user.overlay.nlink
> >>>        bit  5: trusted.overlay.upper
> >>>        bit  6: user.overlay.origin
> >>>        bit  7: trusted.overlay.protattr
> >>>        bit  8: security.apparmor
> >>>        bit  9: user.overlay.protattr
> >>>        bit 10: user.overlay.opaque
> >>>        bit 11: security.selinux
> >>>        bit 12: security.SMACK64TRANSMUTE
> >>>        bit 13: security.SMACK64
> >>>        bit 14: security.SMACK64MMAP
> >>>        bit 15: user.overlay.impure
> >>>        bit 16: security.SMACK64IPIN
> >>>        bit 17: trusted.overlay.redirect
> >>>        bit 18: trusted.overlay.origin
> >>>        bit 19: security.SMACK64IPOUT
> >>>        bit 20: trusted.overlay.opaque
> >>>        bit 21: system.posix_acl_default
> >>>        bit 22:
> >>>        bit 23: user.mime_type
> >>>        bit 24: trusted.overlay.impure
> >>>        bit 25: security.SMACK64EXEC
> >>>        bit 26: user.overlay.redirect
> >>>        bit 27: user.overlay.upper
> >>>        bit 28: security.evm
> >>>        bit 29: security.capability
> >>>        bit 30: system.posix_acl_access
> >>>        bit 31: trusted.overlay.metacopy, user.overlay.metacopy
> >>>
> >>> The h_name_filter field is introduced to the on-disk per-inode xattr
> >>> header to place the corresponding xattr name filter, where bit value 1
> >>> indicates non-existence for compatibility.
> >>>
> >>> This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
> >>> compatible feature bit.
> >>>
> >>> Suggested-by: Alexander Larsson <alexl@redhat.com>
> >>> Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
> >>> ---
> >>>    fs/erofs/erofs_fs.h | 8 +++++++-
> >>>    1 file changed, 7 insertions(+), 1 deletion(-)
> >>>
> >>> diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h
> >>> index 2c7b16e340fe..b4b6235fd720 100644
> >>> --- a/fs/erofs/erofs_fs.h
> >>> +++ b/fs/erofs/erofs_fs.h
> >>> @@ -13,6 +13,7 @@
> >>>
> >>>    #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
> >>>    #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
> >>> +#define EROFS_FEATURE_COMPAT_XATTR_FILTER    0x00000004
> >>
> >> I'd suggest that if we could leave one reserved byte in the
> >> superblock for now (and checking if it's 0) since
> >>     1) xattr filter feature is a compatible feature;
> >>     2) I'm not sure if the implementation could be changed.
> >>
> >> so that later implementation changes won't bother compat bits
> >> again.
> >
> > I would very much like to generate these bloom filters in composefs
> > right now, before the composefs v1 format is completely locked down,
> > and this should be fully possible given that this is a backwards
> > compat change. But this is only possible if it doesn't require a
> > feature flag like this that makes old erofs versions not mount the
> > image.
>
> EROFS has two types of feature bits:
>
>   1) compat flags, which doesn't block mounting on old kernels;
>   2) incompat flags, which will block mounting on old kernels.
>
> here bloom filter use a new compat flag, so old kernels will just
> ignore this and mount.  compat flags just indicates that "an image
> with a feature, and you could use it or not".
>
> Here I just meant the bloom filter internals are fixed for now,
> so that we might reserve a byte in the on-disk super block for
> later potential changes (if any).  And don't need to bother another
> new compat flag.

Cool. Then we're all good!

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
 Alexander Larsson                                Red Hat, Inc
       alexl@redhat.com         alexander.larsson@gmail.com

Re: [PATCH v2 1/2] erofs: update on-disk format for xattr name filter

[Gao Xiang]

On 2023/7/5 16:12, Alexander Larsson wrote:
> On Wed, Jul 5, 2023 at 9:51 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>>
>>
>>
>> On 2023/7/5 15:43, Alexander Larsson wrote:
>>> On Wed, Jul 5, 2023 at 9:25 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>>>>
>>>>
>>>>
>>>> On 2023/7/5 15:04, Jingbo Xu wrote:
>>>>> The xattr name 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 extended attributes (n) is approximately 30.
>>>>
>>>> There are some commonly used extended attributes (n) and the total number
>>>> of these is 31:
>>>>
>>>>>
>>>>>         trusted.overlay.opaque
>>>>>         trusted.overlay.redirect
>>>>>         trusted.overlay.origin
>>>>>         trusted.overlay.impure
>>>>>         trusted.overlay.nlink
>>>>>         trusted.overlay.upper
>>>>>         trusted.overlay.metacopy
>>>>>         trusted.overlay.protattr
>>>>>         user.overlay.opaque
>>>>>         user.overlay.redirect
>>>>>         user.overlay.origin
>>>>>         user.overlay.impure
>>>>>         user.overlay.nlink
>>>>>         user.overlay.upper
>>>>>         user.overlay.metacopy
>>>>>         user.overlay.protattr
>>>>>         security.evm
>>>>>         security.ima
>>>>>         security.selinux
>>>>>         security.SMACK64
>>>>>         security.SMACK64IPIN
>>>>>         security.SMACK64IPOUT
>>>>>         security.SMACK64EXEC
>>>>>         security.SMACK64TRANSMUTE
>>>>>         security.SMACK64MMAP
>>>>>         security.apparmor
>>>>>         security.capability
>>>>>         system.posix_acl_access
>>>>>         system.posix_acl_default
>>>>>         user.mime_type
>>>>>
>>>>> Given the number of bits of the bloom filter (m) is 32, the optimal
>>>>> value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).
>>>>>
>>>>> The single hash function is implemented as:
>>>>>
>>>>>         xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)
>>>>>
>>>>> where index represents the index of corresponding predefined short name
>>>>
>>>> where `index`...
>>>>
>>>>
>>>>
>>>>> prefix, while name represents the name string after stripping the above
>>>>> predefined name prefix.
>>>>>
>>>>> The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
>>>>> used to give a better spread when mapping these 30 extended attributes
>>>>> into 32-bit bloom filter as:
>>>>>
>>>>>         bit  0: security.ima
>>>>>         bit  1:
>>>>>         bit  2: trusted.overlay.nlink
>>>>>         bit  3:
>>>>>         bit  4: user.overlay.nlink
>>>>>         bit  5: trusted.overlay.upper
>>>>>         bit  6: user.overlay.origin
>>>>>         bit  7: trusted.overlay.protattr
>>>>>         bit  8: security.apparmor
>>>>>         bit  9: user.overlay.protattr
>>>>>         bit 10: user.overlay.opaque
>>>>>         bit 11: security.selinux
>>>>>         bit 12: security.SMACK64TRANSMUTE
>>>>>         bit 13: security.SMACK64
>>>>>         bit 14: security.SMACK64MMAP
>>>>>         bit 15: user.overlay.impure
>>>>>         bit 16: security.SMACK64IPIN
>>>>>         bit 17: trusted.overlay.redirect
>>>>>         bit 18: trusted.overlay.origin
>>>>>         bit 19: security.SMACK64IPOUT
>>>>>         bit 20: trusted.overlay.opaque
>>>>>         bit 21: system.posix_acl_default
>>>>>         bit 22:
>>>>>         bit 23: user.mime_type
>>>>>         bit 24: trusted.overlay.impure
>>>>>         bit 25: security.SMACK64EXEC
>>>>>         bit 26: user.overlay.redirect
>>>>>         bit 27: user.overlay.upper
>>>>>         bit 28: security.evm
>>>>>         bit 29: security.capability
>>>>>         bit 30: system.posix_acl_access
>>>>>         bit 31: trusted.overlay.metacopy, user.overlay.metacopy
>>>>>
>>>>> The h_name_filter field is introduced to the on-disk per-inode xattr
>>>>> header to place the corresponding xattr name filter, where bit value 1
>>>>> indicates non-existence for compatibility.
>>>>>
>>>>> This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
>>>>> compatible feature bit.
>>>>>
>>>>> Suggested-by: Alexander Larsson <alexl@redhat.com>
>>>>> Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
>>>>> ---
>>>>>     fs/erofs/erofs_fs.h | 8 +++++++-
>>>>>     1 file changed, 7 insertions(+), 1 deletion(-)
>>>>>
>>>>> diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h
>>>>> index 2c7b16e340fe..b4b6235fd720 100644
>>>>> --- a/fs/erofs/erofs_fs.h
>>>>> +++ b/fs/erofs/erofs_fs.h
>>>>> @@ -13,6 +13,7 @@
>>>>>
>>>>>     #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
>>>>>     #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
>>>>> +#define EROFS_FEATURE_COMPAT_XATTR_FILTER    0x00000004
>>>>
>>>> I'd suggest that if we could leave one reserved byte in the
>>>> superblock for now (and checking if it's 0) since
>>>>      1) xattr filter feature is a compatible feature;
>>>>      2) I'm not sure if the implementation could be changed.
>>>>
>>>> so that later implementation changes won't bother compat bits
>>>> again.
>>>
>>> I would very much like to generate these bloom filters in composefs
>>> right now, before the composefs v1 format is completely locked down,
>>> and this should be fully possible given that this is a backwards
>>> compat change. But this is only possible if it doesn't require a
>>> feature flag like this that makes old erofs versions not mount the
>>> image.
>>
>> EROFS has two types of feature bits:
>>
>>    1) compat flags, which doesn't block mounting on old kernels;
>>    2) incompat flags, which will block mounting on old kernels.
>>
>> here bloom filter use a new compat flag, so old kernels will just
>> ignore this and mount.  compat flags just indicates that "an image
>> with a feature, and you could use it or not".
>>
>> Here I just meant the bloom filter internals are fixed for now,
>> so that we might reserve a byte in the on-disk super block for
>> later potential changes (if any).  And don't need to bother another
>> new compat flag.
> 
> Cool. Then we're all good!

:)

> 

Re: [PATCH v2 1/2] erofs: update on-disk format for xattr name filter

[Gao Xiang]

On 2023/7/5 16:12, Alexander Larsson wrote:
> On Wed, Jul 5, 2023 at 9:51 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>>
>>
>>
>> On 2023/7/5 15:43, Alexander Larsson wrote:
>>> On Wed, Jul 5, 2023 at 9:25 AM Gao Xiang <hsiangkao@linux.alibaba.com> wrote:
>>>>
>>>>
>>>>
>>>> On 2023/7/5 15:04, Jingbo Xu wrote:
>>>>> The xattr name 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 extended attributes (n) is approximately 30.
>>>>
>>>> There are some commonly used extended attributes (n) and the total number
>>>> of these is 31:
>>>>
>>>>>
>>>>>         trusted.overlay.opaque
>>>>>         trusted.overlay.redirect
>>>>>         trusted.overlay.origin
>>>>>         trusted.overlay.impure
>>>>>         trusted.overlay.nlink
>>>>>         trusted.overlay.upper
>>>>>         trusted.overlay.metacopy
>>>>>         trusted.overlay.protattr
>>>>>         user.overlay.opaque
>>>>>         user.overlay.redirect
>>>>>         user.overlay.origin
>>>>>         user.overlay.impure
>>>>>         user.overlay.nlink
>>>>>         user.overlay.upper
>>>>>         user.overlay.metacopy
>>>>>         user.overlay.protattr
>>>>>         security.evm
>>>>>         security.ima
>>>>>         security.selinux
>>>>>         security.SMACK64
>>>>>         security.SMACK64IPIN
>>>>>         security.SMACK64IPOUT
>>>>>         security.SMACK64EXEC
>>>>>         security.SMACK64TRANSMUTE
>>>>>         security.SMACK64MMAP
>>>>>         security.apparmor
>>>>>         security.capability
>>>>>         system.posix_acl_access
>>>>>         system.posix_acl_default
>>>>>         user.mime_type
>>>>>
>>>>> Given the number of bits of the bloom filter (m) is 32, the optimal
>>>>> value for the number of the hash functions (k) is 1 (ln2 * m/n = 0.74).
>>>>>
>>>>> The single hash function is implemented as:
>>>>>
>>>>>         xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index)
>>>>>
>>>>> where index represents the index of corresponding predefined short name
>>>>
>>>> where `index`...
>>>>
>>>>
>>>>
>>>>> prefix, while name represents the name string after stripping the above
>>>>> predefined name prefix.
>>>>>
>>>>> The constant magic number EROFS_XATTR_FILTER_SEED, i.e. 0x25BBE08F, is
>>>>> used to give a better spread when mapping these 30 extended attributes
>>>>> into 32-bit bloom filter as:
>>>>>
>>>>>         bit  0: security.ima
>>>>>         bit  1:
>>>>>         bit  2: trusted.overlay.nlink
>>>>>         bit  3:
>>>>>         bit  4: user.overlay.nlink
>>>>>         bit  5: trusted.overlay.upper
>>>>>         bit  6: user.overlay.origin
>>>>>         bit  7: trusted.overlay.protattr
>>>>>         bit  8: security.apparmor
>>>>>         bit  9: user.overlay.protattr
>>>>>         bit 10: user.overlay.opaque
>>>>>         bit 11: security.selinux
>>>>>         bit 12: security.SMACK64TRANSMUTE
>>>>>         bit 13: security.SMACK64
>>>>>         bit 14: security.SMACK64MMAP
>>>>>         bit 15: user.overlay.impure
>>>>>         bit 16: security.SMACK64IPIN
>>>>>         bit 17: trusted.overlay.redirect
>>>>>         bit 18: trusted.overlay.origin
>>>>>         bit 19: security.SMACK64IPOUT
>>>>>         bit 20: trusted.overlay.opaque
>>>>>         bit 21: system.posix_acl_default
>>>>>         bit 22:
>>>>>         bit 23: user.mime_type
>>>>>         bit 24: trusted.overlay.impure
>>>>>         bit 25: security.SMACK64EXEC
>>>>>         bit 26: user.overlay.redirect
>>>>>         bit 27: user.overlay.upper
>>>>>         bit 28: security.evm
>>>>>         bit 29: security.capability
>>>>>         bit 30: system.posix_acl_access
>>>>>         bit 31: trusted.overlay.metacopy, user.overlay.metacopy
>>>>>
>>>>> The h_name_filter field is introduced to the on-disk per-inode xattr
>>>>> header to place the corresponding xattr name filter, where bit value 1
>>>>> indicates non-existence for compatibility.
>>>>>
>>>>> This feature is indicated by EROFS_FEATURE_COMPAT_XATTR_FILTER
>>>>> compatible feature bit.
>>>>>
>>>>> Suggested-by: Alexander Larsson <alexl@redhat.com>
>>>>> Signed-off-by: Jingbo Xu <jefflexu@linux.alibaba.com>
>>>>> ---
>>>>>     fs/erofs/erofs_fs.h | 8 +++++++-
>>>>>     1 file changed, 7 insertions(+), 1 deletion(-)
>>>>>
>>>>> diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h
>>>>> index 2c7b16e340fe..b4b6235fd720 100644
>>>>> --- a/fs/erofs/erofs_fs.h
>>>>> +++ b/fs/erofs/erofs_fs.h
>>>>> @@ -13,6 +13,7 @@
>>>>>
>>>>>     #define EROFS_FEATURE_COMPAT_SB_CHKSUM          0x00000001
>>>>>     #define EROFS_FEATURE_COMPAT_MTIME              0x00000002
>>>>> +#define EROFS_FEATURE_COMPAT_XATTR_FILTER    0x00000004
>>>>
>>>> I'd suggest that if we could leave one reserved byte in the
>>>> superblock for now (and checking if it's 0) since
>>>>      1) xattr filter feature is a compatible feature;
>>>>      2) I'm not sure if the implementation could be changed.
>>>>
>>>> so that later implementation changes won't bother compat bits
>>>> again.
>>>
>>> I would very much like to generate these bloom filters in composefs
>>> right now, before the composefs v1 format is completely locked down,
>>> and this should be fully possible given that this is a backwards
>>> compat change. But this is only possible if it doesn't require a
>>> feature flag like this that makes old erofs versions not mount the
>>> image.
>>
>> EROFS has two types of feature bits:
>>
>>    1) compat flags, which doesn't block mounting on old kernels;
>>    2) incompat flags, which will block mounting on old kernels.
>>
>> here bloom filter use a new compat flag, so old kernels will just
>> ignore this and mount.  compat flags just indicates that "an image
>> with a feature, and you could use it or not".
>>
>> Here I just meant the bloom filter internals are fixed for now,
>> so that we might reserve a byte in the on-disk super block for
>> later potential changes (if any).  And don't need to bother another
>> new compat flag.
> 
> Cool. Then we're all good!

:)

>