diff options
Diffstat (limited to 'libcr_ipc')
25 files changed, 986 insertions, 592 deletions
diff --git a/libcr_ipc/CMakeLists.txt b/libcr_ipc/CMakeLists.txt index 4590bdd..bd72f54 100644 --- a/libcr_ipc/CMakeLists.txt +++ b/libcr_ipc/CMakeLists.txt @@ -4,26 +4,28 @@ # 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 + _linkedlist.c chan.c - select.c + mutex.c + rpc.c + rwmutex.c + sema.c ) target_link_libraries(libcr_ipc INTERFACE libcr + libmisc ) set(ipc_tests chan - #select - #mutex - #owned_mutex + mutex rpc + rwmutex + select sema ) -if (ENABLE_TESTS) - foreach(test IN LISTS ipc_tests) - add_lib_test(libcr_ipc "test_${test}") - target_include_directories("test_${test}" PUBLIC ${CMAKE_CURRENT_SOURCE_DIR}/tests) - endforeach() -endif() +foreach(test IN LISTS ipc_tests) + add_lib_test(libcr_ipc "test_${test}") +endforeach() diff --git a/libcr_ipc/_linkedlist.c b/libcr_ipc/_linkedlist.c new file mode 100644 index 0000000..b27dba8 --- /dev/null +++ b/libcr_ipc/_linkedlist.c @@ -0,0 +1,62 @@ +/* libcr_ipc/_linkedlist.c - Common low-level linked lists for use in libcr_ipc + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#include <stddef.h> /* for NULL */ + +#include "_linkedlist.h" + +/* singly linked list *********************************************************/ + +void cr_ipc_sll_push_to_rear(_cr_ipc_sll_root *root, cr_ipc_sll_node *node) { + assert(root); + node->rear = NULL; + if (root->rear) + root->rear->rear = node; + else + root->front = node; + root->rear = node; +} + +void cr_ipc_sll_pop_from_front(_cr_ipc_sll_root *root) { + assert(root); + assert(root->front); + root->front = root->front->rear; + if (!root->front) + root->rear = NULL; +} + +/* doubly linked list *********************************************************/ + +void cr_ipc_dll_push_to_rear(_cr_ipc_dll_root *root, cr_ipc_dll_node *node) { + 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; +} + +void cr_ipc_dll_remove(_cr_ipc_dll_root *root, cr_ipc_dll_node *node) { + 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; +} + +void cr_ipc_dll_pop_from_front(_cr_ipc_dll_root *root) { + assert(root); + assert(root->front); + cr_ipc_dll_remove(root, root->front); +} diff --git a/libcr_ipc/_linkedlist.h b/libcr_ipc/_linkedlist.h new file mode 100644 index 0000000..ab6d89e --- /dev/null +++ b/libcr_ipc/_linkedlist.h @@ -0,0 +1,51 @@ +/* libcr_ipc/_linkedlist.h - Common low-level linked lists for use in libcr_ipc + * + * Copyright (C) 2024-2025 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> + +#include <libcr_ipc/_linkedlist_pub.h> + +/* singly linked list *********************************************************/ + +typedef struct _cr_ipc_sll_node { + struct _cr_ipc_sll_node *rear; +} cr_ipc_sll_node; + +#define cr_ipc_sll_node_cast(node_typ, node_ptr) \ + ({ \ + static_assert(_Generic(node_ptr, cr_ipc_sll_node *: 1, default: 0), \ + "typeof("#node_ptr") != cr_ipc_sll_node *"); \ + assert(node_ptr); \ + static_assert(offsetof(node_typ, cr_ipc_sll_node) == 0); \ + ((node_typ*)(node_ptr)); \ + }) + +void cr_ipc_sll_push_to_rear(_cr_ipc_sll_root *root, cr_ipc_sll_node *node); +void cr_ipc_sll_pop_from_front(_cr_ipc_sll_root *root); + +/* doubly linked list *********************************************************/ + +typedef struct _cr_ipc_dll_node { + struct _cr_ipc_dll_node *front, *rear; +} cr_ipc_dll_node; + +#define cr_ipc_dll_node_cast(node_typ, node_ptr) \ + ({ \ + static_assert(_Generic(node_ptr, cr_ipc_dll_node *: 1, default: 0), \ + "typeof("#node_ptr") != cr_ipc_dll_node *"); \ + assert(node_ptr); \ + static_assert(offsetof(node_typ, cr_ipc_dll_node) == 0); \ + ((node_typ*)(node_ptr)); \ + }) + +void cr_ipc_dll_push_to_rear(_cr_ipc_dll_root *root, cr_ipc_dll_node *node); +void cr_ipc_dll_remove(_cr_ipc_dll_root *root, cr_ipc_dll_node *node); +void cr_ipc_dll_pop_from_front(_cr_ipc_dll_root *root); + +#endif /* _LIBCR_IPC__LINKEDLIST_H_ */ diff --git a/libcr_ipc/chan.c b/libcr_ipc/chan.c index 7dd1132..12d2ec2 100644 --- a/libcr_ipc/chan.c +++ b/libcr_ipc/chan.c @@ -4,11 +4,31 @@ * 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> -void _cr_chan_dequeue(void *_ch, size_t) { +#include "_linkedlist.h" + +/* base channels **************************************************************/ + +struct cr_chan_waiter { + cr_ipc_dll_node; + cid_t cid; + void *val_ptr; + void (*dequeue)(void *, size_t); + void *dequeue_arg1; + size_t dequeue_arg2; +}; + +void cr_chan_dequeue(void *_ch, size_t) { struct _cr_chan *ch = _ch; - _cr_ipc_dll_pop_from_front(&ch->waiters); + cr_ipc_dll_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) { @@ -17,7 +37,7 @@ void _cr_chan_xfer(enum _cr_chan_waiter_typ self_typ, struct _cr_chan *ch, void if (ch->waiters.front && ch->waiter_typ != self_typ) { /* non-blocking fast-path */ /* Copy. */ - struct _cr_chan_waiter *front = _cr_ipc_dll_node_cast(struct _cr_chan_waiter, ch->waiters.front); + struct cr_chan_waiter *front = cr_ipc_dll_node_cast(struct cr_chan_waiter, ch->waiters.front); if (self_typ == _CR_CHAN_SENDER) memcpy(front->val_ptr, val_ptr, val_size); else @@ -27,14 +47,123 @@ void _cr_chan_xfer(enum _cr_chan_waiter_typ self_typ, struct _cr_chan *ch, void front->dequeue_arg2); cr_yield(); } else { /* blocking slow-path */ - struct _cr_chan_waiter self = { + struct cr_chan_waiter self = { .cid = cr_getcid(), .val_ptr = val_ptr, - .dequeue = _cr_chan_dequeue, + .dequeue = cr_chan_dequeue, .dequeue_arg1 = ch, }; - _cr_ipc_dll_push_to_rear(&ch->waiters, &self); + cr_ipc_dll_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 *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++) + cr_ipc_dll_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){ + .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; +} diff --git a/libcr_ipc/include/libcr_ipc/_linkedlist.h b/libcr_ipc/include/libcr_ipc/_linkedlist.h deleted file mode 100644 index 543e058..0000000 --- a/libcr_ipc/include/libcr_ipc/_linkedlist.h +++ /dev/null @@ -1,99 +0,0 @@ -/* libcr_ipc/_linkedlist.h - Common low-level linked lists for use in libcr_ipc - * - * Copyright (C) 2024-2025 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 *********************************************************/ - -typedef struct __cr_ipc_sll_node { - struct __cr_ipc_sll_node *rear; -} _cr_ipc_sll_node; - -typedef struct { - _cr_ipc_sll_node *front, *rear; -} _cr_ipc_sll_root; - -#define _cr_ipc_sll_node_cast(node_typ, node_ptr) \ - ({ \ - static_assert(_Generic(node_ptr, _cr_ipc_sll_node *: 1, default: 0), \ - "typeof("#node_ptr") != _cr_ipc_sll_node *"); \ - assert(node_ptr); \ - static_assert(offsetof(node_typ, _cr_ipc_sll_node) == 0); \ - ((node_typ*)(node_ptr)); \ - }) - -static inline void _cr_ipc_sll_push_to_rear(_cr_ipc_sll_root *root, _cr_ipc_sll_node *node) { - assert(root); - node->rear = NULL; - if (root->rear) - root->rear->rear = node; - else - root->front = node; - root->rear = node; -} - -static inline void _cr_ipc_sll_pop_from_front(_cr_ipc_sll_root *root) { - assert(root); - assert(root->front); - root->front = root->front->rear; - if (!root->front) - root->rear = NULL; -} - -/* doubly linked list *********************************************************/ - -typedef struct __cr_ipc_dll_node { - struct __cr_ipc_dll_node *front, *rear; -} _cr_ipc_dll_node; - -typedef struct { - _cr_ipc_dll_node *front, *rear; -} _cr_ipc_dll_root; - -#define _cr_ipc_dll_node_cast(node_typ, node_ptr) \ - ({ \ - static_assert(_Generic(node_ptr, _cr_ipc_dll_node *: 1, default: 0), \ - "typeof("#node_ptr") != _cr_ipc_dll_node *"); \ - assert(node_ptr); \ - static_assert(offsetof(node_typ, _cr_ipc_dll_node) == 0); \ - ((node_typ*)(node_ptr)); \ - }) - -static inline void _cr_ipc_dll_push_to_rear(_cr_ipc_dll_root *root, _cr_ipc_dll_node *node) { - 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; -} - -static inline void _cr_ipc_dll_remove(_cr_ipc_dll_root *root, _cr_ipc_dll_node *node) { - 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; -} - -static inline void _cr_ipc_dll_pop_from_front(_cr_ipc_dll_root *root) { - assert(root); - assert(root->front); - _cr_ipc_dll_remove(root, root->front); -} - -#endif /* _LIBCR_IPC__LINKEDLIST_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/_linkedlist_pub.h b/libcr_ipc/include/libcr_ipc/_linkedlist_pub.h new file mode 100644 index 0000000..6719ba4 --- /dev/null +++ b/libcr_ipc/include/libcr_ipc/_linkedlist_pub.h @@ -0,0 +1,26 @@ +/* libcr_ipc/_linkedlist_pub.h - Common low-level linked lists for use in libcr_ipc + * + * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> + * SPDX-License-Identifier: AGPL-3.0-or-later + */ + +#ifndef _LIBCR_IPC__LINKEDLIST_PUB_H_ +#define _LIBCR_IPC__LINKEDLIST_PUB_H_ + +/* singly linked list *********************************************************/ + +struct _cr_ipc_sll_node; + +typedef struct { + struct _cr_ipc_sll_node *front, *rear; +} _cr_ipc_sll_root; + +/* doubly linked list *********************************************************/ + +struct _cr_ipc_dll_node; + +typedef struct { + struct _cr_ipc_dll_node *front, *rear; +} _cr_ipc_dll_root; + +#endif /* _LIBCR_IPC__LINKEDLIST_PUB_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/chan.h b/libcr_ipc/include/libcr_ipc/chan.h index 5b1e583..ad311a0 100644 --- a/libcr_ipc/include/libcr_ipc/chan.h +++ b/libcr_ipc/include/libcr_ipc/chan.h @@ -9,11 +9,12 @@ #include <stdbool.h> /* for bool */ #include <stddef.h> /* for size_t */ -#include <string.h> /* for memcpy */ -#include <libcr/coroutine.h> /* for cid_t, cr_* */ +#include <libmisc/macro.h> /* LM_CAT2_() */ -#include <libcr_ipc/_linkedlist.h> +#include <libcr_ipc/_linkedlist_pub.h> + +/* base channels **************************************************************/ /** * CR_CHAN_DECLARE(NAME, VAL_T) declares the following type and @@ -21,7 +22,7 @@ * * type: * - * /** + * / ** * * A NAME##_t is a fair unbuffered channel that transports * * values of type `VAL_T`. * * @@ -35,7 +36,7 @@ * * methods: * - * /** + * / ** * * NAME##_send(ch, val) sends `val` over `ch`. * * * * @runs_in coroutine @@ -44,7 +45,7 @@ * * / * void NAME##_send(NAME##_t *ch, VAL_T val); * - * /** + * / ** * * NAME##_recv(ch) reads and returns a value from ch. * * * * @runs_in coroutine @@ -53,7 +54,7 @@ * * / * VAL_T NAME##_recv(NAME##_t *ch); * - * /** + * / ** * * NAME##_can_send(ch) returns whether NAME##_send(ch, val) * * would run without pausing. * * @@ -63,7 +64,7 @@ * * / * bool NAME##_can_send(NAME##_t *ch); * - * /** + * / ** * * NAME##_can_recv(ch) returns whether NAME##_recv(ch) would * * return without pausing. * * @@ -78,51 +79,97 @@ struct _cr_chan core; \ VAL_T vals[0]; \ } NAME##_t; \ - \ + \ static inline void NAME##_send(NAME##_t *ch, VAL_T val) { \ cr_assert_in_coroutine(); \ _cr_chan_xfer(_CR_CHAN_SENDER, &ch->core, &val, sizeof(val)); \ } \ - \ + \ static inline VAL_T NAME##_recv(NAME##_t *ch) { \ cr_assert_in_coroutine(); \ 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) { \ cr_assert_in_coroutine(); \ return ch->core.waiters.front && \ ch->core.waiter_typ == _CR_CHAN_RECVER; \ } \ - \ + \ static inline bool NAME##_can_recv(NAME##_t *ch) { \ cr_assert_in_coroutine(); \ return ch->core.waiters.front && \ ch->core.waiter_typ == _CR_CHAN_SENDER; \ - } + } \ + \ + extern int LM_CAT2_(_CR_CHAN_FORCE_SEMICOLON_, __COUNTER__) enum _cr_chan_waiter_typ { _CR_CHAN_SENDER, _CR_CHAN_RECVER, }; -struct _cr_chan_waiter { - _cr_ipc_dll_node; - cid_t cid; - void *val_ptr; - void (*dequeue)(void *, size_t); - void *dequeue_arg1; - size_t dequeue_arg2; -}; - struct _cr_chan { enum _cr_chan_waiter_typ waiter_typ; - _cr_ipc_dll_root waiters; + _cr_ipc_dll_root waiters; }; -void _cr_chan_dequeue(void *_ch, size_t); 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) \ + /* The _valp temporary variable is to get the compiler to check that \ + * the types are compatible. */ \ + ((struct cr_select_arg){ \ + .op = _CR_SELECT_OP_RECV, \ + .ch = &((CH)->core), \ + .val_ptr = ({ typeof((CH)->vals[0]) *_valp = VALP; _valp; }), \ + .val_siz = sizeof((CH)->vals[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) \ + /* The _valp temporary variable is to get the compiler to check that \ + * the types are compatible. */ \ + ((struct cr_select_arg){ \ + .op = _CR_SELECT_OP_SEND, \ + .ch = &((CH)->core), \ + .val_ptr = ({ typeof((CH)->vals[0]) *_valp = VALP; _valp; }), \ + .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) **********************************************/ + +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 cba8c19..ec40f5c 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,9 @@ #include <stdbool.h> /* for bool */ -#include <libcr/coroutine.h> /* for cid_t, cr_* */ +#include <libmisc/private.h> -#include <libcr_ipc/_linkedlist.h> - -struct _cr_mutex_waiter { - _cr_ipc_sll_node; - cid_t cid; -}; +#include <libcr_ipc/_linkedlist_pub.h> /** * A cr_mutex_t is a fair mutex. @@ -27,8 +22,10 @@ struct _cr_mutex_waiter { * first place, then it has no business unlocking one. */ typedef struct { + BEGIN_PRIVATE(LIBCR_IPC_MUTEX_H); bool locked; _cr_ipc_sll_root waiters; + END_PRIVATE(LIBCR_IPC_MUTEX_H); } cr_mutex_t; /** @@ -38,21 +35,7 @@ typedef struct { * @cr_pauses maybe * @cr_yields maybe */ -static inline 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 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 @@ -62,16 +45,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); - cr_assert_in_coroutine(); - - assert(mu->locked); - if (mu->waiters.front) { - cr_unpause(_cr_ipc_sll_node_cast(struct _cr_mutex_waiter, 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/owned_mutex.h b/libcr_ipc/include/libcr_ipc/owned_mutex.h deleted file mode 100644 index c66240f..0000000 --- a/libcr_ipc/include/libcr_ipc/owned_mutex.h +++ /dev/null @@ -1,79 +0,0 @@ -/* libcr_ipc/owned_mutex.h - Owned mutexes for libcr - * - * Copyright (C) 2024 Luke T. Shumaker <lukeshu@lukeshu.com> - * SPDX-License-Identifier: AGPL-3.0-or-later - */ - -#ifndef _LIBCR_IPC_OWNED_MUTEX_H_ -#define _LIBCR_IPC_OWNED_MUTEX_H_ - -#include <stdbool.h> /* for bool */ - -#include <libcr/coroutine.h> /* for cid_t, cr_unpause(), cr_pause_and_yield() */ - -#include <libcr_ipc/_linkedlist.h> - -struct _cr_owned_mutex_waiter { - _cr_ipc_sll_node; - cid_t cid; -}; - -/** - * A cr_owned_mutex_t is a fair mutex that tracks not just whether it - * is locked, but which coroutine has it locked. - * - * 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 { - cid_t owner; - _cr_ipc_sll_root waiters; -} cr_owned_mutex_t; - -/** - * Lock the mutex. Blocks if it is already locked. - * - * @runs_in coroutine - * @cr_pauses maybe - * @cr_yields maybe - */ -static inline void cr_owned_mutex_lock(cr_owned_mutex_t *mu) { - assert(mu); - - if (!mu->owner) /* non-blocking fast-path */ - mu->owner = cr_getcid(); - else { /* blocking slow-path */ - struct _cr_owned_mutex_waiter self = { - .cid = cr_getcid(), - }; - _cr_ipc_sll_push_to_rear(&mu->waiters, &self); - cr_pause_and_yield(); - } - assert(mu->owner == cr_getcid()); -} - -/** - * Unlock the mutex. Unblocks a coroutine that is blocked on - * cr_owned_mutex_lock(). Must be the called from the same coroutine - * that called cr_owned_mutex_lock(). - * - * @runs_in coroutine - * @cr_pauses never - * @cr_yields never - */ -static inline void cr_owned_mutex_unlock(cr_owned_mutex_t *mu) { - assert(mu); - - assert(mu->owner == cr_getcid()); - if (mu->waiters.front) { - cid_t waiter = _cr_ipc_sll_node_cast(struct _cr_owned_mutex_waiter, mu->waiters.front)->cid; - cr_unpause(waiter); - mu->owner = waiter; - _cr_ipc_sll_pop_from_front(&mu->waiters); - } else - mu->owner = 0; -} - -#endif /* _LIBCR_IPC_OWNED_MUTEX_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/rpc.h b/libcr_ipc/include/libcr_ipc/rpc.h index 0ff8bbf..07ace95 100644 --- a/libcr_ipc/include/libcr_ipc/rpc.h +++ b/libcr_ipc/include/libcr_ipc/rpc.h @@ -8,11 +8,10 @@ #define _LIBCR_IPC_RPC_H_ #include <stdbool.h> /* for bool */ -#include <string.h> /* for memcpy() */ -#include <libcr/coroutine.h> /* for cid_t, cr_* */ +#include <libmisc/macro.h> /* for LM_CAT2_() */ -#include <libcr_ipc/_linkedlist.h> +#include <libcr_ipc/_linkedlist_pub.h> /** * CR_RPC_DECLARE(NAME, REQ_T, RESP_T) declares the following types @@ -20,7 +19,7 @@ * * type: * - * /** + * / ** * * 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`. @@ -35,7 +34,7 @@ * * _recv_req() and _send_resp(). * typedef ... NAME##_t; * - * /** + * / ** * * 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. @@ -43,7 +42,7 @@ * * methods: * - * /** + * / ** * * NAME##_send_req(ch, req) submits the `req` request over `ch` and * * returns the response. * * @@ -53,7 +52,7 @@ * * / * RESP_T NAME##_send_req(NAME##_t *ch, REQ_T req); * - * /** + * / ** * * NAME##_recv_req(ch) reads a request from ch, and returns a * * NAME##_req_t handle wrapping that request. * * @@ -63,7 +62,7 @@ * * / * NAME##_req_t NAME##_recv_req(NAME##_t *ch); * - * /** + * / ** * * NAME##_can_recv_req(ch) returns whether NAME##_recv_req(ch) * * would return without pausing. * * @@ -75,7 +74,7 @@ * * type: * - * /** + * / ** * * A NAME##_req_t is a handle that wraps a REQ_T, and is a channel * * that a response may be written to. * * / @@ -83,7 +82,7 @@ * * methods: * - * /** + * / ** * * cr_rpc_send_resp(req, resp) sends the given response to the given * * request. * * @@ -111,7 +110,7 @@ RESP_T resp; \ _cr_rpc_send_req(&ch->core, \ &req, sizeof(req), \ - &resp, sizeof(resp)); \ + &resp); \ return resp; \ } \ \ @@ -136,95 +135,21 @@ *(req._resp) = resp; \ cr_unpause(req._requester); \ cr_yield(); \ - } + } \ + \ + extern int LM_CAT2_(_CR_RPC_FORCE_SEMICOLON_, __COUNTER__) enum _cr_rpc_waiter_typ { _CR_RPC_REQUESTER, _CR_RPC_RESPONDER, }; -struct _cr_rpc_requester { - _cr_ipc_sll_node; - cid_t cid; - void *req_ptr; /* where to read req from */ - void *resp_ptr; /* where to write resp to */ -}; - -struct _cr_rpc_responder { - _cr_ipc_sll_node; - /* /* before enqueued | after dequeued */ - /* /* -------------------+-------------------- */ - cid_t cid; /* responder cid | requester cid */ - void *ptr; /* where to write req | where to write resp */ -}; - struct _cr_rpc { enum _cr_rpc_waiter_typ waiter_typ; _cr_ipc_sll_root waiters; }; -static inline void _cr_rpc_send_req(struct _cr_rpc *ch, - void *req_ptr, size_t req_size, - void *resp_ptr, size_t resp_size) -{ - 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 = - _cr_ipc_sll_node_cast(struct _cr_rpc_responder, ch->waiters.front); - _cr_ipc_sll_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_requester self = { - .cid = cr_getcid(), - .req_ptr = req_ptr, - .resp_ptr = resp_ptr, - }; - _cr_ipc_sll_push_to_rear(&ch->waiters, &self); - /* Wait for a responder to both copy our req and sed - * `*resp_ptr`. */ - cr_pause_and_yield(); - } -} - -static inline 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 = - _cr_ipc_sll_node_cast(struct _cr_rpc_requester, ch->waiters.front); - _cr_ipc_sll_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_responder self = { - .cid = cr_getcid(), - .ptr = req_ptr, - }; - _cr_ipc_sll_push_to_rear(&ch->waiters, &self); - ch->waiter_typ = _CR_RPC_RESPONDER; - cr_pause_and_yield(); - *ret_requester = self.cid; - *ret_resp_ptr = self.ptr; - } -} +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..924acce --- /dev/null +++ b/libcr_ipc/include/libcr_ipc/rwmutex.h @@ -0,0 +1,77 @@ +/* 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/private.h> + +#include <libcr_ipc/_linkedlist_pub.h> + +/** + * 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; + _cr_ipc_sll_root 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 b845082..0000000 --- a/libcr_ipc/include/libcr_ipc/select.h +++ /dev/null @@ -1,88 +0,0 @@ -/* libcr_ipc/select.h - Select between channels - * - * Copyright (C) 2024-2025 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, -}; - -struct _cr_select_waiters { - size_t cnt; - struct cr_select_arg *args; - struct _cr_chan_waiter *nodes; -}; - -void _cr_select_dequeue(void *_waiters, size_t idx); -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_SELECT_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/sema.h b/libcr_ipc/include/libcr_ipc/sema.h index 6db4015..ae8d93d 100644 --- a/libcr_ipc/include/libcr_ipc/sema.h +++ b/libcr_ipc/include/libcr_ipc/sema.h @@ -9,14 +9,9 @@ #include <stdbool.h> -#include <libcr/coroutine.h> /* for cid_t, cr_* */ +#include <libmisc/private.h> -#include <libcr_ipc/_linkedlist.h> - -struct _cr_sema_waiter { - _cr_ipc_sll_node; - cid_t cid; -}; +#include <libcr_ipc/_linkedlist_pub.h> /** * A cr_sema_t is a fair unbounded[1] counting semaphore. @@ -24,9 +19,11 @@ struct _cr_sema_waiter { * [1]: Well, UINT_MAX */ typedef struct { + BEGIN_PRIVATE(LIBCR_IPC_SEMA_H); unsigned int cnt; bool unpausing; _cr_ipc_sll_root waiters; + END_PRIVATE(LIBCR_IPC_SEMA_H); } cr_sema_t; /** @@ -36,36 +33,14 @@ typedef struct { * @cr_pauses never * @cr_yields never */ -static inline 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( - _cr_ipc_sll_node_cast(struct _cr_sema_waiter, sema->waiters.front)->cid); - sema->unpausing = true; - } - 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); - cr_assert_in_intrhandler(); - - sema->cnt++; - if (sema->waiters.front && !sema->unpausing) { - cr_unpause_from_intrhandler( - _cr_ipc_sll_node_cast(struct _cr_sema_waiter, sema->waiters.front)->cid); - sema->unpausing = true; - } -} +void cr_sema_signal_from_intrhandler(cr_sema_t *sema); /** * Wait until the semaphore is >0, then decrement it. @@ -74,27 +49,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); - cr_assert_in_coroutine(); - - bool saved = cr_save_and_disable_interrupts(); - - struct _cr_sema_waiter self = { - .cid = cr_getcid(), - }; - _cr_ipc_sll_push_to_rear(&sema->waiters, &self); - if (sema->waiters.front != &self || !sema->cnt) - cr_pause_and_yield(); - assert(sema->waiters.front == &self && sema->cnt); - _cr_ipc_sll_pop_from_front(&sema->waiters); - sema->cnt--; - if (sema->cnt && sema->waiters.front) - cr_unpause( - _cr_ipc_sll_node_cast(struct _cr_sema_waiter, sema->waiters.front)->cid); - else - sema->unpausing = false; - 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..28debba --- /dev/null +++ b/libcr_ipc/mutex.c @@ -0,0 +1,45 @@ +/* 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_* */ + +#define IMPLEMENTATION_FOR_LIBCR_IPC_MUTEX_H YES +#include <libcr_ipc/mutex.h> + +#include "_linkedlist.h" + +struct cr_mutex_waiter { + cr_ipc_sll_node; + cid_t cid; +}; + +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 self = { + .cid = cr_getcid(), + }; + cr_ipc_sll_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(cr_ipc_sll_node_cast(struct cr_mutex_waiter, mu->waiters.front)->cid); + cr_ipc_sll_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..a648fde --- /dev/null +++ b/libcr_ipc/rpc.c @@ -0,0 +1,85 @@ +/* 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 <libcr_ipc/rpc.h> + +#include "_linkedlist.h" + +struct cr_rpc_requester { + cr_ipc_sll_node; + cid_t cid; + void *req_ptr; /* where to read req from */ + void *resp_ptr; /* where to write resp to */ +}; + +struct cr_rpc_responder { + cr_ipc_sll_node; + /* before enqueued | after dequeued */ + /* -------------------+-------------------- */ + cid_t cid; /* responder cid | requester cid */ + void *ptr; /* where to write req | where to write resp */ +}; + +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 = + cr_ipc_sll_node_cast(struct cr_rpc_responder, ch->waiters.front); + cr_ipc_sll_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_requester self = { + .cid = cr_getcid(), + .req_ptr = req_ptr, + .resp_ptr = resp_ptr, + }; + cr_ipc_sll_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 = + cr_ipc_sll_node_cast(struct cr_rpc_requester, ch->waiters.front); + cr_ipc_sll_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_responder self = { + .cid = cr_getcid(), + .ptr = req_ptr, + }; + cr_ipc_sll_push_to_rear(&ch->waiters, &self); + ch->waiter_typ = _CR_RPC_RESPONDER; + cr_pause_and_yield(); + *ret_requester = self.cid; + *ret_resp_ptr = self.ptr; + } +} diff --git a/libcr_ipc/rwmutex.c b/libcr_ipc/rwmutex.c new file mode 100644 index 0000000..04016d6 --- /dev/null +++ b/libcr_ipc/rwmutex.c @@ -0,0 +1,103 @@ +/* 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_* */ + +#define IMPLEMENTATION_FOR_LIBCR_IPC_RWMUTEX_H YES +#include <libcr_ipc/rwmutex.h> + +#include "_linkedlist.h" + +struct cr_rwmutex_waiter { + cr_ipc_sll_node; + bool is_reader; + cid_t cid; +}; + +void cr_rwmutex_lock(cr_rwmutex_t *mu) { + assert(mu); + cr_assert_in_coroutine(); + + struct cr_rwmutex_waiter self = { + .is_reader = false, + .cid = cr_getcid(), + }; + cr_ipc_sll_push_to_rear(&mu->waiters, &self); + if (mu->waiters.front != &self.cr_ipc_sll_node || mu->locked) + cr_pause_and_yield(); + assert(mu->waiters.front == &self.cr_ipc_sll_node); + + /* We now hold the lock (and are mu->waiters.front). */ + cr_ipc_sll_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 self = { + .is_reader = true, + .cid = cr_getcid(), + }; + cr_ipc_sll_push_to_rear(&mu->waiters, &self); + if (mu->waiters.front != &self.cr_ipc_sll_node || (mu->locked && mu->nreaders == 0)) + cr_pause_and_yield(); + assert(mu->waiters.front == &self.cr_ipc_sll_node); + + /* We now hold the lock (and are mu->waiters.front). */ + cr_ipc_sll_pop_from_front(&mu->waiters); + mu->nreaders++; + mu->locked = true; + struct cr_rwmutex_waiter *waiter = mu->waiters.front + ? cr_ipc_sll_node_cast(struct cr_rwmutex_waiter, mu->waiters.front) + : NULL; + if (waiter && waiter->is_reader) { + assert(mu->unpausing); + cr_unpause(waiter->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 *waiter = + cr_ipc_sll_node_cast(struct cr_rwmutex_waiter, mu->waiters.front); + mu->unpausing = true; + cr_unpause(waiter->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 *waiter = + cr_ipc_sll_node_cast(struct cr_rwmutex_waiter, mu->waiters.front); + assert(!waiter->is_reader); + mu->unpausing = true; + cr_unpause(waiter->cid); + } else { + mu->locked = false; + } + } +} diff --git a/libcr_ipc/select.c b/libcr_ipc/select.c deleted file mode 100644 index 4bd9067..0000000 --- a/libcr_ipc/select.c +++ /dev/null @@ -1,102 +0,0 @@ -/* libcr_ipc/select.c - Select between channels - * - * Copyright (C) 2024-2025 Luke T. Shumaker <lukeshu@lukeshu.com> - * SPDX-License-Identifier: AGPL-3.0-or-later - */ - -#include <libcr_ipc/select.h> - -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++) - _cr_ipc_dll_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){ - .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; -} diff --git a/libcr_ipc/sema.c b/libcr_ipc/sema.c new file mode 100644 index 0000000..85add6c --- /dev/null +++ b/libcr_ipc/sema.c @@ -0,0 +1,66 @@ +/* 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_* */ + +#define IMPLEMENTATION_FOR_LIBCR_IPC_SEMA_H YES +#include <libcr_ipc/sema.h> + +#include "_linkedlist.h" + +struct cr_sema_waiter { + cr_ipc_sll_node; + cid_t cid; +}; + +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( + cr_ipc_sll_node_cast(struct cr_sema_waiter, sema->waiters.front)->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( + cr_ipc_sll_node_cast(struct cr_sema_waiter, sema->waiters.front)->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 self = { + .cid = cr_getcid(), + }; + cr_ipc_sll_push_to_rear(&sema->waiters, &self); + if (sema->waiters.front != &self.cr_ipc_sll_node || !sema->cnt) + cr_pause_and_yield(); + assert(sema->waiters.front == &self.cr_ipc_sll_node && sema->cnt); + cr_ipc_sll_pop_from_front(&sema->waiters); + sema->cnt--; + if (sema->cnt && sema->waiters.front) + cr_unpause( + cr_ipc_sll_node_cast(struct cr_sema_waiter, sema->waiters.front)->cid); + else + sema->unpausing = false; + cr_restore_interrupts(saved); +} diff --git a/libcr_ipc/tests/config.h b/libcr_ipc/tests/config.h index b00508c..a648589 100644 --- a/libcr_ipc/tests/config.h +++ b/libcr_ipc/tests/config.h @@ -7,9 +7,9 @@ #ifndef _CONFIG_H_ #define _CONFIG_H_ -#define CONFIG_COROUTINE_STACK_SIZE_DEFAULT (4*1024) +#define CONFIG_COROUTINE_STACK_SIZE_DEFAULT (8*1024) #define CONFIG_COROUTINE_NAME_LEN 16 -#define CONFIG_COROUTINE_NUM 8 +#define CONFIG_COROUTINE_NUM 16 #define CONFIG_COROUTINE_MEASURE_STACK 1 #define CONFIG_COROUTINE_PROTECT_STACK 1 diff --git a/libcr_ipc/tests/test_chan.c b/libcr_ipc/tests/test_chan.c index 9d6eecf..9b6f018 100644 --- a/libcr_ipc/tests/test_chan.c +++ b/libcr_ipc/tests/test_chan.c @@ -1,6 +1,6 @@ /* libcr_ipc/tests/test_chan.c - Tests for <libcr_ipc/chan.h> * - * 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,7 +9,7 @@ #include "test.h" -CR_CHAN_DECLARE(intchan, int) +CR_CHAN_DECLARE(intchan, int); COROUTINE cr_producer(void *_ch) { intchan_t *ch = _ch; 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 index 4aff5ca..1e3c471 100644 --- a/libcr_ipc/tests/test_rpc.c +++ b/libcr_ipc/tests/test_rpc.c @@ -9,7 +9,7 @@ #include "test.h" -CR_RPC_DECLARE(intrpc, int, int) +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. */ 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..1db645b --- /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(); + + intchan_send(&ch[n], n); + + cr_end(); +} + +COROUTINE cr_final(void *) { + cr_begin(); + + int ret = intchan_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 index 3208237..e5b22a5 100644 --- a/libcr_ipc/tests/test_sema.c +++ b/libcr_ipc/tests/test_sema.c @@ -5,6 +5,8 @@ */ #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" @@ -54,7 +56,7 @@ COROUTINE cr_consumer(void *_sema) { } int main() { - cr_sema_t sema = {0}; + cr_sema_t sema = {}; printf("== test 1 =========================================\n"); coroutine_add("first", cr_first, &sema); |