From 021afcb8e4aa4fbc7905f527089c415108c86c75 Mon Sep 17 00:00:00 2001 From: Stefan Zabka Date: Thu, 18 Jun 2020 15:04:54 +0200 Subject: Switched to slotmap --- 04_exercise/CMakeLists.txt | 11 +++++++-- 04_exercise/main.c | 2 +- 04_exercise/slotmap/slomap_test.c | 19 ++++++++++++++++ 04_exercise/slotmap/slotmap.c | 48 +++++++++++++++++++++++++++++++++++++++ 04_exercise/slotmap/slotmap.h | 36 +++++++++++++++++++++++++++++ 04_exercise/threadpool.c | 40 ++++++++++++++++---------------- 6 files changed, 132 insertions(+), 24 deletions(-) create mode 100644 04_exercise/slotmap/slomap_test.c create mode 100644 04_exercise/slotmap/slotmap.c create mode 100644 04_exercise/slotmap/slotmap.h diff --git a/04_exercise/CMakeLists.txt b/04_exercise/CMakeLists.txt index c66bf2c..4e89060 100644 --- a/04_exercise/CMakeLists.txt +++ b/04_exercise/CMakeLists.txt @@ -5,7 +5,7 @@ add_executable(quicksort quicksort.c) target_link_libraries(quicksort PRIVATE threadpool) add_library(threadpool threadpool.c) -target_link_libraries(threadpool PRIVATE array Threads::Threads arena_list) +target_link_libraries(threadpool PRIVATE Threads::Threads slotmap) target_link_libraries(threadpool INTERFACE warnings) target_link_libraries(threadpool PUBLIC ppmlib) @@ -27,4 +27,11 @@ target_include_directories(rwlock PUBLIC rwlock) target_link_libraries(rwlock INTERFACE warnings) add_library(ppmlib INTERFACE) -target_include_directories(ppmlib INTERFACE ppmlib) \ No newline at end of file +target_include_directories(ppmlib INTERFACE ppmlib) + +add_library(slotmap slotmap/slotmap.c) +target_include_directories(slotmap PUBLIC slotmap) +target_link_libraries(slotmap INTERFACE warnings) + +add_executable(slotmap_test slotmap/slomap_test.c) +target_link_libraries(slotmap_test PRIVATE slotmap) diff --git a/04_exercise/main.c b/04_exercise/main.c index 69be10b..8c7b8db 100644 --- a/04_exercise/main.c +++ b/04_exercise/main.c @@ -14,7 +14,7 @@ static TASK(long, fib, long) return fibAwait(a) + fibAwait(b); } - +// Show this runs with only one thread and one place in the work queue int main() { setvbuf(stdout, NULL, _IONBF, 0); if (tpInit(4) != 0) diff --git a/04_exercise/slotmap/slomap_test.c b/04_exercise/slotmap/slomap_test.c new file mode 100644 index 0000000..930bfa8 --- /dev/null +++ b/04_exercise/slotmap/slomap_test.c @@ -0,0 +1,19 @@ +// +// Created by stefan on 18.06.20. +// +#include +#include +#include + +bool find1(void const * ptr) { + return * (int const *) ptr == 1; +} +int main() { + smEntry slab [10]; + int data [6] = {0, 1, 2,3,4,5}; + smHeader header = smInit((smEntry *)&slab, 10); + smInsert(&header, &data[1]); + smEntry * entry = smFindEntry(&header, &find1); + assert(*(int *)entry->value == 1); + return 0; +} diff --git a/04_exercise/slotmap/slotmap.c b/04_exercise/slotmap/slotmap.c new file mode 100644 index 0000000..57c4ef5 --- /dev/null +++ b/04_exercise/slotmap/slotmap.c @@ -0,0 +1,48 @@ +// +// Created by stefan on 18.06.20. +// + +#include "slotmap.h" +#include +smHeader smInit(smEntry * slab, size_t size) { + for (int i = 0; i < size; ++i) { + slab[i].value = (intptr_t)NULL; + } + return (smHeader){.slab = slab, .size=size}; +} +int smInsert(smHeader const * header, void * value) { + for (size_t i = 0; i< header->size; ++i ) { + intptr_t ptr = atomic_load(&header->slab[i].value); + if((void *)ptr == NULL) { + intptr_t expected = (intptr_t) NULL; + if(atomic_compare_exchange_strong(&header->slab[i].value, &expected, (intptr_t) value)){ + return 0; + } + } + } + return -1; +} +void smDelete(smEntry * node) { + intptr_t oldval = atomic_exchange(&node->value, (intptr_t)(NULL)); + if((void *) oldval == NULL) { + fprintf(stderr, "A Node has been double deleted"); + } +} +void smDeleteValue(smHeader const * header, void * value){ + for (size_t i = 0; i< header->size; ++i ) { + intptr_t ptr = atomic_load(&header->slab[i].value); + if((void *)ptr == value) { + smDelete(&header->slab[i]); + } + } +} +smEntry *smFindEntry(smHeader const * header, SearchFunction func){ + for (size_t i = 0; i< header->size; ++i ) { + void * value = (void *) atomic_load(&header->slab[i].value); + + if(value != NULL && func(value)) { + return &header->slab[i]; + } + } + return NULL; +} diff --git a/04_exercise/slotmap/slotmap.h b/04_exercise/slotmap/slotmap.h new file mode 100644 index 0000000..1d687fc --- /dev/null +++ b/04_exercise/slotmap/slotmap.h @@ -0,0 +1,36 @@ +// +// Created by stefan on 18.06.20. +// + +#ifndef BETRIEBSYSTEME_SLOTMAP_H +#define BETRIEBSYSTEME_SLOTMAP_H +#include +#include +#include + +typedef struct smNode { + atomic_intptr_t value; +} smEntry; + +typedef struct smHeader { + smEntry *slab; + size_t size; +} smHeader; + +typedef bool (*SearchFunction)(void const *); + +smHeader smInit(smEntry * slab, size_t size); +int smInsert(smHeader const * header, void * value); +void smDelete(smEntry * node); +void smDeleteValue(smHeader const * header, void * value); +/** + * Returns a node whose value is accepted by the SearchFunction + * @param header The header of the slotmap to be searched + * @param func The search function, that will be applied to each element until one is found + * @return the Entry that was found + */ +smEntry *smFindEntry(smHeader const * header, SearchFunction func); + + + +#endif // BETRIEBSYSTEME_SLOTMAP_H diff --git a/04_exercise/threadpool.c b/04_exercise/threadpool.c index d4ee8bb..9d73013 100644 --- a/04_exercise/threadpool.c +++ b/04_exercise/threadpool.c @@ -1,8 +1,8 @@ #include "threadpool.h" -#include "arena_list.h" #include "array.h" #include +#include #include #include #include @@ -19,8 +19,8 @@ typedef struct ThreadPool { /* TODO: benötigte Attribute hinzufügen */ size_t size; Thread *threads; - Node arena[MAX_FUTURES]; - AtomicArenaList al; + smEntry slab [MAX_FUTURES]; + smHeader header; } ThreadPool; ThreadPool threadPool; @@ -31,31 +31,32 @@ bool isFutureWaiting(void const *vFuture) { //This is racy but we'll CAS it later to make sure it's safe return status == FUT_WAITING; } - -void tryRunningFuture(Future *future) { +//TODO Document the behaviour of this function +bool tryRunningFuture(Future * const future) { char expected = FUT_WAITING; // This can happen if multiple threads found the same Future if (!atomic_compare_exchange_strong(&future->status, &expected, FUT_IN_PROGRESS)) { - return; + return false; } - + smDeleteValue(& threadPool.header, future); future->fn(future); - expected = FUT_IN_PROGRESS; - if (!atomic_compare_exchange_strong(&future->status, &expected, FUT_DONE)) { + + if (atomic_exchange(&future->status, FUT_DONE) != FUT_IN_PROGRESS) { perror("The future got marked as done by another thread"); exit(-1); } + return true; } /* TODO: interne Hilfsfunktionen hinzufügen */ bool tryDoingWork() { - Future *future = alFindLastElem(&threadPool.al, &isFutureWaiting); - if (future == NULL) { + smEntry *entry = smFindEntry(&threadPool.header, &isFutureWaiting); + if (entry == NULL) { return false; } + Future * fut = (Future *) entry->value; // This will just return if some other thread was first - tryRunningFuture(future); - return true; + return tryRunningFuture(fut); } /** @brief worker function running in the threadpool */ @@ -78,10 +79,9 @@ _Noreturn void *poolWorkerFunc(void *v_index) { int tpInit(size_t size) { threadPool.size = size; - arrayInit(threadPool.threads); - threadPool.al = alInit(threadPool.arena, MAX_FUTURES); + threadPool.threads = malloc(sizeof(Thread)*size); + threadPool.header = smInit((smEntry *)&threadPool.slab, MAX_FUTURES); for (size_t i = 0; i < size; ++i) { - arrayPush(threadPool.threads); int status; threadPool.threads[i].index = i; if ((status = pthread_create(&threadPool.threads[i].pthread, NULL, @@ -107,13 +107,12 @@ void tpRelease(void) { exit(status); } } - arrayRelease(threadPool.threads); + free(threadPool.threads); } void tpAsync(Future *future) { - if (alPush(&threadPool.al, (void *)future) < -1) { - perror("Push failed"); - exit(-1); + while (smInsert(&threadPool.header, (void *)future) < 0) { + tryDoingWork(); } } @@ -125,5 +124,4 @@ void tpAwait(Future *future) { while (atomic_load(&future->status) != FUT_DONE) { tryDoingWork(); } - alRemoveElem(&threadPool.al, (void *)future); } -- cgit v1.2.3-54-g00ecf