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]

Date:   Wed, 8 Jan 2020 16:23:04 +0100
From:   David Hildenbrand <david@...hat.com>
To:     Michal Hocko <mhocko@...nel.org>
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 08.01.20 15:21, Michal Hocko wrote:
> 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.

It's still wasted space even if it's not necessary in the common case.

> 
>> 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.

Yes, if it's worth for the common case :)

I don't really care in the and either, however, this seems to be the
easiest solution for now - IMHO.

-- 
Thanks,

David / dhildenb