linux-kernel - Re: [PATCH v8 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: <61a2ff76-8f5c-30e5-5645-76ca07ba77f0@redhat.com>
Date:   Wed, 1 Nov 2017 09:16:49 -0400
From:   Waiman Long <longman@...hat.com>
To:     Jan Kara <jack@...e.cz>
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>,
        Davidlohr Bueso <dave@...olabs.net>
Subject: Re: [PATCH v8 5/6] lib/dlock-list: Enable faster lookup with hashing

On 11/01/2017 04:40 AM, Jan Kara wrote:
> On Tue 31-10-17 14:50:59, Waiman Long wrote:
>> Insertion and deletion is relatively cheap and mostly contention
>> free for dlock-list. Lookup, on the other hand, can be rather costly
>> because all the lists in a dlock-list will have to be iterated.
>>
>> Currently dlock-list insertion is based on the cpu that the task is
>> running on. So a given object can be inserted into any one of the
>> lists depending on what the current cpu is.
>>
>> 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.
>>
>> The new APIs are:
>>
>> struct dlock_list_head *dlock_list_hash(struct dlock_list_heads *, void *);
>> void dlock_list_add(struct dlock_list_node *, struct dlock_list_head *);
>>
>> Signed-off-by: Waiman Long <longman@...hat.com>
> Hum, do we have any users for this API? And wouldn't they also need to
> control how many lists are allocated then?

This patch is supposed to be used by the epoll patch from Davidlohr. As
he has retracted the patch, I can drop this patch also. The number of
lists scale with the number of CPU cores in the system whether it is
used one way or the others.

Cheers,
Longman