From 9685b64b970fdd0c0a459cbd52c6291006ee9202 Mon Sep 17 00:00:00 2001 From: Matthias Kruk Date: Tue, 18 Feb 2020 21:00:21 +0900 Subject: [PATCH] kernel/klibc: Add FCFS-semaphore implementation - Add ffs type and ffs_* functions - Fix grammar in documentation of sem_* functions - Make sure lines in sem.h don't exceed 80 columns --- kernel/include/ffs.h | 87 +++++++++++++++++++++++++++ kernel/include/sem.h | 22 +++---- kernel/klibc/ffs.c | 140 +++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 238 insertions(+), 11 deletions(-) create mode 100644 kernel/include/ffs.h create mode 100644 kernel/klibc/ffs.c diff --git a/kernel/include/ffs.h b/kernel/include/ffs.h new file mode 100644 index 0000000..dd7d619 --- /dev/null +++ b/kernel/include/ffs.h @@ -0,0 +1,87 @@ +#ifndef __FFS_H +#define __FFS_H + +#include +#include +#include + +typedef struct { + spinlock_t ffs_lock; + int ffs_count; + int ffs_waiting; + task_t *ffs_waitq[CONFIG_SEM_WAITQLEN]; +} ffs_t; + +/* + * ffs_wait() - Decrease a FCFS-semaphore + * + * SYNPOSIS + * int ffs_wait(ffs_t *ffs); + * + * DESCRIPTION + * The ffs_wait() function decreases the internal counter of the + * semaphore pointed to by `ffs'. If the semaphore cannot immediately + * be decreased, the calling task will be suspended and added to the + * semaphore's wait queue. Once the semaphore gets increased by + * another task, the task at the head of the queue will be woken up + * and get its turn to pass the semaphore. + * + * RETURN VALUE + * 0 The value of the semaphore has been successfully decreased + * -ENOMEM The semaphore's wait queue is full + */ +int ffs_wait(ffs_t*); + +/* + * ffs_trywait() - Decrease a FCFS-semaphore + * + * SYNOPSIS + * int ffs_trywait(ffs_t *ffs); + * + * DESCRIPTION + * The ffs_trywait() function will attempt to decrease the value of + * the semaphore pointed to by `ffs'. If the semaphore cannot be + * decreased immedately, the function will return an error. + * + * RETURN VALUE + * 0 The value of the semaphore has been successfully decreased + * -EAGAIN The semaphore could not immediately be decreased + */ +int ffs_trywait(ffs_t*); + +/* + * ffs_post() - Increase a FCFS-semaphore + * + * SYNOPSIS + * int ffs_post(ffs_t *ffs); + * + * DESCRIPTION + * The ffs_post() function will increase the value of the semaphore + * pointed to by `ffs'. If the operation succeeds, ffs_post() will + * also cause the task in the front of the semaphore's wait queue to + * be woken up. In the case of an error, the state of the semaphore + * will remain unchanged. + * + * RETURN VALUE + * 0 The semaphore's value has been successfully increased + * -OVERFLOW The operation would have caused an overflow + */ +int ffs_post(ffs_t*); + +/* + * ffs_peek() - Get the value of a FCFS-semaphore + * + * SYNOPSIS + * int ffs_peek(ffs_t *ffs); + * + * DESCRIPTION + * The ffs_peek() function will obtain the value of the semaphore + * pointed to by `ffs' and return its value. The value returned will + * always be larger than or equal to zero. + * + * RETURN VALUE + * * The current value of the semaphore (>= 0) + */ +int ffs_peek(ffs_t*); + +#endif /* __FFS_H */ diff --git a/kernel/include/sem.h b/kernel/include/sem.h index acbe68e..169f13e 100644 --- a/kernel/include/sem.h +++ b/kernel/include/sem.h @@ -18,13 +18,13 @@ typedef struct { * int sem_wait(sem_t *sem); * * DESCRIPTION - * The sem_wait() decreases the value of the semaphore pointed - * to by `sem'. If the semaphore cannot be immediately decreased, - * the calling task will be suspended and added to the semaphore's - * wait list. Once the semaphore gets increased by another task, - * all tasks waiting on the semaphore will be woken up, and the - * order in which the tasks will get to pass the semaphore depends - * on the scheduler. + * The sem_wait() function decreases the value of the semaphore + * pointed to by `sem'. If the semaphore cannot be immediately + * decreased, the calling task will be suspended and added to the + * semaphore's wait list. Once the semaphore gets increased by + * another task, all tasks waiting on the semaphore will be woken + * up, and the order in which the tasks will get to pass the + * semaphore depends on the scheduler. * If sem_wait() cannot immediately increase the semaphore, it will * keep trying until it succeeds, meaning that the calling task may * be suspended indefinitely if no other task invokes sem_post() on @@ -62,7 +62,7 @@ int sem_trywait(sem_t*); * The sem_post() function will increase the value of the semaphore * pointed to by `sem'. If the operation succeeds, sem_post() will * also cause all tasks that are waiting on the semaphore to be woken - * up. On failure, the state of the semaphore remains unchanged. + * up. Upon failure, the state of the semaphore remains unchanged. * * RETURN VALUE * 0 The semaphore's value has been successfully increased @@ -77,9 +77,9 @@ int sem_post(sem_t*); * int sem_peek(sem_t *sem); * * DESCRIPTION - * The sem_peek() function will obtain the value of semaphore pointed - * to by `sem' and return its value. The value returned will always be - * larger or equal to zero. + * The sem_peek() function will obtain the value of the semaphore + * pointed to by `sem' and return its value. The value returned will + * always be larger than or equal to zero. * * RETURN VALUE * * The current value of the semaphore (>= 0) diff --git a/kernel/klibc/ffs.c b/kernel/klibc/ffs.c new file mode 100644 index 0000000..8d1ae0e --- /dev/null +++ b/kernel/klibc/ffs.c @@ -0,0 +1,140 @@ +#include +#include +#include +#include +#include +#include +#include + +inline static int _nq(ffs_t *ffs, task_t *t) +{ + int ret_val; + + ret_val = -ENOMEM; + + if(ffs->ffs_waiting < CONFIG_SEM_WAITQLEN) { + ret_val = ffs->ffs_waiting++; + ffs->ffs_waitq[ret_val] = t; + } + + return(ret_val); +} + +inline static task_t* _dq(ffs_t *ffs) +{ + task_t *ret_val; + int n; + + ret_val = 0; + n = ffs->ffs_waiting; + + while(--n >= 0) { + task_t *swp; + + swp = ffs->ffs_waitq[n]; + ffs->ffs_waitq[n] = ret_val; + ret_val = swp; + n--; + } + + return(ret_val); +} + +int ffs_wait(ffs_t *ffs) +{ + task_t *ctask; + int ret_val; + + ctask = task_get_current(); + ret_val = -EAGAIN; + + do { + spinlock_lock(&(ffs->ffs_lock)); + + if(ffs->ffs_count > 0) { + ffs->ffs_count--; + ret_val = 0; + } else { + /* + * Return immediately if we couldn't get in the queue, in + * order to avoid priority inversion bugs. If we'd keep + * busy-waiting on the semaphore, there is a good chance + * we'd acquire the spinlock before the first task in the + * wait queue does. However, this semaphore implementation + * is supposed make sure tasks get their turn in a certain + * order, so don't do that. + */ + if(_nq(ffs, ctask) < 0) { + ret_val = -ENOMEM; + } + } + + spinlock_unlock(&(ffs->ffs_lock)); + + if(ret_val == -EAGAIN) { + /* go to bed */ + sched_sleep(NULL); + } + } while(ret_val == -EAGAIN); + + return(ret_val); +} + +int ffs_trywait(ffs_t *ffs) +{ + int ret_val; + + ret_val = -EAGAIN; + + spinlock_lock(&(ffs->ffs_lock)); + + if(ffs->ffs_count > 0) { + ffs->ffs_count--; + ret_val = 0; + } + + spinlock_unlock(&(ffs->ffs_lock)); + + return(ret_val); +} + +int ffs_post(ffs_t *ffs) +{ + task_t *first; + int new_count; + int ret_val; + + first = NULL; + ret_val = -EOVERFLOW; + + spinlock_lock(&(ffs->ffs_lock)); + + new_count = ffs->ffs_count + 1; + + if(new_count > ffs->ffs_count) { + ffs->ffs_count = new_count; + first = _dq(ffs); + ret_val = 0; + } + + spinlock_unlock(&(ffs->ffs_lock)); + + if(first) { + sched_wakeup(first, 0); + } + + return(ret_val); +} + +int ffs_peek(ffs_t *ffs) +{ + int ret_val; + + spinlock_lock(&(ffs->ffs_lock)); + + ret_val = ffs->ffs_count; + + spinlock_unlock(&(ffs->ffs_lock)); + + return(ret_val); +} -- 2.47.3