lockdep: Maintain read/write states for lock_acquires
Get series with b4
b4 am [email protected]Versions newest first
- v1 Latest6 patches 1 replyIn review
Patches in v1 No applies recorded yet
| # | Subject and files | Size | Replies | Applied |
|---|---|---|---|---|
| 1/6 | lockdep: Remove redundant read checks.kernel/ | +1 | 0 replies | |
| 2/6 | lockdep: Remove strict read checks.kernel/ | +7 | 0 replies | |
| 3/6 | lockdep: Annotate Read/write statesinclude/ kernel/ | +107 | 0 replies | |
| 4/6 | lockdep: Seperate lock ids for read/write acquires.include/ kernel/ | +31 | 0 replies | |
| 5/6 | lockdep: Maintain rw_state entries in locklistinclude/ kernel/ kernel/ | +50 | 0 replies | |
| 6/6 | lockdep: Consider the rw_state of lock while validating the chain.include/ kernel/ | +57 | 0 replies |
Reviews trailers per patch
No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.
Cover letter [RFC/PATCH 0/6] lockdep: Maintain read/write states for lock_acquires
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(-)
Signature · 2 lines
Thanks and Regards gautham.