From patchwork Thu Apr 27 19:05:27 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sandhya Bankar X-Patchwork-Id: 9705679 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 7D632603F7 for ; Sat, 29 Apr 2017 07:40:12 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 54A7E28673 for ; Sat, 29 Apr 2017 07:40:12 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 34BBB28671; Sat, 29 Apr 2017 07:40:12 +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=-5.7 required=2.0 tests=BAYES_00, DATE_IN_PAST_24_48, DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,FREEMAIL_FROM,RCVD_IN_DNSWL_HI autolearn=ham version=3.3.1 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 9F4E228671 for ; Sat, 29 Apr 2017 07:40:11 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S965607AbdD2HjH (ORCPT ); Sat, 29 Apr 2017 03:39:07 -0400 Received: from mail-pf0-f193.google.com ([209.85.192.193]:33482 "EHLO mail-pf0-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933746AbdD2HjF (ORCPT ); Sat, 29 Apr 2017 03:39:05 -0400 Received: by mail-pf0-f193.google.com with SMTP id b23so4643408pfc.0; Sat, 29 Apr 2017 00:39:05 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20161025; h=date:from:to:subject:message-id:references:mime-version :content-disposition:in-reply-to:user-agent; bh=yJ+5ozO7b89Sd/RG/Tw9k1vzNv1b+hTMnasqov6NT+8=; b=PgTDIm0G8UBwLu5/GTIh8hK/gFdi+C/z3iRDC+t4gQXkEJoOL38cD0IzCNLigBWNcb 8ji25oSxcbwr6636wKEkQr8Bc8fpeGf+cP9mck+IYZeYhha2TK+UXdpbqKif4rifQ2j5 6QYz9vokqdPZsGfB/EcnmfxS02SUI8APdNNzqbtw/QIRboAXCN7QY0RJDJxenVuJ51lF LrDoe0paLSKHPJGPsqi5hsZjJ8IPHE4An2QHrkJMxAPi/NP3Nm8t5Beul5Pj9Q9aGMX6 ogOUdIub/hzQJGepiDmjWGLZs5+1ilDknxVT56LoIdzRqQQ/TGJCY8DhxsetaknnWkqT nGJw== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20161025; h=x-gm-message-state:date:from:to:subject:message-id:references :mime-version:content-disposition:in-reply-to:user-agent; bh=yJ+5ozO7b89Sd/RG/Tw9k1vzNv1b+hTMnasqov6NT+8=; b=YJvJJFYyoyOax9ZQukYwsomO+gZfgowApWy3HXkTUXRbhv2bLg89Gva0RliEsyn6L+ ahhRT1/WZY0dGOhJgIyOuhIh02BTnFHvA6s4VAXOESOnj6jlyZ4LRfssgnjyclPa2f1N WMf+/qYVaFM0TFnwIJvpw/AS0WWM+6IyV9YpbwLTuTAZSnLa3MJCEozKAQmHtV9lkn69 ikD43yiVWb2figvpyxPQGC8whiFVv771IBhrc46NbMajKUl0ncZGfi2jjDo0xGHhv3q7 iYJw6OSTXWFvcGfCTZwFIAGXJjZNGYN4v6EdVL1N21W+zqDd5CwiJ9ezudUiXh/UlSuT eyug== X-Gm-Message-State: AN3rC/74b8iFITQpPrj2p84owXqDNz5mzrXlEvYrP7B6ZlUdAcaJmUuN f0gl1owJA3lR8Q== X-Received: by 10.98.8.21 with SMTP id c21mr16004982pfd.252.1493451544751; Sat, 29 Apr 2017 00:39:04 -0700 (PDT) Received: from localhost.localdomain ([223.229.187.11]) by smtp.gmail.com with ESMTPSA id e72sm8922160pfk.17.2017.04.29.00.39.00 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 29 Apr 2017 00:39:04 -0700 (PDT) Date: Fri, 28 Apr 2017 00:35:27 +0530 From: Sandhya Bankar To: linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org, viro@zeniv.linux.org.uk, mawmilcox@microsoft.com, keescook@chromium.org, adobriyan@gmail.com, re.emese@gmail.com, riel@surriel.com Subject: [PATCH 02/13] idr: Add idr_for_each_entry_tagged() Message-ID: <6304287185465885b2b5cdd5e0274b7e5b4950c6.1493315290.git.bankarsandhya512@gmail.com> References: MIME-Version: 1.0 Content-Disposition: inline In-Reply-To: User-Agent: Mutt/1.5.21 (2010-09-15) Sender: linux-fsdevel-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-fsdevel@vger.kernel.org X-Virus-Scanned: ClamAV using ClamSMTP Add the ability to iterate over tagged entries in the IDR with idr_get_next_tag() and idr_for_each_entry_tagged(). Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 15 ++++++++++++++- lib/idr.c | 30 +++++++++++++++++++++++++++++- tools/testing/radix-tree/idr-test.c | 18 ++++++++++-------- tools/testing/radix-tree/test.c | 9 +++++++-- tools/testing/radix-tree/test.h | 1 + 5 files changed, 61 insertions(+), 12 deletions(-) diff --git a/include/linux/idr.h b/include/linux/idr.h index 7eb4432..9f71e63 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -84,7 +84,8 @@ static inline void idr_set_cursor(struct idr *idr, unsigned int val) int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t); int idr_for_each(const struct idr *, int (*fn)(int id, void *p, void *data), void *data); -void *idr_get_next(struct idr *, int *nextid); +void *idr_get_next(const struct idr *, int *nextid); +void *idr_get_next_tag(const struct idr *, int *nextid, unsigned int tag); void *idr_replace(struct idr *, void *, int id); void idr_destroy(struct idr *); @@ -213,6 +214,18 @@ static inline void *idr_find(const struct idr *idr, int id) entry; \ ++id, (entry) = idr_get_next((idr), &(id))) +/** + * idr_for_each_entry_tagged - iterate over IDs with a set tag + * @idr: IDR handle + * @entry: The pointer stored in @idr + * @id: The index of @entry in @idr + * @tag: tag to search for + */ +#define idr_for_each_entry_tagged(idr, entry, id, tag) \ + for (id = 0; \ + ((entry) = idr_get_next_tag(idr, &(id), (tag))) != NULL; \ + ++id) + /* * IDA - IDR based id allocator, use when translation from id to * pointer isn't necessary. diff --git a/lib/idr.c b/lib/idr.c index b13682b..68e39c3 100644 --- a/lib/idr.c +++ b/lib/idr.c @@ -120,7 +120,7 @@ int idr_for_each(const struct idr *idr, * to the ID of the found value. To use in a loop, the value pointed to by * nextid must be incremented by the user. */ -void *idr_get_next(struct idr *idr, int *nextid) +void *idr_get_next(const struct idr *idr, int *nextid) { struct radix_tree_iter iter; void __rcu **slot; @@ -135,6 +135,34 @@ void *idr_get_next(struct idr *idr, int *nextid) EXPORT_SYMBOL(idr_get_next); /** + * idr_get_next_tag - Find next tagged entry + * @idr: idr handle + * @nextid: Pointer to lowest possible ID to return + * @tag: tag to search for + * + * Returns the next tagged entry in the tree with an ID greater than + * or equal to the value pointed to by @nextid. On exit, @nextid is updated + * to the ID of the found value. To use in a loop, the value pointed to by + * nextid must be incremented by the user. If a NULL entry is tagged, it + * will be returned. + */ +void *idr_get_next_tag(const struct idr *idr, int *nextid, unsigned int tag) +{ + struct radix_tree_iter iter; + void __rcu **slot; + + radix_tree_iter_init(&iter, *nextid); + slot = radix_tree_next_chunk(&idr->idr_rt, &iter, + RADIX_TREE_ITER_TAGGED | tag); + if (!slot) + return NULL; + + *nextid = iter.index; + return rcu_dereference_raw(*slot); +} +EXPORT_UNUSED_SYMBOL(idr_get_next_tag); + +/** * idr_replace - replace pointer for given id * @idr: idr handle * @ptr: New pointer to associate with the ID diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index fd94bee..334ce1c 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -23,19 +23,15 @@ int item_idr_free(int id, void *p, void *data) { - struct item *item = p; - assert(item->index == id); - free(p); - + item_free(p, id); return 0; } void item_idr_remove(struct idr *idr, int id) { struct item *item = idr_find(idr, id); - assert(item->index == id); idr_remove(idr, id); - free(item); + item_free(item, id); } void idr_alloc_test(void) @@ -139,11 +135,13 @@ void idr_null_test(void) void idr_tag_test(void) { - unsigned int i; + int i; DEFINE_IDR(idr); + struct item *item; for (i = 0; i < 100; i++) { - assert(idr_alloc(&idr, NULL, 0, 0, GFP_KERNEL) == i); + item = item_create(i, 0); + assert(idr_alloc(&idr, item, 0, 0, GFP_KERNEL) == i); if (i % 7 == 0) idr_tag_set(&idr, i, IDR_TEST); } @@ -157,6 +155,10 @@ void idr_tag_test(void) assert(idr_tag_get(&idr, i, IDR_TEST) == (i % 14 == 7)); } + idr_for_each_entry_tagged(&idr, item, i, IDR_TEST) { + assert(item->index % 14 == 7); + } + idr_for_each(&idr, item_idr_free, &idr); idr_destroy(&idr); } diff --git a/tools/testing/radix-tree/test.c b/tools/testing/radix-tree/test.c index 1a257d7..74f8e5c 100644 --- a/tools/testing/radix-tree/test.c +++ b/tools/testing/radix-tree/test.c @@ -62,13 +62,18 @@ void item_sanity(struct item *item, unsigned long index) assert((item->index | mask) == (index | mask)); } +void item_free(struct item *item, unsigned long index) +{ + item_sanity(item, index); + free(item); +} + int item_delete(struct radix_tree_root *root, unsigned long index) { struct item *item = radix_tree_delete(root, index); if (item) { - item_sanity(item, index); - free(item); + item_free(item, index); return 1; } return 0; diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h index 0f8220c..cbabea1 100644 --- a/tools/testing/radix-tree/test.h +++ b/tools/testing/radix-tree/test.h @@ -13,6 +13,7 @@ struct item { int item_insert(struct radix_tree_root *root, unsigned long index); int item_insert_order(struct radix_tree_root *root, unsigned long index, unsigned order); +void item_free(struct item *item, unsigned long index); int item_delete(struct radix_tree_root *root, unsigned long index); struct item *item_lookup(struct radix_tree_root *root, unsigned long index);