Message-Id: <20130807213736.AC732E0090@blue.fi.intel.com>
Date:	Thu,  8 Aug 2013 00:37:36 +0300 (EEST)
From:	"Kirill A. Shutemov" <kirill.shutemov@...ux.intel.com>
To:	Jan Kara <jack@...e.cz>
Cc:	"Kirill A. Shutemov" <kirill.shutemov@...ux.intel.com>,
	Jan Kara <jack@...e.cz>,
	Andrea Arcangeli <aarcange@...hat.com>,
	Andrew Morton <akpm@...ux-foundation.org>,
	Al Viro <viro@...iv.linux.org.uk>,
	Hugh Dickins <hughd@...gle.com>,
	Wu Fengguang <fengguang.wu@...el.com>,
	Mel Gorman <mgorman@...e.de>, linux-mm@...ck.org,
	Andi Kleen <ak@...ux.intel.com>,
	Matthew Wilcox <willy@...ux.intel.com>,
	"Kirill A. Shutemov" <kirill@...temov.name>,
	Hillf Danton <dhillf@...il.com>, Dave Hansen <dave@...1.net>,
	Ning Qu <quning@...gle.com>, linux-fsdevel@...r.kernel.org,
	linux-kernel@...r.kernel.org
Subject: Re: [PATCH 01/23] radix-tree: implement preload for multiple
 contiguous elements

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" <kirill.shutemov@...ux.intel.com>
> > > > > > 
> > > > > > 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 <willy@...ux.intel.com>
> > > > > > Signed-off-by: Kirill A. Shutemov <kirill.shutemov@...ux.intel.com>
> > > > > > Acked-by: Dave Hansen <dave.hansen@...ux.intel.com>
> > > > > > ---
> > > > > >  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 from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Powered by blists - more mailing lists