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
| ||
|
Date: Mon, 9 Oct 2017 10:16:21 -0400 From: Waiman Long <longman@...hat.com> To: Davidlohr Bueso <dave@...olabs.net> 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 10/09/2017 09:08 AM, Davidlohr Bueso wrote: > On Thu, 05 Oct 2017, 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. > > 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. I could also encapsulate it a bit with inlined function like dlock_list_single_iter_init(iter, dlist, head, flags) It could set up the iterator properly to iterate only 1 list. The flags can be to indicate holding the lock after iteration. In this case, dlock_list_unlock(iter) will have to be called to do the unlock. I could add a patch to do that if you prefer that route. Cheers, Longman
Powered by blists - more mailing lists