From patchwork Mon Jun 11 14:05:38 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 10457863 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 E59B26020F for ; Mon, 11 Jun 2018 14:07:13 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id D2CE028451 for ; Mon, 11 Jun 2018 14:07:13 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id C58BD2846F; Mon, 11 Jun 2018 14:07:13 +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=-2.8 required=2.0 tests=BAYES_00,DKIM_SIGNED, MAILING_LIST_MULTI,RCVD_IN_DNSWL_NONE,T_DKIM_INVALID autolearn=ham version=3.3.1 Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 04F8528451 for ; Mon, 11 Jun 2018 14:07:13 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 8103E6B000E; Mon, 11 Jun 2018 10:06:47 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 7245C6B026E; Mon, 11 Jun 2018 10:06:47 -0400 (EDT) X-Original-To: int-list-linux-mm@kvack.org X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 154226B000A; Mon, 11 Jun 2018 10:06:46 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pg0-f71.google.com (mail-pg0-f71.google.com [74.125.83.71]) by kanga.kvack.org (Postfix) with ESMTP id 75E126B0266 for ; Mon, 11 Jun 2018 10:06:46 -0400 (EDT) Received: by mail-pg0-f71.google.com with SMTP id i12-v6so3634577pgt.13 for ; Mon, 11 Jun 2018 07:06:46 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:dkim-signature:from:to:cc:subject:date :message-id:in-reply-to:references; bh=GWcO8qHo0kt3ntl8a5jR2Ne+3gIMw/C9E24POVCTyQY=; b=fGGe//fYQWGsb33rpWuCfEOIvDoXHGqtFH7Ueh+lKDkz1vh1J+PZd2eHb5v8vDwHmi dtSUhdQ6dRmy6yIKLndmlsWkNevDmRkOzXn5pksEXugKT8rZOH1WumhaXVu+mP19nDRt kFej/YDBnLOEPHrQCRCw5bYuANI0ZkCA2tFp+XIC3ee6DTK55wAxGnhstTc/2JZ65zZb rtO4DS11YSzCCUthU5ZLw23B4ncObSElJdlGoZB1aHFP8KDNtu5WUHzuPtQzS1kZbCZv SrUpvrq8s15ct7snCJpZRJUJzRxQluOgrCGKwRMElvhgJ5mUw2xTjsjZ/GN0ihxZXCIA SwOw== X-Gm-Message-State: APt69E1RZu+y5i6CN7tQ8QHCj7l1gtos4yPwE8hxhXVn2++lMulkoXLG oyKTEjI4Tm2coFBksZ3BKYntDODHHi88yWa0irsWaXe7j+QU8gFBflG3/Nh1O2ZQVpqRvQFiDGi t/IyKkN5jz1cSnJlT8r42qMuXeQsLSFuh+b1ttcZuD1Hpj2ISSxkb1jgdDGxRGQh6nw== X-Received: by 2002:a65:5a07:: with SMTP id y7-v6mr14628900pgs.177.1528726006123; Mon, 11 Jun 2018 07:06:46 -0700 (PDT) X-Google-Smtp-Source: ADUXVKLwn7dRbhebG/vYyR0H3lIIb7Yel3H08fvZW3GulLkNP/QYRc56juzztC1KbXvl/4quIQsX X-Received: by 2002:a65:5a07:: with SMTP id y7-v6mr14628823pgs.177.1528726004812; Mon, 11 Jun 2018 07:06:44 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1528726004; cv=none; d=google.com; s=arc-20160816; b=yJTeBz9+Yk/onuaO1f0RFUQUQ9In81kiTUNJv3ykFTrpyfg5K2IjGaGYouTvMRH2Cw usaWQXbE9BEzS9j+cWRPzOvHOu9CDQxGnJamFtUDfuEQjWLVWeEZJQJxlPwxMGbMugTq rSS/YjBEJjuZhOss6BGWUx6W0mr7RQbMtR7l3TndFdBlOu41z+l+hnlWyj/Lj8l1Ka0w l82mQMMGT4Gc7s+HQP6WnDpMGA/ABwuBgInhYytiqGEElC/dDBuKQMyxov0+EHtyZZzv 7JquJs2rFyPL9DmwqdtsfoUujXh0A2QAl11gypgB7o8b3m7coIh0W2zenWNE/1jaClmB +ZMQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=references:in-reply-to:message-id:date:subject:cc:to:from :dkim-signature:arc-authentication-results; bh=GWcO8qHo0kt3ntl8a5jR2Ne+3gIMw/C9E24POVCTyQY=; b=TQQ/qR2cOrBwIFWGUl/p1i32DrKaf2KMCZ9PC7iiHdSnLlbisseGxm2C9ptzs9Rfr0 xiVtU3j/ARsFmD+V3N9dqbKmc9t675XlnSFg7x0AadgH5V4/o6HrJVsrrk9VmtBOlBFL 5qHVlCZb6OD5JySCWuPJv5+ZBVa0OuWghViAYcOoiFaSf5WbjbdMV0WMJHaBx2h5/FXn S2rwXyo1pWbwIn5KsLgaYg7DARiDaY1kpzhJBLAlccKUYvLZAg+3H+WuxPV2UfM6oKQ8 gi/7pzpHP3jSbr0UXSqUb5hvrqtruRhYQWURwRNhiyO6Shf/fgIdPN5d/AHCKi8hzQ7W g4tg== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@infradead.org header.s=bombadil.20170209 header.b=GioKHzFj; spf=pass (google.com: best guess record for domain of willy@infradead.org designates 2607:7c80:54:e::133 as permitted sender) smtp.mailfrom=willy@infradead.org Received: from bombadil.infradead.org (bombadil.infradead.org. [2607:7c80:54:e::133]) by mx.google.com with ESMTPS id m6-v6si29915874pgt.636.2018.06.11.07.06.44 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 11 Jun 2018 07:06:44 -0700 (PDT) Received-SPF: pass (google.com: best guess record for domain of willy@infradead.org designates 2607:7c80:54:e::133 as permitted sender) client-ip=2607:7c80:54:e::133; Authentication-Results: mx.google.com; dkim=pass header.i=@infradead.org header.s=bombadil.20170209 header.b=GioKHzFj; spf=pass (google.com: best guess record for domain of willy@infradead.org designates 2607:7c80:54:e::133 as permitted sender) smtp.mailfrom=willy@infradead.org 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=GWcO8qHo0kt3ntl8a5jR2Ne+3gIMw/C9E24POVCTyQY=; b=GioKHzFjcfm4M43j3Axf/hlmN VvDdVWDo21wuM9BnbT8CL3KddhQBCmDAd2gXGXOaN0Fm2vGiJtm60nY9eRREVQV988ohoxU86pjym 4p6tusbicOfLZ5UWauBN3y/sOWqpwLZ9xV1ZOfZDqa0/rBlL0KYeOWuwB9wdom4FF7RPEJNyZ5S+E cka2w3r9GZs4QPRjDr7mjK760nPO7B6DwIBf3juE9/AI8hu0itHMkRs6j5zZIeoqLuL31m7U6WVj2 KiTCpfN554WsYTR9zM9Th9iwSRdY8Av7E2RZ1pPJTlAh4xpRcNsOHK6K3DktRlDs65HI6CPfaajBs As+lRAPkA==; Received: from willy by bombadil.infradead.org with local (Exim 4.90_1 #2 (Red Hat Linux)) id 1fSNT1-0004ZL-PS; Mon, 11 Jun 2018 14:06:43 +0000 From: Matthew Wilcox To: linux-mm@kvack.org, linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org Cc: Matthew Wilcox , Jan Kara , Jeff Layton , Lukas Czerner , Ross Zwisler , Christoph Hellwig , Goldwyn Rodrigues , Nicholas Piggin , Ryusuke Konishi , linux-nilfs@vger.kernel.org, Jaegeuk Kim , Chao Yu , linux-f2fs-devel@lists.sourceforge.net Subject: [PATCH v13 11/72] xarray: Add xa_cmpxchg and xa_insert Date: Mon, 11 Jun 2018 07:05:38 -0700 Message-Id: <20180611140639.17215-12-willy@infradead.org> X-Mailer: git-send-email 2.14.3 In-Reply-To: <20180611140639.17215-1-willy@infradead.org> References: <20180611140639.17215-1-willy@infradead.org> X-Bogosity: Ham, tests=bogofilter, spamicity=0.000000, version=1.2.4 Sender: owner-linux-mm@kvack.org Precedence: bulk X-Loop: owner-majordomo@kvack.org List-ID: X-Virus-Scanned: ClamAV using ClamSMTP From: Matthew Wilcox Like cmpxchg(), xa_cmpxchg will only store to the index if the current entry matches the old entry. It returns the current entry, which is usually more useful than the errno returned by radix_tree_insert(). For the users who really only want the errno, the xa_insert() wrapper provides a more convenient calling convention. Signed-off-by: Matthew Wilcox --- include/linux/xarray.h | 60 ++++++++++++++++++++++ lib/xarray.c | 71 ++++++++++++++++++++++++++ tools/testing/radix-tree/xarray-test.c | 10 ++++ 3 files changed, 141 insertions(+) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index b5220493652d..c9fc47d28c09 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -218,6 +218,8 @@ struct xarray { void xa_init_flags(struct xarray *, gfp_t flags); 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); bool xa_get_tag(struct xarray *, unsigned long index, xa_tag_t); void xa_set_tag(struct xarray *, unsigned long index, xa_tag_t); void xa_clear_tag(struct xarray *, unsigned long index, xa_tag_t); @@ -277,6 +279,34 @@ static inline bool xa_tagged(const struct xarray *xa, xa_tag_t tag) return xa->xa_flags & XA_FLAGS_TAG(tag); } +/** + * xa_insert() - 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. + * + * Context: Process context. Takes and releases the xa_lock. + * May sleep if the @gfp flags permit. + * Return: 0 if the store succeeded. -EEXIST if another entry was present. + * -ENOMEM if memory could not be allocated. + */ +static inline int xa_insert(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) @@ -296,9 +326,39 @@ static inline bool xa_tagged(const struct xarray *xa, xa_tag_t tag) */ void *__xa_erase(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); void __xa_set_tag(struct xarray *, unsigned long index, xa_tag_t); void __xa_clear_tag(struct xarray *, unsigned long index, xa_tag_t); +/** + * __xa_insert() - 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. + * + * Context: Any context. Expects xa_lock to be held on entry. May + * release and reacquire xa_lock if the @gfp flags permit. + * Return: 0 if the store succeeded. -EEXIST if another entry was present. + * -ENOMEM if memory could not be allocated. + */ +static inline int __xa_insert(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; +} + /* Everything below here is the Advanced API. Proceed with caution. */ /* diff --git a/lib/xarray.c b/lib/xarray.c index d408627b2479..86b9e00a37a0 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -976,6 +976,77 @@ void *__xa_store(struct xarray *xa, unsigned long index, void *entry, gfp_t gfp) } 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: Memory 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. + * + * Context: Process context. Takes and releases the xa_lock. May sleep + * if the @gfp flags permit. + * 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_load(&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. + * @old: Old value to test against. + * @entry: New entry. + * @gfp: Memory allocation flags. + * + * You must already be holding the xa_lock when calling this function. + * It will drop the lock if needed to allocate memory, and then reacquire + * it afterwards. + * + * Context: Any context. Expects xa_lock to be held on entry. May + * release and reacquire xa_lock if @gfp flags permit. + * 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) +{ + XA_STATE(xas, xa, index); + void *curr; + + if (WARN_ON_ONCE(xa_is_internal(entry))) + return XA_ERROR(-EINVAL); + + do { + curr = xas_load(&xas); + if (curr == old) + xas_store(&xas, entry); + } while (__xas_nomem(&xas, gfp)); + + return xas_result(&xas, curr); +} +EXPORT_SYMBOL(__xa_cmpxchg); + /** * __xa_set_tag() - Set this tag on this entry while locked. * @xa: XArray. diff --git a/tools/testing/radix-tree/xarray-test.c b/tools/testing/radix-tree/xarray-test.c index 7bc84d1d6c9a..575f494e17da 100644 --- a/tools/testing/radix-tree/xarray-test.c +++ b/tools/testing/radix-tree/xarray-test.c @@ -88,6 +88,15 @@ void check_xa_shrink(struct xarray *xa) assert(xa_load(xa, 0) == xa_mk_value(0)); } +void check_cmpxchg(struct xarray *xa) +{ + assert(xa_empty(xa)); + assert(!xa_store(xa, 12345678, xa_mk_value(12345678), GFP_KERNEL)); + assert(!xa_cmpxchg(xa, 5, xa_mk_value(5), NULL, GFP_KERNEL)); + assert(xa_erase(xa, 12345678) == xa_mk_value(12345678)); + assert(xa_empty(xa)); +} + void check_multi_store(struct xarray *xa) { unsigned long i, j, k; @@ -158,6 +167,7 @@ void xarray_checks(void) check_xa_shrink(&array); item_kill_tree(&array); + check_cmpxchg(&array); check_multi_store(&array); item_kill_tree(&array); }