Re: [PATCH 12/16] rtmutex: turn the plist into an rb-tree.

From: Juri Lelli
Date: Sun Apr 22 2012 - 10:29:06 EST

On 04/11/2012 11:11 PM, Steven Rostedt wrote:
On Fri, 2012-04-06 at 09:14 +0200, Juri Lelli wrote:
From: Peter Zijlstra<peterz@xxxxxxxxxxxxx>

Turn the pi-chains from plist to rb-tree, in the rt_mutex code,
and provide a proper comparison function for -deadline and
-priority tasks.

I have to ask. Why not just add a rbtree with a plist? That is, add all
deadline tasks to the rbtree and all others to the plist. As plist has a
O(1) operation, and rbtree does not. We are making all RT tasks suffer
the overhead of the rbtree.

I basically got this patch from the v3 patchset and, since it applied
perfectly and came from Peter, I assumed it was the right way to go ;-).

As deadline tasks always win, the two may stay agnostic from each other.
Check first the rbtree, if it is empty, then check the plist.

This will become more predominant with the -rt tree as it converts most
the locks in the kernel to pi mutexes.

I see your point, but I'm not yet convinced that in the end the plist +
rbtree implementation would win. AFAIK, the only O(1) plist operation is
removal, beeing addition O(K) [K RT priorities]. Now, we have O(logn)
[n elements] operations for rbtrees and we speed-up search with the
leftmost pointer.
So, are we sure that add complexity (and related checks) is needed here?
I'm not against your point, I'm only asking :-).

Thanks a lot,

- Juri

This is done mainly because:
- classical prio field of the plist is just an int, which might
not be enough for representing a deadline;
- manipulating such a list would become O(nr_deadline_tasks),
which might be to much, as the number of -deadline task increases.

Therefore, an rb-tree is used, and tasks are queued in it according
to the following logic:
- among two -priority (i.e., SCHED_BATCH/OTHER/RR/FIFO) tasks, the
one with the higher (lower, actually!) prio wins;
- among a -priority and a -deadline task, the latter always wins;
- among two -deadline tasks, the one with the earliest deadline

Queueing and dequeueing functions are changed accordingly, for both
the list of a task's pi-waiters and the list of tasks blocked on
a pi-lock.

Signed-off-by: Peter Zijlstra<peterz@xxxxxxxxxxxxx>
Signed-off-by: Dario Faggioli<raistlin@xxxxxxxx>
Signed-off-by: Juri Lelli<juri.lelli@xxxxxxxxx>

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at