From patchwork Mon Jun 11 14:05:43 2018 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: "Matthew Wilcox (Oracle)" X-Patchwork-Id: 10457885 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 4ABF260467 for ; Mon, 11 Jun 2018 14:07:54 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 374362846D for ; Mon, 11 Jun 2018 14:07:54 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 2908728451; Mon, 11 Jun 2018 14:07:54 +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 7A78228451 for ; Mon, 11 Jun 2018 14:07:53 +0000 (UTC) Received: by kanga.kvack.org (Postfix) id 5077E6B026B; Mon, 11 Jun 2018 10:06:49 -0400 (EDT) Delivered-To: linux-mm-outgoing@kvack.org Received: by kanga.kvack.org (Postfix, from userid 40) id 3A0016B0271; Mon, 11 Jun 2018 10:06:49 -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 F3E6E6B026B; Mon, 11 Jun 2018 10:06:48 -0400 (EDT) X-Original-To: linux-mm@kvack.org X-Delivered-To: linux-mm@kvack.org Received: from mail-pf0-f199.google.com (mail-pf0-f199.google.com [209.85.192.199]) by kanga.kvack.org (Postfix) with ESMTP id 99E3B6B0270 for ; Mon, 11 Jun 2018 10:06:48 -0400 (EDT) Received: by mail-pf0-f199.google.com with SMTP id n19-v6so4081397pff.8 for ; Mon, 11 Jun 2018 07:06:48 -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=/OXuoNN01nhzSTU6HgfbvZIzFPLZd+W81a8DkuntQPA=; b=MCRBo8KOGEGH0fp/vFDN67nAzmHNiAKV1pc3UL26KMrnS6lUpVLwFU2kUXHi01HYl3 ph9er/MDmjb56Lnq5++B56lnVsr63pMO8eaobhzsdJrIsx7ZfDBdKP88gdtcKw2fwABO oRUErf22eTrxfwipo0cdqrEMUv6CZyHAbJ8RAGbCBd3vnlaFVZbquw3fRHqZDNoqu2wO s3Wiw4IjD5dsURhkKQ3OyqLN5PqtEMjSZYuD5sVtYQQKsI7brA7c0TKNqZe/cV6XqfzJ FB+A68Sg17nJqRx5E4ZoxPgQ/uKyMUGPjQFOw6oXQeGuPhajbMuPBrgT7dUQEv1sYQkF mbFw== X-Gm-Message-State: APt69E0yIuol2wHDMxzGhAbm9VZAcQAijMnorR8J0Uj0P0ql8g2mG+9G 5mVgGxzKbOZieogh1Anx3xkQEIQM+PBI4mTxGuIa3ovs4d8Ku8dF6aZj/SqHZpUwN42CZ8jd8w4 F9hFMcR/40vRnHKp2Zv6Sv/r70CtHSSp6HMzuYSjcu1V29KAJ+ZC7VY3f0yV+AYfxPw== X-Received: by 2002:a63:7a48:: with SMTP id j8-v6mr14903707pgn.415.1528726008288; Mon, 11 Jun 2018 07:06:48 -0700 (PDT) X-Google-Smtp-Source: ADUXVKIbKAn+uZ1rAtb1hbzqFxNp+PydfUcRMNh1tVxeUxSkx80OBqBWMRJ+jIB9dy6lXMeLOQgn X-Received: by 2002:a63:7a48:: with SMTP id j8-v6mr14903625pgn.415.1528726007009; Mon, 11 Jun 2018 07:06:47 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1528726006; cv=none; d=google.com; s=arc-20160816; b=YKZ/SYrfYXPebEaMIzoJI2ZBMqxqQ6kfgtNJAVD/Kn1QX+6lmxJxm1Vn5Y55tIEo8g FXRpIYzpLPepDhqg0SbWuqoU4SWlB+6B4b7cZr0i/OmW+FL3258+GpaQBw99Xbp365jC fQE7nwz0zLtovPvaL8kZWWov1MZ6LndvW0z0NuxMjwy+PthNDIbrmXw1TJe0XWufYdaw djImqZc5xLz0wpTl7fFgt8HEmkmytCTEQ4aRnclrbSCG0SraZW9AF67lSZ5H834A5qMh 0b+4rX9+iw31bJoA8bGQh1qnH0HZlHSxcttclj4wmLga67l3byl3Jk63l+ULBCWYDQU9 QMyA== 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=/OXuoNN01nhzSTU6HgfbvZIzFPLZd+W81a8DkuntQPA=; b=tsZY4wmFBnSZh0mElM3bgyq/w9d6T5Q6z31iIUyro3QLg7XVV02Gc6iyfest6Wn6yr 3Td/QVXbXiwt3RzU2kPom03i1pNigzTncmUwigZXyh9hIYRZV+ylZRvjsdVqeZ2VBO/e tPnqHUNKv+KQtEI3Sj+2g0yhbp0WDwIQMMZYiU7g3JwaDTuFrGNcnsejQgKehj9z4aGn Z2HCG7kGcvMS9UdueDIQvSfBM7DQolWGV1TNmn2ILIq8qfCJCbr/bZ9Vg/NLqMIiYQ/t vL3biQbW8jSfP07rFROQiZoj42wp7thcg1+XNiU2bBWSnazq/K2NILBBgBYHqzPRWF25 gs/g== ARC-Authentication-Results: i=1; mx.google.com; dkim=pass header.i=@infradead.org header.s=bombadil.20170209 header.b=fhCmjc0s; 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 h26-v6si26710034pfj.120.2018.06.11.07.06.46 for (version=TLS1_2 cipher=ECDHE-RSA-CHACHA20-POLY1305 bits=256/256); Mon, 11 Jun 2018 07:06:46 -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=fhCmjc0s; 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=/OXuoNN01nhzSTU6HgfbvZIzFPLZd+W81a8DkuntQPA=; b=fhCmjc0sb8KAhLmuFlr1+POvw Jq1LGFUkBThFZymX5NjKJX/mXAMHpuFoYgS8xF5DFQ4OrZmlNn0jqUtO9Ods9r30jjCEac+mG4t1z yUBrTHIwOAgx/INY0KSV2hbKREWkgC6d/7yqu96pH9w6g5Jt49qc14XS36+XIhgyGu2xIIchow4Qz BW+5ahtfcg5tlK9MAQGV/if7x7G36MRXucUdzi4Pm433ZfNWXB4GQKDK6tpaRa9b9WLE/4eNwotsQ WYJU0V3ymjWi/vygICy/VM7sHmuyl6AEEOhdn+hgIPLQrknYf6RUcBi7t2+U9uZR7FAYMk0lGCpt0 sOmyZdAcQ==; Received: from willy by bombadil.infradead.org with local (Exim 4.90_1 #2 (Red Hat Linux)) id 1fSNT3-0004bh-Vi; Mon, 11 Jun 2018 14:06:45 +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 16/72] xarray: Add xas_for_each_conflict Date: Mon, 11 Jun 2018 07:05:43 -0700 Message-Id: <20180611140639.17215-17-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 This iterator iterates over each entry that is stored in the index or indices specified by the xa_state. This is intended for use for a conditional store of a multiindex entry, or to allow entries which are about to be removed from the xarray to be disposed of properly. Signed-off-by: Matthew Wilcox --- include/linux/xarray.h | 17 +++++++ lib/xarray.c | 61 +++++++++++++++++++++++++ tools/testing/radix-tree/xarray-test.c | 63 ++++++++++++++++++++++++++ 3 files changed, 141 insertions(+) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index dd941454bb5b..6a61aab11038 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -750,6 +750,7 @@ static inline bool xas_retry(struct xa_state *xas, const void *entry) void *xas_load(struct xa_state *); void *xas_store(struct xa_state *, void *entry); void *xas_find(struct xa_state *, unsigned long max); +void *xas_next_conflict(struct xa_state *); bool xas_get_tag(const struct xa_state *, xa_tag_t); void xas_set_tag(const struct xa_state *, xa_tag_t); @@ -964,6 +965,22 @@ enum { for (entry = xas_find_tagged(xas, max, tag); entry; \ entry = xas_next_tagged(xas, max, tag)) +/** + * xas_for_each_conflict() - Iterate over a range of an XArray. + * @xas: XArray operation state. + * @entry: Entry retrieved from the array. + * + * The loop body will be executed for each entry in the XArray that lies + * within the range specified by @xas. If the loop completes successfully, + * any entries that lie in this range will be replaced by @entry. The caller + * may break out of the loop; if they do so, the contents of the XArray will + * be unchanged. The operation may fail due to an out of memory condition. + * The caller may also call xa_set_err() to exit the loop while setting an + * error to record the reason. + */ +#define xas_for_each_conflict(xas, entry) \ + while ((entry = xas_next_conflict(xas))) + void *__xas_next(struct xa_state *); void *__xas_prev(struct xa_state *); diff --git a/lib/xarray.c b/lib/xarray.c index 3b2c2f2240bf..d76db0ff17cf 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1100,6 +1100,67 @@ void *xas_find_tagged(struct xa_state *xas, unsigned long max, xa_tag_t tag) } EXPORT_SYMBOL_GPL(xas_find_tagged); +/** + * xas_next_conflict() - Step for xas_for_each_conflict(). + * @xas: XArray operation state. + * + * This function does the work for xas_for_each_conflict(). + * + * Context: Any context. Expects xa_lock to be held. + * Return: The next entry in the range covered by @xas or %NULL. + */ +void *xas_next_conflict(struct xa_state *xas) +{ + void *curr; + + if (xas_error(xas)) + return NULL; + + if (!xas->xa_node) + return NULL; + + if (xas_top(xas->xa_node)) { + curr = xas_start(xas); + if (!curr) + return NULL; + while (xa_is_node(curr)) { + struct xa_node *node = xa_to_node(curr); + curr = xas_descend(xas, node); + } + if (curr) + return curr; + } + + if (xas->xa_node->shift > xas->xa_shift) + return NULL; + + for (;;) { + if (xas->xa_node->shift == xas->xa_shift) { + if ((xas->xa_offset & xas->xa_sibs) == xas->xa_sibs) + break; + } else if (xas->xa_offset == XA_CHUNK_MASK) { + xas->xa_offset = xas->xa_node->offset; + xas->xa_node = xas->xa_node->parent; + if (!xas->xa_node) + break; + continue; + } + curr = xa_entry_locked(xas->xa, xas->xa_node, ++xas->xa_offset); + if (xa_is_sibling(curr)) + continue; + while (xa_is_node(curr)) { + xas->xa_node = xa_to_node(curr); + xas->xa_offset = 0; + curr = xa_entry_locked(xas->xa, xas->xa_node, 0); + } + if (curr) + return curr; + } + xas->xa_offset -= xas->xa_sibs; + return NULL; +} +EXPORT_SYMBOL_GPL(xas_next_conflict); + /** * xa_init_flags() - Initialise an empty XArray with flags. * @xa: XArray. diff --git a/tools/testing/radix-tree/xarray-test.c b/tools/testing/radix-tree/xarray-test.c index eeafbf8c948c..296ace77c4f4 100644 --- a/tools/testing/radix-tree/xarray-test.c +++ b/tools/testing/radix-tree/xarray-test.c @@ -315,6 +315,68 @@ void check_multi_store(struct xarray *xa) BUG_ON(!xa_empty(xa)); } +void __check_store_iter(struct xarray *xa, unsigned long start, + unsigned int order, unsigned int present) +{ + XA_STATE_ORDER(xas, xa, start, order); + void *entry; + unsigned int count = 0; + +retry: + xas_for_each_conflict(&xas, entry) { + BUG_ON(!xa_is_value(entry)); + BUG_ON(entry < xa_mk_value(start)); + BUG_ON(entry > xa_mk_value(start + (1UL << order) - 1)); + count++; + } + xas_store(&xas, xa_mk_value(start)); + if (xas_nomem(&xas, GFP_KERNEL)) { + count = 0; + goto retry; + } + BUG_ON(xas_error(&xas)); + BUG_ON(count != present); + BUG_ON(xa_load(xa, start) != xa_mk_value(start)); + BUG_ON(xa_load(xa, start + (1UL << order) - 1) != xa_mk_value(start)); + xa_store(xa, start, NULL, 0); +} + +void check_store_iter(struct xarray *xa) +{ + unsigned int i, j; + + for (i = 0; i < 20; i++) { + unsigned int min = 1 << i; + unsigned int max = (2 << i) - 1; + __check_store_iter(xa, 0, i, 0); + BUG_ON(!xa_empty(xa)); + __check_store_iter(xa, min, i, 0); + BUG_ON(!xa_empty(xa)); + + xa_store(xa, min, xa_mk_value(min), GFP_KERNEL); + __check_store_iter(xa, min, i, 1); + BUG_ON(!xa_empty(xa)); + xa_store(xa, max, xa_mk_value(max), GFP_KERNEL); + __check_store_iter(xa, min, i, 1); + BUG_ON(!xa_empty(xa)); + + for (j = 0; j < min; j++) + xa_store(xa, j, xa_mk_value(j), GFP_KERNEL); + __check_store_iter(xa, 0, i, min); + BUG_ON(!xa_empty(xa)); + for (j = 0; j < min; j++) + xa_store(xa, min + j, xa_mk_value(min + j), GFP_KERNEL); + __check_store_iter(xa, min, i, min); + BUG_ON(!xa_empty(xa)); + } + xa_store(xa, 63, xa_mk_value(63), GFP_KERNEL); + xa_store(xa, 65, xa_mk_value(65), GFP_KERNEL); + __check_store_iter(xa, 64, 2, 1); + BUG_ON(xa_load(xa, 63) != xa_mk_value(63)); + xa_store(xa, 63, NULL, 0); + BUG_ON(!xa_empty(xa)); +} + void check_multi_find(struct xarray *xa) { unsigned long index; @@ -537,6 +599,7 @@ void xarray_checks(void) check_cmpxchg(&array); check_multi_store(&array); item_kill_tree(&array); + check_store_iter(&array); check_find(&array); check_xas_delete(&array);