linux-kernel - Re: [PATCH v7 5/6] lib/dlock-list: Enable faster lookup with hashing

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: <20171009160304.GD5131@linux-80c1.suse>
Date:   Mon, 9 Oct 2017 09:03:04 -0700
From:   Davidlohr Bueso <dave@...olabs.net>
To:     Waiman Long <longman@...hat.com>
Cc:     Alexander Viro <viro@...iv.linux.org.uk>, Jan Kara <jack@...e.com>,
        Jeff Layton <jlayton@...chiereds.net>,
        "J. Bruce Fields" <bfields@...ldses.org>,
        Tejun Heo <tj@...nel.org>,
        Christoph Lameter <cl@...ux-foundation.org>,
        linux-fsdevel@...r.kernel.org, linux-kernel@...r.kernel.org,
        Ingo Molnar <mingo@...hat.com>,
        Peter Zijlstra <peterz@...radead.org>,
        Andi Kleen <andi@...stfloor.org>,
        Dave Chinner <dchinner@...hat.com>,
        Boqun Feng <boqun.feng@...il.com>
Subject: Re: [PATCH v7 5/6] lib/dlock-list: Enable faster lookup with hashing

On Mon, 09 Oct 2017, Waiman Long wrote:

>On 10/09/2017 09:08 AM, Davidlohr Bueso wrote:
>> On Thu, 05 Oct 2017, Waiman Long wrote:
>>
>>> This patch provides an alternative way of list selection. The caller
>>> can provide a object context which will be hashed to one of the list
>>> in a dlock-list. The object can then be added into that particular
>>> list. Lookup can be done by iterating elements in the provided list
>>> only instead of all the lists in a dlock-list.
>>
>> Unless I'm misusing the api, I could not find a standard way of
>> iterating a _particular_ list head (the one the dlock_list_hash()
>> returned). This is because iterators always want the all the heads.
>>
>> Also, in my particular epoll case I'd need the head->lock _not_ to
>> be dropped after the iteration, and therefore is pretty adhoc.
>> Currently we do:
>>
>> dlist_for_each_entry() {
>>     // acquire head->lock for each list
>> }
>> // no locks held
>> dlist_add()
>>
>> I'm thinking perhaps we could have dlist_check_add() which passes a
>> callback to ensure we want to add the node. The function could acquire
>> the head->lock and not release it until the very end.
>
>With the dlock_list_hash(), dlock-list is degenerated into a pool of
>list where one is chosen by hashing. So the regular list iteration
>macros like list_for_each_entry() can then be used. Of course, you have
>to explicitly do the lock and unlock operation.

Right, which seemed rather asymmetric and fragile, albeit adhoc to epoll.
Particularly not having the iter structure, makes use directly have to
deal with the spinlock, and there goes irq awareness out the window.

>I could also encapsulate it a bit with inlined function like

Probably not worth it, unless some other use cases came up. This just
bulks the api even more.

Thanks,
Davidlohr