From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: X-Spam-Checker-Version: SpamAssassin 3.4.0 (2014-02-07) on aws-us-west-2-korg-lkml-1.web.codeaurora.org X-Spam-Level: X-Spam-Status: No, score=-9.6 required=3.0 tests=DKIM_INVALID,DKIM_SIGNED, HEADER_FROM_DIFFERENT_DOMAINS,INCLUDES_PATCH,MAILING_LIST_MULTI,SIGNED_OFF_BY, SPF_HELO_NONE,SPF_PASS,USER_AGENT_GIT autolearn=ham autolearn_force=no version=3.4.0 Received: from mail.kernel.org (mail.kernel.org [198.145.29.99]) by smtp.lore.kernel.org (Postfix) with ESMTP id 028A0C33CB2 for ; Wed, 15 Jan 2020 02:38:55 +0000 (UTC) Received: from kanga.kvack.org (kanga.kvack.org [205.233.56.17]) by mail.kernel.org (Postfix) with ESMTP id BD976222C3 for ; Wed, 15 Jan 2020 02:38:54 +0000 (UTC) Authentication-Results: mail.kernel.org; dkim=fail reason="signature verification failed" (2048-bit key) header.d=infradead.org header.i=@infradead.org header.b="B8m47kZ4" DMARC-Filter: OpenDMARC Filter v1.3.2 mail.kernel.org BD976222C3 Authentication-Results: mail.kernel.org; dmarc=none (p=none dis=none) header.from=infradead.org Authentication-Results: mail.kernel.org; spf=pass smtp.mailfrom=owner-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix) id 61FF68E000A; Tue, 14 Jan 2020 21:38:51 -0500 (EST) Received: by kanga.kvack.org (Postfix, from userid 40) id 559448E0008; Tue, 14 Jan 2020 21:38:51 -0500 (EST) X-Delivered-To: int-list-linux-mm@kvack.org Received: by kanga.kvack.org (Postfix, from userid 63042) id 202FF8E0009; Tue, 14 Jan 2020 21:38:51 -0500 (EST) X-Delivered-To: linux-mm@kvack.org Received: from forelay.hostedemail.com (smtprelay0139.hostedemail.com [216.40.44.139]) by kanga.kvack.org (Postfix) with ESMTP id F3C928E0003 for ; Tue, 14 Jan 2020 21:38:50 -0500 (EST) Received: from smtpin07.hostedemail.com (10.5.19.251.rfc1918.com [10.5.19.251]) by forelay04.hostedemail.com (Postfix) with SMTP id B71813A82 for ; Wed, 15 Jan 2020 02:38:50 +0000 (UTC) X-FDA: 76378310820.07.fan80_875d6fd968240 X-HE-Tag: fan80_875d6fd968240 X-Filterd-Recvd-Size: 5349 Received: from bombadil.infradead.org (bombadil.infradead.org [198.137.202.133]) by imf46.hostedemail.com (Postfix) with ESMTP for ; Wed, 15 Jan 2020 02:38:50 +0000 (UTC) DKIM-Signature: v=1; a=rsa-sha256; q=dns/txt; c=relaxed/relaxed; d=infradead.org; s=bombadil.20170209; h=Content-Transfer-Encoding: MIME-Version:References:In-Reply-To:Message-Id:Date:Subject:Cc:To:From:Sender :Reply-To:Content-Type: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=t2MsvrgFyKMklh8a9GSQdPemnFwCPtSVERkAiF6+ogA=; b=B8m47kZ4X+h0DMHQn1K+2rOHkY hwLKteFLytNaxEKnzlCSBDAJz0fJXaVd/spdpfgD0HTWbcfet0LZg+hZP4G1sqBZaNQwr4R8vvEzZ o3Dv6Ei3shJPPTdAqLbFiXyNvlj5/VrpfNTgt4xD0uBSu63frPzORfwhbgpYRVDfuvGTNCORNmu63 Q6hT/xWyrtBntiw54OYBsTjk2J7buSZ/I6G6vvtTzXrbzW1rCypYEonPrY9wKI4I45WI1TMi8rp2W WLz8zHyQwCFyXamXHDqJ/NSvq/OmfNQiqOPKz2C2S0GDsUQW+cyQO3VQe+cPw/2uYQnCOA07g5pVL EiuVVrOg==; Received: from willy by bombadil.infradead.org with local (Exim 4.92.3 #3 (Red Hat Linux)) id 1irYZy-0008AY-2O; Wed, 15 Jan 2020 02:38:46 +0000 From: Matthew Wilcox To: linux-xfs@vger.kernel.org, linux-fsdevel@vger.kernel.org, linux-mm@kvack.org Cc: "Matthew Wilcox (Oracle)" , Jeff Layton , Christoph Hellwig , Chris Mason Subject: [PATCH v2 3/9] XArray: Add xarray_for_each_range Date: Tue, 14 Jan 2020 18:38:37 -0800 Message-Id: <20200115023843.31325-4-willy@infradead.org> X-Mailer: git-send-email 2.21.0 In-Reply-To: <20200115023843.31325-1-willy@infradead.org> References: <20200115023843.31325-1-willy@infradead.org> MIME-Version: 1.0 Content-Transfer-Encoding: quoted-printable 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: From: "Matthew Wilcox (Oracle)" This function supports iterating over a range of an array. Also add documentation links for xarray_for_each_start(). Signed-off-by: Matthew Wilcox (Oracle) --- Documentation/core-api/xarray.rst | 10 ++++++---- include/linux/xarray.h | 30 ++++++++++++++++++++++++++++++ 2 files changed, 36 insertions(+), 4 deletions(-) diff --git a/Documentation/core-api/xarray.rst b/Documentation/core-api/x= array.rst index fcedc5349ace..95a732b5c848 100644 --- a/Documentation/core-api/xarray.rst +++ b/Documentation/core-api/xarray.rst @@ -94,10 +94,10 @@ calling xa_clear_mark(). You can ask whether any ent= ry in the XArray has a particular mark set by calling xa_marked(). =20 You can copy entries out of the XArray into a plain array by calling -xa_extract(). Or you can iterate over the present entries in -the XArray by calling xa_for_each(). You may prefer to use -xa_find() or xa_find_after() to move to the next present -entry in the XArray. +xa_extract(). Or you can iterate over the present entries in the XArray +by calling xa_for_each(), xa_for_each_start() or xa_for_each_range(). +You may prefer to use xa_find() or xa_find_after() to move to the next +present entry in the XArray. =20 Calling xa_store_range() stores the same entry in a range of indices. If you do this, some of the other operations will behave @@ -180,6 +180,8 @@ No lock needed: Takes RCU read lock: * xa_load() * xa_for_each() + * xa_for_each_start() + * xa_for_each_range() * xa_find() * xa_find_after() * xa_extract() diff --git a/include/linux/xarray.h b/include/linux/xarray.h index 86eecbd98e84..a06cb555fe23 100644 --- a/include/linux/xarray.h +++ b/include/linux/xarray.h @@ -445,6 +445,36 @@ static inline bool xa_marked(const struct xarray *xa= , xa_mark_t mark) entry; \ entry =3D xa_find_after(xa, &index, ULONG_MAX, XA_PRESENT)) =20 +/** + * xa_for_each_range() - Iterate over a portion of an XArray. + * @xa: XArray. + * @index: Index of @entry. + * @entry: Entry retrieved from array. + * @start: First index to retrieve from array. + * @last: Last index to retrieve from array. + * + * During the iteration, @entry will have the value of the entry stored + * in @xa at @index. You may modify @index during the iteration if you + * want to skip or reprocess indices. It is safe to modify the array + * during the iteration. At the end of the iteration, @entry will be se= t + * to NULL and @index will have a value less than or equal to max. + * + * xa_for_each_range() is O(n.log(n)) while xas_for_each() is O(n). You= have + * to handle your own locking with xas_for_each(), and if you have to un= lock + * after each iteration, it will also end up being O(n.log(n)). + * xa_for_each_range() will spin if it hits a retry entry; if you intend= to + * see retry entries, you should use the xas_for_each() iterator instead= . + * The xas_for_each() iterator will expand into more inline code than + * xa_for_each_range(). + * + * Context: Any context. Takes and releases the RCU lock. + */ +#define xa_for_each_range(xa, index, entry, start, last) \ + for (index =3D start, \ + entry =3D xa_find(xa, &index, last, XA_PRESENT); \ + entry; \ + entry =3D xa_find_after(xa, &index, last, XA_PRESENT)) + /** * xa_for_each() - Iterate over present entries in an XArray. * @xa: XArray. --=20 2.24.1