Messages in this thread Patch in this message | | | Date | Tue, 6 Jul 1999 16:42:02 -0400 (EDT) | From | Chuck Lever <> | Subject | dynamic hash tables against 2.3.9 |
| |
hi linus-
i submitted this patch last week, but it doesn't appear to be included in 2.3.10-pre4. was there a problem with it? please let me know... thanks!
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/
| |