From patchwork Thu Apr 27 19:06:39 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sandhya Bankar X-Patchwork-Id: 9705683 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 919AC603F7 for ; Sat, 29 Apr 2017 07:40:21 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 7D72428671 for ; Sat, 29 Apr 2017 07:40:21 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 70B0328681; Sat, 29 Apr 2017 07:40:21 +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 DA77928671 for ; Sat, 29 Apr 2017 07:40:20 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1755429AbdD2HkN (ORCPT ); Sat, 29 Apr 2017 03:40:13 -0400 Received: from mail-pf0-f193.google.com ([209.85.192.193]:32843 "EHLO mail-pf0-f193.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753862AbdD2HkM (ORCPT ); Sat, 29 Apr 2017 03:40:12 -0400 Received: by mail-pf0-f193.google.com with SMTP id b23so4646221pfc.0; Sat, 29 Apr 2017 00:40:12 -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=WeqQnai2M9fWQz/MH7pDHjnFjLzSwDlj6XbNoEA0mxk=; b=dw3l0ta7CgsYk7CVJJJ81ryME9W8UU/4U3MKdp71ELLooDV5RXUPclsfphUZG2Tear K4u2H4oOL9D2m01eGzYGRbFILf+b84njmjAn93nq1ufqnbh/qDI0xo2TKRwT4t8LTgyW 9qk2cFDZYIg7CMkxeGOCHPc0hq2jlK4Gf+se5OhONDqlT2jjPBzGzqD6BCuohyVu6IUm 5hp9CEuIwy7CAJTqtyoxTlzKVFwJLZiooDA+kJq0K2zIbFz1E3cg36yYU708cUspOPOm 6XQM5t+JgyaG7M9xepjKlAQpD8hZj+2na1FvLAshWEyl1eDeDio98TyBYekoNwc4ISHh n/gg== 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=WeqQnai2M9fWQz/MH7pDHjnFjLzSwDlj6XbNoEA0mxk=; b=IZWbePs453zODG0BKVjPHqiR6hAAb4WdDNoL3sYYMRFrnpW8vxHS9+e6TWHckrXVIV E4zPFeX4UB/uS39YqJVxmXealSKkGcOIlSDg7F7ds1V2hKTXanGA2u8cFKSSc16fUM40 sStJ2p3B7gN1u4n6xCEn3NBjs93+3afV37ZtESbOW6v1tVd4yzUlIXIzdt6cFlQ+HUSG 2xx+VHnc55uEaEwZVBe4pyMPClZT91jTGYmJ890nlfkpzepYq3qdLTCQbTrP2Ty2QTh4 g9u5SR5bn68swGFDJIHh5uL1iGpQ1PUj0RH35qUZgkJ7aRpdH9PdvvDE0aJaA3QrpNgD 3P7g== X-Gm-Message-State: AN3rC/7Kv8C2u4jz2cuEc7Iu840OdxudhbxDtWEQdR/qj6L9W+HMOHCg seUFwev31WHznA== X-Received: by 10.84.179.65 with SMTP id a59mr18118748plc.171.1493451611632; Sat, 29 Apr 2017 00:40:11 -0700 (PDT) Received: from localhost.localdomain ([223.229.187.11]) by smtp.gmail.com with ESMTPSA id z5sm14398917pfd.76.2017.04.29.00.40.08 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 29 Apr 2017 00:40:11 -0700 (PDT) Date: Fri, 28 Apr 2017 00:36:39 +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 03/13] idr, radix-tree: Add get_tag_batch function Message-ID: 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 To implement select() on top of the IDR, we need to be able to get the tags which represent the open files in bulk. For this user, it makes sense to get a batch of BITS_PER_LONG tags at a time, and until another user shows up that wants something different, let's enforce that instead of coping with arbitrary offsets. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 6 ++++ include/linux/radix-tree.h | 2 ++ lib/radix-tree.c | 55 ++++++++++++++++++++++++++++++++++++- tools/testing/radix-tree/idr-test.c | 20 ++++++++++++++ tools/testing/radix-tree/test.h | 2 +- 5 files changed, 83 insertions(+), 2 deletions(-) diff --git a/include/linux/idr.h b/include/linux/idr.h index 9f71e63..d43cf01 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -147,6 +147,12 @@ static inline bool idr_tag_get(const struct idr *idr, int id, unsigned int tag) return radix_tree_tag_get(&idr->idr_rt, id, tag); } +static inline unsigned long idr_get_tag_batch(const struct idr *idr, int id, + unsigned int tag) +{ + return radix_tree_get_tag_batch(&idr->idr_rt, id, tag); +} + static inline void idr_init(struct idr *idr) { INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER); diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index 3e57350..f701e0b 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -339,6 +339,8 @@ void radix_tree_iter_tag_set(struct radix_tree_root *, const struct radix_tree_iter *iter, unsigned int tag); void radix_tree_iter_tag_clear(struct radix_tree_root *, const struct radix_tree_iter *iter, unsigned int tag); +unsigned long radix_tree_get_tag_batch(const struct radix_tree_root *, + unsigned long index, unsigned int tag); unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag); diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 6723384..855ac8e 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -181,7 +181,8 @@ static inline void root_tag_clear_all(struct radix_tree_root *root) root->gfp_mask &= (1 << ROOT_TAG_SHIFT) - 1; } -static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag) +static inline bool root_tag_get(const struct radix_tree_root *root, + unsigned tag) { return (__force int)root->gfp_mask & (1 << (tag + ROOT_TAG_SHIFT)); } @@ -1571,6 +1572,58 @@ int radix_tree_tag_get(const struct radix_tree_root *root, } EXPORT_SYMBOL(radix_tree_tag_get); +static unsigned long +__radix_tree_get_tag_batch(const struct radix_tree_root *root, + unsigned long index, unsigned int tag) +{ + struct radix_tree_node *node; + void __rcu **slot = NULL; + bool idr_free = is_idr(root) && (tag == IDR_FREE); + + __radix_tree_lookup(root, index, &node, &slot); + if (!slot) + return idr_free ? ~0UL : 0; + if (!node) + return root_tag_get(root, tag) | (idr_free ? ~1UL : 0); + if (node->shift) + return idr_free ? ~0UL : 0; + return node->tags[tag][(index / BITS_PER_LONG) & + (RADIX_TREE_TAG_LONGS - 1)]; +} + +/** + * radix_tree_get_tag_batch() - get a batch of tags + * @root: radix tree root + * @index: start index of batch + * @tag: tag to get + * + * Get a batch of BITS_PER_LONG tags. The only values of @index + * permitted are multiples of BITS_PER_LONG. + * + * Return: The tags for the next BITS_PER_LONG indices. + */ +unsigned long radix_tree_get_tag_batch(const struct radix_tree_root *root, + unsigned long index, unsigned int tag) +{ + unsigned long bits = 0; + unsigned shift = BITS_PER_LONG > RADIX_TREE_MAP_SIZE ? \ + RADIX_TREE_MAP_SIZE : 0; + + if (WARN_ON_ONCE(index & (BITS_PER_LONG - 1))) + return bits; + + index += BITS_PER_LONG; + for (;;) { + index -= RADIX_TREE_MAP_SIZE; + bits |= __radix_tree_get_tag_batch(root, index, tag); + if (!(index & (BITS_PER_LONG - 1))) + break; + bits <<= shift; + } + + return bits; +} + static inline void __set_iter_shift(struct radix_tree_iter *iter, unsigned int shift) { diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 334ce1c..3f9f429 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -139,6 +139,8 @@ void idr_tag_test(void) DEFINE_IDR(idr); struct item *item; + assert(idr_get_tag_batch(&idr, 0, IDR_FREE) == ~0UL); + for (i = 0; i < 100; i++) { item = item_create(i, 0); assert(idr_alloc(&idr, item, 0, 0, GFP_KERNEL) == i); @@ -146,6 +148,20 @@ void idr_tag_test(void) idr_tag_set(&idr, i, IDR_TEST); } + assert(idr_get_tag_batch(&idr, 0, IDR_FREE) == 0); +#if BITS_PER_LONG == 64 + assert(idr_get_tag_batch(&idr, 0, IDR_TEST) == 0x8102040810204081UL); + assert(idr_get_tag_batch(&idr, 64, IDR_TEST) == 0x408102040UL); +#else + assert(idr_get_tag_batch(&idr, 0, IDR_TEST) == 0x10204081UL); + assert(idr_get_tag_batch(&idr, 32, IDR_TEST) == 0x81020408UL); + assert(idr_get_tag_batch(&idr, 64, IDR_TEST) == 0x08102040UL); + assert(idr_get_tag_batch(&idr, 96, IDR_TEST) == 0x4UL); +#endif + assert((int)idr_get_tag_batch(&idr, 64, IDR_FREE) == 0); + assert(idr_get_tag_batch(&idr, 128, IDR_FREE) == ~0UL); + assert(idr_get_tag_batch(&idr, 128, IDR_TEST) == 0); + for (i = 0; i < 100; i += 14) { assert(idr_tag_get(&idr, i, IDR_TEST)); idr_tag_clear(&idr, i, IDR_TEST); @@ -159,6 +175,10 @@ void idr_tag_test(void) assert(item->index % 14 == 7); } + item_free(idr_remove(&idr, 7), 7); + assert((int)idr_get_tag_batch(&idr, 0, IDR_TEST) == 0x00200000UL); + assert((int)idr_get_tag_batch(&idr, 0, IDR_FREE) == 0x00000080); + idr_for_each(&idr, item_idr_free, &idr); idr_destroy(&idr); } diff --git a/tools/testing/radix-tree/test.h b/tools/testing/radix-tree/test.h index cbabea1..09616ff 100644 --- a/tools/testing/radix-tree/test.h +++ b/tools/testing/radix-tree/test.h @@ -52,7 +52,7 @@ struct item * /* Normally private parts of lib/radix-tree.c */ struct radix_tree_node *entry_to_node(void *ptr); void radix_tree_dump(struct radix_tree_root *root); -int root_tag_get(struct radix_tree_root *root, unsigned int tag); +bool root_tag_get(struct radix_tree_root *root, unsigned int tag); unsigned long node_maxindex(struct radix_tree_node *); unsigned long shift_maxindex(unsigned int shift); int radix_tree_cpu_dead(unsigned int cpu);