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] [thread-next>] [day] [month] [year] [list]

Message-ID: <20200108142104.GU32178@dhcp22.suse.cz>
Date:   Wed, 8 Jan 2020 15:21:04 +0100
From:   Michal Hocko <mhocko@...nel.org>
To:     David Hildenbrand <david@...hat.com>
Cc:     Scott Cheloha <cheloha@...ux.vnet.ibm.com>,
        linux-kernel@...r.kernel.org,
        "Rafael J. Wysocki" <rafael@...nel.org>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>,
        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 Wed 08-01-20 14:36:48, David Hildenbrand wrote:
> On 07.01.20 22:48, 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?
> 
> As reply to v1/v2 I argued that this is really only needed if there are
> many devices. So far that seems to be applicable to the memory subsystem
> mostly. No need to waste space on all other subsystems IMHO.

How much space are we talking about? Radix tree (resp. xarray) is a
small data structure and even when we have to allocate nodes dynamically
this doesn't sound like a huge overhead (especially with a small id
space). I might be missing something of course because I am not familiar
with this part the driver model and I would be interested what
maintainers think about that.

> As you said, right now it's easy and straightforward, if we find out
> other subsystems need it we can generalize/factor out.

I will not really push for that but it is almost always better to
improve a common infrastructure rather than build up a dedicated
workarouns in some users. Especially when there are no strong arguments
for that.
-- 
Michal Hocko
SUSE Labs