performance delta after VFS i_mutex=>i_rwsem conversion

tl;dr: Mutexes spin more than than rwsems which makes mutexes perform better when contending ->i_rwsem. But, mutexes do this at the cost of not sleeping much, even with tons of contention.

Should we do something to keep rwsem and mutex performance close to each other? If so, should mutexes be sleeping more or rwsems sleeping less?

---

I was doing some performance comparisons between 4.5 and 4.7 and noticed a weird "blip" in unlink[1] performance where it got worse between 4.5 and 4.7:

	https://www.sr71.net/~dave/intel/rwsem-vs-mutex.png

There are two things to notice here:
1. Although the "1" (4.5) and "2" (4.7) lines nearly converge at high cpu counts, 4.5 outperforms 4.7 by almost 2x at low contention
2. 4.7 has lots of idle time. 4.5 eats lots of cpu spinning

That was a 160-thread Westmere (~4 years old) system, but I moved to a smaller system for some more focused testing (4 cores, Skylake), and bisected it there down to the i_mutex switch to rwsem. I tested on two commits from here on out:

	[d9171b9] 1 commit before 9902af7
	[9902af7] parallel lookups: actual switch to rwsem"

unlink takes the rwsem for write, so it should see the same level of contention as the mutex did. But, at 4 threads, the unlink performance was:

	d9171b9(mutex): 689179
	9902af7(rwsem): 498325 (-27.7%)

I tracked this down to the differences between:

rwsem_spin_on_owner() - false roughly 1% of the time mutex_spin_on_owner() - false roughly 0.05% of the time

The optimistic rwsem and mutex code look quite similar, but there is one big difference: a hunk of code in rwsem_spin_on_owner() stops the spinning for rwsems, but isn't present for mutexes in any form:

If I hack this out, I end up with:

	d9171b9(mutex-original): 689179
	9902af7(rwsem-hacked  ): 671706 (-2.5%)

I think it's safe to say that this accounts for the majority of the difference in behavior. It also shows that the _actual_ i_mutex=>i_rwsem conversion is the issue here, and not some other part of the parallel lookup patches.

So, as it stands today in 4.7-rc1, mutexes end up yielding higher performance under contention. But, they don't let them system go very idle, even under heavy contention, which seems rather wrong. Should we be making rwsems spin more, or mutexes spin less?

--

1. The test in question here is creating/unlinking many files in the same directory: >
https://github.com/antonblanchard/will-it-scale/blob/master/tests/unlink1.c

So my gut feel is that we do want to have the same heuristics for rwsems and mutexes (well, modulo possible actual semantic differences due to the whole shared-vs-exclusive issues).

And I also suspect that the mutexes have gotten a lot more performance tuning done on them, so it's likely the correct thing to try to make the rwsem match the mutex code rather than the other way around.

I think we had Jason and Davidlohr do mutex work last year, let's see if they agree on that "yes, the mutex case is the likely more tuned case" feeling.

The fact that your performance improves when you do that obviously then also validates the assumption that the mutex spinning is the better optimized one.

I think performance is what matters. The fact that it performs better with spinning is a big mark for spinning more.

Being idle under load is _not_ something we should see as a good thing. Yes, yes, it would be lower power, but lock contention is *not* a low-power load. Being slow under lock contention just tends to make for more lock contention, and trying to increase idle time is almost certainly the wrong thing to do.

Spinning behavior tends to have a secondary advantage too: it is a hell of a lot nicer to do performance analysis on. So if you get lock contention on real loads (as opposed to some extreme unlink-microbenchmark), I think a lot of people will be happier seeing the spinning behavior just because it helps pinpoint the problem in ways idling does not.

So I think everything points to: "make rwsems do the same thing mutexes do". But I'll let it locking maintainers pipe up. Peter? Ingo?

Linus

It is probably true that the mutex code has been better tuned as it was more widely used. Now that may be changing as a lot of mutexes have been changed to rwsems.

The tricky part about optimistic spinning in rwsem is that we don't know for sure if any of the lock holding readers is running or not. So we don't do spinning when readers have the lock. Currently, we use the state of the owner variable as the heuristic to determine if the lock owner is a writer (owner) or reader (!owner). However, it is also possible that a writer gets the lock, but hasn't set the owner field yet while while another task samples the owner value at that interval causing it to abort optimistic spinning.

I do have a patchset that allow us to more accurately determine the state of the lock owner.

locking/rwsem: Add reader-owned state to the owner field
http://www.spinics.net/lists/kernel/msg2258572.html

That should eliminate the performance gap between mutex and rwsem wrt spinning when only writers are present. I am hoping that that patchset can be queued for 4.8.

Cheers,
Longman

FWIW, there's another fun issue on ramfs - dcache_readdir() is doing an obscene amount of grabbing/releasing ->d_lock and once you take the external serialization out, parallel getdents load hits contention on *that*. In spades. And unlike mutex (or rswem exclusive), contention on ->d_lock chews a lot of cycles. The root cause is the use of cursors - we not only move them more than we ought to (we do that on each entry reported, rather than once before return from dcache_readdir()), we can't traverse the real list entries (which remain nice and stable; another low-hanging fruit is pointless grabbing ->d_lock on those) without ->d_lock on parent.

I think I have a kinda-sorta solution, but it has a problem. What I want to do is
* list_move() only once per dcache_readdir()
* ->d_lock taken for that and only for that.
* list_move() itself surrounded with write_seqcount_{begin,end} on
some seqcount
* traversal to the next real entry done under rcu_read_lock in a
seqretry loop.

The only problem is where to put that seqcount (unsigned int, really). ->i_dir_seq is an obvious candidate, but that'll need careful profiling on getdents/lookup mixes...

I'm notm sure how common the reader-vs-writer contention is, at least for the new inode use. I'm sure you can trigger it with crazy benchmarks, but I wouldn't worry about it unless people start complaining.

The writer-writer case is easy to trigger with write-heavy loads (ok, rename/unlink in this case). Are there real loads where there are lots of concurrent lookup and writes? I really don't know (note that "lookup" needs to be uncached and actually hit the lowlevel filesystem for the locking to even trigger in the first place).

I guess some "concurrent readdir with unlink" load would show that behavior, but is it _realistic_? No idea. Let's not worry about it too much until somebody shows a reason to worry.

Linus

Yeah, I saw that report, and I'm not entirely surprised. There was no real reason to worry about it before, since readdir() couldn't really cause contention with the previous mutual exclusion at the upper level.

Let's look at smaller changes first.

In particular, why the f*ck do we take "next->d_lock" at all, much less twice?

Do we really need that? Both of them seem bogus:

- the first one only protects the "simple_positive()" test.

That seems stupid. We hold the parent d_lock _and_ we hold the
parent inode lock for reading, how the hell is simple_positive() going to change? Yeah, yeah, *maybe* we could catch a lookup that just happens to add the inode field in process, but it's not a race we even care about. If we see the inode being non-NULL, it will now *stay* non-NULL, and we already depend on that (that "d_inode(next)" is then done without the lock held.

- the second one only protects "list_move()" of the cursor. But since
it's the child list, the "next->d_lock" thing ends up being irrelevant. It's the parent dentry lock we need to hold, nothing else. Not the "next" one.

so I don't see the point of half the d_lock games we play.

And the thing about spinlock contention: having *nested* spinlocks be contented turns contention into an exponential thing. I really suspect that if we can just remove the nested spinlock, the dentry->d_lock contention will go down by a huge amount, because then you completely remove the "wait on lock while holding another lock" thing, which is what tends to really suck.

So before you do something fancy, look at the simple parts. I think getting rid of the nested d_lock might be really simple.

Maybe we might want to do some really careful

     inode = READ_ONCE(dentry->d_inode);

because we're reading the thing without locking, and maybe there's something else subtle going on. But that really looks fairly low-hanging, and it might make the problem go away in practice.

Linus

See upthread re "low-hanging fruit".

Can't happen - it's ramfs and lookups there never end up adding a positive entry. So I don't believe that READ_ONCE() or anything of that sort would be needed. All transitions from negative to positive happen under exclusive lock on parent, which gives us all barriers we need. Transitions from hashed positive to negative or unhashed also happen only under the same exclusive lock on parent, which takes care of going in other direction.

Like I said - it's stable.

Yes.

True in general, but here we really do a lot under that ->d_lock - all list traversals are under it. So I suspect that contention on nested lock is not an issue in that particular load. It's certainly a separate commit, so we'll see how much does it give on its own, but I doubt that it'll be anywhere near enough.

Hmm. Maybe.

But at least we can try to minimize everything that happens under the dentry->d_lock spinlock.

So how about this patch? It's entirely untested, but it rewrites that readdir() function to try to do the minimum possible under the d_lock spinlock.

I say "rewrite", because it really is totally different. It's not just that the nested "next" locking is gone, it also treats the cursor very differently and tries to avoid doing any unnecessary cursor list operations.

So instead of "list_move()" at the beginning of traversal, and another for each successful dir_emit(), it just updates a "move target". The target is stable because it will only ever be a positive directory entry that we emitted, which is stable due to having the directory inode held for reading.

So now there is only one final "list_move()" at the end, and it's only done if we actually emitted a directory entry.

That makes the whole actual loop when we hold the d_lock very tight. So we hold the d_lock for truly the minimal possible case, namely the actual list traversal.

And sure, we keep dropping and re-taking it, so we'll get a fair amount of cacheline ping-pong if we have several CPU's doing this on the same directory at the same time. But minimizing the work we do inside the spinlock should hopefully mean that we get very little actual spinning.

And I do want to repeat that the patch is entirely untested. It compiles. I looked at the assembly it generated. It looks fine to me, but I might have had a brainfart and done something completely broken.

Linus

---

 fs/libfs.c | 55 ++++++++++++++++++++++++++++++++-----------------------
 1 file changed, 32 insertions(+), 23 deletions(-)

index 3db2721144c2..00a0b3a6b23e 100644
@@ -132,45 +132,54 @@ static inline unsigned char dt_type(struct inode *inode)
 	return (inode->i_mode >> 12) & 15;
 }
 
+static inline int dcache_emit_entry(struct dir_context *ctx, struct dentry *dir, struct dentry *child)
+{
+	int ret;
+	struct inode *inode;
+
+	spin_unlock(&dir->d_lock);
+	inode = d_inode(child);
+	ret = dir_emit(ctx, child->d_name.name, child->d_name.len, inode->i_ino,  dt_type(inode));
+	spin_lock(&dir->d_lock);
+	return ret;
+}
+
 /*
  * Directory is locked and all positive dentries in it are safe, since
  * for ramfs-type trees they can't go away without unlink() or rmdir(),
  * both impossible due to the lock on directory.
  */
-
 int dcache_readdir(struct file *file, struct dir_context *ctx)
 {
-	struct dentry *dentry = file->f_path.dentry;
-	struct dentry *cursor = file->private_data;
-	struct list_head *p, *q = &cursor->d_child;
+	struct dentry *dentry, *cursor;
+	struct list_head *entry, *target;
 
 	if (!dir_emit_dots(file, ctx))
 		return 0;
+
+	dentry = file->f_path.dentry;
 	spin_lock(&dentry->d_lock);
-	if (ctx->pos == 2)
-		list_move(q, &dentry->d_subdirs);
-
-	for (p = q->next; p != &dentry->d_subdirs; p = p->next) {
-		struct dentry *next = list_entry(p, struct dentry, d_child);
-		spin_lock_nested(&next->d_lock, DENTRY_D_LOCK_NESTED);
-		if (!simple_positive(next)) {
-			spin_unlock(&next->d_lock);
+
+	cursor = file->private_data;
+	entry = (ctx->pos == 2) ? &dentry->d_subdirs : &cursor->d_child;
+
+	target = NULL;
+	while ((entry = entry->next) != &dentry->d_subdirs) {
+		struct dentry *child = list_entry(entry, struct dentry, d_child);
+
+		if (!simple_positive(child))
 			continue;
-		}
 
-		spin_unlock(&next->d_lock);
-		spin_unlock(&dentry->d_lock);
-		if (!dir_emit(ctx, next->d_name.name, next->d_name.len,
-			      d_inode(next)->i_ino, dt_type(d_inode(next))))
+		/* This will drop and re-take the dentry lock .. */
+		if (!dcache_emit_entry(ctx, dentry, child))
 			return 0;
-		spin_lock(&dentry->d_lock);
-		spin_lock_nested(&next->d_lock, DENTRY_D_LOCK_NESTED);
-		/* next is still alive */
-		list_move(q, p);
-		spin_unlock(&next->d_lock);
-		p = q;
+
+		/* .. but 'entry' is stable because of the shared rwsem */
+		target = entry;
 		ctx->pos++;
 	}
+	if (target)
+		list_move(&cursor->d_child, target);
 	spin_unlock(&dentry->d_lock);
 	return 0;
 }

Dammit.

I did that whole dcache_emit_entry() thing because we need to do the final target cursor move regardless, and dcache_emit_entry() will always return with the spinlock held again.

But then I didn't actually fix the "return" to a "break".

So the "return 0" here:

It seems to at least survive some trivial testing with that fixed..

Linus

Similar to what I've got here, except that mine has a couple of helper functions usable in dcache_dir_lseek() as well:

next_positive(parent, child, n) - returns nth positive child after that one or NULL if there's less than n such. NULL as the second argument => search from the beginning.

move_cursor(cursor, child) - moves cursor immediately past child *or* to the very end if child is NULL.

The third commit in series will be the lockless replacement for for next_positive(). move_cursor() is easy - it became simply

	struct dentry *parent = cursor->d_parent;
	unsigned n, *seq = &parent->d_inode->i_dir_seq;
	spin_lock(&parent->d_lock);
        for (;;) {
                n = *seq;
                if (!(n & 1) && cmpxchg(seq, n, n + 1) == n)  
                        break;
                cpu_relax();
        }
        __list_del(cursor->d_child.prev, cursor->d_child.next);
        if (child)
                list_add(&cursor->d_child, &child->d_child);
        else
                list_add_tail(&cursor->d_child, &parent->d_subdirs);
	smp_store_release(seq, n + 2);
	spin_unlock(&parent->d_lock);

with

static struct dentry *next_positive(struct dentry *parent,
struct dentry *child, int count)

{
        struct list_head *p = child ? &child->d_child : &parent->d_subdirs;
        unsigned *seq = &parent->d_inode->i_dir_seq, n;
        do {
                int i = count;
                n = smp_load_acquire(seq) & ~1;
                rcu_read_lock();
                do {
                        p = p->next;
                        if (p == &parent->d_subdirs) {
                                child = NULL;
                                break;
                        }
                        child = list_entry(p, struct dentry, d_child);
                } while (!simple_positive(child) || --i);
                rcu_read_unlock();
        } while (unlikely(smp_load_acquire(seq) != n));
        return child;
}

as initial attempt at lockless next_positive(); barriers are probably wrong, though...

FWIW,
loff_t dcache_dir_lseek(struct file *file, loff_t offset, int whence)

{
        struct dentry *dentry = file->f_path.dentry;
        switch (whence) {
                case 1:
                        offset += file->f_pos;
                case 0:
                        if (offset >= 0)
                                break;
                default:
                        return -EINVAL;
        }
        if (offset != file->f_pos) {
                file->f_pos = offset;
                if (file->f_pos >= 2) {
                        struct dentry *cursor = file->private_data;
                        loff_t n = file->f_pos - 2;

                        inode_lock_shared(dentry->d_inode);
                        move_cursor(cursor, next_positive(dentry, NULL, n));
                        inode_unlock_shared(dentry->d_inode);
                }
        }
        return offset;
}

and
int dcache_readdir(struct file *file, struct dir_context *ctx)

{
        struct dentry *dentry = file->f_path.dentry;
        struct dentry *cursor = file->private_data;
        struct dentry *child, *next;
        bool moved = false;

        if (!dir_emit_dots(file, ctx))
                return 0;

        child = ctx->pos != 2 ? cursor : NULL;
        while ((next = next_positive(dentry, child, 1)) != NULL) {
                if (!dir_emit(ctx, next->d_name.name, next->d_name.len,
                              d_inode(next)->i_ino, dt_type(d_inode(next))))
                        break;
                moved = true;
                child = next;
                ctx->pos++;
        }
        if (moved)
                move_cursor(cursor, child);
        return 0;
}

is what the methods themselves became.

== NULL" means. Here it means that it's a cursor to the beginning, but in your commentary on move_cursor(), you say "moves cursor immediately past child *or* to the very end if child is NULL".

That's very confusing. Is NULL beginning or end?

I really think you'd be better off having a special ERR_PTR value for end, possibly as a flag value in the cursor dentry.

The whole "what does NULL mean" confusion exists inside that "next_positive" too:

look, here you return NULL for "end" again. Even though it meant beginning at the start of the function. Nasty.

Also, may I suggest that there is a very trivial special case for "next_positive()" that needs no barriers or sequence checking or anything else: at the very beginning, just load the "->next" pointer, and if it's a positive entry, you're done. That's going to be the common case when there _isn't_ crazy multi-threaded readdirs going on, so it's worth handling separately.

In fact, if you have a special value for the case of "cursor is at end" situation, then for the small directory case that can be handled with a single getdents call, you'll *never* set the cursor in the child list at all, which means that the above special case for next_positive() is actually the common case even for the threaded situation.

Linus

More than just barriers... _Absolutely_ untested variant pushed into vfs.git#untested.dcache_readdir (the last 3 commits in there). It compiles, but that's it.

The former for argument, the latter for return value...

Actually, reassigning 'child' here was broken, NULL or no NULL - we want the subsequent retries (if any) to start at the same state.

Point.

Not really. Cursor is allocated on the child list in the first place; it's just that its position is ignored for file->f_pos <= 2. We could change that, but I'd rather avoid the headache right now.

I've seen Makefiles where 'make clean' does a 'find . -name "*.o" | xargs rm'.

But if somebody is doing that often enough against cache-cold directory trees to matter, they have bigger problems (like learning how to properly develop code using 'make'). So unless performance is *so* bad it triggers the lockup detector, it's probably OK....

The performance won't be very bad. It is just that with the right mix of readers and writers, the performance can be a bit worse with i_rwsem than with i_mutex. But in other cases, the performance will be comparable or better with i_rwsem.

Regards,
Longman

Yeah, so I actually had this series merged for testing last week, but a complication with a prereq patch made me unmerge it. But I have no fundamental objections, at all.

I also agree with Linus's general observation that we want to make down_write()/up_write() match mutex performance characteristics.

I think kernel developers should fundamentally be able to switch between mutex_lock()/unlock() and down_write()/up_write() and back, without noticing any high level behavioral changes.

Any 'reader/writer mixing' artifacts are secondary concerns and we'll sort them out as they happen.

Thanks,

Ingo

Ok, these enhancements are now in the locking tree and are queued up for v4.8:

git pull git://git.kernel.org/pub/scm/linux/kernel/git/tip/tip.git locking/core

Dave, you might want to check your numbers with these changes: is rwsem performance still significantly worse than mutex performance?

Thanks,

Ingo

...

It's substantially closer than it was, but there's probably a little work still to do. The rwsem still looks to be sleeping a lot more than the mutex. Here's where we started:

	https://www.sr71.net/~dave/intel/rwsem-vs-mutex.png

The rwsem peaked lower and earlier than the mutex code. Now, if we compare the old (4.7-rc1) rwsem code to the newly-patched rwsem code (from tip/locking):

We can see the peak is a bit higher and more importantly, it's more of a plateau than a sharp peak. We can also compare the new rwsem code to the 4.5 code that had the mutex in place:

rwsems are still a _bit_ below the mutex code at the peak, and they also seem to be substantially lower during the tail from 20 cpus on up. The rwsems are sleeping less than they were before the tip/locking updates, but they are still idling the CPUs 90% of the time while the mutexes end up idle 15-20% of the time when all the cpus are contending on the lock.

In Al Viro's conversion, he introduced inode_lock_shared which uses
read lock in lookup_slow. The rwsem does bail out of optimistic spin when
readers acquire the lock, thus causing us to see a lot less optimistic spinning attempts for the unlink test case.

Whereas earlier for mutex, we will keep spinning.

A simple test may be to see if we get similar performance when changing inode_lock_shared to the writer version.

That said, hopefully we should have a lot more read locking than write locking (i.e. more path look up than changes to the path) so the switch to rwsem is still a win. I guess the lesson here is when there is an equal mix of writers and readers, rwsem could be a bit worse in performance than mutex as we don't spin as hard.

Tim