Messages in this thread |  | | | From | Gautham R Shenoy <> | | Subject | [RFC/PATCH 0/6] lockdep: Maintain read/write states for lock_acquires | | Date | Mon, 11 May 2009 18:09:25 +0530 |
| |
Hi,
Lockdep, while maintaining it's dependency chains does currently not differentiate between the read/write acquires of a lock. Thus a dependency rlock(A) ---> wlock(B) is treated the same as wlock(A) ---> rlock(B).
If the implementation of the reader writer lock is such that upon the arrival of a writer, it ensures that all the future readers will wait till the completion of the writer, this non-distinction between the read and the write acquires doesn't matter. This is because, the reads in such implementations aren't recursive, since a recursive-read can deadlock in the presence of a writer. i.e in : Thread1: rlock(A) ------------> rlock(A) Thread2: wlock(A) Thread 1 will end up blocking on the second rlock(A), while Thread 2 is blocked on wlock(A). The RW-Semaphores in the linux kernel are implemented in this fashion.
However, if the implementation of the reader-writer lock allows "reader-preference", i.e it allows the writer to grab the lock iff there are no readers in the system, the distinction between a read/write acquire may be necessary, since the implementation permits, read-side recursion as a side-effect. rwlocks in the linux kernel follow a similar implementation.
lockdep however refrains from making this read/write acquire distinction for such locks. It tries to solve the problem by not maintaining dependencies for the reads, and maintains dependencies only for the writes.
As a result, ABBA deadlocks of the following type, go unnoticed by lockdep:
Thread 1 ===================== read_lock(A); spin_lock(B); /* A-->B dependency is not maintained for reason mentioned */ +
Thread 2 ===================== spin_lock(B); write_lock(A); /* B-->A dependency maintained. But no cycle in graph.*/ Peter Zijlstra had a patch to solve this by considering the only the first recursive-read instance of a lock in the current context while maintaining the dependencies. http://lkml.org/lkml/2008/4/29/212
However, this had a nasty side effect since now, dependencies of the type: read_lock(A) --> spin_lock(B) spin_lock(B) --> read_lock(A) and it's variants would also be reported as a deadlock.
This patchset solves the problem by recording the read/write states of the locks acquired in a dependency.
i.e, for a dependency of the type spin_lock(B) --> read_lock(A),
in B's "locks_after" entry for this dependency, we not only store the class of A, but also store the the "rw-state" of both A and B. Ditto for A's "locks_before" entry.
We define three rw-states namely: STATE_WRITE STATE_READ STATE_RECURSIVE_READ.
For each of these states, we define a set of conflicting states which can cause a deadlock when involved in a dependency with the former . i.e, conflict_states(STATE_WRITE) = STATE_WRITE | STATE_READ | STATE_RECURSIVE_READ conflict_state(STATE_READ) = STATE_WRITE | STATE_READ conflict_state(STATE_RECURSIVE_READ) = STATE_WRITE So, when we're walking the dependency graph to see if there is a cycle in the graph, we follow only those entries in the "locks_after" list of a given lock, where this lock was acquired in a rw-state which conflicts with that lock's current rw-state.
i.e, if say lock A's current rw-state is STATE_RECURSIVE_READ, and the locks_after list for A looks something like this:
this_class: A
A->locks_after | | V --------------------------------------------------- | dep_class: B | | dep_rw_state: STATE_WRITE | | this_rw_state: STATE_WRITE | --------------------------------------------------- | | V --------------------------------------------------- | dep_class: C | | dep_rw_state: STATE_RECURSIVE_READ | | this_rw_state: STATE_RECURSIVE_READ | --------------------------------------------------- | | V --------------------------------------------------- | dep_class: D | | dep_rw_state: STATE_RECURSIVE_READ | | this_rw_state: STATE_WRITE | --------------------------------------------------- Here, we follow only the entries where dep_class is B and D since these are the only entries where A's rw_state (STATE_WRITE) conflicts with it's current rw_state (STATE_RECURSIVE_READ). However, if A's current rw_state had been STATE_WRITE, we would have followed all the three entries.
The patch-set has been tested against 2.6.30-rc3. It passes the boot-up self-test. However more test cases need to be added to the locking-self test which will be done in the future iterations of the patch.
Feedback is very much appreciated.
--- Gautham R Shenoy (6): lockdep: Consider the rw_state of lock while validating the chain. lockdep: Maintain rw_state entries in locklist lockdep: Seperate lock ids for read/write acquires. lockdep: Annotate Read/write states lockdep: Remove strict read checks. lockdep: Remove redundant read checks.
include/linux/lockdep.h | 153 +++++++++++++++++++++++++++++++------ kernel/lockdep.c | 193 +++++++++++++++++++++++++++++------------------ kernel/lockdep_proc.c | 4 - 3 files changed, 247 insertions(+), 103 deletions(-) -- Thanks and Regards gautham.
|  |