From 9b40330cdc9399acb3687cbccb7696b4fd9feb0e Mon Sep 17 00:00:00 2001 From: Richard Braun Date: Thu, 10 Jan 2019 23:27:59 +0100 Subject: kern/semaphore: rework The previous implementation, which uses a combination of fast and slow paths around accessing an atomic integer, suffers from a bug triggered when two or more posts are performed back-to-back, without a waiter decrementing the semaphore value in between. The first post would be the only one signalling a waiter. In addition, having a fast path that expects the absence of waiters probably doesn't make sense, as semaphores are expected to be used for signalling threads. As a result, it was decided to remove the fast path altogether, and protect the semaphore value with sleep queues. Finally, as part of the rework, semaphores now have a user-defined maximum value, in order to make the implementation of, e.g. wrappers for binary semaphores, convenient. Thanks to Simon Venken for reporting the bug. --- kern/semaphore_i.h | 42 +++--------------------------------------- 1 file changed, 3 insertions(+), 39 deletions(-) (limited to 'kern/semaphore_i.h') diff --git a/kern/semaphore_i.h b/kern/semaphore_i.h index d58ad0ba..f2397e51 100644 --- a/kern/semaphore_i.h +++ b/kern/semaphore_i.h @@ -1,5 +1,5 @@ /* - * Copyright (c) 2017 Richard Braun. + * Copyright (c) 2017-2019 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 @@ -18,47 +18,11 @@ #ifndef KERN_SEMAPHORE_I_H #define KERN_SEMAPHORE_I_H -#include #include -#include - struct semaphore { - unsigned int value; + uint16_t value; + uint16_t max_value; }; -static inline unsigned int -semaphore_dec(struct semaphore *semaphore) -{ - unsigned int prev, value; - - do { - value = atomic_load(&semaphore->value, ATOMIC_RELAXED); - - if (value == 0) { - break; - } - - prev = atomic_cas(&semaphore->value, value, value - 1, ATOMIC_ACQUIRE); - } while (prev != value); - - return value; -} - -static inline unsigned int -semaphore_inc(struct semaphore *semaphore) -{ - unsigned int prev; - - prev = atomic_fetch_add(&semaphore->value, 1, ATOMIC_RELEASE); - assert(prev != SEMAPHORE_VALUE_MAX); - return prev; -} - -void semaphore_wait_slow(struct semaphore *semaphore); - -int semaphore_timedwait_slow(struct semaphore *semaphore, uint64_t ticks); - -void semaphore_post_slow(struct semaphore *semaphore); - #endif /* KERN_SEMAPHORE_I_H */ -- cgit v1.2.3