[RFC 0/2] erofs: introduce bloom filter for xattr

Tue Jul 4 18:05:53 AEST 2023

On Tue, Jul 4, 2023 at 7:56 AM Jingbo Xu <jefflexu at linux.alibaba.com> wrote:
>
>
>
> On 7/3/23 3:25 PM, Alexander Larsson wrote:
>
> >
> > Can't you just add a magic constant to the seed? Then we can come up
> > with one that gives a good spread and hardcode that.
> >
>
> I tried Alex's proposal of making a constant magic as part of the seed like:
>
> ```
> xxh32(name, strlen(name), SEED_MAGIC + index)
> ```
>
> >> where `index` represents the index of corresponding predefined name
> >> prefix (e.g. EROFS_XATTR_INDEX_USER), while `name` represents the name
> >> after stripping the above predefined name prefix (e.g.
> >> "overlay.metacopy" for "user.overlay.metacopy")
>
>
> I tried SEED_MAGIC in range [0, UINT32_MAX], trying to find a constant
> magic giving a best spread.
>
> There are totally 30 commonly used xattrs and 32 bits could be mapped
> into.  I failed to find the most perfect constant magic which maps these
> 30 xattrs to exactly 30 bits with no conflict.
>
> Later I can only select a magic from those that 1) maps 30 xattrs into
> 29 bits (with one conflict) and 2) at least xattrs like selinux, ima,
> evm, apparmor are unconflicted to each other.  Following are all
> candidates and the conflicted xattrs:
>
> ```
> seed: 745a51e
> bit 29: user.overlay.opaque, security.selinux,
>
> seed: fb08ad9
> bit 10: user.overlay.impure, system.posix_acl_access,
>
> seed: 11aa6c32
> bit 19: user.overlay.redirect, security.SMACK64MMAP,
>
> seed: 1438d503
> bit 10: trusted.overlay.protattr, security.ima,
>
> seed: 14ccea75
> bit 30: user.overlay.upper, security.ima,
>
> seed: 1d6a0d15
> bit 31: trusted.overlay.upper, user.overlay.metacopy,
>
> seed: 25bbe08f
> bit 31: trusted.overlay.metacopy, user.overlay.metacopy,
>
> seed: 2649da2a
> bit  6: user.overlay.nlink, security.SMACK64TRANSMUTE,
>
> seed: 2b9180b2
> bit 29: user.overlay.impure, security.evm,
>
> seed: 2c5d7862
> bit 16: user.overlay.upper, system.posix_acl_default,
>
> seed: 322040a6
> bit 17: trusted.overlay.impure, user.overlay.metacopy,
>
> seed: 328bcb8c
> bit 30: user.overlay.opaque, security.evm,
>
> seed: 35afc469
> bit  3: trusted.overlay.opaque, user.overlay.origin,
>
> seed: 435bed25
> bit  4: trusted.overlay.upper, security.SMACK64MMAP,
>
> seed: 43a853af
> bit  3: trusted.overlay.protattr, security.selinux,
>
> seed: 4930f511
> bit 22: trusted.overlay.origin, security.SMACK64,
>
> seed: 4acdce1d
> bit 21: user.overlay.opaque, security.selinux,
>
> seed: 4fc5f2b0
> bit 24: user.overlay.redirect, system.posix_acl_default,
>
> seed: 50632396
> bit  6: security.SMACK64, system.posix_acl_access,
>
> seed: 535f6351
> bit  3: system.posix_acl_access, user.mime_type,
>
> seed: 56f4306e
> bit  9: user.overlay.redirect, security.SMACK64MMAP,
>
> seed: 637e2bd9
> bit 22: trusted.overlay.upper, security.evm,
>
> seed: 6ab57b38
> bit  9: trusted.overlay.upper, user.overlay.metacopy,
>
> seed: 7113bd57
> bit 19: trusted.overlay.redirect, security.SMACK64,
>
> seed: 753e3f24
> bit  6: user.overlay.redirect, security.SMACK64EXEC,
>
> seed: 81883030
> bit  0: trusted.overlay.upper, security.SMACK64IPOUT,
>
> seed: 835f9f14
> bit 27: security.SMACK64EXEC, system.posix_acl_access,
>
> seed: 938fbb78
> bit 28: user.overlay.upper, security.apparmor,
>
> seed: 953bb3e9
> bit 30: user.overlay.protattr, system.posix_acl_access,
>
> seed: 962ccd7f
> bit 29: trusted.overlay.nlink, security.SMACK64IPOUT,
>
> seed: 9fff798e
> bit  3: user.overlay.nlink, user.mime_type,
>
> seed: a2e324eb
> bit 28: trusted.overlay.nlink, user.overlay.impure,
>
> seed: a6e00cef
> bit 26: user.overlay.opaque, security.SMACK64TRANSMUTE,
>
> seed: ae26aaa9
> bit  0: trusted.overlay.metacopy, user.overlay.impure,
>
> seed: b2172573
> bit 14: trusted.overlay.upper, security.ima,
>
> seed: b5917739
> bit  8: trusted.overlay.protattr, user.overlay.impure,
>
> seed: c01a4919
> bit 22: trusted.overlay.nlink, user.overlay.upper,
>
> seed: c1fa0c0a
> bit 19: security.SMACK64TRANSMUTE, user.mime_type,
>
> seed: cbd314d7
> bit  6: trusted.overlay.upper, security.SMACK64IPOUT,
>
> seed: cc6dd8ee
> bit  2: trusted.overlay.nlink, user.overlay.upper,
>
> seed: cc922efd
> bit  3: trusted.overlay.opaque, user.overlay.opaque,
>
> seed: cd478c17
> bit  6: trusted.overlay.metacopy, user.overlay.metacopy,
>
> seed: d35be1c8
> bit  9: trusted.overlay.protattr, security.SMACK64MMAP,
>
> seed: d3914458
> bit  1: trusted.overlay.redirect, security.SMACK64IPIN,
>
> seed: f3251337
> bit  7: user.overlay.opaque, security.SMACK64IPOUT,
>
> seed: f37d8900
> bit  9: trusted.overlay.impure, user.overlay.protattr,
>
> seed: fafd6c93
> bit  0: security.SMACK64, user.mime_type,
>
> seed: fcd35cbb
> bit  3: trusted.overlay.upper, user.overlay.redirect,
>
> seed: fe2e058a
> bit 14: user.overlay.impure, user.mime_type,
> ```
>
>
> Among all these candidates, I would prefer the following three
> candidates as for each inode the same xattr of overlayfs family xattrs,
> e.g. "overlay.metacopy", can not be prefixed with "trusted." and "user."
> at the same time.

Well, they *can* be the same at the same time, it just doesn't make
much sense, so it seems very unlikely. I agree that these make sense,
if the kernel is looking for user.overlay.metacopy, it would be in an
userxattr mounted overlayfs layer, and it would be very unlikely that
it had a trusted metacopy xattr, so there won't be any false negatives
causing us to do a full look up.

> ```
> seed: 25bbe08f
> bit 31: trusted.overlay.metacopy, user.overlay.metacopy,
>
> seed: cc922efd
> bit  3: trusted.overlay.opaque, user.overlay.opaque,
>
> seed: cd478c17
> bit  6: trusted.overlay.metacopy, user.overlay.metacopy,
> ```
>
>
> Any other idea?

Any of these three is good to me. I don't have any ideas directly
related to this. However,  semi-related, it would be really cool if
fuse supported the same approach for xattr lookup. I.e. if lookup
could add a bloom filter value as part of the inode data, then we
could avoid a kernel<->fusefs-d transition for negative xattrs
lookups.

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