From patchwork Thu Apr 27 19:07:59 2017 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Sandhya Bankar X-Patchwork-Id: 9705687 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 5868E602BE for ; Sat, 29 Apr 2017 07:41:34 +0000 (UTC) Received: from mail.wl.linuxfoundation.org (localhost [127.0.0.1]) by mail.wl.linuxfoundation.org (Postfix) with ESMTP id 431B728671 for ; Sat, 29 Apr 2017 07:41:34 +0000 (UTC) Received: by mail.wl.linuxfoundation.org (Postfix, from userid 486) id 36D6328681; Sat, 29 Apr 2017 07:41:34 +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.2 required=2.0 tests=BAYES_00, DATE_IN_PAST_24_48, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, FREEMAIL_FROM, RCVD_IN_DNSWL_HI, RCVD_IN_SORBS_SPAM 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 7F3AA28671 for ; Sat, 29 Apr 2017 07:41:33 +0000 (UTC) Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S969319AbdD2Hl1 (ORCPT ); Sat, 29 Apr 2017 03:41:27 -0400 Received: from mail-pg0-f65.google.com ([74.125.83.65]:36728 "EHLO mail-pg0-f65.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753862AbdD2Hl0 (ORCPT ); Sat, 29 Apr 2017 03:41:26 -0400 Received: by mail-pg0-f65.google.com with SMTP id v1so8516976pgv.3; Sat, 29 Apr 2017 00:41:26 -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=4QjBZCw6yD/NKiHDAO/etUONEzZag4d4FoexgmeuJUE=; b=JnP6a+4HlLjMqRSHJ/ZPD5kForkruOUWW5gB0ItL/tq+svqpjD+m4TqYuP/tdHSAl4 iqIJ17YpZgGUCYqJEJ2hTiv3TBBu/zGhOmWANMd38XAFLVJMdmou9r7oM3sxHVMtTdcj 4BMOvP0BBGR03+g+dWT+/YL+gFic/XUplU8n7pJO/OMfzX73X5+EX1peezwiXv3gbk1q igGUL9DGF0NL/6E5IXr3NFl2gC44C+j1rLqNalJa7nHMGebTvePRy2LHfuxwk8mgBOQ4 v/pFLkZKY5Dh2VB0ZCJaVLwIgqEgDRIfHLS9OfnmkLNGTulgN7oD2Y5GEoZCY6lQE9nM aHgw== 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=4QjBZCw6yD/NKiHDAO/etUONEzZag4d4FoexgmeuJUE=; b=VeBAvyNp9xJ9zNMrkmT+YPhhZe6pB8r/jyo4hSeWBACdXTKvhUkvKjHBPTcUi8RPri /TTY9CPmOdLB1o6MdSO34EoBipbBA/nN2HGXfJLrukXAocrNUBH4YNd7fOoQROVdEbl1 LZyHYV3ZHYL6XXdEHFsbCyu4CPV4iU+jOdE7/MKrRQY3l7QIukxDddwG1LhhCDktN6+v 7GrO1FqwVySHwz8itG6N8i8iXsmgXJE+/tTPBF02Mrr25StA0IDttnYWpXiR33fl8lYz vnKJE9sPq1vf5RL60Ut4U0051amo1FMVIa4H1G8uxqnnT5Myx/R7lksbLQgd4qNqzRh/ 3xYA== X-Gm-Message-State: AN3rC/4h6JhCDgeluDnv6NPWMwzSw2xbCM2CL1ms9cQBYjZkqah6uTcf rEbWVDO8gt/qrw== X-Received: by 10.99.2.84 with SMTP id 81mr15880400pgc.17.1493451685811; Sat, 29 Apr 2017 00:41:25 -0700 (PDT) Received: from localhost.localdomain ([223.229.187.11]) by smtp.gmail.com with ESMTPSA id j73sm14262720pfe.108.2017.04.29.00.41.21 (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Sat, 29 Apr 2017 00:41:25 -0700 (PDT) Date: Fri, 28 Apr 2017 00:37:59 +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 04/13] idr, radix-tree: Implement copy_preload 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 In the file descriptor table duplication code (called at fork()), we need to duplicate an IDR. But we have to do it under a lock (so another thread doesn't open/close a fd in the middle), and there's no suitable preload operation for this today. Adding just idr_copy_preload() isn't enough as another thread could grow the fd table between starting the preload and acquiring the lock. We also need idr_check_preload() to be called after acquiring the lock. Signed-off-by: Matthew Wilcox --- include/linux/idr.h | 32 +++++++++++ include/linux/radix-tree.h | 3 ++ lib/radix-tree.c | 83 +++++++++++++++++++++++++++++ tools/testing/radix-tree/idr-test.c | 24 +++++++++ tools/testing/radix-tree/linux/radix-tree.h | 2 + tools/testing/radix-tree/main.c | 38 +++++++++++++ 6 files changed, 182 insertions(+) diff --git a/include/linux/idr.h b/include/linux/idr.h index d43cf01..eed1c1a 100644 --- a/include/linux/idr.h +++ b/include/linux/idr.h @@ -166,6 +166,38 @@ static inline bool idr_is_empty(const struct idr *idr) } /** + * idr_copy_preload - preload for idr_copy() + * @src: IDR to be copied from + * @gfp: Allocation mask to use for preloading + * + * Preallocates enough memory for a call to idr_copy(). This function + * returns with preemption disabled. Call idr_preload_end() once the + * copy has completed. + * + * Return: -ENOMEM if the memory could not be allocated. + */ +static inline int idr_copy_preload(const struct idr *src, gfp_t gfp) +{ + return radix_tree_copy_preload(&src->idr_rt, gfp); +} + +/** + * idr_check_preload - Check the preload is still sufficient + * @src: IDR to be copied from + * + * Between the successful allocation of memory and acquiring the lock that + * protects @src, the IDR may have expanded. If this function returns + * false, more memory needs to be preallocated. + * + * Return: true if enough memory remains allocated, false to retry the + * preallocation. + */ +static inline bool idr_check_preload(const struct idr *src) +{ + return radix_tree_check_preload(&src->idr_rt); +} + +/** * idr_preload_end - end preload section started with idr_preload() * * Each idr_preload() should be matched with an invocation of this diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index f701e0b..f53d004 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -354,6 +354,9 @@ static inline void radix_tree_preload_end(void) preempt_enable(); } +int radix_tree_copy_preload(const struct radix_tree_root *, gfp_t); +bool radix_tree_check_preload(const struct radix_tree_root *); + int radix_tree_split_preload(unsigned old_order, unsigned new_order, gfp_t); int radix_tree_split(struct radix_tree_root *, unsigned long index, unsigned new_order); diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 855ac8e..c1d75224 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -277,6 +277,55 @@ static unsigned long next_index(unsigned long index, return (index & ~node_maxindex(node)) + (offset << node->shift); } +/** + * radix_tree_count_nodes - Returns the number of nodes in this tree + * @root: radix tree root + * + * This routine does not examine every node in the tree; it assumes that + * all entries in the tree at level 1 are nodes. It will overestimate + * the number of nodes in the tree in the presence of entries of order + * RADIX_TREE_MAP_SHIFT or higher. + */ +static unsigned long radix_tree_count_nodes(const struct radix_tree_root *root) +{ + struct radix_tree_node *node, *child; + unsigned long n = 1; + void *entry = rcu_dereference_raw(root->rnode); + unsigned int offset = 0; + + if (!radix_tree_is_internal_node(entry)) + return 0; + + node = entry_to_node(entry); + if (!node->shift) + return n; + + n += node->count; + if (node->shift == RADIX_TREE_MAP_SHIFT) + return n; + + while (node) { + if (offset == RADIX_TREE_MAP_SIZE) { + offset = node->offset + 1; + node = node->parent; + continue; + } + + entry = rcu_dereference_raw(node->slots[offset]); + offset++; + if (!radix_tree_is_internal_node(entry)) + continue; + child = entry_to_node(entry); + n += child->count; + if (node->shift <= 2 * RADIX_TREE_MAP_SHIFT) + continue; + offset = 0; + node = child; + } + + return n; +} + #ifndef __KERNEL__ static void dump_node(struct radix_tree_node *node, unsigned long index) { @@ -530,6 +579,40 @@ int radix_tree_maybe_preload(gfp_t gfp_mask) } EXPORT_SYMBOL(radix_tree_maybe_preload); +/** + * radix_tree_copy_preload - preload for radix_tree_copy() + * @src: radix tree root to be copied from + * @gfp: Allocation mask to use for preloading + * + * Preallocates enough memory for a call to radix_tree_copy(). This function + * returns with preemption disabled. Call radix_tree_preload_end() once the + * copy has completed. + * + * Return: -ENOMEM if the memory could not be allocated. + */ +int radix_tree_copy_preload(const struct radix_tree_root *src, gfp_t gfp_mask) +{ + return __radix_tree_preload(gfp_mask, radix_tree_count_nodes(src)); +} + +/** + * radix_tree_check_preload - Check the preload is still sufficient + * @src: radix tree to be copied from + * @cookie: Cookie returned from radix_tree_copy_preload() + * + * Between the successful allocation of memory and acquiring the lock that + * protects @src, the radix tree may have expanded. Call this function + * to see if the preallocation needs to be expanded too. + * + * Return: true if enough memory remains allocated, false if it does not + * suffice. + */ +bool radix_tree_check_preload(const struct radix_tree_root *src) +{ + struct radix_tree_preload *rtp = this_cpu_ptr(&radix_tree_preloads); + return rtp->nr >= radix_tree_count_nodes(src); +} + #ifdef CONFIG_RADIX_TREE_MULTIORDER /* * Preload with enough objects to ensure that we can split a single entry diff --git a/tools/testing/radix-tree/idr-test.c b/tools/testing/radix-tree/idr-test.c index 3f9f429..e8d5386 100644 --- a/tools/testing/radix-tree/idr-test.c +++ b/tools/testing/radix-tree/idr-test.c @@ -225,6 +225,29 @@ void idr_get_next_test(void) idr_destroy(&idr); } +void idr_copy_test(void) +{ + DEFINE_IDR(src); + DEFINE_IDR(dst); + int i; + void *p; + + for (i = 0; i < 10000; i++) { + struct item *item = item_create(i, 0); + assert(idr_alloc(&src, item, 0, 20000, GFP_KERNEL) == i); + } + + idr_copy_preload(&src, GFP_KERNEL); + idr_for_each_entry(&src, p, i) { + assert(idr_alloc(&dst, p, i, i + 1, GFP_NOWAIT) == i); + } + idr_preload_end(); + + idr_for_each(&src, item_idr_free, NULL); + idr_destroy(&src); + idr_destroy(&dst); +} + void idr_checks(void) { unsigned long i; @@ -276,6 +299,7 @@ void idr_checks(void) idr_tag_test(); idr_nowait_test(); idr_get_next_test(); + idr_copy_test(); } /* diff --git a/tools/testing/radix-tree/linux/radix-tree.h b/tools/testing/radix-tree/linux/radix-tree.h index bf1bb23..0c5885e 100644 --- a/tools/testing/radix-tree/linux/radix-tree.h +++ b/tools/testing/radix-tree/linux/radix-tree.h @@ -4,6 +4,8 @@ #include "generated/map-shift.h" #include "../../../../include/linux/radix-tree.h" +unsigned long radix_tree_count_nodes(const struct radix_tree_root *root); + extern int kmalloc_verbose; extern int test_verbose; diff --git a/tools/testing/radix-tree/main.c b/tools/testing/radix-tree/main.c index bc9a784..a7504e2 100644 --- a/tools/testing/radix-tree/main.c +++ b/tools/testing/radix-tree/main.c @@ -11,6 +11,42 @@ #include "test.h" #include "regression.h" +static void count_node_check(void) +{ + unsigned long i, j, k; + RADIX_TREE(tree, GFP_KERNEL); + + assert(radix_tree_empty(&tree)); + assert(radix_tree_count_nodes(&tree) == 0); + assert(item_insert(&tree, 0) == 0); + assert(radix_tree_count_nodes(&tree) == 0); + + for (i = 1; i < RADIX_TREE_MAP_SIZE; i++) { + assert(item_insert(&tree, i) == 0); + assert(radix_tree_count_nodes(&tree) == 1); + } + + j = 3; + k = 3; + for (i = RADIX_TREE_MAP_SIZE; i < i * RADIX_TREE_MAP_SIZE; + i *= RADIX_TREE_MAP_SIZE) { + assert(item_insert(&tree, i) == 0); + assert(radix_tree_count_nodes(&tree) == j); + j += k; + k++; + } + + assert(item_insert(&tree, i) == 0); + assert(radix_tree_count_nodes(&tree) == j); + + item_kill_tree(&tree); +} + +void basic_checks(void) +{ + count_node_check(); +} + void __gang_check(unsigned long middle, long down, long up, int chunk, int hop) { long idx; @@ -362,6 +398,8 @@ int main(int argc, char **argv) rcu_register_thread(); radix_tree_init(); + basic_checks(); + regression1_test(); regression2_test(); regression3_test();