(resending with correct netdev address)
Hi,
I thought I should quickly bring this patch up to date and write it up
properly, because IMO it is still useful. I earlier had tried to turn the
algorithm into a library that could be plugged into with specific lookup
functions and such, but that got really nasty and also difficult to retain
a really light fastpath. I don't think it is too nasty to open-code it...
Describe the "Dynamic dynamic data structure" (DDDS) algorithm, and implement
adaptive dcache hash table sizing using DDDS.
The dcache hash size is increased to the next power of 2 if the number
of dentries exceeds the current size of the dcache hash table. It is decreased
in size if it is currently more than 3 times the number of dentries.
This might be a dumb thing to do. It also currently performs the hash resizing
check for each dentry insertion/deletion, and calls the resizing in-line from
there: that's bad, because resizing takes several RCU grace periods. Rather it
should kick off a thread to do the resizing, or even have a background worker
thread checking the sizes periodically and resizing if required.
With this algorithm, I can fit a whole kernel source and git tree in my dcache
hash table that is still 1/8th the size it would be before the patch.
I'm cc'ing netdev because Dave did express some interest in using this for
some networking hashes, and network guys in general are pretty cluey when it
comes to hashes and such ;)
+static struct dcache_hash *alloc_dhash(int size)
+{
+ struct dcache_hash *dh;
+ unsigned long bytes;
+ unsigned int shift;
+ int i;
+
+ shift = ilog2(size);
+ BUG_ON(size != 1UL << shift);
+ bytes = size * sizeof(struct hlist_head *);
+
+ dh = kmalloc(sizeof(struct dcache_hash), GFP_KERNEL);
+ if (!dh)
+ return NULL;
+
+ if (bytes <= PAGE_SIZE) {
+ dh->table = kmalloc(bytes, GFP_KERNEL);
+ } else {
+ dh->table = vmalloc(bytes);
+ }