diff options
| -rw-r--r-- | Makefrag.am | 2 | ||||
| -rw-r--r-- | kern/mutex.c | 120 | ||||
| -rw-r--r-- | kern/mutex.h | 53 |
3 files changed, 175 insertions, 0 deletions
diff --git a/Makefrag.am b/Makefrag.am index d9e34c00..817c6fa8 100644 --- a/Makefrag.am +++ b/Makefrag.am @@ -14,6 +14,8 @@ x15_SOURCES += \ kern/limits.h \ kern/list.h \ kern/macros.h \ + kern/mutex.c \ + kern/mutex.h \ kern/panic.c \ kern/panic.h \ kern/param.h \ diff --git a/kern/mutex.c b/kern/mutex.c new file mode 100644 index 00000000..507116e2 --- /dev/null +++ b/kern/mutex.c @@ -0,0 +1,120 @@ +/* + * Copyright (c) 2013 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 + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + */ + +#include <kern/assert.h> +#include <kern/list.h> +#include <kern/mutex.h> +#include <kern/spinlock.h> +#include <kern/thread.h> +#include <machine/atomic.h> + +struct mutex_waiter { + struct list node; + struct thread *thread; +}; + +void +mutex_init(struct mutex *mutex) +{ + mutex->state = MUTEX_UNLOCKED; + spinlock_init(&mutex->lock); + list_init(&mutex->waiters); +} + +int +mutex_trylock(struct mutex *mutex) +{ + unsigned long state; + + state = atomic_cas(&mutex->state, MUTEX_UNLOCKED, MUTEX_LOCKED); + + if (state == MUTEX_UNLOCKED) + return 0; + + return 1; +} + +void +mutex_lock(struct mutex *mutex) +{ + struct mutex_waiter waiter; + unsigned long state; + + state = atomic_cas(&mutex->state, MUTEX_UNLOCKED, MUTEX_LOCKED); + + if (state == MUTEX_UNLOCKED) + return; + + /* + * The mutex was either locked or contended. Unconditionnally update its + * state to reflect it is now contended, and to check the previous state + * while holding the waiters lock so that the current thread doesn't miss + * a wakeup when the owner unlocks. + */ + + assert((state == MUTEX_LOCKED) || (state == MUTEX_CONTENDED)); + + spinlock_lock(&mutex->lock); + + state = atomic_swap(&mutex->state, MUTEX_CONTENDED); + + if (state == MUTEX_UNLOCKED) + goto out; + + waiter.thread = thread_self(); + list_insert_tail(&mutex->waiters, &waiter.node); + + do { + thread_sleep(&mutex->lock); + state = atomic_swap(&mutex->state, MUTEX_CONTENDED); + } while (state != MUTEX_UNLOCKED); + + list_remove(&waiter.node); + +out: + if (list_empty(&mutex->waiters)) { + state = atomic_swap(&mutex->state, MUTEX_LOCKED); + assert(state == MUTEX_CONTENDED); + } + + spinlock_unlock(&mutex->lock); +} + +void +mutex_unlock(struct mutex *mutex) +{ + struct mutex_waiter *waiter; + unsigned long state; + + state = atomic_swap(&mutex->state, MUTEX_UNLOCKED); + + if (state == MUTEX_LOCKED) + return; + + /* The mutex was contended, wake up the next waiter if any */ + + assert(state == MUTEX_CONTENDED); + + spinlock_lock(&mutex->lock); + + if (!list_empty(&mutex->waiters)) { + waiter = list_first_entry(&mutex->waiters, struct mutex_waiter, node); + thread_wakeup(waiter->thread); + } + + spinlock_unlock(&mutex->lock); +} diff --git a/kern/mutex.h b/kern/mutex.h new file mode 100644 index 00000000..2f46ca8c --- /dev/null +++ b/kern/mutex.h @@ -0,0 +1,53 @@ +/* + * Copyright (c) 2013 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 + * the Free Software Foundation, either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see <http://www.gnu.org/licenses/>. + * + * + * Mutual exclusion locks. + * + * Unlike spin locks, acquiring a mutex may make the calling thread sleep. + */ + +#ifndef _KERN_MUTEX_H +#define _KERN_MUTEX_H + +#include <kern/list.h> +#include <kern/spinlock.h> + +#define MUTEX_UNLOCKED 0 +#define MUTEX_LOCKED 1 +#define MUTEX_CONTENDED 2 + +struct mutex { + unsigned long state; + struct spinlock lock; + struct list waiters; +}; + +#define MUTEX_INITIALIZER(mutex) \ + { MUTEX_UNLOCKED, SPINLOCK_INITIALIZER, LIST_INITIALIZER((mutex).waiters) } + +void mutex_init(struct mutex *mutex); + +/* + * Return 0 on success, 1 if busy. + */ +int mutex_trylock(struct mutex *mutex); + +void mutex_lock(struct mutex *mutex); + +void mutex_unlock(struct mutex *mutex); + +#endif /* _KERN_MUTEX_H */ |