Skip to contentSkip to conversation

Permit inode & dentry hash tables to be allocated > MAX_ORDER size

PATCH In review David Howells 5 participants 15 messages Jun 11, 2004 – Jun 14, 2004

Subsystems (5)
Memory management VFS MM core Page allocator +1 more subsystems
lore
Share & tools
lore

David Howells

author
#0 lore raw

PATCH 1/1 Permit inode & dentry hash tables to be allocated > MAX_ORDER size

Hi Linus, Andrew,

Here's a patch to allocate memory for big system hash tables with the bootmem allocator rather than with main page allocator.

I've coelesced the meat of the inode and dentry allocation routines into one such routine in mm/page_alloc.c that the the respective initialisation functions now call before mem_init() is called.

This routine gets it's approximation of memory size by counting up the ZONE_NORMAL and ZONE_DMA pages (and ZONE_HIGHMEM if requested) in all the nodes passed to the main allocator by paging_init() (or wherever the arch does it). It does not use max_low_pfn as that doesn't seem to be available on all archs, and it doesn't use num_physpages since that includes highmem pages not available to the kernel for allocating data structures upon - which may not be appropriate when calculating hash table size.

On the off chance that the size of each hash bucket may not be exactly a power of two, the routine will only allocate as many pages as is necessary to ensure that the number of buckets is exactly a power of two, rather than allocating the smallest power-of-two sized chunk of memory that will hold the same array of buckets.

The maximum size of any single hash table is given by MAX_SYS_HASH_TABLE_ORDER, as is now defined in linux/mmzone.h.

David

fs/dcache.c +30 -44
diff -uNrp linux-2.6.7-rc3/fs/dcache.c linux-2.6.7-rc3-hash/fs/dcache.c
@@ -30,6 +30,7 @@
 #include <linux/security.h>
 #include <linux/seqlock.h>
 #include <linux/swap.h>
+#include <linux/bootmem.h>
 
 #define DCACHE_PARANOIA 1
 /* #define DCACHE_DEBUG 1 */

@@ -1561,13 +1562,31 @@ static int __init set_dhash_entries(char
 }
 __setup("dhash_entries=", set_dhash_entries);
 
-static void __init dcache_init(unsigned long mempages)
+static void __init dcache_init_early(void)
 {
-	struct hlist_head *d;
-	unsigned long order;
-	unsigned int nr_hash;
-	int i;
+	struct hlist_head *p;
+	int loop;
+
+	dentry_hashtable =
+		alloc_large_system_hash("Dentry cache",
+					sizeof(struct hlist_head),
+					dhash_entries,
+					13,
+					0,
+					&d_hash_shift,
+					&d_hash_mask);
+
+	p = dentry_hashtable;
+	loop = 1 << d_hash_shift;
+	do {
+		INIT_HLIST_HEAD(p);
+		p++;
+		loop--;
+	} while (loop);
+}
 
+static void __init dcache_init(unsigned long mempages)
+{
 	/* 
 	 * A constructor could be added for stable state like the lists,
 	 * but it is probably not worth it because of the cache nature

@@ -1580,45 +1599,6 @@ static void __init dcache_init(unsigned 
 					 NULL, NULL);
 	
 	set_shrinker(DEFAULT_SEEKS, shrink_dcache_memory);
-
-	if (!dhash_entries)
-		dhash_entries = PAGE_SHIFT < 13 ?
-				mempages >> (13 - PAGE_SHIFT) :
-				mempages << (PAGE_SHIFT - 13);
-
-	dhash_entries *= sizeof(struct hlist_head);
-	for (order = 0; ((1UL << order) << PAGE_SHIFT) < dhash_entries; order++)
-		;
-
-	do {
-		unsigned long tmp;
-
-		nr_hash = (1UL << order) * PAGE_SIZE /
-			sizeof(struct hlist_head);
-		d_hash_mask = (nr_hash - 1);
-
-		tmp = nr_hash;
-		d_hash_shift = 0;
-		while ((tmp >>= 1UL) != 0UL)
-			d_hash_shift++;
-
-		dentry_hashtable = (struct hlist_head *)
-			__get_free_pages(GFP_ATOMIC, order);
-	} while (dentry_hashtable == NULL && --order >= 0);
-
-	printk(KERN_INFO "Dentry cache hash table entries: %d (order: %ld, %ld bytes)\n",
-			nr_hash, order, (PAGE_SIZE << order));
-
-	if (!dentry_hashtable)
-		panic("Failed to allocate dcache hash table\n");
-
-	d = dentry_hashtable;
-	i = nr_hash;
-	do {
-		INIT_HLIST_HEAD(d);
-		d++;
-		i--;
-	} while (i);
 }
 
 /* SLAB cache for __getname() consumers */

@@ -1632,6 +1612,12 @@ EXPORT_SYMBOL(d_genocide);
 extern void bdev_cache_init(void);
 extern void chrdev_init(void);
 
+void __init vfs_caches_init_early(void)
+{
+	dcache_init_early();
+	inode_init_early();
+}
+
 void __init vfs_caches_init(unsigned long mempages)
 {
 	unsigned long reserve;
fs/inode.c +24 -42

84 lines not on this page · raw message

include/linux/bootmem.h +8 -0
diff -uNrp linux-2.6.7-rc3/include/linux/bootmem.h linux-2.6.7-rc3-hash/include/linux/bootmem.h
@@ -67,4 +67,12 @@ extern void * __init __alloc_bootmem_nod
 	__alloc_bootmem_node((pgdat), (x), PAGE_SIZE, 0)
 #endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */
 
+extern void *__init alloc_large_system_hash(const char *tablename,
+					    unsigned long bucketsize,
+					    unsigned long numentries,
+					    int scale,
+					    int consider_highmem,
+					    unsigned int *_hash_shift,
+					    unsigned int *_hash_mask);
+
 #endif /* _LINUX_BOOTMEM_H */
include/linux/fs.h +2 -0
diff -uNrp linux-2.6.7-rc3/include/linux/fs.h linux-2.6.7-rc3-hash/include/linux/fs.h
@@ -221,6 +221,7 @@ extern int leases_enable, dir_notify_ena
 extern void update_atime (struct inode *);
 
 extern void inode_init(unsigned long);
+extern void inode_init_early(void);
 extern void mnt_init(unsigned long);
 extern void files_init(unsigned long);
 

@@ -1199,6 +1200,7 @@ extern int filp_close(struct file *, fl_
 extern char * getname(const char __user *);
 
 /* fs/dcache.c */
+extern void vfs_caches_init_early(void);
 extern void vfs_caches_init(unsigned long);
 
 #define __getname()	kmem_cache_alloc(names_cachep, SLAB_KERNEL)
include/linux/mmzone.h +12 -0
diff -uNrp linux-2.6.7-rc3/include/linux/mmzone.h linux-2.6.7-rc3-hash/include/linux/mmzone.h
@@ -20,6 +20,18 @@
 #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
 #endif
 
+/*
+ * system hash table size limits
+ * - on large memory machines, we may want to allocate a bigger hash than that
+ *   permitted by MAX_ORDER, so we allocate with the bootmem allocator, and are
+ *   limited to this size
+ */
+#if MAX_ORDER > 14
+#define MAX_SYS_HASH_TABLE_ORDER MAX_ORDER
+#else
+#define MAX_SYS_HASH_TABLE_ORDER 14
+#endif
+
 struct free_area {
 	struct list_head	free_list;
 	unsigned long		*map;
init/main.c +1 -0
diff -uNrp linux-2.6.7-rc3/init/main.c linux-2.6.7-rc3-hash/init/main.c
@@ -454,6 +454,7 @@ asmlinkage void __init start_kernel(void
 		initrd_start = 0;
 	}
 #endif
+	vfs_caches_init_early();
 	mem_init();
 	kmem_cache_init();
 	if (late_time_init)
mm/page_alloc.c +82 -0

97 lines not on this page · raw message

#1 lore raw
Quoted 3 lines · David Howells

Here's a patch to allocate memory for big system hash tables with the bootmem allocator rather than with main page allocator.

umm, why?

author
#2 lore raw
Quoted 5 lines
Quoted 3 lines

Here's a patch to allocate memory for big system hash tables with the bootmem allocator rather than with main page allocator.

umm, why?

Three reasons:

(1) So that the size can be bigger than MAX_ORDER. IBM have done some testing on their big PPC64 systems (64GB of RAM) with linux-2.4 and found that they get better performance if the sizes of the inode cache hash, dentry cache hash, buffer head hash and page cache hash are increased beyond MAX_ORDER (order 11).

Now the main allocator can't allocate anything larger than MAX_ORDER, but the bootmem allocator can.

In 2.6 it appears that only the inode and dentry hashes remain of those four, but there are other hash tables that could use this service.

(2) Changing MAX_ORDER appears to have a number of effects beyond just limiting the maximum size that can be allocated in one go.

(3) Should someone want a hash table in which each bucket isn't a power of two in size, memory will be wasted as the chunk of memory allocated will be a power of two in size (to hold a power of two number of buckets).

On the other hand, using the bootmem allocator means the allocation will only take up sufficient pages to hold it, rather than the next power of two up.

Admittedly, this point doesn't apply to the dentry and inode hashes, but it might to another hash table that might want to use this service.

David

#3 lore raw
Quoted 3 lines · David Howells

(2) Changing MAX_ORDER appears to have a number of effects beyond just limiting the maximum size that can be allocated in one go.

Several architectures implement CONFIG_FORCE_MAX_ZONEORDER and I haven't heard of larger MAX_ORDERs causing problems.

Certainly, increasing MAX_ORDER is the simplest solution to the problems which you identify so we need to substantiate these "number of effects" much more than this please.

#4 lore raw
Quoted 9 lines
Quoted 2 lines

(2) Changing MAX_ORDER appears to have a number of effects beyond just limiting the maximum size that can be allocated in one go.

Several architectures implement CONFIG_FORCE_MAX_ZONEORDER and I haven't heard of larger MAX_ORDERs causing problems.

Certainly, increasing MAX_ORDER is the simplest solution to the problems which you identify so we need to substantiate these "number of effects" much more than this please.

We've hit a problem with alignment issues where the start of the zone is aligned to 16MB, for instance, and the max grouping is now 256MB. That generatates a "warning: wrong zone alignment: it will crash" error (or something similar). Andy sent me a patch this morning to throw away the lower section, which is much nicer than crashing ... but I'd prefer not to throw that RAM away unless we have to.

Allocating the big-assed hashes out of bootmem seems much cleaner to me, at least ...

M.

#5 lore raw
Quoted 7 lines · Martin J. Bligh

We've hit a problem with alignment issues where the start of the zone is aligned to 16MB, for instance, and the max grouping is now 256MB. That generatates a "warning: wrong zone alignment: it will crash" error (or something similar). Andy sent me a patch this morning to throw away the lower section, which is much nicer than crashing ... but I'd prefer not to throw that RAM away unless we have to.

Confused. Why do we have that test in there at all? We should just toss the pages one at a time into the buddy list and let the normal coalescing work it out. That way we'd end up with a single 16MB "page" followed by N 256MB "pages".

Quoted 2 lines

Allocating the big-assed hashes out of bootmem seems much cleaner to me, at least ...

Maybe. That code seems fragile and I have premonitions of unhappy arch maintainers.

#6 lore raw
Quoted 9 lines · --On Friday, June 11, 2004 16:19:20 -0700 Andrew Morton <[email protected]> wrote:
Quoted 7 lines · Martin J. Bligh

We've hit a problem with alignment issues where the start of the zone is aligned to 16MB, for instance, and the max grouping is now 256MB. That generatates a "warning: wrong zone alignment: it will crash" error (or something similar). Andy sent me a patch this morning to throw away the lower section, which is much nicer than crashing ... but I'd prefer not to throw that RAM away unless we have to.

Quoted 4 lines

Confused. Why do we have that test in there at all? We should just toss the pages one at a time into the buddy list and let the normal coalescing work it out. That way we'd end up with a single 16MB "page" followed by N 256MB "pages".

That's what I thought ... Andy looked at it more than I did, but I think he's asleep, unfortunately. IIRC, he said the buddy stuff keys off zone_start_pfn though. Maybe that's fixable ...

M.

#7 lore raw
Quoted 12 lines · Martin J. Bligh
Quoted 9 lines · --On Friday, June 11, 2004 16:19:20 -0700 Andrew Morton <[email protected]> wrote:
Quoted 7 lines · Martin J. Bligh

We've hit a problem with alignment issues where the start of the zone is aligned to 16MB, for instance, and the max grouping is now 256MB. That generatates a "warning: wrong zone alignment: it will crash" error (or something similar). Andy sent me a patch this morning to throw away the lower section, which is much nicer than crashing ... but I'd prefer not to throw that RAM away unless we have to.

Quoted 8 lines
Quoted 4 lines

Confused. Why do we have that test in there at all? We should just toss the pages one at a time into the buddy list and let the normal coalescing work it out. That way we'd end up with a single 16MB "page" followed by N 256MB "pages".

That's what I thought ... Andy looked at it more than I did, but I think he's asleep, unfortunately. IIRC, he said the buddy stuff keys off zone_start_pfn though. Maybe that's fixable ...

Doesn't look that way. It uses

	(zone->zone_mem_map - page) >> (1 + order)
#8 lore raw
Quoted 3 lines · --On 11 June 2004 16:30 -0700 Andrew Morton <[email protected]> wrote:

Doesn't look that way. It uses

	(zone->zone_mem_map - page) >> (1 + order)

Hmmm, yes. Does this not mean that we will violate the object size N will be aligned at size N. Presumably that's why the error says 'it'll crash'. If we are two pages offset we will allocate 4 page objects 2 page aligned. I'll have a closer look and see if we can just 'round down' the zone_mem_map pointer here to give the correct alignment. As long as we don't try and free them into the allocator originally we should be ok, as they are marked allocated in the bitmaps at the start.

-apw

#9 lore raw
In reply to Andrew Morton
Quoted 5 lines · Andrew Morton

Confused. Why do we have that test in there at all? We should just toss the pages one at a time into the buddy list and let the normal coalescing work it out. That way we'd end up with a single 16MB "page" followed by N 256MB "pages".

Doesn't work that way. We use the base of the memory area as the "zero point", and while the buddy allocator itself shouldn't really care where that zero-point is, anybody who expects physical alignment would be really upset if it doesn't get it.

So the base address has to be as aligned as anybody could ever want. And "anybody" wants quite a bit of alignment. Largepages usually want alignment guarantees, and on most architectures that means a minimum _physical_ address alignment of at least a few megabytes.

So the rule really should be: make sure that the buddy system base address is maximally aligned, and if your memory doesn't actually _start_ at that alignment point, just add the pages and let the buddy allocator build up all the bitmaps etc for you.

Linus

author
#10 lore raw

PATCH 1/1 Permit inode & dentry hash tables to be allocated > MAX_ORDER size [#2]

In reply to David Howells

Hi Linus, Andrew,

Here's an update to my patch. Thanks to Ingo Oeser for noticing that the patch had a couple of problems in the allocation loop (it would never end if an allocation failed, and the result of the allocation didn't need casting).

David

fs/dcache.c +30 -44
diff -uNrp linux-2.6.7-rc3/fs/dcache.c linux-2.6.7-rc3-hash/fs/dcache.c
@@ -30,6 +30,7 @@
 #include <linux/security.h>
 #include <linux/seqlock.h>
 #include <linux/swap.h>
+#include <linux/bootmem.h>
 
 #define DCACHE_PARANOIA 1
 /* #define DCACHE_DEBUG 1 */

@@ -1561,13 +1562,31 @@ static int __init set_dhash_entries(char
 }
 __setup("dhash_entries=", set_dhash_entries);
 
-static void __init dcache_init(unsigned long mempages)
+static void __init dcache_init_early(void)
 {
-	struct hlist_head *d;
-	unsigned long order;
-	unsigned int nr_hash;
-	int i;
+	struct hlist_head *p;
+	int loop;
+
+	dentry_hashtable =
+		alloc_large_system_hash("Dentry cache",
+					sizeof(struct hlist_head),
+					dhash_entries,
+					13,
+					0,
+					&d_hash_shift,
+					&d_hash_mask);
+
+	p = dentry_hashtable;
+	loop = 1 << d_hash_shift;
+	do {
+		INIT_HLIST_HEAD(p);
+		p++;
+		loop--;
+	} while (loop);
+}
 
+static void __init dcache_init(unsigned long mempages)
+{
 	/* 
 	 * A constructor could be added for stable state like the lists,
 	 * but it is probably not worth it because of the cache nature

@@ -1580,45 +1599,6 @@ static void __init dcache_init(unsigned 
 					 NULL, NULL);
 	
 	set_shrinker(DEFAULT_SEEKS, shrink_dcache_memory);
-
-	if (!dhash_entries)
-		dhash_entries = PAGE_SHIFT < 13 ?
-				mempages >> (13 - PAGE_SHIFT) :
-				mempages << (PAGE_SHIFT - 13);
-
-	dhash_entries *= sizeof(struct hlist_head);
-	for (order = 0; ((1UL << order) << PAGE_SHIFT) < dhash_entries; order++)
-		;
-
-	do {
-		unsigned long tmp;
-
-		nr_hash = (1UL << order) * PAGE_SIZE /
-			sizeof(struct hlist_head);
-		d_hash_mask = (nr_hash - 1);
-
-		tmp = nr_hash;
-		d_hash_shift = 0;
-		while ((tmp >>= 1UL) != 0UL)
-			d_hash_shift++;
-
-		dentry_hashtable = (struct hlist_head *)
-			__get_free_pages(GFP_ATOMIC, order);
-	} while (dentry_hashtable == NULL && --order >= 0);
-
-	printk(KERN_INFO "Dentry cache hash table entries: %d (order: %ld, %ld bytes)\n",
-			nr_hash, order, (PAGE_SIZE << order));
-
-	if (!dentry_hashtable)
-		panic("Failed to allocate dcache hash table\n");
-
-	d = dentry_hashtable;
-	i = nr_hash;
-	do {
-		INIT_HLIST_HEAD(d);
-		d++;
-		i--;
-	} while (i);
 }
 
 /* SLAB cache for __getname() consumers */

@@ -1632,6 +1612,12 @@ EXPORT_SYMBOL(d_genocide);
 extern void bdev_cache_init(void);
 extern void chrdev_init(void);
 
+void __init vfs_caches_init_early(void)
+{
+	dcache_init_early();
+	inode_init_early();
+}
+
 void __init vfs_caches_init(unsigned long mempages)
 {
 	unsigned long reserve;
fs/inode.c +24 -42

84 lines not on this page · raw message

include/linux/bootmem.h +8 -0
diff -uNrp linux-2.6.7-rc3/include/linux/bootmem.h linux-2.6.7-rc3-hash/include/linux/bootmem.h
@@ -67,4 +67,12 @@ extern void * __init __alloc_bootmem_nod
 	__alloc_bootmem_node((pgdat), (x), PAGE_SIZE, 0)
 #endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */
 
+extern void *__init alloc_large_system_hash(const char *tablename,
+					    unsigned long bucketsize,
+					    unsigned long numentries,
+					    int scale,
+					    int consider_highmem,
+					    unsigned int *_hash_shift,
+					    unsigned int *_hash_mask);
+
 #endif /* _LINUX_BOOTMEM_H */
include/linux/fs.h +2 -0
diff -uNrp linux-2.6.7-rc3/include/linux/fs.h linux-2.6.7-rc3-hash/include/linux/fs.h
@@ -221,6 +221,7 @@ extern int leases_enable, dir_notify_ena
 extern void update_atime (struct inode *);
 
 extern void inode_init(unsigned long);
+extern void inode_init_early(void);
 extern void mnt_init(unsigned long);
 extern void files_init(unsigned long);
 

@@ -1199,6 +1200,7 @@ extern int filp_close(struct file *, fl_
 extern char * getname(const char __user *);
 
 /* fs/dcache.c */
+extern void vfs_caches_init_early(void);
 extern void vfs_caches_init(unsigned long);
 
 #define __getname()	kmem_cache_alloc(names_cachep, SLAB_KERNEL)
include/linux/mmzone.h +12 -0
diff -uNrp linux-2.6.7-rc3/include/linux/mmzone.h linux-2.6.7-rc3-hash/include/linux/mmzone.h
@@ -20,6 +20,18 @@
 #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
 #endif
 
+/*
+ * system hash table size limits
+ * - on large memory machines, we may want to allocate a bigger hash than that
+ *   permitted by MAX_ORDER, so we allocate with the bootmem allocator, and are
+ *   limited to this size
+ */
+#if MAX_ORDER > 14
+#define MAX_SYS_HASH_TABLE_ORDER MAX_ORDER
+#else
+#define MAX_SYS_HASH_TABLE_ORDER 14
+#endif
+
 struct free_area {
 	struct list_head	free_list;
 	unsigned long		*map;
init/main.c +1 -0
diff -uNrp linux-2.6.7-rc3/init/main.c linux-2.6.7-rc3-hash/init/main.c
@@ -454,6 +454,7 @@ asmlinkage void __init start_kernel(void
 		initrd_start = 0;
 	}
 #endif
+	vfs_caches_init_early();
 	mem_init();
 	kmem_cache_init();
 	if (late_time_init)
mm/page_alloc.c +82 -0

97 lines not on this page · raw message

#11 lore raw

Re: [PATCH] Permit inode & dentry hash tables to be allocated > MAX_ORDER size [#2]

Quoted 2 lines · David Howells

Here's an update to my patch.

-static void __init dcache_init(unsigned long mempages) +static void __init dcache_init_early(void)
{
- struct hlist_head *d;
- unsigned long order;
- unsigned int nr_hash;
- int i;
+ struct hlist_head *p;
+ int loop;
+
+ dentry_hashtable =
+ alloc_large_system_hash("Dentry cache",
+ sizeof(struct hlist_head),
+ dhash_entries,
+ 13,
+ 0,
+ &d_hash_shift,
+ &d_hash_mask);
+
+ p = dentry_hashtable;
+ loop = 1 << d_hash_shift;
+ do {
+ INIT_HLIST_HEAD(p);
+ p++;
+ loop--;
+ } while (loop);
+}

We have an opportunity to make this loop less baroque.

	for (i = 0; i < (1 << d_hash_shift); i++)
		INIT_HLIST_HEAD(p[i]);

+void __init vfs_caches_init_early(void)

This function was declared

+extern void vfs_caches_init_early(void);

whereas in other places you _have_ made the definition of __init functions include the "__init". I'm not sure which is best, really, but it seems better to include the __init in the declaration.

+static inline int log2(unsigned long x) __attribute__((pure));

What's the attribute((pure)) for?

It generates a warning on older gcc - please use __attribute_pure__.

+static inline int log2(unsigned long x)

This is just asking for namespace collisions.

+{
+ int r = 0;
+ for (x >>= 1; x > 0; x >>= 1)
+ r++;
+ return r;
+}

The other four or five implementations of log2() use ffx(~n).

author
#12 lore raw

Re: [PATCH] Permit inode & dentry hash tables to be allocated > MAX_ORDER size [try #3]

Here's version 3 of the patch, incorporating comments from Andrew Morton.

Quoted 1 line · Andrew Morton

We have an opportunity to make this loop less baroque.

That seems reasonable. gcc's optimiser should be able to render them the same.

Quoted 3 lines

whereas in other places you _have_ made the definition of __init functions include the "__init". I'm not sure which is best, really, but it seems better to include the __init in the declaration.

You're probably right. This should probably apply to vfs_caches_init() and inode_init() too.

Quoted 1 line

What's the attribute((pure)) for?

It tells gcc that the function's result only depends on its arguments... it makes no references at all to external data. It's like __attribute__((const)) but stronger. This means that gcc can generate code that caches the result.

See the gcc manual.

Quoted 1 line

It generates a warning on older gcc - please use __attribute_pure__.

We still support gcc's that old?

Quoted 1 line

The other four or five implementations of log2() use ffx(~n).

Yes... but ffs() and ffz() take int args, not long args. I suspect that shouldn't matter (that would require the hash table to be calculated at 4Gig buckets in size or greater to be a problem), but why take the chance when we can avoid it easily?

David

Signed-off-by Paul Mackerras <[email protected]>
Signed-off-by David Howells <[email protected]>
fs/dcache.c +24 -44
diff -uNrp linux-2.6.7-rc3/fs/dcache.c linux-2.6.7-rc3-hash/fs/dcache.c
@@ -30,6 +30,7 @@
 #include <linux/security.h>
 #include <linux/seqlock.h>
 #include <linux/swap.h>
+#include <linux/bootmem.h>
 
 #define DCACHE_PARANOIA 1
 /* #define DCACHE_DEBUG 1 */

@@ -1561,13 +1562,25 @@ static int __init set_dhash_entries(char
 }
 __setup("dhash_entries=", set_dhash_entries);
 
-static void __init dcache_init(unsigned long mempages)
+static void __init dcache_init_early(void)
 {
-	struct hlist_head *d;
-	unsigned long order;
-	unsigned int nr_hash;
-	int i;
+	int loop;
+
+	dentry_hashtable =
+		alloc_large_system_hash("Dentry cache",
+					sizeof(struct hlist_head),
+					dhash_entries,
+					13,
+					0,
+					&d_hash_shift,
+					&d_hash_mask);
 
+	for (loop = 0; loop < (1 << d_hash_shift); loop++)
+		INIT_HLIST_HEAD(&dentry_hashtable[loop]);
+}
+
+static void __init dcache_init(unsigned long mempages)
+{
 	/* 
 	 * A constructor could be added for stable state like the lists,
 	 * but it is probably not worth it because of the cache nature

@@ -1580,45 +1593,6 @@ static void __init dcache_init(unsigned 
 					 NULL, NULL);
 	
 	set_shrinker(DEFAULT_SEEKS, shrink_dcache_memory);
-
-	if (!dhash_entries)
-		dhash_entries = PAGE_SHIFT < 13 ?
-				mempages >> (13 - PAGE_SHIFT) :
-				mempages << (PAGE_SHIFT - 13);
-
-	dhash_entries *= sizeof(struct hlist_head);
-	for (order = 0; ((1UL << order) << PAGE_SHIFT) < dhash_entries; order++)
-		;
-
-	do {
-		unsigned long tmp;
-
-		nr_hash = (1UL << order) * PAGE_SIZE /
-			sizeof(struct hlist_head);
-		d_hash_mask = (nr_hash - 1);
-
-		tmp = nr_hash;
-		d_hash_shift = 0;
-		while ((tmp >>= 1UL) != 0UL)
-			d_hash_shift++;
-
-		dentry_hashtable = (struct hlist_head *)
-			__get_free_pages(GFP_ATOMIC, order);
-	} while (dentry_hashtable == NULL && --order >= 0);
-
-	printk(KERN_INFO "Dentry cache hash table entries: %d (order: %ld, %ld bytes)\n",
-			nr_hash, order, (PAGE_SIZE << order));
-
-	if (!dentry_hashtable)
-		panic("Failed to allocate dcache hash table\n");
-
-	d = dentry_hashtable;
-	i = nr_hash;
-	do {
-		INIT_HLIST_HEAD(d);
-		d++;
-		i--;
-	} while (i);
 }
 
 /* SLAB cache for __getname() consumers */

@@ -1632,6 +1606,12 @@ EXPORT_SYMBOL(d_genocide);
 extern void bdev_cache_init(void);
 extern void chrdev_init(void);
 
+void __init vfs_caches_init_early(void)
+{
+	dcache_init_early();
+	inode_init_early();
+}
+
 void __init vfs_caches_init(unsigned long mempages)
 {
 	unsigned long reserve;
fs/inode.c +18 -42

79 lines not on this page · raw message

include/linux/bootmem.h +8 -0
diff -uNrp linux-2.6.7-rc3/include/linux/bootmem.h linux-2.6.7-rc3-hash/include/linux/bootmem.h
@@ -67,4 +67,12 @@ extern void * __init __alloc_bootmem_nod
 	__alloc_bootmem_node((pgdat), (x), PAGE_SIZE, 0)
 #endif /* !CONFIG_HAVE_ARCH_BOOTMEM_NODE */
 
+extern void *__init alloc_large_system_hash(const char *tablename,
+					    unsigned long bucketsize,
+					    unsigned long numentries,
+					    int scale,
+					    int consider_highmem,
+					    unsigned int *_hash_shift,
+					    unsigned int *_hash_mask);
+
 #endif /* _LINUX_BOOTMEM_H */
include/linux/fs.h +7 -4
diff -uNrp linux-2.6.7-rc3/include/linux/fs.h linux-2.6.7-rc3-hash/include/linux/fs.h
@@ -214,15 +214,17 @@ extern int leases_enable, dir_notify_ena
 #include <linux/list.h>
 #include <linux/radix-tree.h>
 #include <linux/audit.h>
+#include <linux/init.h>
 #include <asm/semaphore.h>
 #include <asm/byteorder.h>
 
 /* Used to be a macro which just called the function, now just a function */
 extern void update_atime (struct inode *);
 
-extern void inode_init(unsigned long);
-extern void mnt_init(unsigned long);
-extern void files_init(unsigned long);
+extern void __init inode_init(unsigned long);
+extern void __init inode_init_early(void);
+extern void __init mnt_init(unsigned long);
+extern void __init files_init(unsigned long);
 
 struct buffer_head;
 typedef int (get_block_t)(struct inode *inode, sector_t iblock,

@@ -1199,7 +1201,8 @@ extern int filp_close(struct file *, fl_
 extern char * getname(const char __user *);
 
 /* fs/dcache.c */
-extern void vfs_caches_init(unsigned long);
+extern void __init vfs_caches_init_early(void);
+extern void __init vfs_caches_init(unsigned long);
 
 #define __getname()	kmem_cache_alloc(names_cachep, SLAB_KERNEL)
 #define __putname(name) kmem_cache_free(names_cachep, (void *)(name))
include/linux/kernel.h +9 -0
diff -uNrp linux-2.6.7-rc3/include/linux/kernel.h linux-2.6.7-rc3-hash/include/linux/kernel.h
@@ -92,6 +92,15 @@ asmlinkage int printk(const char * fmt, 
 
 unsigned long int_sqrt(unsigned long);
 
+static inline int __attribute_pure__ long_log2(unsigned long x)
+{
+	int r = 0;
+	for (x >>= 1; x > 0; x >>= 1)
+		r++;
+	return r;
+}
+
+
 extern int printk_ratelimit(void);
 extern int __printk_ratelimit(int ratelimit_jiffies, int ratelimit_burst);
include/linux/mmzone.h +12 -0
diff -uNrp linux-2.6.7-rc3/include/linux/mmzone.h linux-2.6.7-rc3-hash/include/linux/mmzone.h
@@ -20,6 +20,18 @@
 #define MAX_ORDER CONFIG_FORCE_MAX_ZONEORDER
 #endif
 
+/*
+ * system hash table size limits
+ * - on large memory machines, we may want to allocate a bigger hash than that
+ *   permitted by MAX_ORDER, so we allocate with the bootmem allocator, and are
+ *   limited to this size
+ */
+#if MAX_ORDER > 14
+#define MAX_SYS_HASH_TABLE_ORDER MAX_ORDER
+#else
+#define MAX_SYS_HASH_TABLE_ORDER 14
+#endif
+
 struct free_area {
 	struct list_head	free_list;
 	unsigned long		*map;
init/main.c +1 -0
diff -uNrp linux-2.6.7-rc3/init/main.c linux-2.6.7-rc3-hash/init/main.c
@@ -454,6 +454,7 @@ asmlinkage void __init start_kernel(void
 		initrd_start = 0;
 	}
 #endif
+	vfs_caches_init_early();
 	mem_init();
 	kmem_cache_init();
 	if (late_time_init)
mm/page_alloc.c +73 -0

88 lines not on this page · raw message

#13 lore raw

Re: [PATCH] Permit inode & dentry hash tables to be allocated > MAX_ORDER size [try #3]

Quoted 7 lines · David Howells
Quoted 3 lines

What's the attribute((pure)) for?

It tells gcc that the function's result only depends on its arguments... it makes no references at all to external data. It's like __attribute__((const)) but stronger. This means that gcc can generate code that caches the result.

Of course, but we could use it in zillions of places and we don't. Does it actually help?

Quoted 3 lines
Quoted 1 line

It generates a warning on older gcc - please use __attribute_pure__.

We still support gcc's that old?

yup. And gcc-3.4 complains that log2() conflicts with an inbuilt function, but you renamed it.

Quoted 6 lines
Quoted 1 line

The other four or five implementations of log2() use ffx(~n).

Yes... but ffs() and ffz() take int args, not long args. I suspect that shouldn't matter (that would require the hash table to be calculated at 4Gig buckets in size or greater to be a problem), but why take the chance when we can avoid it easily?

No, ffz() takes an unsigned long argument.

It's still not clear to me why we cannot simply increase MAX_ORDER. If that exposes shortcomings in the buddy allocator, that should be where we expend effort?

author
#14 lore raw

Re: [PATCH] Permit inode & dentry hash tables to be allocated > MAX_ORDER size [try #3]

Quoted 5 lines
Quoted 5 lines
Quoted 1 line

What's the attribute((pure)) for?

It tells gcc that the function's result only depends on its arguments... it makes no references at all to external data. It's like __attribute__((const)) but stronger. This means that gcc can generate code that caches the result.

Actually... I'm wrong about that. I've got "pure" and "const" the wrong way around... Perhaps I need to go and read the gcc manual too:-)

Quoted 2 lines

Of course, but we could use it in zillions of places and we don't. Does it actually help?

Well... it could. It certainly doesn't hurt. Actually, it's probably irrelevant on inline functions as the compiler can look inside of those.

Quoted 2 lines
Quoted 2 lines
Quoted 1 line

The other four or five implementations of log2() use ffx(~n).

I presume this should be ffz() not ffx().

Quoted 6 lines
Quoted 4 lines

Yes... but ffs() and ffz() take int args, not long args. I suspect that shouldn't matter (that would require the hash table to be calculated at 4Gig buckets in size or greater to be a problem), but why take the chance when we can avoid it easily?

No, ffz() takes an unsigned long argument.

So it does. However, ffz(~n) is not equivalent to log2(n). This can be demonstrated by this little test program:

	#include <stdio.h>
	#include <stdlib.h>

	static __inline__ unsigned long ffz(unsigned long word)
	{
		__asm__("bsfl %1,%0"
			:"=r" (word)
			:"r" (~word));
		return word;
	}

	int main(int argc, char *argv[])
	{
		for (argv++; *argv; argv++)
			printf("%lu\n", ffz(~strtoul(*argv, NULL, 0)));

		return 0;
	}

	dhowells>/tmp/ffz 0x10
	4
	dhowells>/tmp/ffz 0x8
	3
	dhowells>/tmp/ffz 0x1f
	0

This is not entirely correct; the third answer should be 4 too. The bit scan occurs in the wrong direction.

David