lockdep: Maintain read/write states for lock_acquires
cover 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.
PATCH 1/6 lockdep: Remove redundant read checks.
1) In kernel/lockdep.c::validate_chain()
ret = check_deadlock(curr, hlock, lock, hlock->read);
ret = 2 only if hlock->read = 2.
Hence,
if (ret == 2) hlock->read = 2;
is redundant, hence can be removed.
2) In kernel/lockdep.c::check_prevs_add(curr, next)
if (hlock->read != 2) check_prev_add(curr, hlock, next, distance);
Thus, check_prev_add is called only when hlock->read != 2.
Quoted 1 line
From the conclusions of 2),
kernel/lockdep.c::check_prev_add(curr, prev, next, distance) gets called iff prev->read != 2.
Hence, in kernel/lockdep.c::check_prev_add(curr, prev, next, distance)
if (prev->read == 2) return 1;
is redunant, hence can be removed.
---
kernel/lockdep.c | 9 +-------- 1 files changed, 1 insertions(+), 8 deletions(-)
kernel/lockdep.c +1 -8
@@ -1496,7 +1496,7 @@ check_prev_add(struct task_struct *curr, struct held_lock *prev,* write-lock never takes any other locks, then the reads are * equivalent to a NOP. */ -if (next->read ==2 || prev->read ==2 ) +if (next->read ==2 )return 1 ;/* * Is the <prev> -> <next> dependency already present?
@@ -1754,13 +1754,6 @@ static int validate_chain(struct task_struct *curr, struct lockdep_map *lock,if (!ret)return 0 ;/* -* Mark recursive read, as we jump over it when -* building dependencies (just like we jump over -* trylock entries): -*/ -if (ret ==2 ) - hlock->read =2 ; -/* * Add dependency only if this lock is not the head * of the chain, and if it's not a secondary read-lock: */
PATCH 2/6 lockdep: Remove strict read checks.
In reply to Gautham R ShenoyRead locks would cause IRQ inversion problems only when they're being taken in a IRQ context. So, except for this case, skip the strict read checks for every other case.
---
kernel/lockdep.c | 13 +++++++------ 1 files changed, 7 insertions(+), 6 deletions(-)
kernel/lockdep.c +7 -6
@@ -1986,8 +1986,6 @@ static int RECLAIM_FS_verbose(struct lock_class *class)return 0 ; } -#define STRICT_READ_CHECKS 1 -static int (*state_verbose_f[])(struct lock_class *class) = { #define LOCKDEP_STATE(__STATE) \ __STATE##_verbose,
@@ -2032,9 +2030,13 @@ mark_lock_irq(struct task_struct *curr, struct held_lock *this,/* * Validate that the lock dependencies don't have conflicting usage * states. +* +* Skip the part if it's a read_lock with LOCK_ENABLED_XXX. +* We'll do that check when a write variant of the same lock is taken, +* or we take the read variant of lock in the LOCK_USED_IN_XXX state. */ -if ((!read || !dir ||STRICT_READ_CHECKS ) && - !usage (curr, this, excl_bit,state_name (new_bit & ~1 ))) +if (!(read && dir) && !usage (curr, this, excl_bit, +state_name (new_bit & ~1 )))return 0 ;/*
@@ -2044,8 +2046,7 @@ mark_lock_irq(struct task_struct *curr, struct held_lock *this,if (!valid_state (curr, this, new_bit, excl_bit +1 ))return 0 ; -if (STRICT_READ_CHECKS && - !usage (curr, this, excl_bit +1 , +if (!usage (curr, this, excl_bit +1 ,state_name (new_bit +1 )))return 0 ; }
PATCH 3/6 lockdep: Annotate Read/write states
In reply to Gautham R ShenoyCurrently we do not save the recursive read dependencies in the dependency chain. As a result, a deadlock caused by the following chains are not spotted, since we never have the chain 1 in our dependency list.
1: Rlock(A)-->lock(B)
2: lock(B) --> Wlock(A), where A is a recursive read lock.
Before adding the Recursive Read locks to the dependency chains, we need to distinguish them from the normal read locks since the conflicting states for these two are quite different.
Currently the read/write status of a lock while it's acquired is denoted by a monotonically increasing variable where
0 - WRITE
1 - READ
2 - RECURSIVE READ.
In this patch, we propose to modify this distinction from a monotonically increasing variable to a bit mask where0x1 - WRITE0x2 - READ0x4 - RECURSIVE READ.
This helps us to define the conflicting states for each lock with ease:
Thereby, the conflicting states for a given states are defined as follows:
Conflicting_states(WRITE): RECURSIVE_READ | READ | WRITE Conflicting_states(READ): READ | WRITE
Conflicting_states(RECURSIVE_READ): WRITE
Also, we use one more bit in the bitmask to distinguish the first recursive read in the current chain from the others, since it is sufficient to add only this dependency to the dependency list.
---
include/linux/lockdep.h | 103 ++++++++++++++++++++++++++++++++++++----------- kernel/lockdep.c | 52 +++++++++++++----------- 2 files changed, 107 insertions(+), 48 deletions(-)
include/linux/lockdep.h +78 -25
@@ -209,7 +209,7 @@ struct held_lock {*/ unsigned int irq_context:2; /* bit 0 - soft, bit 1 - hard */ unsigned int trylock:1; - unsigned int read:2; /* see lock_acquire() comment */ + unsigned int rw_state:4; /* see lock states comment */ unsigned int check:2; /* see lock_acquire() comment */ unsigned int hardirqs_off:1; };
@@ -259,14 +259,49 @@ extern void lockdep_init_map(struct lockdep_map *lock, const char *name, lockdep_init_map(&(lock)->dep_map, #lock, \ (lock)->dep_map.key, sub) +/* lock_state bits */ +#define _W_ 0 +#define _R_ (_W_ + 1) +#define _RR_ (_W_ + 2) +#define _FIRST_RR_ (_W_ + 3) + +#define get_lock_state (lock_bit) (1 << lock_bit) +/* -* Acquire a lock. +* lock states: * -* Values for "read": +* A given lock can have one of the following states: +* - STATE_WRITE: Exclusive Write. +* - STATE_READ: Non-recursive read. +* - STATE_RECURSIVE_READ: Recursive Read. +* +* These states are represented as bitmasks +*/ +#define STATE_WRITE get_lock_state(_W_) +#define STATE_READ get_lock_state(_R_) +#define STATE_RECURSIVE_READ get_lock_state(_RR_) + +/* Helpers to check the current lock's state */ +#define is_simple_read (state) (state & STATE_READ) +#define is_rec_read (state) (state & STATE_RECURSIVE_READ) +#define is_read (state) (is_simple_read(state) | is_rec_read(state)) +#define is_write (state) (state & STATE_WRITE) + +/* +* When maintaining dependency chains for locks acquired with +* STATE_RECURSIVE_READ state, we add a particular instance of the lock to the +* dependency chain only if it's the first recursive read instance in the +* current dependency chain. We don't add recurring instances of the lock +* to the dependency chains. +*/ +#define STATE_FIRST_RECURSIVE_READ get_lock_state(_FIRST_RR_) +#define is_first_rec_read (state) (state & STATE_FIRST_RECURSIVE_READ) + +/* +* Acquire a lock. * -* 0: exclusive (write) acquire -* 1: read-acquire (no recursion allowed) -* 2: read-acquire with same-instance recursion allowed +* Values for "rw_state": +* See comment for lock states: * * Values for check: *
@@ -275,7 +310,7 @@ extern void lockdep_init_map(struct lockdep_map *lock, const char *name,* 2: full validation */ extern void lock_acquire (struct lockdep_map *lock,unsigned int subclass, -int trylock,int read,int check, +int trylock,int rw_state,int check,struct lockdep_map *nest_lock,unsigned long ip); extern void lock_release(struct lockdep_map *lock, int nested,
@@ -419,11 +454,15 @@ static inline void print_irqtrace_events(struct task_struct *curr)#ifdef CONFIG_DEBUG_LOCK_ALLOC # ifdef CONFIG_PROVE_LOCKING -# define spin_acquire (l, s, t, i) lock_acquire(l, s, t, 0, 2, NULL, i) -# define spin_acquire_nest (l, s, t, n, i) lock_acquire(l, s, t, 0, 2, n, i) +# define spin_acquire (l, s, t, i) \ + lock_acquire(l, s, t, STATE_WRITE, 2, NULL, i) +# define spin_acquire_nest (l, s, t, n, i) \ + lock_acquire(l, s, t, STATE_WRITE, 2, n, i)# else -# define spin_acquire (l, s, t, i) lock_acquire(l, s, t, 0, 1, NULL, i) -# define spin_acquire_nest (l, s, t, n, i) lock_acquire(l, s, t, 0, 1, NULL, i) +# define spin_acquire (l, s, t, i) \ + lock_acquire(l, s, t, STATE_WRITE, 1, NULL, i) +# define spin_acquire_nest (l, s, t, n, i) \ + lock_acquire(l, s, t, STATE_WRITE, 1, NULL, i)# endif # define spin_release (l, n, i) lock_release(l, n, i)#else
@@ -433,11 +472,15 @@ static inline void print_irqtrace_events(struct task_struct *curr)#ifdef CONFIG_DEBUG_LOCK_ALLOC # ifdef CONFIG_PROVE_LOCKING -# define rwlock_acquire (l, s, t, i) lock_acquire(l, s, t, 0, 2, NULL, i) -# define rwlock_acquire_read (l, s, t, i) lock_acquire(l, s, t, 2, 2, NULL, i) +# define rwlock_acquire (l, s, t, i) \ + lock_acquire(l, s, t, STATE_WRITE, 2, NULL, i) +# define rwlock_acquire_read (l, s, t, i) \ + lock_acquire(l, s, t, STATE_RECURSIVE_READ, 2, NULL, i)# else -# define rwlock_acquire (l, s, t, i) lock_acquire(l, s, t, 0, 1, NULL, i) -# define rwlock_acquire_read (l, s, t, i) lock_acquire(l, s, t, 2, 1, NULL, i) +# define rwlock_acquire (l, s, t, i) \ + lock_acquire(l, s, t, STATE_WRITE, 1, NULL, i) +# define rwlock_acquire_read (l, s, t, i) \ + lock_acquire(l, s, t, STATE_RECURSIVE_READ, 1, NULL, i)# endif # define rwlock_release (l, n, i) lock_release(l, n, i)#else
@@ -448,9 +491,11 @@ static inline void print_irqtrace_events(struct task_struct *curr)#ifdef CONFIG_DEBUG_LOCK_ALLOC # ifdef CONFIG_PROVE_LOCKING -# define mutex_acquire (l, s, t, i) lock_acquire(l, s, t, 0, 2, NULL, i) +# define mutex_acquire (l, s, t, i) \ + lock_acquire(l, s, t, STATE_WRITE, 2, NULL, i)# else -# define mutex_acquire (l, s, t, i) lock_acquire(l, s, t, 0, 1, NULL, i) +# define mutex_acquire (l, s, t, i) \ + lock_acquire(l, s, t, STATE_WRITE, 1, NULL, i)# endif # define mutex_release (l, n, i) lock_release(l, n, i)#else
@@ -460,11 +505,15 @@ static inline void print_irqtrace_events(struct task_struct *curr)#ifdef CONFIG_DEBUG_LOCK_ALLOC # ifdef CONFIG_PROVE_LOCKING -# define rwsem_acquire (l, s, t, i) lock_acquire(l, s, t, 0, 2, NULL, i) -# define rwsem_acquire_read (l, s, t, i) lock_acquire(l, s, t, 1, 2, NULL, i) +# define rwsem_acquire (l, s, t, i) \ + lock_acquire(l, s, t, STATE_WRITE, 2, NULL, i) +# define rwsem_acquire_read (l, s, t, i) \ + lock_acquire(l, s, t, STATE_READ, 2, NULL, i)# else -# define rwsem_acquire (l, s, t, i) lock_acquire(l, s, t, 0, 1, NULL, i) -# define rwsem_acquire_read (l, s, t, i) lock_acquire(l, s, t, 1, 1, NULL, i) +# define rwsem_acquire (l, s, t, i) \ + lock_acquire(l, s, t, STATE_WRITE, 1, NULL, i) +# define rwsem_acquire_read (l, s, t, i) \ + lock_acquire(l, s, t, STATE_READ, 1, NULL, i)# endif # define rwsem_release (l, n, i) lock_release(l, n, i)#else
@@ -475,9 +524,11 @@ static inline void print_irqtrace_events(struct task_struct *curr)#ifdef CONFIG_DEBUG_LOCK_ALLOC # ifdef CONFIG_PROVE_LOCKING -# define lock_map_acquire (l) lock_acquire(l, 0, 0, 0, 2, NULL, _THIS_IP_) +# define lock_map_acquire (l) \ + lock_acquire(l, 0, 0, STATE_WRITE, 2, NULL, _THIS_IP_)# else -# define lock_map_acquire (l) lock_acquire(l, 0, 0, 0, 1, NULL, _THIS_IP_) +# define lock_map_acquire (l) \ + lock_acquire(l, 0, 0, STATE_WRITE, 1, NULL, _THIS_IP_)# endif # define lock_map_release (l) lock_release(l, 1, _THIS_IP_)#else
@@ -489,13 +540,15 @@ static inline void print_irqtrace_events(struct task_struct *curr)# define might_lock (lock) \ do { \ typecheck(struct lockdep_map *, &(lock)->dep_map); \ - lock_acquire(&(lock)->dep_map, 0, 0, 0, 2, NULL, _THIS_IP_); \ + lock_acquire(&(lock)->dep_map, 0, 0, STATE_WRITE, \ + 2, NULL, _THIS_IP_); \ lock_release(&(lock)->dep_map, 0, _THIS_IP_); \ } while (0)# define might_lock_read (lock) \ do { \ typecheck(struct lockdep_map *, &(lock)->dep_map); \ - lock_acquire(&(lock)->dep_map, 0, 0, 1, 2, NULL, _THIS_IP_); \ + lock_acquire(&(lock)->dep_map, 0, 0, STATE_READ, \ + 2, NULL, _THIS_IP_); \ lock_release(&(lock)->dep_map, 0, _THIS_IP_); \ } while (0)#else
kernel/lockdep.c +29 -23
169 lines not on this page · raw message
PATCH 4/6 lockdep: Seperate lock ids for read/write acquires.
In reply to Gautham R ShenoyThe key of a dependency chain is obtained from the keys of the locks involved in the dependency chains. The keys of the locks are defined as their lock_class id's. Since we don't distinguish between the read/write acquire of a particular lock, we get the same key's for two different chains involving the same locks in the same dependency order, but in different read/write states.
Eg:
lock(A) ---> Rlock(B) lock(A) ---> Wlock(B)
Fix this by distinguishing between the read/write acquires of a lock by defining the lock's key as follows:
class_id + is_read_lock(lock) * MAX_LOCKDEP_KEYS.
Thus for the purpose of chain key calculation, a lock's key can be in the range 1 to 2*MAX_LOCKDEP_KEYS - 1.
---
include/linux/lockdep.h | 14 ++++++++++++++ kernel/lockdep.c | 19 +++++++++++++++++-- 2 files changed, 31 insertions(+), 2 deletions(-)
include/linux/lockdep.h +14 -0
@@ -163,6 +163,7 @@ struct lock_chain { };#define MAX_LOCKDEP_KEYS_BITS 13 +/* * Subtract one because we offset hlock->class_idx by 1 in order * to make 0 mean no class. This avoids overflowing the class_idx
@@ -170,6 +171,19 @@ struct lock_chain {*/ #define MAX_LOCKDEP_KEYS ((1UL << MAX_LOCKDEP_KEYS_BITS) - 1) +/* +* A lock's class id is used to calculate the chain-key. Since we need to +* differentiate between the chains which contain the read acquire of +* a lock from the chains having write acquire of the same lock, +* we offset the class_idx by MAX_LOCKDEP_KEYS if it is a read acquire. +* +* Thus the the lock's key during a chain-key calculation can be in the range +* 1 to 2 * MAX_LOCKDEP_KEYS - 1. +* +* LOCKDEP_CHAIN_KEY_BITS holds the number of bits required to +* represent this range. +*/ +#define LOCKDEP_CHAIN_KEY_BITS (MAX_LOCKDEP_KEYS_BITS + 1)struct held_lock {/* * One-way hash of the dependency chain up to this point. We
kernel/lockdep.c +17 -2
@@ -286,8 +286,8 @@ static struct list_head chainhash_table[CHAINHASH_SIZE];* unique. */ #define iterate_chain_key (key1, key2) \ - (((key1) << MAX_LOCKDEP_KEYS_BITS) ^ \ - ((key1) >> (64-MAX_LOCKDEP_KEYS_BITS)) ^ \ + (((key1) << LOCKDEP_CHAIN_KEY_BITS) ^ \ + ((key1) >> (64 - LOCKDEP_CHAIN_KEY_BITS)) ^ \ (key2))void lockdep_off (void )
@@ -1802,6 +1802,9 @@ static void check_chain_key(struct task_struct *curr)if (DEBUG_LOCKS_WARN_ON (id >=MAX_LOCKDEP_KEYS ))return ; +if (is_read (hlock->rw_state)) + id +=MAX_LOCKDEP_KEYS ; +if (prev_hlock && (prev_hlock->irq_context != hlock->irq_context)) chain_key =0 ;
@@ -2614,6 +2617,18 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,if (DEBUG_LOCKS_WARN_ON (id >=MAX_LOCKDEP_KEYS ))return 0 ; +/* +* Factor in the read/write state in the chain key calculation. +* +* Two chain containing lock dependencies in the same order can +* still differ due to their read/write state +* eg: lock(A)->Rlock(B) is different from lock(A)->Wlock(B) +* +* Hence distinguish between such chains. +*/ +if (is_read (rw_state)) + id +=MAX_LOCKDEP_KEYS ; + chain_key = curr->curr_chain_key;if (!depth) {if (DEBUG_LOCKS_WARN_ON (chain_key !=0 ))
PATCH 5/6 lockdep: Maintain rw_state entries in locklist
In reply to Gautham R ShenoyThe dependencies are currently maintained using a structure named locklist. For a dependency A --> B, it saves B's lock_class in an entry that would be linked to A's locks_after list.
Enhance this infrastructure to save the read/write states of A and B for each dependency. Also, rename a variable in locklist to reflect it's usage better.
Also change the parameter list to add_lock_to_list() to allow us record the r/w values for the two locks involved in a dependency.
---
include/linux/lockdep.h | 16 ++++++++++++++ kernel/lockdep.c | 52 ++++++++++++++++++++++++++++++----------------- kernel/lockdep_proc.c | 4 ++-- 3 files changed, 50 insertions(+), 22 deletions(-)
include/linux/lockdep.h +15 -1
@@ -141,14 +141,28 @@ struct lockdep_map { };/* +* lock_list: List of the other locks taken before or after a particular lock. +* +* @entry - List head linking this particular entry to the +* lock_after/lock_before list of a particular lock. +* @dep_class - lock_class of the lock which is involved in a dependency with +* the lock to which this entry is linked to. +* @this_lock_rw_state - The read/write state of the lock to which this +* dependency entry belongs to. +* @dep_lock_rw_state - The read/write state of the lock with the lock class +* dep_class in this particular dependecy involvement. +* +* * Every lock has a list of other locks that were taken after it. * We only grow the list, never remove from it: */ struct lock_list {struct list_head entry; -struct lock_class *class; +struct lock_class *dep_class;struct stack_trace trace;int distance; +unsigned int this_lock_rw_state:3 ; +unsigned int dep_lock_rw_state:3 ; };/*
kernel/lockdep.c +33 -19
146 lines not on this page · raw message
kernel/lockdep_proc.c +2 -2
@@ -109,8 +109,8 @@ static int l_show(struct seq_file *m, void *v)list_for_each_entry (entry, &class->locks_after, entry) {if (entry->distance ==1 ) { -seq_printf (m," -> [%p] " , entry->class->key); -print_name (m, entry->class); +seq_printf (m," -> [%p] " , entry->dep_class->key); +print_name (m, entry->dep_class);seq_puts (m,"\n" ); } }
PATCH 6/6 lockdep: Consider the rw_state of lock while validating the chain.
In reply to Gautham R ShenoyCurrently, while validating a particular dependency chain, we check if by following the the locks_after list of current lock A, we can reach one of the previous locks in the current chain.
i.e, if current chain is : A --> B -->C, then starting from C -->locks_after, can we reach B.
However, if there are dependency chains:
C--> D --> Rlock(E) Rlock(E) --> A,
where E is a Recursive Read lock, this chain cannot cause a deadlock because of the recursive nature of E.
However, if the dependency chain was
Wlock(E) --> A,
it would have caused a deadlock.
We solve this problem by defining conflicting states of each lock where
Conflict(WRITE) = WRITE, READ, RECURSIVE_READ
Conflict(READ) = WRITE, READ
Conflict(RECURSIVE_READ)= WRITE
Thus, while traversing the locks_after chain of a particular lock A, we traverse through only those entries in the chain where the state of the lock A in the entry conflicts with the state of the lock A with which we started the traversal.
---
include/linux/lockdep.h | 20 ++++++++++++++++ kernel/lockdep.c | 60 +++++++++++++++++++++++++++++------------------ 2 files changed, 57 insertions(+), 23 deletions(-)
include/linux/lockdep.h +20 -0
@@ -326,6 +326,26 @@ extern void lockdep_init_map(struct lockdep_map *lock, const char *name,#define is_first_rec_read (state) (state & STATE_FIRST_RECURSIVE_READ)/* +* Conflicting states: +* - A Recursive read conflicts only with a write. +* - A Non-recursive read can conflict with a non-recursive read and write. +* - A Write conflicts with Write, simple read and recursive read. +*/ + +#define get_rec_read_conflict (state) \ + ((((is_write(state)) << (_RR_ - _W_))) & STATE_RECURSIVE_READ) + +#define get_simple_read_conflict (state) \ + (((((is_write(state)) << (_R_ - _W_))) | (is_simple_read(state))) \ + & STATE_READ) +#define get_write_conflict (state) STATE_WRITE + +#define get_lock_conflict_states (state) \ + (get_rec_read_conflict(state) | \ + get_simple_read_conflict(state) | \ + get_write_conflict(state)) + +/* * Acquire a lock. * * Values for "rw_state":
kernel/lockdep.c +37 -23
147 lines not on this page · raw message
Quoted 1 line · Gautham R Shenoy
Feedback is very much appreciated.
Awesome work :-)
Didn't spot any obvious (in so far as that that word can apply to this series) boo-boos.
More in-depth review will follow a bit later.