sched: A simple priority ceiling framework and an implementation for mutex.
Subsystems (2)
PATCH 1/1 sched: A simple priority ceiling framework and an implementation for mutex.
Some tips of the design:
1. The prio_floor linked-list save all mutex is holded by each task in time order. It is a stack data srtucture.
2. The prio_rmin member of the mutex_waiter is used for tracing current minimum-value(highest) priority of this mutex.
3. It seem the task_struct->nr_null_floors have a bit of redundancy, it's used to guarantee everything's OK when we failed to allocate prio_floor structure.
4. At last, the magic value PRIO_UNDERGROUND (0x19491001), it is the Chinese National Day ;)
The most largest question is how meansure the performance of this patch ? I have no any good idea for this.
Good luck.
Signed-off-by Li Yu <[email protected]>
include/linux/prio_ceiling.h +17 -0
@@ -0,0 +1,17 @@ +#ifndef _LINUX_PRIO_CEILING_H +#define _LINUX_PRIO_CEILING_H + +#ifdef __KERNEL__ + +struct prio_floor { +struct prio_floor *next;/* linked in priority stair */ +void *id;/* which mutex own this floor ? */ +int prio;/* save the priority when acquire */ +}; + +#define FLOOR_ID_NONE ((void*)0) +#define FLOOR_ID_NEXT ((void*)1) + +#endif /* __KERNEL__ */ + +#endif
include/linux/sched.h +84 -1
115 lines not on this page · raw message
kernel/sched.c +3 -0
@@ -727,6 +727,9 @@ static inline int __normal_prio(struct t bonus =CURRENT_BONUS (p) -MAX_BONUS /2 ; prio = p->static_prio - bonus; + +if (!rt_prio (p->prio_ceiling) && p->prio_ceiling < prio) + prio = p->prio_ceiling;if (prio <MAX_RT_PRIO ) prio =MAX_RT_PRIO ;if (prio >MAX_PRIO -1 )
include/linux/mutex.h +4 -0
@@ -14,6 +14,7 @@#include <linux/spinlock_types.h> #include <linux/linkage.h> #include <linux/lockdep.h> +#include <linux/prio_ceiling.h> #include <asm/atomic.h>
@@ -49,6 +50,8 @@ struct mutex {atomic_t count;spinlock_t wait_lock;struct list_head wait_list; +struct task_struct *holder; +struct prio_floor floor;#ifdef CONFIG_DEBUG_MUTEXES struct thread_info *owner;const char *name;
@@ -66,6 +69,7 @@ struct mutex {struct mutex_waiter {struct list_head list;struct task_struct *task; +int prio_rmin;#ifdef CONFIG_DEBUG_MUTEXES struct mutex *lock;void *magic;
kernel/mutex.c +33 -2
@@ -89,6 +89,7 @@ void inline fastcall __sched mutex_lock(* 'unlocked' into 'locked' state. */ __mutex_fastpath_lock (&lock->count, __mutex_lock_slowpath); +task_push_prio_floor (&lock->floor); }EXPORT_SYMBOL (mutex_lock);
@@ -113,6 +114,7 @@ void fastcall __sched mutex_unlock(struc* The unlocking fastpath is the 0->1 transition from 'locked' * into 'unlocked' state: */ +task_pop_prio_floor ();__mutex_fastpath_unlock (&lock->count, __mutex_unlock_slowpath); }
@@ -135,6 +137,19 @@ __mutex_lock_common(struct mutex *lock,mutex_acquire (&lock->dep_map, subclass,0 , _RET_IP_);debug_mutex_add_waiter (lock, &waiter, task->thread_info); +if (!list_empty (&lock->wait_list)) { +struct mutex_waiter *last = +list_entry (lock->wait_list.prev, + struct mutex_waiter, list); +if (task->prio < last->prio_rmin) + waiter.prio_rmin = task->prio; +else + waiter.prio_rmin = last->prio_rmin; + }else + waiter.prio_rmin = task->prio; + lock->floor.prio = waiter.prio_rmin; + lock->floor.id = lock; +/* add waiting tasks to the end of the waitqueue (FIFO): */ list_add_tail (&waiter.list, &lock->wait_list); waiter.task = task;
@@ -167,6 +182,8 @@ __mutex_lock_common(struct mutex *lock,return -EINTR ; }__set_task_state (task, state); + +task_climb_up_wait (lock->holder, &lock->floor);/* didnt get the lock, go to sleep: */ spin_unlock_mutex (&lock->wait_lock, flags);
@@ -177,6 +194,8 @@ __mutex_lock_common(struct mutex *lock,/* got the lock - rejoice! */ mutex_remove_waiter (lock, &waiter, task->thread_info);debug_mutex_set_owner (lock, task->thread_info); + + lock->holder = task;/* set it to 0 if there are no waiters left: */ if (likely (list_empty (&lock->wait_list)))
@@ -229,14 +248,22 @@ __mutex_unlock_common_slowpath(atomic_tif (__mutex_slowpath_needs_to_unlock ())atomic_set (&lock->count,1 ); + lock->holder =NULL ; +task_climb_down (current); +if (!list_empty (&lock->wait_list)) {/* get the first entry from the wait-list: */ struct mutex_waiter *waiter =list_entry (lock->wait_list.next, struct mutex_waiter, list); +struct mutex_waiter *tailor = +list_entry (lock->wait_list.prev, + struct mutex_waiter, list);debug_mutex_wake_waiter (lock, waiter); +task_climb_up_wake (waiter->task, lock, tailor->prio_rmin); +wake_up_process (waiter->task); }
@@ -331,8 +358,12 @@ static inline int __mutex_trylock_slowpa*/ int fastcall __sched mutex_trylock(struct mutex *lock) { -return __mutex_fastpath_trylock (&lock->count, - __mutex_trylock_slowpath); +if (__mutex_fastpath_trylock (&lock->count, __mutex_trylock_slowpath)) { +task_push_prio_floor (&lock->floor); +return 1 ; + }else +return 0 ; + }EXPORT_SYMBOL (mutex_trylock);