Skip to contentSkip to conversation

Horrible L2 cache effects from kernel compile

DISCUSSION Andi Kleen 4 participants 5 messages Feb 25, 2003 – Feb 27, 2003 3 messages not in the archive

Subsystems (2)
lore
Share & tools
lore

A message that is not in the archive (sent off-list or not yet received): [email protected]

Andi Kleen

author
#1 lore raw
Quoted 2 lines · Dave Hansen

The surprising thing? d_lookup() accounts for 8% of the time spent waiting for an L2 miss.

The reason:

Dentry cache hash table entries: 131072 (order: 8, 1048576 bytes) Inode cache hash table entries: 65536 (order: 7, 524288 bytes)

(1GB) I bet on your big memory box it is even worse. No cache in the world can cache that. If the hash function works well it'll guarantee few if any cache locality.

Try the appended experimental patch. It replaces the hash table madness with relatively small fixed tables. The actual size is probably left for experimentation. I choose 64K for inode and 128K for dcache for now. That's more on the small side, but should work on all linux boxes except very small embedded systems. Acutally I suspect the inode could be made even smaller (iget should be rather infrequent even for NFS server loads because nfsd has an own cache) and everybody else should mostly only use the dcache.

Other numbers may work better for your workload. Please test.

It also replaces the cache wasting double pointer list_head hash buckets with single pointer hash buckets. This cuts the hash table overhead in half

Also adds some prefetches which may help a bit for walking the lists.

Work left to do: try to find a better hash function that isn't afraid of prime numbers.

Patch is still experimental, especially I had to change a few details from dcache-rcu (removed the isbucket check which apparently wasn't needed anymore). I only tested on UP/x86-64 so far, it is possible that I added some new RCU races. Review needed.

Also I replaced the max_dentries rcu race break hack with a fixed number now. Unfortunately putting any number there is wrong: if I chose a big number (like I do currently) it can loop for a long time, if I chose a small number there is an artitifical limit on hash table bucket lengths that may be hit in some extreme workloads.

-And

include/linux/list.h renamed from include/linux/list.h-HASH +89 -0
@@ -319,6 +319,95 @@
 	for (pos = (head)->next, n = pos->next; pos != (head); \
 		pos = n, ({ read_barrier_depends(); 0;}), n = pos->next)
 
+/* 
+ * Double linked lists with a single pointer list head. 
+ * Mostly useful for hash tables where the two pointer list head is 
+ * too wasteful.
+ * You lose the ability to access the tail in O(1).
+ */ 
+
+struct hlist_head { 
+	struct hlist_node *first; 
+}; 
+
+struct hlist_node { 
+	struct hlist_node *next, **pprev; 
+}; 
+
+#define HLIST_HEAD_INIT { first: NULL } 
+#define HLIST_HEAD(name) struct hlist_head name = {  first: NULL }
+#define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) 
+#define INIT_HLIST_NODE(ptr) ((ptr)->next = NULL, (ptr)->pprev = NULL)
+
+/* This is really misnamed */
+static __inline__ int hnode_empty(struct hlist_node *h) 
+{ 
+	return h->pprev==0;
+} 
+
+static __inline__ int hlist_empty(struct hlist_head *h) 
+{ 
+	return !h->first;
+} 
+
+static __inline__ void hlist_del(struct hlist_node *n) 
+{
+	/* The if could be avoided by a common dummy pprev target. */
+	if (!n->pprev) 
+		return; 
+	*(n->pprev) = n->next;  
+	if (n->next) 
+		n->next->pprev = n->pprev;
+}  
+
+#define hlist_del_rcu hlist_del  /* list_del_rcu is identical too? */
+
+static __inline__ void hlist_del_init(struct hlist_node *n) 
+{
+	/* The if could be avoided by a common dummy pprev target. */
+	if (!n->pprev) 
+		return; 
+	*(n->pprev) = n->next;  
+	if (n->next) 
+		n->next->pprev = n->pprev;
+	INIT_HLIST_NODE(n);
+}  
+
+static __inline__ void hlist_add_head(struct hlist_node *n, struct hlist_head *h) 
+{ 
+	n->next = h->first; 
+	if (h->first) 
+		h->first->pprev = &n->next;
+	h->first = n; 
+	n->pprev = &h->first; 
+} 
+
+static __inline__ void hlist_add_head_rcu(struct hlist_node *n, struct hlist_head *h) 
+{ 
+	n->next = h->first;
+	wmb();
+	if (h->first) 
+		h->first->pprev = &n->next;
+	h->first = n; 
+	n->pprev = &h->first; 
+} 
+
+/* next must be != NULL */
+static __inline__ void hlist_add_before(struct hlist_node *n, struct hlist_node *next)
+{
+	n->pprev = next->pprev;
+	n->next = next; 
+	next->pprev = &n->next; 
+	*(n->pprev) = n;
+}
+
+#define hlist_entry(ptr, type, member) container_of(ptr,type,member)
+
+/* Cannot easily do prefetch unfortunately */
+#define hlist_for_each(pos, head) \
+	for (pos = (head)->first; pos; \
+	     pos = pos->next) 
+
 #else
 #warning "don't include kernel headers in userspace"
 #endif /* __KERNEL__ */
include/linux/dcache.h renamed from include/linux/dcache.h-HASH +4 -4
@@ -80,8 +80,8 @@
 	unsigned long d_move_count;	/* to indicated moved dentry while lockless lookup */
 	struct inode  * d_inode;	/* Where the name belongs to - NULL is negative */
 	struct dentry * d_parent;	/* parent directory */
-	struct list_head * d_bucket;	/* lookup hash bucket */
-	struct list_head d_hash;	/* lookup hash list */
+	struct hlist_head * d_bucket;	/* lookup hash bucket */
+	struct hlist_node d_hash;	/* lookup hash list */
 	struct list_head d_lru;		/* LRU list */
 	struct list_head d_child;	/* child of parent list */
 	struct list_head d_subdirs;	/* our children */
@@ -171,7 +171,7 @@
 static __inline__ void __d_drop(struct dentry * dentry)
 {
 	dentry->d_vfs_flags |= DCACHE_UNHASHED;
-	list_del_rcu(&dentry->d_hash);
+	hlist_del_rcu(&dentry->d_hash);
 }
 
 static __inline__ void d_drop(struct dentry * dentry)
@@ -198,7 +198,7 @@
 extern struct dentry * d_splice_alias(struct inode *, struct dentry *);
 extern void shrink_dcache_sb(struct super_block *);
 extern void shrink_dcache_parent(struct dentry *);
-extern void shrink_dcache_anon(struct list_head *);
+extern void shrink_dcache_anon(struct hlist_head *);
 extern int d_invalidate(struct dentry *);
 
 /* only used at mount-time */
include/linux/fs.h renamed from include/linux/fs.h-HASH +2 -2
@@ -353,7 +353,7 @@
 };
 
 struct inode {
-	struct list_head	i_hash;
+	struct hlist_node	i_hash;
 	struct list_head	i_list;
 	struct list_head	i_dentry;
 	unsigned long		i_ino;
@@ -601,7 +601,7 @@
 
 	struct list_head	s_dirty;	/* dirty inodes */
 	struct list_head	s_io;		/* parked for writeback */
-	struct list_head	s_anon;		/* anonymous dentries for (nfs) exporting */
+	struct hlist_head	s_anon;		/* anonymous dentries for (nfs) exporting */
 	struct list_head	s_files;
 
 	struct block_device	*s_bdev;
fs/hugetlbfs/inode.c renamed from fs/hugetlbfs/inode.c-HASH +3 -3
@@ -189,7 +189,7 @@
 
 static void hugetlbfs_delete_inode(struct inode *inode)
 {
-	list_del_init(&inode->i_hash);
+	hlist_del_init(&inode->i_hash);
 	list_del_init(&inode->i_list);
 	inode->i_state |= I_FREEING;
 	inodes_stat.nr_inodes--;
@@ -208,7 +208,7 @@
 {
 	struct super_block *super_block = inode->i_sb;
 
-	if (list_empty(&inode->i_hash))
+	if (hlist_empty(&inode->i_hash))
 		goto out_truncate;
 
 	if (!(inode->i_state & (I_DIRTY|I_LOCK))) {
@@ -223,7 +223,7 @@
 
 	/* write_inode_now() ? */
 	inodes_stat.nr_unused--;
-	list_del_init(&inode->i_hash);
+	hlist_del_init(&inode->i_hash);
 out_truncate:
 	list_del_init(&inode->i_list);
 	inode->i_state |= I_FREEING;
fs/fs-writeback.c renamed from fs/fs-writeback.c-HASH +1 -1
@@ -90,7 +90,7 @@
 		 * Only add valid (hashed) inodes to the superblock's
 		 * dirty list.  Add blockdev inodes as well.
 		 */
-		if (list_empty(&inode->i_hash) && !S_ISBLK(inode->i_mode))
+		if (hlist_empty(&inode->i_hash) && !S_ISBLK(inode->i_mode))
 			goto out;
 
 		/*
fs/inode.c renamed from fs/inode.c-HASH +44 -84

305 lines not on this page · raw message

fs/dcache.c renamed from fs/dcache.c-HASH +51 -69

254 lines not on this page · raw message

#2 lore raw
Quoted 1 line · Andi Kleen

Other numbers may work better for your workload. Please test.

The whole post:
http://marc.theaimsgroup.com/?l=linux-kernel&m=104619044800608&w=2

The number of cycles in d_lookup increased by 10% with your patch. But, it looks like lots of stuff was moving around, so I wouldn't take too much stock in it.

% change 2.5.62 2.5.62-ak-dc
in cycles cycles(%oftot) cycles(%oftot)
+20.685% 6251(0.397%) 9834(0.603%) ext3_get_inode_loc
+13.296% 16183(1.027%) 21863(1.341%) try_to_wake_up
+10.560% 130566(8.283%) 166867(10.239%) d_lookup

 +10.202%   12525(0.795%)   15892(0.975%) filemap_nopage
  +5.991%   22127(1.404%)   25793(1.583%) schedule
  +5.581%    8705(0.552%)   10064(0.618%) run_timer_softirq
  +4.246%    7922(0.503%)    8917(0.547%) current_kernel_time
  +4.116%    9196(0.583%)   10324(0.633%) __wake_up
  +3.739%   21650(1.373%)   24123(1.480%) __find_get_block
  +3.631%    7226(0.458%)    8034(0.493%) do_page_cache_readahead
  +3.287%   72668(4.610%)   80239(4.923%) find_get_page
  +2.857%   11435(0.725%)   12518(0.768%) strnlen_user
  -2.184%   35107(2.227%)   34745(2.132%) .text.lock.inode
  -2.200%   17129(1.087%)   16947(1.040%) __fput
  -2.706%   28213(1.790%)   27632(1.695%) start_this_handle
  -2.823%   36539(2.318%)   35703(2.191%) smp_apic_timer_interrupt
  -3.668%   26074(1.654%)   25050(1.537%) load_balance
  -3.844%    8367(0.531%)    8010(0.491%) find_vma
  -4.340%   46642(2.959%)   44211(2.713%) scheduler_tick
  -4.650%    9965(0.632%)    9387(0.576%) default_idle
  -4.667%   14213(0.902%)   13384(0.821%) do_wp_page
  -4.728%   13603(0.863%)   12794(0.785%) mark_offset_tsc
  -4.815%   39748(2.522%)   37319(2.290%) __blk_queue_bounce
  -6.545%   44437(2.819%)   40298(2.473%) x86_profile_hook
  -6.991%   36113(2.291%)   32457(1.991%) __copy_from_user_ll
  -7.660%   16275(1.032%)   14432(0.886%) may_open
 -13.539%   28492(1.807%)   22432(1.376%) get_empty_filp
 -16.257%   10334(0.656%)    7696(0.472%) file_move
Signature · 2 lines
Dave Hansen
[email protected]
#3 lore raw
In reply to Andi Kleen
Quoted 5 lines · Andi Kleen
Quoted 2 lines · Dave Hansen

The surprising thing? d_lookup() accounts for 8% of the time spent waiting for an L2 miss.

Quoted 8 lines

The reason:

Dentry cache hash table entries: 131072 (order: 8, 1048576 bytes) Inode cache hash table entries: 65536 (order: 7, 524288 bytes)

(1GB) I bet on your big memory box it is even worse. No cache in the world can cache that. If the hash function works well it'll guarantee few if any cache locality.

Ehh, I read that as 1MB for the dentry cache and .5MB for the inode cache, Which is several orders less than 1GB. Ofcourse these are only the pointers to the chains of dentries and inodes which take up far more than just 8 bytes per entry. And once you have to start traversing those hashchains you're toast.

Quoted 3 lines

Try the appended experimental patch. It replaces the hash table madness with relatively small fixed tables. The actual size is probably left for experimentation. I choose 64K for inode and 128K for dcache for now.

And as a result you are probably just making the length of any given hashchain longer, and walking the chain is painful as the referenced objects are actually scattered throughout memory.

Another optimization is to leave the tables big (scaled up with memory size), but try to keep the chains as short as possible. f.i. when adding a new entry to a non-empty chain, drop the old entry if it isn't used.

That would give a lot more control over the actual size of the dentry and inode caches, so that updatedb runs won't push these caches to completely take over the VM.

Jan

A message that is not in the archive (sent off-list or not yet received): [email protected]

A message that is not in the archive (sent off-list or not yet received): 20030225170546.GA23772@morningstar.nowhere.lie.suse.lists.linux.kernel

author
#6 lore raw
Quoted 1 line · John W. M. Stevens

http://www.sourcejudy.com/downloads/10minutes.htm

Feel free to code it up. If you did I'm sure someone would be willing to test it on large boxes too.

However with RCU in the equation looking may get very interesting... Hash tables have the advantage that they're simply enough for lockless tricks; balanced trees are likely not so lucky.

-Andi (who took a look at judy some time ago but it looked horribly complicated, even worse so than skiplists)

#7 lore raw
Quoted 7 lines · Andi Kleen
Quoted 1 line · John W. M. Stevens

http://www.sourcejudy.com/downloads/10minutes.htm

Feel free to code it up. If you did I'm sure someone would be willing to test it on large boxes too.

Quoted 6 lines

However with RCU in the equation looking may get very interesting... Hash tables have the advantage that they're simply enough for lockless tricks; balanced trees are likely not so lucky.

-Andi (who took a look at judy some time ago but it looked horribly complicated, even worse so than skiplists)

Note that the Judy trees paper has some text deleted which begins "{some Judy patent applications}... {Remainder deleted, sorry, you don't need to read this to understand the released software.}".

Maybe some parts of the algorithm are patent-pending in the US?

-- Jamie