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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <20200109095011.GM4951@dhcp22.suse.cz>
Date:   Thu, 9 Jan 2020 10:50:11 +0100
From:   Michal Hocko <mhocko@...nel.org>
To:     Greg Kroah-Hartman <gregkh@...uxfoundation.org>
Cc:     "Rafael J. Wysocki" <rafael@...nel.org>,
        linux-kernel@...r.kernel.org,
        Scott Cheloha <cheloha@...ux.vnet.ibm.com>,
        David Hildenbrand <david@...hat.com>, nathanl@...ux.ibm.com,
        ricklind@...ux.vnet.ibm.com,
        Andrew Morton <akpm@...ux-foundation.org>
Subject: Re: [PATCH v3] drivers/base/memory.c: cache blocks in radix tree to
 accelerate lookup

On Thu 09-01-20 10:33:59, Greg KH wrote:
> On Thu, Jan 09, 2020 at 10:19:34AM +0100, Michal Hocko wrote:
> > On Thu 09-01-20 09:56:23, Greg KH wrote:
> > > On Thu, Jan 09, 2020 at 09:49:55AM +0100, Michal Hocko wrote:
> > > > On Tue 07-01-20 22:48:04, Michal Hocko wrote:
> > > > > [Cc Andrew]
> > > > > 
> > > > > On Tue 17-12-19 13:32:38, Scott Cheloha wrote:
> > > > > > Searching for a particular memory block by id is slow because each block
> > > > > > device is kept in an unsorted linked list on the subsystem bus.
> > > > > 
> > > > > Noting that this is O(N^2) would be useful.
> > > > > 
> > > > > > Lookup is much faster if we cache the blocks in a radix tree.
> > > > > 
> > > > > While this is really easy and straightforward, is there any reason why
> > > > > subsys_find_device_by_id has to use such a slow lookup? I suspect nobody
> > > > > simply needed a more optimized data structure for that purpose yet.
> > > > > Would it be too hard to use radix tree for all lookups rather than
> > > > > adding a shadow copy for memblocks?
> > > > 
> > > > Greg, Rafael, this seems to be your domain. Do you have any opinion on
> > > > this?
> > > 
> > > No one has cared about the speed of that call as it has never been on
> > > any "fast path" that I know of.  And it should just be O(N), isn't it
> > > just walking the list of devices in order?
> > 
> > Which means that if you have to call it N times then it is O(N^2) and
> > that is the case here because you are adding N memblocks. See
> > memory_dev_init
> >   for each memblock
> >     add_memory_block
> >       init_memory_block
> >         find_memory_block_by_id # checks all existing devices
> >         register_memory
> > 	  device_register # add new device
> >   
> > In this particular case find_memory_block_by_id is called mostly to make
> > sure we are no re-registering something multiple times which shouldn't
> > happen so it sucks to spend a lot of time on that. We might think of
> > removing that for boot time but who knows what kind of surprises we
> > might see from crazy HW setups.
> 
> Ok, so this is a self-inflicted issue, not a driver core issue :)
> 
> > > If the "memory subsystem" wants a faster lookup for their objects,
> > > there's nothing stopping you from using your own data structure for the
> > > pointers to the objects if you want.  Just be careful about the lifetime
> > > rules.
> > 
> > The main question is whether replacing the linked list with a radix tree
> > in the generic code is something more meaningful.
> 
> I strongly doubt it, it looks like you all are doing something very
> specific to your subsystem that would need this type of speed/lookup.  I
> suggest doing it on your own for now.

OK, fair enough.
-- 
Michal Hocko
SUSE Labs