From nobody Sat Feb 7 16:05:36 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id BEE6DC001DC for ; Fri, 14 Jul 2023 03:10:55 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234714AbjGNDKy (ORCPT ); Thu, 13 Jul 2023 23:10:54 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37184 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234696AbjGNDKm (ORCPT ); Thu, 13 Jul 2023 23:10:42 -0400 Received: from out30-130.freemail.mail.aliyun.com (out30-130.freemail.mail.aliyun.com [115.124.30.130]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id CA47030D1 for ; Thu, 13 Jul 2023 20:10:39 -0700 (PDT) X-Alimail-AntiSpam: AC=PASS;BC=-1|-1;BR=01201311R891e4;CH=green;DM=||false|;DS=||;FP=0|-1|-1|-1|0|-1|-1|-1;HT=ay29a033018046050;MF=jefflexu@linux.alibaba.com;NM=1;PH=DS;RN=6;SR=0;TI=SMTPD_---0VnK8VKq_1689304235; Received: from localhost(mailfrom:jefflexu@linux.alibaba.com fp:SMTPD_---0VnK8VKq_1689304235) by smtp.aliyun-inc.com; Fri, 14 Jul 2023 11:10:36 +0800 From: Jingbo Xu To: hsiangkao@linux.alibaba.com, chao@kernel.org, huyue2@coolpad.com, linux-erofs@lists.ozlabs.org Cc: linux-kernel@vger.kernel.org, alexl@redhat.com Subject: [PATCH v4 1/2] erofs: update on-disk format for xattr name filter Date: Fri, 14 Jul 2023 11:10:33 +0800 Message-Id: <20230714031034.53210-2-jefflexu@linux.alibaba.com> X-Mailer: git-send-email 2.19.1.6.gb485710b In-Reply-To: <20230714031034.53210-1-jefflexu@linux.alibaba.com> References: <20230714031034.53210-1-jefflexu@linux.alibaba.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" 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. There are some commonly used extended attributes (n) and the total number of these 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 =3D 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 h_name_filter 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. Reserve one byte in on-disk superblock as the on-disk format for xattr name filter may change in the future. With this flag we don't need bothering these compatible bits again at that time. Suggested-by: Alexander Larsson Signed-off-by: Jingbo Xu Reviewed-by: Gao Xiang --- fs/erofs/erofs_fs.h | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-) diff --git a/fs/erofs/erofs_fs.h b/fs/erofs/erofs_fs.h index 2c7b16e340fe..e2944f4a6ff9 100644 --- a/fs/erofs/erofs_fs.h +++ b/fs/erofs/erofs_fs.h @@ -13,6 +13,7 @@ =20 #define EROFS_FEATURE_COMPAT_SB_CHKSUM 0x00000001 #define EROFS_FEATURE_COMPAT_MTIME 0x00000002 +#define EROFS_FEATURE_COMPAT_XATTR_FILTER 0x00000004 =20 /* * Any bits that aren't in EROFS_ALL_FEATURE_INCOMPAT should @@ -81,7 +82,8 @@ struct erofs_super_block { __u8 xattr_prefix_count; /* # of long xattr name prefixes */ __le32 xattr_prefix_start; /* start of long xattr prefixes */ __le64 packed_nid; /* nid of the special packed inode */ - __u8 reserved2[24]; + __u8 xattr_filter_reserved; /* reserved for xattr name filter */ + __u8 reserved2[23]; }; =20 /* @@ -200,7 +202,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 +223,10 @@ struct erofs_xattr_ibody_header { #define EROFS_XATTR_LONG_PREFIX 0x80 #define EROFS_XATTR_LONG_PREFIX_MASK 0x7f =20 +#define EROFS_XATTR_FILTER_BITS 32 +#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 */ --=20 2.19.1.6.gb485710b From nobody Sat Feb 7 16:05:36 2026 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org Received: from vger.kernel.org (vger.kernel.org [23.128.96.18]) by smtp.lore.kernel.org (Postfix) with ESMTP id B587AC001DC for ; Fri, 14 Jul 2023 03:10:59 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S234678AbjGNDK5 (ORCPT ); Thu, 13 Jul 2023 23:10:57 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:37094 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S234713AbjGNDKp (ORCPT ); Thu, 13 Jul 2023 23:10:45 -0400 Received: from out30-112.freemail.mail.aliyun.com (out30-112.freemail.mail.aliyun.com [115.124.30.112]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 4E3B530E2 for ; Thu, 13 Jul 2023 20:10:40 -0700 (PDT) X-Alimail-AntiSpam: AC=PASS;BC=-1|-1;BR=01201311R141e4;CH=green;DM=||false|;DS=||;FP=0|-1|-1|-1|0|-1|-1|-1;HT=ay29a033018045192;MF=jefflexu@linux.alibaba.com;NM=1;PH=DS;RN=6;SR=0;TI=SMTPD_---0VnJxOQD_1689304236; Received: from localhost(mailfrom:jefflexu@linux.alibaba.com fp:SMTPD_---0VnJxOQD_1689304236) by smtp.aliyun-inc.com; Fri, 14 Jul 2023 11:10:37 +0800 From: Jingbo Xu To: hsiangkao@linux.alibaba.com, chao@kernel.org, huyue2@coolpad.com, linux-erofs@lists.ozlabs.org Cc: linux-kernel@vger.kernel.org, alexl@redhat.com Subject: [PATCH v4 2/2] erofs: boost negative xattr lookup with bloom filter Date: Fri, 14 Jul 2023 11:10:34 +0800 Message-Id: <20230714031034.53210-3-jefflexu@linux.alibaba.com> X-Mailer: git-send-email 2.19.1.6.gb485710b In-Reply-To: <20230714031034.53210-1-jefflexu@linux.alibaba.com> References: <20230714031034.53210-1-jefflexu@linux.alibaba.com> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Content-Type: text/plain; charset="utf-8" Optimise the negative xattr lookup with bloom filter. The bit value for the bloom filter map has a reverse semantics for compatibility. That is, the bit value of 0 indicates existence, while the bit value of 1 indicates the absence of corresponding xattr. This feature is enabled only when xattr_filter_reserved is non-zero. The on-disk format for the filter map may change in the future, in which case the reserved flag will be set non-zero and we don't need bothering the compatible bits again at that time. For now disable the optimization if this reserved flag is non-zero. Signed-off-by: Jingbo Xu --- fs/erofs/Kconfig | 1 + fs/erofs/internal.h | 3 +++ fs/erofs/super.c | 1 + fs/erofs/xattr.c | 13 +++++++++++++ 4 files changed, 18 insertions(+) diff --git a/fs/erofs/Kconfig b/fs/erofs/Kconfig index f259d92c9720..f49669def828 100644 --- a/fs/erofs/Kconfig +++ b/fs/erofs/Kconfig @@ -38,6 +38,7 @@ config EROFS_FS_DEBUG config EROFS_FS_XATTR bool "EROFS extended attributes" depends on EROFS_FS + select XXHASH default y help Extended attributes are name:value pairs associated with inodes by diff --git a/fs/erofs/internal.h b/fs/erofs/internal.h index 36e32fa542f0..ebcad25e3750 100644 --- a/fs/erofs/internal.h +++ b/fs/erofs/internal.h @@ -151,6 +151,7 @@ struct erofs_sb_info { u32 xattr_prefix_start; u8 xattr_prefix_count; struct erofs_xattr_prefix_item *xattr_prefixes; + unsigned int xattr_filter_reserved; #endif u16 device_id_mask; /* valid bits of device id to be used */ =20 @@ -251,6 +252,7 @@ EROFS_FEATURE_FUNCS(fragments, incompat, INCOMPAT_FRAGM= ENTS) 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) =20 /* 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; =20 + unsigned long xattr_name_filter; unsigned int xattr_shared_count; unsigned int *xattr_shared_xattrs; =20 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 =3D le32_to_cpu(dsb->xattr_blkaddr); sbi->xattr_prefix_start =3D le32_to_cpu(dsb->xattr_prefix_start); sbi->xattr_prefix_count =3D dsb->xattr_prefix_count; + sbi->xattr_filter_reserved =3D dsb->xattr_filter_reserved; #endif sbi->islotbits =3D ilog2(sizeof(struct erofs_inode_compact)); sbi->root_nid =3D le16_to_cpu(dsb->root_nid); diff --git a/fs/erofs/xattr.c b/fs/erofs/xattr.c index 40178b6e0688..eb1d1974d4b3 100644 --- a/fs/erofs/xattr.c +++ b/fs/erofs/xattr.c @@ -5,6 +5,7 @@ * Copyright (C) 2021-2022, Alibaba Cloud */ #include +#include #include "xattr.h" =20 struct erofs_xattr_iter { @@ -87,6 +88,7 @@ static int erofs_init_inode_xattrs(struct inode *inode) } =20 ih =3D it.kaddr + erofs_blkoff(sb, it.pos); + vi->xattr_name_filter =3D le32_to_cpu(ih->h_name_filter); vi->xattr_shared_count =3D ih->h_shared_count; vi->xattr_shared_xattrs =3D kmalloc_array(vi->xattr_shared_count, sizeof(uint), GFP_KERNEL); @@ -392,7 +394,10 @@ int erofs_getxattr(struct inode *inode, int index, con= st char *name, void *buffer, size_t buffer_size) { int ret; + uint32_t bit; struct erofs_xattr_iter it; + struct erofs_inode *vi =3D EROFS_I(inode); + struct erofs_sb_info *sbi =3D EROFS_SB(inode->i_sb); =20 if (!name) return -EINVAL; @@ -401,6 +406,14 @@ int erofs_getxattr(struct inode *inode, int index, con= st char *name, if (ret) return ret; =20 + /* reserved flag is non-zero if there's any change of on-disk format */ + if (erofs_sb_has_xattr_filter(sbi) && !sbi->xattr_filter_reserved) { + bit =3D xxh32(name, strlen(name), EROFS_XATTR_FILTER_SEED + index); + bit &=3D EROFS_XATTR_FILTER_BITS - 1; + if (test_bit(bit, &vi->xattr_name_filter)) + return -ENOATTR; + } + it.index =3D index; it.name =3D (struct qstr)QSTR_INIT(name, strlen(name)); if (it.name.len > EROFS_NAME_LEN) --=20 2.19.1.6.gb485710b