From patchwork Sat Feb 17 20:23:40 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chuck Lever X-Patchwork-Id: 202700 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:693c:2685:b0:108:e6aa:91d0 with SMTP id mn5csp494809dyc; Sat, 17 Feb 2024 12:24:35 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCXz4dwzewSmS6DdZSIwovWOLmg+7HETgorEpiCYA5Mato8evuglaRHWXMg1SR9LZU8tmdGLzBU0ztHjJUjIDp469Qt+7Q== X-Google-Smtp-Source: AGHT+IHixLv/tMODPIzSoqSUqDVuo/pmFJ15vccovboazNZjkJsXIn/mcviWeagGbvCwg6/Lab1P X-Received: by 2002:a0c:da08:0:b0:68c:3d2a:47e7 with SMTP id x8-20020a0cda08000000b0068c3d2a47e7mr7792316qvj.27.1708201474864; Sat, 17 Feb 2024 12:24:34 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1708201474; cv=pass; d=google.com; s=arc-20160816; b=lnd1/JIrXbFWWPADmvdH4FEeN8akj9oY1Fd6AwkGcq82hVSl8NYHHXRWArpDActmfv Ubvy/7UNCtHttlNDzy0uSgfp4tsBVuZt1EIe/dboE/m0OMbC7fMQFZ9NJdkNYz0lWx6m /CFdODne8aMlh7e4mHllxXcgs8gm22J432i2qNu8fYw8QW93yxb/oIkPINYxfaLhnIf+ IUyt3DZDHZl82VqC735wDo4RDeQKnyDn5y/cUDewyw+BZtSJq/jY6187cxHZ6wrrVnmU P47RitKAvX92ewsHtsXCBHH3o9IUB+hKeGI3Ih7CWTf2JBZL/RMHSo0mRmvwGR9DUx7l bfqg== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:user-agent:references:in-reply-to :message-id:date:cc:to:from:subject:dkim-signature; bh=LMwQkCs3Uwwg0hCaF42Dp3GN9kHRnCL1eJ1vax4uPe8=; fh=0JMhqiWEaK+qw2xgbbey7OsRaoj7Z6cFR6nhiwhAbe0=; b=azW94U8YhyFrcCinlrYP1oGtLnQZaeqCxmuJqrNitY0ZdNfQsitjKtQ7KkddXzvcgb K7wWcYgnlMYMZ4wguFIH8i7SeRduYKQGtgfcDt8zzs2Fvwq4iyM3MWVyK6IuJ5M87uha haFg41Lf33c6b990jN/XJUIoZxeb98Va/vq3YL6uZnd1Pjm9KHY53lIhF1rRgkcvVSaj H5al2lp5/lYHOecQLTW/2P2l4dl8tUvhRezBZ+CifPeyZkUA6tuEllBlfA6aXqWV15j3 XS6q/8XEcQcmzVSPSi3juZhYxS6ZH+egkpA51o3IUGsxhMf/mO2KaV8/riijWXYIK8ss A9Gg==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=P4X30OxK; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70068-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70068-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from ny.mirrors.kernel.org (ny.mirrors.kernel.org. [2604:1380:45d1:ec00::1]) by mx.google.com with ESMTPS id fn3-20020ad45d63000000b0068cc38d2032si2694982qvb.364.2024.02.17.12.24.34 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Feb 2024 12:24:34 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-70068-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1; Authentication-Results: mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=P4X30OxK; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70068-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70068-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ny.mirrors.kernel.org (Postfix) with ESMTPS id A510B1C21BD2 for ; Sat, 17 Feb 2024 20:24:34 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 355B07F49E; Sat, 17 Feb 2024 20:23:45 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="P4X30OxK" Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 9F6DC7F48B; Sat, 17 Feb 2024 20:23:42 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201422; cv=none; b=OPCVtslzwYeUx0LNhhbZ+xx97T07EOaZWxcQzjb4C9X6X/t+qEQBRncuuMge1Ed4r5l8aa1ZdWU2i/VO2mHpQOkdZd7g7HVtNJN8jB7CdldziP7VTt43AJtHXDIgiE19rGX5YmjVOYdTtCiET/PSbzcq8LoCsW8tjDkQ0zA06Ik= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201422; c=relaxed/simple; bh=R5X4D36CuE1wpCsrFE/3Fuex0DnO2GtnjfkqVv5cjQg=; h=Subject:From:To:Cc:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=BzUEFfjFPuZ4aoi9hVC7uDl1OA6ZiB7JI7Kq1Qy9L2bjt/iHE06/moj1rpQppUAJUSpiwb3YO1F9SdGdpH7KPhJTTdoRU+gxk417zW5XEqClsIFHldXRi7aae1KuxNvr+2aDrOFAdVDUkrqobXpOZbzt/y1P3e0RSfotP8lYOHQ= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=P4X30OxK; arc=none smtp.client-ip=10.30.226.201 Received: by smtp.kernel.org (Postfix) with ESMTPSA id 32618C433F1; Sat, 17 Feb 2024 20:23:41 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1708201422; bh=R5X4D36CuE1wpCsrFE/3Fuex0DnO2GtnjfkqVv5cjQg=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=P4X30OxKc0EN8nPXm8GE/AdSc3yeT5iVNwWMRGyRMVcJFIie5F4caTrhUc28NAuXO 9voVKSq/opp81jg2cRH3/szMzpTTQ/4XgrT8WdD2WpFkvBWhxoEj1F/vcTYv1kOP4+ FZdDrkL9Ov1gk0qvcx9T66jKl6xWpHB0h4rQB5Ze7WhCUX3SKZ6cEUOGk9Z5vnO5+j XY0aze0RMR8AG9xJitjPfN95aBR+joD0NoDr2zyACqqmGYNchunmvsmDUeW9cgCf9a DCi8QemiRpOkaILmDK6aiHQNcv88w0pNMBL71uYhHVosom/O2z6gP7OwvFkgLUc3ph MCA7wONlVDoYw== Subject: [PATCH v2 1/6] libfs: Re-arrange locking in offset_iterate_dir() From: Chuck Lever To: viro@zeniv.linux.org.uk, brauner@kernel.org, jack@suse.cz, hughd@google.com, akpm@linux-foundation.org, Liam.Howlett@oracle.com, oliver.sang@intel.com, feng.tang@intel.com Cc: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, lkp@intel.com Date: Sat, 17 Feb 2024 15:23:40 -0500 Message-ID: <170820142021.6328.15047865406275957018.stgit@91.116.238.104.host.secureserver.net> In-Reply-To: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> References: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> User-Agent: StGit/1.5 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1791179069430556207 X-GMAIL-MSGID: 1791179069430556207 From: Chuck Lever Liam and Matthew say that once the RCU read lock is released, xa_state is not safe to re-use for the next xas_find() call. But the RCU read lock must be released on each loop iteration so that dput(), which might_sleep(), can be called safely. Thus we are forced to walk the offset tree with fresh state for each directory entry. xa_find() can do this for us, though it might be a little less efficient than maintaining xa_state locally. We believe that in the current code base, inode->i_rwsem provides protection for the xa_state maintained in offset_iterate_dir(). However, there is no guarantee that will continue to be the case in the future. Since offset_iterate_dir() doesn't build xa_state locally any more, there's no longer a strong need for offset_find_next(). Clean up by rolling these two helpers together. Suggested-by: Liam R. Howlett Message-ID: <170785993027.11135.8830043889278631735.stgit@91.116.238.104.host.secureserver.net> Signed-off-by: Chuck Lever Reviewed-by: Jan Kara --- fs/libfs.c | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) diff --git a/fs/libfs.c b/fs/libfs.c index eec6031b0155..752e24c669d9 100644 --- a/fs/libfs.c +++ b/fs/libfs.c @@ -402,12 +402,13 @@ static loff_t offset_dir_llseek(struct file *file, loff_t offset, int whence) return vfs_setpos(file, offset, U32_MAX); } -static struct dentry *offset_find_next(struct xa_state *xas) +static struct dentry *offset_find_next(struct offset_ctx *octx, loff_t offset) { struct dentry *child, *found = NULL; + XA_STATE(xas, &octx->xa, offset); rcu_read_lock(); - child = xas_next_entry(xas, U32_MAX); + child = xas_next_entry(&xas, U32_MAX); if (!child) goto out; spin_lock(&child->d_lock); @@ -430,12 +431,11 @@ static bool offset_dir_emit(struct dir_context *ctx, struct dentry *dentry) static void *offset_iterate_dir(struct inode *inode, struct dir_context *ctx) { - struct offset_ctx *so_ctx = inode->i_op->get_offset_ctx(inode); - XA_STATE(xas, &so_ctx->xa, ctx->pos); + struct offset_ctx *octx = inode->i_op->get_offset_ctx(inode); struct dentry *dentry; while (true) { - dentry = offset_find_next(&xas); + dentry = offset_find_next(octx, ctx->pos); if (!dentry) return ERR_PTR(-ENOENT); @@ -444,8 +444,8 @@ static void *offset_iterate_dir(struct inode *inode, struct dir_context *ctx) break; } + ctx->pos = dentry2offset(dentry) + 1; dput(dentry); - ctx->pos = xas.xa_index + 1; } return NULL; } From patchwork Sat Feb 17 20:23:47 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chuck Lever X-Patchwork-Id: 202701 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:693c:2685:b0:108:e6aa:91d0 with SMTP id mn5csp494875dyc; Sat, 17 Feb 2024 12:24:52 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCUi05nC7zOnB0P8wKKutwTBI2BPbQLUWkoFkGnfENUa1gHKVZAMm45cntjKaXlOgKYWPTLcC/xdaXLMtMs+DkVHiuHY7Q== X-Google-Smtp-Source: AGHT+IHziewwcdt6q0yCW7s8JX+6IxqgaQLmBxHbMwNFpKtTJITDYybGsua4iOKWSBd6xYDa1Xk0 X-Received: by 2002:a05:6214:b62:b0:68e:f594:30cd with SMTP id ey2-20020a0562140b6200b0068ef59430cdmr13602730qvb.30.1708201492530; Sat, 17 Feb 2024 12:24:52 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1708201492; cv=pass; d=google.com; s=arc-20160816; b=vlcKPbuTvRH25XVS/H4F9M3PgaEBmM4TaS6Qjp36V9bpxACDIj39C5DdAyRh/wj/OU J04LBY5WiKyAWDMtijxpMVihIMTKFSz66fpTdiNBId0gCCpMZ/A/+ThQFkqH/ajG85QS VIG7US3lL1iqa06zmg8/uM1D2xnZrbS9xw7VvERd0JPBWdtJp+rTIBucalsrhpWU0X2r ZhFKWkkcd2zED3xA3jr/3R6Cn9gAMkcKek8S6kso4AJw+zjhSnEHHYJOUWq9T5YL0tTh RMEcfx++qXTVAZBr+qSkhELqtMUsx1G43/npjN5xzkZXsO6fdWaEQK/QaFBSpBgiV2ab xgRw== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:user-agent:references:in-reply-to :message-id:date:cc:to:from:subject:dkim-signature; bh=4esY7/t9LpWl+KnSBbx/mU7dFpjJbd72wLpgnvk0B5o=; fh=0JMhqiWEaK+qw2xgbbey7OsRaoj7Z6cFR6nhiwhAbe0=; b=p0oZokCiObDMJYsh1dTDnLk6sjVAQgkBcjhohBpLOU39yvAISx0DBpaaVZrGx+60PO mMbgjLWtdIXCNi0Ceb3XZrBe3t2lLaWQfz7OpsbzQbHo+v0gFqFe/orrpJfGE+fJrQmo izZg/3JVw5W+WrRtdOXmx6wMxBti7XKi0LdDLtEFwm1tFAXsjUhDNA8hYaKOCbLr1mpM xhrDbT8FCPunjjrnyPucZeZILEGH9D1jkoQsDkGDz+mRlA9UrWJMxl54mEHnuOMrF1/m 14xEGde8Hkc6upO2c56zqaP1Txinmn7UnBnrNcr3xCi4tfkIO11LtRUNJsc6+19LCS+I 2Rlw==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=u+UucdZp; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70069-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70069-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from ny.mirrors.kernel.org (ny.mirrors.kernel.org. [2604:1380:45d1:ec00::1]) by mx.google.com with ESMTPS id t13-20020a0562140c6d00b0068ef73244d6si2692069qvj.336.2024.02.17.12.24.52 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Feb 2024 12:24:52 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-70069-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) client-ip=2604:1380:45d1:ec00::1; Authentication-Results: mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=u+UucdZp; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70069-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45d1:ec00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70069-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by ny.mirrors.kernel.org (Postfix) with ESMTPS id 5262D1C21973 for ; Sat, 17 Feb 2024 20:24:52 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 53F227F7D8; Sat, 17 Feb 2024 20:23:52 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="u+UucdZp" Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id C2F357E776; Sat, 17 Feb 2024 20:23:49 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201429; cv=none; b=N2hfDNVF5RhwyRG2EtaSQfWRnXJyzcY/Y5kq/rasw9MZ0xqZ23wRS3jkXzJ0lc3fHRAPUJkaIAcbeF1RRmJRDnQfeRz5UPQ9C6TD2ivjnrun4hW1Wz6PMMx+Tf4QT7DN6N/CaTdBRiFFnTLPHMr7jk9R0fLvD0+9K0IUXsNbwyw= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201429; c=relaxed/simple; bh=zZF7EKK8ftmerUGGzBqiAHI4dgUgyTG9wsRPzQOCpuw=; h=Subject:From:To:Cc:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=SZMjk8QNYGFJwRTufvO4v5a/X/o0OL+g3E8VbO7FOZG+71bV/tXp18pAis1r8zC6OQEGC4LK/YVBtWAxCtrHU+ZKBso54NyisTUi6AL0yGxSVfQiVI4QwSgsAyrR+tQgDpqtq9ZNAXwE7GXGyJDIn9rtI5smdq0DuZNftzFGg/M= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=u+UucdZp; arc=none smtp.client-ip=10.30.226.201 Received: by smtp.kernel.org (Postfix) with ESMTPSA id 67695C433F1; Sat, 17 Feb 2024 20:23:48 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1708201429; bh=zZF7EKK8ftmerUGGzBqiAHI4dgUgyTG9wsRPzQOCpuw=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=u+UucdZptl0WKrqPf/GzRK/R6NMFecqwM1YYAZqGuTX8Ybt6NeHmaEbfcq4uMU3U9 Ecw2UXrIEBHT8fRD9InGawCnpOxNmcCwZ3ahX2kS2mH4tgddN77dJbqWyCVNT0bMA0 uCsmWi90+2ZSjAPCwOFrlaJNnxcvMf1DHC0MSm/5B9QZw7+aAvDn42p2lZ+yy+GcIn qhcNCJFzcAb5Jnw3TT63+A5NFCXaOpx52dL57L05xf7l8y9xkTdOKKrbztYnBt3Vns pWl/My0Gwa3PLUcjSsCc6gbFPHphzxIOwKUeNRyGz/+J92oHuycuFbRbeF/gWsHo+A Yq/c76UNcJfgQ== Subject: [PATCH v2 2/6] libfs: Define a minimum directory offset From: Chuck Lever To: viro@zeniv.linux.org.uk, brauner@kernel.org, jack@suse.cz, hughd@google.com, akpm@linux-foundation.org, Liam.Howlett@oracle.com, oliver.sang@intel.com, feng.tang@intel.com Cc: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, lkp@intel.com Date: Sat, 17 Feb 2024 15:23:47 -0500 Message-ID: <170820142741.6328.12428356024575347885.stgit@91.116.238.104.host.secureserver.net> In-Reply-To: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> References: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> User-Agent: StGit/1.5 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1791179088323987038 X-GMAIL-MSGID: 1791179088323987038 From: Chuck Lever This value is used in several places, so make it a symbolic constant. Reviewed-by: Jan Kara Signed-off-by: Chuck Lever --- fs/libfs.c | 13 ++++++++----- 1 file changed, 8 insertions(+), 5 deletions(-) diff --git a/fs/libfs.c b/fs/libfs.c index 752e24c669d9..f0045db739df 100644 --- a/fs/libfs.c +++ b/fs/libfs.c @@ -240,6 +240,11 @@ const struct inode_operations simple_dir_inode_operations = { }; EXPORT_SYMBOL(simple_dir_inode_operations); +/* 0 is '.', 1 is '..', so always start with offset 2 or more */ +enum { + DIR_OFFSET_MIN = 2, +}; + static void offset_set(struct dentry *dentry, u32 offset) { dentry->d_fsdata = (void *)((uintptr_t)(offset)); @@ -261,9 +266,7 @@ void simple_offset_init(struct offset_ctx *octx) { xa_init_flags(&octx->xa, XA_FLAGS_ALLOC1); lockdep_set_class(&octx->xa.xa_lock, &simple_offset_xa_lock); - - /* 0 is '.', 1 is '..', so always start with offset 2 */ - octx->next_offset = 2; + octx->next_offset = DIR_OFFSET_MIN; } /** @@ -276,7 +279,7 @@ void simple_offset_init(struct offset_ctx *octx) */ int simple_offset_add(struct offset_ctx *octx, struct dentry *dentry) { - static const struct xa_limit limit = XA_LIMIT(2, U32_MAX); + static const struct xa_limit limit = XA_LIMIT(DIR_OFFSET_MIN, U32_MAX); u32 offset; int ret; @@ -481,7 +484,7 @@ static int offset_readdir(struct file *file, struct dir_context *ctx) return 0; /* In this case, ->private_data is protected by f_pos_lock */ - if (ctx->pos == 2) + if (ctx->pos == DIR_OFFSET_MIN) file->private_data = NULL; else if (file->private_data == ERR_PTR(-ENOENT)) return 0; From patchwork Sat Feb 17 20:23:54 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chuck Lever X-Patchwork-Id: 202703 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:693c:2685:b0:108:e6aa:91d0 with SMTP id mn5csp495425dyc; Sat, 17 Feb 2024 12:26:48 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCUqXUMpyNoo2jJcX6DJK7o5ARPPQnxLRJI5OiAt7S73WOwmIXRPynUNAPMzbrmOE8Zf6tHWLEEEko3054q5acK+sf6HOQ== X-Google-Smtp-Source: AGHT+IEotM3YGMYDZNduv5YWUdRvALjh98c+uhjzXH5EeHO0GUcBc3ln2M2nMMdsb2XXMJkfNR/9 X-Received: by 2002:a05:6870:a2c7:b0:21a:80cd:734a with SMTP id w7-20020a056870a2c700b0021a80cd734amr10823303oak.52.1708201608521; Sat, 17 Feb 2024 12:26:48 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1708201608; cv=pass; d=google.com; s=arc-20160816; b=MABidut3pInyBoyMax9bl8Hl05Drr47IiXMvSP3wwG8Ysav2MNHrfEMXEsBkvwMsfP zSrd4LsL0kcsgNEjLGFrsQM5kOlVGb8mOcf5EQtNkSZfYa1RfeTJx+T1AFORy3SBJILK zpoHcCZr4NM80Pvjv0lh4fDuq7U6egCQiSkM9fCYdksUvM4n59hIojP5PN1ERKRzOYsO qRI0/gGuUg/f9wuLELiT3JdVqqklmWD3yMggsHhQ63/R8yN57UsUmfzY0kM+MximFkMC F4DAfzNpjo91UMKLukru1t1T+Y0Nx/0ZINJesIIRhRYPunHjrPnYHg0ZoRi0XWv7PAiz kyng== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:user-agent:references:in-reply-to :message-id:date:cc:to:from:subject:dkim-signature; bh=4qPfTWx2wBbF6c6gCarkXbRmheLFXCu0GVp2UOlPxx0=; fh=0JMhqiWEaK+qw2xgbbey7OsRaoj7Z6cFR6nhiwhAbe0=; b=D3ItboA813EFtrKSfTg3mPlg+rfOG5iyF7/qCbIBMmNw/AjK8/H7l9ucOfSRoXh0Bq 50YG4//u8y6KtQTGjqwU9y7siqS97bC56qNr7NymSOwYccQHVE3JLg1agUNnbgj++gBj 4tE4It4+F2dYyFNViwNC8GDGeZGnwuP2u0OUdNaXHsaIkppZvMazbk8x9xXXWAnvya9Q vmxWKGFbhLa/cm1IKBj2W52fBmO9RFtTvXdb9gUCoLXIaHIdFZ8/2FGjA/19XtaooDhB c7u16xQ/s054QPva13phyfDDSauOeLKGMXnXoDfhYL9Y4AFaW1OvE6yzfPCSzGrtUs6Z lWnw==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=hSPSc3YT; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70070-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70070-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from sv.mirrors.kernel.org (sv.mirrors.kernel.org. [139.178.88.99]) by mx.google.com with ESMTPS id y4-20020a636404000000b005cdfaea88adsi1914247pgb.774.2024.02.17.12.26.48 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Feb 2024 12:26:48 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-70070-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) client-ip=139.178.88.99; Authentication-Results: mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=hSPSc3YT; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70070-ouuuleilei=gmail.com@vger.kernel.org designates 139.178.88.99 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70070-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sv.mirrors.kernel.org (Postfix) with ESMTPS id 1BB4E285250 for ; Sat, 17 Feb 2024 20:25:09 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 826627F7DD; Sat, 17 Feb 2024 20:23:59 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="hSPSc3YT" Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id EF9A67E78A; Sat, 17 Feb 2024 20:23:56 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201437; cv=none; b=gnhCauvvrJ9cE55qf5+gsvLnTpFvsIkbY1lR42+tnpMRpaBanjv3fo0qg1LS2BDFzIuR0vdEDOZUVb2g0Lioze2I3c+TC6hEiAhrEZEmtjf+Qa1m7Ffa5AGZ94ixfs2DgMpv1HPbaLS5awutri/5EJ50oMUGlaeh7JatoUKRwyc= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201437; c=relaxed/simple; bh=Wl5YZpZIwNdyP0j7hPhqHmMF9/qk/KQwvYrvu9hugUU=; h=Subject:From:To:Cc:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=EjnHgVE/RGufgZl+M9v1h4QQQrTCQCnooUTOqQoRHC9BvxiJLj09GwOUNij9CalmVIvL+uXWWZn4/8iMnCYy+WLY/f7jFnznT18uC+moXRtCwE9cYzan+gWFi06tS9G6Oq9S7Nx10UOtKlvbbf+bQ//WWwh6lQKmQxAVOybhLJ0= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=hSPSc3YT; arc=none smtp.client-ip=10.30.226.201 Received: by smtp.kernel.org (Postfix) with ESMTPSA id 9828DC433C7; Sat, 17 Feb 2024 20:23:55 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1708201436; bh=Wl5YZpZIwNdyP0j7hPhqHmMF9/qk/KQwvYrvu9hugUU=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=hSPSc3YTTnETZH7tpcODEx1noXHcGxWv4jbcdGMmkKFsEWnfprlfhBAMvQrRX//ay cgIsqNc565w8r+aJyx0o2wv3/D0ExShXnYuhchx1OdQ6esqSVlx4XCBIwsz0wR4Tc+ SLiXgISMOVYmI8HKJURtotqLYVMwdItc1YCaZMJaTNJ9wiCtKOi5mW2hiO9NAnrsL4 eCstP8GCNdyd2EaFgD7YXM37wiYuqB7EwqVdbHXQCbINlch7KtIHb/1vlLp4w3hwYH R9vt1ltVSLWnz79sr+OcRO1RCM8jv6mrvIq9talI2/YedhJ5Oy60DgXlVhj+DFJHq/ p8Xc60B+KN9Pw== Subject: [PATCH v2 3/6] libfs: Add simple_offset_empty() From: Chuck Lever To: viro@zeniv.linux.org.uk, brauner@kernel.org, jack@suse.cz, hughd@google.com, akpm@linux-foundation.org, Liam.Howlett@oracle.com, oliver.sang@intel.com, feng.tang@intel.com Cc: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, lkp@intel.com Date: Sat, 17 Feb 2024 15:23:54 -0500 Message-ID: <170820143463.6328.7872919188371286951.stgit@91.116.238.104.host.secureserver.net> In-Reply-To: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> References: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> User-Agent: StGit/1.5 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1791179209643446325 X-GMAIL-MSGID: 1791179209643446325 From: Chuck Lever For simple filesystems that use directory offset mapping, rely strictly on the directory offset map to tell when a directory has no children. After this patch is applied, the emptiness test holds only the RCU read lock when the directory being tested has no children. In addition, this adds another layer of confirmation that simple_offset_add/remove() are working as expected. Reviewed-by: Jan Kara Signed-off-by: Chuck Lever --- fs/libfs.c | 32 ++++++++++++++++++++++++++++++++ include/linux/fs.h | 1 + mm/shmem.c | 4 ++-- 3 files changed, 35 insertions(+), 2 deletions(-) diff --git a/fs/libfs.c b/fs/libfs.c index f0045db739df..f7f92a49a418 100644 --- a/fs/libfs.c +++ b/fs/libfs.c @@ -313,6 +313,38 @@ void simple_offset_remove(struct offset_ctx *octx, struct dentry *dentry) offset_set(dentry, 0); } +/** + * simple_offset_empty - Check if a dentry can be unlinked + * @dentry: dentry to be tested + * + * Returns 0 if @dentry is a non-empty directory; otherwise returns 1. + */ +int simple_offset_empty(struct dentry *dentry) +{ + struct inode *inode = d_inode(dentry); + struct offset_ctx *octx; + struct dentry *child; + unsigned long index; + int ret = 1; + + if (!inode || !S_ISDIR(inode->i_mode)) + return ret; + + index = DIR_OFFSET_MIN; + octx = inode->i_op->get_offset_ctx(inode); + xa_for_each(&octx->xa, index, child) { + spin_lock(&child->d_lock); + if (simple_positive(child)) { + spin_unlock(&child->d_lock); + ret = 0; + break; + } + spin_unlock(&child->d_lock); + } + + return ret; +} + /** * simple_offset_rename_exchange - exchange rename with directory offsets * @old_dir: parent of dentry being moved diff --git a/include/linux/fs.h b/include/linux/fs.h index ed5966a70495..03d141809a2c 100644 --- a/include/linux/fs.h +++ b/include/linux/fs.h @@ -3267,6 +3267,7 @@ struct offset_ctx { void simple_offset_init(struct offset_ctx *octx); int simple_offset_add(struct offset_ctx *octx, struct dentry *dentry); void simple_offset_remove(struct offset_ctx *octx, struct dentry *dentry); +int simple_offset_empty(struct dentry *dentry); int simple_offset_rename_exchange(struct inode *old_dir, struct dentry *old_dentry, struct inode *new_dir, diff --git a/mm/shmem.c b/mm/shmem.c index d7c84ff62186..6fed524343cb 100644 --- a/mm/shmem.c +++ b/mm/shmem.c @@ -3374,7 +3374,7 @@ static int shmem_unlink(struct inode *dir, struct dentry *dentry) static int shmem_rmdir(struct inode *dir, struct dentry *dentry) { - if (!simple_empty(dentry)) + if (!simple_offset_empty(dentry)) return -ENOTEMPTY; drop_nlink(d_inode(dentry)); @@ -3431,7 +3431,7 @@ static int shmem_rename2(struct mnt_idmap *idmap, return simple_offset_rename_exchange(old_dir, old_dentry, new_dir, new_dentry); - if (!simple_empty(new_dentry)) + if (!simple_offset_empty(new_dentry)) return -ENOTEMPTY; if (flags & RENAME_WHITEOUT) { From patchwork Sat Feb 17 20:24:01 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chuck Lever X-Patchwork-Id: 202705 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:693c:2685:b0:108:e6aa:91d0 with SMTP id mn5csp495993dyc; Sat, 17 Feb 2024 12:29:00 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCVI6FJ7y89Kha3f9Eo0hqvZ9Z0zkVzFicRo2WdjsQpDuAF9QlzJBEg23V5nyfb0Fx9ZMSut61blLlMriJMrzx4mNANhWw== X-Google-Smtp-Source: AGHT+IF9nSEeweUkrCAaZ8JuFEnqLrejSVRDbHC/6jnbeyFzgEh0xDZ/gzFs6sdRDG89OWY+bdvD X-Received: by 2002:a05:6a21:3118:b0:19e:3391:343b with SMTP id yz24-20020a056a21311800b0019e3391343bmr14965495pzb.27.1708201740680; Sat, 17 Feb 2024 12:29:00 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1708201740; cv=pass; d=google.com; s=arc-20160816; b=lLRADhwI/kzlOYn3DApQPXvjDwjiddUcq6Nt38AzOMKi75UvBKcNwf9rPiA2OGTu1X 6AzV0F2TbS1zqFe+irlLA/e7ZpC0XkWjtZI9JhVX3Zua24lWew3Od86bi4Rv8dZzoQYr L82ieak9fuU5FG6W6PdjerXC1azTHcMU1HBCHdtHHJm0yuHvH2pRa+VSilQ754BDsdYq NbzVnRd7GzLd1tLTVdID2m8NfhMK29TpP5NfYeauh6An23X71JnSQ+lj/3skdroz6k+z wTkowk6VvAQlYb8MacCZvV4By0Z85upNk5excbSLhwgNKfypSp22Cmk+/Hv/5m3/s0Cq dk7w== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:user-agent:references:in-reply-to :message-id:date:cc:to:from:subject:dkim-signature; bh=SMUmZcMQoKBIp6RbfLcR8dux0Zzz6xVP4+GW5vJ+kwE=; fh=0JMhqiWEaK+qw2xgbbey7OsRaoj7Z6cFR6nhiwhAbe0=; b=Gq7f5afhp3VVpXWyJTuE7yOEpeyBP/0I+8MvPZC8GLrxWVxfj4wRJvwAFqgU9Jn8CK Z0XWtMRZgbKqjfGJyYdaAeX1Pnrl33NHrPdrfaUObjrwlH9UOU8iE11CYcCeM/gB+xrH hcUmwPxQ3/nu7E2IU9MnaPII6urnhlbvNndGjPSUg+AXb8ymCKcON9LaJ0z4UCT4viwJ a4WkDyO1hRIPnq7d/XJILDXKTkCVu1D6RJZ/u3I59SQVu9sMQnUlyw8R56zHdrNjb8V8 lOW3jn8FKsC8E1+GRgqzWMZvDHH+89KBNQdG4+LRT98qQmP9P+V4Cmw+WBOG2CDmmBpc 30/w==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=LKKwFZ37; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70071-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70071-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from sy.mirrors.kernel.org (sy.mirrors.kernel.org. [2604:1380:40f1:3f00::1]) by mx.google.com with ESMTPS id a27-20020a630b5b000000b005dc87f9cc80si1848204pgl.553.2024.02.17.12.29.00 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Feb 2024 12:29:00 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-70071-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) client-ip=2604:1380:40f1:3f00::1; Authentication-Results: mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=LKKwFZ37; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70071-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:40f1:3f00::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70071-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sy.mirrors.kernel.org (Postfix) with ESMTPS id 10B95B235E2 for ; Sat, 17 Feb 2024 20:25:29 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id 20DDF7FBB2; Sat, 17 Feb 2024 20:24:07 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="LKKwFZ37" Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 28C827EEF6; Sat, 17 Feb 2024 20:24:03 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201444; cv=none; b=pbJ/J5lzUyr9ya4iOqBG4Aa6YxjHifo+tGcPKmibd4WxwPmu6zyXPYMEMycmX5Pp0BOQaGj7ohbz8wfUt7PgiZy+R4zL5BMCuzeUsi5mYUbKXbAdPZb+V5lUwMbQ47dDoOuHevTHpMBFH5x07LeKZkuBvQztyh9yeoyEuurLr/Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201444; c=relaxed/simple; bh=B9f3lBdgCzE5vmYqmwo7dByZImNHwFkUKnKEUUxLAe8=; h=Subject:From:To:Cc:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=bypAK7cDnMOjxr++vqKsoaLywbIxuiXLvSbaIOBbQ0eynB6eaBBFS1xPeqiie1pFUqhNWVBGdSUWypA9xhqEwJKLHyDWMlfLTgDJPtdvSo6klTFZ3C8NbBCeSEWCW4j8RLI/zCitSqQ8NLZpZ4OQWTPDsUYqYmpY8GkYBC1u61o= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=LKKwFZ37; arc=none smtp.client-ip=10.30.226.201 Received: by smtp.kernel.org (Postfix) with ESMTPSA id B44EAC43390; Sat, 17 Feb 2024 20:24:02 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1708201443; bh=B9f3lBdgCzE5vmYqmwo7dByZImNHwFkUKnKEUUxLAe8=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=LKKwFZ378z7nftyteopcpFImAvTgQDtbs6xRUS2AQ1HltVj6RhcqOIUwjYinyg1U0 GDDicWz5fjRAz4dbG9+0SL6K5hMzvUbHJ35XkN5ywzAsR9cfQwY7TiXSjSZ5oW5sit undKjeWvGc1a7gM6AwMn9yB8nc1zUm8pz2QzWsQo05o28qpCqLf2sWiKayXQCsipgw jNNOwjHB+9U8UjoIo9pD7Bo4l23YoRl2ygwooQhBOhzIhhnzp4mn5QrKSRmh/jZqPz q+XtUJWAzB7Cp2QTyfet6z7B5fjdWN0dgaLuOaU6PxCE6WYPA56RHSrvUhzJQpBufG lsiQTs4cxaUfA== Subject: [PATCH v2 4/6] maple_tree: Add mtree_alloc_cyclic() From: Chuck Lever To: viro@zeniv.linux.org.uk, brauner@kernel.org, jack@suse.cz, hughd@google.com, akpm@linux-foundation.org, Liam.Howlett@oracle.com, oliver.sang@intel.com, feng.tang@intel.com Cc: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, lkp@intel.com Date: Sat, 17 Feb 2024 15:24:01 -0500 Message-ID: <170820144179.6328.12838600511394432325.stgit@91.116.238.104.host.secureserver.net> In-Reply-To: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> References: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> User-Agent: StGit/1.5 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1791179348492371356 X-GMAIL-MSGID: 1791179348492371356 From: Chuck Lever I need a cyclic allocator for the simple_offset implementation in fs/libfs.c. Signed-off-by: Chuck Lever --- include/linux/maple_tree.h | 7 +++ lib/maple_tree.c | 93 ++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 100 insertions(+) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index b3d63123b945..a53ad4dabd7e 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -171,6 +171,7 @@ enum maple_type { #define MT_FLAGS_LOCK_IRQ 0x100 #define MT_FLAGS_LOCK_BH 0x200 #define MT_FLAGS_LOCK_EXTERN 0x300 +#define MT_FLAGS_ALLOC_WRAPPED 0x0800 #define MAPLE_HEIGHT_MAX 31 @@ -319,6 +320,9 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first, int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, void *entry, unsigned long size, unsigned long min, unsigned long max, gfp_t gfp); +int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp, + void *entry, unsigned long range_lo, unsigned long range_hi, + unsigned long *next, gfp_t gfp); int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, void *entry, unsigned long size, unsigned long min, unsigned long max, gfp_t gfp); @@ -499,6 +503,9 @@ void *mas_find_range(struct ma_state *mas, unsigned long max); void *mas_find_rev(struct ma_state *mas, unsigned long min); void *mas_find_range_rev(struct ma_state *mas, unsigned long max); int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp); +int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp, + void *entry, unsigned long range_lo, unsigned long range_hi, + unsigned long *next, gfp_t gfp); bool mas_nomem(struct ma_state *mas, gfp_t gfp); void mas_pause(struct ma_state *mas); diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6f241bb38799..af0970288727 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4290,6 +4290,56 @@ static inline void *mas_insert(struct ma_state *mas, void *entry) } +/** + * mas_alloc_cyclic() - Internal call to find somewhere to store an entry + * @mas: The maple state. + * @startp: Pointer to ID. + * @range_lo: Lower bound of range to search. + * @range_hi: Upper bound of range to search. + * @entry: The entry to store. + * @next: Pointer to next ID to allocate. + * @gfp: The GFP_FLAGS to use for allocations. + * + * Return: 0 if the allocation succeeded without wrapping, 1 if the + * allocation succeeded after wrapping, or -EBUSY if there are no + * free entries. + */ +int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp, + void *entry, unsigned long range_lo, unsigned long range_hi, + unsigned long *next, gfp_t gfp) +{ + unsigned long min = range_lo; + int ret = 0; + + range_lo = max(min, *next); + ret = mas_empty_area(mas, range_lo, range_hi, 1); + if ((mas->tree->ma_flags & MT_FLAGS_ALLOC_WRAPPED) && ret == 0) { + mas->tree->ma_flags &= ~MT_FLAGS_ALLOC_WRAPPED; + ret = 1; + } + if (ret < 0 && range_lo > min) { + ret = mas_empty_area(mas, min, range_hi, 1); + if (ret == 0) + ret = 1; + } + if (ret < 0) + return ret; + + do { + mas_insert(mas, entry); + } while (mas_nomem(mas, gfp)); + if (mas_is_err(mas)) + return xa_err(mas->node); + + *startp = mas->index; + *next = *startp + 1; + if (*next == 0) + mas->tree->ma_flags |= MT_FLAGS_ALLOC_WRAPPED; + + return ret; +} +EXPORT_SYMBOL(mas_alloc_cyclic); + static __always_inline void mas_rewalk(struct ma_state *mas, unsigned long index) { retry: @@ -6443,6 +6493,49 @@ int mtree_alloc_range(struct maple_tree *mt, unsigned long *startp, } EXPORT_SYMBOL(mtree_alloc_range); +/** + * mtree_alloc_cyclic() - Find somewhere to store this entry in the tree. + * @mt: The maple tree. + * @startp: Pointer to ID. + * @range_lo: Lower bound of range to search. + * @range_hi: Upper bound of range to search. + * @entry: The entry to store. + * @next: Pointer to next ID to allocate. + * @gfp: The GFP_FLAGS to use for allocations. + * + * Finds an empty entry in @mt after @next, stores the new index into + * the @id pointer, stores the entry at that index, then updates @next. + * + * @mt must be initialized with the MT_FLAGS_ALLOC_RANGE flag. + * + * Context: Any context. Takes and releases the mt.lock. May sleep if + * the @gfp flags permit. + * + * Return: 0 if the allocation succeeded without wrapping, 1 if the + * allocation succeeded after wrapping, -ENOMEM if memory could not be + * allocated, -EINVAL if @mt cannot be used, or -EBUSY if there are no + * free entries. + */ +int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp, + void *entry, unsigned long range_lo, unsigned long range_hi, + unsigned long *next, gfp_t gfp) +{ + int ret; + + MA_STATE(mas, mt, 0, 0); + + if (!mt_is_alloc(mt)) + return -EINVAL; + if (WARN_ON_ONCE(mt_is_reserved(entry))) + return -EINVAL; + mtree_lock(mt); + ret = mas_alloc_cyclic(&mas, startp, entry, range_lo, range_hi, + next, gfp); + mtree_unlock(mt); + return ret; +} +EXPORT_SYMBOL(mtree_alloc_cyclic); + int mtree_alloc_rrange(struct maple_tree *mt, unsigned long *startp, void *entry, unsigned long size, unsigned long min, unsigned long max, gfp_t gfp) From patchwork Sat Feb 17 20:24:08 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chuck Lever X-Patchwork-Id: 202704 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:693c:2685:b0:108:e6aa:91d0 with SMTP id mn5csp495504dyc; Sat, 17 Feb 2024 12:27:06 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCU7oJTirVsRMcVgLNFP+vZ/Wo4tSqUKRQ2OxSFGNvGQN85KDlrFqZ13ycZnCSh9iwDJo9giownL006/oom+vDgTxpAZtA== X-Google-Smtp-Source: AGHT+IGvZu9GFaanTiy7bqgtDl3mxl1Xwn15lqWlyMrlFLFL2ZKBB6FOLXeUE1m8Om+RRo8ayVhv X-Received: by 2002:a05:6e02:108f:b0:363:bdb9:72af with SMTP id r15-20020a056e02108f00b00363bdb972afmr5663336ilj.23.1708201626416; Sat, 17 Feb 2024 12:27:06 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1708201626; cv=pass; d=google.com; s=arc-20160816; b=OL4w4vy8XRGu6XkS4qmeB1WVuNxNnVJG9rnoEw+gNXIViJXlgtM9UO+Ssm4V/vrQ/q fkwlJ31sQYvYa9PFlvQ2QAmOM4u5yYd4EKCcusJVjop8s9aP206Lq7cW+1p+tZavz/lt vN8s2/IH3HnYY4A47P2AmuPUoEivG5AGF/6gzPBEPXZhYS7B1s+5imRADsD9GRJ5w5ja Tj9tmabQYJ5ype4nJi4fO3IH8+Vm5eYj/TQtg2mKCx5L0lSebTZfEnRgfrVTPa0w0Zpk IQSvX4GKlS6Ef0MusDVg0n51PWAEC8/5oZl+Gz+SVWp/pHaCFD4sbHy6Nn5zbrEEXv2P HRNQ== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:user-agent:references:in-reply-to :message-id:date:cc:to:from:subject:dkim-signature; bh=dH9/7pSMHgIoq16nk50EO6AL6CLhc0Zg3gckgnzjmrE=; fh=0JMhqiWEaK+qw2xgbbey7OsRaoj7Z6cFR6nhiwhAbe0=; b=GxiyEj1/63CqIOJp06X1YAEHmoDsYuk+Z3SaXOKfoKdT6wQgnYVVEQyUonXYGQEixx DKWFBDZCwJqd668dqcG0/CjSS02gGAsCyImihv82UGJikvwVbcOHIZtRUuFs49QKKh5D lF12UW889QGGb51Z18JxjfsT7e8KGNFyh1ckdAAJhGzgBzcK/UsUDtCse/P8VI/+mrAb j7h/uQcXEtLLcpZdOVkHgtOe9a/9gFnAiSZ803mTKR2RbgoQxAHMkzRN7Y7qGPni59BZ OJMp+zVj/QmKlwVC1ubnzejOfbeIzx9YHXqRAA53oXpNlTg9NWCMwF+UW9cxiB/LStjO w3oA==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b="O/VgTJ4c"; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70072-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70072-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from sv.mirrors.kernel.org (sv.mirrors.kernel.org. [2604:1380:45e3:2400::1]) by mx.google.com with ESMTPS id a65-20020a639044000000b005dc8372020esi1902767pge.580.2024.02.17.12.27.06 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Feb 2024 12:27:06 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-70072-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) client-ip=2604:1380:45e3:2400::1; Authentication-Results: mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b="O/VgTJ4c"; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70072-ouuuleilei=gmail.com@vger.kernel.org designates 2604:1380:45e3:2400::1 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70072-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by sv.mirrors.kernel.org (Postfix) with ESMTPS id EF7C528607C for ; Sat, 17 Feb 2024 20:25:46 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id DB6BC7FBDB; Sat, 17 Feb 2024 20:24:13 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="O/VgTJ4c" Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 5DC567FBAC; Sat, 17 Feb 2024 20:24:11 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201451; cv=none; b=m9OenjuRKdhYD1E0hCKuD9WzFBYc6CfKQ3mGftdizUFIAJo7VJoS3CIhp3haM9CZhk7ldLE4F9RBk3n72+phF7uilnh6dvngnLbHgkmwN60bJR33LMJUM2YkeyRB0QCD8R+5VyRAeaFWtI/eRUUanUbaNchNobzheoqPfnsI8Do= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201451; c=relaxed/simple; bh=r6dLn2R32hxUVKrwHaR6P90sYMJO3HfuXaP1srQuHsY=; h=Subject:From:To:Cc:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=lGeq762d7q8FXyZEDTlesMwDnrPM9wgHfW9GsjYa69R/XDIHhI3VQn7JDk5eF+GEsmRjqDsQb5Jtz+jc2aLGfWWOvKRyCm/2RIya7HpmW2ZFq5Z5lJ3D4QvJxpNVFBng0ooKBQkkV8LLSek/OgHIfHy0VnVv/VSS8QrE4sjdW8s= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=O/VgTJ4c; arc=none smtp.client-ip=10.30.226.201 Received: by smtp.kernel.org (Postfix) with ESMTPSA id E7B52C433C7; Sat, 17 Feb 2024 20:24:09 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1708201451; bh=r6dLn2R32hxUVKrwHaR6P90sYMJO3HfuXaP1srQuHsY=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=O/VgTJ4chu/g5D0kuQ6IwQrqk6Yged1gYNOnPpILQjot3IwuwxhS0tjBHhH+sQ2Kz Zxyb7DTRLGPN4oi1a1lmsh4iMS7n4x8eU7JR4n/7kJCgHm31IjaEMLd1aj3WKlJZTI cWR5pWetfkjmwe/CpCU4IWr+5zr/kolzJq/4IHeq53kuEhX7f+Lj34sgVaaCR9TUTA WqRRhpu5EBPzA0IeI1/a8ljmj1zl5QVpNFm6gr31iF/Lh2h1sWihqI5TErBNv7U0Gl nkriuby+Se6wuvehqDAuLb9N0LS2Jbw55eloingd6OQJgzmXnWAbWh+8Yghq/aV+hZ 9cHhYH/qLF81Q== Subject: [PATCH v2 5/6] test_maple_tree: testing the cyclic allocation From: Chuck Lever To: viro@zeniv.linux.org.uk, brauner@kernel.org, jack@suse.cz, hughd@google.com, akpm@linux-foundation.org, Liam.Howlett@oracle.com, oliver.sang@intel.com, feng.tang@intel.com Cc: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, lkp@intel.com Date: Sat, 17 Feb 2024 15:24:08 -0500 Message-ID: <170820144894.6328.13052830860966450674.stgit@91.116.238.104.host.secureserver.net> In-Reply-To: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> References: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> User-Agent: StGit/1.5 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1791179228733666160 X-GMAIL-MSGID: 1791179228733666160 From: Liam R. Howlett This tests the interactions of the cyclic allocations, the maple state index and last, and overflow. Signed-off-by: Liam R. Howlett Signed-off-by: Chuck Lever --- lib/test_maple_tree.c | 44 ++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 44 insertions(+) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 29185ac5c727..399380db449c 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -3599,6 +3599,45 @@ static noinline void __init check_state_handling(struct maple_tree *mt) mas_unlock(&mas); } +static noinline void __init alloc_cyclic_testing(struct maple_tree *mt) +{ + unsigned long location; + unsigned long next; + int ret = 0; + MA_STATE(mas, mt, 0, 0); + + next = 0; + mtree_lock(mt); + for (int i = 0; i < 100; i++) { + mas_alloc_cyclic(&mas, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); + MAS_BUG_ON(&mas, i != location - 2); + MAS_BUG_ON(&mas, mas.index != location); + MAS_BUG_ON(&mas, mas.last != location); + MAS_BUG_ON(&mas, i != next - 3); + } + + mtree_unlock(mt); + mtree_destroy(mt); + next = 0; + mt_init_flags(mt, MT_FLAGS_ALLOC_RANGE); + for (int i = 0; i < 100; i++) { + mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); + MT_BUG_ON(mt, i != location - 2); + MT_BUG_ON(mt, i != next - 3); + MT_BUG_ON(mt, mtree_load(mt, location) != mt); + } + + mtree_destroy(mt); + /* Overflow test */ + next = ULONG_MAX - 1; + ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); + MT_BUG_ON(mt, ret != 0); + ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); + MT_BUG_ON(mt, ret != 0); + ret = mtree_alloc_cyclic(mt, &location, mt, 2, ULONG_MAX, &next, GFP_KERNEL); + MT_BUG_ON(mt, ret != 1); +} + static DEFINE_MTREE(tree); static int __init maple_tree_seed(void) { @@ -3880,6 +3919,11 @@ static int __init maple_tree_seed(void) check_state_handling(&tree); mtree_destroy(&tree); + mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); + alloc_cyclic_testing(&tree); + mtree_destroy(&tree); + + #if defined(BENCH) skip: #endif From patchwork Sat Feb 17 20:24:16 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Chuck Lever X-Patchwork-Id: 202702 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:693c:2685:b0:108:e6aa:91d0 with SMTP id mn5csp495267dyc; Sat, 17 Feb 2024 12:26:09 -0800 (PST) X-Forwarded-Encrypted: i=3; AJvYcCUXI7upLVrk4sQdgaudyNnKBT2hlefrf8WTMj096M3Mtu85RnraKCRctIgU92izx41we1flNmxkk/wOOJIi7OmdVU4RnA== X-Google-Smtp-Source: AGHT+IHhqQLoiNYg3i1mjYMkadohsaxbWQFzvG2Bv2YwjQAvGL/zyZ9JVhsIn4DIHizjC3mMLkjT X-Received: by 2002:a2e:9207:0:b0:2d1:e53:cede with SMTP id k7-20020a2e9207000000b002d10e53cedemr5277061ljg.25.1708201569511; Sat, 17 Feb 2024 12:26:09 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1708201569; cv=pass; d=google.com; s=arc-20160816; b=TNfTcZ94SVoxtC32UNoIobWgIhoSbwu2beyR+1QCByjAhoI+5EH37Z9aoeCTwpNU1+ Tq8bg5qyCmre96JBmbQEPT29FX81qndsbb6PCmLwicEUlikyJzaY6Ukyvl7ZecJuhEBp ddXu/CNIC6m4WR9X2xO7U7gg3sYSmvUobfi+lEHB6d0Q+KOZyrkzcQmpKrYogaC3iEsQ VTzgux+4sfNRhLbP2pQPqx+MsAQMzTtY4MqxzPdUlHMhk0UymAcLULkPg4Y7Z88uF3KL xNki8c/eVI0LyPim+eOsZ+yR3P9zX/GRuVlb6gc6FpYz+BPzOBknc22PnzaosXOue4I2 UM0w== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=content-transfer-encoding:mime-version:list-unsubscribe :list-subscribe:list-id:precedence:user-agent:references:in-reply-to :message-id:date:cc:to:from:subject:dkim-signature; bh=enSJEC+a309h9BZDKMG+FAfIIaZiXnFN47ab++juM4Y=; fh=0JMhqiWEaK+qw2xgbbey7OsRaoj7Z6cFR6nhiwhAbe0=; b=weUFT64+kPJL7yclvkL28o1v5sX2mTtQXfgfDxR7gOAHy6tQ5WSXra5Y/R9aFos5/n i0jZd+1YNs9Hv+68KiesuUNmtJWmlXIfwevdlZd60E6ratzM1+twJ7VkSpr4hHILvy5T InrFsvQmo15410rcTFIddh/sZ89/PYt2TimefU0kTScHpLWoHsin3X1lcQKQNBLCWToN MHNNh5f1RGzA3njEJ3hCwJimRNkCRS5cxUH2fdRkhhnBsH8U5RLd0TZP8+J7ON+bIc8o hM0L2uf+g62wF+pEc2BYpc9ifeLTXLfBlnBnCzE1nlrrlSAOobCUo+r6zg80TElJ6NdG yC+Q==; dara=google.com ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=Hily6QXJ; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70073-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70073-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from am.mirrors.kernel.org (am.mirrors.kernel.org. [147.75.80.249]) by mx.google.com with ESMTPS id e15-20020a056402190f00b0055eba1df579si1020243edz.571.2024.02.17.12.26.09 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Sat, 17 Feb 2024 12:26:09 -0800 (PST) Received-SPF: pass (google.com: domain of linux-kernel+bounces-70073-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) client-ip=147.75.80.249; Authentication-Results: mx.google.com; dkim=pass header.i=@kernel.org header.s=k20201202 header.b=Hily6QXJ; arc=pass (i=1 dkim=pass dkdomain=kernel.org); spf=pass (google.com: domain of linux-kernel+bounces-70073-ouuuleilei=gmail.com@vger.kernel.org designates 147.75.80.249 as permitted sender) smtp.mailfrom="linux-kernel+bounces-70073-ouuuleilei=gmail.com@vger.kernel.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=kernel.org Received: from smtp.subspace.kernel.org (wormhole.subspace.kernel.org [52.25.139.140]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by am.mirrors.kernel.org (Postfix) with ESMTPS id B4CCE1F22E00 for ; Sat, 17 Feb 2024 20:26:08 +0000 (UTC) Received: from localhost.localdomain (localhost.localdomain [127.0.0.1]) by smtp.subspace.kernel.org (Postfix) with ESMTP id A7DA780046; Sat, 17 Feb 2024 20:24:21 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b="Hily6QXJ" Received: from smtp.kernel.org (aws-us-west-2-korg-mail-1.web.codeaurora.org [10.30.226.201]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 7F5FA80023; Sat, 17 Feb 2024 20:24:18 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=10.30.226.201 ARC-Seal: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201458; cv=none; b=gxHiluEMCQILcZhIaIvXmPDF/MTLgDpW3Ynyle2KH28RnrXdj+ZlvDI88QuekBRdAffshdtcqQfFuGQMS3jPwSROT5tpGpDL8NXWJzmeb8rs8Tx5O2D1l+H1XDQakGESTPjKRw2o96Y7HSdoOvgydQu8mx/yohWeTmguTkWiC5Q= ARC-Message-Signature: i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708201458; c=relaxed/simple; bh=iJhBU4UKeak6qEJexG79zX3vwwtlWw+1xSLFESXosd8=; h=Subject:From:To:Cc:Date:Message-ID:In-Reply-To:References: MIME-Version:Content-Type; b=oOHgiYrqAKDsntUswNfF0uoi4Bptihcfbg9iShFFAaughyzB5nfWg7H2iHzQKdVZQVM/A/uUstxCrVZG7qUjqUav7HB1TTkoLRi2ngNNx+K3rzQ1+ByufZJFItsILM8JJ3WBZeybJhA0ggG6RVeamsOA0B/4xGZxqOfraXIYFBs= ARC-Authentication-Results: i=1; smtp.subspace.kernel.org; dkim=pass (2048-bit key) header.d=kernel.org header.i=@kernel.org header.b=Hily6QXJ; arc=none smtp.client-ip=10.30.226.201 Received: by smtp.kernel.org (Postfix) with ESMTPSA id 1B1A2C433F1; Sat, 17 Feb 2024 20:24:17 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=kernel.org; s=k20201202; t=1708201458; bh=iJhBU4UKeak6qEJexG79zX3vwwtlWw+1xSLFESXosd8=; h=Subject:From:To:Cc:Date:In-Reply-To:References:From; b=Hily6QXJZ3MvOQfoHfmflOHSKjso6T7su5pOg1uRjgLZmE6bAK8Lyq/uERlhPLE6t sX2yH/nhAs6Ss3kB2NDRWijgMg9D+5/x3WC+AeJxc4pcG5reGPcPo6z8xuAWCuOWOI Ve02Le0hloVNEKIKxliDpYgSi+MVDE33yPWaXwDbMyrBVYu1c1ly4yey/kR9SxpuYM mpDRY6f9LSwab7UCGnvQvL/WFnHXaCg+vVXWzlMIdHBJy8j6lccu1EowhuPknUYwuw 9OXU/VwaeYJHMptnia1WNs5QVLPJhBk6e07ogG7mlf/U7xZRkhz9IJgiQxgzpSwjib TXq/fl/0XvXHg== Subject: [PATCH v2 6/6] libfs: Convert simple directory offsets to use a Maple Tree From: Chuck Lever To: viro@zeniv.linux.org.uk, brauner@kernel.org, jack@suse.cz, hughd@google.com, akpm@linux-foundation.org, Liam.Howlett@oracle.com, oliver.sang@intel.com, feng.tang@intel.com Cc: linux-kernel@vger.kernel.org, linux-fsdevel@vger.kernel.org, maple-tree@lists.infradead.org, linux-mm@kvack.org, lkp@intel.com Date: Sat, 17 Feb 2024 15:24:16 -0500 Message-ID: <170820145616.6328.12620992971699079156.stgit@91.116.238.104.host.secureserver.net> In-Reply-To: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> References: <170820083431.6328.16233178852085891453.stgit@91.116.238.104.host.secureserver.net> User-Agent: StGit/1.5 Precedence: bulk X-Mailing-List: linux-kernel@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1791179168767480465 X-GMAIL-MSGID: 1791179168767480465 From: Chuck Lever Test robot reports: > kernel test robot noticed a -19.0% regression of aim9.disk_src.ops_per_sec on: > > commit: a2e459555c5f9da3e619b7e47a63f98574dc75f1 ("shmem: stable directory offsets") > https://git.kernel.org/cgit/linux/kernel/git/torvalds/linux.git master Feng Tang further clarifies that: > ... the new simple_offset_add() > called by shmem_mknod() brings extra cost related with slab, > specifically the 'radix_tree_node', which cause the regression. Willy's analysis is that, over time, the test workload causes xa_alloc_cyclic() to fragment the underlying SLAB cache. This patch replaces the offset_ctx's xarray with a Maple Tree in the hope that Maple Tree's dense node mode will handle this scenario more scalably. In addition, we can widen the simple directory offset maximum to signed long (as loff_t is also signed). Suggested-by: Matthew Wilcox Reported-by: kernel test robot Closes: https://lore.kernel.org/oe-lkp/202309081306.3ecb3734-oliver.sang@intel.com Signed-off-by: Chuck Lever Reviewed-by: Jan Kara --- fs/libfs.c | 47 +++++++++++++++++++++++------------------------ include/linux/fs.h | 5 +++-- 2 files changed, 26 insertions(+), 26 deletions(-) diff --git a/fs/libfs.c b/fs/libfs.c index f7f92a49a418..d3d31197c8e4 100644 --- a/fs/libfs.c +++ b/fs/libfs.c @@ -245,17 +245,17 @@ enum { DIR_OFFSET_MIN = 2, }; -static void offset_set(struct dentry *dentry, u32 offset) +static void offset_set(struct dentry *dentry, long offset) { - dentry->d_fsdata = (void *)((uintptr_t)(offset)); + dentry->d_fsdata = (void *)offset; } -static u32 dentry2offset(struct dentry *dentry) +static long dentry2offset(struct dentry *dentry) { - return (u32)((uintptr_t)(dentry->d_fsdata)); + return (long)dentry->d_fsdata; } -static struct lock_class_key simple_offset_xa_lock; +static struct lock_class_key simple_offset_lock_class; /** * simple_offset_init - initialize an offset_ctx @@ -264,8 +264,8 @@ static struct lock_class_key simple_offset_xa_lock; */ void simple_offset_init(struct offset_ctx *octx) { - xa_init_flags(&octx->xa, XA_FLAGS_ALLOC1); - lockdep_set_class(&octx->xa.xa_lock, &simple_offset_xa_lock); + mt_init_flags(&octx->mt, MT_FLAGS_ALLOC_RANGE); + lockdep_set_class(&octx->mt.ma_lock, &simple_offset_lock_class); octx->next_offset = DIR_OFFSET_MIN; } @@ -274,20 +274,19 @@ void simple_offset_init(struct offset_ctx *octx) * @octx: directory offset ctx to be updated * @dentry: new dentry being added * - * Returns zero on success. @so_ctx and the dentry offset are updated. + * Returns zero on success. @octx and the dentry's offset are updated. * Otherwise, a negative errno value is returned. */ int simple_offset_add(struct offset_ctx *octx, struct dentry *dentry) { - static const struct xa_limit limit = XA_LIMIT(DIR_OFFSET_MIN, U32_MAX); - u32 offset; + unsigned long offset; int ret; if (dentry2offset(dentry) != 0) return -EBUSY; - ret = xa_alloc_cyclic(&octx->xa, &offset, dentry, limit, - &octx->next_offset, GFP_KERNEL); + ret = mtree_alloc_cyclic(&octx->mt, &offset, dentry, DIR_OFFSET_MIN, + LONG_MAX, &octx->next_offset, GFP_KERNEL); if (ret < 0) return ret; @@ -303,13 +302,13 @@ int simple_offset_add(struct offset_ctx *octx, struct dentry *dentry) */ void simple_offset_remove(struct offset_ctx *octx, struct dentry *dentry) { - u32 offset; + long offset; offset = dentry2offset(dentry); if (offset == 0) return; - xa_erase(&octx->xa, offset); + mtree_erase(&octx->mt, offset); offset_set(dentry, 0); } @@ -332,7 +331,7 @@ int simple_offset_empty(struct dentry *dentry) index = DIR_OFFSET_MIN; octx = inode->i_op->get_offset_ctx(inode); - xa_for_each(&octx->xa, index, child) { + mt_for_each(&octx->mt, child, index, LONG_MAX) { spin_lock(&child->d_lock); if (simple_positive(child)) { spin_unlock(&child->d_lock); @@ -362,8 +361,8 @@ int simple_offset_rename_exchange(struct inode *old_dir, { struct offset_ctx *old_ctx = old_dir->i_op->get_offset_ctx(old_dir); struct offset_ctx *new_ctx = new_dir->i_op->get_offset_ctx(new_dir); - u32 old_index = dentry2offset(old_dentry); - u32 new_index = dentry2offset(new_dentry); + long old_index = dentry2offset(old_dentry); + long new_index = dentry2offset(new_dentry); int ret; simple_offset_remove(old_ctx, old_dentry); @@ -389,9 +388,9 @@ int simple_offset_rename_exchange(struct inode *old_dir, out_restore: offset_set(old_dentry, old_index); - xa_store(&old_ctx->xa, old_index, old_dentry, GFP_KERNEL); + mtree_store(&old_ctx->mt, old_index, old_dentry, GFP_KERNEL); offset_set(new_dentry, new_index); - xa_store(&new_ctx->xa, new_index, new_dentry, GFP_KERNEL); + mtree_store(&new_ctx->mt, new_index, new_dentry, GFP_KERNEL); return ret; } @@ -404,7 +403,7 @@ int simple_offset_rename_exchange(struct inode *old_dir, */ void simple_offset_destroy(struct offset_ctx *octx) { - xa_destroy(&octx->xa); + mtree_destroy(&octx->mt); } /** @@ -434,16 +433,16 @@ static loff_t offset_dir_llseek(struct file *file, loff_t offset, int whence) /* In this case, ->private_data is protected by f_pos_lock */ file->private_data = NULL; - return vfs_setpos(file, offset, U32_MAX); + return vfs_setpos(file, offset, LONG_MAX); } static struct dentry *offset_find_next(struct offset_ctx *octx, loff_t offset) { + MA_STATE(mas, &octx->mt, offset, offset); struct dentry *child, *found = NULL; - XA_STATE(xas, &octx->xa, offset); rcu_read_lock(); - child = xas_next_entry(&xas, U32_MAX); + child = mas_find(&mas, LONG_MAX); if (!child) goto out; spin_lock(&child->d_lock); @@ -457,8 +456,8 @@ static struct dentry *offset_find_next(struct offset_ctx *octx, loff_t offset) static bool offset_dir_emit(struct dir_context *ctx, struct dentry *dentry) { - u32 offset = dentry2offset(dentry); struct inode *inode = d_inode(dentry); + long offset = dentry2offset(dentry); return ctx->actor(ctx, dentry->d_name.name, dentry->d_name.len, offset, inode->i_ino, fs_umode_to_dtype(inode->i_mode)); diff --git a/include/linux/fs.h b/include/linux/fs.h index 03d141809a2c..55144c12ee0f 100644 --- a/include/linux/fs.h +++ b/include/linux/fs.h @@ -43,6 +43,7 @@ #include #include #include +#include #include #include @@ -3260,8 +3261,8 @@ extern ssize_t simple_write_to_buffer(void *to, size_t available, loff_t *ppos, const void __user *from, size_t count); struct offset_ctx { - struct xarray xa; - u32 next_offset; + struct maple_tree mt; + unsigned long next_offset; }; void simple_offset_init(struct offset_ctx *octx);