diff options
Diffstat (limited to 'libcr_ipc')
| -rw-r--r-- | libcr_ipc/CMakeLists.txt | 26 | ||||
| -rw-r--r-- | libcr_ipc/chan.c | 167 | ||||
| -rw-r--r-- | libcr_ipc/include/libcr_ipc/_linkedlist.h | 108 | ||||
| -rw-r--r-- | libcr_ipc/include/libcr_ipc/chan.h | 240 | ||||
| -rw-r--r-- | libcr_ipc/include/libcr_ipc/mutex.h | 46 | ||||
| -rw-r--r-- | libcr_ipc/include/libcr_ipc/rpc.h | 231 | ||||
| -rw-r--r-- | libcr_ipc/include/libcr_ipc/rwmutex.h | 78 | ||||
| -rw-r--r-- | libcr_ipc/include/libcr_ipc/select.h | 179 | ||||
| -rw-r--r-- | libcr_ipc/include/libcr_ipc/sema.h | 61 | ||||
| -rw-r--r-- | libcr_ipc/mutex.c | 44 | ||||
| -rw-r--r-- | libcr_ipc/rpc.c | 84 | ||||
| -rw-r--r-- | libcr_ipc/rwmutex.c | 98 | ||||
| -rw-r--r-- | libcr_ipc/sema.c | 62 | ||||
| -rw-r--r-- | libcr_ipc/tests/config.h | 20 | ||||
| -rw-r--r-- | libcr_ipc/tests/test.h | 21 | ||||
| -rw-r--r-- | libcr_ipc/tests/test_chan.c | 49 | ||||
| -rw-r--r-- | libcr_ipc/tests/test_mutex.c | 37 | ||||
| -rw-r--r-- | libcr_ipc/tests/test_rpc.c | 59 | ||||
| -rw-r--r-- | libcr_ipc/tests/test_rwmutex.c | 88 | ||||
| -rw-r--r-- | libcr_ipc/tests/test_select.c | 90 | ||||
| -rw-r--r-- | libcr_ipc/tests/test_sema.c | 76 |
21 files changed, 1255 insertions, 609 deletions
diff --git a/libcr_ipc/CMakeLists.txt b/libcr_ipc/CMakeLists.txt index d44203e..60d3f2d 100644 --- a/libcr_ipc/CMakeLists.txt +++ b/libcr_ipc/CMakeLists.txt @@ -1,10 +1,30 @@ -# libcr_ipc/CMakeLists.txt - TODO +# libcr_ipc/CMakeLists.txt - IPC primitives for libcr # -# Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> +# Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> # SPDX-License-Identifier: AGPL-3.0-or-later add_library(libcr_ipc INTERFACE) -target_include_directories(libcr_ipc SYSTEM INTERFACE ${CMAKE_CURRENT_LIST_DIR}/include) +target_include_directories(libcr_ipc PUBLIC INTERFACE ${CMAKE_CURRENT_LIST_DIR}/include) +target_sources(libcr_ipc INTERFACE + chan.c + mutex.c + rpc.c + rwmutex.c + sema.c +) target_link_libraries(libcr_ipc INTERFACE libcr + libmisc +) + +set(ipc_tests + chan + mutex + rpc + rwmutex + select + sema ) +foreach(test IN LISTS ipc_tests) + add_lib_test(libcr_ipc "test_${test}") +endforeach() diff --git a/libcr_ipc/chan.c b/libcr_ipc/chan.c new file mode 100644 index 0000000..6cbe890 --- /dev/null +++ b/libcr_ipc/chan.c @@ -0,0 +1,167 @@ +/* libcr_ipc/chan.c - Simple channels for libcr + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <alloca.h> /* for alloca() */ +#include <string.h> /* for memcpy() */ + +#include <libcr/coroutine.h> /* for cid_t, cr_* */ +#include <libmisc/assert.h> +#include <libmisc/rand.h> + +#include <libcr_ipc/chan.h> + +/* base channels **************************************************************/ + +struct cr_chan_waiter { + cid_t cid; + void *val_ptr; + void (*dequeue)(void *, size_t); + void *dequeue_arg1; + size_t dequeue_arg2; +}; +DLIST_DECLARE_NODE(_cr_chan_waiter_list, struct cr_chan_waiter); + +void cr_chan_dequeue(void *_ch, size_t) { + struct _cr_chan *ch = _ch; + dlist_pop_from_front(&ch->waiters); +} + +void _cr_chan_xfer(enum _cr_chan_waiter_typ self_typ, struct _cr_chan *ch, void *val_ptr, size_t val_size) { + assert(ch); + assert(val_ptr); + + if (ch->waiters.front && ch->waiter_typ != self_typ) { /* non-blocking fast-path */ + /* Copy. */ + struct _cr_chan_waiter_list_node *front = ch->waiters.front; + if (self_typ == _CR_CHAN_SENDER) + memcpy(front->val.val_ptr, val_ptr, val_size); + else + memcpy(val_ptr, front->val.val_ptr, val_size); + cr_unpause(front->val.cid); + front->val.dequeue(front->val.dequeue_arg1, + front->val.dequeue_arg2); + cr_yield(); + } else { /* blocking slow-path */ + struct _cr_chan_waiter_list_node self = { .val = { + .cid = cr_getcid(), + .val_ptr = val_ptr, + .dequeue = cr_chan_dequeue, + .dequeue_arg1 = ch, + }}; + dlist_push_to_rear(&ch->waiters, &self); + ch->waiter_typ = self_typ; + cr_pause_and_yield(); + } +} + +/* select *********************************************************************/ + +enum cr_select_class { + CR_SELECT_CLASS_DEFAULT, + CR_SELECT_CLASS_BLOCKING, + CR_SELECT_CLASS_NONBLOCK, +}; + +struct cr_select_waiters { + size_t cnt; + struct cr_select_arg *args; + struct _cr_chan_waiter_list_node *nodes; +}; + +static inline enum cr_select_class cr_select_getclass(struct cr_select_arg arg) { + switch (arg.op) { + case _CR_SELECT_OP_RECV: + if (arg.ch->waiters.front && arg.ch->waiter_typ == _CR_CHAN_SENDER) + return CR_SELECT_CLASS_NONBLOCK; + else + return CR_SELECT_CLASS_BLOCKING; + case _CR_SELECT_OP_SEND: + if (arg.ch->waiters.front && arg.ch->waiter_typ == _CR_CHAN_RECVER) + return CR_SELECT_CLASS_NONBLOCK; + else + return CR_SELECT_CLASS_BLOCKING; + case _CR_SELECT_OP_DEFAULT: + return CR_SELECT_CLASS_DEFAULT; + default: + assert_notreached("invalid arg.op"); + } +} + +void cr_select_dequeue(void *_waiters, size_t idx) { + struct cr_select_waiters *waiters = _waiters; + for (size_t i = 0; i < waiters->cnt; i++) + dlist_remove(&(waiters->args[i].ch->waiters), + &(waiters->nodes[i])); + waiters->cnt = idx; +} + +size_t cr_select_v(size_t arg_cnt, struct cr_select_arg arg_vec[]) { + size_t cnt_blocking = 0; + size_t cnt_nonblock = 0; + size_t cnt_default = 0; + + assert(arg_cnt); + assert(arg_vec); + cr_assert_in_coroutine(); + + for (size_t i = 0; i < arg_cnt; i++) { + switch (cr_select_getclass(arg_vec[i])) { + case CR_SELECT_CLASS_BLOCKING: + cnt_blocking++; + break; + case CR_SELECT_CLASS_NONBLOCK: + cnt_nonblock++; + break; + case CR_SELECT_CLASS_DEFAULT: + cnt_default++; + break; + } + } + + if (cnt_nonblock) { + size_t choice = rand_uint63n(cnt_nonblock); + for (size_t i = 0, seen = 0; i < arg_cnt; i++) { + if (cr_select_getclass(arg_vec[i]) == CR_SELECT_CLASS_NONBLOCK) { + if (seen == choice) { + _cr_chan_xfer(arg_vec[i].op == _CR_SELECT_OP_RECV + ? _CR_CHAN_RECVER + : _CR_CHAN_SENDER, + arg_vec[i].ch, + arg_vec[i].val_ptr, + arg_vec[i].val_siz); + return i; + } + seen++; + } + } + assert_notreached("should have returned from inside for() loop"); + } + + if (cnt_default) { + for (size_t i = 0; i < arg_cnt; i++) + if (cr_select_getclass(arg_vec[i]) == CR_SELECT_CLASS_DEFAULT) + return i; + assert_notreached("should have returned from inside for() loop"); + } + + struct cr_select_waiters waiters = { + .cnt = arg_cnt, + .args = arg_vec, + .nodes = alloca(sizeof(struct cr_chan_waiter) * arg_cnt), + }; + for (size_t i = 0; i < arg_cnt; i++) { + waiters.nodes[i] = (struct _cr_chan_waiter_list_node){ .val = { + .cid = cr_getcid(), + .val_ptr = arg_vec[i].val_ptr, + .dequeue = cr_select_dequeue, + .dequeue_arg1 = &waiters, + .dequeue_arg2 = i, + }}; + dlist_push_to_rear(&arg_vec[i].ch->waiters, &waiters.nodes[i]); + } + cr_pause_and_yield(); + return waiters.cnt; +} diff --git a/libcr_ipc/include/libcr_ipc/_linkedlist.h b/libcr_ipc/include/libcr_ipc/_linkedlist.h deleted file mode 100644 index e5aa52a..0000000 --- a/libcr_ipc/include/libcr_ipc/_linkedlist.h +++ /dev/null @@ -1,108 +0,0 @@ -/* libcr_ipc/_linkedlist.h - Common low-level linked lists for use in libcr_ipc - * - * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> - * SPDX-License-Identifier: AGPL-3.0-or-later - */ - -#ifndef _LIBCR_IPC__LINKEDLIST_H_ -#define _LIBCR_IPC__LINKEDLIST_H_ - -#include <libmisc/assert.h> - -/* singly linked list *********************************************************/ - -/* The `root` type should have a ->front pointer and a ->rear pointer - * that point to the front and rear nodes respectively; or NULL if the - * list is empty. - * - * The `node` type should have a ->rear pointer that points to the - * node to the rear of it. - * - * ex: - * - * typedef struct { - * MY_NODE *rear; - * ...node_data... - * } MY_NODE; - * - * typedef struct { - * MY_NODE *front, *rear; - * ...root_data... - * } MY_ROOT; - */ - -#define _cr_ipc_sll_push_to_rear(root, node) do { \ - assert(root); \ - (node)->rear = NULL; \ - if ((root)->rear) \ - (root)->rear->rear = node; \ - else { \ - (root)->front = node; \ - (root)->rear = node; \ - } \ - } while(0) - -#define _cr_ipc_sll_pop_from_front(root) do { \ - assert(root); \ - assert((root)->front); \ - (root)->front = (root)->front->rear; \ - if (!((root)->front)) \ - (root)->rear = NULL; \ - } while(0) - -/* doubly linked list *********************************************************/ - -/* The `root` type should have a ->front pointer and a ->rear pointer - * that point to the front and rear nodes respectively; or NULL if the - * list is empty. - * - * The `node` type should also have a ->front pointer that points to - * the node in front of it, or NULL if it is the front; and a ->rear - * pointer that points to the node to the rear of it, or NULL if it is - * the rear. - * - * ex: - * - * typedef struct { - * MY_NODE *front, *rear; - * ...node_data... - * } MY_NODE; - * - * typedef struct { - * MY_NODE *front, *rear; - * ...root_data... - * } MY_ROOT; - */ - -#define _cr_ipc_dll_push_to_rear(root, node) do { \ - assert(root); \ - assert(node); \ - (node)->front = (root)->rear; \ - (node)->rear = NULL; \ - if ((root)->rear) \ - (root)->rear->rear = node; \ - else \ - (root)->front = node; \ - (root)->rear = node; \ - } while(0) - -#define _cr_ipc_dll_remove(root, node) do { \ - assert(root); \ - assert(node); \ - if ((node)->front) \ - (node)->front->rear = (node)->rear; \ - else \ - (root)->front = (node)->rear; \ - if ((node)->rear) \ - (node)->rear->front = (node)->front; \ - else \ - (root)->rear = (node)->front; \ - } while (0) - -#define _cr_ipc_dll_pop_from_front(root) do { \ - assert(root); \ - assert((root)->front); \ - _cr_ipc_dll_remove(root, (root)->front); \ - } while(0) - -#endif /* _LIBCR_IPC__LINKEDLIST_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/chan.h b/libcr_ipc/include/libcr_ipc/chan.h index 53e68dd..5a87643 100644 --- a/libcr_ipc/include/libcr_ipc/chan.h +++ b/libcr_ipc/include/libcr_ipc/chan.h @@ -1,6 +1,6 @@ /* libcr_ipc/chan.h - Simple channels for libcr * - * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> * SPDX-License-Identifier: AGPL-3.0-or-later */ @@ -9,19 +9,15 @@ #include <stdbool.h> /* for bool */ #include <stddef.h> /* for size_t */ -#include <string.h> /* for memcpy */ -#include <libcr/coroutine.h> /* for cid_t, cr_unpause(), cr_pause_and_yield() */ +#include <libmisc/linkedlist.h> /* for DLIST_DECLARE() */ -#include <libcr_ipc/_linkedlist.h> +/* base channels **************************************************************/ /** - * CR_CHAN_DECLARE(NAME, VAL_T) declares the following type and - * methods: + * CR_CHAN_DECLARE(NAME, VAL_T) declares the following type: * - * type: - * - * /** + * / ** * * A NAME##_t is a fair unbuffered channel that transports * * values of type `VAL_T`. * * @@ -32,124 +28,144 @@ * * something from an interrupt handler. * * / * typedef ... NAME##_t; + */ +#define CR_CHAN_DECLARE(NAME, VAL_T) \ + typedef struct { \ + struct _cr_chan core; \ + VAL_T val_typ[0]; \ + } NAME##_t + +/** + * cr_chan_send(ch, val) sends `val` over `ch`. * - * methods: + * @runs_in coroutine + * @cr_pauses maybe + * @cr_yields always * - * /** - * * NAME##_send(ch, val) sends `val` over `ch`. - * * - * * @runs_in coroutine - * * @cr_pauses maybe - * * @cr_yields always - * * / - * void NAME##_send(NAME##_t *ch, VAL_T val); + * void cr_chan_send(NAME##_t *ch, VAL_T val); + */ +#define cr_chan_send(CH, VAL) do { \ + cr_assert_in_coroutine(); \ + typeof((CH)->val_typ[0]) _val_lvalue = VAL; \ + _cr_chan_xfer(_CR_CHAN_SENDER, &(CH)->core, \ + &_val_lvalue, sizeof(_val_lvalue)); \ +} while(0) + +/** + * cr_chan_recv(ch) reads and returns a value from ch. * - * /** - * * NAME##_recv(ch) reads and returns a value from ch. - * * - * * @runs_in coroutine - * * @cr_pauses maybe - * * @cr_yields always - * * / - * VAL_T NAME##_recv(NAME##_t *ch); + * @runs_in coroutine + * @cr_pauses maybe + * @cr_yields always * - * /** - * * NAME##_can_send(ch) returns whether NAME##_send(ch, val) - * * would run without pausing. - * * - * * @runs_in coroutine - * * @cr_pauses never - * * @cr_yields never - * * / - * bool NAME##_can_send(NAME##_t *ch); + * VAL_T cr_chan_recv(NAME##_T ch); + */ +#define cr_chan_recv(CH) ({ \ + cr_assert_in_coroutine(); \ + typeof((CH)->val_typ[0]) _val_lvalue; \ + _cr_chan_xfer(_CR_CHAN_RECVER, &(CH)->core, \ + &_val_lvalue, sizeof(_val_lvalue)); \ + _val_lvalue; \ +}) + +/** + * cr_chan_can_send(ch) returns whether cr_chan_send(ch, val) would + * run without pausing. * - * /** - * * NAME##_can_recv(ch) returns whether NAME##_recv(ch) would - * * return without pausing. - * * - * * @runs_in coroutine - * * @cr_pauses never - * * @cr_yields never - * * / - * NAME##_can_recv(NAME##_t *ch); + * @runs_in coroutine + * @cr_pauses never + * @cr_yields never + * + * bool cr_chan_can_send(NAME##_t *ch); */ -#define CR_CHAN_DECLARE(NAME, VAL_T) \ - typedef struct { \ - struct _cr_chan core; \ - VAL_T vals[0]; \ - } NAME##_t; \ - \ - static inline void NAME##_send(NAME##_t *ch, VAL_T val) { \ - _cr_chan_xfer(_CR_CHAN_SENDER, &ch->core, &val, sizeof(val)); \ - } \ - \ - static inline VAL_T NAME##_recv(NAME##_t *ch) { \ - VAL_T val; \ - _cr_chan_xfer(_CR_CHAN_RECVER, &ch->core, &val, sizeof(val)); \ - return val; \ - } \ - \ - static inline bool NAME##_can_send(NAME##_t *ch) { \ - return ch->core.waiters.front && \ - ch->core.waiter_typ == _CR_CHAN_RECVER; \ - } \ - \ - static inline bool NAME##_can_recv(NAME##_t *ch) { \ - return ch->core.waiters.front && \ - ch->core.waiter_typ == _CR_CHAN_SENDER; \ - } +#define cr_chan_can_send(CH) ({ \ + cr_assert_in_coroutine(); \ + (bool)((CH)->core.waiters.front && \ + (CH)->core.waiter_typ == _CR_CHAN_RECVER); \ +}) + +/** + * cr_chan_can_recv(ch) returns whether cr_chan_recv(ch) would return + * without pausing. + * + * @runs_in coroutine + * @cr_pauses never + * @cr_yields never + * + * bool cr_chan_can_recv(NAME##_t *ch); + */ +#define cr_chan_can_recv(CH) ({ \ + cr_assert_in_coroutine(); \ + (bool)((CH)->core.waiters.front && \ + (CH)->core.waiter_typ == _CR_CHAN_SENDER); \ +}) + enum _cr_chan_waiter_typ { _CR_CHAN_SENDER, _CR_CHAN_RECVER, }; -struct _cr_chan_waiter { - struct _cr_chan_waiter *front, *rear; - cid_t cid; - void *val_ptr; - void (*dequeue)(void *, size_t); - void *dequeue_arg1; - size_t dequeue_arg2; -}; +DLIST_DECLARE(_cr_chan_waiter_list); struct _cr_chan { - enum _cr_chan_waiter_typ waiter_typ; - struct { - struct _cr_chan_waiter *front, *rear; - } waiters; + enum _cr_chan_waiter_typ waiter_typ; + struct _cr_chan_waiter_list waiters; }; -static void _cr_chan_dequeue(void *_ch, size_t) { - struct _cr_chan *ch = _ch; - _cr_ipc_dll_pop_from_front(&ch->waiters); -} - -static inline void _cr_chan_xfer(enum _cr_chan_waiter_typ self_typ, struct _cr_chan *ch, void *val_ptr, size_t val_size) { - assert(ch); - assert(val_ptr); - - if (ch->waiters.front && ch->waiter_typ != self_typ) { /* non-blocking fast-path */ - /* Copy. */ - if (self_typ == _CR_CHAN_SENDER) - memcpy(ch->waiters.front->val_ptr, val_ptr, val_size); - else - memcpy(val_ptr, ch->waiters.front->val_ptr, val_size); - cr_unpause(ch->waiters.front->cid); - ch->waiters.front->dequeue(ch->waiters.front->dequeue_arg1, - ch->waiters.front->dequeue_arg2); - cr_yield(); - } else { /* blocking slow-path */ - struct _cr_chan_waiter self = { - .cid = cr_getcid(), - .val_ptr = val_ptr, - .dequeue = _cr_chan_dequeue, - .dequeue_arg1 = ch, - }; - _cr_ipc_dll_push_to_rear(&ch->waiters, &self); - ch->waiter_typ = self_typ; - cr_pause_and_yield(); - } -} +void _cr_chan_xfer(enum _cr_chan_waiter_typ self_typ, struct _cr_chan *ch, void *val_ptr, size_t val_size); + +/* cr_select arguments ********************************************************/ + +/** + * Do not populate cr_select_arg yourself; use the + * CR_SELECT_{RECV,SEND,DEFAULT} macros. + */ +struct cr_select_arg { + enum { + _CR_SELECT_OP_RECV, + _CR_SELECT_OP_SEND, + _CR_SELECT_OP_DEFAULT, + } op; + struct _cr_chan *ch; + void *val_ptr; + size_t val_siz; +}; + +#define CR_SELECT_RECV(CH, VALP) ((struct cr_select_arg){ \ + .op = _CR_SELECT_OP_RECV, \ + .ch = &((CH)->core), \ + /* The _valp temporary variable is to get the compiler to check that \ + * the types are compatible. */ \ + .val_ptr = ({ typeof((CH)->val_typ[0]) *_valp = VALP; _valp; }), \ + .val_siz = sizeof((CH)->val_typ[0]), \ +}) + +/* BUG: It's bogus that CR_SELECT_SEND takes VALP instead of VAL, but + * since we need an address, taking VAL would introduce uncomfortable + * questions about where VAL sits on the stack. */ +#define CR_SELECT_SEND(CH, VALP) ((struct cr_select_arg){ \ + .op = _CR_SELECT_OP_SEND, \ + .ch = &((CH)->core), \ + /* The _valp temporary variable is to get the compiler to check that \ + * the types are compatible. */ \ + .val_ptr = ({ typeof((CH)->val_typ[0]) *_valp = VALP; _valp; }), \ + .val_siz = sizeof((CH)->val_typ[0]), \ +}) + +#define CR_SELECT_DEFAULT ((struct cr_select_arg){ \ + .op = _CR_SELECT_OP_DEFAULT, \ +}) + +/* cr_select_v(arg_cnt, arg_vec) **********************************************/ + +size_t cr_select_v(size_t arg_cnt, struct cr_select_arg arg_vec[]); + +/* cr_select_l(arg1, arg2, arg3, ...) ******************************************/ + +#define cr_select_l(...) ({ \ + struct cr_select_arg _cr_select_args[] = { __VA_ARGS__ }; \ + cr_select_v(sizeof(_cr_select_args)/sizeof(_cr_select_args[0])); \ +}) #endif /* _LIBCR_IPC_CHAN_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/mutex.h b/libcr_ipc/include/libcr_ipc/mutex.h index 579f7d5..e5f43c8 100644 --- a/libcr_ipc/include/libcr_ipc/mutex.h +++ b/libcr_ipc/include/libcr_ipc/mutex.h @@ -1,6 +1,6 @@ /* libcr_ipc/mutex.h - Simple mutexes for libcr * - * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> * SPDX-License-Identifier: AGPL-3.0-or-later */ @@ -9,14 +9,10 @@ #include <stdbool.h> /* for bool */ -#include <libcr/coroutine.h> /* for cid_t, cr_unpause(), cr_pause_and_yield() */ +#include <libmisc/linkedlist.h> /* for SLIST_DECLARE() */ +#include <libmisc/private.h> -#include <libcr_ipc/_linkedlist.h> - -struct _cr_mutex_waiter { - struct _cr_mutex_waiter *rear; - cid_t cid; -}; +SLIST_DECLARE(_cr_mutex_waiter_list); /** * A cr_mutex_t is a fair mutex. @@ -27,10 +23,10 @@ struct _cr_mutex_waiter { * first place, then it has no business unlocking one. */ typedef struct { - bool locked; - struct { - struct _cr_mutex_waiter *front, *rear; - } waiters; + BEGIN_PRIVATE(LIBCR_IPC_MUTEX_H); + bool locked; + struct _cr_mutex_waiter_list waiters; + END_PRIVATE(LIBCR_IPC_MUTEX_H); } cr_mutex_t; /** @@ -40,20 +36,7 @@ typedef struct { * @cr_pauses maybe * @cr_yields maybe */ -static inline void cr_mutex_lock(cr_mutex_t *mu) { - assert(mu); - - if (!mu->locked) /* non-blocking fast-path */ - mu->locked = true; - else { /* blocking slow-path */ - struct _cr_mutex_waiter self = { - .cid = cr_getcid(), - }; - _cr_ipc_sll_push_to_rear(&mu->waiters, &self); - cr_pause_and_yield(); - } - assert(mu->locked); -} +void cr_mutex_lock(cr_mutex_t *mu); /** * Unlock the mutex. Unblocks a coroutine that is blocked on @@ -63,15 +46,6 @@ static inline void cr_mutex_lock(cr_mutex_t *mu) { * @cr_pauses never * @cr_yields never */ -static inline void cr_mutex_unlock(cr_mutex_t *mu) { - assert(mu); - - assert(mu->locked); - if (mu->waiters.front) { - cr_unpause(mu->waiters.front->cid); - _cr_ipc_sll_pop_from_front(&mu->waiters); - } else - mu->locked = false; -} +void cr_mutex_unlock(cr_mutex_t *mu); #endif /* _LIBCR_IPC_MUTEX_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/rpc.h b/libcr_ipc/include/libcr_ipc/rpc.h index 382105a..ecf48cf 100644 --- a/libcr_ipc/include/libcr_ipc/rpc.h +++ b/libcr_ipc/include/libcr_ipc/rpc.h @@ -1,6 +1,6 @@ /* libcr_ipc/rpc.h - Simple request/response system for libcr * - * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> * SPDX-License-Identifier: AGPL-3.0-or-later */ @@ -9,17 +9,12 @@ #include <stdbool.h> /* for bool */ -#include <libcr/coroutine.h> /* for cid_t, cr_unpause(), cr_pause_and_yield() */ - -#include <libcr_ipc/_linkedlist.h> +#include <libmisc/linkedlist.h> /* for SLIST_DECLARE() */ /** - * CR_RPC_DECLARE(NAME, REQ_T, RESP_T) declares the following types - * and methods: - * - * type: + * CR_RPC_DECLARE(NAME, REQ_T, RESP_T) declares the following types: * - * /** + * / ** * * A NAME##_t is a fair rpc-channel on which the requester submits a * * value of type `REQ_T` and the responder responds with a value of * * type `RESP_T`. @@ -34,127 +29,117 @@ * * _recv_req() and _send_resp(). * typedef ... NAME##_t; * - * methods: + * / ** + * * A NAME##_req_t is handle that wraps a REQ_T and is used to return + * * the response RESP_T to the correct requester. `REQ_T req` is the + * * only public member. + * typedef struct { REQ_T req; ... } NAME##_req_t; + */ +#define CR_RPC_DECLARE(NAME, REQ_T, RESP_T) \ + typedef struct { \ + REQ_T req; \ + \ + RESP_T *_resp; /* where to write resp to */ \ + cid_t _requester; \ + } NAME##_req_t; \ + \ + typedef struct { \ + struct _cr_rpc core; \ + NAME##_req_t handle_typ[0]; \ + } NAME##_t + +/* Methods for NAME##_t *******************************************************/ + +/** + * cr_rpc_send_req(ch, req) submits the `req` request over `ch` and + * returns the response. * - * /** - * * NAME##_send_req(ch, req) submits the `req` request over `ch` and - * * returns the response. - * * - * * @runs_in coroutine - * * @cr_pauses always - * * @cr_yields always - * * / - * RESP_T NAME##_send_req(NAME##_t *ch, REQ_T req); + * @runs_in coroutine + * @cr_pauses always + * @cr_yields always * - * /** - * * NAME##_recv_req(ch) reads a request from ch, and returns a - * * NAME##_req_t handle wrapping that request. - * * - * * @runs_in coroutine - * * @cr_pauses maybe - * * @cr_yields maybe - * * / - * NAME##_req_t NAME##_recv_req(NAME##_t *ch); + * RESP_T cr_rpc_send_req(NAME##_t *ch, REQ_T req); + */ +#define cr_rpc_send_req(CH, REQ) ({ \ + cr_assert_in_coroutine(); \ + typeof((CH)->handle_typ[0].req) _req_lvalue = REQ; \ + typeof(*(CH)->handle_typ[0]._resp) _resp_lvalue; \ + _cr_rpc_send_req(&(CH)->core, \ + &_req_lvalue, sizeof(_req_lvalue), \ + &_resp_lvalue); \ + _resp_lvalue; \ +}) + +/** + * cr_rpc_recv_req(ch) reads a request from ch, and returns a + * NAME##_req_t handle wrapping that request. * - * /** - * * NAME##_can_recv_req(ch) returns whether NAME##_recv_req(ch) - * * would return without pausing. - * * - * * @runs_in coroutine - * * @cr_pauses never - * * @cr_yields never - * * / - * bool NAME##_can_recv_req(NAME##_t *ch); + * @runs_in coroutine + * @cr_pauses maybe + * @cr_yields maybe + * + * NAME##_req_t cr_rcp_recv_req(NAME##_t *ch); + */ +#define cr_rpc_recv_req(CH) ({ \ + cr_assert_in_coroutine(); \ + typeof((CH)->handle_typ[0]) ret; \ + _cr_rpc_recv_req(&(CH)->core, \ + &ret.req, sizeof(ret.req), \ + (void **)&ret._resp, \ + &ret._requester); \ + ret; \ +}) + +/** + * cr_rpc_can_recv_req(ch) returns whether NAME##_recv_req(ch) + * would return without pausing. * - * type: + * @runs_in coroutine + * @cr_pauses never + * @cr_yields never * - * /** - * * A NAME##_req_t is a handle that wraps a REQ_T, and is a channel - * * that a response may be written to. - * * / - * typedef ... NAME##_req_t; + * bool cr_rpc_can_recv_req(NAME##_t *ch); + */ +#define cr_rpc_can_recv_req(CH) ({ \ + cr_assert_in_coroutine(); \ + (bool)((CH)->core.waiters.front && \ + (CH)->core.waiter_typ == _CR_RPC_REQUESTER); \ +}) + +/* Methods for NAME##_req_t ***************************************************/ + +/** + * cr_rpc_send_resp(req, resp) sends the given response to the given + * request. * - * methods: + * @runs_in coroutine + * @cr_pauses never + * @cr_yields always * - * /** - * * cr_rpc_send_resp(req, resp) sends the given response to the given - * * request. - * * - * * @runs_in coroutine - * * @cr_pauses never - * * @cr_yields always - * * / - * void NAME##_send_resp(NAME##_req_t req, RESP_T resp); + * void cr_rpc_send_resp(NAME##_req_t req, RESP_T resp); */ -#define CR_RPC_DECLARE(NAME, REQ_T, RESP_T) \ - typedef struct { \ - REQ_T req; \ - \ - RESP_T *_resp; \ - cid_t _requester; \ - } NAME##_req_t; \ - \ - struct _##NAME##_waiting_req { \ - struct _##NAME##_waiting_req *rear; \ - REQ_T *req; \ - RESP_T *resp; \ - cid_t cid; \ - }; \ - \ - struct _##NAME##_waiting_resp { \ - struct _##NAME##_waiting_resp *rear; \ - cid_t cid; \ - }; \ - \ - typedef struct { \ - struct { \ - struct _##NAME##_waiting_req *front, *rear; \ - } waiting_reqs; \ - struct { \ - struct _##NAME##_waiting_resp *front, *rear; \ - } waiting_resps; \ - } NAME##_t; \ - \ - static inline RESP_T NAME##_send_req(NAME##_t *ch, REQ_T req) { \ - RESP_T resp; \ - struct _##NAME##_waiting_req self = { \ - .req = &req, \ - .resp = &resp, \ - .cid = cr_getcid(), \ - }; \ - _cr_ipc_sll_push_to_rear(&ch->waiting_reqs, &self); \ - if (ch->waiting_resps.front) \ - cr_unpause(ch->waiting_resps.front->cid); \ - cr_pause_and_yield(); \ - return resp; \ - } \ - \ - static inline NAME##_req_t NAME##_recv_req(NAME##_t *ch) { \ - if (!ch->waiting_reqs.front) { \ - struct _##NAME##_waiting_resp self = { \ - .cid = cr_getcid(), \ - }; \ - _cr_ipc_sll_push_to_rear(&ch->waiting_resps, &self); \ - cr_pause_and_yield(); \ - } \ - assert(ch->waiting_reqs.front); \ - NAME##_req_t ret = { \ - .req = *(ch->waiting_reqs.front->req), \ - ._resp = ch->waiting_reqs.front->resp, \ - ._requester = ch->waiting_reqs.front->cid, \ - }; \ - _cr_ipc_sll_pop_from_front(&ch->waiting_reqs); \ - return ret; \ - } \ - \ - static inline bool NAME##_can_recv_req(NAME##_t *ch) { \ - return ch->waiting_reqs.front != NULL; \ - } \ - \ - static inline void NAME##_send_resp(NAME##_req_t req, RESP_T resp) { \ - *(req._resp) = resp; \ - cr_unpause(req._requester); \ - cr_yield(); \ - } +#define cr_rpc_send_resp(REQ, RESP) { \ + cr_assert_in_coroutine(); \ + *((REQ)._resp) = RESP; \ + cr_unpause(REQ._requester); \ + cr_yield(); \ +} while(0) + +/* Background details *********************************************************/ + +enum _cr_rpc_waiter_typ { + _CR_RPC_REQUESTER, + _CR_RPC_RESPONDER, +}; + +SLIST_DECLARE(_cr_rpc_waiter_list); + +struct _cr_rpc { + enum _cr_rpc_waiter_typ waiter_typ; + struct _cr_rpc_waiter_list waiters; +}; + +void _cr_rpc_send_req(struct _cr_rpc *ch, void *req_ptr, size_t req_size, void *resp_ptr); +void _cr_rpc_recv_req(struct _cr_rpc *ch, void *req_ptr, size_t req_size, void **ret_resp_ptr, cid_t *ret_requester); #endif /* _LIBCR_IPC_RPC_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/rwmutex.h b/libcr_ipc/include/libcr_ipc/rwmutex.h new file mode 100644 index 0000000..8ccae63 --- /dev/null +++ b/libcr_ipc/include/libcr_ipc/rwmutex.h @@ -0,0 +1,78 @@ +/* libcr_ipc/rwmutex.h - Simple read/write mutexes for libcr + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#ifndef _LIBCR_IPC_RWMUTEX_H_ +#define _LIBCR_IPC_RWMUTEX_H_ + +#include <stdbool.h> + +#include <libmisc/linkedlist.h> /* for SLIST_DECLARE() */ +#include <libmisc/private.h> + +SLIST_DECLARE(_cr_rwmutex_waiter_list); + +/** + * A cr_rwmutex_t is a fair read/write mutex. + * + * A waiting writer blocks any new readers; this ensures that the + * writer is able to eventually get the lock. + * + * None of the methods have `_from_intrhandler` variants because (1) + * an interrupt handler can't block, so it shouldn't ever lock a mutex + * because that can block; and (2) if it can't lock a mutex in the + * first place, then it has no business unlocking one. + */ +typedef struct { + BEGIN_PRIVATE(LIBCR_IPC_RWMUTEX_H); + unsigned nreaders; + bool locked; + bool unpausing; + struct _cr_rwmutex_waiter_list waiters; + END_PRIVATE(LIBCR_IPC_RWMUTEX_H); +} cr_rwmutex_t; + +/** + * Lock the mutex for writing. Blocks if it is already locked. + * + * @runs_in coroutine + * @cr_pauses maybe + * @cr_yields maybe + */ +void cr_rwmutex_lock(cr_rwmutex_t *mu); + +/** + * Undo a single cr_rwmutex_lock() call. Unblocks either a single + * coroutine that is blocked on cr_rwmutex_lock() or arbitrarily many + * coroutines that are blocked on cr_rwmutex_rlock(). + * + * @runs_in coroutine + * @cr_pauses never + * @cr_yields never + */ +void cr_rwmutex_unlock(cr_rwmutex_t *mu); + +/** + * Lock the mutex for reading. Blocks if it is already locked for + * writing. + * + * @runs_in coroutine + * @cr_pauses maybe + * @cr_yields maybe + */ +void cr_rwmutex_rlock(cr_rwmutex_t *mu); + +/** + * Undo a single cr_rwmutext_rock() call. If the reader count is + * reduced to zero, unblocks a single coroutine that is blocked on + * cr_rwmutex_lock(). + * + * @runs_in coroutine + * @cr_pauses never + * @cr_yields never + */ +void cr_rwmutex_runlock(cr_rwmutex_t *mu); + +#endif /* _LIBCR_IPC_RWMUTEX_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/select.h b/libcr_ipc/include/libcr_ipc/select.h deleted file mode 100644 index 788bf53..0000000 --- a/libcr_ipc/include/libcr_ipc/select.h +++ /dev/null @@ -1,179 +0,0 @@ -/* libcr_ipc/select.h - Select between channels - * - * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> - * SPDX-License-Identifier: AGPL-3.0-or-later - */ - -#include <alloca.h> /* for alloca() */ -#include <stddef.h> /* for size_t */ - -#include <libmisc/assert.h> -#include <libmisc/rand.h> - -#include <libcr_ipc/chan.h> - -#ifndef _LIBCR_IPC_SELECT_H_ -#define _LIBCR_IPC_SELECT_H_ - -/* arguments ******************************************************************/ - -/** - * Do not populate cr_select_arg yourself; use the - * CR_SELECT_{RECV,SEND,DEFAULT} macros. - */ -struct cr_select_arg { - enum { - _CR_SELECT_OP_RECV, - _CR_SELECT_OP_SEND, - _CR_SELECT_OP_DEFAULT, - } op; - struct _cr_chan *ch; - void *val_ptr; - size_t val_siz; -}; - -#define CR_SELECT_RECV(CH, VALP) ({ \ - assert(CH); \ - assert(VALP); \ - /* The _valp indirection is to get the \ - * compiler to check that the types are \ - * compatible. */ \ - typeof((CH)->vals[0]) *_valp = VALP; \ - ((struct cr_select_arg){ \ - .op = _CR_SELECT_OP_RECV, \ - .ch = &((CH)->core), \ - .val_ptr = _valp, \ - .val_siz = sizeof((CH)->vals[0]), \ - }); \ - }) -#define CR_SELECT_SEND(CH, VAL) ({ \ - assert(CH); \ - typeof((CH)->vals[0]) val_lvalue = VAL; \ - ((struct cr_select_arg){ \ - .op = _CR_SELECT_OP_SEND, \ - .ch = &((CH)->core), \ - .val_ptr = &val_lvalue;, \ - .val_siz = sizeof((CH)->vals[0]), \ - }); \ - }) -#define CR_SELECT_DEFAULT \ - ((struct cr_select_arg){ \ - .op = _CR_SELECT_OP_DEFAULT, \ - }) - -/* cr_select_v(arg_cnt, arg_vec) **********************************************/ - -enum _cr_select_class { - _CR_SELECT_CLASS_DEFAULT, - _CR_SELECT_CLASS_BLOCKING, - _CR_SELECT_CLASS_NONBLOCK, -}; - -static inline enum _cr_select_class _cr_select_getclass(struct cr_select_arg arg) { - switch (arg.op) { - case _CR_SELECT_OP_RECV: - if (arg.ch->waiters.front && arg.ch->waiter_typ == _CR_CHAN_SENDER) - return _CR_SELECT_CLASS_NONBLOCK; - else - return _CR_SELECT_CLASS_BLOCKING; - case _CR_SELECT_OP_SEND: - if (arg.ch->waiters.front && arg.ch->waiter_typ == _CR_CHAN_RECVER) - return _CR_SELECT_CLASS_NONBLOCK; - else - return _CR_SELECT_CLASS_BLOCKING; - case _CR_SELECT_OP_DEFAULT: - return _CR_SELECT_CLASS_DEFAULT; - default: - assert_notreached("invalid arg.op"); - } -} - -struct _cr_select_waiters { - size_t cnt; - struct cr_select_arg *args; - struct _cr_chan_waiter *nodes; -}; - -static void _cr_select_dequeue(void *_waiters, size_t idx) { - struct _cr_select_waiters *waiters = waiters; - for (size_t i = 0; i < waiters->cnt; i++) - _cr_ipc_dll_remove(&(waiters->args[i].ch->waiters), - &(waiters->nodes[i])); - waiters->cnt = idx; -} - -static size_t cr_select_v(size_t arg_cnt, struct cr_select_arg arg_vec[]) { - size_t cnt_blocking = 0; - size_t cnt_nonblock = 0; - size_t cnt_default = 0; - - assert(arg_cnt); - assert(arg_vec); - - for (size_t i = 0; i < arg_cnt; i++) { - switch (_cr_select_getclass(arg_vec[i])) { - case _CR_SELECT_CLASS_BLOCKING: - cnt_blocking++; - break; - case _CR_SELECT_CLASS_NONBLOCK: - cnt_nonblock++; - break; - case _CR_SELECT_CLASS_DEFAULT: - cnt_default++; - break; - } - } - - if (cnt_nonblock) { - size_t choice = rand_uint63n(cnt_nonblock); - for (size_t i = 0, seen = 0; i < arg_cnt; i++) { - if (_cr_select_getclass(arg_vec[i]) == _CR_SELECT_CLASS_NONBLOCK) { - if (seen == choice) { - _cr_chan_xfer(arg_vec[i].op == _CR_SELECT_OP_RECV - ? _CR_CHAN_RECVER - : _CR_CHAN_SENDER, - arg_vec[i].ch, - arg_vec[i].val_ptr, - arg_vec[i].val_siz); - return i; - } - seen++; - } - } - assert_notreached("should have returned from inside for() loop"); - } - - if (cnt_default) { - for (size_t i = 0; i < arg_cnt; i++) - if (_cr_select_getclass(arg_vec[i]) == _CR_SELECT_CLASS_DEFAULT) - return i; - assert_notreached("should have returned from inside for() loop"); - } - - struct _cr_select_waiters waiters = { - .cnt = arg_cnt, - .args = arg_vec, - .nodes = alloca(sizeof(struct _cr_chan_waiter) * arg_cnt), - }; - for (size_t i = 0; i < arg_cnt; i++) { - waiters.nodes[i] = (struct _cr_chan_waiter){ - .cid = cr_getcid(), - .val_ptr = arg_vec[i].val_ptr, - .dequeue = _cr_select_dequeue, - .dequeue_arg1 = &waiters, - .dequeue_arg2 = i, - }; - _cr_ipc_dll_push_to_rear(&arg_vec[i].ch->waiters, &waiters.nodes[i]); - } - cr_pause_and_yield(); - return waiters.cnt; -} - -/* cr_select_l(arg1, arg2, arg3, ...) ******************************************/ - -#define cr_select_l(...) ({ \ - struct cr_select_arg _cr_select_args[] = { __VA_ARGS__ }; \ - cr_select_v(sizeof(_cr_select_args)/sizeof(_cr_select_args[0])); \ -}) - -#endif /* _LIBCR_IPC_SELECT_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/sema.h b/libcr_ipc/include/libcr_ipc/sema.h index 0895a22..8b5ac5b 100644 --- a/libcr_ipc/include/libcr_ipc/sema.h +++ b/libcr_ipc/include/libcr_ipc/sema.h @@ -1,20 +1,18 @@ /* libcr_ipc/sema.h - Simple semaphores for libcr * - * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> * SPDX-License-Identifier: AGPL-3.0-or-later */ #ifndef _LIBCR_IPC_SEMA_H_ #define _LIBCR_IPC_SEMA_H_ -#include <libcr/coroutine.h> /* for cid_t, cr_unpause(), cr_pause_and_yield() */ +#include <stdbool.h> -#include <libcr_ipc/_linkedlist.h> +#include <libmisc/linkedlist.h> /* for SLIST_DECLARE() */ +#include <libmisc/private.h> -struct _cr_sema_waiter { - struct _cr_sema_waiter *rear; - cid_t cid; -}; +SLIST_DECLARE(_cr_sema_waiter_list); /** * A cr_sema_t is a fair unbounded[1] counting semaphore. @@ -22,10 +20,11 @@ struct _cr_sema_waiter { * [1]: Well, UINT_MAX */ typedef struct { - unsigned int cnt; - struct { - struct _cr_sema_waiter *front, *rear; - } waiters; + BEGIN_PRIVATE(LIBCR_IPC_SEMA_H); + unsigned int cnt; + bool unpausing; + struct _cr_sema_waiter_list waiters; + END_PRIVATE(LIBCR_IPC_SEMA_H); } cr_sema_t; /** @@ -35,34 +34,14 @@ typedef struct { * @cr_pauses never * @cr_yields never */ -static inline void cr_sema_signal(cr_sema_t *sema) { - assert(sema); - - bool saved = cr_save_and_disable_interrupts(); - sema->cnt++; - if (sema->waiters.front) { - sema->cnt--; - cr_unpause(sema->waiters.front->cid); - _cr_ipc_sll_pop_from_front(&sema->waiters); - } - cr_restore_interrupts(saved); -} +void cr_sema_signal(cr_sema_t *sema); /** * Like cr_sema_signal(), but for use from an interrupt handler. * * @runs_in intrhandler */ -static inline void cr_sema_signal_from_intrhandler(cr_sema_t *sema) { - assert(sema); - - sema->cnt++; - if (sema->waiters.front) { - sema->cnt--; - cr_unpause_from_intrhandler(sema->waiters.front->cid); - _cr_ipc_sll_pop_from_front(&sema->waiters); - } -} +void cr_sema_signal_from_intrhandler(cr_sema_t *sema); /** * Wait until the semaphore is >0, then decrement it. @@ -71,20 +50,6 @@ static inline void cr_sema_signal_from_intrhandler(cr_sema_t *sema) { * @cr_pauses maybe * @cr_yields maybe */ -static inline void cr_sema_wait(cr_sema_t *sema) { - assert(sema); - - bool saved = cr_save_and_disable_interrupts(); - if (sema->cnt) { /* non-blocking */ - sema->cnt--; - } else { /* blocking */ - struct _cr_sema_waiter self = { - .cid = cr_getcid(), - }; - _cr_ipc_sll_push_to_rear(&sema->waiters, &self); - cr_pause_and_yield(); - } - cr_restore_interrupts(saved); -} +void cr_sema_wait(cr_sema_t *sema); #endif /* _LIBCR_IPC_SEMA_H_ */ diff --git a/libcr_ipc/mutex.c b/libcr_ipc/mutex.c new file mode 100644 index 0000000..1b4e626 --- /dev/null +++ b/libcr_ipc/mutex.c @@ -0,0 +1,44 @@ +/* libcr_ipc/mutex.c - Simple mutexes for libcr + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <libcr/coroutine.h> /* for cid_t, cr_* */ +#include <libmisc/assert.h> + +#define IMPLEMENTATION_FOR_LIBCR_IPC_MUTEX_H YES +#include <libcr_ipc/mutex.h> + +struct cr_mutex_waiter { + cid_t cid; +}; +SLIST_DECLARE_NODE(_cr_mutex_waiter_list, struct cr_mutex_waiter); + +void cr_mutex_lock(cr_mutex_t *mu) { + assert(mu); + cr_assert_in_coroutine(); + + if (!mu->locked) /* non-blocking fast-path */ + mu->locked = true; + else { /* blocking slow-path */ + struct _cr_mutex_waiter_list_node self = { .val = { + .cid = cr_getcid(), + }}; + slist_push_to_rear(&mu->waiters, &self); + cr_pause_and_yield(); + } + assert(mu->locked); +} + +void cr_mutex_unlock(cr_mutex_t *mu) { + assert(mu); + cr_assert_in_coroutine(); + + assert(mu->locked); + if (mu->waiters.front) { + cr_unpause(mu->waiters.front->val.cid); + slist_pop_from_front(&mu->waiters); + } else + mu->locked = false; +} diff --git a/libcr_ipc/rpc.c b/libcr_ipc/rpc.c new file mode 100644 index 0000000..fcf51ba --- /dev/null +++ b/libcr_ipc/rpc.c @@ -0,0 +1,84 @@ +/* libcr_ipc/rpc.c - Simple request/response system for libcr + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <string.h> /* for memcpy() */ + +#include <libcr/coroutine.h> /* for cid_t, cr_* */ +#include <libmisc/assert.h> + +#include <libcr_ipc/rpc.h> + +struct cr_rpc_requester { + cid_t cid; + void *req_ptr; /* where to read req from */ + void *resp_ptr; /* where to write resp to */ +}; +struct cr_rpc_responder { + /* before enqueued | after dequeued */ + /* -------------------+-------------------- */ + cid_t cid; /* responder cid | requester cid */ + void *ptr; /* where to write req | where to write resp */ +}; +union cr_rpc_waiter { + struct cr_rpc_requester requester; + struct cr_rpc_responder responder; +}; +SLIST_DECLARE_NODE(_cr_rpc_waiter_list, union cr_rpc_waiter); + +void _cr_rpc_send_req(struct _cr_rpc *ch, void *req_ptr, size_t req_size, void *resp_ptr) { + assert(ch); + assert(req_ptr); + assert(resp_ptr); + + if (ch->waiters.front && ch->waiter_typ != _CR_RPC_REQUESTER) { /* fast-path (still blocks) */ + struct cr_rpc_responder *responder = &ch->waiters.front->val.responder; + slist_pop_from_front(&ch->waiters); + /* Copy the req to the responder's stack. */ + memcpy(responder->ptr, req_ptr, req_size); + /* Notify the responder that we have done so. */ + cr_unpause(responder->cid); + responder->cid = cr_getcid(); + responder->ptr = resp_ptr; + /* Wait for the responder to set `*resp_ptr`. */ + cr_pause_and_yield(); + } else { /* blocking slow-path */ + struct _cr_rpc_waiter_list_node self = { .val = { .requester = { + .cid = cr_getcid(), + .req_ptr = req_ptr, + .resp_ptr = resp_ptr, + }}}; + slist_push_to_rear(&ch->waiters, &self); + /* Wait for a responder to both copy our req and sed + * `*resp_ptr`. */ + cr_pause_and_yield(); + } +} + +void _cr_rpc_recv_req(struct _cr_rpc *ch, void *req_ptr, size_t req_size, void **ret_resp_ptr, cid_t *ret_requester) { + assert(ch); + assert(req_ptr); + assert(ret_resp_ptr); + assert(ret_requester); + + if (ch->waiters.front && ch->waiter_typ != _CR_RPC_RESPONDER) { /* non-blocking fast-path */ + struct cr_rpc_requester *requester = &ch->waiters.front->val.requester; + slist_pop_from_front(&ch->waiters); + + memcpy(req_ptr, requester->req_ptr, req_size); + *ret_requester = requester->cid; + *ret_resp_ptr = requester->resp_ptr; + } else { /* blocking slow-path */ + struct _cr_rpc_waiter_list_node self = { .val = { .responder = { + .cid = cr_getcid(), + .ptr = req_ptr, + }}}; + slist_push_to_rear(&ch->waiters, &self); + ch->waiter_typ = _CR_RPC_RESPONDER; + cr_pause_and_yield(); + *ret_requester = self.val.responder.cid; + *ret_resp_ptr = self.val.responder.ptr; + } +} diff --git a/libcr_ipc/rwmutex.c b/libcr_ipc/rwmutex.c new file mode 100644 index 0000000..191b7fe --- /dev/null +++ b/libcr_ipc/rwmutex.c @@ -0,0 +1,98 @@ +/* libcr_ipc/rwmutex.c - Simple read/write mutexes for libcr + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <libcr/coroutine.h> /* for cid_t, cr_* */ +#include <libmisc/assert.h> + +#define IMPLEMENTATION_FOR_LIBCR_IPC_RWMUTEX_H YES +#include <libcr_ipc/rwmutex.h> + +struct cr_rwmutex_waiter { + bool is_reader; + cid_t cid; +}; +SLIST_DECLARE_NODE(_cr_rwmutex_waiter_list, struct cr_rwmutex_waiter); + +void cr_rwmutex_lock(cr_rwmutex_t *mu) { + assert(mu); + cr_assert_in_coroutine(); + + struct _cr_rwmutex_waiter_list_node self = { .val = { + .is_reader = false, + .cid = cr_getcid(), + }}; + slist_push_to_rear(&mu->waiters, &self); + if (mu->waiters.front != &self || mu->locked) + cr_pause_and_yield(); + assert(mu->waiters.front == &self); + + /* We now hold the lock (and are mu->waiters.front). */ + slist_pop_from_front(&mu->waiters); + assert(mu->nreaders == 0); + mu->locked = true; + mu->unpausing = false; +} + +void cr_rwmutex_rlock(cr_rwmutex_t *mu) { + assert(mu); + cr_assert_in_coroutine(); + + struct _cr_rwmutex_waiter_list_node self = { .val = { + .is_reader = true, + .cid = cr_getcid(), + }}; + slist_push_to_rear(&mu->waiters, &self); + if (mu->waiters.front != &self || (mu->locked && mu->nreaders == 0)) + cr_pause_and_yield(); + assert(mu->waiters.front == &self); + + /* We now hold the lock (and are mu->waiters.front). */ + slist_pop_from_front(&mu->waiters); + mu->nreaders++; + mu->locked = true; + struct _cr_rwmutex_waiter_list_node *waiter = mu->waiters.front; + if (waiter && waiter->val.is_reader) { + assert(mu->unpausing); + cr_unpause(waiter->val.cid); + } else { + mu->unpausing = false; + } +} + +void cr_rwmutex_unlock(cr_rwmutex_t *mu) { + assert(mu); + cr_assert_in_coroutine(); + + assert(mu->locked); + assert(mu->nreaders == 0); + assert(!mu->unpausing); + if (mu->waiters.front) { + struct _cr_rwmutex_waiter_list_node *waiter = mu->waiters.front; + mu->unpausing = true; + cr_unpause(waiter->val.cid); + } else { + mu->locked = false; + } +} + +void cr_rwmutex_runlock(cr_rwmutex_t *mu) { + assert(mu); + cr_assert_in_coroutine(); + + assert(mu->locked); + assert(mu->nreaders > 0); + mu->nreaders--; + if (mu->nreaders == 0 && !mu->unpausing) { + if (mu->waiters.front) { + struct _cr_rwmutex_waiter_list_node *waiter = mu->waiters.front; + assert(!waiter->val.is_reader); + mu->unpausing = true; + cr_unpause(waiter->val.cid); + } else { + mu->locked = false; + } + } +} diff --git a/libcr_ipc/sema.c b/libcr_ipc/sema.c new file mode 100644 index 0000000..f2ac9b6 --- /dev/null +++ b/libcr_ipc/sema.c @@ -0,0 +1,62 @@ +/* libcr_ipc/sema.c - Simple semaphores for libcr + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <libcr/coroutine.h> /* for cid_t, cr_* */ +#include <libmisc/assert.h> + +#define IMPLEMENTATION_FOR_LIBCR_IPC_SEMA_H YES +#include <libcr_ipc/sema.h> + +struct cr_sema_waiter { + cid_t cid; +}; +SLIST_DECLARE_NODE(_cr_sema_waiter_list, struct cr_sema_waiter); + +void cr_sema_signal(cr_sema_t *sema) { + assert(sema); + cr_assert_in_coroutine(); + + bool saved = cr_save_and_disable_interrupts(); + sema->cnt++; + if (sema->waiters.front && !sema->unpausing) { + cr_unpause(sema->waiters.front->val.cid); + sema->unpausing = true; + } + cr_restore_interrupts(saved); +} + +void cr_sema_signal_from_intrhandler(cr_sema_t *sema) { + assert(sema); + cr_assert_in_intrhandler(); + + sema->cnt++; + if (sema->waiters.front && !sema->unpausing) { + cr_unpause_from_intrhandler(sema->waiters.front->val.cid); + sema->unpausing = true; + } +} + +void cr_sema_wait(cr_sema_t *sema) { + assert(sema); + cr_assert_in_coroutine(); + + bool saved = cr_save_and_disable_interrupts(); + + struct _cr_sema_waiter_list_node self = { .val = { + .cid = cr_getcid(), + }}; + slist_push_to_rear(&sema->waiters, &self); + if (sema->waiters.front != &self || !sema->cnt) + cr_pause_and_yield(); + assert(sema->waiters.front == &self && sema->cnt); + slist_pop_from_front(&sema->waiters); + sema->cnt--; + if (sema->cnt && sema->waiters.front) + cr_unpause(sema->waiters.front->val.cid); + else + sema->unpausing = false; + cr_restore_interrupts(saved); +} diff --git a/libcr_ipc/tests/config.h b/libcr_ipc/tests/config.h new file mode 100644 index 0000000..a648589 --- /dev/null +++ b/libcr_ipc/tests/config.h @@ -0,0 +1,20 @@ +/* config.h - Compile-time configuration for the libcr_ipc tests + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#ifndef _CONFIG_H_ +#define _CONFIG_H_ + +#define CONFIG_COROUTINE_STACK_SIZE_DEFAULT (8*1024) +#define CONFIG_COROUTINE_NAME_LEN 16 +#define CONFIG_COROUTINE_NUM 16 + +#define CONFIG_COROUTINE_MEASURE_STACK 1 +#define CONFIG_COROUTINE_PROTECT_STACK 1 +#define CONFIG_COROUTINE_DEBUG 1 +#define CONFIG_COROUTINE_VALGRIND 1 +#define CONFIG_COROUTINE_GDB 1 + +#endif /* _CONFIG_H_ */ diff --git a/libcr_ipc/tests/test.h b/libcr_ipc/tests/test.h new file mode 100644 index 0000000..4928d8d --- /dev/null +++ b/libcr_ipc/tests/test.h @@ -0,0 +1,21 @@ +/* libcr_ipc/tests/test.h - Common test utilities + * + * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#ifndef _LIBCR_IPC_TESTS_TEST_H_ +#define _LIBCR_IPC_TESTS_TEST_H_ + +#include <stdio.h> +#include <stdlib.h> /* for exit() */ + +#define test_assert(expr) do { \ + if (!(expr)) { \ + printf("test failure: %s:%d:%s: %s\n", \ + __FILE__, __LINE__, __func__, #expr); \ + exit(1); \ + } \ + } while (0) + +#endif /* _LIBCR_IPC_TESTS_TEST_H_ */ diff --git a/libcr_ipc/tests/test_chan.c b/libcr_ipc/tests/test_chan.c new file mode 100644 index 0000000..e5d9dc8 --- /dev/null +++ b/libcr_ipc/tests/test_chan.c @@ -0,0 +1,49 @@ +/* libcr_ipc/tests/test_chan.c - Tests for <libcr_ipc/chan.h> + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <libcr/coroutine.h> +#include <libcr_ipc/chan.h> + +#include "test.h" + +CR_CHAN_DECLARE(intchan, int); + +COROUTINE cr_producer(void *_ch) { + intchan_t *ch = _ch; + cr_begin(); + + cr_chan_send(ch, 1); + + while (!cr_chan_can_send(ch)) + cr_yield(); + + cr_chan_send(ch, 2); + + + cr_end(); +} + +COROUTINE cr_consumer(void *_ch) { + int x; + intchan_t *ch = _ch; + cr_begin(); + + x = cr_chan_recv(ch); + test_assert(x == 1); + + x = cr_chan_recv(ch); + test_assert(x == 2); + + cr_end(); +} + +int main() { + intchan_t ch = {0}; + coroutine_add("producer", cr_producer, &ch); + coroutine_add("consumer", cr_consumer, &ch); + coroutine_main(); + return 0; +} diff --git a/libcr_ipc/tests/test_mutex.c b/libcr_ipc/tests/test_mutex.c new file mode 100644 index 0000000..43714c9 --- /dev/null +++ b/libcr_ipc/tests/test_mutex.c @@ -0,0 +1,37 @@ +/* libcr_ipc/tests/test_mutex.c - Tests for <libcr_ipc/mutex.h> + * + * Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <libcr/coroutine.h> +#include <libcr_ipc/mutex.h> + +#include "test.h" + +int counter = 0; + +COROUTINE cr_worker(void *_mu) { + cr_mutex_t *mu = _mu; + cr_begin(); + + for (int i = 0; i < 100; i++) { + cr_mutex_lock(mu); + int a = counter; + cr_yield(); + counter = a + 1; + cr_mutex_unlock(mu); + cr_yield(); + } + + cr_end(); +} + +int main() { + cr_mutex_t mu = {}; + coroutine_add("a", cr_worker, &mu); + coroutine_add("b", cr_worker, &mu); + coroutine_main(); + test_assert(counter == 200); + return 0; +} diff --git a/libcr_ipc/tests/test_rpc.c b/libcr_ipc/tests/test_rpc.c new file mode 100644 index 0000000..910b738 --- /dev/null +++ b/libcr_ipc/tests/test_rpc.c @@ -0,0 +1,59 @@ +/* libcr_ipc/tests/test_rpc.c - Tests for <libcr_ipc/rpc.h> + * + * Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <libcr/coroutine.h> +#include <libcr_ipc/rpc.h> + +#include "test.h" + +CR_RPC_DECLARE(intrpc, int, int); + +/* Test that the RPC is fair, have worker1 start waiting first, and + * ensure that it gets the first request. */ + +COROUTINE cr_caller(void *_ch) { + intrpc_t *ch = _ch; + cr_begin(); + + int resp = cr_rpc_send_req(ch, 1); + test_assert(resp == 2); + + resp = cr_rpc_send_req(ch, 3); + test_assert(resp == 4); + + cr_exit(); +} + +COROUTINE cr_worker1(void *_ch) { + intrpc_t *ch = _ch; + cr_begin(); + + intrpc_req_t req = cr_rpc_recv_req(ch); + test_assert(req.req == 1); + cr_rpc_send_resp(req, 2); + + cr_exit(); +} + +COROUTINE cr_worker2(void *_ch) { + intrpc_t *ch = _ch; + cr_begin(); + + intrpc_req_t req = cr_rpc_recv_req(ch); + test_assert(req.req == 3); + cr_rpc_send_resp(req, 4); + + cr_exit(); +} + +int main() { + intrpc_t ch = {0}; + coroutine_add("worker1", cr_worker1, &ch); + coroutine_add("caller", cr_caller, &ch); + coroutine_add("worker2", cr_worker2, &ch); + coroutine_main(); + return 0; +} diff --git a/libcr_ipc/tests/test_rwmutex.c b/libcr_ipc/tests/test_rwmutex.c new file mode 100644 index 0000000..77e8c7c --- /dev/null +++ b/libcr_ipc/tests/test_rwmutex.c @@ -0,0 +1,88 @@ +/* libcr_ipc/tests/test_rwmutex.c - Tests for <libcr_ipc/rwmutex.h> + * + * Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <string.h> + +#include <libcr/coroutine.h> +#include <libcr_ipc/rwmutex.h> + +#include "test.h" + +cr_rwmutex_t mu = {}; +char out[10] = {0}; +size_t len = 0; + +COROUTINE cr1_reader(void *_mu) { + cr_rwmutex_t *mu = _mu; + cr_begin(); + + cr_rwmutex_rlock(mu); + out[len++] = 'r'; + cr_yield(); + cr_rwmutex_runlock(mu); + + cr_end(); +} + +COROUTINE cr1_writer(void *_mu) { + cr_rwmutex_t *mu = _mu; + cr_begin(); + + cr_rwmutex_lock(mu); + out[len++] = 'w'; + cr_yield(); + cr_rwmutex_unlock(mu); + + cr_end(); +} + +COROUTINE cr2_waiter(void *_ch) { + char ch = *(char *)_ch; + cr_begin(); + + cr_rwmutex_rlock(&mu); + out[len++] = ch; + cr_rwmutex_runlock(&mu); + + cr_end(); +} + +COROUTINE cr2_init(void *) { + cr_begin(); + + char ch; + cr_rwmutex_lock(&mu); + ch = 'a'; coroutine_add("wait-a", cr2_waiter, &ch); + ch = 'b'; coroutine_add("wait-b", cr2_waiter, &ch); + cr_yield(); + ch = 'c'; coroutine_add("wait-c", cr2_waiter, &ch); + cr_rwmutex_unlock(&mu); + + cr_end(); +} + +int main() { + printf("== test 1 =========================================\n"); + coroutine_add("r1", cr1_reader, &mu); + coroutine_add("r2", cr1_reader, &mu); + coroutine_add("w", cr1_writer, &mu); + coroutine_add("r3", cr1_reader, &mu); + coroutine_add("r4", cr1_reader, &mu); + coroutine_main(); + test_assert(len == 5); + test_assert(strcmp(out, "rrwrr") == 0); + + printf("== test 2 =========================================\n"); + mu = (cr_rwmutex_t){}; + len = 0; + memset(out, 0, sizeof(out)); + coroutine_add("init", cr2_init, NULL); + coroutine_main(); + test_assert(len == 3); + test_assert(strcmp(out, "abc") == 0); + + return 0; +} diff --git a/libcr_ipc/tests/test_select.c b/libcr_ipc/tests/test_select.c new file mode 100644 index 0000000..f0a71a3 --- /dev/null +++ b/libcr_ipc/tests/test_select.c @@ -0,0 +1,90 @@ +/* libcr_ipc/tests/test_select.c - Tests for <libcr_ipc/select.h> + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <libcr/coroutine.h> +#include <libcr_ipc/chan.h> + +#include "test.h" + +CR_CHAN_DECLARE(intchan, int); + +intchan_t ch[10] = {0}; +intchan_t fch = {0}; + +COROUTINE cr_consumer(void *) { + cr_begin(); + + struct cr_select_arg args[11]; + + bool chdone[10] = {0}; + int arg2ch[10]; + for (;;) { + int ret_ch; + int i_arg = 0; + for (int i_ch = 0; i_ch < 10; i_ch++) { + if (!chdone[i_ch]) { + args[i_arg] = CR_SELECT_RECV(&ch[i_ch], &ret_ch); + arg2ch[i_arg] = i_ch; + i_arg++; + } + } + if (!i_arg) + break; + args[i_arg] = CR_SELECT_DEFAULT; /* check that default doesn't trigger */ + test_assert(i_arg <= 10); + int ret_arg = cr_select_v(i_arg+1, args); + test_assert(ret_arg < i_arg); + test_assert(arg2ch[ret_arg] == ret_ch); + chdone[ret_ch] = true; + } + int ret_ch, ret_arg; + args[0] = CR_SELECT_RECV(&ch[0], &ret_ch); + args[1] = CR_SELECT_DEFAULT; + ret_arg = cr_select_v(2, args); + test_assert(ret_arg == 1); + + int send = 567; + args[0] = CR_SELECT_SEND(&fch, &send); + args[1] = CR_SELECT_DEFAULT; + ret_arg = cr_select_v(2, args); + test_assert(ret_arg == 0); + + send = 890; + args[0] = CR_SELECT_SEND(&fch, &send); + args[1] = CR_SELECT_DEFAULT; + ret_arg = cr_select_v(2, args); + test_assert(ret_arg == 1); + + cr_end(); +} + +COROUTINE cr_producer(void *_n) { + int n = *(int *)_n; + cr_begin(); + + cr_chan_send(&ch[n], n); + + cr_end(); +} + +COROUTINE cr_final(void *) { + cr_begin(); + + int ret = cr_chan_recv(&fch); + printf("ret=%d\n", ret); + test_assert(ret == 567); + + cr_end(); +} + +int main() { + for (int i = 0; i < 10; i++) + coroutine_add("producer", cr_producer, &i); + coroutine_add("consumer", cr_consumer, NULL); + coroutine_add("final", cr_final, NULL); + coroutine_main(); + return 0; +} diff --git a/libcr_ipc/tests/test_sema.c b/libcr_ipc/tests/test_sema.c new file mode 100644 index 0000000..e5b22a5 --- /dev/null +++ b/libcr_ipc/tests/test_sema.c @@ -0,0 +1,76 @@ +/* libcr_ipc/tests/test_sema.c - Tests for <libcr_ipc/sema.h> + * + * Copyright (C) 2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <libcr/coroutine.h> + +#define IMPLEMENTATION_FOR_LIBCR_IPC_SEMA_H YES /* so we can access .cnt */ +#include <libcr_ipc/sema.h> + +#include "test.h" + +int counter = 0; + +COROUTINE cr_first(void *_sema) { + cr_sema_t *sema = _sema; + cr_begin(); + + cr_sema_wait(sema); + counter++; + cr_sema_signal(sema); + + cr_exit(); +} + +COROUTINE cr_second(void *_sema) { + cr_sema_t *sema = _sema; + cr_begin(); + + cr_sema_signal(sema); /* should be claimed by cr_first, which has been waiting */ + cr_sema_wait(sema); /* should block, because cr_first claimed it */ + test_assert(counter == 1); + + cr_exit(); +} + +COROUTINE cr_producer(void *_sema) { + cr_sema_t *sema = _sema; + cr_begin(); + + for (int i = 0; i < 10; i++) + cr_sema_signal(sema); + + cr_end(); +} + +COROUTINE cr_consumer(void *_sema) { + cr_sema_t *sema = _sema; + cr_begin(); + + for (int i = 0; i < 5; i++) + cr_sema_wait(sema); + + cr_end(); +} + +int main() { + cr_sema_t sema = {}; + + printf("== test 1 =========================================\n"); + coroutine_add("first", cr_first, &sema); + coroutine_add("second", cr_second, &sema); + coroutine_main(); + test_assert(sema.cnt == 0); + + printf("== test 2 =========================================\n"); + coroutine_add("consumer", cr_consumer, &sema); + coroutine_add("producer", cr_producer, &sema); + coroutine_main(); + coroutine_add("consumer", cr_consumer, &sema); + coroutine_main(); + test_assert(sema.cnt == 0); + + return 0; +} |