Skip to contentSkip to conversation

Ocfs2 performance bugs of doom

PATCH Daniel Phillips 10 participants 29 messages Mar 3, 2006 – Mar 11, 2006

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

Hi ocfs2 guys,

Actually, ocfs2 is not doomed - far from it! I just wanted to grab a few more of those eyeballs that normally glaze over each time they see a cluster mail run by on lkml[1]. Today's news: you are still not finished with global lock systime badness, and I already have more performance bugs for you.

For interested observers, the story so far:

A couple of days ago I reported a bug to the ocfs2 team via irc[2]. If I untar a kernel tree several times, each into its own directory, ocfs2 system time (already four times higher than ext3 to start with) increases linearly on each successive iteration, up to a very silly amount where it finally stabilizes.

This is with ocfs2 running uniprocessor on a single node with a local disk. The same performance bug also bites on a cluster of course.

In a dazzling display of developer studlyness, the ocfs2 team found the hash table bottleneck while I was still trying to figure out how to make oprofile behave.

    http://sosdg.org/~coywolf/lxr/source/fs/ocfs2/dlm/dlmdomain.c?v=2.6.16-rc3#L102

So the ocfs2 guys switched from double word to single word hash table heads and quadrupled the size of the hash table. Problem solved, right? No!

I got the patch from Git (note to Gitweb devs: could "plain" please be _really plain_ just like marc's "raw" instead of colorless html?). While system is indeed reduced, it still sucks chamber pot juice:

CPU: P4 / Xeon, speed 2793.41 MHz (estimated)
samples % image name app name symbol name
-------------------------------------------------------------------------------
4399778 64.0568 libbz2.so.1.0.2 libbz2.so.1.0.2 (no symbols)
4399778 100.000 libbz2.so.1.0.2 libbz2.so.1.0.2 (no symbols) [self]
-------------------------------------------------------------------------------
1410173 20.5308 vmlinux vmlinux __dlm_lookup_lockres
1410173 100.000 vmlinux vmlinux __dlm_lookup_lockres [self]
-------------------------------------------------------------------------------
82840 1.2061 oprofiled oprofiled (no symbols)
82840 100.000 oprofiled oprofiled (no symbols) [self]
-------------------------------------------------------------------------------
68368 0.9954 vmlinux vmlinux ocfs2_local_alloc_count_bits
68368 100.000 vmlinux vmlinux ocfs2_local_alloc_count_bits [self]
-------------------------------------------------------------------------------
47639 0.6936 tar tar (no symbols)
47639 100.000 tar tar (no symbols) [self]
-------------------------------------------------------------------------------
1 0.0488 vmlinux vmlinux ide_build_sglist
6 0.2925 vmlinux vmlinux ide_do_request
70 3.4130 vmlinux vmlinux __ide_dma_test_irq
128 6.2409 vmlinux vmlinux ata_vlb_sync
134 6.5334 vmlinux vmlinux proc_ide_read_imodel
147 7.1672 vmlinux vmlinux ide_dma_verbose
1565 76.3042 vmlinux vmlinux ide_do_rw_disk
20390 0.2969 vmlinux vmlinux ide_dma_speed
20390 100.000 vmlinux vmlinux ide_dma_speed [self]
-------------------------------------------------------------------------------

Hash probe cleanup and hand optimization
----------------------------------------

I included two patches below. The first vmallocs a megabyte hash table instead of a single page. This definitively squishes away the global lock hash table overhead so that systime stays about twice as high as ext3 instead of starting at three times and increasing to four times with the (new improved) 4K hash table.

Re vmalloc... even with the extra tlb load, this is better than kmallocing a smaller vector and running the very high risk that the allocation will fail or be forced to fall back because of our lame fragmentation handling. Of course the Right Think To Do is kmalloc a vector of pages and mask the hash into it, but as a lazy person I would rather sink the time into writing this deathless prose.

The second patch is a rewrite of __dlm_lookup_lockres to get rid of the bogus clearing of tmpres on every loop iteration. I also threw in a little hand optimization, which gcc really ought to be doing but isn't. Comparing the first character of the string before doing the full memcmp seems to help measurably. I also tried to provide some more optimization guidance for the compiler, though I do fear it will fall on deaf ears. Finally, I cleaned up some stylistic oddities[3]. I also left one screaming lindent violation intact. Executive summary:
could you please install some editors that show whitespace? And what
is it with this one line per function parameter? After a few edits
of the function name you end up with a mess anyway so why not do as the romans do and stick to lindent style?

The __dlm_lookup_lockres rewrite shows a measurable improvement in hash chain traversal overhead. Every little bit helps. I failed to quantify the improvement precisely because there are other glitchy things going on that interfere with accurate measurement. So now we get to...

How fast is it now?
-------------------

Here is ocfs2 from yesterday's git:

Untar Sync
Trial Real User Sys Real User Sys
1. 31.42 24.90 3.81
2. 31.97 25.15 5.03 (similar to below)
3. 94.72 25.29 5.79
4. 26.27 0.28 4.43
5. 34.24 25.21 6.41
6. 50.71 25.26 7.23
7. 33.73 25.44 6.83

Here is what happens with the shiny new patches:

Untar Sync
Trial Real User Sys Real User Sys

1. 34.12 24.92 3.17 46.70 0.00 0.17
2. 29.63 24.96 3.36 47.25 0.00 0.16
3. 141.18 25.06 3.11 28.43 0.00 0.12
4. 45.20 25.38 3.07 49.04 0.00 0.18
5. 160.70 25.11 3.24 21.74 0.00 0.07
6. 31.65 24.99 3.34 46.30 0.00 0.19
7. 145.45 25.28 3.16 27.26 0.00 0.12
8. 30.87 25.16 3.29 44.60 0.00 0.20
9. 58.31 25.32 3.20 22.82 0.00 0.09
10. 31.01 25.29 3.09 43.93 0.00 0.22

Things to notice: with the still-teensy hash table, systime for global lock lookups is still way too high, eventually stabilizing when lock purging kicks in at about 4 times ext3's systime. Not good (but indeed, not as excruciatingly painful as two days ago).

With the attached patches we kill the hash table overhead dead, dead, dead. But look at real time for the untar and sync!

A) We have huge swings in idle time during the untar

B) We have great whacks of dirty memory sitting around after the untar

So that brings us to...

More performance bugs
---------------------

Ocfs2 starts little or no writeout during the untar itself. Ext3 does.
Solution: check ext3 to see what secret incantations Andrew conjured up to fiddle it into doing something reasonable.

Ocfs2 sometimes sits and gazes at its navel for minutes at a time, doing nothing at all. Timer bug? A quick glance at SysRq-t shows ocfs2 waiting in io_schedule. Waiting for io that never happens? This needs more investigation.

You also might want to look at more fine grained lock purging instead of the current burn the inbox approach. One can closely approximate the performance of a LRU without paying the penalty of a separate per-lock lru field by treating each hash chain as a LRU list. Here is the equation:
either the hash chains are short in which case you don't care about poor LRU behavior because you are not purging locks, or they are long and you do care. Luckily, the longer the hash chains get, the more closely they approximate the behavior of a dedicated LRU list. Amazing.

Delete performance remains horrible, even with a 256 meg journal[4] which is unconscionably big anyway. Compare to ext3, which deletes kernel trees at a steady 2 seconds per, with a much smaller journal. Ocfs2 takes more like a minute.

I would chase down these glitches too, except that I really need to get back to my cluster block devices, without which we cannot fully bake our cluster cake. After all, there are six of you and only one of me, I had better go work on the thing nobody else is working on.

[1] People would be much more interested in ocfs2 if they could get it running in less than a day, right? Well, you can, or at least you could if Oracle's startup scripts were ever so slightly less user hostile. For example, how about scripts/ocfs2 instead of vendor/common/o2cb.init? And it would be nice to expunge the evil of using lsmod to see if a subsystem is available. Also, an actual shared disk is not recommended for your first run. That way you avoid the pain of iscsi, nbd, fiber channel, etc al. (At least for a little while.) Once you get the init script insanity under control, ocfs2 comes up just like a normal filesystem on each node: mount -tocfs2.

[2] It is high time we pried loose the ocfs2 design process from secret irc channels and dark tunnels running deep beneath Oracle headquarters, and started sharing the squishy goodness of filesystem clustering development with some more of the smart people lurking here.

[3] Aha! I hear you cry, he wrote an 83 character line! Actually, I am going to blame the person who invented the name DLM_HASH_BUCKETS. Can you spot the superfluous redundancy? (Hint: name three other kinds of kernel objects that have buckets.)

[4] Could you please have fsck.ocfs2 report the size of the journal?

Patches apply to current linux-git.

Regards,

Daniel

[PATCH] Vmalloc ocfs global lock hash table and make it way bigger

fs/ocfs2/dlm/dlmcommon.h +2 -2
diff -urp 2.6.16.clean/fs/ocfs2/dlm/dlmcommon.h 2.6.16/fs/ocfs2/dlm/dlmcommon.h
@@ -36,8 +36,8 @@
  #define DLM_LOCK_RES_OWNER_UNKNOWN     O2NM_MAX_NODES
  #define DLM_THREAD_SHUFFLE_INTERVAL    5     // flush everything every 5 passes
  #define DLM_THREAD_MS                  200   // flush at least every 200 ms
-
-#define DLM_HASH_BUCKETS     (PAGE_SIZE / sizeof(struct hlist_head))
+#define DLM_HASH_SIZE		(1 << 20)
+#define DLM_HASH_BUCKETS	(DLM_HASH_SIZE / sizeof(struct hlist_head))
 
  enum dlm_ast_type {
  	DLM_AST = 0,
fs/ocfs2/dlm/dlmdomain.c +3 -3
diff -urp 2.6.16.clean/fs/ocfs2/dlm/dlmdomain.c 2.6.16/fs/ocfs2/dlm/dlmdomain.c
@@ -194,7 +191,7 @@ static int dlm_wait_on_domain_helper(con
  static void dlm_free_ctxt_mem(struct dlm_ctxt *dlm)
  {
  	if (dlm->lockres_hash)
-		free_page((unsigned long) dlm->lockres_hash);
+		vfree(dlm->lockres_hash);
 
  	if (dlm->name)
  		kfree(dlm->name);
@@ -1191,7 +1188,7 @@ static struct dlm_ctxt *dlm_alloc_ctxt(c
  		goto leave;
  	}
 
-	dlm->lockres_hash = (struct hlist_head *) __get_free_page(GFP_KERNEL);
+	dlm->lockres_hash = (struct hlist_head *)vmalloc(DLM_HASH_SIZE);
  	if (!dlm->lockres_hash) {
  		mlog_errno(-ENOMEM);
  		kfree(dlm->name);
@@ -1200,7 +1197,7 @@ static struct dlm_ctxt *dlm_alloc_ctxt(c
  		goto leave;
  	}
 
-	for (i=0; i<DLM_HASH_BUCKETS; i++)
+	for (i = 0; i < DLM_HASH_BUCKETS; i++)
  		INIT_HLIST_HEAD(&dlm->lockres_hash[i]);
 
  	strcpy(dlm->name, domain);

[PATCH] Clean up ocfs2 hash probe and make it faster

fs/ocfs2/dlm/dlmdomain.c +14 -17
diff -urp 2.6.16.clean/fs/ocfs2/dlm/dlmdomain.c 2.6.16/fs/ocfs2/dlm/dlmdomain.c
@@ -103,31 +103,28 @@ struct dlm_lock_resource * __dlm_lookup_
  					 const char *name,
  					 unsigned int len)
  {
-	unsigned int hash;
-	struct hlist_node *iter;
-	struct dlm_lock_resource *tmpres=NULL;
  	struct hlist_head *bucket;
+	struct hlist_node *list;
 
  	mlog_entry("%.*s\n", len, name);
 
  	assert_spin_locked(&dlm->spinlock);
+	bucket = dlm->lockres_hash + full_name_hash(name, len) % DLM_HASH_BUCKETS;
 
-	hash = full_name_hash(name, len);
+	hlist_for_each(list, bucket) {
+		struct dlm_lock_resource *res = hlist_entry(list,
+			struct dlm_lock_resource, hash_node);
 
-	bucket = &(dlm->lockres_hash[hash % DLM_HASH_BUCKETS]);
-
-	/* check for pre-existing lock */
-	hlist_for_each(iter, bucket) {
-		tmpres = hlist_entry(iter, struct dlm_lock_resource, hash_node);
-		if (tmpres->lockname.len == len &&
-		    memcmp(tmpres->lockname.name, name, len) == 0) {
-			dlm_lockres_get(tmpres);
-			break;
-		}
-
-		tmpres = NULL;
+		if (likely(res->lockname.name[0] != name[0]))
+			continue;
+		if (likely(res->lockname.len != len))
+			continue;
+		if (likely(memcmp(res->lockname.name + 1, name + 1, len - 1)))
+			continue;
+		dlm_lockres_get(res);
+		return res;
  	}
-	return tmpres;
+	return NULL;
  }
 
  struct dlm_lock_resource * dlm_lookup_lockres(struct dlm_ctxt *dlm,
#1 lore raw

Hi Daniel,

Quoted 7 lines · Daniel Phillips

Hi ocfs2 guys,

Actually, ocfs2 is not doomed - far from it! I just wanted to grab a few more of those eyeballs that normally glaze over each time they see a cluster mail run by on lkml[1]. Today's news: you are still not finished with global lock systime badness, and I already have more performance bugs for you.

Thanks for continuing to profile this stuff. We've definitely got lots of profiling to do, so any help is welcome.

Quoted 2 lines

So the ocfs2 guys switched from double word to single word hash table heads and quadrupled the size of the hash table. Problem solved, right? No!

Heh, well if you remember from irc I told you that there was more to do - specifically that I was looking at increasing the memory dedicated to the hash.

Quoted 5 lines

I included two patches below. The first vmallocs a megabyte hash table instead of a single page. This definitively squishes away the global lock hash table overhead so that systime stays about twice as high as ext3 instead of starting at three times and increasing to four times with the (new improved) 4K hash table.

I completely agree that we need to increase the memory dedicated to the hash, but I fear that vmallocing a 1 megabyte table per domain (effectively per mount) is going overboard. I will assume that this was a straw man patch :)

Quoted 3 lines

Of course the Right Think To Do is kmalloc a vector of pages and mask the hash into it, but as a lazy person I would rather sink the time into writing this deathless prose.

Right. That's one possible approach - I was originally thinking of allocating a large global lockres hash table allocated at module init time. This way we don't have to make large allocs for each domain.

Before anything else though, I'd really like to get an idea of how large we want things. This might very well dictate the severity of the solution.

Quoted 2 lines

The __dlm_lookup_lockres rewrite shows a measurable improvement in hash chain traversal overhead. Every little bit helps.

Yes, this patch seems much easier to swallow ;) Thanks for doing that work. I have some comments about it below.

Quoted 3 lines

I failed to quantify the improvement precisely because there are other glitchy things going on that interfere with accurate measurement. So now we get to...

Definitely if you get a chance to show how much just the lookup optimization helps, I'd like to know. I'll also try to gather some numbers.

Quoted 7 lines

Things to notice: with the still-teensy hash table, systime for global lock lookups is still way too high, eventually stabilizing when lock purging kicks in at about 4 times ext3's systime. Not good (but indeed, not as excruciatingly painful as two days ago).

With the attached patches we kill the hash table overhead dead, dead, dead. But look at real time for the untar and sync!

Indeed. The real time numbers are certainly confusing. I actually saw real time decrease on most of my tests (usually I hack things to increase the hash allocation to something like a few pages). I want to do some more consecutive untars though.

Btw, for what it's worth, here's some single untar numbers I have lying around. Sync numbers are basicaly the same.

Before the hlist patch:

    real    0m21.279s
    user    0m3.940s
    sys     0m18.884s

With the hlist patch:

    real    0m15.717s
    user    0m3.924s
    sys     0m13.324s
Quoted 3 lines

Ocfs2 starts little or no writeout during the untar itself. Ext3 does.
Solution: check ext3 to see what secret incantations Andrew conjured up to fiddle it into doing something reasonable.

Good idea. As you probably already know, we've never been beyond checking to see how ext3 handles a given problem :)

Quoted 4 lines

Ocfs2 sometimes sits and gazes at its navel for minutes at a time, doing nothing at all. Timer bug? A quick glance at SysRq-t shows ocfs2 waiting in io_schedule. Waiting for io that never happens? This needs more investigation.

Did you notice this during the untar? If not, do you have any reproducible test case?

Quoted 4 lines

Delete performance remains horrible, even with a 256 meg journal[4] which is unconscionably big anyway. Compare to ext3, which deletes kernel trees at a steady 2 seconds per, with a much smaller journal. Ocfs2 takes more like a minute.

This doesn't surprise me - our unlink performance leaves much to be desired at the moment. How many nodes did you have mounted when you ran that test? Off the top of my head,the two things which I would guess are hurting delete the most right now are node messaging and lack of directory read ahead. The first will be solved by more intelligent use of the DLM so that the network will only be hit for those nodes that actually care about a given inode -- unlink rename and mount/unmount are the only things left that still use the slower 'vote' mechanism. Directory readahead is much easier to solve, it's just that nobody has gotten around to fixing that yet :/ I bet there's more to figure out with respect to unlink performance.

Quoted 4 lines

I would chase down these glitches too, except that I really need to get back to my cluster block devices, without which we cannot fully bake our cluster cake. After all, there are six of you and only one of me, I had better go work on the thing nobody else is working on.

Hey, we appreciate the help so far - thanks.

Quoted 4 lines

[2] It is high time we pried loose the ocfs2 design process from secret irc channels and dark tunnels running deep beneath Oracle headquarters, and started sharing the squishy goodness of filesystem clustering development with some more of the smart people lurking here.

We're not trying to hide anything from anyone :) I'm always happy to talk about design. We've been in bugfix (and more recently, performance fix) mode for a while now, so there hasn't been much new design yet.

Quoted 6 lines
fs/ocfs2/dlm/dlmdomain.c +0 -5
-	bucket = &(dlm->lockres_hash[hash % DLM_HASH_BUCKETS]);
-
-	/* check for pre-existing lock */
-	hlist_for_each(iter, bucket) {
-		tmpres = hlist_entry(iter, struct dlm_lock_resource, 

hash_node);

fs/ocfs2/dlm/dlmdomain.c struct dlm_lock_resource * __dlm_lookup_ · line 118

Quoted 8 lines
fs/ocfs2/dlm/dlmdomain.c +1 -7
-		if (tmpres->lockname.len == len &&
-		    memcmp(tmpres->lockname.name, name, len) == 0) {
-			dlm_lockres_get(tmpres);
-			break;
-		}
-
-		tmpres = NULL;
+		if (likely(res->lockname.name[0] != name[0]))

Is the likely() here necessary? It actually surprises me that the check even helps so much - if you check the way OCFS2 lock names are built, the first few bytes are very regular - the first char is going to almost always be one of M, D, or W. Hmm, I guess if you're hitting it 1/3 fewer times...

fs/ocfs2/dlm/dlmdomain.c struct dlm_lock_resource * __dlm_lookup_ · line 120

Quoted 2 lines
fs/ocfs2/dlm/dlmdomain.c +2 -0
+			continue;
+		if (likely(res->lockname.len != len))

Also here, lengths of OCFS2 locks are also actually fairly regular, so perhaps the likely() isn't right?

	--Mark

--
Mark Fasheh
Senior Software Developer, Oracle
mark.fasheh at oracle.com

#2 lore raw
Quoted 4 lines · Mark Fasheh

I completely agree that we need to increase the memory dedicated to the hash, but I fear that vmallocing a 1 megabyte table per domain (effectively per mount) is going overboard. I will assume that this was a straw man patch :)

A meg's worth of vmalloc is a small price to pay for killing off the current gross cpu wastage. After that you get into various fiddling that really does not matter much compared to the next half dozen items on the sucks-most list.

Quoted 10 lines
Quoted 3 lines

Of course the Right Think To Do is kmalloc a vector of pages and mask the hash into it, but as a lazy person I would rather sink the time into writing this deathless prose.

Right. That's one possible approach - I was originally thinking of allocating a large global lockres hash table allocated at module init time. This way we don't have to make large allocs for each domain.

Before anything else though, I'd really like to get an idea of how large we want things. This might very well dictate the severity of the solution.

I made the table big enough to stomp the lookup overhead into insignificance up to the point your lock purging kicks in. If you want to adjust one you also want to adjust the other, they go together. As a rough rule of thumb, handling about 100,000 cached locks efficiently seems right to me. Eventually, somebody will want to handle way more or way less than that, but right now that requirement is pretty theoretical.

Quoted 6 lines
Quoted 3 lines

I failed to quantify the improvement precisely because there are other glitchy things going on that interfere with accurate measurement. So now we get to...

Definitely if you get a chance to show how much just the lookup optimization helps, I'd like to know. I'll also try to gather some numbers.

To test this I set the hash table size even lower than you originally had it and I think the simple-minded loop optimization improved throughput by some double digit's worth of percent. In other words, well worth the two line additional test.

Quoted 6 lines
Quoted 1 line

...look at real time for the untar and sync!

Indeed. The real time numbers are certainly confusing. I actually saw real time decrease on most of my tests (usually I hack things to increase the hash allocation to something like a few pages). I want to do some more consecutive untars though.

This is major badness, but who knows, it might not even be in ocfs2 itself. A lazy person might wait for the next point release before investigating further.

Quoted 7 lines
Quoted 4 lines

Ocfs2 sometimes sits and gazes at its navel for minutes at a time, doing nothing at all. Timer bug? A quick glance at SysRq-t shows ocfs2 waiting in io_schedule. Waiting for io that never happens? This needs more investigation.

Did you notice this during the untar? If not, do you have any reproducible test case?

During the untar. Very reproducible. Just untar a few kernel trees into different directories. I will try another kernel release first though, just in case this was a duh that has already been picked up.

Quoted 7 lines
Quoted 4 lines

Delete performance remains horrible, even with a 256 meg journal[4] which is unconscionably big anyway. Compare to ext3, which deletes kernel trees at a steady 2 seconds per, with a much smaller journal. Ocfs2 takes more like a minute.

This doesn't surprise me - our unlink performance leaves much to be desired at the moment. How many nodes did you have mounted when you ran that test?

One, on a local disk :-/

Quoted 8 lines

Off the top of my head,the two things which I would guess are hurting delete the most right now are node messaging and lack of directory read ahead. The first will be solved by more intelligent use of the DLM so that the network will only be hit for those nodes that actually care about a given inode -- unlink rename and mount/unmount are the only things left that still use the slower 'vote' mechanism. Directory readahead is much easier to solve, it's just that nobody has gotten around to fixing that yet :/ I bet there's more to figure out with respect to unlink performance.

I will watch you work on it with interest.

Quoted 6 lines
Quoted 4 lines

[2] It is high time we pried loose the ocfs2 design process from secret irc channels and dark tunnels running deep beneath Oracle headquarters, and started sharing the squishy goodness of filesystem clustering development with some more of the smart people lurking here.

We're not trying to hide anything from anyone :)

I wasn't implying that, but it's a fact that most of the ocfs2 discussion happens offline, and I completely understand how easy it is to settle into that pattern. But by so doing, we are really cheating the community of part of the benefit of having an open source community in the first place, which to be able to watch the development process in real time and learn from it. Not to mention creating a better historical record and - need I mention it - a googleable database of development strategies.

Quoted 3 lines

I'm always happy to talk about design. We've been in bugfix (and more recently, performance fix) mode for a while now, so there hasn't been much new design yet.

Fortunately, it seems that the core design is pretty solid already. I'd add that a main goal at this point should be to explain as much as possible of the internals to outsiders, and I certainly include myself in that at this point. Please use one syllable words where possible :-)

Quoted 6 lines

fs/ocfs2/dlm/dlmdomain.c struct dlm_lock_resource * __dlm_lookup_ · line 118

Quoted 1 line
fs/ocfs2/dlm/dlmdomain.c +1 -0
+		if (likely(res->lockname.name[0] != name[0]))

Is the likely() here necessary? It actually surprises me that the check even helps so much - if you check the way OCFS2 lock names are built, the first few bytes are very regular - the first char is going to almost always be one of M, D, or W. Hmm, I guess if you're hitting it 1/3 fewer times...

Sure, you can improve the test by knowing more about the distribution, which is prefectly fair because this function does not to be very general. To tell the truth, I did not check to see which of my hacks sped things up. I was more interested in just reorganizing it to make it easier to optimize. You could check the second byte or first word
or whatever.

The likely itself is correct though: if the hash chains are short then you don't care, and if they are long then the early fail is certainly most likely. What I didn't check is if gcc is even smart enough to unroll the loop the correct way to eliminate some jumps. It would be easy to unroll this loop by hand a few iterations to test that.

Quoted 5 lines

fs/ocfs2/dlm/dlmdomain.c struct dlm_lock_resource * __dlm_lookup_ · line 120

Quoted 2 lines
fs/ocfs2/dlm/dlmdomain.c +2 -0
+			continue;
+		if (likely(res->lockname.len != len))

Also here, lengths of OCFS2 locks are also actually fairly regular, so perhaps the likely() isn't right?

Yes, that one is questionable. Maybe:

    if (likely((res->lockname.name[0] ^ name[0]) | (res->lockname.len ^ len)))

which modern processors should parallelize very nicely.

At this point it might be a good idea to step back and let some micro-optimization mavens lurking here have a go at it. Even a tiny optimization in this inner loop is a major performance win.

Regards,

Daniel

#3 lore raw
In reply to Daniel Phillips
Quoted 7 lines · Daniel Phillips
fs/ocfs2/dlm/dlmdomain.c +0 -0
@@ -103,31 +103,28 @@ struct dlm_lock_resource * __dlm_lookup_
   					 const char *name,
   					 unsigned int len)
   {
 -	unsigned int hash;
 -	struct hlist_node *iter;

fs/ocfs2/dlm/dlmdomain.c struct dlm_lock_resource * __dlm_lookup_ · line 117

Quoted 10 lines
fs/ocfs2/dlm/dlmdomain.c +0 -0
 -	struct dlm_lock_resource *tmpres=NULL;
   	struct hlist_head *bucket;
 +	struct hlist_node *list;
 
   	mlog_entry("%.*s\n", len, name);
 
   	assert_spin_locked(&dlm->spinlock);
 +	bucket = dlm->lockres_hash + full_name_hash(name, len) % DLM_HASH_BUCKETS;
 
 -	hash = full_name_hash(name, len);

err, you might want to calculate that hash outside the spinlock.

Maybe have a lock per bucket, too.

A 1MB hashtable is verging on comical. How may data are there in total?

#4 lore raw
Quoted 3 lines · Andrew Morton
Quoted 1 line

- hash = full_name_hash(name, len);

err, you might want to calculate that hash outside the spinlock.

Hmm, good catch.

Quoted 1 line

Maybe have a lock per bucket, too.

That could be an avenue to explore. I guess we probably want to optimize the actual lookup and memory usage before looking at that.

Quoted 1 line

A 1MB hashtable is verging on comical. How may data are there in total?

Yes 1MB is much too big. We're looking right now at 3 lock resources per inode, so total number of elements depends upon your file system I suppose. Hopefully I'll have some time today to run some basic tests which may show us what size strikes a better balance of performance versus memory overhead.

	--Mark

--
Mark Fasheh
Senior Software Developer, Oracle
mark.fasheh at oracle.com

#5 lore raw
In reply to Andrew Morton
Quoted 7 lines · Andrew Morton

fs/ocfs2/dlm/dlmdomain.c struct dlm_lock_resource * __dlm_lookup_ · line 115

Quoted 4 lines · Daniel Phillips
  	assert_spin_locked(&dlm->spinlock);
fs/ocfs2/dlm/dlmdomain.c +1 -1
+	bucket = dlm->lockres_hash + full_name_hash(name, len) % DLM_HASH_BUCKETS;
 
-	hash = full_name_hash(name, len);

err, you might want to calculate that hash outside the spinlock.

Yah.

Quoted 1 line

Maybe have a lock per bucket, too.

So the lock memory is as much as the hash table? ;-)

Quoted 1 line

A 1MB hashtable is verging on comical. How may data are there in total?

Even with the 256K entry hash table, __dlm_lookup_lockres is still the top systime gobbler:

-------------
real 31.01
user 25.29
sys 3.09
-------------

CPU: P4 / Xeon, speed 2793.37 MHz (estimated)
Counted GLOBAL_POWER_EVENTS events (time during which processor is not stopped) with a unit mask of 0x01 (mandatory) count 240000
samples % image name app name symbol name
-------------------------------------------------------------------------------
17071831 71.2700 libbz2.so.1.0.2 libbz2.so.1.0.2 (no symbols)
17071831 100.000 libbz2.so.1.0.2 libbz2.so.1.0.2 (no symbols) [self]
-------------------------------------------------------------------------------
2638066 11.0132 vmlinux vmlinux __dlm_lookup_lockres
2638066 100.000 vmlinux vmlinux __dlm_lookup_lockres [self]
-------------------------------------------------------------------------------
332683 1.3889 oprofiled oprofiled (no symbols)
332683 100.000 oprofiled oprofiled (no symbols) [self]
-------------------------------------------------------------------------------
254736 1.0634 vmlinux vmlinux ocfs2_local_alloc_count_bits
254736 100.000 vmlinux vmlinux ocfs2_local_alloc_count_bits [self]
-------------------------------------------------------------------------------
176794 0.7381 tar tar (no symbols)
176794 100.000 tar tar (no symbols) [self]
-------------------------------------------------------------------------------

Note, this is uniprocessor, single node on a local disk. Something pretty badly broken all right. Tomorrow I will take a look at the hash distribution and see what's up.

I guess there are about 250k symbols in the table before purging finally kicks in, which happens 5th or 6th time I untar a kernel tree. So, 20,000 names times 5-6 times the three locks per inode Mark mentioned. I'll actually measure that tomorrow instead of inferring it.

I think this table is per-ocfs2-mount, and really really, a meg is nothing if it makes CPU cycles go away. That's .05% of the memory on this box, which is a small box where clusters are concerned. But there is also some gratuitous cpu suck still happening in there that needs investigating. I would not be surprised at all to learn that full_name_hash is a terrible hash function.

Regards,

Daniel

#6 lore raw
Quoted 10 lines · Daniel Phillips

Note, this is uniprocessor, single node on a local disk. Something pretty badly broken all right. Tomorrow I will take a look at the hash distribution and see what's up.

I guess there are about 250k symbols in the table before purging finally kicks in, which happens 5th or 6th time I untar a kernel tree. So, 20,000 names times 5-6 times the three locks per inode Mark mentioned. I'll actually measure that tomorrow instead of inferring it.

Quoted 6 lines

I think this table is per-ocfs2-mount, and really really, a meg is nothing if it makes CPU cycles go away. That's .05% of the memory on this box, which is a small box where clusters are concerned. But there is also some gratuitous cpu suck still happening in there that needs investigating. I would not be surprised at all to learn that full_name_hash is a terrible hash function.

Can you try the attached patch? Here's a sample OCFS2 lock name:

M0000000000000000036cc0458354c5

So as you can see, things at the beginning of the name are very regular - something that I don't think full_name_hash() is handling very well. I hacked a (barely) new hash function to avoid the first 7 bytes and it reliably saves me 2 seconds in real time on my untars. I think we can actually make it much better (this is still pretty dumb) than that, but I'm just curious as to how much it helps on your tests.

fs/ocfs2/dlm/dlmdomain.c +11 -2
index 8f3a9e3..06cebb2 100644
@@ -81,6 +81,15 @@ void __dlm_unhash_lockres(struct dlm_loc
 	dlm_lockres_put(lockres);
 }
 
+static inline unsigned int
+dlm_name_hash(const unsigned char *name, unsigned int len)
+{
+	/* optimize for OCFS2 lock names */
+	if (len > 7)
+		return full_name_hash(&name[7], len - 7);
+	return full_name_hash(name, len);
+}
+
 void __dlm_insert_lockres(struct dlm_ctxt *dlm,
 		       struct dlm_lock_resource *res)
 {
@@ -90,7 +99,7 @@ void __dlm_insert_lockres(struct dlm_ctx
 	assert_spin_locked(&dlm->spinlock);
 
 	q = &res->lockname;
-	q->hash = full_name_hash(q->name, q->len);
+	q->hash = dlm_name_hash(q->name, q->len);
 	bucket = &(dlm->lockres_hash[q->hash % DLM_HASH_BUCKETS]);
 
 	/* get a reference for our hashtable */
@@ -112,7 +121,7 @@ struct dlm_lock_resource * __dlm_lookup_
 
 	assert_spin_locked(&dlm->spinlock);
 
-	hash = full_name_hash(name, len);
+	hash = dlm_name_hash(name, len);
 
 	bucket = &(dlm->lockres_hash[hash % DLM_HASH_BUCKETS]);
 
#7 lore raw
Quoted 9 lines · Mark Fasheh
Quoted 6 lines · Daniel Phillips

I think this table is per-ocfs2-mount, and really really, a meg is nothing if it makes CPU cycles go away. That's .05% of the memory on this box, which is a small box where clusters are concerned. But there is also some gratuitous cpu suck still happening in there that needs investigating. I would not be surprised at all to learn that full_name_hash is a terrible hash function.

Can you try the attached patch?

With patch:

     Real  User  Sys
    31.93 23.72 3.69
    29.39 24.18 4.01
    53.36 24.25 4.80
    30.24 24.40 4.76
    63.60 24.09 5.03
    29.95 24.18 4.91

Without patch:

     Real  User  Sys
    30.15 23.90 3.58
    54.99 24.38 4.56
    31.49 24.63 5.28
    60.09 24.71 5.47
    31.44 24.34 5.72
    65.36 24.31 5.84

So that hack apparently improves the bucket distribution quite a bit, but look, the bad old linear systime creep is still very obvious. For that there is no substitute for lots of buckets.

The hash function can be improved way more. Your resource encoding is also painfully wasteful.

As for optimizing the loop... most of the loop overhead comes from loading cold cache lines no doubt. The struct qstr is an impediment there because it adds another cache line to every loop. Speaking of that, the qstr is so far away from the list.next pointer that you're most probably getting an extra cache line load there too. Just move the qstr up next to the hash list.

Notice, those wildly gyrating real times are still manifesting. Seen them over there?

Regards,

Daniel

#8 lore raw
Quoted 3 lines · Daniel Phillips

So that hack apparently improves the bucket distribution quite a bit, but look, the bad old linear systime creep is still very obvious. For that there is no substitute for lots of buckets.

Yes, I think the way to go right now is to allocate an array of pages and index into that. We can make the array size a mount option so that the default can be something reasonable ;)

Quoted 3 lines

Speaking of that, the qstr is so far away from the list.next pointer that you're most probably getting an extra cache line load there too. Just move the qstr up next to the hash list.

Ahh, good catch.

Quoted 2 lines

Notice, those wildly gyrating real times are still manifesting. Seen them over there?

Yes - times from a test run are below.

Real User Sys
14.35 3.82 11.99
16.75 3.62 13.90
32.12 4.06 15.81
18.94 3.99 16.69
35.18 3.96 15.80
18.66 3.89 16.44
52.09 4.24 16.66
21.25 3.85 17.09
19.73 4.00 17.20
35.40 3.88 16.60

So this definitely reproduces elsewhere.

	--Mark

--
Mark Fasheh
Senior Software Developer, Oracle
mark.fasheh at oracle.com

#9 lore raw
Quoted 7 lines · Mark Fasheh
Quoted 3 lines · Daniel Phillips

So that hack apparently improves the bucket distribution quite a bit, but look, the bad old linear systime creep is still very obvious. For that there is no substitute for lots of buckets.

Yes, I think the way to go right now is to allocate an array of pages and index into that. We can make the array size a mount option so that the default can be something reasonable ;)

Did you actually do some statistics how long the hash chains are? Just increasing hash tables blindly has other bad side effects, like increasing cache misses.

-Andi

#10 lore raw
Quoted 3 lines · Andi Kleen

Did you actually do some statistics how long the hash chains are? Just increasing hash tables blindly has other bad side effects, like increasing cache misses.

Yep, the gory details are at:

http://oss.oracle.com/~mfasheh/lock_distribution.csv

This measure was taken about 18,000 locks into a kernel untar. The only change was that I switched things to only hash the last 18 characters of lock resource names.

In short things aren't so bad that a larger hash table wouldn't help. We've definitely got some peaks however. Our in-house laboratory of mathematicians (read: Bill Irwin) is checking out methods by which we can smooth things out a bit more :)

	--Mark

--
Mark Fasheh
Senior Software Developer, Oracle
mark.fasheh at oracle.com

#11 lore raw
Quoted 6 lines · Mark Fasheh
Quoted 3 lines · Andi Kleen

Did you actually do some statistics how long the hash chains are? Just increasing hash tables blindly has other bad side effects, like increasing cache misses.

Quoted 7 lines

Yep, the gory details are at:

http://oss.oracle.com/~mfasheh/lock_distribution.csv

This measure was taken about 18,000 locks into a kernel untar. The only change was that I switched things to only hash the last 18 characters of lock resource names.

Eventually you will realize how much those bloated lock resource names cost in CPU and change them to a binary encoding.

Quoted 4 lines

In short things aren't so bad that a larger hash table wouldn't help. We've definitely got some peaks however. Our in-house laboratory of mathematicians (read: Bill Irwin) is checking out methods by which we can smooth things out a bit more :)

Twould be a shame to invest a lot of effort hashing those horrible strings before finally realizing the strings themselves should be gotten rid of, and have to optimize the hash all over again.

Since the hash table won't fit in cache except on the beefiest of machines, the right hash chain length to aim for is one. That requires both good a hash function and big hash table. A sane resource encoding would also help.

Chestnut for the day: don't get too obsessed about optimizing for the light load case. A cluster filesystem is supposed to be a beast of burden. It needs big feet.

Regards,

Daniel

#12 lore raw
In reply to Mark Fasheh
Quoted 8 lines · Mark Fasheh
Quoted 3 lines · Andi Kleen

Did you actually do some statistics how long the hash chains are? Just increasing hash tables blindly has other bad side effects, like increasing cache misses.

Yep, the gory details are at:

http://oss.oracle.com/~mfasheh/lock_distribution.csv

Hi Mark,

I don't know how you got your statistics, but I went to the bother of writing a proc interface to dump the bucket counts. Mostly to try out the seq_file interface, though it turned into something more of a tour through the slimy unberbelly of seq_read. (This patch includes surgery for one of the several bunions I found there - seq_read failed to distinguish between "buffer full" and "buffer overrun", expanding the buffer unnecessarily in the former case). This also includes my simple-minded big hash table code, with a 256K table size this time.

This proc interface always names itself /proc/ocfs2hash (a bug if you create more than one lockspace). It gives the chain length as a uint32_t per bucket.

Dump the buckets like this:

    cat /proc/ocfs2hash | hexdump -e'32 " %1.1X" "\n"'

To total the buckets:

    cat /proc/ocfs2hash | hexdump -v -e'"%1.1d\n"' | awk '{sum += $1} END {print "Total: ", sum;}'

After untarring four kernel trees, number of locks hits a peak of 128K. With 64K buckets the hash, a typical region of the table looks like:

3 0 3 6 1 2 2 1 2 6 1 0 1 2 1 0 0 3 1 2 2 3 1 2 5 3 2 2 1 0 3 1 1 1 3 5 2 2 1 0 2 3 3 1 3 0 5 2 2 3 0 2 1 3 1 2 4 2 0 2 5 1 4 3 5 3 3 3 3 1 4 1 2 1 2 6 2 1 3 0 2 2 2 8 1 2 2 2 3 1 0 1 3 2 1 1 1 2 2 2 2 3 2 0 2 2 2 5 2 3 2 1 1 2 6 6 1 2 2 4 2 0 3 0 3 3 3 0 2 2 1 1 2 3 2 0 2 3 3 1 3 3 3 1 4 2 8 3 2 2 2 4 3 0 1 2 3 4 2 0 3 1 0 1 2 2 3 1 4 2 1 1 3 3 4 3 3 3 4 2 1 4 2 1 5 2 1 3 1 2 3 2 1 0 1 5 3 2 1 2 3 0 1 1 2 3 4 4 4 1 3 1 4 3 2 2 4 4 1 3 1 0 0 1 3 1 1 3 0 3 0 1 1 1 1 1 3 4 4 2 4 3 4 2 3 3 0 3 4 2 1 5 4 1 3 1 1 0 1 0 1 4 1 2 1 4 2 0 2 2 5 2 1 1 1 2 3 6 4 5 5 1 1 2 3 1 5 1 3 0 1 0 3 3 2 0 2 1 2 1 0 4 3 2 1 0 1 0 2 7 1 3 2 1 1 2 4 1 3 1 2 2 3 1 3 3 1 2 0 2 1 3 1 2 0 4 4 1 2 1 2 3 3 6 0 5 2 1 1 0 3 0 1 0 2 0 4 3 2 1 0 0 2 0 1 4 2 4 5 1 0 1 3 2 2 1 1 3 2 3 0 2 1 1 3 0 0 0 2 5 3 1 0 2 0 1 0 0 2 0 4 2 1 2 4 3 0 1 2 4 1 3 0 0 1 4

A poor distribution as you already noticed[1]. Even if it was a great distribution, we would still average a little over two nodes per bucket twice as many as we should allow unless you believe that people running cluster filesystems have too much time on their hands and need to waste some of it waiting for the computer to chew its way through millions of cold cache lines.

So if we improve the hash function, 128K buckets (512K table size) is the right number, given a steady-state number of hash resources around 128K. This is pretty much independent of load: if you run light loads long enough, you will eventually fill up the hash table. Of course, if we take a critical look at your locking strategy we might find some fat to cut there too. Could I possibly interest you in writing up a tech note on your global locking strategy?

[1] And this is our all-important dentry hash function. Oops.

Regards,

Daniel

fs/ocfs2/dlm/dlmcommon.h +2 -2
diff -urp 2.6.16.clean/fs/ocfs2/dlm/dlmcommon.h 2.6.16/fs/ocfs2/dlm/dlmcommon.h
@@ -36,8 +36,8 @@
  #define DLM_LOCK_RES_OWNER_UNKNOWN     O2NM_MAX_NODES
  #define DLM_THREAD_SHUFFLE_INTERVAL    5     // flush everything every 5 passes
  #define DLM_THREAD_MS                  200   // flush at least every 200 ms
-
-#define DLM_HASH_BUCKETS     (PAGE_SIZE / sizeof(struct hlist_head))
+#define DLM_HASH_SIZE		(1 << 18)
+#define DLM_HASH_BUCKETS	(DLM_HASH_SIZE / sizeof(struct hlist_head))
 
  enum dlm_ast_type {
  	DLM_AST = 0,
fs/ocfs2/dlm/dlmdomain.c +86 -2

124 lines not on this page · raw message

fs/seq_file.c +19 -16
diff -urp 2.6.16.clean/fs/seq_file.c 2.6.16/fs/seq_file.c
@@ -106,18 +106,17 @@ ssize_t seq_read(struct file *file, char
  		if (!size)
  			goto Done;
  	}
+expand:
  	/* we need at least one record in buffer */
-	while (1) {
-		pos = m->index;
-		p = m->op->start(m, &pos);
-		err = PTR_ERR(p);
-		if (!p || IS_ERR(p))
-			break;
-		err = m->op->show(m, p);
-		if (err)
-			break;
-		if (m->count < m->size)
-			goto Fill;
+	pos = m->index;
+	p = m->op->start(m, &pos);
+	err = PTR_ERR(p);
+	if (!p || IS_ERR(p))
+		goto Errstop;
+
+	err = m->op->show(m, p);
+
+	if (err == -1) {
  		m->op->stop(m, p);
  		kfree(m->buf);
  		m->buf = kmalloc(m->size <<= 1, GFP_KERNEL);
@@ -125,12 +124,12 @@ ssize_t seq_read(struct file *file, char
  			goto Enomem;
  		m->count = 0;
  		m->version = 0;
+		goto expand;
  	}
-	m->op->stop(m, p);
-	m->count = 0;
-	goto Done;
-Fill:
-	/* they want more? let's try to get some more */
+
+	if (err)
+		goto Errstop;
+
  	while (m->count < size) {
  		size_t offs = m->count;
  		loff_t next = pos;
@@ -172,6 +171,10 @@ Enomem:
  Efault:
  	err = -EFAULT;
  	goto Done;
+Errstop:
+	m->op->stop(m, p);
+	m->count = 0;
+	goto Done;
  }
  EXPORT_SYMBOL(seq_read);
#13 lore raw
Quoted 7 lines · Daniel Phillips

A poor distribution as you already noticed[1]. Even if it was a great distribution, we would still average a little over two nodes per bucket twice as many as we should allow unless you believe that people running cluster filesystems have too much time on their hands and need to waste some of it waiting for the computer to chew its way through millions of cold cache lines.

Just interested: do the locks have any sort of locality of lookup? If so, then have you tried moving hot (ie. the one you've just found, or newly inserted) hash entries to the head of the hash list?

In applications with really good locality you can sometimes get away with small hash tables (10s even 100s of collisions on average) without taking too big a hit this way, because your entries basically get sorted LRU for you.

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
#14 lore raw
Quoted 8 lines · Nick Piggin

Just interested: do the locks have any sort of locality of lookup? If so, then have you tried moving hot (ie. the one you've just found, or newly inserted) hash entries to the head of the hash list?

In applications with really good locality you can sometimes get away with small hash tables (10s even 100s of collisions on average) without taking too big a hit this way, because your entries basically get sorted LRU for you.

LRU hashes have really bad cache behaviour though if that is not the case because you possibily need to bounce around the hash heads as DIRTY cache lines instead of keeping them in SHARED state.
My feeling would be that scalability is more important for this, which would discourage this.

-Andi

#15 lore raw
Quoted 13 lines · Andi Kleen
Quoted 8 lines · Nick Piggin

Just interested: do the locks have any sort of locality of lookup? If so, then have you tried moving hot (ie. the one you've just found, or newly inserted) hash entries to the head of the hash list?

In applications with really good locality you can sometimes get away with small hash tables (10s even 100s of collisions on average) without taking too big a hit this way, because your entries basically get sorted LRU for you.

Quoted 6 lines

LRU hashes have really bad cache behaviour though if that is not the case because you possibily need to bounce around the hash heads as DIRTY cache lines instead of keeping them in SHARED state.
My feeling would be that scalability is more important for this, which would discourage this.

That's true, it would have to have very good locality of reference to be of use. In that case it is not always going to dirty the cachelines because you now only have to make your hash table size appropriate for your _working set_ rather than the entire set - if the working set is small enough and you make your hash say 4 times bigger than it, then you might expect to often hit the right lock at the head of the list.

The other thing is: if the alternative is a 1MB hash, then that may result in more capacity cache misses than invalidate misses. Not to mention TLB misses if it is vmalloced :(

Anyway you're absolutely right -- this is only going to work under select types of hash loads, so lots of testing would be required.

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
#16 lore raw
Quoted 24 lines · Nick Piggin
Quoted 14 lines · Andi Kleen
Quoted 8 lines · Nick Piggin

Just interested: do the locks have any sort of locality of lookup? If so, then have you tried moving hot (ie. the one you've just found, or newly inserted) hash entries to the head of the hash list?

In applications with really good locality you can sometimes get away with small hash tables (10s even 100s of collisions on average) without taking too big a hit this way, because your entries basically get sorted LRU for you.

Quoted 7 lines

LRU hashes have really bad cache behaviour though if that is not the case because you possibily need to bounce around the hash heads as DIRTY cache lines instead of keeping them in SHARED state.
My feeling would be that scalability is more important for this, which would
discourage this.

Quoted 7 lines

That's true, it would have to have very good locality of reference to be of use. In that case it is not always going to dirty the cachelines because you now only have to make your hash table size appropriate for your _working set_ rather than the entire set - if the working set is small enough and you make your hash say 4 times bigger than it, then you might expect to often hit the right lock at the head of the list.

OTOH, I suspect it actually isn't all that bad. There is already a shared lock there, which will definitely have its cacheline invalidated.

So adding an extra cacheline bounce is not like the bad problem of going from perfect scalability (no shared cachelines) to a single shared cacheline.

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
#17 lore raw
In reply to Daniel Phillips
Quoted 18 lines · Daniel Phillips

After untarring four kernel trees, number of locks hits a peak of 128K. With 64K buckets the hash, a typical region of the table looks like:

3 0 3 6 1 2 2 1 2 6 1 0 1 2 1 0 0 3 1 2 2 3 1 2 5 3 2 2 1 0 3 1 1 1 3 5 2 2 1 0 2 3 3 1 3 0 5 2 2 3 0 2 1 3 1 2 4 2 0 2 5 1 4 3 5 3 3 3 3 1 4 1 2 1 2 6 2 1 3 0 2 2 2 8 1 2 2 2 3 1 0 1 3 2 1 1 1 2 2 2 2 3 2 0 2 2 2 5 2 3 2 1 1 2 6 6 1 2 2 4 2 0 3 0 3 3 3 0 2 2 1 1 2 3 2 0 2 3 3 1 3 3 3 1 4 2 8 3 2 2 2 4 3 0 1 2 3 4 2 0 3 1 0 1 2 2 3 1 4 2 1 1 3 3 4 3 3 3 4 2 1 4 2 1 5 2 1 3 1 2 3 2 1 0 1 5 3 2 1 2 3 0 1 1 2 3 4 4 4 1 3 1 4 3 2 2 4 4 1 3 1 0 0 1 3 1 1 3 0 3 0 1 1 1 1 1 3 4 4 2 4 3 4 2 3 3 0 3 4 2 1 5 4 1 3 1 1 0 1 0 1 4 1 2 1 4 2 0 2 2 5 2 1 1 1 2 3 6 4 5 5 1 1 2 3 1 5 1 3 0 1 0 3 3 2 0 2 1 2 1 0 4 3 2 1 0 1 0 2 7 1 3 2 1 1 2 4 1 3 1 2 2 3 1 3 3 1 2 0 2 1 3 1 2 0 4 4 1 2 1 2 3 3 6 0 5 2 1 1 0 3 0 1 0 2 0 4 3 2 1 0 0 2 0 1 4 2 4 5 1 0 1 3 2 2 1 1 3 2 3 0 2 1 1 3 0 0 0 2 5 3 1 0 2 0 1 0 0 2 0 4 2 1 2 4 3 0 1 2 4 1 3 0 0 1 4

A poor distribution as you already noticed[1].

[...]

Quoted 1 line

[1] And this is our all-important dentry hash function. Oops.

Why do you say that? I don't think it is particularly bad. Your sample has an average of 2.06, and a standard deviation of 1.49 while a random assignment using glibc's random() here has a standard deviation of 1.44

I can't remember much stats, but I think that means in your sample of over 400, you're likely to find several instances of "6" and not unlikely to find some higher. Actually given that it is bound at zero and so not a normal distribution, that is likely to move results a bit further to the right [I'm sure there's a formula for that], which is pretty consistent with what you have, and you would hardly notice a difference using rand()

Signature · 2 lines
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com 
#18 lore raw

Re: [Ocfs2-devel] Ocfs2 performance

In reply to Daniel Phillips

E-mail subject line change, because the old one has worn thin ;)

Quoted 2 lines · Daniel Phillips

I don't know how you got your statistics, but I went to the bother of writing a proc interface to dump the bucket counts.

The initial set of numbers I posted was collected by hacking the dlm to dump bucket lengths at about 20,000 locks. I have since written some user space code to model the dlm hash and output chain lengths. This allowed me to test hash distributions at a rapid rate. As a data set, I used debugfs.ocfs2 to collect lock names from a file system with a fully untarred kernel tree. The program outputs in a format suitable for import into gnuplot. If interested, you can get the program and a sample data set from:

http://oss.oracle.com/~mfasheh/dlm_hash/distribution_modeling/

Standard disclaimers apply - that code is a hack and wasn't edited to be particularly performant, error resistant or pretty. It's also clearly not intended for testing the actual performance of the hash (just distribution output). Anyway, it turns out that full_name_hash() didn't have the severe spikes in distribution that my original hack to compare only the last parts of a lockres name had. This makes it inappropriate for general use, even though it resulted in a performance gain on our micro-benchmark.

Quoted 4 lines

So if we improve the hash function, 128K buckets (512K table size) is the right number, given a steady-state number of hash resources around 128K. This is pretty much independent of load: if you run light loads long enough, you will eventually fill up the hash table.

Your hash sizes are still ridiculously large. All my data shows that we need to increase the hash size by much much less. At the following location you will find a series of files detailing the results of 10 untar runs with various hash allocations. The short story is that we really only need an allocation on the order of a few pages.

http://oss.oracle.com/~mfasheh/dlm_hash/untar_timings/

If you average up the untar times you'll get something close to this:

1 page:   23 seconds
2 pages:  18 seconds
4 pages:  16 seconds
6 pages:  15 seconds
8 pages:  14 seconds

16 pages: 14 seconds
32 pages: 14 seconds
64 pages: 14 seconds

PAGE_SIZE on this system is 4096

So our largest performance gain is by just adding a page, and things seem to top out at 6-8 pages. I will likely have a patch in the next few days or so which will allocate a small array of pages at dlm startup. The bottom line is that the default is extremely likely to be on the order of a few pages. Eventually this will also be user configurable.

Quoted 3 lines

Of course, if we take a critical look at your locking strategy we might find some fat to cut there too. Could I possibly interest you in writing up a tech note on your global locking strategy?

Sure, but it'll take a while. I've already got one OCFS2 related paper to write. Perhaps I'll be able to kill two birds with one stone.

By the way, an interesting thing happened when I recently switched disk arrays - the fluctuations in untar times disappeared. The new array is much nicer, while the old one was basically Just A Bunch Of Disks. Also, sync times dropped dramatically.

	--Mark

--
Mark Fasheh
Senior Software Developer, Oracle
mark.fasheh at oracle.com

#19 lore raw

Re: [Ocfs2-devel] Ocfs2 performance

Quoted 1 line · Mark Fasheh

Your hash sizes are still ridiculously large.

How long are those entries in the buckets kept? I mean if I untar a tree the files are only locked while extracted, afterwards they are owner-less... (I must admint I dont understand ocfs2 very deeply, but maybe explaining why so many active locks need to be cached might help to find an optimized way.

Quoted 4 lines

By the way, an interesting thing happened when I recently switched disk arrays - the fluctuations in untar times disappeared. The new array is much nicer, while the old one was basically Just A Bunch Of Disks. Also, sync times dropped dramatically.

Writeback Cache?

Gruss
Bernd

#20 lore raw

Re: [Ocfs2-devel] Ocfs2 performance

Please don't drop the ocfs2-devel Cc: I'm bouncing this there.

Quoted 22 lines · Bernd Eckenfels
Quoted 1 line · Mark Fasheh

Your hash sizes are still ridiculously large.

How long are those entries in the buckets kept? I mean if I untar a tree the files are only locked while extracted, afterwards they are owner-less... (I must admint I dont understand ocfs2 very deeply, but maybe explaining why so many active locks need to be cached might help to find an optimized way.

Quoted 4 lines

By the way, an interesting thing happened when I recently switched disk arrays - the fluctuations in untar times disappeared. The new array is much nicer, while the old one was basically Just A Bunch Of Disks. Also, sync times dropped dramatically.

Writeback Cache?

Gruss
Bernd
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo at vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

Signature · 9 lines
"Depend on the rabbit's foot if you will, but remember, it didn't
 help the rabbit."
	- R. E. Shay

Joel Becker
Principal Software Developer
Oracle
E-mail: joel.becker at oracle.com
Phone: (650) 506-8127
#21 lore raw

Re: [Ocfs2-devel] Ocfs2 performance

In reply to Bernd Eckenfels
Quoted 4 lines · Bernd Eckenfels
Quoted 1 line · Mark Fasheh

Your hash sizes are still ridiculously large.

How long are those entries in the buckets kept?

Shortly after the inode is destroyed. Basically the entries are "lock resources" which the DLM tracks. OCFS2 only ever gets lock objects attached to those resources. In OCFS2 the lock objects obey inode lifetimes. So the DLM can't purge the lock resources until OCFS2 destroys the inode, etc. If other nodes take locks on that resource and your local node is the "master" (as in, arbitrates access to the resource) it may stay around longer.

Quoted 4 lines

I mean if I untar a tree the files are only locked while extracted, afterwards they are owner-less... (I must admint I dont understand ocfs2 very deeply, but maybe explaining why so many active locks need to be cached might help to find an optimized way.

Well, OCFS2 caches locks. That is, once you've gone to the DLM to acquire a lock at a given level, OCFS2 will just hold onto it and manage access to it until the locks needs to be upgraded or downgraded. This provides a very large performance increase over always asking the DLM for a new lock. Anyway, at the point that we've acquired the lock the first time, the file system isn't really forcing the dlm to hit the hash much.

Quoted 6 lines
Quoted 4 lines

By the way, an interesting thing happened when I recently switched disk arrays - the fluctuations in untar times disappeared. The new array is much nicer, while the old one was basically Just A Bunch Of Disks. Also, sync times dropped dramatically.

Writeback Cache?

Yep, and a whole slew of other nice features :)

	--Mark

--
Mark Fasheh
Senior Software Developer, Oracle
mark.fasheh at oracle.com

#22 lore raw

Re: [Ocfs2-devel] Ocfs2 performance

Quoted 2 lines · Mark Fasheh

until the locks needs to be upgraded or downgraded. This provides a very large performance increase over always asking the DLM for a new lock.

Yes, it is basically the same problem as the buffer cache. Excessive single-use patterns dirty the small cache or require a too big cache to be usefull.

Maybe a user specific limit of percentage of hash (and locks) used? I mean the untar test case is a bit synthetic, but think of concurrent read access in a cluster of nntp servers (news article pool).

Gruss
Bernd

#23 lore raw

Re: [Ocfs2-devel] Ocfs2 performance

In reply to Mark Fasheh
Quoted 7 lines · Mark Fasheh

Your hash sizes are still ridiculously large. All my data shows that we need to increase the hash size by much much less. At the following location you will find a series of files detailing the results of 10 untar runs with various hash allocations. The short story is that we really only need an allocation on the order of a few pages.

http://oss.oracle.com/~mfasheh/dlm_hash/untar_timings/

There is a very obvious drop going from 16 to 32 pages, then you seem to drop into the noise. So if you agree that 32 is a "few" pages I think we're in the right ballpark. I've been testing with 64 pages lately, with satisfactory results.

Funny your systimes are so much higher than mine. You don't seem to have the massive failure to start writeout that I see here. Did you fix something? Also, I don't see that wildly flucuating real time. Fixed something else? I'm still running 2.6.16-pre3.

Quoted 9 lines

If you average up the untar times you'll get something close to this:

1 page:   23 seconds
2 pages:  18 seconds
4 pages:  16 seconds
6 pages:  15 seconds
8 pages:  14 seconds

16 pages: 14 seconds
32 pages: 14 seconds
64 pages: 14 seconds

Ahem, we were talking about systime. Sure, I've noticed that systime often gets buried by disk latency, but not always, and even when it does it still generates heat and slows down other things that might be running at the same time. A database for example :-)

Quoted 5 lines

PAGE_SIZE on this system is 4096

So our largest performance gain is by just adding a page, and things seem to top out at 6-8 pages. I will likely have a patch in the next few days or so which will allocate a small array of pages at dlm startup.

No need, here is a functioning patch, slice and dice to your heart's content. I wrote this to test the theory I've often heard that vmallocs are more costly to use than vectors full of pages because of tlb pressure. Balderdash, I say.

With hashvec, (64K buckets)

      real user sys
    29.62 23.87 3.02
    28.80 24.16 3.07
    50.95 24.11 3.04
    28.17 23.95 3.20
    61.21 23.89 3.16
    28.61 23.88 3.30

With vmalloc (64K buckets)

      real user sys
    29.67 23.98 2.88
    28.35 23.96 3.13
    52.29 24.16 2.89
    28.39 24.07 2.97
    65.13 24.08 3.01
    28.08 24.02 3.16

Pretty close race - vmalloc is slightly faster if anything. Note: I presume that gcc has compiled shifts and masks for my table arithmetic but I did not check. Anyway, this patch does eliminate the possibility of running around on vmalloc fragmentation.

Quoted 6 lines
Quoted 3 lines

Of course, if we take a critical look at your locking strategy we might find some fat to cut there too. Could I possibly interest you in writing up a tech note on your global locking strategy?

Sure, but it'll take a while. I've already got one OCFS2 related paper to write. Perhaps I'll be able to kill two birds with one stone.

We're not picky, how about some early notes?

Quoted 4 lines

By the way, an interesting thing happened when I recently switched disk arrays - the fluctuations in untar times disappeared. The new array is much nicer, while the old one was basically Just A Bunch Of Disks. Also, sync times dropped dramatically.

Interesting, but maybe you'd better treat the bad old disk as a blessing in disguise and let it help you find that bug.

Regards,

Daniel

fs/ocfs2/dlm/dlmcommon.h +10 -3
diff -urp 2.6.16.clean/fs/ocfs2/dlm/dlmcommon.h 2.6.16/fs/ocfs2/dlm/dlmcommon.h
@@ -36,8 +36,10 @@
  #define DLM_LOCK_RES_OWNER_UNKNOWN     O2NM_MAX_NODES
  #define DLM_THREAD_SHUFFLE_INTERVAL    5     // flush everything every 5 passes
  #define DLM_THREAD_MS                  200   // flush at least every 200 ms
-
-#define DLM_HASH_BUCKETS     (PAGE_SIZE / sizeof(struct hlist_head))
+#define DLM_HASH_SIZE		(1 << 18)
+#define DLM_HASH_PAGES		(DLM_HASH_SIZE / PAGE_SIZE)
+#define DLM_BUCKETS_PER_PAGE	(PAGE_SIZE / sizeof(struct hlist_head))
+#define DLM_HASH_BUCKETS	(DLM_HASH_PAGES * DLM_BUCKETS_PER_PAGE)
 
  enum dlm_ast_type {
  	DLM_AST = 0,
@@ -85,7 +87,7 @@ enum dlm_ctxt_state {
  struct dlm_ctxt
  {
  	struct list_head list;
-	struct hlist_head *lockres_hash;
+	struct hlist_head **lockres_hash;
  	struct list_head dirty_list;
  	struct list_head purge_list;
  	struct list_head pending_asts;
@@ -132,6 +134,11 @@ struct dlm_ctxt
  	struct list_head	dlm_eviction_callbacks;
  };
 
+static inline struct hlist_head *lockres_hash(struct dlm_ctxt *dlm, unsigned i)
+{
+	return dlm->lockres_hash[(i / DLM_BUCKETS_PER_PAGE) % DLM_HASH_PAGES] + i % DLM_BUCKETS_PER_PAGE;
+}
+
  /* these keventd work queue items are for less-frequently
   * called functions that cannot be directly called from the
   * net message handlers for some reason, usually because
fs/ocfs2/dlm/dlmdebug.c +1 -1
diff -urp 2.6.16.clean/fs/ocfs2/dlm/dlmdebug.c 2.6.16/fs/ocfs2/dlm/dlmdebug.c
@@ -130,7 +130,7 @@ void dlm_dump_lock_resources(struct dlm_
 
  	spin_lock(&dlm->spinlock);
  	for (i=0; i<DLM_HASH_BUCKETS; i++) {
-		bucket = &(dlm->lockres_hash[i]);
+		bucket = lockres_hash(dlm, i);
  		hlist_for_each_entry(res, iter, bucket, hash_node)
  			dlm_print_one_lock_resource(res);
  	}
fs/ocfs2/dlm/dlmdomain.c +37 -8

99 lines not on this page · raw message

fs/ocfs2/dlm/dlmrecovery.c +2 -2
diff -urp 2.6.16.clean/fs/ocfs2/dlm/dlmrecovery.c 2.6.16/fs/ocfs2/dlm/dlmrecovery.c
@@ -1721,7 +1721,7 @@ static void dlm_finish_local_lockres_rec
  	 * the RECOVERING state and set the owner
  	 * if necessary */
  	for (i = 0; i < DLM_HASH_BUCKETS; i++) {
-		bucket = &(dlm->lockres_hash[i]);
+		bucket = lockres_hash(dlm, i);
  		hlist_for_each_entry(res, hash_iter, bucket, hash_node) {
  			if (res->state & DLM_LOCK_RES_RECOVERING) {
  				if (res->owner == dead_node) {
@@ -1879,7 +1879,7 @@ static void dlm_do_local_recovery_cleanu
  	 *    need to be fired as a result.
  	 */
  	for (i = 0; i < DLM_HASH_BUCKETS; i++) {
-		bucket = &(dlm->lockres_hash[i]);
+		bucket = lockres_hash(dlm, i);
  		hlist_for_each_entry(res, iter, bucket, hash_node) {
   			/* always prune any $RECOVERY entries for dead nodes,
   			 * otherwise hangs can occur during later recovery */
#24 lore raw

Re: [Ocfs2-devel] Ocfs2 performance

Quoted 2 lines

Pretty close race - vmalloc is slightly faster if anything.

I don't think that test tells us anything interesting about the relative load on the TLB. What would be interesting is seeing the effect vmalloc()ed hashes have on a concurrently running load that puts heavy pressure on the TLB.

- z

#25 lore raw

Re: [Ocfs2-devel] Ocfs2 performance

Quoted 6 lines · Zach Brown
Quoted 1 line

Pretty close race - vmalloc is slightly faster if anything.

I don't think that test tells us anything interesting about the relative load on the TLB. What would be interesting is seeing the effect vmalloc()ed hashes have on a concurrently running load that puts heavy pressure on the TLB.

Bzip2 isn't that kind of load?

Regards,

Daniel

#26 lore raw

Re: [Ocfs2-devel] Ocfs2 performance

In reply to Daniel Phillips

Going back to that mysterious idle time fluctuation problem, I just noticed something interesting here:

Quoted 12 lines

With hashvec, (64K buckets)

      real user sys
    29.62 23.87 3.02
    28.80 24.16 3.07
    50.95 24.11 3.04
    28.17 23.95 3.20
    61.21 23.89 3.16
    28.61 23.88 3.30

With vmalloc (64K buckets)

Quoted 7 lines
      real user sys
    29.67 23.98 2.88
    28.35 23.96 3.13
    52.29 24.16 2.89
    28.39 24.07 2.97
    65.13 24.08 3.01
    28.08 24.02 3.16

Look, the real time artifacts show up in the same places in the two different runs. There was a reboot before each run. There is a sync before and after each trial. Each trial was initiated by hand, so this isn't about something else going on in the machine at the same time.

Got to be a clue in there somewhere.

Regards,

Daniel

#27 lore raw
In reply to Daniel Phillips
Quoted 17 lines · Daniel Phillips

After untarring four kernel trees, number of locks hits a peak of 128K. With 64K buckets the hash, a typical region of the table looks like:

3 0 3 6 1 2 2 1 2 6 1 0 1 2 1 0 0 3 1 2 2 3 1 2 5 3 2 2 1 0 3 1 1 1 3 5 2 2 1 0 2 3 3 1 3 0 5 2 2 3 0 2 1 3 1 2 4 2 0 2 5 1 4 3 5 3 3 3 3 1 4 1 2 1 2 6 2 1 3 0 2 2 2 8 1 2 2 2 3 1 0 1 3 2 1 1 1 2 2 2 2 3 2 0 2 2 2 5 2 3 2 1 1 2 6 6 1 2 2 4 2 0 3 0 3 3 3 0 2 2 1 1 2 3 2 0 2 3 3 1 3 3 3 1 4 2 8 3 2 2 2 4 3 0 1 2 3 4 2 0 3 1 0 1 2 2 3 1 4 2 1 1 3 3 4 3 3 3 4 2 1 4 2 1 5 2 1 3 1 2 3 2 1 0 1 5 3 2 1 2 3 0 1 1 2 3 4 4 4 1 3 1 4 3 2 2 4 4 1 3 1 0 0 1 3 1 1 3 0 3 0 1 1 1 1 1 3 4 4 2 4 3 4 2 3 3 0 3 4 2 1 5 4 1 3 1 1 0 1 0 1 4 1 2 1 4 2 0 2 2 5 2 1 1 1 2 3 6 4 5 5 1 1 2 3 1 5 1 3 0 1 0 3 3 2 0 2 1 2 1 0 4 3 2 1 0 1 0 2 7 1 3 2 1 1 2 4 1 3 1 2 2 3 1 3 3 1 2 0 2 1 3 1 2 0 4 4 1 2 1 2 3 3 6 0 5 2 1 1 0 3 0 1 0 2 0 4 3 2 1 0 0 2 0 1 4 2 4 5 1 0 1 3 2 2 1 1 3 2 3 0 2 1 1 3 0 0 0 2 5 3 1 0 2 0 1 0 0 2 0 4 2 1 2 4 3 0 1 2 4 1 3 0 0 1 4

Quoted 1 line

A poor distribution as you already noticed[1].

How did you decide that? The distribution of bucket sizes is:

0: 58
1: 108
2: 105
3: 82
4: 37
5: 16
6: 7
7: 1
8: 2

which, without running any statistics, looks pretty close to a binomial distribution:

0 52.884
1 109.21
2 112.63
3 77.349
4 39.793
5 16.358
6 5.5972
7 1.6397
8 0.41980

so it's probably about what you'd get if the hash function were choosing buckets uniformly at random, which is the best I'd think you could do without special knowledge of the inputs.

--b.

#28 lore raw
Quoted 4 lines · J. Bruce Fields
Quoted 1 line · Daniel Phillips

A poor distribution as you already noticed[1].

How did you decide that?

I looked at it and jumped to the wrong conclusion :-)

When I actually simulated it I found that the distribution is in fact not much different from what I get from rand. So much for trying to pin the blame on the hash function. Next lets try to pin the blame on vmalloc. (Spoiler: it's not vmalloc's fault either.)

Regards,

Daniel