From 7fd168d9bf3775380044ea4b71d693f195e8033c Mon Sep 17 00:00:00 2001 From: Vito Caputo Date: Wed, 2 May 2018 13:23:15 -0700 Subject: *: initial commit of libpulp libpulp is a very basic cooperatively-scheduled userspace threading library. It refers to the userspace threads as fibers, and uses my other little library libthunk to bind the functions and their calling environment into tidy little structures having a uniform calling convention. At this time there's no build system or anything of the sort, it's early days and I'll probably be submoduling this into another project for direct inclusion and compilation. --- src/example.c | 52 +++++++ src/list.h | 252 +++++++++++++++++++++++++++++++++ src/pulp.c | 445 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ src/pulp.h | 36 +++++ 4 files changed, 785 insertions(+) create mode 100644 src/example.c create mode 100644 src/list.h create mode 100644 src/pulp.c create mode 100644 src/pulp.h (limited to 'src') diff --git a/src/example.c b/src/example.c new file mode 100644 index 0000000..f8d4ba8 --- /dev/null +++ b/src/example.c @@ -0,0 +1,52 @@ +/* + * Copyright (C) 2018 Vito Caputo - + * + * This program is free software: you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 3 as published + * by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ +#include +#include +#include + + +THUNK_DEFINE(bar, int, id) +{ + printf("%i ", id); + return 0; +} + + +THUNK_DEFINE(foo, pulp_t *, p, int, w, int, h) +{ + for (int y = 0; y < h; y++) { + printf("\nw=%i h=%i\n", w, h); + for (int x = 0; x < w; x++) + (void) pulp_fiber_new(p, (w - x), THUNK(bar(x))); + + pulp_msleep(p, w + 1); + } + + return 0; +} + + +int main(int argc, char *argv[]) +{ + pulp_t *p; + + p = pulp_new(); + (void) pulp_fiber_new(p, 0, THUNK(foo(p, 40, 100))); + pulp_run(p); + pulp_free(p); + + return 0; +} diff --git a/src/list.h b/src/list.h new file mode 100644 index 0000000..48bca36 --- /dev/null +++ b/src/list.h @@ -0,0 +1,252 @@ +#ifndef __LIST_H +#define __LIST_H + +/* linux kernel linked list interface */ + +/* + * Simple doubly linked list implementation. + * + * Some of the internal functions ("__xxx") are useful when + * manipulating whole lists rather than single entries, as + * sometimes we already know the next/prev entries and we can + * generate better code by using them directly rather than + * using the generic single-entry routines. + */ + +typedef struct list_head { + struct list_head *next, *prev; +} list_head_t; + +#define LIST_HEAD_INIT(name) { &(name), &(name) } + +#define LIST_HEAD(name) \ + struct list_head name = LIST_HEAD_INIT(name) + +#define INIT_LIST_HEAD(ptr) do { \ + (ptr)->next = (ptr); (ptr)->prev = (ptr); \ +} while (0) + +/* + * Insert a new entry between two known consecutive entries. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __list_add(struct list_head *new, + struct list_head *prev, + struct list_head *next) +{ + next->prev = new; + new->next = next; + new->prev = prev; + prev->next = new; +} + +/** + * list_add - add a new entry + * @new: new entry to be added + * @head: list head to add it after + * + * Insert a new entry after the specified head. + * This is good for implementing stacks. + */ +static inline void list_add(struct list_head *new, struct list_head *head) +{ + __list_add(new, head, head->next); +} + +/** + * list_add_tail - add a new entry + * @new: new entry to be added + * @head: list head to add it before + * + * Insert a new entry before the specified head. + * This is useful for implementing queues. + */ +static inline void list_add_tail(struct list_head *new, struct list_head *head) +{ + __list_add(new, head->prev, head); +} + +/* + * Delete a list entry by making the prev/next entries + * point to each other. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __list_del(struct list_head *prev, struct list_head *next) +{ + next->prev = prev; + prev->next = next; +} + +/** + * list_del - deletes entry from list. + * @entry: the element to delete from the list. + * Note: list_empty on entry does not return true after this, the entry is in an undefined state. + */ +static inline void list_del(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + entry->next = (void *) 0; + entry->prev = (void *) 0; +} + +/** + * list_del_init - deletes entry from list and reinitialize it. + * @entry: the element to delete from the list. + */ +static inline void list_del_init(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + INIT_LIST_HEAD(entry); +} + +/** + * list_move - delete from one list and add as another's head + * @list: the entry to move + * @head: the head that will precede our entry + */ +static inline void list_move(struct list_head *list, struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add(list, head); +} + +/** + * list_move_tail - delete from one list and add as another's tail + * @list: the entry to move + * @head: the head that will follow our entry + */ +static inline void list_move_tail(struct list_head *list, + struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add_tail(list, head); +} + +/** + * list_empty - tests whether a list is empty + * @head: the list to test. + */ +static inline int list_empty(struct list_head *head) +{ + return head->next == head; +} + +static inline void __list_splice(struct list_head *list, + struct list_head *head) +{ + struct list_head *first = list->next; + struct list_head *last = list->prev; + struct list_head *at = head->next; + + first->prev = head; + head->next = first; + + last->next = at; + at->prev = last; +} + +/** + * list_splice - join two lists + * @list: the new list to add. + * @head: the place to add it in the first list. + */ +static inline void list_splice(struct list_head *list, struct list_head *head) +{ + if (!list_empty(list)) + __list_splice(list, head); +} + +/** + * list_splice_init - join two lists and reinitialise the emptied list. + * @list: the new list to add. + * @head: the place to add it in the first list. + * + * The list at @list is reinitialised + */ +static inline void list_splice_init(struct list_head *list, + struct list_head *head) +{ + if (!list_empty(list)) { + __list_splice(list, head); + INIT_LIST_HEAD(list); + } +} + +/** + * list_entry - get the struct for this entry + * @ptr: the &struct list_head pointer. + * @type: the type of the struct this is embedded in. + * @member: the name of the list_struct within the struct. + */ +#define list_entry(ptr, type, member) \ + ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) + +/** + * list_for_each - iterate over a list + * @pos: the &struct list_head to use as a loop counter. + * @head: the head for your list. + */ +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); \ + pos = pos->next) +/** + * list_for_each_prev - iterate over a list backwards + * @pos: the &struct list_head to use as a loop counter. + * @head: the head for your list. + */ +#define list_for_each_prev(pos, head) \ + for (pos = (head)->prev; pos != (head); \ + pos = pos->prev) + +/** + * list_for_each_safe - iterate over a list safe against removal of list entry + * @pos: the &struct list_head to use as a loop counter. + * @n: another &struct list_head to use as temporary storage + * @head: the head for your list. + */ +#define list_for_each_safe(pos, n, head) \ + for (pos = (head)->next, n = pos->next; pos != (head); \ + pos = n, n = pos->next) + +/** + * list_for_each_entry - iterate over list of given type + * @pos: the type * to use as a loop counter. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry(pos, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +/** + * list_for_each_entry_prev - iterate over list of given type backwards + * @pos: the type * to use as a loop counter. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_prev(pos, head, member) \ + for (pos = list_entry((head)->prev, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.prev, typeof(*pos), member)) + + +/** + * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry + * @pos: the type * to use as a loop counter. + * @n: another type * to use as temporary storage + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_safe(pos, n, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member), \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member)) + + +#endif diff --git a/src/pulp.c b/src/pulp.c new file mode 100644 index 0000000..fdb95cd --- /dev/null +++ b/src/pulp.c @@ -0,0 +1,445 @@ +/* + * Copyright (C) 2018 Vito Caputo - + * + * This program is free software: you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 3 as published + * by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +/* pulp implements a very simple cooperative multi-tasking scheduler + * with zero consideration for IO-wait states. This only concerns itself + * with the switching of lightweight CPU-bound fibers which may either + * exit, sleep for a specified duration, or go idle indefinitely with + * the possibility of being awoken by other fibers via the pulp api. + * + * No consideration for SMP/threads has been made, no locking or atomic + * stuff is in effect here. You can run a pulp scheduler per-thread to + * scale to SMP, but migrating/stealing fibers across the per-thread schedulers + * is not supported at this time. + * + */ + +#include +#include +#include +#include +#include +#include +#include + +#include "list.h" +#include "pulp.h" + +/* for when this needs to support windows: + * https://www.codeproject.com/Tips/4225/Unix-ucontext-t-Operations-on-Windows-Platforms + */ + +#define PULP_USECS_PER_SEC 1000000ULL +#define PULP_USECS_PER_MSEC 1000ULL +#define PULP_FIBER_STACK_SIZE (16 * 1024) +#define PULP_FIBER_ALLOC_NUM 32 + +typedef struct pulp_context_t { + ucontext_t ucontext; + char stack[PULP_FIBER_STACK_SIZE]; +} pulp_context_t; + +typedef struct pulp_fiber_t { + list_head_t fibers; /* node on free/idle/run/sleep list */ + union { + struct { + pulp_usec_t alarm; + } sleep; + } state; + + pulp_context_t context; +} pulp_fiber_t; + +typedef struct pulp_fiber_alloc_t { + list_head_t allocs; + unsigned n_fibers; + pulp_fiber_t fibers[]; +} pulp_fiber_alloc_t; + +typedef struct pulp_t { + pulp_fiber_t *current; /* currently running fiber */ + pulp_usec_t now; /* current time updated @ schedule via expire_alarms() */ + int exited:1; /* set when pulp_exit() triggered switch to caller */ + struct { + list_head_t free; + list_head_t idle; + list_head_t run; + list_head_t sleep; + } fibers; + + list_head_t allocs; /* list of pulp_fiber_alloc_t */ + pulp_context_t schedule_context; + pulp_context_t caller_context; +} pulp_t; + + +static void pulp_schedule(pulp_t *pulp); + + +/* allocate more free fibers */ +static int more_fibers(pulp_t *pulp) +{ + pulp_fiber_alloc_t *alloc; + unsigned i; + + assert(pulp); + + alloc = calloc(1, sizeof(pulp_fiber_alloc_t) + sizeof(pulp_fiber_t) * PULP_FIBER_ALLOC_NUM); + if (!alloc) + return -ENOMEM; + + alloc->n_fibers = PULP_FIBER_ALLOC_NUM; /* TODO: maybe grow this? */ + for (i = 0; i < alloc->n_fibers; i++) { + pulp_fiber_t *fiber = &alloc->fibers[i]; + + list_add_tail(&fiber->fibers, &pulp->fibers.free); + } + + list_add(&alloc->allocs, &pulp->allocs); + + return 0; +} + + +/* put the current fiber on a list @ tail */ +/* note pulp->current is left intact, it's pulp_schedule()'s responsibility + * to replace it. */ +static inline void put_current_fiber(pulp_t *pulp, list_head_t *where) +{ + assert(pulp); + assert(where); + assert(pulp->current); + + list_add(&pulp->current->fibers, where); +} + + +/* set the current fiber from the first entry on the list at head */ +static inline void set_current_fiber(pulp_t *pulp, list_head_t *head) +{ + assert(pulp); + assert(head); + assert(!list_empty(head)); + + pulp->current = list_entry(head->next, pulp_fiber_t, fibers); + list_del(&pulp->current->fibers); +} + + +/* setup a context to run func w/ptr */ +static void setup_context(pulp_t *pulp, pulp_context_t *context, void *func, void *ptr) +{ + assert(pulp); + assert(context); + assert(func); + + getcontext(&context->ucontext); + context->ucontext.uc_stack.ss_sp = context->stack; + context->ucontext.uc_stack.ss_size = sizeof(context->stack); + context->ucontext.uc_link = &pulp->schedule_context.ucontext; + makecontext(&context->ucontext, func, 1, ptr); +} + + +/* sets the supplied context as the executing context */ +static void enter_context(pulp_context_t *context) +{ + assert(context); + + setcontext(&context->ucontext); +} + + +/* swaps the new supplied context with the executing context */ +/* the current context is saved in old */ +static void swap_context(pulp_context_t *old, pulp_context_t *new) +{ + assert(old); + assert(new); + + if (old == new) + return; + + swapcontext(&old->ucontext, &new->ucontext); +} + + +/* handle a return out of a fiber, equivalent to the fiber exiting */ +static void schedule_context(pulp_t *pulp) +{ + assert(pulp); + + if (pulp->current) + put_current_fiber(pulp, &pulp->fibers.free); + + pulp_schedule(pulp); +} + + +/* return time of day in microseconds */ +static pulp_usec_t now(void) +{ + struct timeval ts_now; + pulp_usec_t now; + + gettimeofday(&ts_now, NULL); + now = ts_now.tv_sec * PULP_USECS_PER_SEC; + now += ts_now.tv_usec; + + return now; +} + + +/* create a new pulp scheduler instance */ +pulp_t * pulp_new(void) +{ + pulp_t *pulp; + + pulp = calloc(1, sizeof(pulp_t)); + if (!pulp) + return NULL; + + INIT_LIST_HEAD(&pulp->fibers.free); + INIT_LIST_HEAD(&pulp->fibers.idle); + INIT_LIST_HEAD(&pulp->fibers.run); + INIT_LIST_HEAD(&pulp->fibers.sleep); + INIT_LIST_HEAD(&pulp->allocs); + + if (more_fibers(pulp) < 0) { + free(pulp); + return NULL; + } + + setup_context(pulp, &pulp->schedule_context, schedule_context, pulp); + pulp->now = now(); + + return pulp; +} + + +/* free a pulp scheduler instance */ +void pulp_free(pulp_t *pulp) +{ + pulp_fiber_alloc_t *alloc, *_alloc; + + assert(pulp); + + list_for_each_entry_safe(alloc, _alloc, &pulp->allocs, allocs) + free(alloc); + + free(pulp); +} + + +/* move any expired sleeps from pulp->fibers.sleep to run */ +static void expire_alarms(pulp_t *pulp) +{ + pulp_fiber_t *f, *_f; + + assert(pulp); + + pulp->now = now(); + + /* TODO: use a priority queue */ + list_for_each_entry_safe(f, _f, &pulp->fibers.sleep, fibers) { + if (pulp->now >= f->state.sleep.alarm) + list_move_tail(&f->fibers, &pulp->fibers.run); + } +} + + +/* schedule and switch to the next fiber */ +static void pulp_schedule(pulp_t *pulp) +{ + pulp_context_t *target_context = &pulp->caller_context; + pulp_fiber_t *current; + + assert(pulp); + + expire_alarms(pulp); + + current = pulp->current; + pulp->current = NULL; + + if (!list_empty(&pulp->fibers.run)) { + set_current_fiber(pulp, &pulp->fibers.run); + target_context = &pulp->current->context; + } + + if (current) + swap_context(¤t->context, target_context); + else + enter_context(target_context); +} + + +/* Tick a pulp scheduler - runs fibers until all are idle/sleeping. + * An estimate of how much time may pass before the next tick should occur is stored in next_tick_delay_us. + * If pulp_exit() is called by a fiber, or no more fibers exist, the return value is -1, and next_tick_delay_us is ignored. + * If all fibers are idle, the return value is 0, and next_tick_delay_us is ignored. + * If any fibers are sleeping, the return value is 1, and next_tick_delay_us is useful. + */ +int pulp_tick(pulp_t *pulp, unsigned *next_tick_delay_us) +{ + assert(pulp); + + swap_context(&pulp->caller_context, &pulp->schedule_context); + + if (pulp->exited) + return -1; + + /* every tick drains the run queue currently */ + assert(list_empty(&pulp->fibers.run)); + + if (!list_empty(&pulp->fibers.sleep)) { + /* TODO: get delay from the sleep queue when it's a priority queue */ + *next_tick_delay_us = 333; + + return 1; + } + + if (!list_empty(&pulp->fibers.idle)) + return 0; + + return -1; +} + + +/* run a pulp scheduler until pulp_exit() is called or all fibers return */ +void pulp_run(pulp_t *pulp) +{ + for (;;) { + unsigned delay = 1000000; + + switch (pulp_tick(pulp, &delay)) { + case 0: + /* XXX: everything idle is a terminally wedged state in pulp_run(), + * unless I suppose a signal handler changes a fiber state. + */ + assert(0); + /* or fall-through to a sleep on NDEBUG */ + + case 1: { + struct timespec ts_delay = { 0, delay * 1000 }; + + /* TODO: get the minimum sleep from the priority queue when implemented, for now we spin a bit. */ + nanosleep(&ts_delay, NULL); + break; + } + + case -1: + return; + } + } +} + + +/* exit a pulp scheduler from within a fiber */ +/* this causes pulp_tick() to return immediately. */ +void pulp_exit(pulp_t *pulp) +{ + assert(pulp); + + pulp->exited = 1; + enter_context(&pulp->caller_context); +} + + +/* find a free fiber - this returns the next free fiber but does not + * modify its free state, it remains on the free list at return. + */ +static pulp_fiber_t * find_free_fiber(pulp_t *pulp) +{ + assert(pulp); + + if (list_empty(&pulp->fibers.free) && more_fibers(pulp) < 0) + return NULL; + + return list_entry(pulp->fibers.free.next, pulp_fiber_t, fibers); +} + + +/* run a new fiber on a pulp scheduler after delay_ms milliseconds (0 for immediately). + * returns the created fiber in case the caller wants to + * retain the ability to operate on it. Fibers are automatically + * reclaimed on return so this generally isn't necessary. + */ +pulp_fiber_t * pulp_fiber_new(pulp_t *pulp, unsigned delay_ms, thunk_t *thunk) +{ + pulp_fiber_t *fiber; + + assert(pulp); + assert(thunk); + + fiber = find_free_fiber(pulp); + if (!fiber) + return NULL; + + setup_context(pulp, &fiber->context, thunk->dispatch, thunk); + + if (!delay_ms) { + list_move_tail(&fiber->fibers, &pulp->fibers.run); + } else { + fiber->state.sleep.alarm = pulp->now + delay_ms * PULP_USECS_PER_MSEC; + list_move_tail(&fiber->fibers, &pulp->fibers.sleep); + } + + return fiber; +} + + +/* sleep for the supplied number of microseconds (not public) */ +static void pulp_usleep(pulp_t *pulp, unsigned useconds) +{ + assert(pulp); + + pulp->current->state.sleep.alarm = pulp->now + useconds; + put_current_fiber(pulp, &pulp->fibers.sleep); + pulp_schedule(pulp); +} + + +/* sleep for the supplied number of milliseconds */ +void pulp_msleep(pulp_t *pulp, unsigned milliseconds) +{ + assert(pulp); + + return pulp_usleep(pulp, milliseconds * PULP_USECS_PER_MSEC); +} + + +/* sleep for the supplied number of seconds */ +void pulp_sleep(pulp_t *pulp, unsigned seconds) +{ + assert(pulp); + + return pulp_usleep(pulp, seconds * PULP_USECS_PER_SEC); +} + + +/* return 'now' from the scheduler */ +/* this is a convenience/optimization for fibers which need the current + * time - the scheduler already caches it, so make it available. + */ +pulp_usec_t pulp_now(pulp_t *pulp) +{ + return pulp->now; +} + + +/* TODO: interfaces for idling/waking fibers */ +/* TODO: interfaces for synchronization across fibers */ +/* all these are left to be implemented as their needs arise */ diff --git a/src/pulp.h b/src/pulp.h new file mode 100644 index 0000000..fb270f0 --- /dev/null +++ b/src/pulp.h @@ -0,0 +1,36 @@ +/* + * Copyright (C) 2018 Vito Caputo - + * + * This program is free software: you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 3 as published + * by the Free Software Foundation. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with this program. If not, see . + */ + +#ifndef _PULP_H +#define _PULP_H + +#include +#include + +typedef struct pulp_fiber_t pulp_fiber_t; +typedef struct pulp_t pulp_t; +typedef uint64_t pulp_usec_t; + +pulp_t * pulp_new(void); +void pulp_free(pulp_t *pulp); +int pulp_tick(pulp_t *pulp, unsigned *next_tick_delay_us); +void pulp_run(pulp_t *pulp); +pulp_fiber_t * pulp_fiber_new(pulp_t *pulp, unsigned delay_ms, thunk_t *thunk); +void pulp_msleep(pulp_t *pulp, unsigned milliseconds); +void pulp_sleep(pulp_t *pulp, unsigned seconds); +pulp_usec_t pulp_now(pulp_t *pulp); + +#endif -- cgit v1.2.3