RE: Limit hash table size

Chen, Kenneth W
2004-01-14T22:32:46Z

[-- Attachment #1: Type: text/plain, Size: 1587 bytes --]

Anton Blanchard wrote:
> Well x86 isnt very interesting here, its all the 64bit archs
> that will end up with TBs of memory in the future.

To address Anton's concerns on PPC64, we have revised the patch to
enforce maximum size base on number of entry instead of page order. So
differences in page size/pointer size etc doesn't affect the final
calculation. The upper bound is capped at 2M. All numbers on x86
remain the same as we don't want to disturb already established and
working number. See patch at the end of the email. It is diff'ed
relative to 2.6.1-mm3 tree.

> But look at the horrid worst case there. My point is limiting
> the hash without any data is not a good idea. In 2.4 we raised
> MAX_ORDER on ppc64 because we spent so much time walking
> pagecache chains,

I just have to re-iterate that when hash table is made too large, we
start trading cache misses on the head array accesses for misses on the
hash list traversal. Big hashes can hurt you if you don't actually use
the capacity.

> Why cant we do something like Andrews recent min_free_kbytes
> patch and make the rate of change non linear. Just slow the
> increase down as we get bigger. I agree a 2GB hashtable is
> pretty ludicrous, but a 4MB one on a 512GB machine (which
> we sell at the moment) could be too :)

It doesn't need to be over designed. Generally there is no one size fit
all type of solution either. Linear scale works fine for many years and
it just start to tip off on large machine. We just need to put a upper
bound before it runs away.

- Ken

[-- Attachment #2: hash2.patch --]
[-- Type: application/octet-stream, Size: 1769 bytes --]

diff -Nur linux-2.6.1-mm3.orig/fs/dcache.c linux-2.6.1-mm3/fs/dcache.c
--- linux-2.6.1-mm3.orig/fs/dcache.c 2004-01-14 13:48:09.000000000 -0800
+++ linux-2.6.1-mm3/fs/dcache.c 2004-01-14 14:02:02.000000000 -0800
@@ -49,6 +49,7 @@
*/
#define D_HASHBITS d_hash_shift
#define D_HASHMASK d_hash_mask
+#define D_HASHMAX (2*1024*1024UL) /* max number of entries */

static unsigned int d_hash_mask;
static unsigned int d_hash_shift;
@@ -1552,9 +1553,9 @@

set_shrinker(DEFAULT_SEEKS, shrink_dcache_memory);

- mempages >>= 1;
- mempages *= sizeof(struct hlist_head);
- for (order = 0; (order < 10) && (((1UL << order) << PAGE_SHIFT) < mempages); order++)
+ mempages = (mempages << PAGE_SHIFT) >> 13;
+ mempages = min(D_HASHMAX, mempages) * sizeof(struct hlist_head);
+ for (order = 0; ((1UL << order) << PAGE_SHIFT) < mempages; order++)
;

do {
diff -Nur linux-2.6.1-mm3.orig/fs/inode.c linux-2.6.1-mm3/fs/inode.c
--- linux-2.6.1-mm3.orig/fs/inode.c 2004-01-14 13:48:09.000000000 -0800
+++ linux-2.6.1-mm3/fs/inode.c 2004-01-14 14:01:34.000000000 -0800
@@ -53,6 +53,7 @@
*/
#define I_HASHBITS i_hash_shift
#define I_HASHMASK i_hash_mask
+#define I_HASHMAX (2*1024*1024UL) /* max number of entries */

static unsigned int i_hash_mask;
static unsigned int i_hash_shift;
@@ -1328,9 +1329,9 @@
for (i = 0; i < ARRAY_SIZE(i_wait_queue_heads); i++)
init_waitqueue_head(&i_wait_queue_heads[i].wqh);

- mempages >>= 2;
- mempages *= sizeof(struct hlist_head);
- for (order = 0; (order < 10) && (((1UL << order) << PAGE_SHIFT) < mempages); order++)
+ mempages = (mempages << PAGE_SHIFT) >> 14;
+ mempages = min(I_HASHMAX, mempages) * sizeof(struct hlist_head);
+ for (order = 0; ((1UL << order) << PAGE_SHIFT) < mempages; order++)
;

do {