futex/rtmutex: Fix issues exposed by trinity

I think this patch is just a workaround, it is not the proper fix. you need a updated deadlock-check mechanism:

- (old) skip the check when top_waiter != task_top_pi_waiter(task)
+ (new) skip the check when top_waiter->prio > task->prio

	/*
	 * Drop out, when the task has no waiters. Note,
	 * top_waiter can be NULL, when we are in the deboosting
	 * mode!
	 */
	if (top_waiter && (!task_has_pi_waiters(task) ||
			   top_waiter != task_top_pi_waiter(task)))
		goto out_unlock_pi;

(also need to update the code in other places respectively)

kernel/locking/rtmutex.c static int rt_mutex_adjust_prio_chain(st · line 345

Quoted 5 lines

kernel/locking/rtmutex.c +4 -0

 	/*
+	 * Deadlock check for the following scenario:
+	 *
+	 * T holds lock L and has waiters
+	 * T locks L again, but does not end up as it's own top waiter

ABBA problem (TA TB TC TD are of the same priority)

TA holds lock LA, and try to lock LB which TC already has waited on TB holds lock LB, and try to lock LA which TD already has waited on

I think this check can't detect it IIUC.

kernel/locking/rtmutex.c static int rt_mutex_adjust_prio_chain(st · line 352

Quoted 7 lines

kernel/locking/rtmutex.c +7 -0

+	 *
+	 * So we would drop out at the next check without noticing.
+	 *
+	 * Note, we need to check for orig_waiter as it might be NULL
+	 * when deboosting!
+	 */
+	if (orig_waiter && orig_waiter->task == rt_mutex_owner(lock)) {

when non-first-loop, it is already checked.

kernel/locking/rtmutex.c static int rt_mutex_adjust_prio_chain(st · line 355

Quoted 3 lines

kernel/locking/rtmutex.c +3 -0

+		ret = deadlock_detect ? -EDEADLK : 0;
+		goto out_unlock_pi;
+	}

I considered you blamed to me.
I would feel better if you directly blamed to me.

I considered you blamed to me.
I would feel better if you directly blamed to me.

Quoted 2 lines · Lai Jiangshan

I considered you blamed to me.
I would feel better if you directly blamed to me.

Well, the way I see it all you're to blame for is 'forgetting' to update the rt mutex test for 3 years, and while that is unfortunate, the much bigger fail is merging the patch without it to begin with.

So in that respect Steven is primarily responsible for merging incomplete work.

Now Thomas was entirely grumpy from staring at bugs for a long while, which is entirely understandable. That said I don't think he went overboard calling Steven out on this.

Now, if you and Steve get this sorted, nothing really happened except that Thomas got grumpy, which is entirely normal, what else would he be? :-)

Now, if you and Steve get this sorted, nothing really happened except that Thomas got grumpy, which is entirely normal, what else would he be? :-)

Quoted 4 lines · Peter Zijlstra

Now, if you and Steve get this sorted, nothing really happened except that Thomas got grumpy, which is entirely normal, what else would he be? :-)

Who is that grumpy Thomas dude, should I know him?

Lai, Steven,

before you waste lots of time on the tester, I want to look at it whether we can simplify it or even rewrite it from scratch. I glanced at it today and I really can't remember what kind of substances were involved when I wrote this almost a decade ago.

The whole schedule_rt_mutex mechanism was mostly done to create controlled lock stealing scenarios and deal with the BKL oddities.

With Lai's simplification and the demise of BKL I'm quite sure we do not need it anymore.

So we can just get rid of the complexity in schedule_rt_mutex() and replace it with a simple:

    while (!td->continue)
    	  schedule();

That would also make the teardown and reset of the whole thing manageable. Right now it's easy to create a situation where unrolling stuff gets almost impossible except by pushing the reset button.

The state readouts can be done directly via the rtmutexes and the task structs.

Thoughts?

Quoted 7 lines · On Tue, 13 May 2014 21:42:54 +0200 (CEST) Thomas Gleixner <[email protected]>…

Quoted 4 lines · Peter Zijlstra

Now, if you and Steve get this sorted, nothing really happened except that Thomas got grumpy, which is entirely normal, what else would he be? :-)

Who is that grumpy Thomas dude, should I know him?

Quoted 6 lines

Lai, Steven,

before you waste lots of time on the tester, I want to look at it whether we can simplify it or even rewrite it from scratch. I glanced at it today and I really can't remember what kind of substances were involved when I wrote this almost a decade ago.

Thank God. /me removes the ton of trace_printk()s in the code as well as all the trace_marker.write("%s" %(line)) from the test to figure out what was going on.

Quoted 21 lines

The whole schedule_rt_mutex mechanism was mostly done to create controlled lock stealing scenarios and deal with the BKL oddities.

With Lai's simplification and the demise of BKL I'm quite sure we do not need it anymore.

So we can just get rid of the complexity in schedule_rt_mutex() and replace it with a simple:

    while (!td->continue)
    	  schedule();

That would also make the teardown and reset of the whole thing manageable. Right now it's easy to create a situation where unrolling stuff gets almost impossible except by pushing the reset button.

The state readouts can be done directly via the rtmutexes and the task structs.

Quoted 2 lines

Thoughts?

What about having a module that creates a bunch of threads and forces all the scenarios that we want to test? Wouldn't it be easier to do than to have a userspace interface to dictate commands to the kernel?

Quoted 3 lines · Steven Rostedt

What about having a module that creates a bunch of threads and forces all the scenarios that we want to test? Wouldn't it be easier to do than to have a userspace interface to dictate commands to the kernel?

I second this approach! The kernel environment makes it -much- easier to force races and other conditions, which turns into much simpler and more effective tests.

Quoted 8 lines · Paul E. McKenney

Quoted 3 lines · Steven Rostedt

What about having a module that creates a bunch of threads and forces all the scenarios that we want to test? Wouldn't it be easier to do than to have a userspace interface to dictate commands to the kernel?

I second this approach! The kernel environment makes it -much- easier to force races and other conditions, which turns into much simpler and more effective tests.

The point of the rtmutex tester was NOT to force races and stuff, it was intended to be a formal test for certain static scenarios:

- verify boosting / debosting
- verify set_scheduler interaction
- verify deadlock detection

The latter was incomplete and therefor missed the futex wreckage :(

Having a formal checker makes a lot of sense.

Plastering the code with a gazillion of trace_printks, waiting several hours for each iteration and staring into several GB of traces just to figure out, that it is an algorithmic issue, is utter waste of time and nerves. And that stuff is definitely complex enough to justify a static checker.

Back then when I wrote it, it unearthed quite some logic bugs. And I needed the schedule_rt_mutex() hack to verify the BKL interaction and the lock steal machinery, which made it impossible to be a module. It could have been done, but that'd have been even more ugly hackery.

So I made it a user space interface to add/modify test cases without recompiling the kernel. But now with BKL and the lock steal muck gone, we simply might kill it.

Now that allows a module, but then I'm still not sure whether formal verification rules are fun to code in C. There are certainly better ways than the *.tst rules I defined back then. But yes, we could add a similar cryptic thing with static arrays of OP/Data pairs in C.

Good points -- I was indeed thinking about stress testing instead of algorithmic testing.

Quoted 2 lines · On Tue, 13 May 2014 15:00:09 -0700 "Paul E. McKenney"…

Good points -- I was indeed thinking about stress testing instead of algorithmic testing.

But doesn't lockdep use algorithmic tests too?

Quoted 7 lines · Steven Rostedt

Quoted 2 lines · On Tue, 13 May 2014 15:00:09 -0700 "Paul E. McKenney"…

Good points -- I was indeed thinking about stress testing instead of algorithmic testing.

Quoted 1 line

But doesn't lockdep use algorithmic tests too?

I suppose you could argue that there is no such thing as non-algorithmic testing, given that all test code uses an algorithm of some sort. Perhaps with the exception of letting your pet walk across the keyboard. ;-)

Perhaps I should have instead said that I was thinking about random testing instead of formal testing?

Quoted 8 lines · On Tue, 13 May 2014 16:27:11 -0700 "Paul E. McKenney"…

Quoted 7 lines · Steven Rostedt

Quoted 2 lines · On Tue, 13 May 2014 15:00:09 -0700 "Paul E. McKenney"…

Good points -- I was indeed thinking about stress testing instead of algorithmic testing.

Quoted 8 lines

Quoted 1 line

But doesn't lockdep use algorithmic tests too?

I suppose you could argue that there is no such thing as non-algorithmic testing, given that all test code uses an algorithm of some sort. Perhaps with the exception of letting your pet walk across the keyboard. ;-)

Perhaps I should have instead said that I was thinking about random testing instead of formal testing?

Actually it still applies, but I was mistaken, it's not lockdep itself, it's the LOCKING_API_SELFTESTS. They are a form of formal testing as suppose to random testing.

See lib/locking-selftest.c.

That looks more like something we can do for the rtmutex code, or even add to it.

Quoted 8 lines · On Tue, 13 May 2014 16:27:11 -0700 "Paul E. McKenney"…

Quoted 7 lines · Steven Rostedt

Quoted 2 lines · On Tue, 13 May 2014 15:00:09 -0700 "Paul E. McKenney"…

Good points -- I was indeed thinking about stress testing instead of algorithmic testing.

Quoted 8 lines

Quoted 1 line

But doesn't lockdep use algorithmic tests too?

I suppose you could argue that there is no such thing as non-algorithmic testing, given that all test code uses an algorithm of some sort. Perhaps with the exception of letting your pet walk across the keyboard. ;-)

Perhaps I should have instead said that I was thinking about random testing instead of formal testing?

Actually it still applies, but I was mistaken, it's not lockdep itself, it's the LOCKING_API_SELFTESTS. They are a form of formal testing as suppose to random testing.

See lib/locking-selftest.c.

That looks more like something we can do for the rtmutex code, or even add to it.

On May 13, 2014 11:54 PM, "Thomas Gleixner" <[email protected]> wrote:

I'll gladly accept new functional/algorithm type tests to futextest (performance stuff is probably going to perf instead, and Dave Miller beat

me to the fuzz tester with Trinity). But I think there is evidence we should build out the futex functional testing, and futextest seems a logical place for it.

Quoted 2 lines · On Tue, 13 May 2014 15:00:09 -0700 "Paul E. McKenney"…

Good points -- I was indeed thinking about stress testing instead of algorithmic testing.

But doesn't lockdep use algorithmic tests too?

Hi, Thomas,

I think this patch is just a workaround, it is not the proper fix. you need a updated deadlock-check mechanism:

- (old) skip the check when top_waiter != task_top_pi_waiter(task)
+ (new) skip the check when top_waiter->prio > task->prio

kernel/locking/rtmutex.c static int rt_mutex_adjust_prio_chain(st · line 345

Quoted 5 lines

kernel/locking/rtmutex.c +4 -0

 	/*
+	 * Deadlock check for the following scenario:
+	 *
+	 * T holds lock L and has waiters
+	 * T locks L again, but does not end up as it's own top waiter

ABBA problem (TA TB TC TD are of the same priority)

TA holds lock LA, and try to lock LB which TC already has waited on TB holds lock LB, and try to lock LA which TD already has waited on

I think this check can't detect it IIUC.

	/*
	 * Drop out, when the task has no waiters. Note,
	 * top_waiter can be NULL, when we are in the deboosting
	 * mode!
	 */
	if (top_waiter && (!task_has_pi_waiters(task) ||
			   top_waiter != task_top_pi_waiter(task)))
		goto out_unlock_pi;

We happily allow userspace to declare a random kernel thread to be the owner of a user space PI futex.

Found while analysing the fallout of Dave Jones syscall fuzzer.

Quoted 4 lines · Thomas Gleixner

We happily allow userspace to declare a random kernel thread to be the owner of a user space PI futex.

Found while analysing the fallout of Dave Jones syscall fuzzer.

Did you also still want to check the ppid for _PRIVATE futexes?

We happily allow userspace to declare a random kernel thread to be the owner of a user space PI futex.

Found while analysing the fallout of Dave Jones syscall fuzzer.

Signed-off-by Thomas Gleixner <[email protected]>

Cc [email protected]

---
 kernel/futex.c |    7 +++++++
 1 file changed, 7 insertions(+)

Index: linux-2.6/kernel/futex.c
===================================================================

kernel/futex.c +2 -0

@@ -682,6 +682,8 @@ static struct task_struct * futex_find_g
        p = find_task_by_vpid(pid);
        if (p)
                get_task_struct(p);
+       else
+               p = NULL;
 
        rcu_read_unlock();
 

Quoted 11 lines · Thomas Gleixner

We happily allow userspace to declare a random kernel thread to be the owner of a user space PI futex.

Found while analysing the fallout of Dave Jones syscall fuzzer.

Signed-off-by Thomas Gleixner <[email protected]>

Cc [email protected]

---
 kernel/futex.c |    7 +++++++
 1 file changed, 7 insertions(+)

kernel/futex.c static struct task_struct * futex_find_g · line 686

Quoted 10 lines

Index: linux-2.6/kernel/futex.c
===================================================================

kernel/futex.c +2 -0

@@ -682,6 +682,8 @@ static struct task_struct * futex_find_g
        p = find_task_by_vpid(pid);
        if (p)
                get_task_struct(p);
+       else
+               p = NULL;

Quoted 7 lines

kernel/futex.c +0 -0

        rcu_read_unlock();
 

@@ -814,6 +816,11 @@ lookup_pi_state(u32 uval, struct futex_h
        if (!p)
                return -ESRCH;
 

kernel/futex.c lookup_pi_state(u32 uval, struct futex_h · line 822

Quoted 4 lines

kernel/futex.c +4 -0

+       if (!p->mm) {
+               put_task_struct(p);
+               return -EPERM;
+       }

It might make sense to check the mm inside futex_find_get_task(), and simply never take the refcount if NULL.

Steven, I told you more than once, that your damned performance and feature mania is completely unacceptable.

When the patch was posted, you were reviewing it. When I wanted to test it, it did not apply and you told me you'll fix it and pick it up. Sure you made it apply and you sticked it into a git tree and let Ingo pull it.

I didn't pay much attention as I was happy with the idea in general. I trusted your review and judgement. My problem.

Why on earth did you merge that patch even if the changelog mentions that Documentation was left stale and the tester broken?

This is beyond sloppy and outright stupid.

Get this fixed now!

And those fixes are not going to be merged without my Reviewed-by.

I'm not going to let your multi-reader patches anywhere near RT, unless this Documentation and tester issue is resolved.

After that I'm going through them with a fine comb, as I really lost the last modicom of hope, that you can do something without leaving trainwrecks left and right.

Quoted 2 lines · On Mon, 12 May 2014 20:45:32 -0000 Thomas Gleixner <[email protected]> wrote:

Steven, I told you more than once, that your damned performance and feature mania is completely unacceptable.

Yes you have, and now you are yelling at me for something I did 3 years ago. But this isn't one of my "performance and feature mania" things you bitched at me about. This is something *you* asked me to look at!

http://marc.info/?l=linux-kernel&m=129242481625261

The "stress test" you recommend back then was just to port it to -rt and test it there. Which I did, and it found various issues where I helped Lai fix.

Quoted 12 lines · Steven Rostedt

Quoted 2 lines · On Mon, 12 May 2014 20:45:32 -0000 Thomas Gleixner <[email protected]> wrote:

Steven, I told you more than once, that your damned performance and feature mania is completely unacceptable.

Yes you have, and now you are yelling at me for something I did 3 years ago. But this isn't one of my "performance and feature mania" things you bitched at me about. This is something *you* asked me to look at!

Quoted 5 lines

http://marc.info/?l=linux-kernel&m=129242481625261

The "stress test" you recommend back then was just to port it to -rt and test it there. Which I did, and it found various issues where I helped Lai fix.

And that's an excuse to merge stuff which leaves trainwrecks behind it?

Steven, start getting adult and admit your failures.

I'm cutting it right here as the following is just your attempt to redirect the failure to me.

Yes, I made a mistake. The very mistake of trusting you.

That'll not happen again.

I did admit I made a mistake. If you read the rest of my email that you cut off, I said "Sure, I should have pushed Lai for that at the time. Lessons learned. I was expecting he would do so after we got to a final version of the patch but I was also working on other things at the time and forgot to remind him."

I even stated that I'm doing better now. That means I have learned from my mistakes. And continue to do so.

Quoted 8 lines · Steven Rostedt

I did admit I made a mistake. If you read the rest of my email that you cut off, I said "Sure, I should have pushed Lai for that at the time. Lessons learned. I was expecting he would do so after we got to a final version of the patch but I was also working on other things at the time and forgot to remind him."

I even stated that I'm doing better now. That means I have learned from my mistakes. And continue to do so.

Sure, with your latest multi reader patches you break even the compile with CONFIG_DEBUG_RT_MUTEXES=y due to:

+ debug_rt_mutex_print_deadlock(waiter);

I'm really impressed by your improvements.

Quoted 1 line

This is beyond sloppy and outright stupid.

Thomas, listen to yourself. You are calling something that got in without updating the documentation and test case "beyond sloppy and outright stupid". Sure, I'll agree it was a little sloppy, and today I'm more on the ball to get things like this right (as we push much harder today on documentation coming in along with code changes). But the change log had:

need updated after this patch is accepted
1) Document/*
2) the testcase scripts/rt-tester/t4-l2-pi-deboost.tst

I agree this should be fixed, but you temper tantrum over this seems a bit over the top.

In current rtmutex,

In the current rtmutex code,

From 8161239a8bcce9ad6b537c04a1fa3b5c68bae693 Mon Sep 17 00:00:00 2001

Dave reported recently that the trinity syscall fuzzer triggers a warning in the rtmutex code via the futex syscall.

It took me quite a while to understand the issue, until I was able to write a minimalistic reproducer.

The first two patches address the issues and the third one is adding an unrelated sanity check to prevent user space from assigning PI futexes to kernel threads.

I ran it through my usual tests (except of one, see below), Darrens futex tester and it holds up against a 400 threads trinity whacking for well above 12hrs now.

Staring three days into futex.c/rtmutex.c and a few GB of traces definitly brings one in a lousy mood. But I discovered two things which made me outright grumpy:

2) glibc fun

While writing an isolated test case for the trinity wreckage, I found out that glibc has an interesting misfeature:

strace tells me:

futex(0x600e00, FUTEX_LOCK_PI_PRIVATE, 1) = -1 EINVAL (Invalid argument)

but the return value of pthread_mutex_lock() is 0

Yay, for another master piece of trainwreck engineering!

I checked the glibc source and of course neither the lock nor the unlock path gets any error code from the syscall propagated.

The handling of -EDEADLOCK is even more impressive. Instead of propagating it to the caller something in the guts of glibc calls pause().

     futex(0x601300, FUTEX_LOCK_PI_PRIVATE, 1) = -1 EDEADLK (Resource deadlock avoided)
     pause(

So any kind of futex wreckage which is not detectable by glibc itself ends up in a disaster one way or the other. How is Joe user of this stuff who reads the manpages supposed to find out that the kernel detected an inconsistent user space variable?

If someone of the glibc folks can be bothered to look after that, I'm happy to provide the simple test cases, but I'm sure that looking at the code which simply ignores or pauses on kernel error return values is enough to figure out why its broken.

This does not only apply to the PI version, the bog standard futexes have error returns from the kernel as well, which are handled in the same absurd way.

Yours grumpy

tglx

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

Quoted 4 lines · Thomas Gleixner

strace tells me:

   futex(0x600e00, FUTEX_LOCK_PI_PRIVATE, 1) = -1 EINVAL (Invalid argument)

Quoted 1 line

but the return value of pthread_mutex_lock() is 0

So something is clearly wrong there - however, were you looking at the comments (sorry, I mean the C code), or the implementation (all the ASM)? The only way I've been able to be sure in the past is to delete the ASM files and recompile using the C files. Hopefully we'll be able to drop all the ASM in the pthread calls soonish (measured in years in glibc development time scales).... sigh.

Quoted 5 lines · Darren Hart

Quoted 4 lines · Thomas Gleixner

strace tells me:

   futex(0x600e00, FUTEX_LOCK_PI_PRIVATE, 1) = -1 EINVAL (Invalid argument)

Quoted 7 lines

Quoted 1 line

but the return value of pthread_mutex_lock() is 0

So something is clearly wrong there - however, were you looking at the comments (sorry, I mean the C code), or the implementation (all the ASM)? The only way I've been able to be sure in the past is to delete the ASM files and recompile using the C files. Hopefully we'll be able to drop all the ASM in the pthread calls soonish (measured in years in glibc development time scales).... sigh.

The C implementation does:

	    if (INTERNAL_SYSCALL_ERROR_P (e, __err)
		&& (INTERNAL_SYSCALL_ERRNO (e, __err) == ESRCH
		    || INTERNAL_SYSCALL_ERRNO (e, __err) == EDEADLK))
	      {
		assert (INTERNAL_SYSCALL_ERRNO (e, __err) != EDEADLK
			|| (kind != PTHREAD_MUTEX_ERRORCHECK_NP
			    && kind != PTHREAD_MUTEX_RECURSIVE_NP));
		/* ESRCH can happen only for non-robust PI mutexes where
		   the owner of the lock died.  */
		assert (INTERNAL_SYSCALL_ERRNO (e, __err) != ESRCH || !robust);

		/* Delay the thread indefinitely.  */
		while (1)
		  pause_not_cancel ();
	      }

So anything else than ESRCH and EDEADLK is ignored and then the thing happily returns 0 at the end. Unlock is the same:

	{
	  int robust = mutex->__data.__kind & PTHREAD_MUTEX_ROBUST_NORMAL_NP;
	  int private = (robust
			 ? PTHREAD_ROBUST_MUTEX_PSHARED (mutex)
			 : PTHREAD_MUTEX_PSHARED (mutex));
	  INTERNAL_SYSCALL_DECL (__err);
	  INTERNAL_SYSCALL (futex, __err, 2, &mutex->__data.__lock,
			    __lll_private_flag (FUTEX_UNLOCK_PI, private));
	}

Quoted 2 lines · Thomas Gleixner

So anything else than ESRCH and EDEADLK is ignored and then the thing happily returns 0 at the end. Unlock is the same:

The code is valid so long as you expect only ESRCH and EDEADLK to be the only errors the kernel returns.

What other error codes are returned and under what conditions?

Are those other errors actionable by the user?

Since anything other than the agreed upon set of error returns is a failure in the coordinated implementation between glibc and the kernel.

Quoted 9 lines

	{
	  int robust = mutex->__data.__kind & PTHREAD_MUTEX_ROBUST_NORMAL_NP;
	  int private = (robust
			 ? PTHREAD_ROBUST_MUTEX_PSHARED (mutex)
			 : PTHREAD_MUTEX_PSHARED (mutex));
	  INTERNAL_SYSCALL_DECL (__err);
	  INTERNAL_SYSCALL (futex, __err, 2, &mutex->__data.__lock,
			    __lll_private_flag (FUTEX_UNLOCK_PI, private));
	}

Isn't the the same issue as before? This code presumes that because the atomic operation completed successfully that the kernel state is OK. Assuming otherwise slows down the fast path in the unlock just to check for kernel bugs. Is the returned error in any way actionable by the user?

Quoted 6 lines · Carlos O'Donell

Quoted 2 lines · Thomas Gleixner

So anything else than ESRCH and EDEADLK is ignored and then the thing happily returns 0 at the end. Unlock is the same:

The code is valid so long as you expect only ESRCH and EDEADLK to be the only errors the kernel returns.

Brilliant assumption, really. So we rather return 0 to the user than having a catch for that case?

You know that this is how a large portion of security holes are created, right?

Quoted 1 line

What other error codes are returned and under what conditions?

-ENOMEM Kernel can't allocate state.

-EFAULT Accessing the user space futex failed. Might be a mapping
zapped by a different thread or no valid access (e.g. RO mapping)

-EPERM No permission to attach yourself to a futex owned by someone
else or to unlock it.

-EINVAL Inconsistant state detected.

-ETIMEDOUT
timed op timed out

-EWOULDBLOCK

For non PI indicates that the caller raced against another thread.

For PI also returned if trylock fails.

-ESRCH Owner died

-EAGAIN Owner is about to die, but has not yet finished the cleanup

Quoted 1 line

Are those other errors actionable by the user?

Define actionable. Most of them are in my opinion.

Some of them like -EWOULDBLOCK for non PI or -EAGAIN are for glibc internal consumption.

Quoted 2 lines

Since anything other than the agreed upon set of error returns is a failure in the coordinated implementation between glibc and the kernel.

Well. Back then when we implemented pi and robust futex support this was done hand in hand with glibc folks and they knew about ALL the error codes we return. I'm quite sure that we did not add any new one since then, but I really can't be bothered to look.

Quoted 10 lines

Quoted 9 lines

	{
	  int robust = mutex->__data.__kind & PTHREAD_MUTEX_ROBUST_NORMAL_NP;
	  int private = (robust
			 ? PTHREAD_ROBUST_MUTEX_PSHARED (mutex)
			 : PTHREAD_MUTEX_PSHARED (mutex));
	  INTERNAL_SYSCALL_DECL (__err);
	  INTERNAL_SYSCALL (futex, __err, 2, &mutex->__data.__lock,
			    __lll_private_flag (FUTEX_UNLOCK_PI, private));
	}

Quoted 4 lines

Isn't the the same issue as before? This code presumes that because the atomic operation completed successfully that the kernel state is OK. Assuming otherwise slows down the fast path in the unlock just to check for kernel bugs. Is the returned error in any way actionable by the user?

We return EPERM, EFAULT and EINVAL on unlock.

EPERM Tells you that the user space / kernel state is
inconsistent, because kernel thinks the owner is not current.

EINVAL That would be a glibc bug calling unlock pi for a non futex,
which has non pi waiters in the kernel.

That one was explicitely there from the very beginning.

And as I demonstrated in the other mail, it's easy to corrupt state w/o glibc even being able to notice. So you better handle that gracefully instead of making utterly stupid assumptions.

Quoted 10 lines · Thomas Gleixner

Quoted 6 lines · Carlos O'Donell

Quoted 2 lines · Thomas Gleixner

So anything else than ESRCH and EDEADLK is ignored and then the thing happily returns 0 at the end. Unlock is the same:

The code is valid so long as you expect only ESRCH and EDEADLK to be the only errors the kernel returns.

Brilliant assumption, really. So we rather return 0 to the user than having a catch for that case?

That's correct. At the time the argument was that performance of the hot path was the only thing that mattered. For each additional error code we add the hot path instruction length is enlarged. I'm not arguing for or against, but simply stating the design criteria that I know were part of the original work. Thus it would have been perfectly valid to ignore all error codes except those that mattered to the implementation, leaving failures like ENOMEM to bubble up elsewhere instead of slowing down threads.

I will make my personal opinion clear:

- Internal defects should raise immediate assertions.

- Real problems like resource availability, deadlocks, and other recoverable errors should result in the API returning an appropriate error code that must not diverge from the POSIX definitions for those codes (when such a definition exists).

I'm not a believer in "only the hot path matters", there are such things as robustness and error detection, and they matter.

Awesome. I like the direction this conversation is taking, since this is actionable for me to fix the implementation.

Quoted 6 lines

Quoted 1 line

Are those other errors actionable by the user?

Define actionable. Most of them are in my opinion.

Some of them like -EWOULDBLOCK for non PI or -EAGAIN are for glibc internal consumption.

That's what I mean. Can the user do anything useful with the error?

However, if glibc detects an inconsistency between the kernel and glibc, I am not excited about returning EINVAL to the user, I would rather abort or assert that the data structures have been corrupted. The principal here being to abort or assert as close to the point at which the corruption occurred to help the developer debug the problem. I would argue that returning EINVAL to a library or application that already manged to corrupt state is unlikely to know how to properly handle the error anyway.

Would you agree?

Quoted 4 lines

We return EPERM, EFAULT and EINVAL on unlock.

EPERM Tells you that the user space / kernel state is
inconsistent, because kernel thinks the owner is not current.

I would assert on that.

Quoted 4 lines

EINVAL That would be a glibc bug calling unlock pi for a non futex,
which has non pi waiters in the kernel.

That one was explicitely there from the very beginning.

I would also assert on this.

Quoted 3 lines

And as I demonstrated in the other mail, it's easy to corrupt state w/o glibc even being able to notice. So you better handle that gracefully instead of making utterly stupid assumptions.

The assumptions are predicated on a particular design that doesn't seem to match your expectations. I accept that in this case you're correct. We should be catching state corruption and asserting. It's useful and prevents the program from continuing to corrupt other potentially more important program state.

As I mentioned before I'm not overly worried about a few extra instructions in the hot path. I am worried about programs that run as if they were correct but in fact are corrupting state. Debugging this is both costly and painful.

Nobody has looked at this code in years, likely because all parties thought they were done, but had in fact agreed to distinct expectations and assumptions about the implementation.

I want it fix, and I'm in a position to move resources to fix it.

Nobody has looked at this code in years, likely because all parties thought they were done, but had in fact agreed to distinct expectations and assumptions about the implementation.

I want it fix, and I'm in a position to move resources to fix it.

I will make my personal opinion clear:

- Internal defects should raise immediate assertions.

- Real problems like resource availability, deadlocks, and other recoverable errors should result in the API returning an appropriate error code that must not diverge from the POSIX definitions for those codes (when such a definition exists).

I'm not a believer in "only the hot path matters", there are such things as robustness and error detection, and they matter.

Quoted 9 lines · Carlos O'Donell

I will make my personal opinion clear:

- Internal defects should raise immediate assertions.

- Real problems like resource availability, deadlocks, and other recoverable errors should result in the API returning an appropriate error code that must not diverge from the POSIX definitions for those codes (when such a definition exists).

Quoted 2 lines

I'm not a believer in "only the hot path matters", there are such things as robustness and error detection, and they matter.

Awesome. In case of doubt though, I would prefer a return to an assert, just in case userspace actually does know wtf its doing ;-)

Granted, that seems to be very rare, but still, its entirely annoying for those few people who do care to get dead programs.

Alternatively, we could have something like you have for the allocator (which is, afaik, also considered a hot path) these env variables like MALLOC_CHECK_ to influence this edge behaviour.

Quoted 28 lines · Thomas Gleixner

Dave reported recently that the trinity syscall fuzzer triggers a warning in the rtmutex code via the futex syscall.

It took me quite a while to understand the issue, until I was able to write a minimalistic reproducer.

The first two patches address the issues and the third one is adding an unrelated sanity check to prevent user space from assigning PI futexes to kernel threads.

I ran it through my usual tests (except of one, see below), Darrens futex tester and it holds up against a 400 threads trinity whacking for well above 12hrs now.

Staring three days into futex.c/rtmutex.c and a few GB of traces definitly brings one in a lousy mood. But I discovered two things which made me outright grumpy:

2) glibc fun

While writing an isolated test case for the trinity wreckage, I found out that glibc has an interesting misfeature:

strace tells me:

   futex(0x600e00, FUTEX_LOCK_PI_PRIVATE, 1) = -1 EINVAL (Invalid argument)

Quoted 1 line

but the return value of pthread_mutex_lock() is 0

So something is clearly wrong there - however, were you looking at the comments (sorry, I mean the C code), or the implementation (all the ASM)? The only way I've been able to be sure in the past is to delete the ASM files and recompile using the C files. Hopefully we'll be able to drop all the ASM in the pthread calls soonish (measured in years in glibc development time scales).... sigh.

Quoted 4 lines

Yay, for another master piece of trainwreck engineering!

I checked the glibc source and of course neither the lock nor the unlock path gets any error code from the syscall propagated.

Quoted 6 lines

The handling of -EDEADLOCK is even more impressive. Instead of propagating it to the caller something in the guts of glibc calls pause().

     futex(0x601300, FUTEX_LOCK_PI_PRIVATE, 1) = -1 EDEADLK (Resource deadlock avoided)
     pause(

Gotta love comments like these though - such trust!:

	/* The mutex is locked.  The kernel will now take care of
           everything. */

IIRC, glibc takes the approach that if this operation fails, there is no way for it to recovery "properly", and so it chooses to:

	/* Delay the thread indefinitely. */

I believe the thinking goes that if we get to here, then the lock is in an inconsistent state (between kernel and userspace). I don't have an answer for why pausing forever would be preferable to returning an error however...

Quoted 5 lines

So any kind of futex wreckage which is not detectable by glibc itself ends up in a disaster one way or the other. How is Joe user of this stuff who reads the manpages supposed to find out that the kernel detected an inconsistent user space variable?

Quoted 4 lines

If someone of the glibc folks can be bothered to look after that, I'm happy to provide the simple test cases, but I'm sure that looking at the code which simply ignores or pauses on kernel error return values is enough to figure out why its broken.

Was there a spot where it ignores it completely? I suppose if it's anything other than ESRCH or EDEADLK... yuck...

Quoted 3 lines

This does not only apply to the PI version, the bog standard futexes have error returns from the kernel as well, which are handled in the same absurd way.

We do have the attention of some of the new glibc maintainers with the requeue PI work, and some redhat folks are digging into other PI related spec issues. I'll bring this up in those discussions and see if there might be something we can do here.

Quoted 15 lines

Quoted 6 lines

The handling of -EDEADLOCK is even more impressive. Instead of propagating it to the caller something in the guts of glibc calls pause().

     futex(0x601300, FUTEX_LOCK_PI_PRIVATE, 1) = -1 EDEADLK (Resource deadlock avoided)
     pause(

Gotta love comments like these though - such trust!:

	/* The mutex is locked.  The kernel will now take care of
           everything. */

IIRC, glibc takes the approach that if this operation fails, there is no way for it to recovery "properly", and so it chooses to:

Quoted 5 lines

	/* Delay the thread indefinitely. */

I believe the thinking goes that if we get to here, then the lock is in an inconsistent state (between kernel and userspace). I don't have an answer for why pausing forever would be preferable to returning an error however...

What error would we return?

This particular case is a serious error for which we have no good error code to return to userspace. It's an implementation defect, a bug, we should probably assert instead of pausing.

We can't cancel the stuck thread because pthread_mutex_lock is not a cancellation point.

In practice the rest of the application can make forward progress with a single thread stuck. You can attach the debugger and inspect state, so it's useful from that perspective.

Quoted 5 lines

Quoted 3 lines

I believe the thinking goes that if we get to here, then the lock is in an inconsistent state (between kernel and userspace). I don't have an answer for why pausing forever would be preferable to returning an error however...

What error would we return?

EDEADLK is a valid user return for pthread_mutex_lock() as per:

http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html

Quoted 3 lines

This particular case is a serious error for which we have no good error code to return to userspace. It's an implementation defect, a bug, we should probably assert instead of pausing.

No, its perfectly fine to have a lock sequence abort with -EDEADLK. Userspace should release its locks and re-attempt.

You can implement usable locking schemes using this error, like wound/wait locking.

Quoted 6 lines

We can't cancel the stuck thread because pthread_mutex_lock is not a cancellation point.

In practice the rest of the application can make forward progress with a single thread stuck. You can attach the debugger and inspect state, so it's useful from that perspective.

That's just totally braindead. Return EDEADLK to userspace already, let the user deal with it.

Quoted 6 lines · Peter Zijlstra

Quoted 5 lines

Quoted 3 lines

I believe the thinking goes that if we get to here, then the lock is in an inconsistent state (between kernel and userspace). I don't have an answer for why pausing forever would be preferable to returning an error however...

What error would we return?

Quoted 3 lines

EDEADLK is a valid user return for pthread_mutex_lock() as per:

http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html

How is that correct? It isn't a deadlock we've detected but inconsistent state between glibc and the kernel. In this case glibc should assert. Delaying indefinitely with pause() never seems correct (despite that being what we do today).

Quoted 11 lines · Carlos O'Donell

Quoted 9 lines · Peter Zijlstra

Quoted 5 lines

Quoted 3 lines

I believe the thinking goes that if we get to here, then the lock is in an inconsistent state (between kernel and userspace). I don't have an answer for why pausing forever would be preferable to returning an error however...

What error would we return?

EDEADLK is a valid user return for pthread_mutex_lock() as per:

http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html

Quoted 4 lines

How is that correct? It isn't a deadlock we've detected but inconsistent state between glibc and the kernel. In this case glibc should assert. Delaying indefinitely with pause() never seems correct (despite that being what we do today).

If there is inconsistent state detected then the kernel will return -EPERM or -EINVAL. So lets put inconsistent state aside.

In glibc you only can detect the simple AA dead lock, i.e lock owner tries to lock the lock it owns again. Trivial, right ?

But glibc has no idea which lock chains are involved and might lead to a dead lock caused by nested locking, simplest and most popular being ABBA.

The kernel can (if the implementation is fixed, patch is available already) very well detect ABBA and even more complex nested lock deadlocks. So it rightfully returns -EDEADLK and that is completely correct versus the spec and the call site can do something about it.

And that's not different from the glibc detected AA deadlock at all. It's just detected by a different mechanism.

On kernel side we currently provide this service only for the PI futexes because we have a kernel side state representation as long as the user space state is not corrupted.

Back then when it was implemented the dead lock detection actually worked and was agreed on by both sides - kernel and glibc - to be usefull and essential to the whole endavour.

Quoted 2 lines

No, its perfectly fine to have a lock sequence abort with -EDEADLK. Userspace should release its locks and re-attempt.

I agree. If I can prove that it's actually a deadlock, and that unlock/relock will work to fix it, then we can arrange for glibc to return EDEADLK.

Quoted 6 lines · Carlos O'Donell

Quoted 2 lines

No, its perfectly fine to have a lock sequence abort with -EDEADLK. Userspace should release its locks and re-attempt.

I agree. If I can prove that it's actually a deadlock, and that unlock/relock will work to fix it, then we can arrange for glibc to return EDEADLK.

The only reason the kernel would return EDEADLK is because its walked the lock graph and determined its well, a deadlock.

I agree. Something is wrong. There are *few* cases where we might probe the kernel to test for things, but you'd only see that failed futex syscall once. If this is repeating for each call to pthread_mutex_lock, then I would appreciate a test case I could use to debug this and then stick into the regression tests for glibc.

Quoted 8 lines

IIRC, glibc takes the approach that if this operation fails, there is no way for it to recovery "properly", and so it chooses to:

	/* Delay the thread indefinitely. */

I believe the thinking goes that if we get to here, then the lock is in an inconsistent state (between kernel and userspace). I don't have an answer for why pausing forever would be preferable to returning an error however...

What error would we return?

This particular case is a serious error for which we have no good error code to return to userspace. It's an implementation defect, a bug, we should probably assert instead of pausing.

Quoted 5 lines

What error would we return?

This particular case is a serious error for which we have no good error code to return to userspace. It's an implementation defect, a bug, we should probably assert instead of pausing.

Errm.

http://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_mutex_lock.html

The pthread_mutex_lock() function may fail if:

[EDEADLK]
The current thread already owns the mutex.

That's a exactly the error code, which the kernel returns when it detects a deadlock.

And glibc returns EDEADLK at a lot of places already. So in that case it's not a serious error? Because it's detected by glibc. You can't be serious about that.

So why is a kernel detected deadlock different? Because it detects not only AA, it detects ABBA and more. But it's still a dead lock. And while posix spec only talks about AA, it's the very same issue.

So why not propagate this to the caller so he gets an alert right away instead of letting him attach a debugger, and scratch his head and lookup glibc source to find out why the hell glibc called pause.

Quoted 26 lines · Thomas Gleixner

Quoted 5 lines

What error would we return?

This particular case is a serious error for which we have no good error code to return to userspace. It's an implementation defect, a bug, we should probably assert instead of pausing.

Errm.

http://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_mutex_lock.html

The pthread_mutex_lock() function may fail if:

[EDEADLK]
The current thread already owns the mutex.

That's a exactly the error code, which the kernel returns when it detects a deadlock.

And glibc returns EDEADLK at a lot of places already. So in that case it's not a serious error? Because it's detected by glibc. You can't be serious about that.

So why is a kernel detected deadlock different? Because it detects not only AA, it detects ABBA and more. But it's still a dead lock. And while posix spec only talks about AA, it's the very same issue.

Quoted 3 lines

So why not propagate this to the caller so he gets an alert right away instead of letting him attach a debugger, and scratch his head and lookup glibc source to find out why the hell glibc called pause.

http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html

The pthread_mutex_lock() function may fail if:

[EDEADLK]
A deadlock condition was detected or the current thread already owns the mutex.

Which is explicitly wider than the AA recursion and fully supports the full lock graph traversal we do.

Quoted 27 lines · Peter Zijlstra

Quoted 26 lines · Thomas Gleixner

Quoted 5 lines

What error would we return?

This particular case is a serious error for which we have no good error code to return to userspace. It's an implementation defect, a bug, we should probably assert instead of pausing.

Errm.

http://pubs.opengroup.org/onlinepubs/7908799/xsh/pthread_mutex_lock.html

The pthread_mutex_lock() function may fail if:

[EDEADLK]
The current thread already owns the mutex.

That's a exactly the error code, which the kernel returns when it detects a deadlock.

And glibc returns EDEADLK at a lot of places already. So in that case it's not a serious error? Because it's detected by glibc. You can't be serious about that.

So why is a kernel detected deadlock different? Because it detects not only AA, it detects ABBA and more. But it's still a dead lock. And while posix spec only talks about AA, it's the very same issue.

Quoted 5 lines

Quoted 3 lines

So why not propagate this to the caller so he gets an alert right away instead of letting him attach a debugger, and scratch his head and lookup glibc source to find out why the hell glibc called pause.

http://pubs.opengroup.org/onlinepubs/009695399/functions/pthread_mutex_lock.html

Yuck. I should not have used the first link Gurgle brought up.