0 branches 0 tags
4
Moving things around
jonroach 1 Sep 2025 08:23
1 contributor
367 lines9.8 KB
Text Raw Blame
  • Delete
1#include "coroutine.h"
2#include <assert.h>
3#include <setjmp.h>
4#include <stdbool.h>
5#include <stddef.h>
6#include <stdio.h>
7#include <semaphore.h>
8#include <fcntl.h>
9#include <unistd.h>
10
11#define COROUTINE_STACK_SIZE 16384
12#define COROUTINE_STARTUP_STACK_SIZE 1024
13
14
15///////////////////////////////////////////////////////////////////////////////
16// 2-way linked lists...
17//
18// Broght inline here to avoid namespace polution
19///////////////////////////////////////////////////////////////////////////////
20
21typedef struct List_Link List_Link;
22struct List_Link {
23 List_Link *next;
24 List_Link *prev;
25};
26
27typedef struct List_Head List_Head;
28struct List_Head {
29 union {
30 struct {
31 List_Link link;
32 List_Link *filler;
33 } fwd;
34 struct {
35 List_Link *filler;
36 List_Link link;
37 } back;
38 };
39};
40
41static inline bool List_IsEmpty(const List_Head *list) {
42 return list->fwd.link.next == &list->back.link;
43}
44
45static inline List_Link *List_GetHead(const List_Head *list) {
46 return List_IsEmpty(list) ? NULL : list->fwd.link.next;
47}
48static inline List_Link *List_GetTail(const List_Head *list) {
49 return List_IsEmpty(list) ? NULL : list->back.link.prev;
50}
51#define OFFSETOF(Container, Field) ((char *)&((Container *)4)->Field - (char *)(Container *)4)
52#define List_Link_Container(Container, Link, link) ((Container *)((char *)(link) - OFFSETOF(Container, Link)))
53
54static inline void List_Init(List_Head *list)
55{
56 list->fwd.link.next = &list->back.link;
57 list->fwd.link.prev = NULL;
58 list->back.link.prev = &list->fwd.link;
59}
60
61static inline void List_AddHead(List_Head *list, List_Link *link)
62{
63 List_Link *first = list->fwd.link.next;
64 link->next = first;
65 link->prev = &list->fwd.link;
66 first->prev = link;
67 list->fwd.link.next = link;
68}
69
70static inline void List_AddTail(List_Head *list, List_Link *link)
71{
72 List_Link *last = list->back.link.prev;
73 link->prev = last;
74 link->next = &list->back.link;
75 last->next = link;
76 list->back.link.prev = link;
77}
78
79static inline void List_Remove(List_Link *link)
80{
81 link->prev->next = link->next;
82 link->next->prev = link->prev;
83}
84
85///////////////////////////////////////////////////////////////////////////////
86// ...2-way linked lists
87///////////////////////////////////////////////////////////////////////////////
88
89
90enum {
91 Coroutines_Idle,
92 Coroutines_Starting,
93 Coroutines_Started,
94 Coroutines_Active,
95 Coroutines_Stopping
96};
97
98enum {
99 Chunk_Initial,
100 Chunk_Create,
101 Chunk_Enter
102};
103
104enum {
105 Coroutine_Constructing,
106 Coroutine_Free,
107 Coroutine_Idle,
108 Coroutine_Running,
109 Coroutine_Waiting,
110 Coroutine_Complete
111};
112
113enum {
114 Coroutines_Init,
115 Coroutines_AllocatedChunk,
116 Coroutines_CoroutineComplete,
117};
118
119struct Coroutine {
120 List_Link link;
121 jmp_buf buf;
122 void *this;
123 Coroutine_YieldCallback on_yield;
124 Coroutine_Start start;
125 void *entry_param;
126 void *value;
127 char state;
128 char action;
129};
130
131typedef struct Coroutines Coroutines;
132
133struct Coroutines {
134 jmp_buf controller;
135 jmp_buf chunk_allocated;
136
137 // singletons
138 Coroutine *tip; // top of stack chunk
139 Coroutine *active; // currently running coroutine
140 Coroutine *primary; // Coroutine_Run coroutine
141
142 // lists
143 List_Head free;
144 List_Head inactive; // idle or complete
145 List_Head runable; // running or waiting to run
146 List_Head waiting; // yielded / waiting to run
147 sem_t *waiting_sem;
148
149 // state
150 char state;
151};
152
153Coroutines g_c;
154
155static void stack_chunk_chunk(Coroutine *parent);
156static void stack_chunk_base(Coroutine *parent);
157
158static void Coroutine_PrimeStackChunks()
159{
160 unsigned char chunk_of_stack[COROUTINE_STACK_SIZE];
161 chunk_of_stack[0] = 0xde;
162 chunk_of_stack[1] = 0xad;
163 chunk_of_stack[2] = 0xbe;
164 chunk_of_stack[3] = 0xef;
165 chunk_of_stack[COROUTINE_STACK_SIZE - 4] = 0xde;
166 chunk_of_stack[COROUTINE_STACK_SIZE - 3] = 0xad;
167 chunk_of_stack[COROUTINE_STACK_SIZE - 2] = 0xbe;
168 chunk_of_stack[COROUTINE_STACK_SIZE - 1] = 0xef;
169 stack_chunk_base(NULL);
170}
171
172static void stack_chunk_chunk(Coroutine *parent){
173 unsigned char chunk_of_stack[COROUTINE_STACK_SIZE];
174 chunk_of_stack[0] = 0xde;
175 chunk_of_stack[1] = 0xad;
176 chunk_of_stack[2] = 0xbe;
177 chunk_of_stack[3] = 0xef;
178 chunk_of_stack[COROUTINE_STACK_SIZE - 4] = 0xde;
179 chunk_of_stack[COROUTINE_STACK_SIZE - 3] = 0xad;
180 chunk_of_stack[COROUTINE_STACK_SIZE - 2] = 0xbe;
181 chunk_of_stack[COROUTINE_STACK_SIZE - 1] = 0xef;
182 stack_chunk_base(parent);
183}
184
185static void Coroutine_RunNext()
186{
187 sem_wait(g_c.waiting_sem);
188 assert(!List_IsEmpty(&g_c.runable));
189 Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c.runable));
190 assert(next->state == Coroutine_Running);
191 longjmp(next->buf, Chunk_Enter);
192 assert(false);
193}
194
195static void stack_chunk_base(Coroutine *parent){
196 Coroutine here;
197 here.state = Coroutine_Constructing;
198 switch (setjmp(here.buf)) {
199 case Chunk_Initial:
200 // got here for the first time
201 // parent now has a chunk_of_stack - add it to the free list
202 if (parent) {
203 assert(parent->state == Coroutine_Constructing);
204 parent->state = Coroutine_Free;
205 List_AddHead(&g_c.free, &parent->link);
206 }
207 // note that here is the tip of the chunk-claim stack
208 g_c.tip = &here;
209
210 // return to the coroutine allocator
211 longjmp(g_c.chunk_allocated, 1);
212 case Chunk_Create:
213 // request to create a new chunk on the stack
214 assert(here.state == Coroutine_Constructing);
215 stack_chunk_chunk(&here);
216 assert(false);
217 case Chunk_Enter:
218 // request to start a coroutine (ie use the chunk for a coroutine)
219 assert(here.state == Coroutine_Running);
220 g_c.active = &here;
221 here.value = here.start(here.entry_param);
222 g_c.active = NULL;
223 assert(here.state == Coroutine_Running);
224 List_Remove(&here.link);
225 here.state = Coroutine_Complete;
226 List_AddTail(&g_c.inactive, &here.link);
227 // coroutine has completed
228 if (g_c.primary == &here) {
229 // if primary coroutine - return to Coroutine_Run
230 longjmp(g_c.controller, Coroutines_CoroutineComplete);
231 }
232 Coroutine_RunNext();
233 assert(false);
234 }
235}
236
237void Coroutine_StartSystem()
238{
239 assert(g_c.state == Coroutines_Idle);
240 g_c.state = Coroutines_Starting;
241
242 g_c.tip = NULL;
243 g_c.active = NULL;
244
245 List_Init(&g_c.free);
246 List_Init(&g_c.inactive);
247 List_Init(&g_c.runable);
248 List_Init(&g_c.waiting);
249 char tbuf[256];
250 snprintf(tbuf, sizeof(tbuf), "/coroutine_waiting_sem_%d", getpid());
251 g_c.waiting_sem = sem_open(tbuf, O_CREAT, 0644, 0);
252 sem_unlink(tbuf);
253 assert(g_c.waiting_sem != SEM_FAILED);
254
255 // prime the chunk system
256 if (!setjmp(g_c.chunk_allocated)){
257 Coroutine_PrimeStackChunks();
258 assert(false);
259 }
260 assert(g_c.state == Coroutines_Starting);
261 g_c.state = Coroutines_Started;
262}
263
264void Coroutine_StopSystem()
265{
266 assert(g_c.state == Coroutines_Started);
267 g_c.state = Coroutines_Stopping;
268
269 assert(List_IsEmpty(&g_c.inactive));
270 sem_close(g_c.waiting_sem);
271 g_c.waiting_sem = NULL;
272
273 assert(g_c.state == Coroutines_Stopping);
274 g_c.state = Coroutines_Idle;
275}
276
277void *Coroutine_Run(Coroutine *cor, void *value){
278 assert(g_c.state == Coroutines_Started);
279 g_c.state = Coroutines_Active;
280 g_c.primary = cor;
281 Coroutine_Continue(g_c.primary, value, true);
282
283 if (!setjmp(g_c.controller)){
284 // start the first coroutine
285 Coroutine_RunNext();
286 }
287 assert(List_IsEmpty(&g_c.runable));
288 assert(List_IsEmpty(&g_c.waiting));
289 assert(g_c.state == Coroutines_Active);
290 g_c.state = Coroutines_Started;
291 return Coroutine_GetValue(cor);
292}
293
294Coroutine *Coroutine_New(void *this, Coroutine_YieldCallback on_yield, Coroutine_Start start){
295 assert(g_c.state == Coroutines_Started || g_c.state == Coroutines_Active);
296
297 // if none free - add one
298 if (List_IsEmpty(&g_c.free)){
299 if (!setjmp(g_c.chunk_allocated)){
300 longjmp(g_c.tip->buf, Chunk_Create);
301 }
302 }
303
304 Coroutine *cor = List_Link_Container(Coroutine, link, List_GetHead(&g_c.free));
305 assert(cor->state == Coroutine_Free);
306 cor->state = Coroutine_Idle;
307 cor->this = this;
308 cor->start = start;
309 cor->on_yield = on_yield;
310 cor->value = NULL;
311 List_Remove(&cor->link);
312 List_AddHead(&g_c.inactive, &cor->link);
313
314 return cor;
315}
316
317void Coroutine_Delete(Coroutine *cor){
318 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Complete);
319 cor->state = Coroutine_Free;
320 List_Remove(&cor->link);
321 List_AddTail(&g_c.free, &cor->link);
322}
323
324void Coroutine_Continue(Coroutine *cor, void *value, bool early){
325 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Waiting);
326 cor->entry_param = value;
327 cor->state = Coroutine_Running;
328 List_Remove(&cor->link);
329 if ( early ) {
330 List_AddHead(&g_c.runable, &cor->link);
331 } else {
332 List_AddTail(&g_c.runable, &cor->link);
333 }
334 sem_post(g_c.waiting_sem);
335}
336
337void *Coroutine_Yield(void *value){
338 Coroutine *me = g_c.active;
339 assert(me && me->state == Coroutine_Running);
340 me->value = value;
341 me->state = Coroutine_Waiting;
342 List_Remove(&me->link);
343 List_AddTail(&g_c.waiting, &me->link);
344 if (!setjmp(me->buf)){
345 me->on_yield(me->this);
346 Coroutine_RunNext();
347 }
348 g_c.active = me;
349 // when we return here - we are running again
350 assert(me->state == Coroutine_Running);
351 return me->entry_param;
352}
353
354void *Coroutine_GetValue(Coroutine *cor){
355 return cor->value;
356}
357
358Coroutine *Coroutine_GetActive()
359{
360 return g_c.active;
361}
362
363bool Coroutine_IsRunning(Coroutine *cor)
364{
365 return cor->state == Coroutine_Running || cor->state == Coroutine_Waiting;
366}
367