Re: [patch] arca-vm-2.2.5

[Doug Ledford <dledford@redhat.com>]

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

Andrea Arcangeli wrote:
> 
> On Mon, 5 Apr 1999, Chuck Lever wrote:
> 
> >buckets out of 32K buckets have hundreds of buffers).  i have a new hash
> >function that works very well, and even helps inter-run variance and
> >perceived interactive response.  i'll post more on this soon.
> 
> Cool! ;)) But could you tell me _how_ do you design an hash function? Are
> you doing math or do you use instinct? I never gone into the details of
> benchmarking or designing an hash function simply because I don't like
> fuzzy hash and instead I want to replace them with RB-trees all over the
> place (and I know the math about RB-trees), but I like to learn how to
> design an hash function anyway (even if I don't want to discover that
> myself without reading docs as usual ;).
> 
> >but also the page hash function uses the hash table size as a shift value
> >when computing the index, so it may combine the interesting bits in a
> >different (worse) way when you change the hash table size.  i'm planning
> >to instrument the page hash to see exactly what's going on.
> 
> Agreed. This is true. I thought about that and I am resizing the hash
> table size to the original 11 bit now (since you are confirming that I
> broken the hash function).
> 
> >IMHO, i'd think if the buffer cache has a large hash table, you'd want the
> >page cache to have a table as large or larger.  both track roughly the
> >same number of objects...  and the page cache is probably used more often
> 
> Agreed.

Hmmm...I've talked about this a few times to Alan Cox and Stephen
Tweedie.  I didn't bother to instrument the hash function because in
this case I knew it was tuned to the size of the inode structs.  But, I
did implement a variable sized page cache hash table array.  I did this
because at 512MB of RAM, having only 2048 hash buckets (11 bits) became
a real bottleneck in page cache hash entry lookups.  Essentially, when
the number of physical pages per hash buckets gets too large, then hash
chains can grow excessively long and take entirely too long to look up
when the page is not in the page cache (or when it is but it's at the
end of a long chain).  Since these lookups occur as frequently as they
do, they get to be excessive quickly.  I'm attaching the patch I've been
using here for a while.  Feel free to try it out.  One of the best tests
for the effect of this patch is a bonnie run on a machine with more disk
speed than CPU power.  In that case the page cache lookup becomes a
bottleneck.  In other conditions, you see the same disk speed results
but with smaller % CPU utilization.  On a PII400 dual machine with 512MB
RAM and a 4 Cheetah RAID0 array it made a 10MByte/s difference in
throughput.  On another machine it made a roughly 6 to 8% difference in
CPU utilization.


-- 
  Doug Ledford   <dledford@redhat.com>
   Opinions expressed are my own, but
      they should be everybody's.

[-- Attachment #2: page-2.2.2.patch --]
[-- Type: application/octet-stream, Size: 3509 bytes --]

--- linux/include/linux/pagemap.h.page	Thu Jan 28 17:43:17 1999
+++ linux/include/linux/pagemap.h	Mon Mar  8 07:37:54 1999
@@ -17,13 +17,13 @@
 	return PAGE_OFFSET + PAGE_SIZE * (page - mem_map);
 }
 
-#define PAGE_HASH_BITS 11
-#define PAGE_HASH_SIZE (1 << PAGE_HASH_BITS)
-
 #define PAGE_AGE_VALUE 16
-
 extern unsigned long page_cache_size; /* # of pages currently in the hash table */
-extern struct page * page_hash_table[PAGE_HASH_SIZE];
+extern struct page ** page_hash_table;
+extern unsigned long page_hash_size;
+extern unsigned long page_hash_mask;
+extern unsigned long page_hash_bits;
+extern long page_cache_init(long, long);
 
 /*
  * We use a power-of-two hash table to avoid a modulus,
@@ -35,8 +35,8 @@
 {
 #define i (((unsigned long) inode)/(sizeof(struct inode) & ~ (sizeof(struct inode) - 1)))
 #define o (offset >> PAGE_SHIFT)
-#define s(x) ((x)+((x)>>PAGE_HASH_BITS))
-	return s(i+o) & (PAGE_HASH_SIZE-1);
+#define s(x) ((x)+((x)>>page_hash_bits))
+	return s(i+o) & page_hash_mask;
 #undef i
 #undef o
 #undef s
--- linux/init/main.c.page	Mon Feb 22 22:44:53 1999
+++ linux/init/main.c	Mon Mar  8 07:37:54 1999
@@ -19,6 +19,7 @@
 #include <linux/utsname.h>
 #include <linux/ioport.h>
 #include <linux/init.h>
+#include <linux/pagemap.h>
 #include <linux/smp_lock.h>
 #include <linux/blk.h>
 #include <linux/hdreg.h>
@@ -1149,6 +1150,7 @@
 		initrd_start = 0;
 	}
 #endif
+	memory_start = page_cache_init(memory_start, memory_end);
 	mem_init(memory_start,memory_end);
 	kmem_cache_sizes_init();
 #ifdef CONFIG_PROC_FS
--- linux/mm/filemap.c.page	Mon Feb 22 22:44:53 1999
+++ linux/mm/filemap.c	Mon Mar  8 07:37:54 1999
@@ -13,6 +13,7 @@
 #include <linux/shm.h>
 #include <linux/mman.h>
 #include <linux/locks.h>
+#include <linux/init.h>
 #include <linux/pagemap.h>
 #include <linux/swap.h>
 #include <linux/smp_lock.h>
@@ -23,6 +24,7 @@
 
 #include <asm/pgtable.h>
 #include <asm/uaccess.h>
+#include <asm/io.h>
 
 /*
  * Shared mappings implemented 30.11.1994. It's not fully working yet,
@@ -32,7 +34,45 @@
  */
 
 unsigned long page_cache_size = 0;
-struct page * page_hash_table[PAGE_HASH_SIZE];
+unsigned long page_hash_size = 0;
+unsigned long page_hash_bits = 0;
+unsigned long page_hash_mask = 0;
+struct page ** page_hash_table = NULL;
+
+/*
+ * The init function that starts off our page cache
+ */
+long __init page_cache_init( long mem_begin, long mem_end )
+{
+	long cache_begin;
+	long i;
+
+	for(i=0; i < sizeof(long) * 8; i++)
+		if(virt_to_phys((void *)mem_end) & (1<<i))
+			page_hash_bits = i;
+	page_hash_bits -= (PAGE_SHIFT + 2);
+	if(page_hash_bits < 10)
+		page_hash_bits = 10;
+	cache_begin = (mem_begin + (PAGE_SIZE - 1)) & ~PAGE_SIZE;
+	page_hash_size = 1 << page_hash_bits;
+	page_hash_mask = page_hash_size - 1;
+	if ( ((virt_to_phys((void *)cache_begin) <= 0xfffff) && 
+	      (virt_to_phys((void *)cache_begin) >= (0x9f000 - page_hash_size))) )
+	{
+		/*
+		 * Our structure would fall into the middle of the upper 
+		 * BIOS area of the computer, go above it to the 1MB mark
+		 * and start from there
+		 */
+		cache_begin = (long)phys_to_virt(0x100000);
+	}
+	page_hash_table = (struct page **)cache_begin;
+	memset(page_hash_table, 0, page_hash_size * sizeof(void));
+	printk(KERN_INFO "page_cache_init: allocated %ldk of RAM with %ld hash "
+		"buckets.\n", (page_hash_size * sizeof(void *)) / 1024,
+		page_hash_size);
+	return(cache_begin + (page_hash_size * sizeof(void *)));
+}
 
 /*
  * Simple routines for both non-shared and shared mappings.