dynamic dentry and inode hash tables

Chuck Lever (cel@monkey.org)
Thu, 1 Jul 1999 15:32:05 -0400 (EDT)


kernel 2.3.9 already has a dynamically allocated page and buffer cache.
i've implemented dynamically allocated hash tables for the dentry and
inode caches with this patch, against 2.3.9, in the same style as the page
and buffer caches.

diff -ruN linux-2.3.9-ref/fs/dcache.c linux/fs/dcache.c
--- linux-2.3.9-ref/fs/dcache.c Thu Jul 1 10:56:14 1999
+++ linux/fs/dcache.c Thu Jul 1 15:06:19 1999
@@ -41,11 +41,9 @@
* 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 10
-#define D_HASHSIZE (1UL << D_HASHBITS)
-#define D_HASHMASK (D_HASHSIZE-1)
+unsigned long dentry_hashshift, dentry_hashmask;
+static struct list_head *dentry_hashtable;

-static struct list_head dentry_hashtable[D_HASHSIZE];
static LIST_HEAD(dentry_unused);

struct {
@@ -333,6 +331,7 @@
continue;
list_del(tmp);
list_add(tmp, &dentry_unused);
+ dentry_stat.nr_unused++;
}

/*
@@ -564,8 +563,9 @@
static inline struct list_head * d_hash(struct dentry * parent, unsigned long hash)
{
hash += (unsigned long) parent;
- hash = hash ^ (hash >> D_HASHBITS) ^ (hash >> D_HASHBITS*2);
- return dentry_hashtable + (hash & D_HASHMASK);
+ hash = hash + (hash >> dentry_hashshift) +
+ (hash >> (dentry_hashshift << 1));
+ return dentry_hashtable + (hash & dentry_hashmask);
}

struct dentry * d_lookup(struct dentry * parent, struct qstr * name)
@@ -900,10 +900,44 @@
return ino;
}

-void __init dcache_init(void)
+#define BUCKET_SIZE sizeof(struct list_head)
+
+void __init dcache_init(unsigned long memory_size)
{
int i;
- struct list_head *d = dentry_hashtable;
+ unsigned long table_size, order;
+ struct list_head *d;
+
+ table_size = memory_size >> 14;
+ table_size *= BUCKET_SIZE;
+ for(order = 0; (PAGE_SIZE << order) < table_size; order++)
+ ;
+
+ do {
+ dentry_hashtable = (struct list_head *)
+ __get_free_pages(GFP_ATOMIC, order);
+ } while(dentry_hashtable == NULL && --order > 0);
+
+ table_size = (PAGE_SIZE << order) / BUCKET_SIZE;
+ dentry_hashmask = table_size - 1;
+
+ dentry_hashshift = 0;
+ while((table_size >>= 1UL) != 0UL)
+ dentry_hashshift++;
+
+ printk("Dentry-cache hash table entries: %d (order: %ld, %ld bytes)\n",
+ (1 << dentry_hashshift), order, (PAGE_SIZE << order));
+ /* panic *after* we print diagnostic message */
+ if (!dentry_hashtable)
+ panic("Failed to allocate dentry hash table\n");
+
+ i = 1 << dentry_hashshift; /* hash table bucket count */
+ d = dentry_hashtable;
+ do {
+ INIT_LIST_HEAD(d);
+ d++;
+ i--;
+ } while (i);

/*
* A constructor could be added for stable state like the lists,
@@ -920,11 +954,4 @@
NULL, NULL);
if (!dentry_cache)
panic("Cannot create dentry cache");
-
- i = D_HASHSIZE;
- do {
- INIT_LIST_HEAD(d);
- d++;
- i--;
- } while (i);
}
diff -ruN linux-2.3.9-ref/fs/inode.c linux/fs/inode.c
--- linux-2.3.9-ref/fs/inode.c Thu Jul 1 10:56:44 1999
+++ linux/fs/inode.c Thu Jul 1 15:06:35 1999
@@ -28,9 +28,8 @@
* Inode lookup is no longer as critical as it used to be:
* most of the lookups are going to be through the dcache.
*/
-#define HASH_BITS 8
-#define HASH_SIZE (1UL << HASH_BITS)
-#define HASH_MASK (HASH_SIZE-1)
+unsigned long inode_hashshift, inode_hashmask;
+static struct list_head * inode_hashtable;

/*
* Each inode can be on two separate lists. One is
@@ -46,7 +45,6 @@

static LIST_HEAD(inode_in_use);
static LIST_HEAD(inode_unused);
-static struct list_head inode_hashtable[HASH_SIZE];

/*
* A simple spinlock to protect the list manipulations.
@@ -639,8 +637,9 @@
static inline unsigned long hash(struct super_block *sb, unsigned long i_ino)
{
unsigned long tmp = i_ino | (unsigned long) sb;
- tmp = tmp + (tmp >> HASH_BITS) + (tmp >> HASH_BITS*2);
- return tmp & HASH_MASK;
+ tmp = tmp + (tmp >> inode_hashshift) +
+ (tmp >> (inode_hashshift << 1));
+ return tmp & inode_hashmask;
}

/* Yeah, I know about quadratic hash. Maybe, later. */
@@ -798,13 +797,39 @@
* value for max inodes
*/
#define MAX_INODE (16384)
+#define BUCKET_SIZE sizeof(struct list_head)

-void __init inode_init(void)
+void __init inode_init(unsigned long memory_size)
{
int i, max;
- struct list_head *head = inode_hashtable;
+ unsigned long table_size, order;
+ struct list_head *head;

- i = HASH_SIZE;
+ table_size = memory_size >> 17;
+ table_size *= BUCKET_SIZE;
+ for(order = 0; (PAGE_SIZE << order) < table_size; order++)
+ ;
+
+ do {
+ inode_hashtable = (struct list_head *)
+ __get_free_pages(GFP_ATOMIC, order);
+ } while(inode_hashtable == NULL && --order > 0);
+
+ table_size = (PAGE_SIZE << order) / BUCKET_SIZE;
+ inode_hashmask = table_size - 1;
+
+ inode_hashshift = 0;
+ while((table_size >>= 1UL) != 0UL)
+ inode_hashshift++;
+
+ printk("Inode-cache hash table entries: %d (order: %ld, %ld bytes)\n",
+ (1 << inode_hashshift), order, (PAGE_SIZE << order));
+ /* panic *after* we print diagnostic message */
+ if (!inode_hashtable)
+ panic("Failed to allocate inode hash table\n");
+
+ i = 1 << inode_hashshift; /* hash table bucket count */
+ head = inode_hashtable;
do {
INIT_LIST_HEAD(head);
head++;
diff -ruN linux-2.3.9-ref/include/linux/fs.h linux/include/linux/fs.h
--- linux-2.3.9-ref/include/linux/fs.h Thu Jul 1 10:56:46 1999
+++ linux/include/linux/fs.h Thu Jul 1 14:54:06 1999
@@ -177,9 +177,9 @@
#define UPDATE_ATIME(inode) update_atime (inode)

extern void buffer_init(unsigned long);
-extern void inode_init(void);
+extern void inode_init(unsigned long);
extern void file_table_init(void);
-extern void dcache_init(void);
+extern void dcache_init(unsigned long);

typedef char buffer_block[BLOCK_SIZE];

diff -ruN linux-2.3.9-ref/init/main.c linux/init/main.c
--- linux-2.3.9-ref/init/main.c Thu Jul 1 10:56:46 1999
+++ linux/init/main.c Thu Jul 1 12:24:13 1999
@@ -1183,12 +1183,12 @@
#endif
uidcache_init();
filescache_init();
- dcache_init();
+ dcache_init(memory_end-memory_start);
vma_init();
buffer_init(memory_end-memory_start);
page_cache_init(memory_end-memory_start);
signals_init();
- inode_init();
+ inode_init(memory_end-memory_start);
file_table_init();
#if defined(CONFIG_SYSVIPC)
ipc_init();

- Chuck Lever

--
corporate:	<chuckl@netscape.com>
personal:	<chucklever@netscape.net> or <cel@monkey.org>

The Linux Scalability project: http://www.citi.umich.edu/projects/linux-scalability/

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