Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitf611e8c

Browse files
fbqPeter Zijlstra
authored and
Peter Zijlstra
committed
lockdep: Take read/write status in consideration when generate chainkey
Currently, the chainkey of a lock chain is a hash sum of the class_idxof all the held locks, the read/write status are not taken in toconsideration while generating the chainkey. This could result into aproblem, if we have:P1(){read_lock(B);lock(A);}P2(){lock(A);read_lock(B);}P3(){lock(A);write_lock(B);}, and P1(), P2(), P3() run one by one. And when running P2(), lockdepdetects such a lock chain A -> B is not a deadlock, then it's added inthe chain cache, and then when running P3(), even if it's a deadlock, wecould miss it because of the hit of chain cache. This could be confirmedby self testcase "chain cached mixed R-L/L-W ".To resolve this, we use concept "hlock_id" to generate the chainkey, thehlock_id is a tuple (hlock->class_idx, hlock->read), which fits in a u16type. With this, the chainkeys are different is the lock sequences havethe same locks but different read/write status.Besides, since we use "hlock_id" to generate chainkeys, the chain_hlocksarray now store the "hlock_id"s rather than lock_class indexes.Signed-off-by: Boqun Feng <boqun.feng@gmail.com>Signed-off-by: Peter Zijlstra (Intel) <peterz@infradead.org>Link:https://lkml.kernel.org/r/20200807074238.1632519-15-boqun.feng@gmail.com
1 parentd4f200e commitf611e8c

File tree

1 file changed

+35
-18
lines changed

1 file changed

+35
-18
lines changed

‎kernel/locking/lockdep.c‎

Lines changed: 35 additions & 18 deletions
Original file line numberDiff line numberDiff line change
@@ -371,6 +371,21 @@ static struct hlist_head classhash_table[CLASSHASH_SIZE];
371371

372372
staticstructhlist_headchainhash_table[CHAINHASH_SIZE];
373373

374+
/*
375+
* the id of held_lock
376+
*/
377+
staticinlineu16hlock_id(structheld_lock*hlock)
378+
{
379+
BUILD_BUG_ON(MAX_LOCKDEP_KEYS_BITS+2>16);
380+
381+
return (hlock->class_idx | (hlock->read <<MAX_LOCKDEP_KEYS_BITS));
382+
}
383+
384+
staticinlineunsignedintchain_hlock_class_idx(u16hlock_id)
385+
{
386+
returnhlock_id& (MAX_LOCKDEP_KEYS-1);
387+
}
388+
374389
/*
375390
* The hash key of the lock dependency chains is a hash itself too:
376391
* it's a hash of all locks taken up to that lock, including that lock.
@@ -3202,7 +3217,10 @@ static inline void free_chain_hlocks(int base, int size)
32023217

32033218
structlock_class*lock_chain_get_class(structlock_chain*chain,inti)
32043219
{
3205-
returnlock_classes+chain_hlocks[chain->base+i];
3220+
u16chain_hlock=chain_hlocks[chain->base+i];
3221+
unsignedintclass_idx=chain_hlock_class_idx(chain_hlock);
3222+
3223+
returnlock_classes+class_idx-1;
32063224
}
32073225

32083226
/*
@@ -3228,12 +3246,12 @@ static inline int get_first_held_lock(struct task_struct *curr,
32283246
/*
32293247
* Returns the next chain_key iteration
32303248
*/
3231-
staticu64print_chain_key_iteration(intclass_idx,u64chain_key)
3249+
staticu64print_chain_key_iteration(u16hlock_id,u64chain_key)
32323250
{
3233-
u64new_chain_key=iterate_chain_key(chain_key,class_idx);
3251+
u64new_chain_key=iterate_chain_key(chain_key,hlock_id);
32343252

3235-
printk("class_idx:%d -> chain_key:%016Lx",
3236-
class_idx,
3253+
printk("hlock_id:%d -> chain_key:%016Lx",
3254+
(unsignedint)hlock_id,
32373255
(unsigned long long)new_chain_key);
32383256
returnnew_chain_key;
32393257
}
@@ -3250,27 +3268,27 @@ print_chain_keys_held_locks(struct task_struct *curr, struct held_lock *hlock_ne
32503268
hlock_next->irq_context);
32513269
for (;i<depth;i++) {
32523270
hlock=curr->held_locks+i;
3253-
chain_key=print_chain_key_iteration(hlock->class_idx,chain_key);
3271+
chain_key=print_chain_key_iteration(hlock_id(hlock),chain_key);
32543272

32553273
print_lock(hlock);
32563274
}
32573275

3258-
print_chain_key_iteration(hlock_next->class_idx,chain_key);
3276+
print_chain_key_iteration(hlock_id(hlock_next),chain_key);
32593277
print_lock(hlock_next);
32603278
}
32613279

32623280
staticvoidprint_chain_keys_chain(structlock_chain*chain)
32633281
{
32643282
inti;
32653283
u64chain_key=INITIAL_CHAIN_KEY;
3266-
intclass_id;
3284+
u16hlock_id;
32673285

32683286
printk("depth: %u\n",chain->depth);
32693287
for (i=0;i<chain->depth;i++) {
3270-
class_id=chain_hlocks[chain->base+i];
3271-
chain_key=print_chain_key_iteration(class_id,chain_key);
3288+
hlock_id=chain_hlocks[chain->base+i];
3289+
chain_key=print_chain_key_iteration(hlock_id,chain_key);
32723290

3273-
print_lock_name(lock_classes+class_id);
3291+
print_lock_name(lock_classes+chain_hlock_class_idx(hlock_id)-1);
32743292
printk("\n");
32753293
}
32763294
}
@@ -3319,7 +3337,7 @@ static int check_no_collision(struct task_struct *curr,
33193337
}
33203338

33213339
for (j=0;j<chain->depth-1;j++,i++) {
3322-
id=curr->held_locks[i].class_idx;
3340+
id=hlock_id(&curr->held_locks[i]);
33233341

33243342
if (DEBUG_LOCKS_WARN_ON(chain_hlocks[chain->base+j]!=id)) {
33253343
print_collision(curr,hlock,chain);
@@ -3368,7 +3386,6 @@ static inline int add_chain_cache(struct task_struct *curr,
33683386
structheld_lock*hlock,
33693387
u64chain_key)
33703388
{
3371-
structlock_class*class=hlock_class(hlock);
33723389
structhlist_head*hash_head=chainhashentry(chain_key);
33733390
structlock_chain*chain;
33743391
inti,j;
@@ -3411,11 +3428,11 @@ static inline int add_chain_cache(struct task_struct *curr,
34113428

34123429
chain->base=j;
34133430
for (j=0;j<chain->depth-1;j++,i++) {
3414-
intlock_id=curr->held_locks[i].class_idx;
3431+
intlock_id=hlock_id(curr->held_locks+i);
34153432

34163433
chain_hlocks[chain->base+j]=lock_id;
34173434
}
3418-
chain_hlocks[chain->base+j]=class-lock_classes;
3435+
chain_hlocks[chain->base+j]=hlock_id(hlock);
34193436
hlist_add_head_rcu(&chain->entry,hash_head);
34203437
debug_atomic_inc(chain_lookup_misses);
34213438
inc_chains(chain->irq_context);
@@ -3602,7 +3619,7 @@ static void check_chain_key(struct task_struct *curr)
36023619
if (prev_hlock&& (prev_hlock->irq_context!=
36033620
hlock->irq_context))
36043621
chain_key=INITIAL_CHAIN_KEY;
3605-
chain_key=iterate_chain_key(chain_key,hlock->class_idx);
3622+
chain_key=iterate_chain_key(chain_key,hlock_id(hlock));
36063623
prev_hlock=hlock;
36073624
}
36083625
if (chain_key!=curr->curr_chain_key) {
@@ -4749,7 +4766,7 @@ static int __lock_acquire(struct lockdep_map *lock, unsigned int subclass,
47494766
chain_key=INITIAL_CHAIN_KEY;
47504767
chain_head=1;
47514768
}
4752-
chain_key=iterate_chain_key(chain_key,class_idx);
4769+
chain_key=iterate_chain_key(chain_key,hlock_id(hlock));
47534770

47544771
if (nest_lock&& !__lock_is_held(nest_lock,-1)) {
47554772
print_lock_nested_lock_not_held(curr,hlock,ip);
@@ -5648,7 +5665,7 @@ static void remove_class_from_lock_chain(struct pending_free *pf,
56485665
inti;
56495666

56505667
for (i=chain->base;i<chain->base+chain->depth;i++) {
5651-
if (chain_hlocks[i]!=class-lock_classes)
5668+
if (chain_hlock_class_idx(chain_hlocks[i])!=class-lock_classes)
56525669
continue;
56535670
/*
56545671
* Each lock class occurs at most once in a lock chain so once

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp