Messages in this thread | | | Date | Wed, 14 Apr 1999 19:14:18 +0200 (CEST) | From | Andrea Arcangeli <> | Subject | [patch] page cache in per-inode RB-trees |
| |
The last week I implemented from scratch RB-trees. Then I changed the kernel to use them in the page cache (I killed the page_hash_table). Via my rbtree.h you can enable/disable at compile time the colouring code (disabling it the tree will be a plain binary-search-tree). It's obviously enabled by default ;). You can also enable a compile time some profiling thing (that I used while benchmarking RB in userspace). All the rb-code is not inline but it's fastcall. It's not inline because I don't want to lose L1 caching.
My second object is to replace the buffer hash table with a per-bdev rbtree (since also the buffer cache is dynamic in size as the page cache).
The code is working _great_ here (I am writing this while there are 2 kernel compile + cvs diff -u and other things running). So now I am very very courious to get some number, to know how my RB will perform on high end machines (also with tons of RAM) under high high I/O load (right now I don't have too much time to bench them myself..).
The RB-trees patch is against 2.2.5_arca11.bz2 but a port to 2.2.5 would be really _trivial_. If you download only the rbtree-patch should be perfectly readable also standalone.
So I ask for people who can run benchmarks to compare 2.2.5 with 2.2.5_arca11 and then to compare 2.2.5_arca11 with 2.2.5_arca11+rbtree_patch. Please do some bench also under high swap/swapcache load. And, please, continue to use the machine (like moving the mouse or whole windows under X) also during high swapout load: this will allow you to see differences between different VM in preserving the working set (you won't produce numbers but you'll can see big differences).
Here it is 2.2.5_arca11:
ftp://e-mind.com/pub/linux/arca-tree/2.2.5_arca11.bz2
and here the RB patch against 2.2.5_arca11:
ftp://e-mind.com/pub/linux/kernel-patches/rbtree-2.2.5_arca11.bz2
The last thing about implementation details is that I would like to do a rb_entry() operation that will return NULl if the node-pointer was NULL and that will return the pagemap-pointer if the node-pointer wasn't null, but _without_ producing branch in the asm. I could avoid the additional branch just now playing with the rb_node_t directly in filemap.c but it wasn't clean according to me because I want _all_ the rb details _only_ in pagemap.h...
Right now the rb_entry() call is:
#define rb_entry(ptr, type, member) \ ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member)))
If somebody has hints about this or about every other thing let me know as usual ;).
Andrea Arcangeli
- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.rutgers.edu Please read the FAQ at http://www.tux.org/lkml/
| |