Skip to content

Commit a23ba90

Browse files
Davidlohr Buesotorvalds
Davidlohr Bueso
authored and
torvalds
committed
locking/rtmutex: replace top-waiter and pi_waiters leftmost caching
... with the generic rbtree flavor instead. No changes in semantics whatsoever. Link: http://lkml.kernel.org/r/20170719014603.19029-10-dave@stgolabs.net Signed-off-by: Davidlohr Bueso <dbueso@suse.de> Acked-by: Peter Zijlstra (Intel) <peterz@infradead.org> Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: Linus Torvalds <torvalds@linux-foundation.org>
1 parent 2161573 commit a23ba90

File tree

7 files changed

+27
-44
lines changed

7 files changed

+27
-44
lines changed

‎include/linux/init_task.h‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -175,9 +175,8 @@ extern struct cred init_cred;
175175

176176
#ifdef CONFIG_RT_MUTEXES
177177
# define INIT_RT_MUTEXES(tsk) \
178-
.pi_waiters = RB_ROOT, \
179-
.pi_top_task = NULL, \
180-
.pi_waiters_leftmost = NULL,
178+
.pi_waiters = RB_ROOT_CACHED, \
179+
.pi_top_task = NULL,
181180
#else
182181
# define INIT_RT_MUTEXES(tsk)
183182
#endif

‎include/linux/rtmutex.h‎

Lines changed: 5 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -22,18 +22,17 @@ extern int max_lock_depth; /* for sysctl */
2222
* The rt_mutex structure
2323
*
2424
* @wait_lock: spinlock to protect the structure
25-
* @waiters: rbtree root to enqueue waiters in priority order
26-
* @waiters_leftmost: top waiter
25+
* @waiters: rbtree root to enqueue waiters in priority order;
26+
* caches top-waiter (leftmost node).
2727
* @owner: the mutex owner
2828
*/
2929
struct rt_mutex {
3030
raw_spinlock_t wait_lock;
31-
struct rb_root waiters;
32-
struct rb_node *waiters_leftmost;
31+
struct rb_root_cached waiters;
3332
struct task_struct *owner;
3433
#ifdef CONFIG_DEBUG_RT_MUTEXES
3534
int save_state;
36-
const char *name, *file;
35+
const char *name, *file;
3736
int line;
3837
void *magic;
3938
#endif
@@ -84,7 +83,7 @@ do { \
8483

8584
#define __RT_MUTEX_INITIALIZER(mutexname) \
8685
{ .wait_lock = __RAW_SPIN_LOCK_UNLOCKED(mutexname.wait_lock) \
87-
, .waiters = RB_ROOT \
86+
, .waiters = RB_ROOT_CACHED \
8887
, .owner = NULL \
8988
__DEBUG_RT_MUTEX_INITIALIZER(mutexname) \
9089
__DEP_MAP_RT_MUTEX_INITIALIZER(mutexname)}

‎include/linux/sched.h‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -812,8 +812,7 @@ struct task_struct {
812812

813813
#ifdef CONFIG_RT_MUTEXES
814814
/* PI waiters blocked on a rt_mutex held by this task: */
815-
struct rb_root pi_waiters;
816-
struct rb_node *pi_waiters_leftmost;
815+
struct rb_root_cached pi_waiters;
817816
/* Updated under owner's pi_lock and rq lock */
818817
struct task_struct *pi_top_task;
819818
/* Deadlock detection and priority inheritance handling: */

‎kernel/fork.c‎

Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1462,8 +1462,7 @@ static void rt_mutex_init_task(struct task_struct *p)
14621462
{
14631463
raw_spin_lock_init(&p->pi_lock);
14641464
#ifdef CONFIG_RT_MUTEXES
1465-
p->pi_waiters = RB_ROOT;
1466-
p->pi_waiters_leftmost = NULL;
1465+
p->pi_waiters = RB_ROOT_CACHED;
14671466
p->pi_top_task = NULL;
14681467
p->pi_blocked_on = NULL;
14691468
#endif

‎kernel/locking/rtmutex-debug.c‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -58,7 +58,7 @@ static void printk_lock(struct rt_mutex *lock, int print_owner)
5858

5959
void rt_mutex_debug_task_free(struct task_struct *task)
6060
{
61-
DEBUG_LOCKS_WARN_ON(!RB_EMPTY_ROOT(&task->pi_waiters));
61+
DEBUG_LOCKS_WARN_ON(!RB_EMPTY_ROOT(&task->pi_waiters.rb_root));
6262
DEBUG_LOCKS_WARN_ON(task->pi_blocked_on);
6363
}
6464

‎kernel/locking/rtmutex.c‎

Lines changed: 11 additions & 24 deletions
Original file line numberDiff line numberDiff line change
@@ -271,10 +271,10 @@ rt_mutex_waiter_equal(struct rt_mutex_waiter *left,
271271
static void
272272
rt_mutex_enqueue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)
273273
{
274-
struct rb_node **link = &lock->waiters.rb_node;
274+
struct rb_node **link = &lock->waiters.rb_root.rb_node;
275275
struct rb_node *parent = NULL;
276276
struct rt_mutex_waiter *entry;
277-
int leftmost = 1;
277+
bool leftmost = true;
278278

279279
while (*link) {
280280
parent = *link;
@@ -283,15 +283,12 @@ rt_mutex_enqueue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)
283283
link = &parent->rb_left;
284284
} else {
285285
link = &parent->rb_right;
286-
leftmost = 0;
286+
leftmost = false;
287287
}
288288
}
289289

290-
if (leftmost)
291-
lock->waiters_leftmost = &waiter->tree_entry;
292-
293290
rb_link_node(&waiter->tree_entry, parent, link);
294-
rb_insert_color(&waiter->tree_entry, &lock->waiters);
291+
rb_insert_color_cached(&waiter->tree_entry, &lock->waiters, leftmost);
295292
}
296293

297294
static void
@@ -300,20 +297,17 @@ rt_mutex_dequeue(struct rt_mutex *lock, struct rt_mutex_waiter *waiter)
300297
if (RB_EMPTY_NODE(&waiter->tree_entry))
301298
return;
302299

303-
if (lock->waiters_leftmost == &waiter->tree_entry)
304-
lock->waiters_leftmost = rb_next(&waiter->tree_entry);
305-
306-
rb_erase(&waiter->tree_entry, &lock->waiters);
300+
rb_erase_cached(&waiter->tree_entry, &lock->waiters);
307301
RB_CLEAR_NODE(&waiter->tree_entry);
308302
}
309303

310304
static void
311305
rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
312306
{
313-
struct rb_node **link = &task->pi_waiters.rb_node;
307+
struct rb_node **link = &task->pi_waiters.rb_root.rb_node;
314308
struct rb_node *parent = NULL;
315309
struct rt_mutex_waiter *entry;
316-
int leftmost = 1;
310+
bool leftmost = true;
317311

318312
while (*link) {
319313
parent = *link;
@@ -322,15 +316,12 @@ rt_mutex_enqueue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
322316
link = &parent->rb_left;
323317
} else {
324318
link = &parent->rb_right;
325-
leftmost = 0;
319+
leftmost = false;
326320
}
327321
}
328322

329-
if (leftmost)
330-
task->pi_waiters_leftmost = &waiter->pi_tree_entry;
331-
332323
rb_link_node(&waiter->pi_tree_entry, parent, link);
333-
rb_insert_color(&waiter->pi_tree_entry, &task->pi_waiters);
324+
rb_insert_color_cached(&waiter->pi_tree_entry, &task->pi_waiters, leftmost);
334325
}
335326

336327
static void
@@ -339,10 +330,7 @@ rt_mutex_dequeue_pi(struct task_struct *task, struct rt_mutex_waiter *waiter)
339330
if (RB_EMPTY_NODE(&waiter->pi_tree_entry))
340331
return;
341332

342-
if (task->pi_waiters_leftmost == &waiter->pi_tree_entry)
343-
task->pi_waiters_leftmost = rb_next(&waiter->pi_tree_entry);
344-
345-
rb_erase(&waiter->pi_tree_entry, &task->pi_waiters);
333+
rb_erase_cached(&waiter->pi_tree_entry, &task->pi_waiters);
346334
RB_CLEAR_NODE(&waiter->pi_tree_entry);
347335
}
348336

@@ -1657,8 +1645,7 @@ void __rt_mutex_init(struct rt_mutex *lock, const char *name,
16571645
{
16581646
lock->owner = NULL;
16591647
raw_spin_lock_init(&lock->wait_lock);
1660-
lock->waiters = RB_ROOT;
1661-
lock->waiters_leftmost = NULL;
1648+
lock->waiters = RB_ROOT_CACHED;
16621649

16631650
if (name && key)
16641651
debug_rt_mutex_init(lock, name, key);

‎kernel/locking/rtmutex_common.h‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -45,31 +45,31 @@ struct rt_mutex_waiter {
4545

4646
static inline int rt_mutex_has_waiters(struct rt_mutex *lock)
4747
{
48-
return !RB_EMPTY_ROOT(&lock->waiters);
48+
return !RB_EMPTY_ROOT(&lock->waiters.rb_root);
4949
}
5050

5151
static inline struct rt_mutex_waiter *
5252
rt_mutex_top_waiter(struct rt_mutex *lock)
5353
{
5454
struct rt_mutex_waiter *w;
5555

56-
w = rb_entry(lock->waiters_leftmost, struct rt_mutex_waiter,
57-
tree_entry);
56+
w = rb_entry(lock->waiters.rb_leftmost,
57+
struct rt_mutex_waiter, tree_entry);
5858
BUG_ON(w->lock != lock);
5959

6060
return w;
6161
}
6262

6363
static inline int task_has_pi_waiters(struct task_struct *p)
6464
{
65-
return !RB_EMPTY_ROOT(&p->pi_waiters);
65+
return !RB_EMPTY_ROOT(&p->pi_waiters.rb_root);
6666
}
6767

6868
static inline struct rt_mutex_waiter *
6969
task_top_pi_waiter(struct task_struct *p)
7070
{
71-
return rb_entry(p->pi_waiters_leftmost, struct rt_mutex_waiter,
72-
pi_tree_entry);
71+
return rb_entry(p->pi_waiters.rb_leftmost,
72+
struct rt_mutex_waiter, pi_tree_entry);
7373
}
7474

7575
#else

0 commit comments

Comments
 (0)