Messages in this thread Patch in this message | | | Subject | Re: [PATCH v4] drivers/base/memory.c: cache blocks in radix tree to accelerate lookup | From | David Hildenbrand <> | Date | Thu, 16 Jan 2020 17:17:54 +0100 |
| |
On 16.01.20 16:28, David Hildenbrand wrote: > On 16.01.20 16:22, Michal Hocko wrote: >> On Wed 15-01-20 20:09:48, David Hildenbrand wrote: >>> On 09.01.20 22:25, 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@linux.ibm.com> >>>> Acked-by: David Hildenbrand <david@redhat.com> >>>> Acked-by: Nathan Lynch <nathanl@linux.ibm.com> >>>> Acked-by: Michal Hocko <mhocko@suse.com> >>> >>> Soooo, >>> >>> I just learned that radix trees are nowadays only a wrapper for xarray >>> (for quite a while already!), and that the xarray interface shall be >>> used in new code. >> >> Good point. I somehow didn't realize this would add more work for a >> later code refactoring. The mapping should be pretty straightforward. > > Yes it is. @Scott, care to send a fixup that does the mapping?
Never having used an xarray, I gave it a quick shot. The following should do the trick:
diff --git a/drivers/base/memory.c b/drivers/base/memory.c index c6d288fad493..c75dec35de43 100644 --- a/drivers/base/memory.c +++ b/drivers/base/memory.c @@ -19,7 +19,7 @@ #include <linux/memory.h> #include <linux/memory_hotplug.h> #include <linux/mm.h> -#include <linux/radix-tree.h> +#include <linux/xarray.h> #include <linux/stat.h> #include <linux/slab.h> @@ -58,11 +58,11 @@ static struct bus_type memory_subsys = { }; /* - * Memory blocks are cached in a local radix tree to avoid + * Memory blocks are cached in a local xarray to avoid * a costly linear search for the corresponding device on * the subsystem bus. */ -static RADIX_TREE(memory_blocks, GFP_KERNEL); +static DEFINE_XARRAY(memory_blocks); static BLOCKING_NOTIFIER_HEAD(memory_chain); @@ -566,7 +566,7 @@ static struct memory_block *find_memory_block_by_id(unsigned long block_id) { struct memory_block *mem; - mem = radix_tree_lookup(&memory_blocks, block_id); + mem = xa_load(&memory_blocks, block_id); if (mem) get_device(&mem->dev); return mem; @@ -621,7 +621,8 @@ int register_memory(struct memory_block *memory) put_device(&memory->dev); return ret; } - ret = radix_tree_insert(&memory_blocks, memory->dev.id, memory); + ret = xa_err(xa_store(&memory_blocks, memory->dev.id, memory, + GFP_KERNEL)); if (ret) { put_device(&memory->dev); device_unregister(&memory->dev); @@ -683,7 +684,7 @@ 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); + WARN_ON(xa_erase(&memory_blocks, memory->dev.id) == NULL); /* drop the ref. we got via find_memory_block() */ put_device(&memory->dev);
-- Thanks,
David / dhildenb
| |