From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Cyrus-Session-Id: sloti22d1t05-391662-1516223521-2-931852607598756144 X-Sieve: CMU Sieve 3.0 X-Spam-known-sender: no X-Spam-score: 0.0 X-Spam-hits: BAYES_00 -1.9, HEADER_FROM_DIFFERENT_DOMAINS 0.25, RCVD_IN_DNSWL_HI -5, T_RP_MATCHES_RCVD -0.01, LANGUAGES en, BAYES_USED global, SA_VERSION 3.4.0 X-Spam-source: IP='209.132.180.67', Host='vger.kernel.org', Country='US', FromHeader='org', MailFrom='org' X-Spam-charsets: X-Resolved-to: greg@kroah.com X-Delivered-to: greg@kroah.com X-Mail-from: linux-usb-owner@vger.kernel.org ARC-Seal: i=1; a=rsa-sha256; cv=none; d=messagingengine.com; s=arctest; t=1516223520; b=foVfdk1Wg9MHLa0SRCL7JbJYfF3MMNG79CMs+uKSXlazJSr nkabZQ4YqSWpzHxjG+yfLuUmikkfnaPfR+xOAK5pQUz3OP2RnwAIBOmDEBYa632R Cp7KFFJhr/FEVxbuZBMEnBZyqpQZhg9D2fKyoE5nH6ihIG1ACLTN2ZLYGdVD+RXb YspBE2Q8rtTMS20t/VBadbiEtsMbKbzDeRNVhZMzrmp/x594Z584clAtkeiwkPpE O2mgHIsNSbATtGTYE5wv1mrcCeHnejYGSMwnMKg6kv704M6cgJoT1MytlIq149eQ vaHxx2De0N43xaNQjBcBDCoXsTwLMA+KCApd+lg== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d= messagingengine.com; h=from:to:cc:subject:date:message-id :in-reply-to:references:sender:list-id; s=arctest; t=1516223520; bh=U7Ppqrm+TLKGiXF8Pc1wwiFBxPAfK/hABgjmJWVDARU=; b=fjmMZqo+mdK0 DRbJ6QaGYMHO87Bnw10+ypK73QicCX72L9v7wMIUHv8J0IbYc84P0XFMvr/4+RHu 8BgmF935ciopysB5lUpwaWePkT5NEWQkCSC7GC4bmw2+DpF19T1r1SDTPLZl3kx8 YaaFkTqugmpA+FoFynExictgq3xsmOqFkVbCvGTRpbdiHxRAXlHKIrfs+v4Ey8VV /srAVHYfGaMAppqYRb4ZlVpdkXABmsC2nt+YmqVP2dOgEVm9UlLxiwKYhPm53dp5 vslCjck1f3uWNPMjjuxCnb5pu5RB1In/ga+qfN4bliLTQUKkM3K6DRHe4Lmbocc+ hxcbxDt0Mw== ARC-Authentication-Results: i=1; mx6.messagingengine.com; arc=none (no signatures found); dkim=fail (message has been altered; 2048-bit rsa key sha256) header.d=infradead.org header.i=@infradead.org header.b=D3/Qgy7N x-bits=2048 x-keytype=rsa x-algorithm=sha256 x-selector=bombadil.20170209; dmarc=none (p=none,has-list-id=yes,d=none) header.from=infradead.org; iprev=pass policy.iprev=209.132.180.67 (vger.kernel.org); spf=none smtp.mailfrom=linux-usb-owner@vger.kernel.org smtp.helo=vger.kernel.org; x-aligned-from=fail; x-ptr=pass x-ptr-helo=vger.kernel.org x-ptr-lookup=vger.kernel.org; x-return-mx=pass smtp.domain=vger.kernel.org smtp.result=pass smtp_org.domain=kernel.org smtp_org.result=pass smtp_is_org_domain=no header.domain=infradead.org header.result=pass header_is_org_domain=yes Authentication-Results: mx6.messagingengine.com; arc=none (no signatures found); dkim=fail (message has been altered; 2048-bit rsa key sha256) header.d=infradead.org header.i=@infradead.org header.b=D3/Qgy7N x-bits=2048 x-keytype=rsa x-algorithm=sha256 x-selector=bombadil.20170209; dmarc=none (p=none,has-list-id=yes,d=none) header.from=infradead.org; iprev=pass policy.iprev=209.132.180.67 (vger.kernel.org); spf=none smtp.mailfrom=linux-usb-owner@vger.kernel.org smtp.helo=vger.kernel.org; x-aligned-from=fail; x-ptr=pass x-ptr-helo=vger.kernel.org x-ptr-lookup=vger.kernel.org; x-return-mx=pass smtp.domain=vger.kernel.org smtp.result=pass smtp_org.domain=kernel.org smtp_org.result=pass smtp_is_org_domain=no header.domain=infradead.org header.result=pass header_is_org_domain=yes Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754796AbeAQVL4 (ORCPT ); Wed, 17 Jan 2018 16:11:56 -0500 Received: from bombadil.infradead.org ([65.50.211.133]:58287 "EHLO bombadil.infradead.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753361AbeAQUWb (ORCPT ); Wed, 17 Jan 2018 15:22:31 -0500 From: Matthew Wilcox To: linux-kernel@vger.kernel.org Cc: Matthew Wilcox , 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, Bjorn Andersson , Stefano Stabellini , iommu@lists.linux-foundation.org, linux-remoteproc@vger.kernel.org, linux-s390@vger.kernel.org, intel-gfx@lists.freedesktop.org, cgroups@vger.kernel.org, linux-sh@vger.kernel.org, David Howells Subject: [PATCH v6 13/99] xarray: Add xa_extract Date: Wed, 17 Jan 2018 12:20:37 -0800 Message-Id: <20180117202203.19756-14-willy@infradead.org> X-Mailer: git-send-email 2.14.3 In-Reply-To: <20180117202203.19756-1-willy@infradead.org> References: <20180117202203.19756-1-willy@infradead.org> Sender: linux-usb-owner@vger.kernel.org X-Mailing-List: linux-usb@vger.kernel.org X-getmail-retrieved-from-mailbox: INBOX X-Mailing-List: linux-kernel@vger.kernel.org List-ID: From: Matthew Wilcox This function combines the functionality of radix_tree_gang_lookup() and radix_tree_gang_lookup_tagged(). It extracts entries matching the specified filter into a normal array. Signed-off-by: Matthew Wilcox --- include/linux/xarray.h | 2 ++ lib/xarray.c | 80 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 82 insertions(+) diff --git a/include/linux/xarray.h b/include/linux/xarray.h index fcd7ef68933a..d79fd48e4957 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -219,6 +219,8 @@ void *xa_find(struct xarray *xa, unsigned long *index, unsigned long max, xa_tag_t) __attribute__((nonnull(2))); void *xa_find_after(struct xarray *xa, unsigned long *index, unsigned long max, xa_tag_t) __attribute__((nonnull(2))); +unsigned int xa_extract(struct xarray *, void **dst, unsigned long start, + unsigned long max, unsigned int n, xa_tag_t); /** * xa_init() - Initialise an empty XArray. diff --git a/lib/xarray.c b/lib/xarray.c index 3e6be0a07525..be276618f81b 100644 --- a/lib/xarray.c +++ b/lib/xarray.c @@ -1368,6 +1368,86 @@ void *xa_find_after(struct xarray *xa, unsigned long *indexp, } EXPORT_SYMBOL(xa_find_after); +static unsigned int xas_extract_present(struct xa_state *xas, void **dst, + unsigned long max, unsigned int n) +{ + void *entry; + unsigned int i = 0; + + rcu_read_lock(); + xas_for_each(xas, entry, max) { + if (xas_retry(xas, entry)) + continue; + dst[i++] = entry; + if (i == n) + break; + } + rcu_read_unlock(); + + return i; +} + +static unsigned int xas_extract_tag(struct xa_state *xas, void **dst, + unsigned long max, unsigned int n, xa_tag_t tag) +{ + void *entry; + unsigned int i = 0; + + rcu_read_lock(); + xas_for_each_tag(xas, entry, max, tag) { + if (xas_retry(xas, entry)) + continue; + dst[i++] = entry; + if (i == n) + break; + } + rcu_read_unlock(); + + return i; +} + +/** + * xa_extract() - Copy selected entries from the XArray into a normal array. + * @xa: The source XArray to copy from. + * @dst: The buffer to copy entries into. + * @start: The first index in the XArray eligible to be selected. + * @max: The last index in the XArray eligible to be selected. + * @n: The maximum number of entries to copy. + * @filter: Selection criterion. + * + * Copies up to @n entries that match @filter from the XArray. The + * copied entries will have indices between @start and @max, inclusive. + * + * The @filter may be an XArray tag value, in which case entries which are + * tagged with that tag will be copied. It may also be %XA_PRESENT, in + * which case non-NULL entries will be copied. + * + * This function uses the RCU lock to protect itself. That means that the + * entries returned may not represent a snapshot of the XArray at a moment + * in time. For example, if index 5 is stored to, then index 10 is stored to, + * calling xa_extract() may return the old contents of index 5 and the + * new contents of index 10. Indices not modified while this function is + * running will not be skipped. + * + * If you need stronger guarantees, holding the xa_lock across calls to this + * function will prevent concurrent modification. + * + * Return: The number of entries copied. + */ +unsigned int xa_extract(struct xarray *xa, void **dst, unsigned long start, + unsigned long max, unsigned int n, xa_tag_t filter) +{ + XA_STATE(xas, xa, start); + + if (!n) + return 0; + + if ((__force unsigned int)filter < XA_MAX_TAGS) + return xas_extract_tag(&xas, dst, max, n, filter); + return xas_extract_present(&xas, dst, max, n); +} +EXPORT_SYMBOL(xa_extract); + #ifdef XA_DEBUG void xa_dump_node(const struct xa_node *node) { -- 2.15.1