From 4da8e81989f6ed86628d6497397b22e0cd8daf53 Mon Sep 17 00:00:00 2001 From: "Luke T. Shumaker" Date: Mon, 30 Sep 2024 21:29:08 -0600 Subject: libcr_ipc: Redo --- libcr_ipc/include/libcr_ipc/_TODO_select.h | 65 ++++++++ libcr_ipc/include/libcr_ipc/_common.h | 57 ------- libcr_ipc/include/libcr_ipc/_linkedlist.h | 108 +++++++++++++ libcr_ipc/include/libcr_ipc/chan.h | 248 +++++++++++++++------------- libcr_ipc/include/libcr_ipc/mutex.h | 41 +++-- libcr_ipc/include/libcr_ipc/rpc.h | 251 ++++++++++++++++------------- libcr_ipc/include/libcr_ipc/sema.h | 122 +++++--------- 7 files changed, 514 insertions(+), 378 deletions(-) create mode 100644 libcr_ipc/include/libcr_ipc/_TODO_select.h delete mode 100644 libcr_ipc/include/libcr_ipc/_common.h create mode 100644 libcr_ipc/include/libcr_ipc/_linkedlist.h (limited to 'libcr_ipc') diff --git a/libcr_ipc/include/libcr_ipc/_TODO_select.h b/libcr_ipc/include/libcr_ipc/_TODO_select.h new file mode 100644 index 0000000..5510fc4 --- /dev/null +++ b/libcr_ipc/include/libcr_ipc/_TODO_select.h @@ -0,0 +1,65 @@ +/* + * Copyright (C) 2024 Luke T. Shumaker + * SPDX-Licence-Identifier: AGPL-3.0-or-later + */ + +struct _cr_select_arg { + enum _cr_select_op { + _CR_SELECT_NONE, + _CR_SELECT_RECV, + _CR_SELECT_SEND, + _CR_SELECT_DEFAULT, + } op; + struct _cr_chan *ch; + struct _cr_chan_waiter self; +}; +#define CR_SELECT_RECV(ch) ((struct _cr_select_arg){.op=_CR_SELECT_RECV, sizeof((ch)->vals[0]), ch, +#define CR_SELECT_SEND(ch) _CR_SELECT_SEND, sizeof((ch)->vals[0]), ch, +#define CR_SELECT_DEFAULT _CR_SELECT_DEFAULT, +#define CR_SELECT(OPS) switch(_cr_chan_select(OPS _CR_SELECT_NONE)) + +size_t _cr_chan_select(enum _cr_select_op a, ...) { + restart: + size_t blocking, nonblocking; + bool have_default = false; + + va_list args; + va_start(args, a); + bool first = true; + for (size_t i = 0; true; i++) { + enum _cr_select_op op; + if (first) { + op = a; + first = false; + } else + op = va_arg(args, enum _cr_select_op); + if (op == _CR_SELECT_NONE) + break; + else if (op == _CR_SELECT_DEFAULT) { + have_default = true; + continue; + } + size_t sz; + struct _cr_chan *ch; + sz = va_arg(args, size_t); + ch = va_arg(args, struct _cr_chan *); + if (op == _CR_SELECT_RECV) { + if (ch->waiters.front && ch->waiter_typ == _CH_CHAN_SENDER) + nonblocking++; + else + blocking++; + } else { + if (ch->waiters.front && ch->waiter_typ == _CH_CHAN_RECVER) + nonblocking++; + else + blocking++; + } + } + va_end(args); + + random() + + if (nonblocking == 0 && !have_default) { + goto restart; + } +} diff --git a/libcr_ipc/include/libcr_ipc/_common.h b/libcr_ipc/include/libcr_ipc/_common.h deleted file mode 100644 index 8d7f656..0000000 --- a/libcr_ipc/include/libcr_ipc/_common.h +++ /dev/null @@ -1,57 +0,0 @@ -/* libcr_ipc/_common.h - Common low-level utilities for use in libcr_ipc - * - * Copyright (C) 2024 Luke T. Shumaker - * SPDX-Licence-Identifier: AGPL-3.0-or-later - */ - -#ifndef _COROUTINE__COMMON_H_ -#define _COROUTINE__COMMON_H_ - -#include - -#include - -#define _cr_ipc_static_assert_sametype(a, b, msg) \ - static_assert(_Generic(a, typeof(b): 1, default: 0), msg) -#define _cr_ipc_str(a) #a - -struct _cr_ipc_cid_fifo_node { - cid_t val; - struct _cr_ipc_cid_fifo_node *next; -}; - -struct _cr_ipc_cid_fifo { - struct _cr_ipc_cid_fifo_node *head, **tail; -}; - - -#define _cr_ipc_cid_fifo_self(name) \ - struct _cr_ipc_cid_fifo_node name = { \ - .val = cr_getcid(), \ - .next = NULL, \ - } - -static inline bool _cr_ipc_cid_fifo_isempty(struct _cr_ipc_cid_fifo *fifo) { - return !fifo->head; -} - -static inline void _cr_ipc_cid_fifo_push(struct _cr_ipc_cid_fifo *fifo, struct _cr_ipc_cid_fifo_node *self) { - if (!fifo->tail) - fifo->tail = &(fifo->head); - *(fifo->tail) = self; - fifo->tail = &(self->next); -} - -static inline cid_t _cr_ipc_cid_fifo_pop(struct _cr_ipc_cid_fifo *fifo) { - if (!fifo->tail) - fifo->tail = &(fifo->head); - cid_t cid = 0; - if (fifo->head) { - cid = fifo->head->val; - if (!(( fifo->head = fifo->head->next )) ) - fifo->tail = &(fifo->head); - } - return cid; -} - -#endif /* _COROUTINE__COMMON_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/_linkedlist.h b/libcr_ipc/include/libcr_ipc/_linkedlist.h new file mode 100644 index 0000000..8e746c9 --- /dev/null +++ b/libcr_ipc/include/libcr_ipc/_linkedlist.h @@ -0,0 +1,108 @@ +/* libcr_ipc/_linkedlist.h - Common low-level linked lists for use in libcr_ipc + * + * Copyright (C) 2024 Luke T. Shumaker + * SPDX-Licence-Identifier: AGPL-3.0-or-later + */ + +#ifndef _COROUTINE__LINKEDLIST_H_ +#define _COROUTINE__LINKEDLIST_H_ + +#include + +/* 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 /* _COROUTINE__LINKEDLIST_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/chan.h b/libcr_ipc/include/libcr_ipc/chan.h index bc6163c..26e8a8d 100644 --- a/libcr_ipc/include/libcr_ipc/chan.h +++ b/libcr_ipc/include/libcr_ipc/chan.h @@ -7,131 +7,151 @@ #ifndef _COROUTINE_CHAN_H_ #define _COROUTINE_CHAN_H_ -#include +#include /* for bool */ +#include /* for size_t */ +#include /* for memcpy */ + +#include /* for cid_t, cr_unpause(), cr_pause_and_yield() */ + +#include /** - * A cr_chan_t(val_t) is a simple unbuffered (Go-like) channel that - * transports values of type `val_t`. + * CR_CHAN_DECLARE(NAME, VAL_T) declares the following type and + * methods: + * + * type: + * + * /** + * * A NAME##_t is a fair unbuffered channel that transports + * * values of type `VAL_T`. + * * + * * None of the methods have `_from_intrhandler` variants + * * because either end of a channel may block, and interrupt + * * handlers must not block. Perhaps you would be better served + * * with a semaphore if you need to signal + * * something from an interrupt handler. + * * / + * typedef ... NAME##_t; + * + * methods: + * + * /** + * * 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); * - * None of the methods have `_from_intrhandler` variants because - * either end of a channel may block, and interrupt handlers must not - * block. + * /** + * * 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); + * + * /** + * * 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); + * + * /** + * * 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); */ -#define cr_chan_t(val_t) struct { \ - bool ok_to_write; \ - cid_t reader, *tail_reader; \ - val_t *reader_val; \ - \ - bool ok_to_read; \ - cid_t writer, *tail_writer; \ - val_t *writer_val; \ +#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; \ } -/* These "functions" are preprocessor macros instead of real C - * functions so that the compiler can do type-checking instead of - * having these functions take `void*`. */ +enum _cr_chan_waiter_typ { + _CR_CHAN_SENDER, + _CR_CHAN_RECVER, +}; -/** - * ch_chan_send(ch, val) sends `val` over `ch`. - * - * @runs_in coroutine - * @cr_pauses maybe - * @cr_yields maybe - */ -#define cr_chan_send(ch, _val) do { \ - _cr_ipc_static_assert_sametype(_val, *(ch)->reader_val, \ - "wrong val type for chan: " \ - _cr_ipc_str(_val)); \ - assert(ch); \ - if ((ch)->ok_to_write) { /* non-blocking */ \ - *((ch)->reader_val) = (_val); \ - (ch)->ok_to_write = false; \ - cr_unpause((ch)->reader); \ - } else { /* blocking */ \ - typeof(*(ch)->writer_val) _val_lvalue = _val; \ - cid_t next = 0; \ - if ((ch)->writer) { \ - *((ch)->tail_writer) = cr_getcid(); \ - (ch)->tail_writer = &next; \ - cr_pause_and_yield(); \ - } else { \ - (ch)->writer = cr_getcid(); \ - (ch)->tail_writer = &next; \ - } \ - assert((ch)->writer == cr_getcid()); \ - (ch)->writer_val = &_val_lvalue; \ - (ch)->ok_to_read = true; \ - cr_pause_and_yield(); \ - assert((ch)->ok_to_read == false); \ - if (next) { \ - (ch)->writer = next; \ - cr_unpause(next); \ - } else { \ - (ch)->writer = 0; \ - (ch)->tail_writer = NULL; \ - } \ - } \ - } while (0) +struct _cr_chan_waiter { + struct _cr_chan_waiter *rear; + cid_t cid; + void *val_ptr; +}; -/** - * cr_chan_recv(ch, val_p) reads a value from ch into `*val_p`. - * - * @runs_in coroutine - * @cr_pauses maybe - * @cr_yields maybe - */ -#define cr_chan_recv(ch, _val_p) do { \ - _cr_ipc_static_assert_sametype(_val_p, (ch)->reader_val, \ - "wrong val_p type for chan: " \ - _cr_ipc_str(_val_p)); \ - assert(ch); \ - if ((ch)->ok_to_read) { /* non-blocking */ \ - *(_val_p) = *((ch)->writer_val); \ - (ch)->ok_to_read = false; \ - cr_unpause((ch)->writer); \ - } else { /* blocking */ \ - cid_t next = 0; \ - if ((ch)->reader) { \ - *((ch)->tail_reader) = cr_getcid(); \ - (ch)->tail_reader = &next; \ - cr_pause_and_yield(); \ - } else { \ - (ch)->reader = cr_getcid(); \ - (ch)->tail_reader = &next; \ - } \ - assert((ch)->reader == cr_getcid()); \ - (ch)->reader_val = (_val_p); \ - (ch)->ok_to_write = true; \ - cr_pause_and_yield(); \ - assert((ch)->ok_to_write == false); \ - if (next) { \ - (ch)->reader = next; \ - cr_unpause(next); \ - } else { \ - (ch)->reader = 0; \ - (ch)->tail_reader = NULL; \ - } \ - } \ - } while (0) +struct _cr_chan { + enum _cr_chan_waiter_typ waiter_typ; + struct { + struct _cr_chan_waiter *front, *rear; + } waiters; +}; -/** - * cr_chan_can_send(ch) returns whether cr_chan_send(ch, val) would - * run without blocking. - * - * @runs_in coroutine - * @cr_pauses never - * @cr_yields never - */ -#define cr_chan_can_send(ch) ((ch)->ok_to_write) +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); -/** - * cr_chan_can_recv(ch) returns whether cr_chan_recv(ch, &val) would - * run without blocking. + 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); + /* Advance cpy_front and *maybe* unpause_front. */ + cr_unpause(ch->waiters.front->cid); + _cr_ipc_sll_pop_from_front(&ch->waiters); + cr_yield(); + } else { /* blocking slow-path */ + struct _cr_chan_waiter self = { + .cid = cr_getcid(), + .val_ptr = val_ptr, + }; + _cr_ipc_sll_push_to_rear(&ch->waiters, &self); + ch->waiter_typ = self_typ; + cr_pause_and_yield(); + } +} + +/* TODO: Implement CR_SELECT() (see `_TODO_select.h`). + * + * Changes required to what's here in chan.h: + * + * - Change the singly-linked-list to a doubly-linked-list (add + * `*front` to _waiter, then replace `sll` with `ddl`). * - * @runs_in coroutine - * @cr_pauses never - * @cr_yields never + * - Have the non-blocking fast-path not just call _pop_from_front() + * on that channel's list, but _remove() on all selected channels' + * lists. */ -#define cr_chan_can_recv(ch) ((ch)->ok_to_read) #endif /* _COROUTINE_CHAN_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/mutex.h b/libcr_ipc/include/libcr_ipc/mutex.h index 01693cf..eb1ecb1 100644 --- a/libcr_ipc/include/libcr_ipc/mutex.h +++ b/libcr_ipc/include/libcr_ipc/mutex.h @@ -7,8 +7,16 @@ #ifndef _COROUTINE_MUTEX_H_ #define _COROUTINE_MUTEX_H_ -#include -#include +#include /* for bool */ + +#include /* for cid_t, cr_unpause(), cr_pause_and_yield() */ + +#include + +struct _cr_mutex_waiter { + struct _cr_mutex_waiter *rear; + cid_t cid; +}; /** * A cr_mutex_t is a fair mutex. @@ -19,8 +27,10 @@ * first place, then it has no business unlocking one. */ typedef struct { - bool locked; - struct _cr_ipc_cid_fifo waiters; + bool locked; + struct { + struct _cr_mutex_waiter *front, *rear; + } waiters; } cr_mutex_t; /** @@ -32,13 +42,17 @@ typedef struct { */ static inline void cr_mutex_lock(cr_mutex_t *mu) { assert(mu); - if (!mu->locked) { + + if (!mu->locked) /* non-blocking fast-path */ mu->locked = true; - return; + 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(); } - _cr_ipc_cid_fifo_self(self); - _cr_ipc_cid_fifo_push(&mu->waiters, &self); - cr_pause_and_yield(); + assert(mu->locked); } /** @@ -51,11 +65,12 @@ static inline void cr_mutex_lock(cr_mutex_t *mu) { */ static inline void cr_mutex_unlock(cr_mutex_t *mu) { assert(mu); + assert(mu->locked); - cid_t next = _cr_ipc_cid_fifo_pop(&mu->waiters); - if (next) - cr_unpause(next); - else + if (mu->waiters.front) { + cr_unpause(mu->waiters.front->cid); + _cr_ipc_sll_pop_from_front(&mu->waiters); + } else mu->locked = false; } diff --git a/libcr_ipc/include/libcr_ipc/rpc.h b/libcr_ipc/include/libcr_ipc/rpc.h index 2351569..9c9c0d5 100644 --- a/libcr_ipc/include/libcr_ipc/rpc.h +++ b/libcr_ipc/include/libcr_ipc/rpc.h @@ -7,129 +7,154 @@ #ifndef _COROUTINE_RPC_H_ #define _COROUTINE_RPC_H_ -#include +#include /* for bool */ -/** - * cr_rpc_t(req_t, resp_t) evaluates to the type definition for a - * rpc-channel on which the requester submits a value of type `req_t` - * and the responder responds with a value of type `resp_t`. - * - * There may be multiple concurrent requesters, but only one - * concurrent responder. If you need multiple concurrent responders, - * set up a system of channels. - * - * None of the methods have `_from_intrhandler` variants, because both - * ends may block, and interrupt handlers must not block. Perhaps you - * would be better served with a semaphore if you - * need to signal something from an interrupt handler. - */ -#define cr_rpc_t(req_t, resp_t) struct { \ - cid_t requester, *tail_requester; \ - cid_t responder; \ - req_t *req_p; \ - resp_t *resp_p; \ - } +#include /* for cid_t, cr_unpause(), cr_pause_and_yield() */ -/* These "functions" are preprocessor macros instead of real C - * functions so that the compiler can do type-checking instead of - * having these functions take `void*`. */ +#include /** - * ch_rpc_req(cr_rpc_t(req_t, resp_t) *ch, resp_t *resp, req_t req) - * submits the `req` request to `ch` puts the response in `*resp_p`. + * CR_RPC_DECLARE(NAME, REQ_T, RESP_T) declares the following types + * and methods: * - * Blocking: Always; until the + * type: * - * @runs_in coroutine - * @cr_pauses always; until the responder has called both - * cr_rpc_recv_req() and cr_rpc_send_resp(). - * @cr_yields always - */ -#define cr_rpc_req(ch, _resp_p, _req) do { \ - typeof(_req) _req_lvalue = _req; \ - _cr_ipc_static_assert_sametype(_resp_p, (ch)->resp_p, \ - "wrong resp_p type for rpc chan: " \ - _cr_ipc_str(_resp_p)); \ - _cr_ipc_static_assert_sametype(&_req_lvalue, (ch)->req_p, \ - "wrong req type for rpc chan: " \ - _cr_ipc_str(_req)); \ - assert(ch); \ - assert(_resp_p); \ - cid_t next = 0; \ - if ((ch)->requester) { \ - *((ch)->tail_requester) = cr_getcid(); \ - (ch)->tail_requester = &next; \ - cr_pause_and_yield(); \ - } else { \ - (ch)->requester = cr_getcid(); \ - (ch)->tail_requester = &next; \ - } \ - assert((ch)->requester == cr_getcid()); \ - (ch)->req_p = &_req_lvalue; \ - (ch)->resp_p = (_resp_p); \ - if ((ch)->responder != 0) \ - cr_unpause((ch)->responder); \ - cr_pause_and_yield(); \ - if (next) { \ - (ch)->requester = next; \ - cr_unpause(next); \ - } else { \ - (ch)->requester = 0; \ - (ch)->tail_requester = NULL; \ - } \ - } while (0) - -/** - * cr_rpc_have_req(cr_rpc_t(req_t, resp_t) *ch) allows a responder - * to check whether or not there is a request waiting to be received - * (with cr_rpc_recv_req()) without blocking if there is not. + * /** + * * 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`. + * * + * * None of the methods have `_from_intrhandler` variants, because the + * * requester end always blocks, and the responder end may block; and + * * interrupt handlers must not block. + * * + * * This rpc-channel construction is more efficient than building a + * * system of one-directional channels because + * * control doesn't need to transfer back to the requester between + * * _recv_req() and _send_resp(). + * typedef ... NAME##_t; * - * @runs_in coroutine - * @cr_pauses never - * @cr_yields never - */ -#define cr_rpc_have_req(ch) ((ch)->req_p != NULL) - -/** - * cr_rpc_recv_req(cr_rpc_t(req_t, resp_t) *ch, req_t *req_p) reads - * a request from ch into `*req_p`. + * methods: * - * If there is not a pending request on `ch`, blocks until there is. + * /** + * * 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 maybe - * @cr_yields maybe - */ -#define cr_rpc_recv_req(ch, _req_p) do { \ - _cr_ipc_static_assert_sametype(_req_p, (ch)->req_p, \ - "wrong req_p type for rpc chan: " \ - _cr_ipc_str(_req_p)); \ - assert(ch); \ - assert(_req_p); \ - (ch)->responder = cr_getcid(); \ - if ((ch)->requester == 0) \ - cr_pause_and_yield(); \ - *(_req_p) = *((ch)->req_p); \ - (ch)->req_p = NULL; \ - } while (0) - -/** - * cr_rpc_send_resp(cr_rpc_t(req_t, resp_t) *ch, resp_t resp) sends - * the reply to the most-recently-read request. + * /** + * * 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); + * + * /** + * * 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 never - * @cr_yields never + * type: + * + * /** + * * 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; + * + * methods: + * + * /** + * * 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); */ -#define cr_rpc_send_resp(ch, _resp) do { \ - _cr_ipc_static_assert_sametype(_resp, *(ch)->resp_p, \ - "wrong resp type for rpc chan: " \ - _cr_ipc_str(_reps)); \ - assert(ch); \ - (ch)->responder = 0; \ - *((ch)->resp_p) = (_resp); \ - (ch)->resp_p = NULL; \ - cr_unpause((ch)->requester); \ - } while (0) +#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(); \ + } #endif /* _COROUTINE_RPC_H_ */ diff --git a/libcr_ipc/include/libcr_ipc/sema.h b/libcr_ipc/include/libcr_ipc/sema.h index 410c092..52ee670 100644 --- a/libcr_ipc/include/libcr_ipc/sema.h +++ b/libcr_ipc/include/libcr_ipc/sema.h @@ -7,12 +7,14 @@ #ifndef _COROUTINE_SEMA_H_ #define _COROUTINE_SEMA_H_ -#include -#include +#include /* for cid_t, cr_unpause(), cr_pause_and_yield() */ -/* Most of the complexity in this file is so that - * cr_sema_signal_from_intrhandler() can actually be safe when called - * in an interrupt handler. */ +#include + +struct _cr_sema_waiter { + struct _cr_sema_waiter *rear; + cid_t cid; +}; /** * A cr_sema_t is a fair unbounded[1] counting semaphore. @@ -20,66 +22,12 @@ * [1]: Well, UINT_MAX */ typedef struct { - volatile int cnt; - - struct _cr_ipc_cid_fifo waiters; - /* locked indicates that a call from within a coroutine is is - * messing with ->waiters, so an interrupt handler can't read - * it. Use `asm volatile ("":::"memory")` after setting =true - * and before setting =false to make sure the compiler doesn't - * re-order writes to ->waiters to be outside of the critical - * section! */ - volatile bool locked; + unsigned int cnt; + struct { + struct _cr_sema_waiter *front, *rear; + } waiters; } cr_sema_t; -/** - * Drain a maximum of sema->cnt coroutines from the sema->waiters - * list. Returns true if cr_getcid() was drained and we're not in an - * interrupt handler. - */ -static inline bool _cr_sema_drain(cr_sema_t *sema, bool in_intrhandler) { - assert(!sema->locked); - cid_t self = cr_getcid(); - - enum drain_result { - DRAINING, - DRAINED_SELF, /* stopped because drained `self` */ - DRAINED_ALL, /* stopped because sema->waiters is empty */ - DRAINED_SOME, /* stopped because sema->cnt == 0 */ - } state = DRAINING; - do { - sema->locked = true; - asm volatile ("":::"memory"); - while (state == DRAINING) { - if (_cr_ipc_cid_fifo_isempty(&sema->waiters)) { - state = DRAINED_ALL; - } else if (!sema->cnt) { - state = DRAINED_SOME; - } else { - sema->cnt--; - cid_t cid = _cr_ipc_cid_fifo_pop(&sema->waiters); - if (in_intrhandler) - cr_unpause_from_intrhandler(cid); - else { - if (cid == self) - state = DRAINED_SELF; - else - cr_unpause(cid); - } - } - } - asm volatile ("":::"memory"); - sema->locked = false; - /* If there are still coroutines in sema->waiters, - * check that sema->cnt wasn't incremented between `if - * (!sema->cnt)` and `sema->locked = false`. */ - } while (state == DRAINED_SOME && sema->cnt); - /* If state == DRAINED_SELF, then we better have been the last - * item in the list! */ - assert(state != DRAINED_SELF || _cr_ipc_cid_fifo_isempty(&sema->waiters)); - return state == DRAINED_SELF; -} - /** * Increment the semaphore, * @@ -87,21 +35,33 @@ static inline bool _cr_sema_drain(cr_sema_t *sema, bool in_intrhandler) { * @cr_pauses never * @cr_yields never */ -static inline void cr_sema_signal(cr_sema_t *sema) { +static inline void cr_sema_signal(cr_sema_t *sema) { + assert(sema); + + cr_disable_interrupts(); sema->cnt++; - if (!sema->locked) - assert(!_cr_sema_drain(sema, false)); + if (sema->waiters.front) { + sema->cnt--; + cr_unpause(sema->waiters.front->cid); + _cr_ipc_sll_pop_from_front(&sema->waiters); + } + cr_enable_interrupts(); } /** - * Like cr_sema_signal(), but safe to call from an interrupt handler. + * 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->locked) - assert(!_cr_sema_drain(sema, true)); + if (sema->waiters.front) { + sema->cnt--; + cr_unpause_from_intrhandler(sema->waiters.front->cid); + _cr_ipc_sll_pop_from_front(&sema->waiters); + } } /** @@ -112,20 +72,20 @@ static inline void cr_sema_signal_from_intrhandler(cr_sema_t *sema) { * @cr_yields maybe */ static inline void cr_sema_wait(cr_sema_t *sema) { - _cr_ipc_cid_fifo_self(self); - - sema->locked = true; - asm volatile ("":::"memory"); - _cr_ipc_cid_fifo_push(&sema->waiters, &self); - asm volatile ("":::"memory"); - sema->locked = false; + assert(sema); - if (_cr_sema_drain(sema, false)) - /* DRAINED_SELF: (1) No need to pause+yield, (2) we - * better have been the last item in the list! */ - assert(!self.next); - else + cr_disable_interrupts(); + if (sema->cnt) { /* non-blocking */ + sema->cnt--; + cr_enable_interrupts(); + } else { /* blocking */ + struct _cr_sema_waiter self = { + .cid = cr_getcid(), + }; + _cr_ipc_sll_push_to_rear(&sema->waiters, &self); + cr_enable_interrupts(); cr_pause_and_yield(); + } } #endif /* _COROUTINE_SEMA_H_ */ -- cgit v1.2.3-2-g168b