Re: [PATCH 01/23] radix-tree: implement preload for multiplecontiguous elements

[Jan Kara]

On Fri 09-08-13 14:13:51, Kirill A. Shutemov wrote:
> Jan Kara wrote:
> > On Thu 08-08-13 11:45:05, Kirill A. Shutemov wrote:
> > > From 35ba5687ea7aea98645da34ddd0be01a9de8b32d Mon Sep 17 00:00:00 2001
> > > From: "Kirill A. Shutemov" <kirill.shutemov@xxxxxxxxxxxxxxx>
> > > Date: Wed, 9 Jan 2013 13:25:47 +0200
> > > Subject: [PATCH] radix-tree: implement preload for multiple contiguous
> > >  elements
> > > 
> > > 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 9KiB per-CPU on x86_64, details below.
> > > 
> > > 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
> > > 
> > > We are not going to use transparent huge page cache on small machines or
> > > in userspace, so we are interested in RADIX_TREE_MAP_SHIFT=6.
> > > 
> > > On 64-bit system old array size is 21, new is 37. Per-CPU feature
> > > overhead is
> > >  for preload array:
> > >    (37 - 21) * sizeof(void*) = 128 bytes
> > >  plus, if the preload array is full
> > >    (37 - 21) * sizeof(struct radix_tree_node) = 16 * 560 = 8960 bytes
> > >  total: 9088 bytes
> > > 
> > > On 32-bit system old array size is 11, new is 22. Per-CPU feature
> > > overhead is
> > >  for preload array:
> > >    (22 - 11) * sizeof(void*) = 44 bytes
> > >  plus, if the preload array is full
> > >    (22 - 11) * sizeof(struct radix_tree_node) = 11 * 296 = 3256 bytes
> > >  total: 3300 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@xxxxxxxxxxxxxxx>
> > > Signed-off-by: Kirill A. Shutemov <kirill.shutemov@xxxxxxxxxxxxxxx>
> > > Acked-by: Dave Hansen <dave.hansen@xxxxxxxxxxxxxxx>
> > > ---
> > >  include/linux/radix-tree.h | 11 ++++++
> > >  lib/radix-tree.c           | 89 +++++++++++++++++++++++++++++++++++++++++-----
> > >  2 files changed, 91 insertions(+), 9 deletions(-)
> > > 
> > > diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> > > index 4039407..3bf0b3e 100644
> > > --- a/include/linux/radix-tree.h
> > > +++ b/include/linux/radix-tree.h
> > > @@ -83,6 +83,16 @@ do {									\
> > >  	(root)->rnode = NULL;						\
> > >  } while (0)
> > >  
> > > +#ifdef CONFIG_TRANSPARENT_HUGEPAGE_PAGECACHE
> > > +/*
> > > + * At the moment only THP uses preload for more then on item for batched
> > > + * pagecache manipulations.
> > > + */
> > > +#define RADIX_TREE_PRELOAD_NR	512
> > > +#else
> > > +#define RADIX_TREE_PRELOAD_NR	1
> > > +#endif
> > > +
> > >  /**
> > >   * Radix-tree synchronization
> > >   *
> > > @@ -232,6 +242,7 @@ unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
> > >  				unsigned long index, unsigned long max_scan);
> > >  int radix_tree_preload(gfp_t gfp_mask);
> > >  int radix_tree_maybe_preload(gfp_t gfp_mask);
> > > +int radix_tree_maybe_preload_contig(unsigned size, gfp_t gfp_mask);
> > >  void radix_tree_init(void);
> > >  void *radix_tree_tag_set(struct radix_tree_root *root,
> > >  			unsigned long index, unsigned int tag);
> > > diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> > > index 7811ed3..980e4c4 100644
> > > --- a/lib/radix-tree.c
> > > +++ b/lib/radix-tree.c
> > > @@ -84,14 +84,54 @@ static struct kmem_cache *radix_tree_node_cachep;
> > >   * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
> > >   * Hence:
> > >   */
> > > -#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
> > > +#define RADIX_TREE_PRELOAD_MIN (RADIX_TREE_MAX_PATH * 2 - 1)
> > > +
> > > +/*
> > > + * Inserting N contiguous items is more complex. To simplify calculation, let's
> > > + * limit N (validated in radix_tree_init()):
> > > + *  - N is multiplier of RADIX_TREE_MAP_SIZE (or 1);
> >   Is this limitation really worth the one reserved item you save?
> 
> It's not really limitation, It just doesn't make any sense to lower
> RADIX_TREE_PRELOAD_NR not to RADIX_TREE_MAP_SIZE boundary, since we will
> have to round it up anyway.
> 
> I made one more mistake: I've modeled not the situation I've describe, so
> last -1 is wrong. Fixed in patch below.
> 
> > > -static int __radix_tree_preload(gfp_t gfp_mask)
> > > +static int __radix_tree_preload_contig(unsigned size, gfp_t gfp_mask)
> > >  {
> > >  	struct radix_tree_preload *rtp;
> > >  	struct radix_tree_node *node;
> > >  	int ret = -ENOMEM;
> > > +	int preload_target = RADIX_TREE_PRELOAD_MIN +
> > > +		DIV_ROUND_UP(size - 1, RADIX_TREE_MAP_SIZE);
> >   So you should also warn if size % RADIX_TREE_MAP_SIZE != 0, right?
> 
> I've reworked logic here to match RADIX_TREE_PRELOAD_MAX calculation math.
> 
> > Otherwise the patch looks fine.
> 
> Ack?
  Yes. You can add:
Reviewed-by: Jan Kara <jack@xxxxxxx>

								Honza
> 
> From 0e7d481093a4ded0dfb58e87d4edda003f3b2fd6 Mon Sep 17 00:00:00 2001
> From: "Kirill A. Shutemov" <kirill.shutemov@xxxxxxxxxxxxxxx>
> Date: Wed, 9 Jan 2013 13:25:47 +0200
> Subject: [PATCH] radix-tree: implement preload for multiple contiguous
>  elements
> 
> 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 9.5KiB per-CPU on x86_64, details below.
> 
> 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
> 
> We are not going to use transparent huge page cache on small machines or
> in userspace, so we are interested in RADIX_TREE_MAP_SHIFT=6.
> 
> On 64-bit system old array size is 21, new is 37. Per-CPU feature
> overhead is
>  for preload array:
>    (38 - 21) * sizeof(void*) = 136 bytes
>  plus, if the preload array is full
>    (38 - 21) * sizeof(struct radix_tree_node) = 17 * 560 = 9520 bytes
>  total: 9656 bytes
> 
> On 32-bit system old array size is 11, new is 22. Per-CPU feature
> overhead is
>  for preload array:
>    (23 - 11) * sizeof(void*) = 48 bytes
>  plus, if the preload array is full
>    (23 - 11) * sizeof(struct radix_tree_node) = 12 * 296 = 3552 bytes
>  total: 3600 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@xxxxxxxxxxxxxxx>
> Signed-off-by: Kirill A. Shutemov <kirill.shutemov@xxxxxxxxxxxxxxx>
> Acked-by: Dave Hansen <dave.hansen@xxxxxxxxxxxxxxx>
> ---
>  include/linux/radix-tree.h | 11 ++++++
>  lib/radix-tree.c           | 95 +++++++++++++++++++++++++++++++++++++++++-----
>  2 files changed, 97 insertions(+), 9 deletions(-)
> 
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h
> index 4039407..3bf0b3e 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -83,6 +83,16 @@ do {									\
>  	(root)->rnode = NULL;						\
>  } while (0)
>  
> +#ifdef CONFIG_TRANSPARENT_HUGEPAGE_PAGECACHE
> +/*
> + * At the moment only THP uses preload for more then on item for batched
> + * pagecache manipulations.
> + */
> +#define RADIX_TREE_PRELOAD_NR	512
> +#else
> +#define RADIX_TREE_PRELOAD_NR	1
> +#endif
> +
>  /**
>   * Radix-tree synchronization
>   *
> @@ -232,6 +242,7 @@ unsigned long radix_tree_prev_hole(struct radix_tree_root *root,
>  				unsigned long index, unsigned long max_scan);
>  int radix_tree_preload(gfp_t gfp_mask);
>  int radix_tree_maybe_preload(gfp_t gfp_mask);
> +int radix_tree_maybe_preload_contig(unsigned size, gfp_t gfp_mask);
>  void radix_tree_init(void);
>  void *radix_tree_tag_set(struct radix_tree_root *root,
>  			unsigned long index, unsigned int tag);
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index 7811ed3..1c19595 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -84,14 +84,52 @@ static struct kmem_cache *radix_tree_node_cachep;
>   * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
>   * Hence:
>   */
> -#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
> +#define RADIX_TREE_PRELOAD_MIN (RADIX_TREE_MAX_PATH * 2 - 1)
> +
> +/*
> + * Inserting N contiguous items is more complex. To simplify calculation, let's
> + * limit N (validated in radix_tree_init()):
> + *  - N is multiplier of RADIX_TREE_MAP_SIZE (or 1);
> + *  - N <= number of items 2-level tree can contain:
> + *    1UL << (2 * RADIX_TREE_MAP_SHIFT).
> + *
> + * No limitation on insert index alignment.
> + *
> + * Then the worst case 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 is equal to.
> + *
> + * In this case we need:
> + *
> + * - RADIX_TREE_MAX_PATH nodes to build new path to item with index 0;
> + * - N / RADIX_TREE_MAP_SIZE + 1 nodes for last level nodes for new items:
> + *    - +1 is for misalinged case;
> + * - 2 * (RADIX_TREE_MAX_PATH - 2) - 1 nodes to build path to last level nodes:
> + *    - -2, because root node and last level nodes are already accounted).
> + *
> + * Hence:
> + */
> +#if RADIX_TREE_PRELOAD_NR > 1
> +#define RADIX_TREE_PRELOAD_MAX \
> +	( RADIX_TREE_MAX_PATH + \
> +	  RADIX_TREE_PRELOAD_NR / RADIX_TREE_MAP_SIZE + 1 + \
> +	  2 * (RADIX_TREE_MAX_PATH - 2))
> +#else
> +#define RADIX_TREE_PRELOAD_MAX RADIX_TREE_PRELOAD_MIN
> +#endif
>  
>  /*
>   * Per-cpu pool of preloaded nodes
>   */
>  struct radix_tree_preload {
>  	int nr;
> -	struct radix_tree_node *nodes[RADIX_TREE_PRELOAD_SIZE];
> +	struct radix_tree_node *nodes[RADIX_TREE_PRELOAD_MAX];
>  };
>  static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
>  
> @@ -263,29 +301,43 @@ radix_tree_node_free(struct radix_tree_node *node)
>  
>  /*
>   * Load up this CPU's radix_tree_node buffer with sufficient objects to
> - * ensure that the addition of a single element in the tree cannot fail.  On
> - * success, return zero, with preemption disabled.  On error, return -ENOMEM
> + * ensure that the addition of *contiguous* items in the tree cannot fail.
> + * On success, return zero, with preemption disabled.  On error, return -ENOMEM
>   * with preemption not disabled.
>   *
>   * To make use of this facility, the radix tree must be initialised without
>   * __GFP_WAIT being passed to INIT_RADIX_TREE().
>   */
> -static int __radix_tree_preload(gfp_t gfp_mask)
> +static int __radix_tree_preload_contig(unsigned size, gfp_t gfp_mask)
>  {
>  	struct radix_tree_preload *rtp;
>  	struct radix_tree_node *node;
>  	int ret = -ENOMEM;
> +	int preload_target = RADIX_TREE_PRELOAD_MIN;
>  
> +	if (size > 1) {
> +		size = round_up(size, RADIX_TREE_MAP_SIZE);
> +		if (WARN_ONCE(size > RADIX_TREE_PRELOAD_NR,
> +					"too large preload requested"))
> +			return -ENOMEM;
> +
> +		/* The same math as with RADIX_TREE_PRELOAD_MAX */
> +		preload_target = RADIX_TREE_MAX_PATH +
> +			size / RADIX_TREE_MAP_SIZE + 1 +
> +			2 * (RADIX_TREE_MAX_PATH - 2);
> +	}
> +
> +	BUG_ON(preload_target > RADIX_TREE_PRELOAD_MAX);
>  	preempt_disable();
>  	rtp = &__get_cpu_var(radix_tree_preloads);
> -	while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
> +	while (rtp->nr < preload_target) {
>  		preempt_enable();
>  		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
>  		if (node == NULL)
>  			goto out;
>  		preempt_disable();
>  		rtp = &__get_cpu_var(radix_tree_preloads);
> -		if (rtp->nr < ARRAY_SIZE(rtp->nodes))
> +		if (rtp->nr < preload_target)
>  			rtp->nodes[rtp->nr++] = node;
>  		else
>  			kmem_cache_free(radix_tree_node_cachep, node);
> @@ -308,7 +360,7 @@ int radix_tree_preload(gfp_t gfp_mask)
>  {
>  	/* Warn on non-sensical use... */
>  	WARN_ON_ONCE(!(gfp_mask & __GFP_WAIT));
> -	return __radix_tree_preload(gfp_mask);
> +	return __radix_tree_preload_contig(1, gfp_mask);
>  }
>  EXPORT_SYMBOL(radix_tree_preload);
>  
> @@ -320,13 +372,22 @@ EXPORT_SYMBOL(radix_tree_preload);
>  int radix_tree_maybe_preload(gfp_t gfp_mask)
>  {
>  	if (gfp_mask & __GFP_WAIT)
> -		return __radix_tree_preload(gfp_mask);
> +		return __radix_tree_preload_contig(1, gfp_mask);
>  	/* Preloading doesn't help anything with this gfp mask, skip it */
>  	preempt_disable();
>  	return 0;
>  }
>  EXPORT_SYMBOL(radix_tree_maybe_preload);
>  
> +int radix_tree_maybe_preload_contig(unsigned size, gfp_t gfp_mask)
> +{
> +	if (gfp_mask & __GFP_WAIT)
> +		return __radix_tree_preload_contig(size, gfp_mask);
> +	/* Preloading doesn't help anything with this gfp mask, skip it */
> +	preempt_disable();
> +	return 0;
> +}
> +
>  /*
>   *	Return the maximum key which can be store into a
>   *	radix tree with height HEIGHT.
> @@ -1483,6 +1544,22 @@ static int radix_tree_callback(struct notifier_block *nfb,
>  
>  void __init radix_tree_init(void)
>  {
> +	/*
> +	 * Restrictions on RADIX_TREE_PRELOAD_NR simplify RADIX_TREE_PRELOAD_MAX
> +	 * calculation, it's already complex enough:
> +	 *  - it must be multiplier of RADIX_TREE_MAP_SIZE, otherwise we will
> +	 *    have to round it up to next RADIX_TREE_MAP_SIZE multiplier and we
> +	 *    don't win anything;
> +	 *  - must be less then number of items 2-level tree can contain.
> +	 *    It's easier to calculate number of internal nodes required
> +	 *    this way.
> +	 */
> +	if (RADIX_TREE_PRELOAD_NR != 1) {
> +		BUILD_BUG_ON(RADIX_TREE_PRELOAD_NR % RADIX_TREE_MAP_SIZE != 0);
> +		BUILD_BUG_ON(RADIX_TREE_PRELOAD_NR >
> +				1UL << (2 * RADIX_TREE_MAP_SHIFT));
> +	}
> +
>  	radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
>  			sizeof(struct radix_tree_node), 0,
>  			SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
> -- 
>  Kirill A. Shutemov
-- 
Jan Kara <jack@xxxxxxx>
SUSE Labs, CR
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/