Priority Inversion and Unlimited Spin of pthread_rwlock_t

[Peng Zheng]

On 2024/3/12 22:39, Florian Weimer wrote:
> * Peng Zheng:
> 
>> And the SCHED_OTHER writer was just about to enable the `__wrphase_futex` in
>> `__pthread_rwlock_wrlock_full` (just one ARM instruction away)
>> but never able to do that (the two readers ate nearly all available CPUs):
>>
>>    while ((r & PTHREAD_RWLOCK_WRPHASE) == 0
>>       && (r >> PTHREAD_RWLOCK_READER_SHIFT) == 0)
>>      {
>>        if (atomic_compare_exchange_weak_acquire (&rwlock->__data.__readers,
>>                          &r, r | PTHREAD_RWLOCK_WRPHASE))
>>      {
>>        atomic_store_relaxed (&rwlock->__data.__wrphase_futex, 1);  /* writer was stuck HERE! */
>>
>>        goto done;
>>      }
>>        /* TODO Back-off.  */
>>      }
> 
> Is this about filling in the TODO?

No, I forgot to remove inline comments from the original source.

It is about a low priority (SCHED_OTHER) writer, which was about to 
acquire its lock, preempted by high priority readers, and thus was not 
able to set `__wrphase_futex` to 1 (see IT IS PREEMPTED HERE comment).

   while ((r & PTHREAD_RWLOCK_WRPHASE) == 0
      && (r >> PTHREAD_RWLOCK_READER_SHIFT) == 0)
     {
       if (atomic_compare_exchange_weak_acquire (&rwlock->__data.__readers,
                         &r, r | PTHREAD_RWLOCK_WRPHASE))
     {
       /* IT IS PREEMPTED HERE */
       atomic_store_relaxed (&rwlock->__data.__wrphase_futex, 1);
       goto done;
     }
     }


And these two priority readers were stuck in a loop near the end of 
`__pthread_rwlock_rdlock_full` eating all available CPU.

   for (;;)
     {
       while (((wpf = atomic_load_relaxed (&rwlock->__data.__wrphase_futex))
           | PTHREAD_RWLOCK_FUTEX_USED) == (1 | PTHREAD_RWLOCK_FUTEX_USED))
       {/*omitted*/}
       if (ready)
              break;
       if ((atomic_load_acquire (&rwlock->__data.__readers)
        & PTHREAD_RWLOCK_WRPHASE) == 0)
             ready = true;
     }
   return 0;

Note that PTHREAD_RWLOCK_WRPHASE was already set by the preempted 
writer. That means `ready` is always false.

Note also that `__wrphase_futex` was not yet enabled by the preempted 
writer. That means these readers can not wait on futex to stop spinning.

This illustrates one of the several unlimited spin possibilities and I 
encounter two/three of them. If you are interested, I could provide 
corresponding postmortem debug sessions.

-- 
Peng Zheng