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: <890c1d43-b5c6-e126-c228-cb8c062df654@redhat.com>
Date:   Wed, 8 Jan 2020 14:36:48 +0100
From:   David Hildenbrand <david@...hat.com>
To:     Michal Hocko <mhocko@...nel.org>,
        Scott Cheloha <cheloha@...ux.vnet.ibm.com>
Cc:     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 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.

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

-- 
Thanks,

David / dhildenb