From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S933641Ab3HGVe2 (ORCPT ); Wed, 7 Aug 2013 17:34:28 -0400 Received: from mga09.intel.com ([134.134.136.24]:1466 "EHLO mga09.intel.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S933318Ab3HGVe0 (ORCPT ); Wed, 7 Aug 2013 17:34:26 -0400 X-ExtLoop1: 1 X-IronPort-AV: E=Sophos;i="4.89,835,1367996400"; d="scan'208";a="359251389" From: "Kirill A. Shutemov" To: Jan Kara Cc: "Kirill A. Shutemov" , Jan Kara , Andrea Arcangeli , Andrew Morton , Al Viro , Hugh Dickins , Wu Fengguang , Mel Gorman , linux-mm@kvack.org, Andi Kleen , Matthew Wilcox , "Kirill A. Shutemov" , Hillf Danton , Dave Hansen , Ning Qu , linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org In-Reply-To: <20130807203650.GI26516@quack.suse.cz> References: <1375582645-29274-1-git-send-email-kirill.shutemov@linux.intel.com> <1375582645-29274-2-git-send-email-kirill.shutemov@linux.intel.com> <20130805111739.GA25691@quack.suse.cz> <20130807163236.0F17DE0090@blue.fi.intel.com> <20130807200032.GE26516@quack.suse.cz> <20130807202403.7BCEEE0090@blue.fi.intel.com> <20130807203650.GI26516@quack.suse.cz> Subject: Re: [PATCH 01/23] radix-tree: implement preload for multiple contiguous elements Content-Transfer-Encoding: 7bit Message-Id: <20130807213736.AC732E0090@blue.fi.intel.com> Date: Thu, 8 Aug 2013 00:37:36 +0300 (EEST) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Jan Kara wrote: > On Wed 07-08-13 23:24:03, Kirill A. Shutemov wrote: > > Jan Kara wrote: > > > On Wed 07-08-13 19:32:36, Kirill A. Shutemov wrote: > > > > Jan Kara wrote: > > > > > On Sun 04-08-13 05:17:03, Kirill A. Shutemov wrote: > > > > > > From: "Kirill A. Shutemov" > > > > > > > > > > > > The radix tree is variable-height, so an insert operation not only has > > > > > > to build the branch to its corresponding item, it also has to build the > > > > > > branch to existing items if the size has to be increased (by > > > > > > radix_tree_extend). > > > > > > > > > > > > The worst case is a zero height tree with just a single item at index 0, > > > > > > and then inserting an item at index ULONG_MAX. This requires 2 new branches > > > > > > of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. > > > > > > > > > > > > Radix tree is usually protected by spin lock. It means we want to > > > > > > pre-allocate required memory before taking the lock. > > > > > > > > > > > > Currently radix_tree_preload() only guarantees enough nodes to insert > > > > > > one element. It's a hard limit. For transparent huge page cache we want > > > > > > to insert HPAGE_PMD_NR (512 on x86-64) entries to address_space at once. > > > > > > > > > > > > This patch introduces radix_tree_preload_count(). It allows to > > > > > > preallocate nodes enough to insert a number of *contiguous* elements. > > > > > > The feature costs about 5KiB per-CPU, details below. > > > > > > > > > > > > Worst case for adding N contiguous items is adding entries at indexes > > > > > > (ULONG_MAX - N) to ULONG_MAX. It requires nodes to insert single worst-case > > > > > > item plus extra nodes if you cross the boundary from one node to the next. > > > > > > > > > > > > Preload uses per-CPU array to store nodes. The total cost of preload is > > > > > > "array size" * sizeof(void*) * NR_CPUS. We want to increase array size > > > > > > to be able to handle 512 entries at once. > > > > > > > > > > > > Size of array depends on system bitness and on RADIX_TREE_MAP_SHIFT. > > > > > > > > > > > > We have three possible RADIX_TREE_MAP_SHIFT: > > > > > > > > > > > > #ifdef __KERNEL__ > > > > > > #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) > > > > > > #else > > > > > > #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ > > > > > > #endif > > > > > > > > > > > > On 64-bit system: > > > > > > For RADIX_TREE_MAP_SHIFT=3, old array size is 43, new is 107. > > > > > > For RADIX_TREE_MAP_SHIFT=4, old array size is 31, new is 63. > > > > > > For RADIX_TREE_MAP_SHIFT=6, old array size is 21, new is 30. > > > > > > > > > > > > On 32-bit system: > > > > > > For RADIX_TREE_MAP_SHIFT=3, old array size is 21, new is 84. > > > > > > For RADIX_TREE_MAP_SHIFT=4, old array size is 15, new is 46. > > > > > > For RADIX_TREE_MAP_SHIFT=6, old array size is 11, new is 19. > > > > > > > > > > > > On most machines we will have RADIX_TREE_MAP_SHIFT=6. In this case, > > > > > > on 64-bit system the per-CPU feature overhead is > > > > > > for preload array: > > > > > > (30 - 21) * sizeof(void*) = 72 bytes > > > > > > plus, if the preload array is full > > > > > > (30 - 21) * sizeof(struct radix_tree_node) = 9 * 560 = 5040 bytes > > > > > > total: 5112 bytes > > > > > > > > > > > > on 32-bit system the per-CPU feature overhead is > > > > > > for preload array: > > > > > > (19 - 11) * sizeof(void*) = 32 bytes > > > > > > plus, if the preload array is full > > > > > > (19 - 11) * sizeof(struct radix_tree_node) = 8 * 296 = 2368 bytes > > > > > > total: 2400 bytes > > > > > > > > > > > > Since only THP uses batched preload at the moment, we disable (set max > > > > > > preload to 1) it if !CONFIG_TRANSPARENT_HUGEPAGE_PAGECACHE. This can be > > > > > > changed in the future. > > > > > > > > > > > > Signed-off-by: Matthew Wilcox > > > > > > Signed-off-by: Kirill A. Shutemov > > > > > > Acked-by: Dave Hansen > > > > > > --- > > > > > > include/linux/radix-tree.h | 11 +++++++++++ > > > > > > lib/radix-tree.c | 41 ++++++++++++++++++++++++++++++++--------- > > > > > > 2 files changed, 43 insertions(+), 9 deletions(-) > > > > > ... > > > > > > diff --git a/lib/radix-tree.c b/lib/radix-tree.c > > > > > > index 7811ed3..99ab73c 100644 > > > > > > --- a/lib/radix-tree.c > > > > > > +++ b/lib/radix-tree.c > > > > > > @@ -82,16 +82,24 @@ static struct kmem_cache *radix_tree_node_cachep; > > > > > > * The worst case is a zero height tree with just a single item at index 0, > > > > > > * and then inserting an item at index ULONG_MAX. This requires 2 new branches > > > > > > * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. > > > > > > + * > > > > > > + * Worst case for adding N contiguous items is adding entries at indexes > > > > > > + * (ULONG_MAX - N) to ULONG_MAX. It requires nodes to insert single worst-case > > > > > > + * item plus extra nodes if you cross the boundary from one node to the next. > > > > > > + * > > > > > > * Hence: > > > > > > */ > > > > > > -#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1) > > > > > > +#define RADIX_TREE_PRELOAD_MIN (RADIX_TREE_MAX_PATH * 2 - 1) > > > > > > +#define RADIX_TREE_PRELOAD_MAX \ > > > > > > + (RADIX_TREE_PRELOAD_MIN + \ > > > > > > + DIV_ROUND_UP(RADIX_TREE_PRELOAD_NR - 1, RADIX_TREE_MAP_SIZE)) > > > > > Umm, is this really correct? I see two problems: > > > > > 1) You may need internal tree nodes at various levels but you seem to > > > > > account only for the level 1. > > > > > 2) The rounding doesn't seem right because RADIX_TREE_MAP_SIZE+2 nodes may > > > > > require 3 nodes at level 1 if the indexes are like: > > > > > i_0 | i_1 .. i_{RADIX_TREE_MAP_SIZE} | i_{RADIX_TREE_MAP_SIZE+1} > > > > > ^ ^ > > > > > node boundary node boundary > > > > > > > > My bad. Let's try to calculate once again. > > > > > > > > We want to insert N contiguous items without restriction on alignment. > > > > > > > > Let's limit N <= 1UL << (2 * RADIX_TREE_MAP_SHIFT), without > > > > CONFIG_BASE_SMALL it's 4096. It will simplify calculation a bit. > > > > > > > > Worst case scenario, I can imagine, is tree with only one element at index > > > > 0 and we add N items where at least one index requires max tree high and > > > > we cross boundary between items in root node. > > > > > > > > Basically, at least one index is less then > > > > > > > > 1UL << ((RADIX_TREE_MAX_PATH - 1) * RADIX_TREE_MAP_SHIFT) > > > > > > > > and one equal or more. > > > > > > > > In this case we need: > > > > > > > > - RADIX_TREE_MAX_PATH nodes to build new path to item with index 0; > > > > - DIV_ROUND_UP(N, RADIX_TREE_MAP_SIZE) nodes for last level nodes for new > > > > items; > > > Here, I think you need to count with > > > DIV_ROUND_UP(N + RADIX_TREE_MAP_SIZE - 1, RADIX_TREE_MAP_SIZE) to propely > > > account for the situation b) I described. > > > > It's not obvious for me why it's needed. Since we limit N, we can cross > > second (or above) level node boundary only once. > > > > I've tried to confirm the math with my kvm (see *ugly* patch below) and > > I was not able to find anything that is not covered. > > > > Could you demonstrate the case you are talking about. > Sure. So let RADIX_TREE_MAP_SHIFT be 6 (i.e. RADIX_TREE_MAP_SIZE == 64). > Let's have radix tree with single element from index 0. We insert 66 elements > starting from index 127. So for nodes at the last level we need - node for > index 127, node for indexes 128 .. 191, node for index 192. That is > together three nodes. But DIV_ROUND_UP(66, 64) = 2. The problem happens > because starting index 127 isn't multiple of RADIX_TREE_MAP_SIZE so we can > have partially used nodes both at the beginning and at the end of the > range. I see. Looks like you are correct. So with patch in previous mail, it should be triable if we set RADIX_TREE_PRELOAD_NR to 514 and off to (1UL << ((RADIX_TREE_MAX_PATH - 1) * RADIX_TREE_MAP_SHIFT)) - RADIX_TREE_MAP_SIZE - 1 In this case it should use 39 nodes, but it uses only 38. I can't understand why. :( -- Kirill A. Shutemov From mboxrd@z Thu Jan 1 00:00:00 1970 From: "Kirill A. Shutemov" Subject: Re: [PATCH 01/23] radix-tree: implement preload for multiple contiguous elements Date: Thu, 8 Aug 2013 00:37:36 +0300 (EEST) Message-ID: <20130807213736.AC732E0090@blue.fi.intel.com> References: <1375582645-29274-1-git-send-email-kirill.shutemov@linux.intel.com> <1375582645-29274-2-git-send-email-kirill.shutemov@linux.intel.com> <20130805111739.GA25691@quack.suse.cz> <20130807163236.0F17DE0090@blue.fi.intel.com> <20130807200032.GE26516@quack.suse.cz> <20130807202403.7BCEEE0090@blue.fi.intel.com> <20130807203650.GI26516@quack.suse.cz> Content-Transfer-Encoding: 7bit Cc: "Kirill A. Shutemov" , Jan Kara , Andrea Arcangeli , Andrew Morton , Al Viro , Hugh Dickins , Wu Fengguang , Mel Gorman , linux-mm@kvack.org, Andi Kleen , Matthew Wilcox , "Kirill A. Shutemov" , Hillf Danton , Dave Hansen , Ning Qu , linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org To: Jan Kara Return-path: In-Reply-To: <20130807203650.GI26516@quack.suse.cz> Sender: owner-linux-mm@kvack.org List-Id: linux-fsdevel.vger.kernel.org Jan Kara wrote: > On Wed 07-08-13 23:24:03, Kirill A. Shutemov wrote: > > Jan Kara wrote: > > > On Wed 07-08-13 19:32:36, Kirill A. Shutemov wrote: > > > > Jan Kara wrote: > > > > > On Sun 04-08-13 05:17:03, Kirill A. Shutemov wrote: > > > > > > From: "Kirill A. Shutemov" > > > > > > > > > > > > The radix tree is variable-height, so an insert operation not only has > > > > > > to build the branch to its corresponding item, it also has to build the > > > > > > branch to existing items if the size has to be increased (by > > > > > > radix_tree_extend). > > > > > > > > > > > > The worst case is a zero height tree with just a single item at index 0, > > > > > > and then inserting an item at index ULONG_MAX. This requires 2 new branches > > > > > > of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. > > > > > > > > > > > > Radix tree is usually protected by spin lock. It means we want to > > > > > > pre-allocate required memory before taking the lock. > > > > > > > > > > > > Currently radix_tree_preload() only guarantees enough nodes to insert > > > > > > one element. It's a hard limit. For transparent huge page cache we want > > > > > > to insert HPAGE_PMD_NR (512 on x86-64) entries to address_space at once. > > > > > > > > > > > > This patch introduces radix_tree_preload_count(). It allows to > > > > > > preallocate nodes enough to insert a number of *contiguous* elements. > > > > > > The feature costs about 5KiB per-CPU, details below. > > > > > > > > > > > > Worst case for adding N contiguous items is adding entries at indexes > > > > > > (ULONG_MAX - N) to ULONG_MAX. It requires nodes to insert single worst-case > > > > > > item plus extra nodes if you cross the boundary from one node to the next. > > > > > > > > > > > > Preload uses per-CPU array to store nodes. The total cost of preload is > > > > > > "array size" * sizeof(void*) * NR_CPUS. We want to increase array size > > > > > > to be able to handle 512 entries at once. > > > > > > > > > > > > Size of array depends on system bitness and on RADIX_TREE_MAP_SHIFT. > > > > > > > > > > > > We have three possible RADIX_TREE_MAP_SHIFT: > > > > > > > > > > > > #ifdef __KERNEL__ > > > > > > #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) > > > > > > #else > > > > > > #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ > > > > > > #endif > > > > > > > > > > > > On 64-bit system: > > > > > > For RADIX_TREE_MAP_SHIFT=3, old array size is 43, new is 107. > > > > > > For RADIX_TREE_MAP_SHIFT=4, old array size is 31, new is 63. > > > > > > For RADIX_TREE_MAP_SHIFT=6, old array size is 21, new is 30. > > > > > > > > > > > > On 32-bit system: > > > > > > For RADIX_TREE_MAP_SHIFT=3, old array size is 21, new is 84. > > > > > > For RADIX_TREE_MAP_SHIFT=4, old array size is 15, new is 46. > > > > > > For RADIX_TREE_MAP_SHIFT=6, old array size is 11, new is 19. > > > > > > > > > > > > On most machines we will have RADIX_TREE_MAP_SHIFT=6. In this case, > > > > > > on 64-bit system the per-CPU feature overhead is > > > > > > for preload array: > > > > > > (30 - 21) * sizeof(void*) = 72 bytes > > > > > > plus, if the preload array is full > > > > > > (30 - 21) * sizeof(struct radix_tree_node) = 9 * 560 = 5040 bytes > > > > > > total: 5112 bytes > > > > > > > > > > > > on 32-bit system the per-CPU feature overhead is > > > > > > for preload array: > > > > > > (19 - 11) * sizeof(void*) = 32 bytes > > > > > > plus, if the preload array is full > > > > > > (19 - 11) * sizeof(struct radix_tree_node) = 8 * 296 = 2368 bytes > > > > > > total: 2400 bytes > > > > > > > > > > > > Since only THP uses batched preload at the moment, we disable (set max > > > > > > preload to 1) it if !CONFIG_TRANSPARENT_HUGEPAGE_PAGECACHE. This can be > > > > > > changed in the future. > > > > > > > > > > > > Signed-off-by: Matthew Wilcox > > > > > > Signed-off-by: Kirill A. Shutemov > > > > > > Acked-by: Dave Hansen > > > > > > --- > > > > > > include/linux/radix-tree.h | 11 +++++++++++ > > > > > > lib/radix-tree.c | 41 ++++++++++++++++++++++++++++++++--------- > > > > > > 2 files changed, 43 insertions(+), 9 deletions(-) > > > > > ... > > > > > > diff --git a/lib/radix-tree.c b/lib/radix-tree.c > > > > > > index 7811ed3..99ab73c 100644 > > > > > > --- a/lib/radix-tree.c > > > > > > +++ b/lib/radix-tree.c > > > > > > @@ -82,16 +82,24 @@ static struct kmem_cache *radix_tree_node_cachep; > > > > > > * The worst case is a zero height tree with just a single item at index 0, > > > > > > * and then inserting an item at index ULONG_MAX. This requires 2 new branches > > > > > > * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. > > > > > > + * > > > > > > + * Worst case for adding N contiguous items is adding entries at indexes > > > > > > + * (ULONG_MAX - N) to ULONG_MAX. It requires nodes to insert single worst-case > > > > > > + * item plus extra nodes if you cross the boundary from one node to the next. > > > > > > + * > > > > > > * Hence: > > > > > > */ > > > > > > -#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1) > > > > > > +#define RADIX_TREE_PRELOAD_MIN (RADIX_TREE_MAX_PATH * 2 - 1) > > > > > > +#define RADIX_TREE_PRELOAD_MAX \ > > > > > > + (RADIX_TREE_PRELOAD_MIN + \ > > > > > > + DIV_ROUND_UP(RADIX_TREE_PRELOAD_NR - 1, RADIX_TREE_MAP_SIZE)) > > > > > Umm, is this really correct? I see two problems: > > > > > 1) You may need internal tree nodes at various levels but you seem to > > > > > account only for the level 1. > > > > > 2) The rounding doesn't seem right because RADIX_TREE_MAP_SIZE+2 nodes may > > > > > require 3 nodes at level 1 if the indexes are like: > > > > > i_0 | i_1 .. i_{RADIX_TREE_MAP_SIZE} | i_{RADIX_TREE_MAP_SIZE+1} > > > > > ^ ^ > > > > > node boundary node boundary > > > > > > > > My bad. Let's try to calculate once again. > > > > > > > > We want to insert N contiguous items without restriction on alignment. > > > > > > > > Let's limit N <= 1UL << (2 * RADIX_TREE_MAP_SHIFT), without > > > > CONFIG_BASE_SMALL it's 4096. It will simplify calculation a bit. > > > > > > > > Worst case scenario, I can imagine, is tree with only one element at index > > > > 0 and we add N items where at least one index requires max tree high and > > > > we cross boundary between items in root node. > > > > > > > > Basically, at least one index is less then > > > > > > > > 1UL << ((RADIX_TREE_MAX_PATH - 1) * RADIX_TREE_MAP_SHIFT) > > > > > > > > and one equal or more. > > > > > > > > In this case we need: > > > > > > > > - RADIX_TREE_MAX_PATH nodes to build new path to item with index 0; > > > > - DIV_ROUND_UP(N, RADIX_TREE_MAP_SIZE) nodes for last level nodes for new > > > > items; > > > Here, I think you need to count with > > > DIV_ROUND_UP(N + RADIX_TREE_MAP_SIZE - 1, RADIX_TREE_MAP_SIZE) to propely > > > account for the situation b) I described. > > > > It's not obvious for me why it's needed. Since we limit N, we can cross > > second (or above) level node boundary only once. > > > > I've tried to confirm the math with my kvm (see *ugly* patch below) and > > I was not able to find anything that is not covered. > > > > Could you demonstrate the case you are talking about. > Sure. So let RADIX_TREE_MAP_SHIFT be 6 (i.e. RADIX_TREE_MAP_SIZE == 64). > Let's have radix tree with single element from index 0. We insert 66 elements > starting from index 127. So for nodes at the last level we need - node for > index 127, node for indexes 128 .. 191, node for index 192. That is > together three nodes. But DIV_ROUND_UP(66, 64) = 2. The problem happens > because starting index 127 isn't multiple of RADIX_TREE_MAP_SIZE so we can > have partially used nodes both at the beginning and at the end of the > range. I see. Looks like you are correct. So with patch in previous mail, it should be triable if we set RADIX_TREE_PRELOAD_NR to 514 and off to (1UL << ((RADIX_TREE_MAX_PATH - 1) * RADIX_TREE_MAP_SHIFT)) - RADIX_TREE_MAP_SIZE - 1 In this case it should use 39 nodes, but it uses only 38. I can't understand why. :( -- Kirill A. Shutemov -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from psmtp.com (na3sys010amx139.postini.com [74.125.245.139]) by kanga.kvack.org (Postfix) with SMTP id 2B6AE6B0032 for ; Wed, 7 Aug 2013 17:34:27 -0400 (EDT) From: "Kirill A. Shutemov" In-Reply-To: <20130807203650.GI26516@quack.suse.cz> References: <1375582645-29274-1-git-send-email-kirill.shutemov@linux.intel.com> <1375582645-29274-2-git-send-email-kirill.shutemov@linux.intel.com> <20130805111739.GA25691@quack.suse.cz> <20130807163236.0F17DE0090@blue.fi.intel.com> <20130807200032.GE26516@quack.suse.cz> <20130807202403.7BCEEE0090@blue.fi.intel.com> <20130807203650.GI26516@quack.suse.cz> Subject: Re: [PATCH 01/23] radix-tree: implement preload for multiple contiguous elements Content-Transfer-Encoding: 7bit Message-Id: <20130807213736.AC732E0090@blue.fi.intel.com> Date: Thu, 8 Aug 2013 00:37:36 +0300 (EEST) Sender: owner-linux-mm@kvack.org List-ID: To: Jan Kara Cc: "Kirill A. Shutemov" , Andrea Arcangeli , Andrew Morton , Al Viro , Hugh Dickins , Wu Fengguang , Mel Gorman , linux-mm@kvack.org, Andi Kleen , Matthew Wilcox , "Kirill A. Shutemov" , Hillf Danton , Dave Hansen , Ning Qu , linux-fsdevel@vger.kernel.org, linux-kernel@vger.kernel.org Jan Kara wrote: > On Wed 07-08-13 23:24:03, Kirill A. Shutemov wrote: > > Jan Kara wrote: > > > On Wed 07-08-13 19:32:36, Kirill A. Shutemov wrote: > > > > Jan Kara wrote: > > > > > On Sun 04-08-13 05:17:03, Kirill A. Shutemov wrote: > > > > > > From: "Kirill A. Shutemov" > > > > > > > > > > > > The radix tree is variable-height, so an insert operation not only has > > > > > > to build the branch to its corresponding item, it also has to build the > > > > > > branch to existing items if the size has to be increased (by > > > > > > radix_tree_extend). > > > > > > > > > > > > The worst case is a zero height tree with just a single item at index 0, > > > > > > and then inserting an item at index ULONG_MAX. This requires 2 new branches > > > > > > of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. > > > > > > > > > > > > Radix tree is usually protected by spin lock. It means we want to > > > > > > pre-allocate required memory before taking the lock. > > > > > > > > > > > > Currently radix_tree_preload() only guarantees enough nodes to insert > > > > > > one element. It's a hard limit. For transparent huge page cache we want > > > > > > to insert HPAGE_PMD_NR (512 on x86-64) entries to address_space at once. > > > > > > > > > > > > This patch introduces radix_tree_preload_count(). It allows to > > > > > > preallocate nodes enough to insert a number of *contiguous* elements. > > > > > > The feature costs about 5KiB per-CPU, details below. > > > > > > > > > > > > Worst case for adding N contiguous items is adding entries at indexes > > > > > > (ULONG_MAX - N) to ULONG_MAX. It requires nodes to insert single worst-case > > > > > > item plus extra nodes if you cross the boundary from one node to the next. > > > > > > > > > > > > Preload uses per-CPU array to store nodes. The total cost of preload is > > > > > > "array size" * sizeof(void*) * NR_CPUS. We want to increase array size > > > > > > to be able to handle 512 entries at once. > > > > > > > > > > > > Size of array depends on system bitness and on RADIX_TREE_MAP_SHIFT. > > > > > > > > > > > > We have three possible RADIX_TREE_MAP_SHIFT: > > > > > > > > > > > > #ifdef __KERNEL__ > > > > > > #define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6) > > > > > > #else > > > > > > #define RADIX_TREE_MAP_SHIFT 3 /* For more stressful testing */ > > > > > > #endif > > > > > > > > > > > > On 64-bit system: > > > > > > For RADIX_TREE_MAP_SHIFT=3, old array size is 43, new is 107. > > > > > > For RADIX_TREE_MAP_SHIFT=4, old array size is 31, new is 63. > > > > > > For RADIX_TREE_MAP_SHIFT=6, old array size is 21, new is 30. > > > > > > > > > > > > On 32-bit system: > > > > > > For RADIX_TREE_MAP_SHIFT=3, old array size is 21, new is 84. > > > > > > For RADIX_TREE_MAP_SHIFT=4, old array size is 15, new is 46. > > > > > > For RADIX_TREE_MAP_SHIFT=6, old array size is 11, new is 19. > > > > > > > > > > > > On most machines we will have RADIX_TREE_MAP_SHIFT=6. In this case, > > > > > > on 64-bit system the per-CPU feature overhead is > > > > > > for preload array: > > > > > > (30 - 21) * sizeof(void*) = 72 bytes > > > > > > plus, if the preload array is full > > > > > > (30 - 21) * sizeof(struct radix_tree_node) = 9 * 560 = 5040 bytes > > > > > > total: 5112 bytes > > > > > > > > > > > > on 32-bit system the per-CPU feature overhead is > > > > > > for preload array: > > > > > > (19 - 11) * sizeof(void*) = 32 bytes > > > > > > plus, if the preload array is full > > > > > > (19 - 11) * sizeof(struct radix_tree_node) = 8 * 296 = 2368 bytes > > > > > > total: 2400 bytes > > > > > > > > > > > > Since only THP uses batched preload at the moment, we disable (set max > > > > > > preload to 1) it if !CONFIG_TRANSPARENT_HUGEPAGE_PAGECACHE. This can be > > > > > > changed in the future. > > > > > > > > > > > > Signed-off-by: Matthew Wilcox > > > > > > Signed-off-by: Kirill A. Shutemov > > > > > > Acked-by: Dave Hansen > > > > > > --- > > > > > > include/linux/radix-tree.h | 11 +++++++++++ > > > > > > lib/radix-tree.c | 41 ++++++++++++++++++++++++++++++++--------- > > > > > > 2 files changed, 43 insertions(+), 9 deletions(-) > > > > > ... > > > > > > diff --git a/lib/radix-tree.c b/lib/radix-tree.c > > > > > > index 7811ed3..99ab73c 100644 > > > > > > --- a/lib/radix-tree.c > > > > > > +++ b/lib/radix-tree.c > > > > > > @@ -82,16 +82,24 @@ static struct kmem_cache *radix_tree_node_cachep; > > > > > > * The worst case is a zero height tree with just a single item at index 0, > > > > > > * and then inserting an item at index ULONG_MAX. This requires 2 new branches > > > > > > * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. > > > > > > + * > > > > > > + * Worst case for adding N contiguous items is adding entries at indexes > > > > > > + * (ULONG_MAX - N) to ULONG_MAX. It requires nodes to insert single worst-case > > > > > > + * item plus extra nodes if you cross the boundary from one node to the next. > > > > > > + * > > > > > > * Hence: > > > > > > */ > > > > > > -#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1) > > > > > > +#define RADIX_TREE_PRELOAD_MIN (RADIX_TREE_MAX_PATH * 2 - 1) > > > > > > +#define RADIX_TREE_PRELOAD_MAX \ > > > > > > + (RADIX_TREE_PRELOAD_MIN + \ > > > > > > + DIV_ROUND_UP(RADIX_TREE_PRELOAD_NR - 1, RADIX_TREE_MAP_SIZE)) > > > > > Umm, is this really correct? I see two problems: > > > > > 1) You may need internal tree nodes at various levels but you seem to > > > > > account only for the level 1. > > > > > 2) The rounding doesn't seem right because RADIX_TREE_MAP_SIZE+2 nodes may > > > > > require 3 nodes at level 1 if the indexes are like: > > > > > i_0 | i_1 .. i_{RADIX_TREE_MAP_SIZE} | i_{RADIX_TREE_MAP_SIZE+1} > > > > > ^ ^ > > > > > node boundary node boundary > > > > > > > > My bad. Let's try to calculate once again. > > > > > > > > We want to insert N contiguous items without restriction on alignment. > > > > > > > > Let's limit N <= 1UL << (2 * RADIX_TREE_MAP_SHIFT), without > > > > CONFIG_BASE_SMALL it's 4096. It will simplify calculation a bit. > > > > > > > > Worst case scenario, I can imagine, is tree with only one element at index > > > > 0 and we add N items where at least one index requires max tree high and > > > > we cross boundary between items in root node. > > > > > > > > Basically, at least one index is less then > > > > > > > > 1UL << ((RADIX_TREE_MAX_PATH - 1) * RADIX_TREE_MAP_SHIFT) > > > > > > > > and one equal or more. > > > > > > > > In this case we need: > > > > > > > > - RADIX_TREE_MAX_PATH nodes to build new path to item with index 0; > > > > - DIV_ROUND_UP(N, RADIX_TREE_MAP_SIZE) nodes for last level nodes for new > > > > items; > > > Here, I think you need to count with > > > DIV_ROUND_UP(N + RADIX_TREE_MAP_SIZE - 1, RADIX_TREE_MAP_SIZE) to propely > > > account for the situation b) I described. > > > > It's not obvious for me why it's needed. Since we limit N, we can cross > > second (or above) level node boundary only once. > > > > I've tried to confirm the math with my kvm (see *ugly* patch below) and > > I was not able to find anything that is not covered. > > > > Could you demonstrate the case you are talking about. > Sure. So let RADIX_TREE_MAP_SHIFT be 6 (i.e. RADIX_TREE_MAP_SIZE == 64). > Let's have radix tree with single element from index 0. We insert 66 elements > starting from index 127. So for nodes at the last level we need - node for > index 127, node for indexes 128 .. 191, node for index 192. That is > together three nodes. But DIV_ROUND_UP(66, 64) = 2. The problem happens > because starting index 127 isn't multiple of RADIX_TREE_MAP_SIZE so we can > have partially used nodes both at the beginning and at the end of the > range. I see. Looks like you are correct. So with patch in previous mail, it should be triable if we set RADIX_TREE_PRELOAD_NR to 514 and off to (1UL << ((RADIX_TREE_MAX_PATH - 1) * RADIX_TREE_MAP_SHIFT)) - RADIX_TREE_MAP_SIZE - 1 In this case it should use 39 nodes, but it uses only 38. I can't understand why. :( -- Kirill A. Shutemov -- To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to majordomo@kvack.org. For more info on Linux MM, see: http://www.linux-mm.org/ . Don't email: email@kvack.org