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 for Android: free password hash cracker in your pocket

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

Message-ID: <1334178715.23924.308.camel@gandalf.stny.rr.com>
Date:	Wed, 11 Apr 2012 17:11:55 -0400
From:	Steven Rostedt <rostedt@...dmis.org>
To:	Juri Lelli <juri.lelli@...il.com>
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 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.

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.

-- Steve

> 
> 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/