From 4278f99adcbcfbd52904c0d8809184afe091c958 Mon Sep 17 00:00:00 2001 From: Agustina Arzille Date: Fri, 21 Jul 2017 00:49:39 +0200 Subject: Rework mutex implementation selection --- Makefrag.am | 10 +++- configure.ac | 7 +++ kern/atomic.h | 6 +-- kern/mutex.c | 71 -------------------------- kern/mutex.h | 98 ++++++------------------------------ kern/mutex/mutex_pi_i.h | 60 ++++++++++++++++++++++ kern/mutex/mutex_pi_types.h | 39 ++++++++++++++ kern/mutex/mutex_plain.c | 65 ++++++++++++++++++++++++ kern/mutex/mutex_plain_i.h | 112 +++++++++++++++++++++++++++++++++++++++++ kern/mutex/mutex_plain_types.h | 33 ++++++++++++ kern/mutex_i.h | 53 ------------------- kern/mutex_types.h | 24 ++------- kern/rtmutex.c | 3 +- 13 files changed, 348 insertions(+), 233 deletions(-) delete mode 100644 kern/mutex.c create mode 100644 kern/mutex/mutex_pi_i.h create mode 100644 kern/mutex/mutex_pi_types.h create mode 100644 kern/mutex/mutex_plain.c create mode 100644 kern/mutex/mutex_plain_i.h create mode 100644 kern/mutex/mutex_plain_types.h delete mode 100644 kern/mutex_i.h diff --git a/Makefrag.am b/Makefrag.am index e9d4e63e..c3f8d035 100644 --- a/Makefrag.am +++ b/Makefrag.am @@ -44,10 +44,12 @@ x15_SOURCES += \ kern/llsync_i.h \ kern/log2.h \ kern/macros.h \ - kern/mutex.c \ kern/mutex.h \ - kern/mutex_i.h \ kern/mutex_types.h \ + kern/mutex/mutex_pi_i.h \ + kern/mutex/mutex_pi_types.h \ + kern/mutex/mutex_plain_i.h \ + kern/mutex/mutex_plain_types.h \ kern/panic.c \ kern/panic.h \ kern/param.h \ @@ -103,6 +105,10 @@ x15_SOURCES += \ kern/xcall.c \ kern/xcall.h +if !MUTEX_PI + x15_SOURCES += kern/mutex/mutex_plain.c +endif + x15_SOURCES += \ vm/vm_adv.h \ vm/vm_inherit.h \ diff --git a/configure.ac b/configure.ac index be21f3d2..dd4607c9 100644 --- a/configure.ac +++ b/configure.ac @@ -100,9 +100,16 @@ AC_DEFINE_UNQUOTED([X15_MAX_CPUS], [$opt_max_cpus], [maximum number of supported processors]) AC_MSG_NOTICE([maximum number of supported processors: $opt_max_cpus]) +AS_IF([test x"$enable_mutex_pi" = xyes], + [mutex_impl="priority inheritance"], + [mutex_impl=plain]) +AC_MSG_NOTICE([mutex implementation: $mutex_impl]) + AS_IF([test x"$enable_mutex_pi" = xyes], [AC_DEFINE_UNQUOTED([X15_MUTEX_PI], [], [Enable priority inheritance for regular mutexes])]) +AM_CONDITIONAL([MUTEX_PI], + [test x"$enable_mutex_pi" = xyes]) AS_IF([test x"$enable_thread_stack_guard" = xyes], [AC_DEFINE_UNQUOTED([X15_THREAD_STACK_GUARD], [], diff --git a/kern/atomic.h b/kern/atomic.h index 75b07012..63f0ac73 100644 --- a/kern/atomic.h +++ b/kern/atomic.h @@ -116,6 +116,9 @@ MACRO_END * Common shortcuts. */ +#define atomic_load_acquire(ptr) atomic_load(ptr, ATOMIC_ACQUIRE) +#define atomic_store_release(ptr, val) atomic_store(ptr, val, ATOMIC_RELEASE) + #define atomic_cas_acquire(ptr, oval, nval) \ atomic_cas(ptr, oval, nval, ATOMIC_ACQUIRE) @@ -129,9 +132,6 @@ MACRO_END #define atomic_swap_release(ptr, val) atomic_swap(ptr, val, ATOMIC_RELEASE) #define atomic_swap_acq_rel(ptr, val) atomic_swap(ptr, val, ATOMIC_ACQ_REL) -#define atomic_fetch_add_acq_rel(ptr, val) \ - atomic_fetch_add(ptr, val, ATOMIC_ACQ_REL) - #define atomic_fetch_sub_acq_rel(ptr, val) \ atomic_fetch_sub(ptr, val, ATOMIC_ACQ_REL) diff --git a/kern/mutex.c b/kern/mutex.c deleted file mode 100644 index 7899bef9..00000000 --- a/kern/mutex.c +++ /dev/null @@ -1,71 +0,0 @@ -/* - * 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 - * 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 . - */ - -#ifndef X15_MUTEX_PI - -#include -#include - -#include -#include -#include - -void -mutex_lock_slow(struct mutex *mutex) -{ - struct sleepq *sleepq; - unsigned long flags; - unsigned int state; - - sleepq = sleepq_lend(mutex, false, &flags); - - for (;;) { - state = atomic_swap_acquire(&mutex->state, MUTEX_CONTENDED); - - if (state == MUTEX_UNLOCKED) { - break; - } - - sleepq_wait(sleepq, "mutex"); - } - - if (sleepq_empty(sleepq)) { - state = atomic_swap_acquire(&mutex->state, MUTEX_LOCKED); - assert(state == MUTEX_CONTENDED); - } - - sleepq_return(sleepq, flags); -} - -void -mutex_unlock_slow(struct mutex *mutex) -{ - struct sleepq *sleepq; - unsigned long flags; - - sleepq = sleepq_acquire(mutex, false, &flags); - - if (sleepq == NULL) { - return; - } - - sleepq_signal(sleepq); - - sleepq_release(sleepq, flags); -} - -#endif /* X15_MUTEX_PI */ diff --git a/kern/mutex.h b/kern/mutex.h index 1100b77d..e599e8a2 100644 --- a/kern/mutex.h +++ b/kern/mutex.h @@ -18,75 +18,31 @@ * Mutual exclusion sleep locks. * * Unlike spin locks, acquiring a mutex may make the calling thread sleep. - * - * TODO Adaptive spinning. */ #ifndef _KERN_MUTEX_H #define _KERN_MUTEX_H -#include - -#ifdef X15_MUTEX_PI - -#include - -struct mutex; - -#define mutex_assert_locked(mutex) rtmutex_assert_locked(&(mutex)->rtmutex) - -static inline void -mutex_init(struct mutex *mutex) -{ - rtmutex_init(&mutex->rtmutex); -} - -static inline int -mutex_trylock(struct mutex *mutex) -{ - return rtmutex_trylock(&mutex->rtmutex); -} - -static inline void -mutex_lock(struct mutex *mutex) -{ - rtmutex_lock(&mutex->rtmutex); -} - -static inline void -mutex_unlock(struct mutex *mutex) -{ - rtmutex_unlock(&mutex->rtmutex); +#if defined(X15_MUTEX_PI) +#include +#else +#include +#endif - /* - * If this mutex was used along with a condition variable, wake up - * a potential pending waiter. This must be done after the mutex is - * unlocked so that a higher priority thread can directly acquire it. - */ - thread_wakeup_last_cond(); -} - -#else /* X15_MUTEX_PI */ - -#include -#include -#include -#include +#include #include -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; + mutex_impl_init(mutex); } +#define mutex_assert_locked(mutex) mutex_impl_assert_locked(mutex) + /* * Attempt to lock the given mutex. * @@ -97,37 +53,20 @@ mutex_init(struct mutex *mutex) static inline int mutex_trylock(struct mutex *mutex) { - unsigned int state; - - state = mutex_lock_fast(mutex); - - if (unlikely(state != MUTEX_UNLOCKED)) { - assert((state == MUTEX_LOCKED) || (state == MUTEX_CONTENDED)); - return ERROR_BUSY; - } - - return 0; + return mutex_impl_trylock(mutex); } /* * Lock a mutex. * - * If the mutex is already locked, the calling thread sleeps until the - * mutex is unlocked. + * On return, the mutex is locked. A mutex can only be locked once. * - * A mutex can only be locked once. + * This function may sleep. */ static inline void mutex_lock(struct mutex *mutex) { - unsigned int state; - - state = mutex_lock_fast(mutex); - - if (unlikely(state != MUTEX_UNLOCKED)) { - assert((state == MUTEX_LOCKED) || (state == MUTEX_CONTENDED)); - mutex_lock_slow(mutex); - } + mutex_impl_lock(mutex); } /* @@ -139,14 +78,7 @@ mutex_lock(struct mutex *mutex) static inline void mutex_unlock(struct mutex *mutex) { - unsigned int state; - - state = mutex_unlock_fast(mutex); - - if (unlikely(state != MUTEX_LOCKED)) { - assert(state == MUTEX_CONTENDED); - mutex_unlock_slow(mutex); - } + mutex_impl_unlock(mutex); /* * If this mutex was used along with a condition variable, wake up @@ -155,6 +87,4 @@ mutex_unlock(struct mutex *mutex) thread_wakeup_last_cond(); } -#endif /* X15_MUTEX_PI */ - #endif /* _KERN_MUTEX_H */ diff --git a/kern/mutex/mutex_pi_i.h b/kern/mutex/mutex_pi_i.h new file mode 100644 index 00000000..6c39db74 --- /dev/null +++ b/kern/mutex/mutex_pi_i.h @@ -0,0 +1,60 @@ +/* + * Copyright (c) 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 + * 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 . + */ + +#ifndef _KERN_MUTEX_PI_I_H +#define _KERN_MUTEX_PI_I_H + +#ifndef _KERN_MUTEX_H +#error "don't include directly," \ + " use instead" +#endif + +#include +#include + +/* + * Interface exported to the public mutex header. + */ + +static inline void +mutex_impl_init(struct mutex *mutex) +{ + rtmutex_init(&mutex->rtmutex); +} + +#define mutex_impl_assert_locked(mutex) \ + rtmutex_assert_locked(&(mutex)->rtmutex) + +static inline int +mutex_impl_trylock(struct mutex *mutex) +{ + return rtmutex_trylock(&mutex->rtmutex); +} + +static inline void +mutex_impl_lock(struct mutex *mutex) +{ + rtmutex_lock(&mutex->rtmutex); +} + +static inline void +mutex_impl_unlock(struct mutex *mutex) +{ + rtmutex_unlock(&mutex->rtmutex); +} + +#endif /* _KERN_MUTEX_PI_I_H */ diff --git a/kern/mutex/mutex_pi_types.h b/kern/mutex/mutex_pi_types.h new file mode 100644 index 00000000..d9ebb6e2 --- /dev/null +++ b/kern/mutex/mutex_pi_types.h @@ -0,0 +1,39 @@ +/* + * Copyright (c) 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 + * 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 . + * + * + * Isolated type definition used to avoid inclusion circular dependencies. + */ + +#ifndef _KERN_MUTEX_PI_TYPES_H +#define _KERN_MUTEX_PI_TYPES_H + +#ifndef _KERN_MUTEX_TYPES_H +#error "don't include directly," \ + " use instead" +#endif + +#include + +/* + * Do not directly alias rtmutex to make sure they cannot be used + * with condition variables by mistake. + */ +struct mutex { + struct rtmutex rtmutex; +}; + +#endif /* _KERN_MUTEX_PI_TYPES_H */ diff --git a/kern/mutex/mutex_plain.c b/kern/mutex/mutex_plain.c new file mode 100644 index 00000000..a925a5a2 --- /dev/null +++ b/kern/mutex/mutex_plain.c @@ -0,0 +1,65 @@ +/* + * Copyright (c) 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 + * 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 . + */ + +#include +#include + +#include +#include +#include +#include + +void +mutex_plain_lock_slow(struct mutex *mutex) +{ + unsigned int state; + struct sleepq *sleepq; + unsigned long flags; + + sleepq = sleepq_lend(mutex, false, &flags); + + for (;;) { + state = atomic_swap_release(&mutex->state, MUTEX_CONTENDED); + + if (state == MUTEX_UNLOCKED) { + break; + } + + sleepq_wait(sleepq, "mutex"); + } + + if (sleepq_empty(sleepq)) { + /* TODO Review memory order */ + atomic_store(&mutex->state, MUTEX_LOCKED, ATOMIC_RELEASE); + } + + sleepq_return(sleepq, flags); +} + +void +mutex_plain_unlock_slow(struct mutex *mutex) +{ + struct sleepq *sleepq; + unsigned long flags; + + sleepq = sleepq_acquire(mutex, false, &flags); + + if (sleepq != NULL) { + sleepq_signal(sleepq); + sleepq_release(sleepq, flags); + } +} diff --git a/kern/mutex/mutex_plain_i.h b/kern/mutex/mutex_plain_i.h new file mode 100644 index 00000000..9e41ff27 --- /dev/null +++ b/kern/mutex/mutex_plain_i.h @@ -0,0 +1,112 @@ +/* + * Copyright (c) 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 + * 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 . + */ + +#ifndef _KERN_MUTEX_PLAIN_I_H +#define _KERN_MUTEX_PLAIN_I_H + +#ifndef _KERN_MUTEX_H +#error "don't include directly," \ + " use instead" +#endif + +#include +#include +#include +#include + +#define MUTEX_UNLOCKED 0 +#define MUTEX_LOCKED 1 +#define MUTEX_CONTENDED 2 + +static inline void +mutex_plain_init(struct mutex *mutex) +{ + mutex->state = MUTEX_UNLOCKED; +} + +#define mutex_plain_assert_locked(mutex) \ + assert((mutex)->state != MUTEX_UNLOCKED) + +static inline int +mutex_plain_lock_fast(struct mutex *mutex) +{ + unsigned int state; + + state = atomic_cas_acquire(&mutex->state, MUTEX_UNLOCKED, MUTEX_LOCKED); + + if (unlikely(state != MUTEX_UNLOCKED)) { + return ERROR_BUSY; + } + + return 0; +} + +static inline int +mutex_plain_unlock_fast(struct mutex *mutex) +{ + unsigned int state; + + state = atomic_swap_release(&mutex->state, MUTEX_UNLOCKED); + + if (unlikely(state == MUTEX_CONTENDED)) { + return ERROR_BUSY; + } + + return 0; +} + +void mutex_plain_lock_slow(struct mutex *mutex); +void mutex_plain_unlock_slow(struct mutex *mutex); + +/* + * Interface exported to the public mutex header. + */ + +#define mutex_impl_init mutex_plain_init +#define mutex_impl_assert_locked mutex_plain_assert_locked + +static inline int +mutex_impl_trylock(struct mutex *mutex) +{ + return mutex_plain_lock_fast(mutex); +} + +static inline void +mutex_impl_lock(struct mutex *mutex) +{ + int error; + + error = mutex_plain_lock_fast(mutex); + + if (unlikely(error)) { + mutex_plain_lock_slow(mutex); + } +} + +static inline void +mutex_impl_unlock(struct mutex *mutex) +{ + int error; + + error = mutex_plain_unlock_fast(mutex); + + if (unlikely(error)) { + mutex_plain_unlock_slow(mutex); + } +} + +#endif /* _KERN_MUTEX_PLAIN_I_H */ diff --git a/kern/mutex/mutex_plain_types.h b/kern/mutex/mutex_plain_types.h new file mode 100644 index 00000000..02731e94 --- /dev/null +++ b/kern/mutex/mutex_plain_types.h @@ -0,0 +1,33 @@ +/* + * Copyright (c) 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 + * 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 . + * + * + * Isolated type definition used to avoid inclusion circular dependencies. + */ + +#ifndef _KERN_MUTEX_PLAIN_TYPES_H +#define _KERN_MUTEX_PLAIN_TYPES_H + +#ifndef _KERN_MUTEX_TYPES_H +#error "don't include directly," \ + " use instead" +#endif + +struct mutex { + unsigned int state; +}; + +#endif /* _KERN_MUTEX_PLAIN_TYPES_H */ diff --git a/kern/mutex_i.h b/kern/mutex_i.h deleted file mode 100644 index a4a40eb5..00000000 --- a/kern/mutex_i.h +++ /dev/null @@ -1,53 +0,0 @@ -/* - * 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 - * 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 . - */ - -#ifndef _KERN_MUTEX_I_H -#define _KERN_MUTEX_I_H - -#ifndef X15_MUTEX_PI - -#include -#include -#include - -#define MUTEX_UNLOCKED 0 -#define MUTEX_LOCKED 1 -#define MUTEX_CONTENDED 2 - -static inline unsigned int -mutex_lock_fast(struct mutex *mutex) -{ - return atomic_cas_acquire(&mutex->state, MUTEX_UNLOCKED, MUTEX_LOCKED); -} - -static inline unsigned int -mutex_unlock_fast(struct mutex *mutex) -{ - unsigned int state; - - state = atomic_swap_release(&mutex->state, MUTEX_UNLOCKED); - assert((state == MUTEX_LOCKED) || (state == MUTEX_CONTENDED)); - return state; -} - -void mutex_lock_slow(struct mutex *mutex); - -void mutex_unlock_slow(struct mutex *mutex); - -#endif /* X15_MUTEX_PI */ - -#endif /* _KERN_MUTEX_I_H */ diff --git a/kern/mutex_types.h b/kern/mutex_types.h index 4b7947fc..432eab30 100644 --- a/kern/mutex_types.h +++ b/kern/mutex_types.h @@ -21,24 +21,10 @@ #ifndef _KERN_MUTEX_TYPES_H #define _KERN_MUTEX_TYPES_H -#ifdef X15_MUTEX_PI - -#include - -/* - * Do not directly alias rtmutex to make sure they cannot be used - * with condition variables by mistake. - */ -struct mutex { - struct rtmutex rtmutex; -}; - -#else /* X15_MUTEX_PI */ - -struct mutex { - unsigned int state; -}; - -#endif /* X15_MUTEX_PI */ +#if defined(X15_MUTEX_PI) +#include +#else +#include +#endif #endif /* _KERN_MUTEX_TYPES_H */ diff --git a/kern/rtmutex.c b/kern/rtmutex.c index 6f639ddf..6909ce18 100644 --- a/kern/rtmutex.c +++ b/kern/rtmutex.c @@ -36,7 +36,7 @@ void rtmutex_lock_slow(struct rtmutex *rtmutex) { struct turnstile *turnstile; - uintptr_t owner, prev_owner; + uintptr_t owner, prev_owner; /* TODO Review names */ struct thread *thread; uintptr_t bits; @@ -64,6 +64,7 @@ rtmutex_lock_slow(struct rtmutex *rtmutex) turnstile_own(turnstile); if (turnstile_empty(turnstile)) { + /* TODO Review memory order */ prev_owner = atomic_swap_acquire(&rtmutex->owner, owner); assert(prev_owner == (owner | bits)); } -- cgit v1.2.3