lkml.org 
[lkml]   [2003]   [Nov]   [25]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
Patch in this message
/
From
SubjectRe: hash table sizes
Date
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
--- 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)[unhandled content-type:application/pgp-signature]
\
 
 \ /
  Last update: 2005-03-22 13:58    [from the cache]
©2003-2011 Jasper Spaans