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

[Jan Kara]

On Wed 04-10-17 17:20:06, 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@xxxxxxxxxx>

OK, this makes sense but do you have any particular user in mind? In
particular I'm not sure how big advantage this API brings over an existing
one in include/linux/list_bl.h. Sure it's a tradeoff between bitlock /
spinlock but is there a user where it matters?

								Honza
-- 
Jan Kara <jack@xxxxxxxx>
SUSE Labs, CR