diff options
| -rw-r--r-- | Makefrag.am | 3 | ||||
| -rw-r--r-- | kern/semaphore.c | 60 | ||||
| -rw-r--r-- | kern/semaphore.h | 125 | ||||
| -rw-r--r-- | kern/semaphore_i.h | 60 |
4 files changed, 248 insertions, 0 deletions
diff --git a/Makefrag.am b/Makefrag.am index 78679f00..f4f8f631 100644 --- a/Makefrag.am +++ b/Makefrag.am @@ -56,6 +56,9 @@ x15_SOURCES += \ kern/rtmutex.h \ kern/rtmutex_i.h \ kern/rtmutex_types.h \ + kern/semaphore.c \ + kern/semaphore.h \ + kern/semaphore_types.h \ kern/sleepq.c \ kern/sleepq.h \ kern/spinlock.h \ diff --git a/kern/semaphore.c b/kern/semaphore.c new file mode 100644 index 00000000..e41e2c2f --- /dev/null +++ b/kern/semaphore.c @@ -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 <http://www.gnu.org/licenses/>. + */ + +#include <stdbool.h> +#include <stddef.h> + +#include <kern/semaphore.h> +#include <kern/semaphore_i.h> +#include <kern/sleepq.h> + +void +semaphore_wait_slow(struct semaphore *semaphore) +{ + struct sleepq *sleepq; + unsigned int prev; + + sleepq = sleepq_lend(semaphore, false); + + for (;;) { + prev = semaphore_dec(semaphore); + + if (prev != 0) { + break; + } + + sleepq_wait(sleepq, "sem"); + } + + sleepq_return(sleepq); +} + +void +semaphore_post_slow(struct semaphore *semaphore) +{ + struct sleepq *sleepq; + + sleepq = sleepq_acquire(semaphore, false); + + if (sleepq == NULL) { + return; + } + + sleepq_signal(sleepq); + + sleepq_release(sleepq); +} diff --git a/kern/semaphore.h b/kern/semaphore.h new file mode 100644 index 00000000..f5cb82b5 --- /dev/null +++ b/kern/semaphore.h @@ -0,0 +1,125 @@ +/* + * 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 <http://www.gnu.org/licenses/>. + * + * + * Semaphores are resource-counting sleeping synchronization objects. + * They are used to synchronize access to resources and signal events. + * + * The main operations supported by semaphores are locking and unlocking. + * A semaphore is implemented as an atomic integer with an initial value. + * Locking a semaphore means decrementing that integer, whereas unlocking + * means incrementing it. Locking can only succeed if the semaphore value + * is strictly greater than 0. + * + * Semaphores should not be used to implement critical sections. Instead, + * use mutexes, which are similar to binary semaphores but with additional + * restrictions that can improve debugging. + */ + +#ifndef _KERN_SEMAPHORE_H +#define _KERN_SEMAPHORE_H + +#include <kern/assert.h> +#include <kern/error.h> +#include <kern/macros.h> + +#define SEMAPHORE_VALUE_MAX 32768 + +#include <kern/semaphore_i.h> + +struct semaphore; + +/* + * Initialize a semaphore. + */ +static inline void +semaphore_init(struct semaphore *semaphore, unsigned int value) +{ + assert(value <= SEMAPHORE_VALUE_MAX); + semaphore->value = value; +} + +/* + * Attempt to lock a semaphore. + * + * This function may not sleep. + * + * Return 0 on success, ERROR_AGAIN if the semaphore could not be decremented. + */ +static inline int +semaphore_trywait(struct semaphore *semaphore) +{ + unsigned int prev; + + prev = semaphore_dec(semaphore); + + if (prev == 0) { + return ERROR_AGAIN; + } + + return 0; +} + +/* + * Lock a semaphore. + * + * If the semaphore value doesn't allow locking, the calling thread sleeps + * until the semaphore value is incremented. + */ +static inline void +semaphore_wait(struct semaphore *semaphore) +{ + unsigned int prev; + + prev = semaphore_dec(semaphore); + + if (prev != 0) { + return; + } + + semaphore_wait_slow(semaphore); +} + +/* + * Unlock a semaphore. + * + * If the semaphore value becomes strictly greater than 0, a thread waiting + * on the semaphore is awaken. + */ +static inline void +semaphore_post(struct semaphore *semaphore) +{ + unsigned int prev; + + prev = semaphore_inc(semaphore); + + if (prev != 0) { + return; + } + + semaphore_post_slow(semaphore); +} + +/* + * Get the value of a semaphore. + */ +static inline unsigned int +semaphore_getvalue(const struct semaphore *semaphore) +{ + return read_once(semaphore->value); +} + +#endif /* _KERN_SEMAPHORE_H */ diff --git a/kern/semaphore_i.h b/kern/semaphore_i.h new file mode 100644 index 00000000..c6769c12 --- /dev/null +++ b/kern/semaphore_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 <http://www.gnu.org/licenses/>. + */ + +#ifndef _KERN_SEMAPHORE_I_H +#define _KERN_SEMAPHORE_I_H + +#include <kern/assert.h> +#include <machine/atomic.h> + +struct semaphore { + unsigned int value; +}; + +static inline unsigned int +semaphore_dec(struct semaphore *semaphore) +{ + unsigned int prev, value; + + do { + value = semaphore->value; + + if (value == 0) { + break; + } + + prev = atomic_cas_uint(&semaphore->value, value, value - 1); + } while (prev != value); + + return value; +} + +static inline unsigned int +semaphore_inc(struct semaphore *semaphore) +{ + unsigned int prev; + + prev = atomic_fetchadd_uint(&semaphore->value, 1); + assert(prev != SEMAPHORE_VALUE_MAX); + return prev; +} + +void semaphore_wait_slow(struct semaphore *semaphore); + +void semaphore_post_slow(struct semaphore *semaphore); + +#endif /* _KERN_SEMAPHORE_I_H */ |