From b9771b85d4f543af78465985e6350c0ca57f4c70 Mon Sep 17 00:00:00 2001 From: Stefan Zabka Date: Thu, 11 Jun 2020 23:24:02 +0200 Subject: Broken Mess --- 04_exercise/arena/arena_list.c | 123 ++++++++++++++++++++++++++++------------- 04_exercise/arena/arena_list.h | 32 ++++++++--- 04_exercise/arena/arena_test.c | 14 ++++- 3 files changed, 123 insertions(+), 46 deletions(-) (limited to '04_exercise/arena') diff --git a/04_exercise/arena/arena_list.c b/04_exercise/arena/arena_list.c index 822f8f0..4becef6 100644 --- a/04_exercise/arena/arena_list.c +++ b/04_exercise/arena/arena_list.c @@ -2,6 +2,12 @@ // Created by stefan on 10.06.20. // #include "arena_list.h" +#include +#include +#include +#include + +#include Node *listPopFront(List *list) { Node *front = list->first; @@ -16,14 +22,30 @@ Node *listPopFront(List *list) { return front; } - if (front->next != NULL) { - list->first->prev = NULL; - front->next = NULL; - } + list->first->prev = NULL; + front->next = NULL; + return front; } -Node *listPopBack(List* list) { return NULL; } +Node *listPopBack(List *list) { + Node *back = list->last; + if (back == NULL) { + return NULL; + } + + list->last = back->prev; + if (back == list->first) { + // Only Node in the list + list->last = NULL; + return back; + } + + list->last->next = NULL; + back->prev = NULL; + + return back; +} void listPushFront(List *list, Node *new) { if (list->first == NULL) { @@ -38,14 +60,14 @@ void listPushFront(List *list, Node *new) { list->first = new; } -void listPushBack(List* list, Node *value) {} +// void listPushBack(List *list, Node *value) {} -ArenaList alInit(Node *arena, size_t size) { - ArenaList al; - al.activeList = (List){.first = NULL, .last = NULL}; - al.freeList = (List){.first = arena, .last = &arena[size - 1]}; - al.arena = arena; - al.size = size; +AtomicArenaList alInit(Node *arena, size_t size) { + AtomicArenaList al = {.activeList = (List){.first = NULL, .last = NULL}, + .freeList = (List){.first = arena, .last = &arena[size - 1]}, + .arena = arena, + .size = size}; + atomic_init(&al.lock, RW_UNLOCKED); arena[0] = (Node){.value = NULL, .prev = NULL, .next = &arena[1]}; for (size_t i = 1; i < size - 1; ++i) { arena[i] = (Node){.value = NULL, .prev = &arena[i - 1], .next = &arena[i + 1]}; @@ -54,48 +76,73 @@ ArenaList alInit(Node *arena, size_t size) { return al; } -int alPush(ArenaList* al, void *value) { +int alPush(AtomicArenaList *al, void *value) { + fprintf(stderr, "Thread %lu: Pushing \n", pthread_self() % 1000); + rwLockWrite(&al->lock); Node *current = listPopFront(&al->freeList); // List is empty if (current == NULL) { + rwUnlockWrite(&al->lock); return -1; } current->value = value; listPushFront(&al->activeList, current); + rwUnlockWrite(&al->lock); return 0; } +int alRemoveElem(AtomicArenaList *al, void *value) { + fprintf(stderr, "Thread %lu: Removing element \n", pthread_self() % 1000); + rwLockWrite(&al->lock); + for (size_t i = 0; i < al->size; ++i) { + if (al->arena[i].value != value) { + continue; + } + Node *node = &al->arena[i]; + if (node == al->activeList.first) { + listPopFront(&al->activeList); + listPushFront(&al->freeList, node); + atomic_char *a = &al->lock; + rwUnlockWrite(a); + return 0; + } + if (node == al->activeList.last) { + listPopBack(&al->activeList); + listPushFront(&al->freeList, node); + rwUnlockWrite(&al->lock); + return 0; + } + // The node is somewhere in the middle + Node *prev = node->prev; + Node *next = node->next; + next->prev = prev; + prev->next = next; -int alRemoveElem(ArenaList* al, void * value){ - for(size_t i = 0; i < al->size; ++i) { - if(al->arena[i].value == value) { - return alRemove(al, &al->arena[i]); - } + listPushFront(&al->freeList, node); + rwUnlockWrite(&al->lock); + return 0; } + rwUnlockWrite(&al->lock); return -1; } -int alRemove(ArenaList* al, Node * node) { - //TODO Should we check that the node is actually in the active list - //Maybe as an assert that gets optimized out - if(node == al->activeList.first) { - listPopFront(&al->activeList); - listPushFront(&al->freeList, node); - return 0; - } - if(node == al->activeList.last) { - listPopBack(&al->activeList); - listPushFront(&al->freeList, node); - return 0; - } - // The node is somewhere in the middle - Node * prev = node ->prev; - Node * next = node ->next; +void *alFindLastElem(AtomicArenaList *al, SearchFunction f) { + fprintf(stderr, "Thread %lu: Finding last element \n", pthread_self() % 1000); - next->prev = prev; - prev->next = next; + rwLockRead(&al->lock); - listPushFront(&al->freeList, node); - return 0; + List const *const actList = &al->activeList; + if (actList->last == NULL) { + rwUnlockRead(&al->lock); + return NULL; + } + for (Node *current = actList->last; current != NULL; current = current->prev) { + if (f(current->value)) { + rwUnlockRead(&al->lock); + return current; + } + } + rwUnlockRead(&al->lock); + return NULL; } diff --git a/04_exercise/arena/arena_list.h b/04_exercise/arena/arena_list.h index 387f881..304209c 100644 --- a/04_exercise/arena/arena_list.h +++ b/04_exercise/arena/arena_list.h @@ -6,6 +6,9 @@ #define BETRIEBSYSTEME_ARENA_LIST_H #include +#include +#include + typedef struct Node { void * value; struct Node * next; @@ -16,24 +19,39 @@ typedef struct List { Node * first; Node * last; } List; -// This structure manages an arena / memory slab to be used + + // Should we have a free list or just a bit set relative to the size of the slab? +/** This structure manages an arena / memory slab to be used + * This structure is thread-safe as it locks internally + * It will spin until a request is safe to access the items + * This also means this structure shouldn't be read externally + * unless the thread doing so managed to aquire the atomic_flag + */ typedef struct ArenaList { List freeList; List activeList; Node * arena; size_t size; -} ArenaList; + atomic_char lock; +} AtomicArenaList; +typedef bool (*SearchFunction)(void const *); //Initializes the node array -ArenaList alInit(Node * arena, size_t size); +AtomicArenaList alInit(Node * arena, size_t size); // Return -1 if the List is full -int alPush(ArenaList* al, void * value); +int alPush(AtomicArenaList * al, void * value); // Return -1 if the Node was already deleted -int alRemove(ArenaList* al, Node * node); +int alRemoveElem(AtomicArenaList * al, void * value); -// Return -1 if the Node was already deleted -int alRemoveElem(ArenaList* al, void * value); +/** + * Searches the activeList for an element + * for which the search function returns true + * The function will be passed the value pointer + * of a given Node + * @return the Element pointed or NULL if nothing matched + */ +void *alFindLastElem(AtomicArenaList *al, SearchFunction f); #endif // BETRIEBSYSTEME_ARENA_LIST_H diff --git a/04_exercise/arena/arena_test.c b/04_exercise/arena/arena_test.c index b0927f1..51a9b0c 100644 --- a/04_exercise/arena/arena_test.c +++ b/04_exercise/arena/arena_test.c @@ -3,9 +3,14 @@ // #include "arena_list.h" #include +#include +bool isEqualTo3(void const *data) { + int *value = (void *)data; + return *value == 3; +} int main() { Node arena[5]; - ArenaList al = alInit(arena, 5); + AtomicArenaList al = alInit(arena, 5); int data[5] = {1, 2, 3, 4, 5}; for (int i = 0; i < 5; ++i) { alPush(&al, &data[4 - i]); @@ -14,5 +19,12 @@ int main() { for (Node *cur = al.activeList.first; cur != NULL; cur = cur->next) { printf("Got digit %d \n", *(int *)cur->value); } + Node const * node = alFindLastElem(&al, &isEqualTo3); + int * value = (int *) node->value; + printf("The value was actually %d \n", *value); + assert(*value == 3); + for (int i = 0; i < 5; ++i) { + alRemoveElem(&al, &data[4 - i]); + } } -- cgit v1.2.3-54-g00ecf