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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:	Sun, 22 Apr 2012 16:28:56 +0200
From:	Juri Lelli <juri.lelli@...il.com>
To:	Steven Rostedt <rostedt@...dmis.org>
CC:	peterz@...radead.org, tglx@...utronix.de, mingo@...hat.com,
	oleg@...hat.com, fweisbec@...il.com, darren@...art.com,
	johan.eker@...csson.com, p.faure@...tech.ch,
	linux-kernel@...r.kernel.org, claudio@...dence.eu.com,
	michael@...rulasolutions.com, fchecconi@...il.com,
	tommaso.cucinotta@...up.it, nicola.manica@...i.unitn.it,
	luca.abeni@...tn.it, dhaval.giani@...il.com, hgu1972@...il.com,
	paulmck@...ux.vnet.ibm.com, raistlin@...ux.it,
	insop.song@...csson.com, liming.wang@...driver.com
Subject: Re: [PATCH 12/16] rtmutex: turn the plist into an rb-tree.

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@...radead.org>
>>
>> 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
>>     wins.
>>
>> 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@...radead.org>
>> Signed-off-by: Dario Faggioli<raistlin@...ux.it>
>> Signed-off-by: Juri Lelli<juri.lelli@...il.com>
>
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/