misc/24641: pthread_rwlock_rdlock can deadlock

[Earl Chew]

Daniel Eischen wrote:
> POSIX says that:
> 
>   If the Thread Execution Scheduling option is supported, and
>   the threads involved in the lock are executing with the scheduling
>   policies SCHED_FIFO or SCHED_RR, the calling thread shall not
>   acquire the lock if a writer holds the lock or if writers of
>   higher or equal priority are blocked on the lock; otherwise,
>   the calling thread shall acquire the lock.

Call this P1.

> Forget about the writer's priority for a moment; we don't
> currently honor that.  And FYI, SCHED_OTHER in FreeBSD is
> SCHED_RR.
> 
> POSIX also says that:
> 
>   A thread may hold multiple concurrent read locks on rwlock (that
>   is, successfully call the pthread_rwlock_rdlock() function n
>   times). If so, the application shall ensure that the thread
>   performs matching unlocks (that is, it calls the
>   pthread_rwlock_unlock() function n times).

Call this P2.

I interpret P2 as requiring rdlock() to be recursive. That is, once
a thread acquires a rdlock(), it can do so repeatedly, as long as it
performs the correct number of matching unlocks().

I interpret P1 as giving wrlock()s preference over rdlocks() for
a particular lock.

> It isn't clear to me that this means that a subsequent rdlock
> request while there are writers blocked on the lock succeeds.

Hmm... reading P2 again, I can see how you could be right.

However, it appears counter-intuitive to me that if a thread has already
acquired a rdlock(), and the rdlock() is recursive, that a subsequent
call should fail.

Failure should indicate that the lock could not be acquired. But the
thread _already_ has the lock! So it's hard to explain why the
subsequent call should fail (given the requirement that the
rdlock be recursive).

> It may seem trivial to implement this, but when you consider
> that there may be a lot of readers then it is not so trivial.
> In order to implement it, you need to know whether a thread
> owns the rdlock and have a recurse count for it.

Hmm... doesn't P2 already require you to support recursion?

> And threads
> may own multiple read locks.  You would have to track all
> of them and it would add a bit of overhead having to search
> the owned read locks (and they don't have to be taken and
> released in order so you'd have to search the entire queue).

I don't see how either P1 or P2 requires this behaviour. What am
I missing?

Earl