Created attachment 4606 [details]
Patch that fixes the problem for me

The patch is wrong.  Most likely just mips have wrong definition of the
atomic_compare_and_swap_bool macros where it doesn't tell the compiler that *mem
actually changes (missing "=m" (*mem) ? ).

It looks like the problem is not in the macro, the "m" (*mem) is actually there:

#define __arch_compare_and_exchange_xxx_32_int(mem, newval, oldval, rel, acq) \
     __asm__ __volatile__ (                                                   \
     ".set      push\n\t"                                                     \
     MIPS_PUSH_MIPS2                                                          \
     rel        "\n"                                                          \
     "1:\t"                                                                   \
     "ll        %0,%4\n\t"                                                    \
     "move      %1,$0\n\t"                                                    \
     "bne       %0,%2,2f\n\t"                                                 \
     "move      %1,%3\n\t"                                                    \
     "sc        %1,%4\n\t"                                                    \
     "beqz      %1,1b\n"                                                      \
     acq        "\n\t"                                                        \
     ".set      pop\n"                                                        \
     "2:\n\t"                                                                 \
              : "=&r" (__prev), "=&r" (__cmp)                                 \
              : "r" (oldval), "r" (newval), "m" (*mem)                        \
              : "memory")


If we look at the disassembled output of gcc, we see that in below loop (inside __new_sem_post), the "cur = isem->value" 
is taken out of the loop, as isem->value does not seem to change. 

The relevant code from sem_post:
 do
    {
      cur = isem->value; // <-- taken out of the loop
      if (isem->value == SEM_VALUE_MAX) //<--- taken out of the loop as well
        {
          __set_errno (EOVERFLOW);
          return -1;
        }
    }
  while (atomic_compare_and_exchange_bool_acq (&isem->value, cur + 1, cur));

And here the disassembly, with explanation:
0000e530 <sem_post>:
    e530:       3c1c0002        lui     gp,0x2
    e534:       279ceb00        addiu   gp,gp,-5376
    e538:       0399e021        addu    gp,gp,t9
    e53c:       8c860000        lw      a2,0(a0)        // a2 (=cur) = isem->value
    e540:       3c037fff        lui     v1,0x7fff
    e544:       3462ffff        ori     v0,v1,0xffff    // v0 = SEM_VALUE_MAX
    e548:       14c20007        bne     a2,v0,e568 <sem_post+0x38>  //check for overflow
    e54c:       24c50001        addiu   a1,a2,1         // a1 = cur + 1 (note: branch delay slot!!)

<-- code to return error in case of overflow
    e550:       8f84833c        lw      a0,-31940(gp)
    e554:       7c03e83b        rdhwr   v1,$29
    e558:       00831021        addu    v0,a0,v1
    e55c:       2404ffff        li      a0,-1
    e560:       10000021        b       e5e8 <sem_post+0xb8>
    e564:       2403004f        li      v1,79 -->

// Execution continues here after overflow check. Please note that the ll/sc combination
// is used, which is in fact atomic. Furthermore, it fetches 0(a0) again, which is isem->value.
    e568:       c0830000        ll      v1,0(a0)        

// And here is the problem!! It compares the just fetched value with a2, which is initialised
// at the beginning of the loop, but never loaded again. The fact that 'll' is used for the load
// above (instead of lw), makes me believe that the atomic_compare_and_exchange_bool_acq macro
// is in fact correct (the ll belongs to the macro, since it's a special instruction for
// atomic operations and not generated by gcc). 
    e56c:       14660006        bne     v1,a2,e588 <sem_post+0x58>
    e570:       00003821        move    a3,zero
    e574:       00a03821        move    a3,a1
    e578:       e0870000        sc      a3,0(a0)
    e57c:       10e0fffa        beqz    a3,e568 <sem_post+0x38>
    e580:       00000000        nop
    e584:       0000000f        sync
    ....

"m" (*mem) should be "+m" (*mem) since *mem is rw.

Indeed, the + is missing. This could cause statements after the macro to read a 
value from before the macro (as the compiler doesn't expect the macro to change it 
without the +, and therefore might use some old value stored in a register). 

But this is all within the same thread/instance: it doesn't fix the problem. What 
if a different thread changes isem->value?? The only way to tell the compiler 
(that I know of I must say;-)) is by means of the 'volatile' keyword.

"+m" and "=m"/"0" is not recommended, you should really use "=m" (*mem) ... "m"
(*mem).

And all you need to fix is exactly this, the atomic_* insn takes care of other
threads accessing the same field.
Even volatile wouldn't change anything.  You just load the value the field has
at some point in the current thread, compute the new value you want to use and then
atomic_* will succeed only if the memory has the same value as it had when it
has been loaded.

I understand that adding 'volatile' does not change anything to the behaviour of the macro, and that the atomic 
instructions take care of other threads _while inside the atomic_compare_and_exchange_bool_acq macro_. The problem 
is, that it doesn't take care of concurrency in the instructions before that.

without volatile the compiler optimizes the code to:
  cur = isem->value;
  if (isem->value == SEM_VALUE_MAX)
   {
     __set_errno (EOVERFLOW);
     return -1;
   }
// if we get a context switch here, and someone else increases isem->value, 
// we get a deadlock, because cur contains isem->value+1, and
// atomic_compare_and_exchange_bool_acq can never succeed.
  do
   {
   }
 while (atomic_compare_and_exchange_bool_acq (&isem->value, cur + 1, cur));


So, while it doesn't alter the behaviour of atomic_compare_and_exchange_bool_acq, it does put the 'cur = isem->value' 
statement inside the while loop. However, changing the patch as proposed does this as well (although for different 
reasons: now the compiler is aware that the macro itself (instead of other threads) can change isem->value).

Created attachment 4608 [details]
Adds *mem as an output to atomic macro's for MIPS

Thanks, I've applied the patch to the atomic macros.