Priority Lists for the RT mutex
Subsystems (3)
PATCH 1/1 Priority Lists for the RT mutex
Source: Daniel Walker <[email protected]> MontaVista Software, Inc Description:
This patch adds the priority list data structure from Inaky Perez-Gonzalez
to the Preempt Real-Time mutex.
the patch order is (starting with a 2.6.11 kernel tree),
patch-2.6.12-rc2
realtime-preempt-2.6.12-rc2-V0.7.44-01
include/linux/plist.h +310 -0
@@ -0,0 +1,310 @@ +/* +* Descending-priority-sorted double-linked list +* +* (C) 2002-2003 Intel Corp +* Inaky Perez-Gonzalez <[email protected]>. +* +* 2001-2005 (c) MontaVista Software, Inc. +* Daniel Walker <[email protected]> +* +* Licensed under the FSF's GNU Public License v2 or later. +* +* Based on simple lists (include/linux/list.h). +* +* +* This is a priority-sorted list of nodes; each node has a >= 0 +* priority from 0 (highest) to INT_MAX (lowest). The list itself has +* a priority too (the highest of all the nodes), stored in the head +* of the list (that is a node itself). +* +* Addition is O(1), removal is O(1), change of priority of a node is +* O(1). +* +* Addition and change of priority's order is really O(K), where K is +* a constant being the maximum number of different priorities you +* will store in the list. Being a constant, it means it is O(1). +* +* This list is really a list of lists: +* +* - The tier 1 list is the dp list (Different Priority) +* +* - The tier 2 list is the sp list (Same Priority) +* +* All the nodes in a SP list have the same priority, and all the DP +* lists have different priorities (and are sorted by priority, of +* course). +* +* Addition means: look for the DP node in the DP list for the +* priority of the node and append to the SP list corresponding to +* that node. If it is the first node of that priority, add it to the +* DP list in the right position and it will be the head of the SP +* list for his priority. +* +* Removal means remove it from the SP list corresponding to its +* prio. If it is the only one, it means its also the head and thus a +* DP node, so we remove it from the DP list. If it is the head but +* there are others in its SP list, then we remove it from both and +* get the first one of the SP list to be the new head. +* +* INT_MIN is the highest priority, 0 is the medium highest, INT_MAX +* is lowest priority. +* +* No locking is done, up to the caller. +* +* NOTE: This implementation does not offer as many interfaces as +* linux/list.h does -- it is lazily minimal. You are welcome to +* add them. +*/ + +#ifndef _LINUX_PLIST_H_ +#define _LINUX_PLIST_H_ + +#include <linux/kernel.h> +#include <linux/list.h> + +/* Priority-sorted list */ +struct plist { +int prio; +struct list_head dp_node; +struct list_head sp_node; +}; + +#define PLIST_INIT (p,__prio) \ +{ \ + .prio = __prio, \ + .dp_node = LIST_HEAD_INIT((p).dp_node), \ + .sp_node = LIST_HEAD_INIT((p).sp_node), \ +} + +/** +* plist_entry - get the struct for this entry +* @ptr: the &struct plist pointer. +* @type: the type of the struct this is embedded in. +* @member: the name of the list_struct within the struct. +*/ +#define plist_entry (ptr, type, member) \ + container_of(plist_first (ptr), type, member) +/** +* plist_for_each - iterate over the plist +* @pos1: the type * to use as a loop counter. +* @pos1: the type * to use as a second loop counter. +* @head: the head for your list. +*/ +#define plist_for_each (pos1, pos2, head) \ + list_for_each_entry(pos1, &((head)->dp_node), dp_node) \ + list_for_each_entry(pos2, &((pos1)->sp_node), sp_node) +/** +* plist_for_each_entry_safe - iterate over a plist of given type safe against removal of list entry +* @pos1: the type * to use as a loop counter. +* @pos2: the type * to use as a loop counter. +* @n1: another type * to use as temporary storage +* @n2: another type * to use as temporary storage +* @head: the head for your list. +*/ +#define plist_for_each_safe (pos1, pos2, n1, n2, head) \ + list_for_each_entry_safe(pos1, n1, &((head)->dp_node), dp_node) \ + list_for_each_entry_safe(pos2, n2, &((pos1)->sp_node), sp_node) + +/* Initialize a pl */ +static inline +void plist_init (struct plist *pl,int prio) +{ + pl->prio = prio; +INIT_LIST_HEAD (&pl->dp_node); +INIT_LIST_HEAD (&pl->sp_node); +} + +/* Return the first node (and thus, highest priority) +* +* Assumes the plist is _not_ empty. +*/ +static inline +struct plist *plist_first (struct plist *plist) +{ + return list_entry (plist->dp_node.next, struct plist, dp_node); +} + +/* Return if the plist is empty. */ +static inline +unsigned plist_empty (const struct plist *plist) +{ +return list_empty (&plist->dp_node); +} + +/* Update the maximum priority of the whole list +* +* @returns !0 if the plist prio changed, 0 otherwise. +* +* __plist_update_prio() assumes the plist is not empty. +*/ +static inline +unsigned __plist_update_prio (struct plist *plist) +{ +int prio =plist_first (plist)->prio; +if (plist->prio == prio) +return 0 ; + plist->prio = prio; +return !0 ; +} + +static inline +unsigned plist_update_prio (struct plist *plist) +{ +int old_prio = plist->prio; +/* plist empty, lowest prio = INT_MAX */ + plist->prio =plist_empty (plist)?INT_MAX :plist_first (plist)->prio; +return old_prio != plist->prio; +} + +/* Add a node to the plist [internal] +* +* pl->prio == INT_MAX is an special case, means low priority, get +* down to the end of the plist. Note the we want FIFO behaviour on +* the same priority. +*/ +static inline +void __plist_add_sorted (struct plist *plist,struct plist *pl) +{ +struct list_head *itr; +struct plist *itr_pl; + + +if (pl->prio <INT_MAX ) { + list_for_each (itr, &plist->dp_node) { + itr_pl = list_entry (itr, struct plist, dp_node); +if (pl->prio == itr_pl->prio) + goto existing_sp_head; +else if (pl->prio < itr_pl->prio) + goto new_sp_head; + } + itr_pl = plist; + goto new_sp_head; + } +/* Append to end, SP list for prio INT_MAX */ + itr_pl = container_of (plist->dp_node.prev, struct plist, dp_node); +if (!list_empty (&plist->dp_node) && itr_pl->prio ==INT_MAX ) + goto existing_sp_head; + itr_pl = plist; + +new_sp_head: +list_add_tail (&pl->dp_node, &itr_pl->dp_node); +INIT_LIST_HEAD (&pl->sp_node); +return ; + +existing_sp_head: +list_add_tail (&pl->sp_node, &itr_pl->sp_node); +INIT_LIST_HEAD (&pl->dp_node); +return ; +} + + +/** +* Add node @pl to @plist @returns !0 if the plist prio changed, 0 +* otherwise. +*/ +static inline +unsigned plist_add (struct plist *pl,struct plist *plist) +{ +__plist_add_sorted (plist, pl); +/* Are we setting a higher priority? */ +if (pl->prio < plist->prio) { + plist->prio = pl->prio; +return !0 ; + } +return 0 ; +} + + +/* Grunt to do the real removal work of @pl from the plist. */ +static inline +void __plist_del (struct plist *pl) +{ +struct list_head *victim; +if (list_empty (&pl->dp_node))/* SP-node, not head */ + victim = &pl->sp_node; +else if (list_empty (&pl->sp_node))/* DP-node, empty SP list */ + victim = &pl->dp_node; +else {/* SP list head, not empty */ +struct plist *pl_new =container_of (pl->sp_node.next, + struct plist, sp_node); + victim = &pl->sp_node; +list_replace_rcu (&pl->dp_node, &pl_new->dp_node); + } +list_del_init (victim); +} + +/** +* Remove a node @pl from @plist. @returns !0 if the plist prio +* changed, 0 otherwise. +*/ +static inline +unsigned plist_del (struct plist *plist,struct plist *pl) +{ +__plist_del (pl); +return plist_update_prio (plist); +} + +/** +* plist_del_init - deletes entry from list and reinitialize it. +* @entry: the element to delete from the list. +*/ +static inline void plist_del_init (struct plist *plist,struct plist *pl) +{ +plist_del (plist, pl); +plist_init (pl,0 ); +} + +/* Return the priority a pl node */ +static inline +int plist_prio (struct plist *pl) +{ +return pl->prio; +} + +/* Change the priority of a pl node, without updating plist position */ +static inline +void __plist_chprio (struct plist *pl,int new_prio) +{ + pl->prio = new_prio; +} + +/** +* Change the priority of node @pl in @plist (updating the list's max +* priority). @returns !0 if the plist's maximum priority changes +*/ +static inline +unsigned plist_chprio (struct plist *plist,struct plist *pl,int new_prio) +{ +if (new_prio == plist->prio) +return 0 ; +__plist_chprio (pl, new_prio); +__plist_del (pl); +__plist_add_sorted (plist, pl); +return __plist_update_prio (plist); +} + + +static inline +struct plist *__plist_dp_next (struct plist *node_dp) +{ + return container_of (node_dp->dp_node.next, struct plist, dp_node); +} + + +extern void __plist_splice (struct plist *dst,struct plist *src); + +/** Join @src plist to @dst plist and reinitialise @dst. @returns !0 */ +static inline +unsigned plist_splice_init (struct plist *dst,struct plist *src) +{ +int old_prio; +if (plist_empty (src)) +return 0 ; + old_prio = dst->prio; +__plist_splice (dst, src); +plist_init (src,INT_MAX ); +return old_prio != dst->prio; +} + +#endif /* #ifndef _LINUX_PLIST_H_ */ +
include/linux/rt_lock.h +6 -5
@@ -3,6 +3,7 @@#include <linux/config.h> #include <linux/list.h> +#include <linux/plist.h> /* * These are the basic SMP spinlocks, allowing only a single CPU anywhere.
@@ -57,7 +58,7 @@*/ struct rt_mutex {raw_spinlock_t wait_lock; -struct list_head wait_list; +struct plist wait_list;struct task_struct *owner;int owner_prio;# ifdef CONFIG_RT_DEADLOCK_DETECT
@@ -75,8 +76,8 @@*/ struct rt_mutex_waiter {struct rt_mutex *lock; -struct list_head list; -struct list_head pi_list; +struct plist list; +struct plist pi_list;struct task_struct *task;unsigned long eip;// for debugging
@@ -85,12 +86,12 @@#ifdef CONFIG_RT_DEADLOCK_DETECT # define __RT_MUTEX_INITIALIZER (lockname) \ { .wait_lock = RAW_SPIN_LOCK_UNLOCKED, \ - .wait_list = LIST_HEAD_INIT((lockname).wait_list), \ + .wait_list = PLIST_INIT((lockname).wait_list, 0), \ .name = #lockname, .file = __FILE__, .line = __LINE__ }#else # define __RT_MUTEX_INITIALIZER (lockname) \ { .wait_lock = RAW_SPIN_LOCK_UNLOCKED, \ - LIST_HEAD_INIT((lockname).wait_list) } + PLIST_INIT((lockname).wait_list, 0) }#endif /* * RW-semaphores are an RT mutex plus a reader-depth count.
include/linux/sched.h +1 -1
@@ -837,7 +837,7 @@/* realtime bits */ struct list_head delayed_put; -struct list_head pi_waiters; +struct plist pi_waiters;/* RT deadlock detection and priority inheritance handling */ struct rt_mutex_waiter *blocked_on;
kernel/fork.c +1 -1
@@ -990,7 +990,7 @@ }#endif INIT_LIST_HEAD (&p->delayed_put); -INIT_LIST_HEAD (&p->pi_waiters); +plist_init (&p->pi_waiters,0 ); p->blocked_on =NULL ;/* not blocked yet */ p->tgid = p->pid;
kernel/rt.c +61 -70
324 lines not on this page · raw message
Quoted 2 lines · Daniel Walker
This patch adds the priority list data structure from Inaky
Perez-Gonzalez to the Preempt Real-Time mutex.
this one looks really clean.
it makes me wonder, what is the current status of fusyn's? Such a light datastructure would be much more mergeable upstream than the former 100-queues approach.
Ingo
Quoted 10 lines · Ingo Molnar
Quoted 2 lines · Daniel Walker
This patch adds the priority list data structure from Inaky
Perez-Gonzalez to the Preempt Real-Time mutex.this one looks really clean.
it makes me wonder, what is the current status of fusyn's? Such a light datastructure would be much more mergeable upstream than the former 100-queues approach.
Ingo,
Joe Korty has been doing a lot of work on Fusyn recently.
Fusyn is now a generic implementation, similar to the RT mutex. SMP scalability is somewhat better for decoupled locks on PI (last I checked). It has the extra bulk required to support user space.
The major issue that concerns the Fusym and the real-time patch is that merging the kernel portion of Fusyn creates a collision of redundant PI implementations with respect to the RT mutex.
The issues are outlined here:
http://developer.osdl.org/dev/mutexes/
There are a few mistakes on the page, (RT mutex does not do priority ceiling), but for the most part the info is current.
If the RT mutex could be exposed in non PREEMPT_RT configurations, the fulock portion could be superseded by the RT mutex, and the remaining pieces merged in. Or vice versa.
We discussed the scenarios recently, any guidance you can offer to help us out would be greatly appreciated.
http://lists.osdl.org/pipermail/robustmutexes/2005-April/000532.html
Sven
Quoted 16 lines · Sven-Thorsten Dietrich
Quoted 10 lines · Ingo Molnar
Quoted 2 lines · Daniel Walker
This patch adds the priority list data structure from Inaky
Perez-Gonzalez to the Preempt Real-Time mutex.this one looks really clean.
it makes me wonder, what is the current status of fusyn's? Such a light datastructure would be much more mergeable upstream than the former 100-queues approach.
Ingo,
Joe Korty has been doing a lot of work on Fusyn recently.
Quoted 7 lines
Fusyn is now a generic implementation, similar to the RT mutex. SMP scalability is somewhat better for decoupled locks on PI (last I checked). It has the extra bulk required to support user space.
The major issue that concerns the Fusym and the real-time patch is that merging the kernel portion of Fusyn creates a collision of redundant PI implementations with respect to the RT mutex.
i'd not mind merging the extra bits to PREEMPT_RT to enable fusyn's, if they come in small, clean steps. E.g. Daniel's plist.h stuff was nice and clean.
Quoted 2 lines
There are a few mistakes on the page, (RT mutex does not do priority ceiling), but for the most part the info is current.
is priority ceiling coming in via some POSIX feature that fusyn's need to address? What would be needed precisely - a way to set a priority for a lock (independently of the owner's task priority), and let that control the PI mechanism?
Unless i'm missing something, this could be implemented by detaching lock->owner_prio from lock->owner - via e.g. negative values. Thus some minimal code would check whether we need the owner's priority in the PI logic, or the semaphore's "own" priority level.
i.e. this doesnt seem to really affect the core design of RT mutexes.
OTOH, deadlock detection is another issue. It's quite expensive and i'm not sure we want to make it a runtime thing. But for fusyn's deadlock detection and safe teardown on owner-exit is a must-have i suspect?
Quoted 3 lines
If the RT mutex could be exposed in non
PREEMPT_RTconfigurations, the fulock portion could be superseded by the RT mutex, and the remaining pieces merged in. Or vice versa.
sure, RT mutexes could be exposed in !PREEMPT_RT.
Ingo
Quoted 4 lines · Ingo Molnar
Unless i'm missing something, this could be implemented by detaching
lock->owner_priofromlock->owner- via e.g. negative values. Thus some minimal code would check whether we need the owner's priority in the PI logic, or the semaphore's "own" priority level.
The owners priority should be set to the semaphore's priority .. Or the highest priority of all the semaphores that it has locked.
Daniel
Quoted 5 lines · Ingo Molnar
this one looks really clean.
it makes me wonder, what is the current status of fusyn's? Such a light datastructure would be much more mergeable upstream than the former 100-queues approach.
Inaky was telling me that 100 queues approach is two years old.
The biggest problem is that fusyn has it's own PI system .. So it's not clear if that will work with the RT mutex,. I was thinking the PI stuff could be made generic so, fusyn, maybe futex, can use it also .
Daniel
Quoted 3 lines · Daniel Walker
Description:
This patch adds the priority list data structure from Inaky
Perez-Gonzalez to the Preempt Real-Time mutex.
ok, i've added this patch to the -45-00 release. It's looking good on my testsystems so far, but it will need some more testing i guess.
Ingo
Quoted 2 lines · Ingo Molnar
ok, i've added this patch to the -45-00 release. It's looking good on my testsystems so far, but it will need some more testing i guess.
Yes, I ran the PI test, and just let the system run .. So it could use more extensive testing..
Daniel
include/linux/plist.h
Quoted 18 lines · Daniel Walker
Source: Daniel Walker <[email protected]> MontaVista Software, Inc Description:
This patch adds the priority list data structure from Inaky Perez-Gonzalez
to the Preempt Real-Time mutex.the patch order is (starting with a 2.6.11 kernel tree),
patch-2.6.12-rc2
realtime-preempt-2.6.12-rc2-V0.7.44-01Signed-off-by Daniel Walker <[email protected]>Index:
linux-2.6.11/include/linux/plist.h
===================================================================include/linux/plist.h +0
-0@@ -0,0 +1,310 @@
[ . . . ]
Quoted 4 lines
include/linux/plist.h +4
-0+/* Grunt to do the real removal work of @pl from the plist. */ +static inline +void __plist_del (struct plist *pl) +{
include/linux/plist.h line 231
Quoted 10 lines
include/linux/plist.h +10
-0+struct list_head *victim; +if (list_empty (&pl->dp_node))/* SP-node, not head */ + victim = &pl->sp_node; +else if (list_empty (&pl->sp_node))/* DP-node, empty SP list */ + victim = &pl->dp_node; +else {/* SP list head, not empty */ +struct plist *pl_new =container_of (pl->sp_node.next, + struct plist, sp_node); + victim = &pl->sp_node; +list_replace_rcu (&pl->dp_node, &pl_new->dp_node);
If you are protecting this list with RCU...
include/linux/plist.h line 16
Quoted 2 lines
include/linux/plist.h +2
-0+ } +list_del_init (victim);
... you need to wait for a grace period before deleting the element removed from the list.
Or are you just using list_replace_rcu() for its replacement capability? If so, seems like it might be worthwhile to make a list_replace(). This would get rid of the memory barrier, and also keep from confusing people like myself. ;-)
Thanx, Paul