linux-kernel - Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

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: <5038074D.300@gmail.com>
Date:	Sat, 25 Aug 2012 00:59:25 +0200
From:	Sasha Levin <levinsasha928@...il.com>
To:	Tejun Heo <tj@...nel.org>
CC:	torvalds@...ux-foundation.org, akpm@...ux-foundation.org,
	linux-kernel@...r.kernel.org, linux-mm@...ck.org,
	paul.gortmaker@...driver.com, davem@...emloft.net,
	rostedt@...dmis.org, mingo@...e.hu, ebiederm@...ssion.com,
	aarcange@...hat.com, ericvh@...il.com, netdev@...r.kernel.org,
	josh@...htriplett.org, eric.dumazet@...il.com,
	mathieu.desnoyers@...icios.com, axboe@...nel.dk, agk@...hat.com,
	dm-devel@...hat.com, neilb@...e.de, ccaulfie@...hat.com,
	teigland@...hat.com, Trond.Myklebust@...app.com,
	bfields@...ldses.org, fweisbec@...il.com, jesse@...ira.com,
	venkat.x.venkatsubra@...cle.com, ejt@...hat.com,
	snitzer@...hat.com, edumazet@...gle.com, linux-nfs@...r.kernel.org,
	dev@...nvswitch.org, rds-devel@....oracle.com, lw@...fujitsu.com
Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable

>> Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place yet
>> that needed direct access to the bucket itself.
> 
> Because whole hash table walking is much less common and we can avoid
> another full set of iterators.

I don't agree. Out of 32 places which now use a hashtable iterator of some kind,
12 of them (38%) walk the entire table.

The thing is that usually data structures are indexable by more than one key, so
usually hashtables are fully walked in cold paths to look for different keys.

Take kernel/workqueue.c for example: There are 4 places which do a key lookup
(find_worker_executing_work()) and 3 places which fully walk the entire table
(for_each_busy_worker()).

>> This basically means 11 macros/functions that would let us have full
>> encapsulation and will make it very easy for future implementations to work with
>> this API instead of making up a new one. It's also not significantly (+~2-3)
>> more than the ones you listed.
> 
> I'm not sure whether full encapsulation is a good idea for trivial
> hashtable.  For higher level stuff, sure but at this level I think
> benefits coming from known obvious implementation can be larger.
> e.g. suppose the caller knows certain entries to be way colder than
> others and wants to put them at the end of the chain.

Thats the thing, the amount of things of things you can do with a given bucket
is very limited. You can't add entries to any point besides the head (without
walking the entire list).

Basically you can do only two things with a bucket:

 - Add something to it at a very specific place.
 - Walk it

So I don't understand whats the point in exposing the internal structure of the
hashtable if there's nothing significant that can be gained from it by the user.

> 
> So, I think implmenting the minimal set of helpers which reflect the
> underlying trivial implementation explicitly could actually be better
> even when discounting the reduced number of wrappers.
> 
> Thanks.
> 

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/