Re: [PATCH] drivers/base/memory.c: cache blocks in radix tree to accelerate lookup

[Michal Hocko]

On Thu 09-01-20 15:19:52, Scott Cheloha wrote:
> Searching for a particular memory block by id is an O(n) operation
> because each memory block's underlying device is kept in an unsorted
> linked list on the subsystem bus.
> 
> We can cut the lookup cost to O(log n) if we cache the memory blocks in
> a radix tree.  With a radix tree cache in place both memory subsystem
> initialization and memory hotplug run palpably faster on systems with a
> large number of memory blocks.
> 
> Signed-off-by: Scott Cheloha <cheloha@xxxxxxxxxxxxx>
> Acked-by: David Hildenbrand <david@xxxxxxxxxx>
> Acked-by: Nathan Lynch <nathanl@xxxxxxxxxxxxx>
> Acked-by: Michal Hocko <mhocko@xxxxxxxx>
> ---
> v2 incorporates suggestions from David Hildenbrand.
> 
> v3 changes:
>   - Rebase atop "drivers/base/memory.c: drop the mem_sysfs_mutex"
> 
>   - Be conservative: don't use radix_tree_for_each_slot() in
>     walk_memory_blocks() yet.  It introduces RCU which could
>     change behavior.  Walking the tree "by hand" with
>     find_memory_block_by_id() is slower but keeps the patch
>     simple.
> 
> v4 changes:
>   - Rewrite commit message to explicitly note the time
>     complexity improvements.
> 
>   - Provide anecdotal accounts of time-savings in the changelog
>     (see below).
> 
> mhocko@xxxxxxxx has asked for additional details on time
> savings, so here are some results I've collected when measuring
> memory_dev_init() with/without the patch.

This data should be part of the changelog. Thanks!

> 1. A 32GB POWER9 VM with 16MB memblocks has 2048 blocks:
> 
> # Unpatched
> [    0.005121] adding memory block 0... ok
> [...]
> [    0.095230] adding memory block 1024... ok
> [...]
> [    0.304248] adding memory block 2047... ok
> [    0.304508] added all memory blocks
> 
> # Patched
> [    0.004701] adding memory block 0... ok
> [...]
> [    0.033383] adding memory block 1024... ok
> [...]
> [    0.061387] adding memory block 2047... ok
> [    0.061414] added all memory blocks
> 
>    Unpatched, memory_dev_init() runs in about 0.299 seconds.  Patched,
>    it runs in about 0.057 seconds.  Savings of .242 seconds, or nearly
>    a quarter of a second.
> 
> 2. A 32TB POWER9 LPAR with 256MB memblocks has 131072 blocks:
> 
> # Unpatched
> [   13.703907] memory_dev_init: adding blocks
> [   13.703931] memory_dev_init: added block 0
> [   13.762678] memory_dev_init: added block 1024
> [   13.910359] memory_dev_init: added block 2048
> [   14.146941] memory_dev_init: added block 3072
> [...]
> [  218.516235] memory_dev_init: added block 57344
> [  229.310467] memory_dev_init: added block 58368
> [  240.590857] memory_dev_init: added block 59392
> [  252.351665] memory_dev_init: added block 60416
> [...]
> [ 2152.023248] memory_dev_init: added block 128000
> [ 2196.464430] memory_dev_init: added block 129024
> [ 2241.746515] memory_dev_init: added block 130048
> [ 2287.406099] memory_dev_init: added all blocks
> 
> # Patched
> [   13.696898] memory_dev_init: adding blocks
> [   13.696920] memory_dev_init: added block 0
> [   13.710966] memory_dev_init: added block 1024
> [   13.724865] memory_dev_init: added block 2048
> [   13.738802] memory_dev_init: added block 3072
> [...]
> [   14.520999] memory_dev_init: added block 57344
> [   14.536355] memory_dev_init: added block 58368
> [   14.551747] memory_dev_init: added block 59392
> [   14.567128] memory_dev_init: added block 60416
> [...]
> [   15.595638] memory_dev_init: added block 126976
> [   15.611761] memory_dev_init: added block 128000
> [   15.627889] memory_dev_init: added block 129024
> [   15.644048] memory_dev_init: added block 130048
> [   15.660035] memory_dev_init: added all blocks
> 
>    Unpatched, memory_dev_init() runs in about 2275 seconds,
>    or ~37 minutes.  Patched, memory_dev_init() runs in about
>    1.97 seconds.  Savings of ~37 minutes.
> 
>    I did not actually measure walk_memory_blocks(), but during
>    boot on this machine without the patch I got the following
>    (abbreviated) traces:
> 
> [ 2347.494986] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> [ 2527.625378] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> [ 2707.761977] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> [ 2887.899975] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> [ 3068.028318] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> [ 3248.158764] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> [ 3428.287296] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> [ 3608.425357] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> [ 3788.554572] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> [ 3968.695071] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> [ 4148.823970] [c000000014c5bb60] [c000000000869af4] walk_memory_blocks+0x94/0x160
> 
>    Those traces disappeared with the patch, so I'm pretty sure
>    this patch shaves ~30 minutes off of walk_memory_blocks()
>    at boot.
> 
> Given the above results I think it is safe to say that this patch will
> dramatically improve boot times on large POWER systems.
> 
>  drivers/base/memory.c | 36 +++++++++++++++++++++++-------------
>  1 file changed, 23 insertions(+), 13 deletions(-)
> 
> diff --git a/drivers/base/memory.c b/drivers/base/memory.c
> index 799b43191dea..8902930d5ef2 100644
> --- a/drivers/base/memory.c
> +++ b/drivers/base/memory.c
> @@ -19,6 +19,7 @@
>  #include <linux/memory.h>
>  #include <linux/memory_hotplug.h>
>  #include <linux/mm.h>
> +#include <linux/radix-tree.h>
>  #include <linux/stat.h>
>  #include <linux/slab.h>
>  
> @@ -56,6 +57,13 @@ static struct bus_type memory_subsys = {
>  	.offline = memory_subsys_offline,
>  };
>  
> +/*
> + * Memory blocks are cached in a local radix tree to avoid
> + * a costly linear search for the corresponding device on
> + * the subsystem bus.
> + */
> +static RADIX_TREE(memory_blocks, GFP_KERNEL);
> +
>  static BLOCKING_NOTIFIER_HEAD(memory_chain);
>  
>  int register_memory_notifier(struct notifier_block *nb)
> @@ -572,20 +580,14 @@ int __weak arch_get_memory_phys_device(unsigned long start_pfn)
>  /* A reference for the returned memory block device is acquired. */
>  static struct memory_block *find_memory_block_by_id(unsigned long block_id)
>  {
> -	struct device *dev;
> +	struct memory_block *mem;
>  
> -	dev = subsys_find_device_by_id(&memory_subsys, block_id, NULL);
> -	return dev ? to_memory_block(dev) : NULL;
> +	mem = radix_tree_lookup(&memory_blocks, block_id);
> +	if (mem)
> +		get_device(&mem->dev);
> +	return mem;
>  }
>  
> -/*
> - * For now, we have a linear search to go find the appropriate
> - * memory_block corresponding to a particular phys_index. If
> - * this gets to be a real problem, we can always use a radix
> - * tree or something here.
> - *
> - * This could be made generic for all device subsystems.
> - */
>  struct memory_block *find_memory_block(struct mem_section *section)
>  {
>  	unsigned long block_id = base_memory_block_id(__section_nr(section));
> @@ -628,9 +630,15 @@ int register_memory(struct memory_block *memory)
>  	memory->dev.offline = memory->state == MEM_OFFLINE;
>  
>  	ret = device_register(&memory->dev);
> -	if (ret)
> +	if (ret) {
>  		put_device(&memory->dev);
> -
> +		return ret;
> +	}
> +	ret = radix_tree_insert(&memory_blocks, memory->dev.id, memory);
> +	if (ret) {
> +		put_device(&memory->dev);
> +		device_unregister(&memory->dev);
> +	}
>  	return ret;
>  }
>  
> @@ -688,6 +696,8 @@ static void unregister_memory(struct memory_block *memory)
>  	if (WARN_ON_ONCE(memory->dev.bus != &memory_subsys))
>  		return;
>  
> +	WARN_ON(radix_tree_delete(&memory_blocks, memory->dev.id) == NULL);
> +
>  	/* drop the ref. we got via find_memory_block() */
>  	put_device(&memory->dev);
>  	device_unregister(&memory->dev);
> -- 
> 2.24.1

-- 
Michal Hocko
SUSE Labs