diff options
| -rw-r--r-- | kern/condition.c | 194 | ||||
| -rw-r--r-- | kern/condition.h | 56 | ||||
| -rw-r--r-- | kern/condition_types.h | 9 | ||||
| -rw-r--r-- | kern/mutex.c | 44 | ||||
| -rw-r--r-- | kern/mutex.h | 52 | ||||
| -rw-r--r-- | kern/mutex_i.h | 65 | ||||
| -rw-r--r-- | kern/mutex_types.h | 5 | ||||
| -rw-r--r-- | kern/thread.c | 1 | ||||
| -rw-r--r-- | kern/thread.h | 43 | ||||
| -rw-r--r-- | kern/thread_i.h | 9 |
10 files changed, 292 insertions, 186 deletions
diff --git a/kern/condition.c b/kern/condition.c index 467cb85a..bcd5ba42 100644 --- a/kern/condition.c +++ b/kern/condition.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2013-2014 Richard Braun. + * Copyright (c) 2013-2017 Richard Braun. * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -15,124 +15,178 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. * * - * In order to avoid the infamous thundering herd problem, this implementation - * doesn't wake all threads when broadcasting a condition. Instead, they are - * queued on the mutex associated with the condition, and an attempt to wake - * one by locking and unlocking the mutex is performed. If the mutex is already - * locked, the current owner does the same when unlocking. + * Locking order : mutex -> sleep queue */ #include <stddef.h> #include <kern/assert.h> #include <kern/condition.h> -#include <kern/list.h> +#include <kern/condition_types.h> #include <kern/mutex.h> -#include <kern/mutex_i.h> -#include <kern/spinlock.h> +#include <kern/sleepq.h> #include <kern/thread.h> -void -condition_wait(struct condition *condition, struct mutex *mutex) +static void +condition_inc_nr_sleeping_waiters(struct condition *condition) { - struct mutex_waiter waiter; - unsigned int state; + condition->nr_sleeping_waiters++; + assert(condition->nr_sleeping_waiters != 0); +} - waiter.thread = thread_self(); +static void +condition_dec_nr_sleeping_waiters(struct condition *condition) +{ + assert(condition->nr_sleeping_waiters != 0); + condition->nr_sleeping_waiters--; +} - spinlock_lock(&condition->lock); +static void +condition_inc_nr_pending_waiters(struct condition *condition) +{ + condition->nr_pending_waiters++; + assert(condition->nr_pending_waiters != 0); +} - assert((condition->mutex == NULL) || (condition->mutex == mutex)); +static void +condition_dec_nr_pending_waiters(struct condition *condition) +{ + assert(condition->nr_pending_waiters != 0); + condition->nr_pending_waiters--; +} - if (condition->mutex == NULL) { - condition->mutex = mutex; - } +static void +condition_move_waiters(struct condition *condition) +{ + unsigned short old; - list_insert_tail(&condition->waiters, &waiter.node); + assert(condition->nr_sleeping_waiters != 0); + old = condition->nr_pending_waiters; + condition->nr_pending_waiters += condition->nr_sleeping_waiters; + assert(old < condition->nr_pending_waiters); + condition->nr_sleeping_waiters = 0; +} - spinlock_lock(&mutex->lock); +void +condition_wait(struct condition *condition, struct mutex *mutex) +{ + struct condition *last_cond; + struct sleepq *sleepq; + + mutex_assert_locked(mutex); + + /* + * Special case : + * + * mutex_lock(lock); + * + * for (;;) { + * while (!done) { + * condition_wait(condition, lock); + * } + * + * do_something(); + * } + * + * Pull the last condition before unlocking the mutex to prevent + * mutex_unlock() from reacquiring the condition sleep queue. + */ + last_cond = thread_pull_last_cond(); + + sleepq = sleepq_lend(condition, true); + + mutex_unlock(mutex); + + if (last_cond != NULL) { + assert(last_cond == condition); + + if (condition->nr_pending_waiters != 0) { + sleepq_signal(sleepq); + } + } - state = mutex_release(mutex); + condition_inc_nr_sleeping_waiters(condition); + sleepq_wait(sleepq, "cond"); + condition_dec_nr_pending_waiters(condition); - if (state == MUTEX_CONTENDED) { - mutex_signal(mutex); + if (condition->nr_pending_waiters != 0) { + thread_set_last_cond(condition); } - spinlock_unlock(&condition->lock); + sleepq_return(sleepq); - mutex_wait(mutex, &waiter); - mutex_trydowngrade(mutex); - - spinlock_unlock(&mutex->lock); + mutex_lock(mutex); } void condition_signal(struct condition *condition) { - struct mutex_waiter *waiter; - struct mutex *mutex; - unsigned int state; + struct sleepq *sleepq; - spinlock_lock(&condition->lock); + sleepq = sleepq_acquire(condition, true); - if (condition->mutex == NULL) { - spinlock_unlock(&condition->lock); + if (sleepq == NULL) { return; } - mutex = condition->mutex; - waiter = list_first_entry(&condition->waiters, struct mutex_waiter, node); - list_remove(&waiter->node); - - if (list_empty(&condition->waiters)) { - condition->mutex = NULL; + if (condition->nr_sleeping_waiters == 0) { + goto out; } - spinlock_unlock(&condition->lock); - - spinlock_lock(&mutex->lock); - - mutex_queue(mutex, waiter); - state = mutex_tryacquire_slow(mutex); + sleepq_signal(sleepq); - if (state == MUTEX_UNLOCKED) { - mutex_release(mutex); - mutex_signal(mutex); - } + condition_dec_nr_sleeping_waiters(condition); + condition_inc_nr_pending_waiters(condition); - spinlock_unlock(&mutex->lock); +out: + sleepq_release(sleepq); } void condition_broadcast(struct condition *condition) { - struct list waiters; - struct mutex *mutex; - unsigned int state; + struct sleepq *sleepq; - spinlock_lock(&condition->lock); + sleepq = sleepq_acquire(condition, true); - if (condition->mutex == NULL) { - spinlock_unlock(&condition->lock); + if (sleepq == NULL) { return; } - mutex = condition->mutex; - condition->mutex = NULL; - list_set_head(&waiters, &condition->waiters); - list_init(&condition->waiters); + if (condition->nr_sleeping_waiters == 0) { + goto out; + } - spinlock_unlock(&condition->lock); + sleepq_signal(sleepq); - spinlock_lock(&mutex->lock); + condition_move_waiters(condition); - mutex_queue_list(mutex, &waiters); - state = mutex_tryacquire_slow(mutex); +out: + sleepq_release(sleepq); +} - if (state == MUTEX_UNLOCKED) { - mutex_release(mutex); - mutex_signal(mutex); +void +condition_wakeup(struct condition *condition) +{ + struct sleepq *sleepq; + + sleepq = sleepq_acquire(condition, true); + + if (sleepq == NULL) { + return; } - spinlock_unlock(&mutex->lock); + if (condition->nr_pending_waiters == 0) { + goto out; + } + + /* + * Rely on the FIFO ordering of sleep queues so that signalling multiple + * times always wakes up the same thread, as long as that thread didn't + * reacquire the sleep queue. + */ + sleepq_signal(sleepq); + +out: + sleepq_release(sleepq); } diff --git a/kern/condition.h b/kern/condition.h index 55d37bf2..0ce8d94f 100644 --- a/kern/condition.h +++ b/kern/condition.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2013-2014 Richard Braun. + * Copyright (c) 2013-2017 Richard Braun. * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -16,34 +16,62 @@ * * * Condition variables. + * + * A condition variable is a synchronization primitive used to wait + * until a predicate becomes true. Multiple threads can be waiting + * for this condition. In order to synchronize changes on the predicate + * with waiting and signalling, a condition variable must be associated + * with a mutex. */ #ifndef _KERN_CONDITION_H #define _KERN_CONDITION_H -#include <stddef.h> - #include <kern/condition_types.h> -#include <kern/list.h> -#include <kern/spinlock.h> +#include <kern/mutex_types.h> -/* - * Condition variable. - */ struct condition; +/* + * Initialize a condition variable. + */ static inline void condition_init(struct condition *condition) { - spinlock_init(&condition->lock); - condition->mutex = NULL; - list_init(&condition->waiters); + condition->nr_sleeping_waiters = 0; + condition->nr_pending_waiters = 0; } -void condition_wait(struct condition *cond, struct mutex *mutex); +/* + * Wait for a wake-up on the given condition variable. + * + * The associated mutex must be locked when calling this function. + * It is unlocked before waiting and relocked before returning. + */ +void condition_wait(struct condition *condition, struct mutex *mutex); -void condition_signal(struct condition *cond); +/* + * Wake up one (signal) or all (broadcast) threads waiting on a + * condition variable, if any. + * + * Although it is not necessary to hold the mutex associated to the + * condition variable when calling these functions, doing so guarantees + * that a wake-up done when changing the predicate cannot be missed by + * waiting threads. + */ +void condition_signal(struct condition *condition); +void condition_broadcast(struct condition *condition); -void condition_broadcast(struct condition *cond); +/* + * Wake up a pending thread. + * + * This function isn't part of the standard condition variable interface. + * It is used to chain wake-ups to avoid the thundering herd effect. + * When broadcasting a condition variable, a single thread is actually + * awaken. Other threads become "pending waiters", still asleep but + * eligible for wake-up when the mutex associated to the condition variable, + * relocked when returning from condition_wait(), is finally unlocked. + */ +void condition_wakeup(struct condition *condition); #endif /* _KERN_CONDITION_H */ diff --git a/kern/condition_types.h b/kern/condition_types.h index 03b22676..13a29205 100644 --- a/kern/condition_types.h +++ b/kern/condition_types.h @@ -21,14 +21,9 @@ #ifndef _KERN_CONDITION_TYPES_H #define _KERN_CONDITION_TYPES_H -#include <kern/list_types.h> -#include <kern/mutex_types.h> -#include <kern/spinlock_types.h> - struct condition { - struct spinlock lock; - struct mutex *mutex; - struct list waiters; + unsigned short nr_sleeping_waiters; + unsigned short nr_pending_waiters; }; #endif /* _KERN_CONDITION_TYPES_H */ diff --git a/kern/mutex.c b/kern/mutex.c index 58e24513..1a1c2ea7 100644 --- a/kern/mutex.c +++ b/kern/mutex.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2013-2014 Richard Braun. + * Copyright (c) 2013-2017 Richard Braun. * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -15,36 +15,50 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. */ +#include <stddef.h> + #include <kern/mutex.h> #include <kern/mutex_i.h> -#include <kern/spinlock.h> -#include <kern/thread.h> +#include <kern/sleepq.h> void mutex_lock_slow(struct mutex *mutex) { - struct mutex_waiter waiter; + struct sleepq *sleepq; unsigned int state; - spinlock_lock(&mutex->lock); + sleepq = sleepq_lend(mutex, false); + + for (;;) { + state = atomic_swap_uint(&mutex->state, MUTEX_CONTENDED); - state = mutex_tryacquire_slow(mutex); + if (state == MUTEX_UNLOCKED) { + break; + } - if (state != MUTEX_UNLOCKED) { - waiter.thread = thread_self(); - mutex_queue(mutex, &waiter); - mutex_wait(mutex, &waiter); + sleepq_wait(sleepq, "mutex"); } - mutex_trydowngrade(mutex); + if (sleepq_empty(sleepq)) { + state = atomic_swap_uint(&mutex->state, MUTEX_LOCKED); + assert(state == MUTEX_CONTENDED); + } - spinlock_unlock(&mutex->lock); + sleepq_return(sleepq); } void mutex_unlock_slow(struct mutex *mutex) { - spinlock_lock(&mutex->lock); - mutex_signal(mutex); - spinlock_unlock(&mutex->lock); + struct sleepq *sleepq; + + sleepq = sleepq_acquire(mutex, false); + + if (sleepq == NULL) { + return; + } + + sleepq_signal(sleepq); + + sleepq_release(sleepq); } diff --git a/kern/mutex.h b/kern/mutex.h index 64efa350..2804fc44 100644 --- a/kern/mutex.h +++ b/kern/mutex.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2013-2014 Richard Braun. + * Copyright (c) 2013-2017 Richard Braun. * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -15,9 +15,11 @@ * along with this program. If not, see <http://www.gnu.org/licenses/>. * * - * Mutual exclusion locks. + * Mutual exclusion sleep locks. * * Unlike spin locks, acquiring a mutex may make the calling thread sleep. + * + * TODO Adaptive spinning. */ #ifndef _KERN_MUTEX_H @@ -25,23 +27,30 @@ #include <kern/assert.h> #include <kern/error.h> -#include <kern/list.h> #include <kern/mutex_i.h> #include <kern/mutex_types.h> -#include <kern/spinlock.h> +#include <kern/thread.h> struct mutex; +#define mutex_assert_locked(mutex) assert((mutex)->state != MUTEX_UNLOCKED) + +/* + * Initialize a mutex. + */ static inline void mutex_init(struct mutex *mutex) { mutex->state = MUTEX_UNLOCKED; - spinlock_init(&mutex->lock); - list_init(&mutex->waiters); } -#define mutex_assert_locked(mutex) assert((mutex)->state != MUTEX_UNLOCKED) - +/* + * Attempt to lock the given mutex. + * + * This function may not sleep. + * + * Return 0 on success, ERROR_BUSY if the mutex is already locked. + */ static inline int mutex_trylock(struct mutex *mutex) { @@ -56,6 +65,14 @@ mutex_trylock(struct mutex *mutex) return ERROR_BUSY; } +/* + * Lock a mutex. + * + * If the mutex is already locked, the calling thread sleeps until the + * mutex is unlocked. + * + * A mutex can only be locked once. + */ static inline void mutex_lock(struct mutex *mutex) { @@ -72,6 +89,12 @@ mutex_lock(struct mutex *mutex) mutex_lock_slow(mutex); } +/* + * Unlock a mutex. + * + * The mutex must be locked, and must have been locked by the calling + * thread. + */ static inline void mutex_unlock(struct mutex *mutex) { @@ -79,13 +102,16 @@ mutex_unlock(struct mutex *mutex) state = mutex_release(mutex); - if (state == MUTEX_LOCKED) { - return; + if (state != MUTEX_LOCKED) { + assert(state == MUTEX_CONTENDED); + mutex_unlock_slow(mutex); } - assert(state == MUTEX_CONTENDED); - - mutex_unlock_slow(mutex); + /* + * If this mutex was used along with a condition variable, wake up + * a potential pending waiter. + */ + thread_wakeup_last_cond(); } #endif /* _KERN_MUTEX_H */ diff --git a/kern/mutex_i.h b/kern/mutex_i.h index 5e78a4da..a161b1bb 100644 --- a/kern/mutex_i.h +++ b/kern/mutex_i.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2013-2014 Richard Braun. + * Copyright (c) 2013-2017 Richard Braun. * * This program is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by @@ -19,24 +19,13 @@ #define _KERN_MUTEX_I_H #include <kern/assert.h> -#include <kern/list.h> #include <kern/mutex_types.h> -#include <kern/thread.h> #include <machine/atomic.h> #define MUTEX_UNLOCKED 0 #define MUTEX_LOCKED 1 #define MUTEX_CONTENDED 2 -struct mutex_waiter { - struct list node; - struct thread *thread; -}; - -void mutex_lock_slow(struct mutex *mutex); - -void mutex_unlock_slow(struct mutex *mutex); - static inline unsigned int mutex_tryacquire(struct mutex *mutex) { @@ -44,12 +33,6 @@ mutex_tryacquire(struct mutex *mutex) } static inline unsigned int -mutex_tryacquire_slow(struct mutex *mutex) -{ - return atomic_swap_uint(&mutex->state, MUTEX_CONTENDED); -} - -static inline unsigned int mutex_release(struct mutex *mutex) { unsigned int state; @@ -59,51 +42,9 @@ mutex_release(struct mutex *mutex) return state; } -static inline void -mutex_queue(struct mutex *mutex, struct mutex_waiter *waiter) -{ - list_insert_tail(&mutex->waiters, &waiter->node); -} - -static inline void -mutex_queue_list(struct mutex *mutex, struct list *waiters) -{ - list_concat(&mutex->waiters, waiters); -} - -static inline void -mutex_wait(struct mutex *mutex, struct mutex_waiter *waiter) -{ - unsigned int state; - - do { - thread_sleep(&mutex->lock, mutex, "mutex"); - state = mutex_tryacquire_slow(mutex); - } while (state != MUTEX_UNLOCKED); - - list_remove(&waiter->node); -} - -static inline void -mutex_signal(struct mutex *mutex) -{ - struct mutex_waiter *waiter; - - if (!list_empty(&mutex->waiters)) { - waiter = list_first_entry(&mutex->waiters, struct mutex_waiter, node); - thread_wakeup(waiter->thread); - } -} +void mutex_lock_slow(struct mutex *mutex); -static inline void -mutex_trydowngrade(struct mutex *mutex) -{ - if (list_empty(&mutex->waiters)) { - unsigned int state; +void mutex_unlock_slow(struct mutex *mutex); - state = atomic_swap_uint(&mutex->state, MUTEX_LOCKED); - assert(state == MUTEX_CONTENDED); - } -} #endif /* _KERN_MUTEX_I_H */ diff --git a/kern/mutex_types.h b/kern/mutex_types.h index b348fb7b..e3126b10 100644 --- a/kern/mutex_types.h +++ b/kern/mutex_types.h @@ -21,13 +21,8 @@ #ifndef _KERN_MUTEX_TYPES_H #define _KERN_MUTEX_TYPES_H -#include <kern/list_types.h> -#include <kern/spinlock_types.h> - struct mutex { unsigned int state; - struct spinlock lock; - struct list waiters; }; #endif /* _KERN_MUTEX_TYPES_H */ diff --git a/kern/thread.c b/kern/thread.c index 3eccebda..436df07a 100644 --- a/kern/thread.c +++ b/kern/thread.c @@ -1803,6 +1803,7 @@ thread_init(struct thread *thread, void *stack, } turnstile_td_init(&thread->turnstile_td); + thread->last_cond = NULL; thread->propagate_priority = false; thread->preempt = THREAD_SUSPEND_PREEMPT_LEVEL; thread->pinned = 0; diff --git a/kern/thread.h b/kern/thread.h index 15babbfc..b9308b65 100644 --- a/kern/thread.h +++ b/kern/thread.h @@ -37,6 +37,7 @@ #include <stddef.h> #include <kern/assert.h> +#include <kern/condition.h> #include <kern/cpumap.h> #include <kern/macros.h> #include <kern/spinlock_types.h> @@ -436,6 +437,48 @@ thread_sleepq_return(struct sleepq *sleepq) } /* + * Condition variable related functions. + */ + +static inline void +thread_set_last_cond(struct condition *last_cond) +{ + struct thread *thread; + + thread = thread_self(); + assert(thread->last_cond == NULL); + thread->last_cond = last_cond; +} + +static inline struct condition * +thread_pull_last_cond(void) +{ + struct condition *last_cond; + struct thread *thread; + + thread = thread_self(); + last_cond = thread->last_cond; + + if (last_cond != NULL) { + thread->last_cond = NULL; + } + + return last_cond; +} + +static inline void +thread_wakeup_last_cond(void) +{ + struct condition *last_cond; + + last_cond = thread_pull_last_cond(); + + if (last_cond != NULL) { + condition_wakeup(last_cond); + } +} + +/* * Turnstile lending functions. */ diff --git a/kern/thread_i.h b/kern/thread_i.h index 865787a0..9bb55827 100644 --- a/kern/thread_i.h +++ b/kern/thread_i.h @@ -107,6 +107,15 @@ struct thread { /* Turnstile available for lending */ struct turnstile *priv_turnstile; + /* + * When a thread wakes up after waiting for a condition variable, + * it sets this variable so that other waiters are only awaken + * after the associated mutex has actually been released. + * + * This member is thread-local. + */ + struct condition *last_cond; + /* Per-thread turnstile data */ struct turnstile_td turnstile_td; |