Skip to contentSkip to conversation

dynamic resizing dentry hash using RCU

RFC PATCH In review Nick Piggin 8 participants 20 messages Feb 23, 2007 – Mar 5, 2007 VFS

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 dynamic resizing dentry hash using RCU

The dentry hash uses up 8MB for 1 million entries on my 4GB system is one of the biggest wasters of memory for me. Because I rarely have more than one or two hundred thousand dentries. And that's with several kernel trees worth of entries. Most desktop and probably even many types of servers will only use a fraction of that.

So I introduce a new method for resizing hash tables with RCU, and apply that to the dentry hash.

The primitive heuristic is that the hash size is doubled when the number of entries reaches 150% the hash size, and halved when the number is 50%. It should also be able to shrink under memory pressure, and scale up as large as we go.

A pity it uses vmalloc memory for the moment.

The implementation is not highly stress tested, but it is running now. It could do a bit more RCU stuff asynchronously rather than with synchronize_rcu, but who cares, for now.

The hash is costing me about 256K now, which is a 32x reduction in memory.

I don't know if it's worthwhile to do this, rather than move things to other data structures, but something just tempted me to have a go! I'd be interested to hear comments, and how many holes people can spot in my design ;)

Thanks,
Nick

RCU hash resizing algorithm as follows:

There is a 2 pointer system, the regular hash table, and an "old" hash table pointer which is NULL except when resizing the hash.

When resizing the hash table, the pointer is set to the current table, and the regular hash table pointer is switched from the current table to a newly initialised hash table (so the current table becomes the old table, and the new table becomes the current table). Memory barriers are used so a reader won't find a NULL old table AND a new, empty current table.

Then we wait for a grace period, so that all readers can see this new world order. Readers are anybody who wants to get a handle on the hash table, including to add entries to it (ie. the data we're protecting is the actual table -- hash entry locking is pretty well decoupled from this algorithm). So any new insertions should be going into the current table at this point.

Now we start moving hash entries from the old table into the current table. This is done under a seqlock, and we can do it bit by bit, as time and latency allow... After all entries are moved, then we set the "old" pointer to NULL, wait for a grace period (now no readers will have a handle on it), then free it.

On the read side, we load the current hash pointer and the old hash pointer first (remember this has to happen under rcu_read_lock). Then everything happens as normal when the old pointer is NULL, which is the common case. If the old pointer is not NULL, we have to be prepared to search both hash tables to find the entry we want. We also have to do this under the read seqlock in case we miss an entry when it is being moved from the old table to the current table as part of the resize process.

NOTE: you can be creative with the seqlock. It could be several seqlocks, if performance under resize is important. It doesn't even have to be a seqlock, just something to give you synchronisation. Say if you have a spinlock per
bucket: just hold locks for both buckets while doing the move from one to the other, and have the read-side search the old table first.

struct hash_table *table, *old_table;

lookup_hash()

{
	struct hash_table *cur, *old;

	rcu_read_lock();
	cur = table;
	smp_rmb();
	old = old_table;

	if (unlikely(old)) {
		do {
			read_seqbegin();
			entry = search_table(cur);
			if (!entry)
				entry = search_table(old);
		} while (read_seqretry());
	} else {
		entry = search_table(cur);
	}
	rcu_read_unlock();
}

resize_hash()

{
	init(new_table, new_size);

	old_table = table;
	smp_wmb();
	table = new_table;
	synchronize_rcu();

	for_each_entry_in(entry, old_table) {
		write_seqlock();
		rehash(entry, new_table);
		write_sequnlock();
	}

	tmp = old_table;
	old_table = NULL;
	synchronize_rcu();
	free(tmp);
}
 fs/dcache.c |  324 +++++++++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 243 insertions(+), 81 deletions(-)
fs/dcache.c +243 -81
Index: linux-2.6/fs/dcache.c
===================================================================
@@ -20,6 +20,7 @@
 #include <linux/fs.h>
 #include <linux/fsnotify.h>
 #include <linux/slab.h>
+#include <linux/vmalloc.h>
 #include <linux/init.h>
 #include <linux/smp_lock.h>
 #include <linux/hash.h>
@@ -31,15 +32,18 @@
 #include <linux/security.h>
 #include <linux/seqlock.h>
 #include <linux/swap.h>
-#include <linux/bootmem.h>
+#include <linux/mutex.h>
+#include <linux/kthread.h>
 #include "internal.h"
 
 
 int sysctl_vfs_cache_pressure __read_mostly = 100;
 EXPORT_SYMBOL_GPL(sysctl_vfs_cache_pressure);
 
- __cacheline_aligned_in_smp DEFINE_SPINLOCK(dcache_lock);
+__cacheline_aligned_in_smp DEFINE_SPINLOCK(dcache_lock);
 static __cacheline_aligned_in_smp DEFINE_SEQLOCK(rename_lock);
+static __cacheline_aligned_in_smp DEFINE_SEQLOCK(resize_transfer_lock);
+static DEFINE_MUTEX(resize_mutex);
 
 EXPORT_SYMBOL(dcache_lock);
 
@@ -55,12 +59,22 @@ static struct kmem_cache *dentry_cache _
  * This hash-function tries to avoid losing too many bits of hash
  * information, yet avoid using a prime hash-size or similar.
  */
-#define D_HASHBITS     d_hash_shift
-#define D_HASHMASK     d_hash_mask
+struct dentry_hash {
+	unsigned int shift;
+	unsigned long mask;
+	struct hlist_head *table;
+};
+
+struct dentry_hash *dentry_hash __read_mostly;
+struct dentry_hash *old_dentry_hash __read_mostly;
+
+#define MIN_DHASH_SHIFT 10 /* 4K */
+#if BITS_PER_LONG == 32
+#define MAX_DHASH_SHIFT 24 /* 64MB */
+#else
+#define MAX_DHASH_SHIFT 30 /* 8GB */
+#endif
 
-static unsigned int d_hash_mask __read_mostly;
-static unsigned int d_hash_shift __read_mostly;
-static struct hlist_head *dentry_hashtable __read_mostly;
 static LIST_HEAD(dentry_unused);
 
 /* Statistics gathering. */
@@ -68,6 +82,20 @@ struct dentry_stat_t dentry_stat = {
 	.age_limit = 45,
 };
 
+static void dcache_hash_resize(unsigned int new_shift);
+static void mod_nr_dentry(int mod)
+{
+	unsigned long dentry_size;
+
+	dentry_stat.nr_dentry += mod;
+
+	dentry_size = 1 << dentry_hash->shift;
+	if (unlikely(dentry_stat.nr_dentry > dentry_size+(dentry_size>>1)))
+		dcache_hash_resize(dentry_hash->shift+1);
+	else if (unlikely(dentry_stat.nr_dentry < (dentry_size>>1)))
+		dcache_hash_resize(dentry_hash->shift-1);
+}
+
 static void __d_free(struct dentry *dentry)
 {
 	if (dname_external(dentry))
@@ -201,7 +229,7 @@ kill_it: {
   			dentry_stat.nr_unused--;
   		}
   		list_del(&dentry->d_u.d_child);
-		dentry_stat.nr_dentry--;	/* For d_free, below */
+		mod_nr_dentry(-1);	/* For d_free, below */
 		/*drops the locks, at that point nobody can reach this dentry */
 		dentry_iput(dentry);
 		parent = dentry->d_parent;
@@ -380,7 +408,7 @@ static void prune_one_dentry(struct dent
 
 	__d_drop(dentry);
 	list_del(&dentry->d_u.d_child);
-	dentry_stat.nr_dentry--;	/* For d_free, below */
+	mod_nr_dentry(-1);		/* For d_free, below */
 	dentry_iput(dentry);
 	parent = dentry->d_parent;
 	d_free(dentry);
@@ -660,7 +688,7 @@ static void shrink_dcache_for_umount_sub
 out:
 	/* several dentries were freed, need to correct nr_dentry */
 	spin_lock(&dcache_lock);
-	dentry_stat.nr_dentry -= detached;
+	mod_nr_dentry(-detached);
 	spin_unlock(&dcache_lock);
 }
 
@@ -916,7 +944,7 @@ struct dentry *d_alloc(struct dentry * p
 	spin_lock(&dcache_lock);
 	if (parent)
 		list_add(&dentry->d_u.d_child, &parent->d_subdirs);
-	dentry_stat.nr_dentry++;
+	mod_nr_dentry(1);
 	spin_unlock(&dcache_lock);
 
 	return dentry;
@@ -1057,12 +1085,12 @@ struct dentry * d_alloc_root(struct inod
 	return res;
 }
 
-static inline struct hlist_head *d_hash(struct dentry *parent,
-					unsigned long hash)
+static inline struct hlist_head *d_hash(struct dentry_hash *hashtable,
+			struct dentry *parent, unsigned long hash)
 {
 	hash += ((unsigned long) parent ^ GOLDEN_RATIO_PRIME) / L1_CACHE_BYTES;
-	hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> D_HASHBITS);
-	return dentry_hashtable + (hash & D_HASHMASK);
+	hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> hashtable->shift);
+	return hashtable->table + (hash & hashtable->mask);
 }
 
 /**
@@ -1219,18 +1247,18 @@ struct dentry * d_lookup(struct dentry *
 	return dentry;
 }
 
-struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)
+static struct dentry * __d_lookup_hash(struct dentry_hash * hashtable,
+				struct dentry * parent, struct qstr * name)
 {
-	unsigned int len = name->len;
 	unsigned int hash = name->hash;
+	unsigned int len = name->len;
 	const unsigned char *str = name->name;
-	struct hlist_head *head = d_hash(parent,hash);
-	struct dentry *found = NULL;
 	struct hlist_node *node;
+	struct hlist_head *head;
 	struct dentry *dentry;
+	struct dentry *found = NULL;
 
-	rcu_read_lock();
-	
+	head = d_hash(hashtable, parent, hash);
 	hlist_for_each_entry_rcu(dentry, node, head, d_hash) {
 		struct qstr *qstr;
 
@@ -1273,9 +1301,39 @@ struct dentry * __d_lookup(struct dentry
 next:
 		spin_unlock(&dentry->d_lock);
  	}
+
+	return found;
+}
+
+struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)
+{
+	struct dentry *ret;
+	struct dentry_hash *hashtable, *old_hashtable;
+
+	rcu_read_lock();
+	hashtable = dentry_hash;
+	smp_rmb(); /* see smp_wmb in dcache_hash_resize_work */
+	old_hashtable = old_dentry_hash;
+
+	if (unlikely(old_hashtable)) {
+		unsigned long seq;
+		do {
+			seq = read_seqbegin(&resize_transfer_lock);
+			ret = __d_lookup_hash(old_hashtable, parent, name);
+			if (ret)
+				goto out_rcu;
+			ret = __d_lookup_hash(hashtable, parent, name);
+			if (ret)
+				goto out_rcu;
+		} while (read_seqretry(&resize_transfer_lock, seq));
+	} else {
+		ret = __d_lookup_hash(hashtable, parent, name);
+	}
+
+out_rcu:
  	rcu_read_unlock();
 
- 	return found;
+ 	return ret;
 }
 
 /**
@@ -1304,6 +1362,28 @@ out:
 	return dentry;
 }
 
+static int d_validate_hash(struct dentry_hash *hashtable,
+				struct dentry *dentry, struct dentry *parent)
+{
+	struct hlist_head *base;
+	struct hlist_node *lhp;
+
+	base = d_hash(hashtable, parent, dentry->d_name.hash);
+	spin_lock(&dcache_lock);
+	hlist_for_each(lhp,base) {
+		/* hlist_for_each_entry_rcu() not required for d_hash list
+		 * as it is parsed under dcache_lock
+		 */
+		if (dentry == hlist_entry(lhp, struct dentry, d_hash)) {
+			__dget_locked(dentry);
+			spin_unlock(&dcache_lock);
+			return 1;
+		}
+	}
+	spin_unlock(&dcache_lock);
+	return 0;
+}
+
 /**
  * d_validate - verify dentry provided from insecure source
  * @dentry: The dentry alleged to be valid child of @dparent
@@ -1316,33 +1396,42 @@ out:
  * Zero is returned in the dentry is invalid.
  */
  
-int d_validate(struct dentry *dentry, struct dentry *dparent)
+int d_validate(struct dentry *dentry, struct dentry *parent)
 {
-	struct hlist_head *base;
-	struct hlist_node *lhp;
+	struct dentry_hash *hashtable, *old_hashtable;
+	int ret = 0;
 
 	/* Check whether the ptr might be valid at all.. */
 	if (!kmem_ptr_validate(dentry_cache, dentry))
 		goto out;
 
-	if (dentry->d_parent != dparent)
+	if (dentry->d_parent != parent)
 		goto out;
 
-	spin_lock(&dcache_lock);
-	base = d_hash(dparent, dentry->d_name.hash);
-	hlist_for_each(lhp,base) { 
-		/* hlist_for_each_entry_rcu() not required for d_hash list
-		 * as it is parsed under dcache_lock
-		 */
-		if (dentry == hlist_entry(lhp, struct dentry, d_hash)) {
-			__dget_locked(dentry);
-			spin_unlock(&dcache_lock);
-			return 1;
-		}
+	rcu_read_lock();
+	hashtable = dentry_hash;
+	smp_rmb(); /* see smp_wmb in dcache_hash_resize_work */
+	old_hashtable = old_dentry_hash;
+
+	if (unlikely(old_hashtable)) {
+		unsigned long seq;
+		do {
+			seq = read_seqbegin(&resize_transfer_lock);
+			ret = d_validate_hash(old_hashtable, dentry, parent);
+			if (ret)
+				goto out_rcu;
+			ret = d_validate_hash(hashtable, dentry, parent);
+			if (ret)
+				goto out_rcu;
+		} while (read_seqretry(&resize_transfer_lock, seq));
+	} else {
+		ret = d_validate_hash(hashtable, dentry, parent);
 	}
-	spin_unlock(&dcache_lock);
+
+out_rcu:
+ 	rcu_read_unlock();
 out:
-	return 0;
+	return ret;
 }
 
 /*
@@ -1402,7 +1491,9 @@ static void __d_rehash(struct dentry * e
 
 static void _d_rehash(struct dentry * entry)
 {
-	__d_rehash(entry, d_hash(entry->d_parent, entry->d_name.hash));
+	rcu_read_lock();
+	__d_rehash(entry, d_hash(dentry_hash, entry->d_parent, entry->d_name.hash));
+	rcu_read_unlock();
 }
 
 /**
@@ -1518,8 +1609,10 @@ static void d_move_locked(struct dentry 
 	hlist_del_rcu(&dentry->d_hash);
 
 already_unhashed:
-	list = d_hash(target->d_parent, target->d_name.hash);
+	rcu_read_lock();
+	list = d_hash(dentry_hash, target->d_parent, target->d_name.hash);
 	__d_rehash(dentry, list);
+	rcu_read_unlock();
 
 	/* Unhash the target: dput() will then get rid of it */
 	__d_drop(target);
@@ -2009,42 +2102,114 @@ ino_t find_inode_number(struct dentry *d
 	return ino;
 }
 
-static __initdata unsigned long dhash_entries;
-static int __init set_dhash_entries(char *str)
+static unsigned int resize_new_shift;
+
+static void dcache_hash_resize_work(struct work_struct *work)
 {
-	if (!str)
-		return 0;
-	dhash_entries = simple_strtoul(str, &str, 0);
-	return 1;
+	unsigned long new_size, old_size;
+	int i;
+	struct dentry_hash *new_hash, *old_hash;
+	unsigned long transferred;
+
+	if (!mutex_trylock(&resize_mutex))
+		goto out;
+
+	new_hash = kmalloc(sizeof(struct dentry_hash), GFP_KERNEL);
+	if (!new_hash)
+		goto out_unlock;
+
+	new_hash->shift = resize_new_shift;
+	new_size = 1 << new_hash->shift;
+	new_hash->mask = new_size - 1;
+	new_hash->table = vmalloc(new_size*sizeof(struct hlist_head));
+	if (!new_hash->table)
+		goto out_kfree;
+	for (i = 0; i < new_size; i++)
+		INIT_HLIST_HEAD(&new_hash->table[i]);
+
+	old_dentry_hash = dentry_hash;
+	/*
+	 * ensure that if the reader sees the new dentry_hash,
+	 * then they will also see the old_dentry_hash assignment,
+	 * above.
+	 */
+	smp_wmb();
+	dentry_hash = new_hash;
+	synchronize_rcu();
+
+	old_size = 1 << old_dentry_hash->shift;
+	transferred = 0;
+	for (i = 0; i < old_size; i++) {
+		struct hlist_head *head = &old_dentry_hash->table[i];
+
+		if (hlist_empty(head))
+			continue;
+
+		spin_lock(&dcache_lock);
+		write_seqlock(&resize_transfer_lock);
+		while (!hlist_empty(head)) {
+			struct dentry *dentry;
+			struct hlist_head *new_head;
+
+			dentry = hlist_entry(head->first, struct dentry, d_hash);
+			new_head = d_hash(dentry_hash, dentry->d_parent, dentry->d_name.hash);
+
+			spin_lock(&dentry->d_lock);
+			hlist_del_rcu(head->first);
+ 			hlist_add_head_rcu(&dentry->d_hash, new_head);
+			spin_unlock(&dentry->d_lock);
+			transferred++;
+		}
+		write_sequnlock(&resize_transfer_lock);
+		spin_unlock(&dcache_lock);
+	}
+
+	printk("resize dcache hash from %lu to %lu, moved %lu entries\n", old_size, new_size, transferred);
+
+	old_hash = old_dentry_hash;
+	old_dentry_hash = NULL;
+	mutex_unlock(&resize_mutex);
+	synchronize_rcu();
+	vfree(old_hash->table);
+	kfree(old_hash);
+
+	resize_new_shift = 0;
+	return;
+
+out_kfree:
+	kfree(new_hash);
+out_unlock:
+	mutex_unlock(&resize_mutex);
+out:
+	resize_new_shift = 0;
+	return;
 }
-__setup("dhash_entries=", set_dhash_entries);
 
-static void __init dcache_init_early(void)
+static DEFINE_SPINLOCK(resize_lock);
+
+static void dcache_hash_resize(unsigned int new_shift)
 {
-	int loop;
+	static DECLARE_WORK(resize_work, dcache_hash_resize_work);
 
-	/* If hashes are distributed across NUMA nodes, defer
-	 * hash allocation until vmalloc space is available.
-	 */
-	if (hashdist)
+	if (new_shift < MIN_DHASH_SHIFT || new_shift > MAX_DHASH_SHIFT)
 		return;
 
-	dentry_hashtable =
-		alloc_large_system_hash("Dentry cache",
-					sizeof(struct hlist_head),
-					dhash_entries,
-					13,
-					HASH_EARLY,
-					&d_hash_shift,
-					&d_hash_mask,
-					0);
+	if (resize_new_shift)
+		return;
+	spin_lock(&resize_lock);
+	if (resize_new_shift) {
+		spin_unlock(&resize_lock);
+		return;
+	}
+	resize_new_shift = new_shift;
+	spin_unlock(&resize_lock);
 
-	for (loop = 0; loop < (1 << d_hash_shift); loop++)
-		INIT_HLIST_HEAD(&dentry_hashtable[loop]);
+	schedule_work(&resize_work);
 }
 
 static void __init dcache_init(unsigned long mempages)
 {
+	unsigned long hash_size;
 	int loop;
 
 	/* 
@@ -2061,22 +2226,20 @@ static void __init dcache_init(unsigned 
 	
 	set_shrinker(DEFAULT_SEEKS, shrink_dcache_memory);
 
-	/* Hash may have been set up in dcache_init_early */
-	if (!hashdist)
-		return;
-
-	dentry_hashtable =
-		alloc_large_system_hash("Dentry cache",
-					sizeof(struct hlist_head),
-					dhash_entries,
-					13,
-					0,
-					&d_hash_shift,
-					&d_hash_mask,
-					0);
+	old_dentry_hash = NULL;
 
-	for (loop = 0; loop < (1 << d_hash_shift); loop++)
-		INIT_HLIST_HEAD(&dentry_hashtable[loop]);
+	dentry_hash = kmalloc(sizeof(struct dentry_hash), GFP_ATOMIC);
+	if (!dentry_hash)
+		panic("Failed to allocate dentry_hash\n");
+	dentry_hash->shift = MIN_DHASH_SHIFT;
+	hash_size = 1 << dentry_hash->shift;
+	dentry_hash->mask = hash_size - 1;
+	dentry_hash->table = __vmalloc(hash_size*sizeof(struct hlist_head),
+					GFP_ATOMIC, PAGE_KERNEL);
+	if (!dentry_hash->table)
+		panic("Failed to allocate dentry_hash->table\n");
+	for (loop = 0; loop < hash_size; loop++)
+		INIT_HLIST_HEAD(&dentry_hash->table[loop]);
 }
 
 /* SLAB cache for __getname() consumers */
@@ -2089,7 +2252,6 @@ EXPORT_SYMBOL(d_genocide);
 
 void __init vfs_caches_init_early(void)
 {
-	dcache_init_early();
 	inode_init_early();
 }
 
#1 lore raw
Quoted 22 lines · Nick Piggin

The dentry hash uses up 8MB for 1 million entries on my 4GB system is one of the biggest wasters of memory for me. Because I rarely have more than one or two hundred thousand dentries. And that's with several kernel trees worth of entries. Most desktop and probably even many types of servers will only use a fraction of that.

So I introduce a new method for resizing hash tables with RCU, and apply that to the dentry hash.

The primitive heuristic is that the hash size is doubled when the number of entries reaches 150% the hash size, and halved when the number is 50%. It should also be able to shrink under memory pressure, and scale up as large as we go.

A pity it uses vmalloc memory for the moment.

The implementation is not highly stress tested, but it is running now. It could do a bit more RCU stuff asynchronously rather than with synchronize_rcu, but who cares, for now.

The hash is costing me about 256K now, which is a 32x reduction in memory.

Quoted 7 lines

I don't know if it's worthwhile to do this, rather than move things to other data structures, but something just tempted me to have a go! I'd be interested to hear comments, and how many holes people can spot in my design ;)

Thanks,
Nick

Hi Nick

Thats a really good idea !

The vmalloc() thing could be a problem, so :

Could you bring back the support of 'dhash_entries=262144' boot param, so that an admin could set the initial size of dhash table, (and not shrink it under this size even if the number of dentries is low)

In case dhash_entries is set in boot params, we could try to use alloc_large_system_hash() for the initial table, (eventually using Hugepages (not vmalloc)), if we add a free_large_system_hash() function to be able to free the initial table.

Or else, time is to add the possibility for vmalloc() to use hugepages itself...

#2 lore raw
Quoted 33 lines · Eric Dumazet
Quoted 22 lines · Nick Piggin

The dentry hash uses up 8MB for 1 million entries on my 4GB system is one of the biggest wasters of memory for me. Because I rarely have more than one or two hundred thousand dentries. And that's with several kernel trees worth of entries. Most desktop and probably even many types of servers will only use a fraction of that.

So I introduce a new method for resizing hash tables with RCU, and apply that to the dentry hash.

The primitive heuristic is that the hash size is doubled when the number of entries reaches 150% the hash size, and halved when the number is 50%. It should also be able to shrink under memory pressure, and scale up as large as we go.

A pity it uses vmalloc memory for the moment.

The implementation is not highly stress tested, but it is running now. It could do a bit more RCU stuff asynchronously rather than with synchronize_rcu, but who cares, for now.

The hash is costing me about 256K now, which is a 32x reduction in memory.

Quoted 7 lines

I don't know if it's worthwhile to do this, rather than move things to other data structures, but something just tempted me to have a go! I'd be interested to hear comments, and how many holes people can spot in my design ;)

Thanks,
Nick

Hi Nick

Quoted 7 lines

Thats a really good idea !

The vmalloc() thing could be a problem, so :

Could you bring back the support of 'dhash_entries=262144' boot param, so that an admin could set the initial size of dhash table, (and not shrink it under this size even if the number of dentries is low)

Hi Eric,

Yeah, that's a good idea. I'll look at doing that.

Quoted 7 lines

In case dhash_entries is set in boot params, we could try to use alloc_large_system_hash() for the initial table, (eventually using Hugepages (not vmalloc)), if we add a free_large_system_hash() function to be able to free the initial table.

Or else, time is to add the possibility for vmalloc() to use hugepages itself...

That sounds like a nice idea to have a hugepage vmalloc for very large allocations. The big NUMA guys already use vmalloc to allocate large hashes, so hugepages would probably be a big win for them.

#3 lore raw
In reply to Nick Piggin
Quoted 9 lines · Nick Piggin

The dentry hash uses up 8MB for 1 million entries on my 4GB system is one of the biggest wasters of memory for me. Because I rarely have more than one or two hundred thousand dentries. And that's with several kernel trees worth of entries. Most desktop and probably even many types of servers will only use a fraction of that.

So I introduce a new method for resizing hash tables with RCU, and apply that to the dentry hash.

Can you compare what you've done to the design that Paul and David talked about a year ago?

http://lkml.org/lkml/2006/1/30/74

I'd love to see a generic implementation of RCU hashing that subsystems can then take advantage of. It's long been on the fun side of my todo list. The side I never get to :/.

- z

#4 lore raw
Quoted 14 lines · Zach Brown
Quoted 11 lines · Nick Piggin

The dentry hash uses up 8MB for 1 million entries on my 4GB system is one
of the biggest wasters of memory for me. Because I rarely have more than one or
two hundred thousand dentries. And that's with several kernel trees worth of
entries. Most desktop and probably even many types of servers will only use a
fraction of that.

Quoted 8 lines
Quoted 3 lines

So I introduce a new method for resizing hash tables with RCU, and apply
that to the dentry hash.

Can you compare what you've done to the design that Paul and David talked about a year ago?

http://lkml.org/lkml/2006/1/30/74

Thanks for the link, I wasn't aware of Paul's algorithm before.

I guess most variants are going to have a double pointer scheme, so they are similar in that regard.

I think Paul's is quite complex in moving entries to the new table, and it looks like it requires a lot of grace periods. I avoid all that by using the seqlock.

It wasn't clear to me how Paul handled the case where an item is present in the not_current table, but the lookup misses it when it gets moved between the tables. It is a little tricky to follow the find details because it is not in code or pseudo code format.

Quoted 3 lines

I'd love to see a generic implementation of RCU hashing that subsystems can then take advantage of. It's long been on the fun side of my todo list. The side I never get to :/.

Yeah if this is to be used anywhere else, I think it definitely needs to be made into a generic library if possible. Main thing I wanted was to get something working and see what people think about it.

Thanks,
Nick

#5 lore raw
Quoted 29 lines · Nick Piggin
Quoted 14 lines · Zach Brown
Quoted 11 lines · Nick Piggin

The dentry hash uses up 8MB for 1 million entries on my 4GB system is one
of the biggest wasters of memory for me. Because I rarely have more than one or
two hundred thousand dentries. And that's with several kernel trees worth of
entries. Most desktop and probably even many types of servers will only use a
fraction of that.

Quoted 8 lines
Quoted 3 lines

So I introduce a new method for resizing hash tables with RCU, and apply
that to the dentry hash.

Can you compare what you've done to the design that Paul and David talked about a year ago?

http://lkml.org/lkml/2006/1/30/74

Thanks for the link, I wasn't aware of Paul's algorithm before.

I guess most variants are going to have a double pointer scheme, so they are similar in that regard.

Quoted 8 lines

I think Paul's is quite complex in moving entries to the new table, and it looks like it requires a lot of grace periods. I avoid all that by using the seqlock.

It wasn't clear to me how Paul handled the case where an item is present in the not_current table, but the lookup misses it when it gets moved between the tables. It is a little tricky to follow the find details because it is not in code or pseudo code format.

I guess the other thing is that Paul's seems quite hash specific, wheras mine does not have to be tied to any particular data strcture.

All you need it to know how to perform a lookup on both your old and new data structure, and the same algorithm is basically applicable to switching between any 2 data structures.

#6 lore raw
In reply to Zach Brown
Quoted 3 lines · Zach Brown

I'd love to see a generic implementation of RCU hashing that subsystems can then take advantage of. It's long been on the fun side of my todo list. The side I never get to :/.

There's an active thread on netdev about implementing an RCU hash. I'd suggest a 2-left (or possibly even k-left) hash for statistical reasons discussed briefly there, and in greater depth in a paper by Michael Mitzenmacher at www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/iproute.ps. Despite his paper's emphasis on hardware parallelism, there's a bigger win associated with Poisson statistics and decreasing occupation fraction (and therefore collision probability) in successive hashes.

Cheers,
- Michael

#7 lore raw
Quoted 5 lines · Michael K. Edwards
Quoted 3 lines · Zach Brown

I'd love to see a generic implementation of RCU hashing that subsystems can then take advantage of. It's long been on the fun side of my todo list. The side I never get to :/.

Quoted 8 lines

There's an active thread on netdev about implementing an RCU hash. I'd suggest a 2-left (or possibly even k-left) hash for statistical reasons discussed briefly there, and in greater depth in a paper by Michael Mitzenmacher at www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/iproute.ps. Despite his paper's emphasis on hardware parallelism, there's a bigger win associated with Poisson statistics and decreasing occupation fraction (and therefore collision probability) in successive hashes.

Thanks for the link, I'll take a look.

I'm *pretty* sure that my algorithm will work with any kind of data structure. It could even change from one to another completely different data structure.

The important point is that, when a switch is in progress, the data structure effectively becomes the union of the old and the new. Readers insert items only into the new structure, but it is implicit that they have checked for collisions in the union (in the case where collisions are possible).

And finally, (you probably gathered this, but I'll just make it clear), I haven't implemented a lockless hash lookup. The dcache already has this. My algorithm is a lockless dynamic data structure switch, rather than having anything specifically to do with a specific type of hash, or even a hash at all. So yes, it should be applicable to resizing a 2-left hash or whatever.

Thanks,
Nick

#8 lore raw
In reply to Nick Piggin
Quoted 4 lines · On Fri, 23 Feb 2007 16:37:43 +0100 Nick Piggin <[email protected]> wrote:
fs/dcache.c +4 -0
+static void dcache_hash_resize(unsigned int new_shift);
+static void mod_nr_dentry(int mod)
+{
+	unsigned long dentry_size;

fs/dcache.c struct dentry_stat_t dentry_stat = { · line 98

Quoted 10 lines
fs/dcache.c +10 -0
+
+	dentry_stat.nr_dentry += mod;
+
+	dentry_size = 1 << dentry_hash->shift;
+	if (unlikely(dentry_stat.nr_dentry > dentry_size+(dentry_size>>1)))
+		dcache_hash_resize(dentry_hash->shift+1);
+	else if (unlikely(dentry_stat.nr_dentry < (dentry_size>>1)))
+		dcache_hash_resize(dentry_hash->shift-1);
+}
+

Do we need to do this kind of resizing in implicit automatic way ? I think it's good to show contention rate by /proc and add sysctl for resize this.

-Kame

#9 lore raw
Quoted 13 lines · KAMEZAWA Hiroyuki
Quoted 10 lines · On Fri, 23 Feb 2007 16:37:43 +0100 Nick Piggin <[email protected]> wrote:
fs/dcache.c +10 -0
+static void dcache_hash_resize(unsigned int new_shift);
+static void mod_nr_dentry(int mod)
+{
+	unsigned long dentry_size;
+
+	dentry_stat.nr_dentry += mod;
+
+	dentry_size = 1 << dentry_hash->shift;
+	if (unlikely(dentry_stat.nr_dentry > dentry_size+(dentry_size>>1)))
+		dcache_hash_resize(dentry_hash->shift+1);
Quoted 8 lines

fs/dcache.c struct dentry_stat_t dentry_stat = { · line 98

Quoted 4 lines
fs/dcache.c +4 -0
+	else if (unlikely(dentry_stat.nr_dentry < (dentry_size>>1)))
+		dcache_hash_resize(dentry_hash->shift-1);
+}
+

Do we need to do this kind of resizing in implicit automatic way ? I think it's good to show contention rate by /proc and add sysctl for resize this.

Well having the kernel automatically adjust to the workload is better than a sysctl. But it could well be the case that these simple heuristics are bad (though they're fine for my system).

But a manual override is a good idea as well.

#10 lore raw
In reply to Nick Piggin
Quoted 11 lines · Nick Piggin

The dentry hash uses up 8MB for 1 million entries on my 4GB system is one of the biggest wasters of memory for me. Because I rarely have more than one or two hundred thousand dentries. And that's with several kernel trees worth of entries. Most desktop and probably even many types of servers will only use a fraction of that.
So I introduce a new method for resizing hash tables with RCU, and apply that to the dentry hash.
The primitive heuristic is that the hash size is doubled when the number of entries reaches 150% the hash size, and halved when the number is 50%. It should also be able to shrink under memory pressure, and scale up as large as we go.

You would be better served by a data structure different from a hashtable.

-- wli

#11 lore raw
Quoted 13 lines · William Lee Irwin III
Quoted 11 lines · Nick Piggin

The dentry hash uses up 8MB for 1 million entries on my 4GB system is one of the biggest wasters of memory for me. Because I rarely have more than one or two hundred thousand dentries. And that's with several kernel trees worth of entries. Most desktop and probably even many types of servers will only use a fraction of that.
So I introduce a new method for resizing hash tables with RCU, and apply that to the dentry hash.
The primitive heuristic is that the hash size is doubled when the number of entries reaches 150% the hash size, and halved when the number is 50%. It should also be able to shrink under memory pressure, and scale up as large as we go.

Quoted 1 line

You would be better served by a data structure different from a hashtable.

Possibly. Note that I wasn't intending to rewrite the dcache hash specifically, but just demonstrate my lockless dynamic data structure switch, and the dentry hash was the most obvious candidate.

But considering that it is lockless, and basically free in the fastpath (ie. a single easily-predicted branch), then I'm better served by an dynamically sized dynamic hash table than an inappropriately sized one.

Well, almost. The vmalloc issue is the downside, of course. But if I'm on a NUMA that is doing vmalloc hashes anyway, then there is little downside.

Out of curiosity, what better data structure do you have in mind for the dentry hash?

#12 lore raw
Quoted 1 line · William Lee Irwin III
Quoted 1 line

You would be better served by a data structure different from a hashtable.

Quoted 2 lines · Nick Piggin

Out of curiosity, what better data structure do you have in mind for the dentry hash?

Per-directory indices of ->d_subdirs. Hash tries (spelled correctly) and B+ trees hung off dentries corresponding to directories are plausible. There are plenty of other possibilities; just do it on a per-directory basis so you don't intermix children of different parents in some boot-time -allocated global trainwreck and you're home free. Benchmarking is probably needed to gauge which performs best.

-- wli

#13 lore raw

From: William Lee Irwin III <[email protected]>
Date: Sat, 24 Feb 2007 14:56:31 -0800

Quoted 4 lines

just do it on a per-directory basis so you don't intermix children of different parents in some boot-time -allocated global trainwreck and you're home free. Benchmarking is probably needed to gauge which performs best.

The original dentry implementation in the kernel did things per-directory and it sucked.

The problem you run into is that you end up with recursive algorithms all over the place, which chew up and overflow the kernel stack.

So it would be a regression to go to a per-directory type lookup data structure for dentries.

#14 lore raw
Quoted 6 lines

From: William Lee Irwin III <[email protected]>
Date: Sat, 24 Feb 2007 14:56:31 -0800

Quoted 4 lines

just do it on a per-directory basis so you don't intermix children of different parents in some boot-time -allocated global trainwreck and you're home free. Benchmarking is probably needed to gauge which performs best.

Quoted 6 lines · David Miller

The original dentry implementation in the kernel did things per-directory and it sucked.
The problem you run into is that you end up with recursive algorithms all over the place, which chew up and overflow the kernel stack. So it would be a regression to go to a per-directory type lookup data structure for dentries.

Recursive code is clearly inadmissible in kernel environments. Any implementations would clearly be required to be coded iteratively. It's unclear to me where the choice of data structure would make a demand for recursive code, but wherever it ostensibly does so, an explicitly-allocated stack (or queue or worklist of whatever sort) should be able to unravel it. There are furthermore rather stringent bounds on balanced tree heights due to address space limits, so whatever explicitly-allocated stacks may be required for e.g. tree balancing algorithms are tightly bounded in depth.

The usual objection is to lexicographically ordered balanced trees such as B+ trees on the grounds that string comparison is cache- intensive. Hash tries resolve that concern, albeit at the amortized cost of expansion and contraction of what are effectively nodes in a radix tree with a large radix as well as undoing path compression where required (speaking of which, lib/radix-tree.c should really do path compression instead of the ->depth hack). The quest, as I see it, is for self-sizing data structures with as little restructuring and direct key (string) comparison as possible. Should the obvious candidates not incur significant overhead on account of where they do such, maybe they're good enough.

So I'm not sure what else to say as far as the per-directory lookup structure commentary goes. There's no way I'd propose putting recursive code in the kernel. I don't believe any of what I'm talking about requires such. I'm aware of various drawbacks the algorithms have, and have in mind that they should pass benchmark criteria in addition to reducing kernel memory consumption in order to prove that they don't overwhelm the putative benefits. So I think I've got all the bases covered.

Am I off-base on any of this? Is there anything I missed?

-- wli

(P.S.: The only time I ever proposed putting something "recursive" in the kernel, it used a flag to limit the recursion depth to two stack frames. It was for the purpose of simplifying the reservation of metadata in an allocator, and so not strictly necessary. A simplified metadata allocator could've easily been devised, albeit at the cost of some code duplication.)

#15 lore raw
In reply to Nick Piggin
Quoted 21 lines · Nick Piggin

The dentry hash uses up 8MB for 1 million entries on my 4GB system is one of the biggest wasters of memory for me. Because I rarely have more than one or two hundred thousand dentries. And that's with several kernel trees worth of entries. Most desktop and probably even many types of servers will only use a fraction of that.

So I introduce a new method for resizing hash tables with RCU, and apply that to the dentry hash.

The primitive heuristic is that the hash size is doubled when the number of entries reaches 150% the hash size, and halved when the number is 50%. It should also be able to shrink under memory pressure, and scale up as large as we go.

A pity it uses vmalloc memory for the moment.

The implementation is not highly stress tested, but it is running now. It could do a bit more RCU stuff asynchronously rather than with synchronize_rcu, but who cares, for now.

Quoted 5 lines

The hash is costing me about 256K now, which is a 32x reduction in memory.

I don't know if it's worthwhile to do this, rather than move things to other data structures, but something just tempted me to have a go! I'd be interested to hear comments, and how many holes people can spot in my design ;)

The pseudocode looks sound to me. The discussion on netdev has a few alternatives that are interesting as well -- one of them gets rid of the need for the sequence lock using a trick similar to one that Josh Triplett came up with for atomically moving an element from one list to another in face of RCU readers. Another is Robert Ohlsson's "trash" trie-hash implementation.

Some rather impressive algorithms all around!

Thanx, Paul

Quoted 593 lines

Thanks,
Nick

RCU hash resizing algorithm as follows:

There is a 2 pointer system, the regular hash table, and an "old" hash table pointer which is NULL except when resizing the hash.

When resizing the hash table, the pointer is set to the current table, and the regular hash table pointer is switched from the current table to a newly initialised hash table (so the current table becomes the old table, and the new table becomes the current table). Memory barriers are used so a reader won't find a NULL old table AND a new, empty current table.

Then we wait for a grace period, so that all readers can see this new world order. Readers are anybody who wants to get a handle on the hash table, including to add entries to it (ie. the data we're protecting is the actual table -- hash entry locking is pretty well decoupled from this algorithm). So any new insertions should be going into the current table at this point.

Now we start moving hash entries from the old table into the current table. This is done under a seqlock, and we can do it bit by bit, as time and latency allow... After all entries are moved, then we set the "old" pointer to NULL, wait for a grace period (now no readers will have a handle on it), then free it.

On the read side, we load the current hash pointer and the old hash pointer first (remember this has to happen under rcu_read_lock). Then everything happens as normal when the old pointer is NULL, which is the common case. If the old pointer is not NULL, we have to be prepared to search both hash tables to find the entry we want. We also have to do this under the read seqlock in case we miss an entry when it is being moved from the old table to the current table as part of the resize process.

NOTE: you can be creative with the seqlock. It could be several seqlocks, if performance under resize is important. It doesn't even have to be a seqlock, just something to give you synchronisation. Say if you have a spinlock per
bucket: just hold locks for both buckets while doing the move from one to the other, and have the read-side search the old table first.

struct hash_table *table, *old_table;

lookup_hash()

{
	struct hash_table *cur, *old;

	rcu_read_lock();
	cur = table;
	smp_rmb();
	old = old_table;

	if (unlikely(old)) {
		do {
			read_seqbegin();
			entry = search_table(cur);
			if (!entry)
				entry = search_table(old);
		} while (read_seqretry());
	} else {
		entry = search_table(cur);
	}
	rcu_read_unlock();
}

resize_hash()

{
	init(new_table, new_size);

	old_table = table;
	smp_wmb();
	table = new_table;
	synchronize_rcu();

	for_each_entry_in(entry, old_table) {
		write_seqlock();
		rehash(entry, new_table);
		write_sequnlock();
	}

	tmp = old_table;
	old_table = NULL;
	synchronize_rcu();
	free(tmp);
}
 fs/dcache.c |  324 +++++++++++++++++++++++++++++++++++++++++++++---------------
 1 file changed, 243 insertions(+), 81 deletions(-)

Index: linux-2.6/fs/dcache.c
===================================================================

fs/dcache.c +243 -82
@@ -20,6 +20,7 @@
 #include <linux/fs.h>
 #include <linux/fsnotify.h>
 #include <linux/slab.h>
+#include <linux/vmalloc.h>
 #include <linux/init.h>
 #include <linux/smp_lock.h>
 #include <linux/hash.h>
@@ -31,15 +32,18 @@
 #include <linux/security.h>
 #include <linux/seqlock.h>
 #include <linux/swap.h>
-#include <linux/bootmem.h>
+#include <linux/mutex.h>
+#include <linux/kthread.h>
 #include "internal.h"
 
 
 int sysctl_vfs_cache_pressure __read_mostly = 100;
 EXPORT_SYMBOL_GPL(sysctl_vfs_cache_pressure);
 
- __cacheline_aligned_in_smp DEFINE_SPINLOCK(dcache_lock);
+__cacheline_aligned_in_smp DEFINE_SPINLOCK(dcache_lock);
 static __cacheline_aligned_in_smp DEFINE_SEQLOCK(rename_lock);
+static __cacheline_aligned_in_smp DEFINE_SEQLOCK(resize_transfer_lock);
+static DEFINE_MUTEX(resize_mutex);
 
 EXPORT_SYMBOL(dcache_lock);
 
@@ -55,12 +59,22 @@ static struct kmem_cache *dentry_cache _
  * This hash-function tries to avoid losing too many bits of hash
  * information, yet avoid using a prime hash-size or similar.
  */
-#define D_HASHBITS     d_hash_shift
-#define D_HASHMASK     d_hash_mask
+struct dentry_hash {
+	unsigned int shift;
+	unsigned long mask;
+	struct hlist_head *table;
+};
+
+struct dentry_hash *dentry_hash __read_mostly;
+struct dentry_hash *old_dentry_hash __read_mostly;
+
+#define MIN_DHASH_SHIFT 10 /* 4K */
+#if BITS_PER_LONG == 32
+#define MAX_DHASH_SHIFT 24 /* 64MB */
+#else
+#define MAX_DHASH_SHIFT 30 /* 8GB */
+#endif
 
-static unsigned int d_hash_mask __read_mostly;
-static unsigned int d_hash_shift __read_mostly;
-static struct hlist_head *dentry_hashtable __read_mostly;
 static LIST_HEAD(dentry_unused);
 
 /* Statistics gathering. */
@@ -68,6 +82,20 @@ struct dentry_stat_t dentry_stat = {
 	.age_limit = 45,
 };
 
+static void dcache_hash_resize(unsigned int new_shift);
+static void mod_nr_dentry(int mod)
+{
+	unsigned long dentry_size;
+
+	dentry_stat.nr_dentry += mod;
+
+	dentry_size = 1 << dentry_hash->shift;
+	if (unlikely(dentry_stat.nr_dentry > dentry_size+(dentry_size>>1)))
+		dcache_hash_resize(dentry_hash->shift+1);
+	else if (unlikely(dentry_stat.nr_dentry < (dentry_size>>1)))
+		dcache_hash_resize(dentry_hash->shift-1);
+}
+
 static void __d_free(struct dentry *dentry)
 {
 	if (dname_external(dentry))
@@ -201,7 +229,7 @@ kill_it: {
   			dentry_stat.nr_unused--;
   		}
   		list_del(&dentry->d_u.d_child);
-		dentry_stat.nr_dentry--;	/* For d_free, below */
+		mod_nr_dentry(-1);	/* For d_free, below */
 		/*drops the locks, at that point nobody can reach this dentry */
 		dentry_iput(dentry);
 		parent = dentry->d_parent;
@@ -380,7 +408,7 @@ static void prune_one_dentry(struct dent
 
 	__d_drop(dentry);
 	list_del(&dentry->d_u.d_child);
-	dentry_stat.nr_dentry--;	/* For d_free, below */
+	mod_nr_dentry(-1);		/* For d_free, below */
 	dentry_iput(dentry);
 	parent = dentry->d_parent;
 	d_free(dentry);
@@ -660,7 +688,7 @@ static void shrink_dcache_for_umount_sub
 out:
 	/* several dentries were freed, need to correct nr_dentry */
 	spin_lock(&dcache_lock);
-	dentry_stat.nr_dentry -= detached;
+	mod_nr_dentry(-detached);
 	spin_unlock(&dcache_lock);
 }
 
@@ -916,7 +944,7 @@ struct dentry *d_alloc(struct dentry * p
 	spin_lock(&dcache_lock);
 	if (parent)
 		list_add(&dentry->d_u.d_child, &parent->d_subdirs);
-	dentry_stat.nr_dentry++;
+	mod_nr_dentry(1);
 	spin_unlock(&dcache_lock);
 
 	return dentry;
@@ -1057,12 +1085,12 @@ struct dentry * d_alloc_root(struct inod
 	return res;
 }
 
-static inline struct hlist_head *d_hash(struct dentry *parent,
-					unsigned long hash)
+static inline struct hlist_head *d_hash(struct dentry_hash *hashtable,
+			struct dentry *parent, unsigned long hash)
 {
 	hash += ((unsigned long) parent ^ GOLDEN_RATIO_PRIME) / L1_CACHE_BYTES;
-	hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> D_HASHBITS);
-	return dentry_hashtable + (hash & D_HASHMASK);
+	hash = hash ^ ((hash ^ GOLDEN_RATIO_PRIME) >> hashtable->shift);
+	return hashtable->table + (hash & hashtable->mask);
 }
 
 /**
@@ -1219,18 +1247,18 @@ struct dentry * d_lookup(struct dentry *
 	return dentry;
 }
 
-struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)
+static struct dentry * __d_lookup_hash(struct dentry_hash * hashtable,
+				struct dentry * parent, struct qstr * name)
 {
-	unsigned int len = name->len;
 	unsigned int hash = name->hash;
+	unsigned int len = name->len;
 	const unsigned char *str = name->name;
-	struct hlist_head *head = d_hash(parent,hash);
-	struct dentry *found = NULL;
 	struct hlist_node *node;
+	struct hlist_head *head;
 	struct dentry *dentry;
+	struct dentry *found = NULL;
 
-	rcu_read_lock();
-	
+	head = d_hash(hashtable, parent, hash);
 	hlist_for_each_entry_rcu(dentry, node, head, d_hash) {
 		struct qstr *qstr;
 
@@ -1273,9 +1301,39 @@ struct dentry * __d_lookup(struct dentry
 next:
 		spin_unlock(&dentry->d_lock);
  	}
+
+	return found;
+}
+
+struct dentry * __d_lookup(struct dentry * parent, struct qstr * name)
+{
+	struct dentry *ret;
+	struct dentry_hash *hashtable, *old_hashtable;
+
+	rcu_read_lock();
+	hashtable = dentry_hash;
+	smp_rmb(); /* see smp_wmb in dcache_hash_resize_work */
+	old_hashtable = old_dentry_hash;
+
+	if (unlikely(old_hashtable)) {
+		unsigned long seq;
+		do {
+			seq = read_seqbegin(&resize_transfer_lock);
+			ret = __d_lookup_hash(old_hashtable, parent, name);
+			if (ret)
+				goto out_rcu;
+			ret = __d_lookup_hash(hashtable, parent, name);
+			if (ret)
+				goto out_rcu;
+		} while (read_seqretry(&resize_transfer_lock, seq));
+	} else {
+		ret = __d_lookup_hash(hashtable, parent, name);
+	}
+
+out_rcu:
  	rcu_read_unlock();
 
- 	return found;
+ 	return ret;
 }
 
 /**
@@ -1304,6 +1362,28 @@ out:
 	return dentry;
 }
 
+static int d_validate_hash(struct dentry_hash *hashtable,
+				struct dentry *dentry, struct dentry *parent)
+{
+	struct hlist_head *base;
+	struct hlist_node *lhp;
+
+	base = d_hash(hashtable, parent, dentry->d_name.hash);
+	spin_lock(&dcache_lock);
+	hlist_for_each(lhp,base) {
+		/* hlist_for_each_entry_rcu() not required for d_hash list
+		 * as it is parsed under dcache_lock
+		 */
+		if (dentry == hlist_entry(lhp, struct dentry, d_hash)) {
+			__dget_locked(dentry);
+			spin_unlock(&dcache_lock);
+			return 1;
+		}
+	}
+	spin_unlock(&dcache_lock);
+	return 0;
+}
+
 /**
  * d_validate - verify dentry provided from insecure source
  * @dentry: The dentry alleged to be valid child of @dparent
@@ -1316,33 +1396,42 @@ out:
  * Zero is returned in the dentry is invalid.
  */
 
-int d_validate(struct dentry *dentry, struct dentry *dparent)
+int d_validate(struct dentry *dentry, struct dentry *parent)
 {
-	struct hlist_head *base;
-	struct hlist_node *lhp;
+	struct dentry_hash *hashtable, *old_hashtable;
+	int ret = 0;
 
 	/* Check whether the ptr might be valid at all.. */
 	if (!kmem_ptr_validate(dentry_cache, dentry))
 		goto out;
 
-	if (dentry->d_parent != dparent)
+	if (dentry->d_parent != parent)
 		goto out;
 
-	spin_lock(&dcache_lock);
-	base = d_hash(dparent, dentry->d_name.hash);
-	hlist_for_each(lhp,base) { 
-		/* hlist_for_each_entry_rcu() not required for d_hash list
-		 * as it is parsed under dcache_lock
-		 */
-		if (dentry == hlist_entry(lhp, struct dentry, d_hash)) {
-			__dget_locked(dentry);
-			spin_unlock(&dcache_lock);
-			return 1;
-		}
+	rcu_read_lock();
+	hashtable = dentry_hash;
+	smp_rmb(); /* see smp_wmb in dcache_hash_resize_work */
+	old_hashtable = old_dentry_hash;
+
+	if (unlikely(old_hashtable)) {
+		unsigned long seq;
+		do {
+			seq = read_seqbegin(&resize_transfer_lock);
+			ret = d_validate_hash(old_hashtable, dentry, parent);
+			if (ret)
+				goto out_rcu;
+			ret = d_validate_hash(hashtable, dentry, parent);
+			if (ret)
+				goto out_rcu;
+		} while (read_seqretry(&resize_transfer_lock, seq));
+	} else {
+		ret = d_validate_hash(hashtable, dentry, parent);
 	}
-	spin_unlock(&dcache_lock);
+
+out_rcu:
+ 	rcu_read_unlock();
 out:
-	return 0;
+	return ret;
 }
 
 /*
@@ -1402,7 +1491,9 @@ static void __d_rehash(struct dentry * e
 
 static void _d_rehash(struct dentry * entry)
 {
-	__d_rehash(entry, d_hash(entry->d_parent, entry->d_name.hash));
+	rcu_read_lock();
+	__d_rehash(entry, d_hash(dentry_hash, entry->d_parent, entry->d_name.hash));
+	rcu_read_unlock();
 }
 
 /**
@@ -1518,8 +1609,10 @@ static void d_move_locked(struct dentry 
 	hlist_del_rcu(&dentry->d_hash);
 
 already_unhashed:
-	list = d_hash(target->d_parent, target->d_name.hash);
+	rcu_read_lock();
+	list = d_hash(dentry_hash, target->d_parent, target->d_name.hash);
 	__d_rehash(dentry, list);
+	rcu_read_unlock();
 
 	/* Unhash the target: dput() will then get rid of it */
 	__d_drop(target);
@@ -2009,42 +2102,114 @@ ino_t find_inode_number(struct dentry *d
 	return ino;
 }
 
-static __initdata unsigned long dhash_entries;
-static int __init set_dhash_entries(char *str)
+static unsigned int resize_new_shift;
+
+static void dcache_hash_resize_work(struct work_struct *work)
 {
-	if (!str)
-		return 0;
-	dhash_entries = simple_strtoul(str, &str, 0);
-	return 1;
+	unsigned long new_size, old_size;
+	int i;
+	struct dentry_hash *new_hash, *old_hash;
+	unsigned long transferred;
+
+	if (!mutex_trylock(&resize_mutex))
+		goto out;
+
+	new_hash = kmalloc(sizeof(struct dentry_hash), GFP_KERNEL);
+	if (!new_hash)
+		goto out_unlock;
+
+	new_hash->shift = resize_new_shift;
+	new_size = 1 << new_hash->shift;
+	new_hash->mask = new_size - 1;
+	new_hash->table = vmalloc(new_size*sizeof(struct hlist_head));
+	if (!new_hash->table)
+		goto out_kfree;
+	for (i = 0; i < new_size; i++)
+		INIT_HLIST_HEAD(&new_hash->table[i]);
+
+	old_dentry_hash = dentry_hash;
+	/*
+	 * ensure that if the reader sees the new dentry_hash,
+	 * then they will also see the old_dentry_hash assignment,
+	 * above.
+	 */
+	smp_wmb();
+	dentry_hash = new_hash;
+	synchronize_rcu();
+
+	old_size = 1 << old_dentry_hash->shift;
+	transferred = 0;
+	for (i = 0; i < old_size; i++) {
+		struct hlist_head *head = &old_dentry_hash->table[i];
+
+		if (hlist_empty(head))
+			continue;
+
+		spin_lock(&dcache_lock);
+		write_seqlock(&resize_transfer_lock);
+		while (!hlist_empty(head)) {
+			struct dentry *dentry;
+			struct hlist_head *new_head;
+
+			dentry = hlist_entry(head->first, struct dentry, d_hash);
+			new_head = d_hash(dentry_hash, dentry->d_parent, dentry->d_name.hash);
+
+			spin_lock(&dentry->d_lock);
+			hlist_del_rcu(head->first);
+ 			hlist_add_head_rcu(&dentry->d_hash, new_head);
+			spin_unlock(&dentry->d_lock);
+			transferred++;
+		}
+		write_sequnlock(&resize_transfer_lock);
+		spin_unlock(&dcache_lock);
+	}
+
+	printk("resize dcache hash from %lu to %lu, moved %lu entries\n", old_size, new_size, transferred);
+
+	old_hash = old_dentry_hash;
+	old_dentry_hash = NULL;
+	mutex_unlock(&resize_mutex);
+	synchronize_rcu();
+	vfree(old_hash->table);
+	kfree(old_hash);
+
+	resize_new_shift = 0;
+	return;
+
+out_kfree:
+	kfree(new_hash);
+out_unlock:
+	mutex_unlock(&resize_mutex);
+out:
+	resize_new_shift = 0;
+	return;
 }
-__setup("dhash_entries=", set_dhash_entries);
 
-static void __init dcache_init_early(void)
+static DEFINE_SPINLOCK(resize_lock);
+
+static void dcache_hash_resize(unsigned int new_shift)
 {
-	int loop;
+	static DECLARE_WORK(resize_work, dcache_hash_resize_work);
 
-	/* If hashes are distributed across NUMA nodes, defer
-	 * hash allocation until vmalloc space is available.
-	 */
-	if (hashdist)
+	if (new_shift < MIN_DHASH_SHIFT || new_shift > MAX_DHASH_SHIFT)
 		return;
 
-	dentry_hashtable =
-		alloc_large_system_hash("Dentry cache",
-					sizeof(struct hlist_head),
-					dhash_entries,
-					13,
-					HASH_EARLY,
-					&d_hash_shift,
-					&d_hash_mask,
-					0);
+	if (resize_new_shift)
+		return;
+	spin_lock(&resize_lock);
+	if (resize_new_shift) {
+		spin_unlock(&resize_lock);
+		return;
+	}
+	resize_new_shift = new_shift;
+	spin_unlock(&resize_lock);
 
-	for (loop = 0; loop < (1 << d_hash_shift); loop++)
-		INIT_HLIST_HEAD(&dentry_hashtable[loop]);
+	schedule_work(&resize_work);
 }
 
 static void __init dcache_init(unsigned long mempages)
 {
+	unsigned long hash_size;
 	int loop;
 
 	/* 
@@ -2061,22 +2226,20 @@ static void __init dcache_init(unsigned 
 
 	set_shrinker(DEFAULT_SEEKS, shrink_dcache_memory);
 
-	/* Hash may have been set up in dcache_init_early */
-	if (!hashdist)
-		return;
-
-	dentry_hashtable =
-		alloc_large_system_hash("Dentry cache",
-					sizeof(struct hlist_head),
-					dhash_entries,
-					13,
-					0,
-					&d_hash_shift,
-					&d_hash_mask,
-					0);
+	old_dentry_hash = NULL;
 
-	for (loop = 0; loop < (1 << d_hash_shift); loop++)
-		INIT_HLIST_HEAD(&dentry_hashtable[loop]);
+	dentry_hash = kmalloc(sizeof(struct dentry_hash), GFP_ATOMIC);
+	if (!dentry_hash)
+		panic("Failed to allocate dentry_hash\n");
+	dentry_hash->shift = MIN_DHASH_SHIFT;
+	hash_size = 1 << dentry_hash->shift;
+	dentry_hash->mask = hash_size - 1;
+	dentry_hash->table = __vmalloc(hash_size*sizeof(struct hlist_head),
+					GFP_ATOMIC, PAGE_KERNEL);
+	if (!dentry_hash->table)
+		panic("Failed to allocate dentry_hash->table\n");
+	for (loop = 0; loop < hash_size; loop++)
+		INIT_HLIST_HEAD(&dentry_hash->table[loop]);
 }
 
 /* SLAB cache for __getname() consumers */
@@ -2089,7 +2252,6 @@ EXPORT_SYMBOL(d_genocide);
 
 void __init vfs_caches_init_early(void)
 {
-	dcache_init_early();
 	inode_init_early();
 }
 
-

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

#16 lore raw
In reply to Nick Piggin

From: Nick Piggin <[email protected]>
Date: Fri, 23 Feb 2007 16:37:43 +0100

Quoted 2 lines

So I introduce a new method for resizing hash tables with RCU, and apply that to the dentry hash.

Thanks for doing this work Nick. I'm going to take your ideas and apply them to an ipv4 routing cache dynamic growth patch I worked on a while ago.

One minor nit:

fs/dcache.c static struct kmem_cache *dentry_cache _ · line 66

Quoted 5 lines
fs/dcache.c +5 -0
+struct dentry_hash {
+	unsigned int shift;
+	unsigned long mask;
+	struct hlist_head *table;
+};

I don't see any reason to make 'mask' an unsigned long and this makes this structure take up 8 bytes more than necessary on 64-bit.

#17 lore raw
Quoted 9 lines · David Miller

From: Nick Piggin <[email protected]>
Date: Fri, 23 Feb 2007 16:37:43 +0100

Quoted 2 lines

So I introduce a new method for resizing hash tables with RCU, and apply that to the dentry hash.

Thanks for doing this work Nick. I'm going to take your ideas and apply them to an ipv4 routing cache dynamic growth patch I worked on a while ago.

Sounds great, I would be happy to help review it. If we can create a bit of common infrastructure, the dcache conversion might become a bit more palatable and we could look at other things like the inode hash as well.

Quoted 11 lines

One minor nit:

fs/dcache.c static struct kmem_cache *dentry_cache _ · line 66

Quoted 5 lines
fs/dcache.c +5 -0
+struct dentry_hash {
+	unsigned int shift;
+	unsigned long mask;
+	struct hlist_head *table;
+};

I don't see any reason to make 'mask' an unsigned long and this makes this structure take up 8 bytes more than necessary on 64-bit.

You're right, the mask is currently just an int, so my patch should not be messing with that. Thanks.

The other thing you'll have to be careful of when looking at doing an implementation, is that I think I forgot to use the RCU accessors (rcu_assign_pointer, rcu_dereference) when assigning and loading the new/old hash table pointers.

#18 lore raw

From: Nick Piggin <[email protected]>
Date: Mon, 5 Mar 2007 05:27:24 +0100

Quoted 4 lines

Sounds great, I would be happy to help review it. If we can create a bit of common infrastructure, the dcache conversion might become a bit more palatable and we could look at other things like the inode hash as well.

Absolutely, I'll run my patch by you once I have it ready.

Quoted 4 lines

The other thing you'll have to be careful of when looking at doing an implementation, is that I think I forgot to use the RCU accessors (rcu_assign_pointer, rcu_dereference) when assigning and loading the new/old hash table pointers.

Thanks for the heads-up.

#19 lore raw
In reply to Nick Piggin
Quoted 13 lines · Nick Piggin
Quoted 11 lines · David Miller

One minor nit:

fs/dcache.c static struct kmem_cache *dentry_cache _ · line 66

Quoted 5 lines
fs/dcache.c +5 -0
+struct dentry_hash {
+	unsigned int shift;
+	unsigned long mask;
+	struct hlist_head *table;
+};

I don't see any reason to make 'mask' an unsigned long and this makes this structure take up 8 bytes more than necessary on 64-bit.

Quoted 7 lines

You're right, the mask is currently just an int, so my patch should not be messing with that. Thanks.

The other thing you'll have to be careful of when looking at doing an implementation, is that I think I forgot to use the RCU accessors (rcu_assign_pointer, rcu_dereference) when assigning and loading the new/old hash table pointers.

Also, now that I think of it, if resize performance is far far less important than read-side performance, then you should be able to get away without the additional smp_rmb() that I add to the read-side in the algorithm I described.

All you have to do is introduce an additional RCU grace period between assigning the old pointer to the current table, and the current pointer to the new table. This will still ensure that an (old_table == NULL && cur_table == new_table) condition is impossible (that condition would mean that one of our active tables is invisible to the reader).

This should truely reduce read-side fastpath overhead to just a single, predictable branch, an extra read_mostly load or two and the rcu_blah() bits.