From patchwork Wed Jun 21 08:32:08 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jingbo Xu X-Patchwork-Id: 110863 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp4216561vqr; Wed, 21 Jun 2023 01:52:14 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ4QPDAfm1ckZUzg1ff69pwN9RSaGy5qSk4Z93stYn0OKKXtOtJ/UiWqcF1IBxeXANsx4Frb X-Received: by 2002:a05:6870:a702:b0:188:101f:a628 with SMTP id g2-20020a056870a70200b00188101fa628mr12259162oam.20.1687337534020; Wed, 21 Jun 2023 01:52:14 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1687337533; cv=none; d=google.com; s=arc-20160816; b=W8rB/AtM75AI+J+4gzm5IweVjsqcpuMKfyivSI1gy6pk/g2yGLh28hCdSxLCVLyUKJ OEhgyPxTLCh2hJ3jL/XcbX/0MpwMCp9iYkEoszbIk1ilcRoDw4aVlYYsCMA2a9wF39we 9OyiHiMfIElqNe3li2Kwcsvnc+PF86kTIQPiEa0QSIJsBqW4u0udPiSGjQmV+MBdaKiu o6vfsnKdbIfEarP7FV32yN0ndhjpsvwDaJ17pbRfBBa78JOc4AQKqeHoZVUNbHnVdj5u lr1/SDjPGTxqqn+V8hkmp7sE5wgiimG3pW/H4nJHVJ53Pjc55sAQpbfWPfcEM05ty4mI n/tA== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=jdm0x44f0DZPQRgQWannoPLo9P6McTAM8LC51Z2exQ8=; b=tgRRoh7I6qIplBkupKUVQfVmVRui6VqbnGlMVfckbtvsYg1+QzXOaywtNaO9koy18A pMYKKGKrz4kZccUlkBg9p8UBs6jTQ0mLDqzmQOwLUR1viqMaVo4GmE6tvGk8uBgMhSW4 0gnydjip5QbRtjvVZ48p/Jp/ok539DBC6zaYwhUZBjMHSpDr6HmxNiq2fnCufuTXK39u jQnofl1+5OjR2FGwfBs+Un2BbzyBdQhP2lxyj+Zd2P1HSe4VGC4Z7vAlU0FEPdk7AmVl TOfnDsiSJ9vYYtZupMreyzQzk3p3n3BbaEP2QoTVFZya6boR5pTA5z5ZLMulNGg+ZOi8 EmWg== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=alibaba.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id 21-20020a621815000000b006662fba14a9si3582960pfy.73.2023.06.21.01.52.01; Wed, 21 Jun 2023 01:52:13 -0700 (PDT) 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; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=alibaba.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S229664AbjFUIcT (ORCPT + 99 others); Wed, 21 Jun 2023 04:32:19 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59214 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229999AbjFUIcP (ORCPT ); Wed, 21 Jun 2023 04:32:15 -0400 Received: from out30-119.freemail.mail.aliyun.com (out30-119.freemail.mail.aliyun.com [115.124.30.119]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id 61BF110E6 for ; Wed, 21 Jun 2023 01:32:14 -0700 (PDT) X-Alimail-AntiSpam: AC=PASS;BC=-1|-1;BR=01201311R121e4;CH=green;DM=||false|;DS=||;FP=0|-1|-1|-1|0|-1|-1|-1;HT=ay29a033018045170;MF=jefflexu@linux.alibaba.com;NM=1;PH=DS;RN=6;SR=0;TI=SMTPD_---0VlfGJyV_1687336330; Received: from localhost(mailfrom:jefflexu@linux.alibaba.com fp:SMTPD_---0VlfGJyV_1687336330) by smtp.aliyun-inc.com; Wed, 21 Jun 2023 16:32:10 +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: [RFC 1/2] erofs: update on-disk format for xattr bloom filter Date: Wed, 21 Jun 2023 16:32:08 +0800 Message-Id: <20230621083209.116024-2-jefflexu@linux.alibaba.com> X-Mailer: git-send-email 2.19.1.6.gb485710b In-Reply-To: <20230621083209.116024-1-jefflexu@linux.alibaba.com> References: <20230621083209.116024-1-jefflexu@linux.alibaba.com> MIME-Version: 1.0 X-Spam-Status: No, score=-9.9 required=5.0 tests=BAYES_00, ENV_AND_HDR_SPF_MATCH,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS, T_SCC_BODY_TEXT_LINE,UNPARSEABLE_RELAY,USER_IN_DEF_SPF_WL autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1769301642088930479?= X-GMAIL-MSGID: =?utf-8?q?1769301642088930479?= The xattr 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 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). Signed-off-by: Jingbo Xu --- 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..9daea86cdb52 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_BLOOM 0x00000003 /* * 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_map; /* bloom 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_BLOOM_BITS 32 +#define EROFS_XATTR_BLOOM_MASK (EROFS_XATTR_BLOOM_BITS - 1) +#define EROFS_XATTR_BLOOM_DEFAULT UINT32_MAX +#define EROFS_XATTR_BLOOM_COUNTS 2 + /* xattr entry (for both inline & shared xattrs) */ struct erofs_xattr_entry { __u8 e_name_len; /* length of name */ From patchwork Wed Jun 21 08:32:09 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jingbo Xu X-Patchwork-Id: 110865 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a59:994d:0:b0:3d9:f83d:47d9 with SMTP id k13csp4217064vqr; Wed, 21 Jun 2023 01:53:46 -0700 (PDT) X-Google-Smtp-Source: ACHHUZ4jZ40GeuUwSJeGXvRG6weHw3lrXuQlgoP0B93cwYLYZKu/VPfLJPz4zInVBd+b+0onr2Js X-Received: by 2002:a05:6a20:8f11:b0:11f:84d4:2fa8 with SMTP id b17-20020a056a208f1100b0011f84d42fa8mr6865084pzk.40.1687337626579; Wed, 21 Jun 2023 01:53:46 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1687337626; cv=none; d=google.com; s=arc-20160816; b=p331tQ8agBxQNzuKsWkNyjRI2EdgjhM/YBjdXjRyZ15YdLRXMpfpf9+e8xJ4tWtrGA qGwk59n8UzUPxsfMqPXtMO0CF0k7Nlh1CqppqBRCD4R5gB/TMjQ8bsefxrEkE83Yfcev dCBoUmQUHYFtaAHDcf0x2LMxdyC1Z0rDVAxLOSb3MlGG0TE+c4xdJz6qG6Q0pbgjPYOp 1Zuq+YwNSUwacChQbOD7Q9nYxuCt4k6VKEaDupSJ7vSZJ7t7wG0KYlqyl3WMWhoH/1lC zlNTzMmzMrwd98zNt321FZAp8FYjM1kvGN+YUNSotNbPmBa67WqgTZh5MF3Q+kAvwbSN BOrw== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:date:subject:cc:to:from; bh=oIAT8M+DKvAewzHVQb5BvMdk1hHvsxeoMQ0dgeTxf8g=; b=j0XevyVnJW0h+n+mdRDIQU9Y1n4DIj4nybc7vauXBYYcJ5raaAiSsnGulnylvhWkHa JKmNPIJwyBwPlTf1EmEJ0LX5PLwzf4mthzlUk0udQtUs5TEIddFlCRCc728Yg8XO9TRS k0ftzlmm+OvSCY44oP/T/QsVdMPXnDg5WZXCmCyTUflsXGG/RXwuWdGD+vJhLqWoN7VG f0ljEIZoIApGWceZUDXdN0xhdf78dIiaqo+ecm1hNBqvQQpOwLBaZO8/Ol93vhqXxbKz yAHee7ROKWG4vSZviqb0QsqsHPlaCZ0Ujo/OzE23mSXw7vg8z/cJTGrVzJoH1/ICZqLu HJ4g== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=alibaba.com Received: from out1.vger.email (out1.vger.email. [2620:137:e000::1:20]) by mx.google.com with ESMTP id km6-20020a17090327c600b001992f451a28si3553148plb.384.2023.06.21.01.53.31; Wed, 21 Jun 2023 01:53:46 -0700 (PDT) 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; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 2620:137:e000::1:20 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org; dmarc=fail (p=NONE sp=NONE dis=NONE) header.from=alibaba.com Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S231386AbjFUIcZ (ORCPT + 99 others); Wed, 21 Jun 2023 04:32:25 -0400 Received: from lindbergh.monkeyblade.net ([23.128.96.19]:59224 "EHLO lindbergh.monkeyblade.net" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S229759AbjFUIcS (ORCPT ); Wed, 21 Jun 2023 04:32:18 -0400 Received: from out30-133.freemail.mail.aliyun.com (out30-133.freemail.mail.aliyun.com [115.124.30.133]) by lindbergh.monkeyblade.net (Postfix) with ESMTPS id C841A19F for ; Wed, 21 Jun 2023 01:32:16 -0700 (PDT) X-Alimail-AntiSpam: AC=PASS;BC=-1|-1;BR=01201311R411e4;CH=green;DM=||false|;DS=||;FP=0|-1|-1|-1|0|-1|-1|-1;HT=ay29a033018045170;MF=jefflexu@linux.alibaba.com;NM=1;PH=DS;RN=6;SR=0;TI=SMTPD_---0VlfH3v6_1687336331; Received: from localhost(mailfrom:jefflexu@linux.alibaba.com fp:SMTPD_---0VlfH3v6_1687336331) by smtp.aliyun-inc.com; Wed, 21 Jun 2023 16:32:11 +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: [RFC 2/2] erofs: optimize getxattr with bloom filter Date: Wed, 21 Jun 2023 16:32:09 +0800 Message-Id: <20230621083209.116024-3-jefflexu@linux.alibaba.com> X-Mailer: git-send-email 2.19.1.6.gb485710b In-Reply-To: <20230621083209.116024-1-jefflexu@linux.alibaba.com> References: <20230621083209.116024-1-jefflexu@linux.alibaba.com> MIME-Version: 1.0 X-Spam-Status: No, score=-9.9 required=5.0 tests=BAYES_00, ENV_AND_HDR_SPF_MATCH,RCVD_IN_DNSWL_NONE,RCVD_IN_MSPIKE_H2, SPF_HELO_NONE,SPF_PASS,T_SCC_BODY_TEXT_LINE,UNPARSEABLE_RELAY, URIBL_BLOCKED,USER_IN_DEF_SPF_WL autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on lindbergh.monkeyblade.net Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org X-getmail-retrieved-from-mailbox: =?utf-8?q?INBOX?= X-GMAIL-THRID: =?utf-8?q?1769301738979114054?= X-GMAIL-MSGID: =?utf-8?q?1769301738979114054?= Boost the negative xattr lookup with bloom filter. The bit value for the bloom filter map has a reverse semantics for compatibility. That is, the mapped bits will be cleared to 0, while the bit value of 1 indicates the absence of corresponding xattr. Signed-off-by: Jingbo Xu --- fs/erofs/internal.h | 2 ++ fs/erofs/xattr.c | 16 +++++++++++++++- 2 files changed, 17 insertions(+), 1 deletion(-) diff --git a/fs/erofs/internal.h b/fs/erofs/internal.h index 1e39c03357d1..49b4b350af8a 100644 --- a/fs/erofs/internal.h +++ b/fs/erofs/internal.h @@ -285,6 +285,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_bloom, compat, COMPAT_XATTR_BLOOM) /* atomic flag definitions */ #define EROFS_I_EA_INITED_BIT 0 @@ -304,6 +305,7 @@ struct erofs_inode { unsigned char inode_isize; unsigned int xattr_isize; + unsigned long xattr_bloom_map; unsigned int xattr_shared_count; unsigned int *xattr_shared_xattrs; diff --git a/fs/erofs/xattr.c b/fs/erofs/xattr.c index 4376f654474d..1ab481b46e8d 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" 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_bloom_map = le32_to_cpu(ih->h_map); vi->xattr_shared_count = ih->h_shared_count; vi->xattr_shared_xattrs = kmalloc_array(vi->xattr_shared_count, sizeof(uint), GFP_KERNEL); @@ -392,8 +394,11 @@ int erofs_getxattr(struct inode *inode, int index, const char *name, void *buffer, size_t buffer_size) { - int ret; + int i, ret; + uint32_t bit; struct erofs_xattr_iter it; + struct erofs_inode *const vi = EROFS_I(inode); + struct erofs_sb_info *sbi = EROFS_SB(inode->i_sb); if (!name) return -EINVAL; @@ -402,6 +407,15 @@ int erofs_getxattr(struct inode *inode, int index, if (ret) return ret; + if (erofs_sb_has_xattr_bloom(sbi) && vi->xattr_bloom_map) { + for (i = 0; i < EROFS_XATTR_BLOOM_COUNTS; i++) { + bit = xxh32(name, strlen(name), index + i); + bit &= EROFS_XATTR_BLOOM_MASK; + if (test_bit(bit, &vi->xattr_bloom_map)) + return -ENOATTR; + } + } + it.index = index; it.name = (struct qstr)QSTR_INIT(name, strlen(name)); if (it.name.len > EROFS_NAME_LEN)