Re: hash table sizes

[Thomas Schlichter <schlicht@uni-mannheim.de>]

[-- Attachment #1.1: Type: text/plain, Size: 2490 bytes --]

Hi Jens,

I was wondering about you funny formula, too. (especially because it was 23 - 
(PAGE_SHIFT -1) and not 24 - PAGE_SHIFT ;-) So I wanted to find out why this:
1:	mempages >>= (23 - (PAGE_SHIFT - 1));
2:	order = max(2, fls(mempages));
3:	order = min(12, order);

should be similar to this original code:
4:	mempages >>= (14 - PAGE_SHIFT);
5:	mempages *= sizeof(struct hlist_head);
6:	for (order = 0; ((1UL << order) << PAGE_SHIFT) < mempages; order++)
7:		;

Well, first I saw that lines 2 and 3 make order to be between 2 and 12. OK 
this is new, and I like it ;-) Then I saw you tried to convert the ugly lines 
6 + 7 into a fls() call. Fine! (I like that, too) Line 6 + 7 can be converted 
to following (almost equivalent) lines:
6 + 7	-> 8a:	order = fls(mempages) - PAGE_SHIFT;
or
6 + 7	-> 8b:	order = fls(mempages >> PAGE_SHIFT);

Now the shift is not present in line 2, so I folded it from line 8b into line 
4 and got:
4	-> 9:	mempages >>= 14;
5:		mempages *= sizeof(struct hlist_head);
8b	-> 10:	order = fls(mempages);

But to make the math a bit more correct the multiplication from line 5 has to 
be done before the shift in line 9. So I got following simple two lines 
equivalent to lines 4 to 7:
5 + 9	-> 11:	mempages = (mempages * sizeof(struct hlist_head)) >> 14;
10:		order = fls(mempages);

So, now we can compare line 1 and 11. OK, let's assume PAGE_SHIFT = 12. So we 
get:
1	-> 12:	mempages >>= (23 - (12 - 1)); // right shift by 12

If sizeof(struct hlist_head) == 4, we get for line 10:
11	-> 13:	mempages = (mempages * 4) >> 14; // right shift by 12

And HURRAY, we've got it...!
But they are only equivalent if (PAGE_SHIFT == 12) && (sizeof(struct 
hlist_head) == 4)...

So I propose the attached patch which should be closer to the original and 
makes order not to be greater than 12. (Btw. this only changes anything for 
more than 2^24 pages of memory, so I think this is a good idea!)

Best reagrds
   Thomas Schlichter

On Tuesday 25 November 2003 14:54, Jes Sorensen wrote:
> >>>>> "William" == William Lee Irwin <wli@holomorphy.com> writes:
>
> William> On Tue, Nov 25, 2003 at 08:35:49AM -0500, Jes Sorensen wrote:
> >> + mempages >>= (23 - (PAGE_SHIFT - 1)); + order = max(2,
> >> fls(mempages)); + order = min(12, order);
>
> William> This is curious; what's 23 - (PAGE_SHIFT - 1) supposed to
> William> represent?
>
> Well MB >> 2 or consider it trial and error ;-)
>
> Cheers,
> Jes

[-- Attachment #1.2: hash_sizes.diff --]
[-- Type: text/x-diff, Size: 2265 bytes --]

--- linux-2.6.0-test9-mm5/fs/dcache.c.orig	Tue Nov 25 15:29:38 2003
+++ linux-2.6.0-test9-mm5/fs/dcache.c	Tue Nov 25 16:18:37 2003
@@ -1530,9 +1530,8 @@
 static void __init dcache_init(unsigned long mempages)
 {
 	struct hlist_head *d;
-	unsigned long order;
 	unsigned int nr_hash;
-	int i;
+	int i, order;
 
 	/* 
 	 * A constructor could be added for stable state like the lists,
@@ -1552,12 +1551,10 @@
 	
 	set_shrinker(DEFAULT_SEEKS, shrink_dcache_memory);
 
-#if PAGE_SHIFT < 13
-	mempages >>= (13 - PAGE_SHIFT);
-#endif
-	mempages *= sizeof(struct hlist_head);
-	for (order = 0; ((1UL << order) << PAGE_SHIFT) < mempages; order++)
-		;
+	mempages = (mempages * sizeof(struct hlist_head)) >> 13;
+	order = fls(mempages);
+	if (order > 12)
+		order = 12;
 
 	do {
 		unsigned long tmp;
@@ -1575,7 +1572,7 @@
 			__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",
+	printk(KERN_INFO "Dentry cache hash table entries: %d (order: %d, %ld bytes)\n",
 			nr_hash, order, (PAGE_SIZE << order));
 
 	if (!dentry_hashtable)
--- linux-2.6.0-test9-mm5/fs/inode.c.orig	Tue Nov 25 15:33:22 2003
+++ linux-2.6.0-test9-mm5/fs/inode.c	Tue Nov 25 16:17:38 2003
@@ -1319,17 +1319,16 @@
 void __init inode_init(unsigned long mempages)
 {
 	struct hlist_head *head;
-	unsigned long order;
 	unsigned int nr_hash;
-	int i;
+	int i, order;
 
 	for (i = 0; i < ARRAY_SIZE(i_wait_queue_heads); i++)
 		init_waitqueue_head(&i_wait_queue_heads[i].wqh);
 
-	mempages >>= (14 - PAGE_SHIFT);
-	mempages *= sizeof(struct hlist_head);
-	for (order = 0; ((1UL << order) << PAGE_SHIFT) < mempages; order++)
-		;
+	mempages = (mempages * sizeof(struct hlist_head)) >> 14;
+	order = fls(mempages);
+	if (order > 12)
+		order = 12;
 
 	do {
 		unsigned long tmp;
@@ -1347,7 +1346,7 @@
 			__get_free_pages(GFP_ATOMIC, order);
 	} while (inode_hashtable == NULL && --order >= 0);
 
-	printk("Inode-cache hash table entries: %d (order: %ld, %ld bytes)\n",
+	printk("Inode-cache hash table entries: %d (order: %d, %ld bytes)\n",
 			nr_hash, order, (PAGE_SIZE << order));
 
 	if (!inode_hashtable)

[-- Attachment #2: signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]