Received-SPF: pass (google.com: best guess record for domain of linux-kernel-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
Content-Type: text/plain; charset=utf-8
Content-Transfer-Encoding: quoted-printable
From:   David Hildenbrand <david@redhat.com>
Mime-Version: 1.0 (1.0)
Subject: Re: [PATCH v4] drivers/base/memory.c: cache blocks in radix tree to accelerate lookup
Date:   Thu, 9 Jan 2020 23:35:28 +0100
Message-Id: <F8AD9915-061E-4829-8670-B35D5F2DFC03@redhat.com>
References: <20200109142758.659c1545cb8df2d05f299a4a@linux-foundation.org>
Cc:     David Hildenbrand <david@redhat.com>,
        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>
In-Reply-To: <20200109142758.659c1545cb8df2d05f299a4a@linux-foundation.org>
To:     Andrew Morton <akpm@linux-foundation.org>
Sender: linux-kernel-owner@vger.kernel.org
Precedence: bulk

> Am 09.01.2020 um 23:28 schrieb Andrew Morton <akpm@linux-foundation.org>:
>=20
> =EF=BB=BFOn Thu, 9 Jan 2020 23:17:09 +0100 David Hildenbrand <david@redhat=
.com> wrote:
>=20
>>=20
>>=20
>>>> Am 09.01.2020 um 23:00 schrieb Andrew Morton <akpm@linux-foundation.org=
>:
>>>=20
>>> =EF=BB=BFOn Thu,  9 Jan 2020 15:25:16 -0600 Scott Cheloha <cheloha@linux=
.vnet.ibm.com> wrote:
>>>=20
>>>> 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.
>>>>=20
>>>> 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.
>>>>=20
>>>> ...
>>>>=20
>>>> @@ -56,6 +57,13 @@ static struct bus_type memory_subsys =3D {
>>>>   .offline =3D memory_subsys_offline,
>>>> };
>>>>=20
>>>> +/*
>>>> + * 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);
>>>=20
>>> What protects this tree from racy accesses?
>>=20
>> I think the device hotplug lock currently (except during boot where no ra=
ces can happen).
>>=20
>=20
> So this?
>=20
> --- a/drivers/base/memory.c~drivers-base-memoryc-cache-blocks-in-radix-tre=
e-to-accelerate-lookup-fix
> +++ a/drivers/base/memory.c
> @@ -61,6 +61,9 @@ static struct bus_type memory_subsys =3D {
>  * 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 guara=
nteed
> + * single-threadness at boot time.
>  */
> static RADIX_TREE(memory_blocks, GFP_KERNEL);
>=20
>=20
> But are we sure this is all true?

I think the device hotplug lock, not the memory hotplug lock. Will double ch=
eck later.
>=20