Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) client-ip=2620:137:e000::1:20;
MIME-Version: 1.0
References: <20230621083209.116024-1-jefflexu@linux.alibaba.com>
 <CAL7ro1EmCcienVMY7Pi_mEFbUiLZq24EGOyFovexmpJMGbfjcA@mail.gmail.com> <3730215c-d59d-8b8e-fe36-7754f7782d15@linux.alibaba.com>
In-Reply-To: <3730215c-d59d-8b8e-fe36-7754f7782d15@linux.alibaba.com>
From:   Alexander Larsson <alexl@redhat.com>
Date:   Thu, 22 Jun 2023 07:56:43 +0000
Message-ID: <CAL7ro1HhYUDrOX7A-13p7rLBZSWHTQWGOdOzVcYkddkU_LArUw@mail.gmail.com>
Subject: Re: [RFC 0/2] erofs: introduce bloom filter for xattr
To:     Jingbo Xu <jefflexu@linux.alibaba.com>
Cc:     hsiangkao@linux.alibaba.com, chao@kernel.org, huyue2@coolpad.com,
        linux-erofs@lists.ozlabs.org, linux-kernel@vger.kernel.org
Content-Type: text/plain; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable
Precedence: bulk

On Thu, Jun 22, 2023 at 8:37=E2=80=AFAM Jingbo Xu <jefflexu@linux.alibaba.c=
om> wrote:
>
>
>
> On 6/21/23 7:50 PM, Alexander Larsson wrote:
> > On Wed, Jun 21, 2023 at 10:32=E2=80=AFAM Jingbo Xu <jefflexu@linux.alib=
aba.com> wrote:
> >>
> >> Background
> >> =3D=3D=3D=3D=3D=3D=3D=3D=3D=3D
> >> 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
> >> =3D=3D=3D=3D=3D=3D=3D=3D
> >> 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 t=
he
> >> 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 previous=
ly
> >> 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 va=
lue
> >> for the number of the hash functions (k) is 2 (ln2 * m/n =3D 2.7).
> >
> > This is indeed the optimal value in a traditional use of bloom
> > filters. However, I think it is based on a much larger set of values.
> > For this usecase it may be better to choose a different value.
> >
> > I did some research a while ago on this, and I thought about the
> > counts too. Having more than one hash function is useful because it
> > allows you to avoid problems if two values happen to hash to the same
> > bucket, but this happens at the cost of there being less "unique
> > buckets".  I spent some time looking for common xattr values
> > (including some from userspace) and ended up with a list of about 30.
>
> Yeah, if the number of common used xattr (n) is 30, then the optimal
> value for the number of the hash functions (k) is 1 (ln2 * m/n =3D 0.74).
> The optimal value in theory also matches our intuition.
>
>
> > If we can choose a single hash function that maps all (or most) of
> > these to a unique bucket (mod 32),
>
> Excellent research!  Would you mind sharing the list of these
> approximately 30 commonly used xattrs, so that I could check if they are
> mapped to unique bucket with the single hash function we proposed?

This is the list I came up with:

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

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