Sergey Vojtovich writes:

...

# First spin wait, hoping to get the mutex without yielding. os_compare_and_swap_ulint(&mutex->waiters, 0, 1); Where did you see "os_compare_and_swap_ulint(&mutex->waiters, 0, 1)"? FWICS waiters of InnoDB mutex are non-atomic loads/stores.

mutex_enter_func() calls mutex_spin_wait() which does mutex_set_waiters(mutex, 1): mutex_set_waiters(mutex_t *mutex, ulint n) { #ifdef INNODB_RW_LOCKS_USE_ATOMICS if (n) { os_compare_and_swap_ulint(&mutex->waiters, 0, 1); } else { os_compare_and_swap_ulint(&mutex->waiters, 1, 0); } So that is where I saw it. I do not understand what you mean with "waiters of InnoDB mutex are non-atomic loads/stores" ?

...

os_compare_and_swap_ulint() is defined as either __sync_bool_compare_and_swap() or atomic_cas_ulong(), both of which implies a full barrier. So ENTER looks ok. See above: waiters loads/stores are not atomic, so no memory barriers at all.

Well, the code is hopelessly complicated with various #ifdef cases. I do not claim to have verified all cases that they have the correct barrier for ENTER. However, I found that in my particular build, mutex_set_waiters used the INNODB_RW_LOCKS_USE_ATOMICS case, which uses os_compare_and_swap_ulint(). And that is defined in os0sync.h as either __sync_bool_compare_and_swap(), which is documented as having a full barrier; or atomic_cas_ulong(), which I think is the MySQL's own atomics, which on x86 were implemented using LOCK prefix last time I looked, so also full barrier. Why do you think there is no full barrier? Did I miss something?

...

This is consistent with the observations in MDEV-7026. A thread is waiting for wakeup on a mutex that is already marked free. Ok, so you say this hang is now repeatable with x86 because we changed ACQUIRE -> RELEASE. I assume you were actually able to reproduce it on x86.

I have not tried reproducing on x86. Note that on x86 we changed it from full barrier (XCHG instruction) to aquire (which does nothing if my test program is to be believed). The documentation only guarantees AQUIRE for __sync_lock_test_and_set(), true, but in reality it seems to have been full barrier on x86, which would explain why it worked before. I am speculating that some of the hangs that started to appear recently could be due to this change. At least one case, that I researched in considerable depth, can be explained adequately in this way. It seems likely that this is the explanation, but I cannot be sure.

Note that we also added mysterious os_isync to mutex_exit_func, which is supposed to be among other things ACQUIRE. But on x86 it is no-op with a comment: /* Performance regression was observed at some conditions for Intel architecture. Disable memory barrier for Intel architecture for now. */

I saw the added isync. I think this is also wrong. isync is about speculative execution, one can use it with a conditional instruction to prevent instructions being executed ahead of the completion of a load. But the place I saw, it was used incorrectly, without the conditional instruction. I did not dig deeper into this though, as even if used correctly it would still not be the full barrier that seems to be required here.

Does it explain server lockups at startup or during normal operations? Could you elaborate the problem you're talking about?

So my guess is that on x86, the full barriers are in place, and the mutex code works without losing wakeups. However, at some point there was some problem, maybe some specific compiler or architecture or whatever, and the sync_arr_wake_threads_if_sema_free() hack was implemented. I am guessing that things work correctly on x86 because the sync_arr_wake_threads_if_sema_free() is fundamentally broken. It is not active during startup (and maybe shutdown?). And it does not work if the server error monitor thread happens to also get stuck on a mutex. So I think missing barriers on x86 would have been discovered in commonly used binaries. And the sync_arr_wake_threads_if_sema_free() has been able to hide problems in rare architectures. That is my guess. As to the concrete problems: 1. MDEV-7026 there is a lockup during startup. I believe this is visible because the server error monitor thread is not running at this point. 2. In a user hang I investigated in detail, a thread was waiting on log_sys->mutex, but no other thread was holding that mutex (consistent with lost wakeup). The server error monitor thread was itself stuck on a mutex, which would prevent sync_arr_wake_threads_if_sema_free() from hiding the problem.

with Power8. I'd vote for putting full memory barrier into mutex_exit_func() and probably remove that ugly hack with sync_arr_wake_threads_if_sema_free. :(

Yes, I agree, that is what I meant. I agree that it was probably broken on PowerPC also before the change. But it looked to me like we had full barriers on x86 before the change (even if it was not guaranteed by documentation).

Though a proper solution should never issue full memory barriers for mutex lock/unlock. I suggested different idea, but that's for 10.1:

This sounds very strange. Are you sure? Normally, mutex lock/unlock is assumed to be a full barrier. If my reading of the code is correct, this is also how it was implemented on x86. It seems _very_ likely that part of the InnoDB code relies on such full barriers. It does not seem safe to me to change it. Posix thread operations are for example defined to imply full barrier. Or do you mean that there should be _one_ full barrier implied in mutex_enter(), and one in mutex_exit()? But there are currently more than one, and this should be optimised? That would make sense. Though my personal opinion is that the InnoDB mutex implementation has always been a piece of garbage, and rather than mess more with it, it should be replaced with something simpler and better (isn't this what the InnoDB team is already working on?). - Kristian.

Sergey Vojtovich writes:

Never seen this before. InnoDB of 5.5 and InnoDB/XtraDB of 10.0 both have:

UNIV_INTERN void mutex_set_waiters( /*==============*/ ib_mutex_t* mutex, /*!< in: mutex */ ulint n) /*!< in: value to set */ { volatile ulint* ptr; /* declared volatile to ensure that the value is stored to memory */ ut_ad(mutex);

ptr = &(mutex->waiters);

os_wmb;

*ptr = n; /* Here we assume that the write of a single word in memory is atomic */ }

But I confirm that I see this in XtraDB of 5.5.

Interesting. Clearly I got confused between 5.5/10.0 and the XtraDB/InnoDB distinction. There might be more to learn here. In fact, I was looking mostly at the assembler output, to be sure I correctly understood all the #ifdef magic and actual instructions generated, and only refering back to source code for the description. Looks like storage/innobase have a __sync_lock_test_and_set() (with a full barrier on x86) in the mutex_test_and_set() instead. But making sure that all the different combinations are correct looks like it could be a lot of fun...

Agree. What we basically do is: lock_word= 0; // atomic store with release barrier isync; if (waiters) // non-atomic load

But that's wrong, isn't it? Doesn't the isync need to go _after_ the conditional branch? isync discards any following speculated execution. So if you load a value and make a conditional jump that depends on the value loaded, then no instructions can start until after the load completed. Because the load must complete before the conditional can be decided. This effectively gives LoadLoad and LoadStore order. But isync _before_ a conditional - I am not sure that will do anything. But I guess, this was your point, as well ;-)

Here we need to ensure that store completes before load. But: - there is no isync on x86 - isync doesn't guarantee StoreLoad order (there are many articles about this)

Agree.

So full memory barrier seem to be the only option.

Yes...

...

2. In a user hang I investigated in detail, a thread was waiting on log_sys->mutex, but no other thread was holding that mutex (consistent with lost wakeup). The server error monitor thread was itself stuck on a mutex, which would prevent sync_arr_wake_threads_if_sema_free() from hiding the problem. Strange... Monty should have fixed this. Error monitor thread should call log_get_lsn_nowait(), which basically does trylock. Do you happen to have call trace?

This investigation was some time ago (maybe 1-2 months). It seems likely that this was a version before Monty's log_get_lsn_nowait() (eg. 10.0.14 has it, but not 10.0.13).

Do you have a link to articles that define full memory barrier for mutex

Hm, I don't really have a reference to point to. Well, I believe the posix thread definition says that a number of operations ensure full memory ordering across them.

lock/unlock? Probably that was quite outdated writing. See e.g.:

Outdated, perhaps, but aquire/release is AFAIK a relatively new concept. Mutexes, and InnoDB source code predates that? I'm not sure that C++ coming up with some strange new semantics for their language has much bearing on legacy code? But I agree it would be nice to have some references about "old-style" mutexes implying full memory barrier, so that it's not just me...

http://en.cppreference.com/w/cpp/atomic/memory_order

...Atomic load with memory_order_acquire or stronger is an acquire operation. The lock() operation on a Mutex is also an acquire operation...

...Atomic store with memory_order_release or stronger is a release operation. The unlock() operation on a Mutex is also a release operation...

Interesting... so C++ defines a "Mutex" with different semantics than what is usually understood with eg. pthread_mutex...

Full memory barriers are way too heavy even for mutexes. All we need to to is to ensure that: - all loads following lock are performed after lock (acquire) - all stores preceding unlock are completed before unlock (release)

Are you sure? Note that if this is true, then it means that there is _no_ way to get a StoreLoad barrier using only normal mutex operations. That seems odd... I know I have seen, and written, code that depends on lock/unlock being full barrier. How can we be sure that such code doesn't also exist in InnoDB? Though I agree that full barrier is a lot more expensive than just LoadLoad or StoreStore, and best avoided if possible (I even blogged about that not so long ago). - Kristian.

Sergey Vojtovich writes:

According to history ACQUIRE -> RELEASE fix appeared in 10.0.13 and fix for log_get_lsn() appeared in 10.0.14. Both fixes appeared similtaneously in 5.5.40.

So runtime hangs should be solved both in 5.5 and 10.0. This leaves hangs during startup, which are unfortunate but not as critical as runtime hangs.

Are there any other known hangs?

If you are going to argue for deliberately keeping broken mutex_enter() / mutex_exit() in MariaDB, I will stay out of the discussion. I was only trying to get Buildbot green so that I can push my completely unrelated fixes for 10.0. - Kristian.

Kristian Nielsen writes:

Hm, I don't really have a reference to point to. Well, I believe the posix thread definition says that a number of operations ensure full memory ordering across them.

I guess I was thinking of this: http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_... It is somewhat wague: "The following functions synchronize memory with respect to other threads: ...". I thought some more about this. Consider a simple example: THREAD A THREAD B lock(M) foo() unlock(M) lock(M) bar() unlock(M) Here, I would expect that bar() in B can see all changes made by foo() in A, because B locked the mutex after A released it. This requires that stores in foo() are completed before loads in bar() begin, effectively a full barrier. However, this can be implemented in different ways. It doesn't have to be done with an explicit full barrier CPU instruction, as long as the correct semantics is preserved. So let's consider unlock() with release semantics, and lock() with aquire semantics: unlock(M): __sync_lock_release(M->lock_word) lock(M): while (__sync_lock_test_and_set(M->lock_word, 1)) /* wait for lock */ ; The release barrier ensures that stores in foo() will complete before the store of lock_word. The acquire barrier in the wait loop ensures that loads in bar() cannot start until a load in the while loop has seen the store to lock_word. Thus, loads in bar() become ordered after stores in foo(), effectively a full memory barrier even though no explicit full barrier instruction was needed. So you may be right that the implementation needs no explicit full memory barrier in theory... On the other hand, I have implemented code that _does_ assume a full barrier for each operation individually (see wait_for_commit::wakeup_subsequent_commits2() in 10.0 for an example). Others could have done the same. Reviewing all InnoDB code to make sure it is not the case, it does not really seem feasible... The burden will be on the one who changes InnoDB locking primitives to prove that such change is safe with respect to the expectations of the code that uses those primitives. This is made all the more challenging by the semantics being somewhat unclear, and the main platform x86 mostly doing "full barrier" by default on atomic operations like test-and-set. - Kristian.

Hi Kristian, On Fri, Nov 07, 2014 at 08:40:36AM +0100, Kristian Nielsen wrote:

Kristian Nielsen writes:

...

Hm, I don't really have a reference to point to. Well, I believe the posix thread definition says that a number of operations ensure full memory ordering across them.

I guess I was thinking of this:

http://pubs.opengroup.org/onlinepubs/9699919799/basedefs/V1_chap04.html#tag_...

It is somewhat wague: "The following functions synchronize memory with respect to other threads: ...".

I thought some more about this. Consider a simple example:

THREAD A THREAD B lock(M) foo() unlock(M) lock(M) bar() unlock(M)

Here, I would expect that bar() in B can see all changes made by foo() in A, because B locked the mutex after A released it. This requires that stores in foo() are completed before loads in bar() begin, effectively a full barrier.

However, this can be implemented in different ways. It doesn't have to be done with an explicit full barrier CPU instruction, as long as the correct semantics is preserved.

So let's consider unlock() with release semantics, and lock() with aquire semantics:

unlock(M): __sync_lock_release(M->lock_word)

lock(M): while (__sync_lock_test_and_set(M->lock_word, 1)) /* wait for lock */ ;

The release barrier ensures that stores in foo() will complete before the store of lock_word. The acquire barrier in the wait loop ensures that loads in bar() cannot start until a load in the while loop has seen the store to lock_word.

Thus, loads in bar() become ordered after stores in foo(), effectively a full memory barrier even though no explicit full barrier instruction was needed.

So you may be right that the implementation needs no explicit full memory barrier in theory... Right. But I just realized that I'm a bit lost in terms now. When you say full memory barrier I assume memory_order_seq_cst. Is there any other type of barrier was available before C11/C++11 acquire/release semantics were introduced?

On the other hand, I have implemented code that _does_ assume a full barrier for each operation individually (see wait_for_commit::wakeup_subsequent_commits2() in 10.0 for an example). Others could have done the same. Reviewing all InnoDB code to make sure it is not the case, it does not really seem feasible...

The burden will be on the one who changes InnoDB locking primitives to prove that such change is safe with respect to the expectations of the code that uses those primitives. This is made all the more challenging by the semantics being somewhat unclear, and the main platform x86 mostly doing "full barrier" by default on atomic operations like test-and-set.

*** I MAY BE VERY WRONG NOW, GUESS BASED STATEMENTS FOLLOW *** If we abstract from platform specific implementation of barriers and think in logical acquire/release terms... In fact there is additional requirement for pthread_mutex_lock() which I omitted before: stores that appear after ACQUIRE must be actually performed after ACQUIRE. Manual says: ... memory_order_acquire: A load operation with this memory order performs the acquire operation on the affected memory location: prior writes made to other memory locations by the thread that did the release become visible in this thread. ... As you can see it only defines that memory LOADS become visible, but doesn't define anything wrt stores performed by current thread. This makes me think that stores are allowed to be postponed, but they are never executed in advance. If that's the case, your code is correct wrt memory barriers. Regards, Sergey

MARK CALLAGHAN writes:

Did this ever get resolved? I enjoyed reading this, you did a nice job explaining the problem.

It was resolved for x86 in the sense that the code was reverted to the old behaviour. The code is semantically incorrect (uses the wrong barriers), but it happens to generate the correct assembler code on x86 due to its rather strong memory ordering. It is probably still incorrect for some other architectures (eg. multi-core ARM).

Linux had some fun in this area recently -- https://groups.google.com/forum/#!topic/mechanical-sympathy/QbmpZxp6C64

Right. This is very complex technology, very few developers have a full understanding of these issues. And the ones that do can still easily make mistakes.

The InnoDB thread that checked waiting threads once per second for wakeup was a hack to fix a misunderstood bug. Fortunately the amazing Yasufumi

Right. The InnoDB mutex implementation could benefit a lot from being rewritten, I think (and you have written about this as well). I think I heard it mention that MySQL@Oracle are actually working on this (but I do not know details). I am glad you enjoyed reading my write-up. - Kristian.

Stewart Smith writes:

...

It is probably still incorrect for some other architectures (eg. multi-core ARM).

What about POWER? It's officially supported by Maria now :)

There is special code for POWER (#ifdef), so it should work... - Kristian.

MARK CALLAGHAN writes:

What about ARM which has a much weaker memory model compared to x86?

Yes. There is in fact a bug about it: https://mariadb.atlassian.net/browse/MDEV-7658 - Kristian.