From patchwork Fri Dec 15 22:03:45 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 10116249 Return-Path: Received: from mail.wl.linuxfoundation.org (pdx-wl-mail.web.codeaurora.org [172.30.200.125]) by pdx-korg-patchwork.web.codeaurora.org (Postfix) with ESMTP id 721D96019C for ; Fri, 15 Dec 2017 22:15:07 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 62BC429D7C for ; Fri, 15 Dec 2017 22:15:07 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 55BFC2A1B7; Fri, 15 Dec 2017 22:15:07 +0000 (UTC) X-Spam-Checker-Version: SpamAssassin 3.3.1 (2010-03-16) on pdx-wl-mail.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-6.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, RCVD_IN_DNSWL_HI,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id A8BB529D7C for ; Fri, 15 Dec 2017 22:15:06 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S932691AbdLOWPE (ORCPT ); Fri, 15 Dec 2017 17:15:04 -0500 Received: from bombadil.infradead.org ([65.50.211.133]:39861 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1755972AbdLOWFa (ORCPT ); Fri, 15 Dec 2017 17:05:30 -0500 DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=References:In-Reply-To:Message-Id: Date:Subject:Cc:To:From:Sender:Reply-To:MIME-Version:Content-Type: Content-Transfer-Encoding:Content-ID:Content-Description:Resent-Date: Resent-From:Resent-Sender:Resent-To:Resent-Cc:Resent-Message-ID:List-Id: List-Help:List-Unsubscribe:List-Subscribe:List-Post:List-Owner:List-Archive; bh=bPInS0mdJcIklE9LE5q9S3CpTS2pu9XpJMN63/RdUtU=; b=Ty16q4OnnHLpfoxr6JR1iHxXG GByl6BtfYEnagtapgGvInN4WIxCne3Lze7C2c4FGTskAmfjSFcTDb2ZIjMnaU1OOn3DhFZ1WHzazA f361gqkcTorj2awYHwRfDnS0aEv99WjT0WHeNzRCXkXMzUetNIaWO+KlFCqlovjJX/u+kwRKWXSrD BIIoqztdjrr+6Go1IQuuutFS0nYZzmus8H0sJezeYETgg3Qnse0Ld3u3GvV6JA1F432vnfpSe567T RYDGX3QSvcAzTULPTCg+B5MFp7hgK3VIGXcpOKebEq6o9F6hjbc9xWvhiqpfA80t0EObvdengd94t TKwlFKgww==; Received: from willy by bombadil.infradead.org with local (Exim 4.87 #1 (Red Hat Linux)) id 1ePy6F-00025y-PF; Fri, 15 Dec 2017 22:04:59 +0000 From: Matthew Wilcox To: linux-kernel@vger.kernel.org Cc: Matthew Wilcox , Ross Zwisler , David Howells , Shaohua Li , Jens Axboe , Rehas Sachdeva , Marc Zyngier , linux-mm@kvack.org, linux-fsdevel@vger.kernel.org, linux-f2fs-devel@lists.sourceforge.net, linux-nilfs@vger.kernel.org, linux-btrfs@vger.kernel.org, linux-xfs@vger.kernel.org, linux-usb@vger.kernel.org, linux-raid@vger.kernel.org Subject: [PATCH v5 13/78] xarray: Add xa_cmpxchg Date: Fri, 15 Dec 2017 14:03:45 -0800 Message-Id: <20171215220450.7899-14-willy@infradead.org> X-Mailer: git-send-email 2.9.5 In-Reply-To: <20171215220450.7899-1-willy@infradead.org> References: <20171215220450.7899-1-willy@infradead.org> Sender: linux-btrfs-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-btrfs@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP From: Matthew Wilcox This works like doing cmpxchg() on an array entry. Code which wants the radix_tree_insert() semantic of not overwriting an existing entry can cmpxchg() with NULL and get the action it wants. Plus, instead of having an error returned, they get the value currently stored in the array, which often saves them a subsequent lookup. Signed-off-by: Matthew Wilcox --- include/linux/xarray.h | 33 +++++++++++++++++++++++++ lib/xarray.c | 65 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 98 insertions(+) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 05873095bc7f..56db23edac82 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -75,6 +75,8 @@ static inline void xa_init(struct xarray *xa) void *xa_load(struct xarray *, unsigned long index); void *xa_store(struct xarray *, unsigned long index, void *entry, gfp_t); +void *xa_cmpxchg(struct xarray *, unsigned long index, + void *old, void *entry, gfp_t); /** * xa_erase() - Erase this entry from the XArray. @@ -216,6 +218,32 @@ static inline int xa_err(void *entry) return 0; } +/** + * xa_store_empty() - Store this entry in the XArray unless another entry is + * already present. + * @xa: XArray. + * @index: Index into array. + * @entry: New entry. + * @gfp: Memory allocation flags. + * + * If you would rather see the existing entry in the array, use xa_cmpxchg(). + * This function is for users who don't care what the entry is, only that + * one is present. + * + * Return: -EEXIST if another entry was present, 0 if the store succeeded, + * or another negative errno if a different error happened (eg -ENOMEM). + */ +static inline int xa_store_empty(struct xarray *xa, unsigned long index, + void *entry, gfp_t gfp) +{ + void *curr = xa_cmpxchg(xa, index, NULL, entry, gfp); + if (!curr) + return 0; + if (xa_is_err(curr)) + return xa_err(curr); + return -EEXIST; +} + #define xa_trylock(xa) spin_trylock(&(xa)->xa_lock) #define xa_lock(xa) spin_lock(&(xa)->xa_lock) #define xa_unlock(xa) spin_unlock(&(xa)->xa_lock) @@ -242,9 +270,14 @@ enum xa_ctx { void *__xa_erase(struct xarray *, unsigned long index); void *___xa_store(struct xarray *, unsigned long index, void *entry, gfp_t, enum xa_ctx); +void *___xa_cmpxchg(struct xarray *, unsigned long index, void *old, + void *entry, gfp_t, enum xa_ctx); #define __xa_store(x, i, e, g) ___xa_store(x, i, e, g, XA_CTX_PRC) #define __xa_store_bh(x, i, e, g) ___xa_store(x, i, e, g, XA_CTX_BH) #define __xa_store_irq(x, i, e, g) ___xa_store(x, i, e, g, XA_CTX_IRQ) +#define __xa_cmpxchg(x, i, o, e, g) ___xa_cmpxchg(x, i, o, e, g, XA_CTX_PRC) +#define __xa_cmpxchg_bh(x, i, o, e, g) ___xa_cmpxchg(x, i, o, e, g, XA_CTX_BH) +#define __xa_cmpxchg_irq(x, i, o, e, g) ___xa_cmpxchg(x, i, o, e, g, XA_CTX_IRQ) void __xa_set_tag(struct xarray *, unsigned long index, xa_tag_t); void __xa_clear_tag(struct xarray *, unsigned long index, xa_tag_t); diff --git a/lib/xarray.c b/lib/xarray.c index 64f88ce23392..ef3340471e5c 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -921,6 +921,71 @@ void *___xa_store(struct xarray *xa, unsigned long index, void *entry, } EXPORT_SYMBOL(___xa_store); +/** + * xa_cmpxchg() - Conditionally replace an entry in the XArray. + * @xa: XArray. + * @index: Index into array. + * @old: Old value to test against. + * @entry: New value to place in array. + * @gfp: Allocation flags. + * + * If the entry at @index is the same as @old, replace it with @entry. + * If the return value is equal to @old, then the exchange was successful. + * + * Return: The old value at this index or xa_err() if an error happened. + */ +void *xa_cmpxchg(struct xarray *xa, unsigned long index, + void *old, void *entry, gfp_t gfp) +{ + XA_STATE(xas, xa, index); + void *curr; + + if (WARN_ON_ONCE(xa_is_internal(entry))) + return XA_ERROR(-EINVAL); + + do { + xas_lock(&xas); + curr = xas_create(&xas); + if (curr == old) + xas_store(&xas, entry); + xas_unlock(&xas); + } while (xas_nomem(&xas, gfp)); + + return xas_result(&xas, curr); +} +EXPORT_SYMBOL(xa_cmpxchg); + +/* + * ___xa_cmpxchg() - Store this entry in the XArray. + * @xa: XArray. + * @index: Index into array. + * @entry: New entry. + * @gfp: Allocation flags. + * @lock_type: Lock acquisition type. + * + * Internal implementation detail. + * + * Return: The old entry at this index or xa_err() if an error happened. + */ +void *___xa_cmpxchg(struct xarray *xa, unsigned long index, + void *old, void *entry, gfp_t gfp, enum xa_ctx ctx) +{ + XA_STATE(xas, xa, index); + void *curr; + + if (WARN_ON_ONCE(xa_is_internal(entry))) + return XA_ERROR(-EINVAL); + + do { + curr = xas_create(&xas); + if (curr == old) + xas_store(&xas, entry); + } while (__xas_nomem(&xas, gfp, ctx)); + + return xas_result(&xas, curr); +} +EXPORT_SYMBOL(___xa_cmpxchg); + /** * __xa_set_tag() - Set this tag on this entry while locked. * @xa: XArray.