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: <20200109084955.GI4951@dhcp22.suse.cz>
Date:   Thu, 9 Jan 2020 09:49:55 +0100
From:   Michal Hocko <mhocko@...nel.org>
To:     "Rafael J. Wysocki" <rafael@...nel.org>,
        Greg Kroah-Hartman <gregkh@...uxfoundation.org>
Cc:     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 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?
-- 
Michal Hocko
SUSE Labs