From d1c74f98db73d4c643bb2d0e0338b350a05289b0 Mon Sep 17 00:00:00 2001 From: David Kerkeslager Date: Sat, 10 Sep 2016 12:07:34 -0400 Subject: [PATCH] Some work on the vm --- vm/instruction.c | 19 +++++++++++++++ vm/mpsc_queue.c | 55 ++++++++++++++++++++++++-------------------- vm/mpsc_queue_test.c | 6 ++--- vm/thread.c | 27 ++++++++++++++++++++++ 4 files changed, 79 insertions(+), 28 deletions(-) create mode 100644 vm/instruction.c create mode 100644 vm/thread.c diff --git a/vm/instruction.c b/vm/instruction.c new file mode 100644 index 0000000..c39f68d --- /dev/null +++ b/vm/instruction.c @@ -0,0 +1,19 @@ +// Call a function +void callFunction(Thread* thread); + +// Return from the current function +// If the stack is empty, end the thread +void returnFromFunction(Thread* thread); + +// Call a function on a new thread +void startThread(Thread* thread); + +// Process a message in the inbox +// If the inbox is empty, defer to another thread +void receive(Thread* thread); + +// Send a message to another thread's inbox +void send(Thread* thread); + +// Add two numbers +void add(Thread* thread); diff --git a/vm/mpsc_queue.c b/vm/mpsc_queue.c index a665a0f..76646b3 100644 --- a/vm/mpsc_queue.c +++ b/vm/mpsc_queue.c @@ -1,17 +1,20 @@ +#ifndef MPSC_QUEUE +#define MPSC_QUEUE + #include #include -struct Queue; -typedef struct Queue Queue; -struct QueueNode; -typedef struct QueueNode QueueNode; +struct MPSCQueue; +typedef struct MPSCQueue MPSCQueue; +struct MPSCQueueNode; +typedef struct MPSCQueueNode MPSCQueueNode; -void initializeQueue(Queue* queue); -void enqueue(Queue* queue, void* item); -void* dequeue(Queue* queue); -void freeQueue(Queue* queue, void (*itemFreer)(void*)); +void initializeMPSCQueue(MPSCQueue* queue); +void enqueue(MPSCQueue* queue, void* item); +void* dequeue(MPSCQueue* queue); +void destructMPSCQueue(MPSCQueue* queue, void (*itemFreer)(void*)); -struct Queue +struct MPSCQueue { // This implements a multiple-producer, single-consumer lockless concurrent // queue. @@ -24,35 +27,35 @@ struct Queue // dequeued. In fact, `head->item` may have been freed after it was // dequeued, so we should never dereference it. // 2. At initialization, no item has been dequeued yet, so we must allocate - // an extra `QueueNode` at initialization which will never be used to + // an extra `MPSCQueueNode` at initialization which will never be used to // store an item. // // However, this extra memory allocation at initialization means that we // never have to check whether `head` or `tail` are `NULL`, or initialize // these variables concurrently, which are expensive operations. - QueueNode* head; - QueueNode* tail; + MPSCQueueNode* head; + MPSCQueueNode* tail; }; -struct QueueNode +struct MPSCQueueNode { // This implements a singly-linked list. void* item; - QueueNode* next; + MPSCQueueNode* next; }; -void initializeQueue(Queue* queue) +void initializeMPSCQueue(MPSCQueue* queue) { // Initialize the queue with a node that fakes the previously dequeued item. // We don't have to initialize `dummyNode->item` because it will never be // used. - QueueNode* dummyNode = malloc(sizeof(QueueNode)); + MPSCQueueNode* dummyNode = malloc(sizeof(MPSCQueueNode)); dummyNode->next = NULL; queue->head = dummyNode; queue->tail = dummyNode; } -bool isEmpty(Queue* queue) +bool isEmpty(MPSCQueue* queue) { // In a normal singly-linked list, the list is empty when the `head` is // `NULL`, but here the queue is empty when the `head` is the same as the @@ -60,10 +63,10 @@ bool isEmpty(Queue* queue) return queue->head == queue->tail; } -void enqueue(Queue* queue, void* item) +void enqueue(MPSCQueue* queue, void* item) { // Create the node that will be the new tail. - QueueNode* node = malloc(sizeof(QueueNode)); + MPSCQueueNode* node = malloc(sizeof(MPSCQueueNode)); node->item = item; node->next = NULL; @@ -82,36 +85,38 @@ void enqueue(Queue* queue, void* item) // We don't have to worry that another thread might have appended more // nodes; advancing `queue->tail` to the end of the linked list is always // the correct thing to do. - QueueNode* tail; + MPSCQueueNode* tail; while((tail = queue->tail)->next != NULL) { __sync_val_compare_and_swap(&(queue->tail), tail, tail->next); } } -void* dequeue(Queue* queue) +void* dequeue(MPSCQueue* queue) { if(isEmpty(queue)) { return NULL; // TODO Provide ability to return a defined default. } - QueueNode* oldHead = queue->head; + MPSCQueueNode* oldHead = queue->head; queue->head = oldHead->next; free(oldHead); return queue->head->item; } -void freeQueue(Queue* queue, void (*itemFreer)(void*)) +void destructMPSCQueue(MPSCQueue* queue, void (*itemFreer)(void*)) { - QueueNode* current = queue->head; + MPSCQueueNode* current = queue->head; while(current != NULL) { itemFreer(current->item); - QueueNode* temp = current->next; + MPSCQueueNode* temp = current->next; free(current); current = temp; } } + +#endif diff --git a/vm/mpsc_queue_test.c b/vm/mpsc_queue_test.c index be869c8..1fb6598 100644 --- a/vm/mpsc_queue_test.c +++ b/vm/mpsc_queue_test.c @@ -7,8 +7,8 @@ void noopFreer(void* _) { } bool test_single_threaded() { - Queue queue; - initializeQueue(&queue); + MPSCQueue queue; + initializeMPSCQueue(&queue); int inputs[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 }; @@ -30,7 +30,7 @@ bool test_single_threaded() assert(i == *(outputs[i])); } - freeQueue(&queue, noopFreer); + freeMPSCQueue(&queue, noopFreer); return true; } diff --git a/vm/thread.c b/vm/thread.c new file mode 100644 index 0000000..87a1ec6 --- /dev/null +++ b/vm/thread.c @@ -0,0 +1,27 @@ +#ifndef THREAD +#define THREAD + +#include "mpsc_queue.c" + +struct Thread; +typedef struct Thread Thread; + +void initializeThread(Thread* thread); +void destructThread(Thread* thread); + +struct Thread +{ + MPSCQueue inbox; +}; + +void initializeThread(Thread* thread) +{ + initializeMPSCQueue(&(thread->inbox)); +} + +void destructThread(Thread* thread) +{ + destructMPSCQueue(&(thread->inbox)); +} + +#endif -- 2.20.1