From patchwork Sun Jun 17 01:59:50 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Matthew Wilcox X-Patchwork-Id: 10468211 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 0B958600CC for ; Sun, 17 Jun 2018 02:01:42 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id EE66128BC1 for ; Sun, 17 Jun 2018 02:01:41 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id E2CEC28BDB; Sun, 17 Jun 2018 02:01:41 +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 32ACD28BD0 for ; Sun, 17 Jun 2018 02:01:41 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 48E4E6B026E; Sat, 16 Jun 2018 22:01:04 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 3F59B6B026F; Sat, 16 Jun 2018 22:01:04 -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 15DA26B0270; Sat, 16 Jun 2018 22:01:04 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pf0-f198.google.com (mail-pf0-f198.google.com [209.85.192.198]) by kanga.kvack.org (Postfix) with ESMTP id 6E9616B026E for ; Sat, 16 Jun 2018 22:01:03 -0400 (EDT) Received: by mail-pf0-f198.google.com with SMTP id z9-v6so6619479pfe.23 for ; Sat, 16 Jun 2018 19:01:03 -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=P3h7Y608mo+07Z2krzf3Bqsbr7SfCi8zVrrr+t6coas=; b=ZraPLt7iGxe3adLJOQhpufO8DecP564dw/wmVdh6y7LaBq+Esn/LwSLtKHqQu1P414 6Y7mKj0dhLV/FW9If7ZaVCSiKkW/X9rRB8+DqzJv1g86j8CJPnB8lmSNc0CqQiIL4RU3 x3sYASblMlmSQwzKRxDgcGZks/d4oWJ5wo1RPsnFKX4DAGWjJKALQhXt5lPDZVe608nl KcoPGwNK2HrLGE8/ovSDCzXj+jiP4kRXc3CzIvWK+qe3Tot1EClQSF5DmVtH9FC1FPSJ V9r97ZiyQosAAc7EEtfPZT9vTJDDXM5yEDBgQa5SXMhkjuOM0kSHS+B04UHTpOPCTChm Nd1Q== X-Gm-Message-State: APt69E3j6wG2rz1Ir+pFKBs+9jvEB4kfEi8Iwuj2kURpfevjF1KT2+hq zaL4e0clrpZQ3W24Jbv/JBtRy+yYiPHQXtKUVGalUxTLFEORELuqusRhsT7NtXeKw121oDJFG0C ynna0UHVn2yef+5oR//QQ9j8+eRgl1/Xd5TUAAptw1qGJ20i8QSzSAQZRr1FEB8XC/Q== X-Received: by 2002:a17:902:89:: with SMTP id a9-v6mr8244112pla.326.1529200863123; Sat, 16 Jun 2018 19:01:03 -0700 (PDT) X-Google-Smtp-Source: ADUXVKJdNPK25iz1eTECIfWBfMF1RUIjjuU/HFe0rWGpgrbhX5an7+ZwbYT/OJPMiU6gJxh1BzHG X-Received: by 2002:a17:902:89:: with SMTP id a9-v6mr8244070pla.326.1529200862211; Sat, 16 Jun 2018 19:01:02 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1529200862; cv=none; d=google.com; s=arc-20160816; b=s6L4JdutCzFsYWTJpHft50mOqhGOU+Fl7za3xcrZTjxUj+GoYR0DWGuyuCFwPjX5rk 4Z1UFPGay0+TDB6h+P76p2lC2INU1SUomtiVltHC0geMxHC3bozeORKzH2/+n7zVvilr H9hahc7T41ZwoiSdwqC5i6JZ7wPF+uXeIWYy6aGhPy9+lekBUjf7AP/D1SQJ3HI6j0vh HCnkJlOjgYNHMXZKNeGeP812uAgNbmlc5TDJLzvDmyuEDAUKTzGZyCwIMnAuzqooWM7n tRNmXXw2Udco6mm/e5K9La5epcZMjehZXOQzxgDE08EXQ5EqBuivK9MG9ZGIACmjrJQA geOw== 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=P3h7Y608mo+07Z2krzf3Bqsbr7SfCi8zVrrr+t6coas=; b=hUYSfclKuEEEzTZs27rjh1T0Jaor5QXUCNYw3QwD2fgyh7bbDtrxZeJXmRMSmVPnWn LO9HLgamyh2KUeXDvEp7dDaDDOBR6E9qVykKtVVw+fu6yXBZ13DTpFeqs84pm3fwOMcY 3OthhFPcop2+VrMh1Xy36h4xZDTL65p4gxxyly3d5ugtSRavzIpbiguWOZoF2a+Ig13N FHSjhcQ2eDVMRKb1dwBzRO9e+5SZHkEgFrXRTkfOEA2blpV3EiWAVA5/osUxVDPFyM6Z FTRqoZd4c6Q7hID1SjiwhUrTWkTQ8LSpAV0NstfQZSwk9ShrGMWvco+lVjVxORaxQ3mC bIWw== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@infradead.org header.s=bombadil.20170209 header.b=F2UOjdbT; 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 q5-v6si8833928pgv.537.2018.06.16.19.01.02 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Sat, 16 Jun 2018 19:01:02 -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=F2UOjdbT; 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=P3h7Y608mo+07Z2krzf3Bqsbr7SfCi8zVrrr+t6coas=; b=F2UOjdbTw2i9qdS3E2SubsrR+ 9uToOeetXYMEmnxqc4b4KJ0RAL1TCiC41Vn2NUOBd9QzJ2BUJr7yf47ygmymxZiSYVvaT9bABK8Lv 6Y8HJZ21X/C92Rx1GLRcHZooTDeL+7udSzJ/71ZEVvE1YN3JBUMRMQcWWSLbI9ueV380+AmnSVZgD SbbKSGhlLJaezilKE/IYUgFNrCSCN0PDzSiiHT70k+DSNPajCEJXlObSkPdrp7l8QtVSuI36nMiIO l6VZ+pJJ/ctSdzITsetLrR2RyWYotD/BhteaFYJ4GWFC+l6pWEAQzE0iiA4Wg7T5y4K/gPRqCYXX/ 2E7TME9kQ==; Received: from willy by bombadil.infradead.org with local (Exim 4.90_1 #2 (Red Hat Linux)) id 1fUMzw-0001GJ-Bn; Sun, 17 Jun 2018 02:00:56 +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 v14 12/74] xarray: Add XArray conditional store operations Date: Sat, 16 Jun 2018 18:59:50 -0700 Message-Id: <20180617020052.4759-13-willy@infradead.org> X-Mailer: git-send-email 2.14.3 In-Reply-To: <20180617020052.4759-1-willy@infradead.org> References: <20180617020052.4759-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 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/test_xarray.c | 20 ++++++++++++ lib/xarray.c | 71 ++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 151 insertions(+) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 13e5c4084dcd..94b7f454a6a0 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 void *xa_erase(struct xarray *xa, unsigned long index) return xa_store(xa, index, NULL, 0); } +/** + * 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 void *xa_erase(struct xarray *xa, unsigned long index) */ 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/test_xarray.c b/lib/test_xarray.c index cb6e9910e369..35fca5e23cbc 100644 --- a/lib/test_xarray.c +++ b/lib/test_xarray.c @@ -181,6 +181,25 @@ static void check_xa_shrink(struct xarray *xa) XA_BUG_ON(xa, !xa_empty(xa)); } +static void check_cmpxchg(struct xarray *xa) +{ + void *FIVE = xa_mk_value(5); + void *SIX = xa_mk_value(6); + void *LOTS = xa_mk_value(12345678); + + XA_BUG_ON(xa, !xa_empty(xa)); + XA_BUG_ON(xa, xa_store_value(xa, 12345678, GFP_KERNEL) != NULL); + XA_BUG_ON(xa, xa_insert(xa, 12345678, xa, GFP_KERNEL) != -EEXIST); + XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, SIX, FIVE, GFP_KERNEL) != LOTS); + XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, LOTS, FIVE, GFP_KERNEL) != LOTS); + XA_BUG_ON(xa, xa_cmpxchg(xa, 12345678, FIVE, LOTS, GFP_KERNEL) != FIVE); + XA_BUG_ON(xa, xa_cmpxchg(xa, 5, FIVE, NULL, GFP_KERNEL) != NULL); + XA_BUG_ON(xa, xa_cmpxchg(xa, 5, NULL, FIVE, GFP_KERNEL) != NULL); + xa_erase_value(xa, 12345678); + xa_erase_value(xa, 5); + XA_BUG_ON(xa, !xa_empty(xa)); +} + static void check_multi_store(struct xarray *xa) { unsigned long i, j, k; @@ -248,6 +267,7 @@ static int xarray_checks(void) check_xa_load(&array); check_xa_tag(&array); check_xa_shrink(&array); + check_cmpxchg(&array); check_multi_store(&array); printk("XArray: %u of %u tests passed\n", tests_passed, tests_run); diff --git a/lib/xarray.c b/lib/xarray.c index 18043aee8a91..1a3a256cbb37 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -962,6 +962,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.