Skip to content

lockdep: Maintain read/write states for lock_acquires

Gautham R Shenoy lkml 1 version In review

Get series with b4
b4 am [email protected]

Versions newest first

  1. v1 Latest6 patches 1 replyIn review

Patches in v1 No applies recorded yet

#Subject and filesSizeRepliesApplied
1/6lockdep: Remove redundant read checks.kernel/lockdep.c+1 -80 replies
2/6lockdep: Remove strict read checks.kernel/lockdep.c+7 -60 replies
3/6lockdep: Annotate Read/write statesinclude/linux/lockdep.h kernel/lockdep.c+107 -480 replies
4/6lockdep: Seperate lock ids for read/write acquires.include/linux/lockdep.h kernel/lockdep.c+31 -20 replies
5/6lockdep: Maintain rw_state entries in locklistinclude/linux/lockdep.h kernel/lockdep.c kernel/lockdep_proc.c+50 -220 replies
6/6lockdep: Consider the rw_state of lock while validating the chain.include/linux/lockdep.h kernel/lockdep.c+57 -230 replies

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v1 yet.

Read the v1 thread

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.