From: David Hildenbrand <david@redhat.com>
To: Andrew Morton <akpm@linux-foundation.org>
Cc: Scott Cheloha <cheloha@linux.vnet.ibm.com>,
linux-kernel@vger.kernel.org,
"Rafael J. Wysocki" <rafael@kernel.org>,
Greg Kroah-Hartman <gregkh@linuxfoundation.org>,
nathanl@linux.ibm.com, ricklind@linux.vnet.ibm.com,
mhocko@suse.com, Scott Cheloha <cheloha@linux.ibm.com>
Subject: Re: [PATCH v4] drivers/base/memory.c: cache blocks in radix tree to accelerate lookup
Date: Fri, 10 Jan 2020 10:32:01 +0100 [thread overview]
Message-ID: <bc21eec6-7251-4c91-2f57-9a0671f8d414@redhat.com> (raw)
In-Reply-To: <F8AD9915-061E-4829-8670-B35D5F2DFC03@redhat.com>
On 09.01.20 23:35, David Hildenbrand wrote:
>> Am 09.01.2020 um 23:28 schrieb Andrew Morton <akpm@linux-foundation.org>:
>>
>> On Thu, 9 Jan 2020 23:17:09 +0100 David Hildenbrand <david@redhat.com> wrote:
>>
>>>
>>>
>>>>> Am 09.01.2020 um 23:00 schrieb Andrew Morton <akpm@linux-foundation.org>:
>>>>
>>>> On Thu, 9 Jan 2020 15:25:16 -0600 Scott Cheloha <cheloha@linux.vnet.ibm.com> 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.
>>>>>
>>>>> ...
>>>>>
>>>>> @@ -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);
>>>>
>>>> What protects this tree from racy accesses?
>>>
>>> I think the device hotplug lock currently (except during boot where no races can happen).
>>>
>>
>> So this?
>>
>> --- a/drivers/base/memory.c~drivers-base-memoryc-cache-blocks-in-radix-tree-to-accelerate-lookup-fix
>> +++ a/drivers/base/memory.c
>> @@ -61,6 +61,9 @@ static struct bus_type memory_subsys = {
>> * Memory blocks are cached in a local radix tree to avoid
>> * a costly linear search for the corresponding device on
>> * the subsystem bus.
>> + *
>> + * Protected by mem_hotplug_lock in mem_hotplug_begin(), and by the guaranteed
>> + * single-threadness at boot time.
>> */
>> static RADIX_TREE(memory_blocks, GFP_KERNEL);
>>
>>
>> But are we sure this is all true?
>
> I think the device hotplug lock, not the memory hotplug lock. Will double check later.
So all writers either hold the device_hotplug_lock or run during boot.
Documented e.g., for memory_dev_init(), create_memory_block_devices(),
remove_memory_block_devices().
The readers are mainly
- find_memory_block()
-> called via online_pages()/offline_pages() where we hold the
device_hotplug_lock
-> called from arch/powerpc/platforms/pseries/hotplug-memory.c,
where we always hold the device_hotplug_lock
- walk_memory_blocks()
-> Callers in drivers/acpi/acpi_memhotplug.c either hold the
device_hotplug_lock or are called early during boot
-> Callers in mm/memory_hotplug.c either hold the
device_hotplug_lock or are called early during boot
-> link_mem_sections() is called either early during boot or via
add_memory_resource() (whereby all callers either hold the
device_hotplug_lock or are called early during boot)
-> Callers in arch/powerpc/platforms/powernv/memtrace.c hold the
device_hotplug_lock
So we are fine.
I suggest we document that expected behavior via
diff --git a/drivers/base/memory.c b/drivers/base/memory.c
index 799b43191dea..8c8dc081597e 100644
--- a/drivers/base/memory.c
+++ b/drivers/base/memory.c
@@ -585,6 +585,8 @@ static struct memory_block
*find_memory_block_by_id(unsigned long block_id)
* tree or something here.
*
* This could be made generic for all device subsystems.
+ *
+ * Called under device_hotplug_lock.
*/
struct memory_block *find_memory_block(struct mem_section *section)
{
@@ -837,6 +839,8 @@ void __init memory_dev_init(void)
*
* In case func() returns an error, walking is aborted and the error is
* returned.
+ *
+ * Called under device_hotplug_lock.
*/
int walk_memory_blocks(unsigned long start, unsigned long size,
void *arg, walk_memory_blocks_func_t func)
Please note that the memory hotplug lock is not safe on the reader side.
But also not on the writer side after
https://lkml.kernel.org/r/157863061737.2230556.3959730620803366776.stgit@dwillia2-desk3.amr.corp.intel.com
--
Thanks,
David / dhildenb
next prev parent reply other threads:[~2020-01-10 9:32 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
[not found] <20191217193238-1-cheloha@linux.vnet.ibm.com>
2020-01-09 21:19 ` [PATCH] drivers/base/memory.c: cache blocks in radix tree to accelerate lookup Scott Cheloha
2020-01-09 21:30 ` Michal Hocko
2020-01-09 21:25 ` [PATCH v4] " Scott Cheloha
2020-01-09 22:00 ` Andrew Morton
2020-01-09 22:17 ` David Hildenbrand
2020-01-09 22:27 ` Andrew Morton
2020-01-09 22:35 ` David Hildenbrand
2020-01-10 9:32 ` David Hildenbrand [this message]
2020-01-10 11:31 ` Michal Hocko
2020-01-15 19:09 ` David Hildenbrand
2020-01-16 15:22 ` Michal Hocko
2020-01-16 15:28 ` David Hildenbrand
2020-01-16 16:17 ` David Hildenbrand
2020-01-17 9:35 ` Michal Hocko
2020-01-20 9:15 ` David Hildenbrand
2020-01-21 12:30 ` Michal Hocko
2020-01-16 17:17 ` Don Dutile
2020-01-21 23:10 ` [PATCH v5] drivers/base/memory.c: cache memory blocks in xarray " Scott Cheloha
2020-01-22 10:43 ` David Hildenbrand
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=bc21eec6-7251-4c91-2f57-9a0671f8d414@redhat.com \
--to=david@redhat.com \
--cc=akpm@linux-foundation.org \
--cc=cheloha@linux.ibm.com \
--cc=cheloha@linux.vnet.ibm.com \
--cc=gregkh@linuxfoundation.org \
--cc=linux-kernel@vger.kernel.org \
--cc=mhocko@suse.com \
--cc=nathanl@linux.ibm.com \
--cc=rafael@kernel.org \
--cc=ricklind@linux.vnet.ibm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).