0 branches 0 tags
49
Change guard checking to be an assert
jonroach 22 Oct 2025 08:32
1 contributor
594 lines14.5 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 "cor_platform.h"
7
8
9static void Coroutine_RunNext(void);
10static void _Coroutine_Continue(Coroutine *cor, void *value, bool early);
11
12///////////////////////////////////////////////////////////////////////////////
13// 2-way linked lists...
14//
15// Brought inline here to avoid namespace polution
16///////////////////////////////////////////////////////////////////////////////
17
18typedef struct List_Link List_Link;
19struct List_Link {
20 List_Link *next;
21 List_Link *prev;
22};
23
24typedef struct List_Head List_Head;
25struct List_Head {
26 union {
27 struct {
28 List_Link link;
29 List_Link *filler;
30 } fwd;
31 struct {
32 List_Link *filler;
33 List_Link link;
34 } back;
35 };
36};
37
38
39static inline bool List_IsEmpty(
40 const List_Head *list
41){
42 return list->fwd.link.next == &list->back.link;
43}
44
45
46static inline List_Link *List_GetHead(
47 const List_Head *list
48){
49 return List_IsEmpty(list) ? NULL : list->fwd.link.next;
50}
51
52
53// static inline List_Link *List_GetTail(
54// const List_Head *list
55// ){
56// return List_IsEmpty(list) ? NULL : list->back.link.prev;
57// }
58
59
60#define OFFSETOF(Container, Field) ((char *)&((Container *)4)->Field - (char *)(Container *)4)
61#define List_Link_Container(Container, Link, link) ((Container *)((char *)(link) - OFFSETOF(Container, Link)))
62
63
64static inline void List_Init(
65 List_Head *list
66){
67 list->fwd.link.next = &list->back.link;
68 list->fwd.link.prev = NULL;
69 list->back.link.prev = &list->fwd.link;
70}
71
72
73static inline void List_AddHead(
74 List_Head *list,
75 List_Link *link
76){
77 List_Link *first = list->fwd.link.next;
78 link->next = first;
79 link->prev = &list->fwd.link;
80 first->prev = link;
81 list->fwd.link.next = link;
82}
83
84
85static inline void List_AddTail(
86 List_Head *list,
87 List_Link *link
88){
89 List_Link *last = list->back.link.prev;
90 link->prev = last;
91 link->next = &list->back.link;
92 last->next = link;
93 list->back.link.prev = link;
94}
95
96
97static inline void List_Remove(
98 List_Link *link
99){
100 link->prev->next = link->next;
101 link->next->prev = link->prev;
102}
103
104///////////////////////////////////////////////////////////////////////////////
105// ...2-way linked lists
106///////////////////////////////////////////////////////////////////////////////
107
108typedef struct Coroutines Coroutines;
109
110enum {
111 Coroutines_Idle,
112 Coroutines_Starting,
113 Coroutines_Started,
114 Coroutines_Active,
115 Coroutines_Stopping
116};
117
118enum {
119 Chunk_Initial,
120 Chunk_Create,
121 Chunk_Enter
122};
123
124typedef enum Coroutine_State {
125 Coroutine_Constructing,
126 Coroutine_Free,
127 Coroutine_Idle,
128 Coroutine_Running,
129 Coroutine_Waiting,
130 Coroutine_Complete
131} Coroutine_State;
132
133enum {
134 Coroutines_Init,
135 Coroutines_AllocatedChunk,
136 Coroutines_CoroutineComplete,
137};
138
139struct Coroutine {
140 Coroutines *coroutines; // so can work with it off-thread
141 List_Link link; // for whichever list it's on
142 jmp_buf buf; // how to get back to it
143 unsigned char *guard; // where the stack overrun guard is
144 Coroutine_Start start; // entry point
145 void *entry_param; // to pass to start
146 void *value; // yielded/returned
147 Coroutine_State state;
148};
149
150struct Coroutines {
151 _Cor_Mutex mutex;
152 jmp_buf controller; // to return from Coroutine_Run
153 jmp_buf chunk_allocated;// for chunk allocation
154 unsigned char *guard; // the stack guard for the startup sequence
155
156 // singletons
157 Coroutine *tip; // top of stack chunk
158 Coroutine *active; // currently running coroutine
159 Coroutine *primary; // Coroutine_Run coroutine
160
161 // lists
162 List_Head free;
163 List_Head inactive; // idle or complete
164 List_Head runable; // running or waiting to run
165 List_Head waiting; // yielded / waiting to run
166 _Cor_Mutex waiting_mutex;
167
168 // Summary of the system
169 Coroutine_Report report;
170
171 // state
172 char state;
173};
174
175_Cor_thread_local Coroutines g_c;
176
177static void stack_chunk_chunk(Coroutine *parent);
178static void stack_chunk_base(Coroutine *parent, unsigned char *guard);
179
180
181// Check whether the guard is intact
182static inline bool Check_Guard(
183 unsigned char *guard
184){
185 return guard[0] == 0xde &&
186 guard[1] == 0xad &&
187 guard[2] == 0xbe &&
188 guard[3] == 0xef;
189}
190
191
192static void Coroutine_PrimeStackChunks(void)
193{
194 unsigned char chunk_of_stack[COROUTINE_STARTUP_STACK_SIZE];
195 for (uintptr_t i = 0; i < COROUTINE_STARTUP_STACK_SIZE-3; i += 4){
196 chunk_of_stack[i+0] = 0xde;
197 chunk_of_stack[i+1] = 0xad;
198 chunk_of_stack[i+2] = 0xbe;
199 chunk_of_stack[i+3] = 0xef;
200 }
201 assert(Check_Guard(chunk_of_stack));
202
203 // Stacks grow down in memory (almost always), so if the caller of this function changes
204 // the guard before entering the coroutine system, it has overrun the startup stack
205 g_c.guard = chunk_of_stack;
206
207 stack_chunk_base(NULL, NULL);
208}
209
210
211static void stack_chunk_chunk(
212 Coroutine *parent
213){
214 unsigned char chunk_of_stack[COROUTINE_STACK_SIZE];
215 for (uintptr_t i = 0; i < COROUTINE_STACK_SIZE-3; i += 4){
216 chunk_of_stack[i+0] = 0xde;
217 chunk_of_stack[i+1] = 0xad;
218 chunk_of_stack[i+2] = 0xbe;
219 chunk_of_stack[i+3] = 0xef;
220 }
221 stack_chunk_base(parent, chunk_of_stack);
222}
223
224
225static void stack_chunk_base(
226 Coroutine *parent,
227 unsigned char *guard
228){
229 Coroutine here;
230 here.state = Coroutine_Constructing;
231 switch (setjmp(here.buf)) {
232 case Chunk_Initial:
233 // got here for the first time
234 // parent now has a chunk_of_stack - add it to the free list
235 if (parent) {
236 assert(parent->state == Coroutine_Constructing);
237 assert(Check_Guard(guard));
238 parent->guard = guard;
239 parent->state = Coroutine_Free;
240 List_AddHead(&g_c.free, &parent->link);
241 g_c.report.coroutines_pool_size += 1;
242 }
243 // note that here is the tip of the chunk-claim stack
244 here.coroutines = &g_c;
245 g_c.tip = &here;
246
247 // return to the coroutine allocator
248 longjmp(g_c.chunk_allocated, 1);
249 case Chunk_Create:
250 // request to create a new chunk on the stack
251 assert(here.state == Coroutine_Constructing);
252 stack_chunk_chunk(&here);
253 assert(false);
254 case Chunk_Enter:
255 // request to start a coroutine (ie use the chunk for a coroutine)
256 // arrive here with mutex locked
257 assert(here.state == Coroutine_Running);
258 g_c.active = &here;
259 _Cor_Mutex_Unlock(&g_c.mutex);
260 here.value = here.start(here.entry_param);
261
262 // check the guard
263 assert(Check_Guard(here.guard));
264
265 _Cor_Mutex_Lock(&g_c.mutex);
266 g_c.active = NULL;
267 assert(here.state == Coroutine_Running);
268 List_Remove(&here.link);
269 here.state = Coroutine_Complete;
270 List_AddTail(&g_c.inactive, &here.link);
271 // coroutine has completed
272 if (g_c.primary == &here) {
273 // if primary coroutine - return to Coroutine_Run
274 longjmp(g_c.controller, Coroutines_CoroutineComplete);
275 }
276 _Cor_Mutex_Unlock(&g_c.mutex);
277 Coroutine_RunNext();
278 assert(false);
279 }
280}
281
282
283static void Coroutine_RunNext(void)
284{
285 // arrive here with mutex unlocked
286 _Cor_Mutex_Lock(&g_c.waiting_mutex);
287 _Cor_Mutex_Lock(&g_c.mutex);
288 Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c.runable));
289 assert(next->state == Coroutine_Running);
290 longjmp(next->buf, Chunk_Enter);
291 assert(false);
292}
293
294
295void Coroutine_StartSystem(void)
296{
297 assert(g_c.state == Coroutines_Idle);
298 g_c.state = Coroutines_Starting;
299
300 _Cor_Mutex_ctor(&g_c.mutex);
301
302 g_c.tip = NULL;
303 g_c.active = NULL;
304
305 List_Init(&g_c.free);
306 List_Init(&g_c.inactive);
307 List_Init(&g_c.runable);
308 List_Init(&g_c.waiting);
309 _Cor_Mutex_ctor(&g_c.waiting_mutex);
310 _Cor_Mutex_Lock(&g_c.waiting_mutex);
311
312 g_c.report.coroutines_created = 0;
313 g_c.report.coroutines_pool_size = 0;
314 g_c.report.lowest_headroom = COROUTINE_STACK_SIZE;
315
316 // prime the chunk system
317 if (!setjmp(g_c.chunk_allocated)){
318 Coroutine_PrimeStackChunks();
319 assert(false);
320 }
321
322 assert(g_c.state == Coroutines_Starting);
323 g_c.state = Coroutines_Started;
324}
325
326
327Coroutine_Report Coroutine_StopSystem(void)
328{
329 _Cor_Mutex_Lock(&g_c.mutex);
330 assert(g_c.state == Coroutines_Started);
331 g_c.state = Coroutines_Stopping;
332
333 uintptr_t stackminheadroom = COROUTINE_STACK_SIZE;
334 for (List_Link *link = g_c.free.fwd.link.next; link->next; link = link->next){
335 Coroutine *cor = List_Link_Container(Coroutine, link, link);
336 for (uintptr_t i = 4; i < COROUTINE_STACK_SIZE-3; i += 4){
337 if (!Check_Guard(&cor->guard[i])){
338 stackminheadroom = i < stackminheadroom ? i : stackminheadroom;
339 break;
340 }
341 }
342 }
343 g_c.report.lowest_headroom = stackminheadroom;
344
345 assert(List_IsEmpty(&g_c.inactive));
346 _Cor_Mutex_Unlock(&g_c.waiting_mutex);
347 _Cor_Mutex_dtor(&g_c.waiting_mutex);
348
349 assert(g_c.state == Coroutines_Stopping);
350 g_c.state = Coroutines_Idle;
351 _Cor_Mutex_Unlock(&g_c.mutex);
352 _Cor_Mutex_dtor(&g_c.mutex);
353
354 return g_c.report;
355}
356
357
358void Coroutine_Run_Coroutine(
359 Coroutine *cor,
360 void *value
361){
362 Coroutines *cors = cor->coroutines;
363 assert(&g_c == cors);
364 _Cor_Mutex_Lock(&cors->mutex);
365 assert(cors->state == Coroutines_Started);
366 cors->state = Coroutines_Active;
367 cors->primary = cor;
368
369 _Coroutine_Continue(cor, value, true);
370
371 if (!setjmp(cors->controller)){
372 _Cor_Mutex_Unlock(&cors->mutex);
373
374 // check the guard
375 assert(Check_Guard(cors->guard));
376
377 // start the first coroutine
378 Coroutine_RunNext();
379 }
380 // arrive here with mutex locked
381 assert(List_IsEmpty(&cors->runable));
382 assert(List_IsEmpty(&cors->waiting));
383 assert(cors->state == Coroutines_Active);
384 cors->state = Coroutines_Started;
385 _Cor_Mutex_Unlock(&cors->mutex);
386}
387
388
389void *Coroutine_Run(
390 Coroutine_Start start,
391 void *value
392){
393 Coroutine *cor = Coroutine_New(start);
394 Coroutine_Run_Coroutine(cor, value);
395 void *res = Coroutine_GetValue(cor);
396 Coroutine_Delete(cor);
397 return res;
398}
399
400
401Coroutine *Coroutine_New(
402 Coroutine_Start start
403){
404 assert((g_c.state == Coroutines_Started && List_IsEmpty(&g_c.inactive)) || g_c.state == Coroutines_Active);
405
406 // if none free - add one
407 if (List_IsEmpty(&g_c.free)){
408 if (!setjmp(g_c.chunk_allocated)){
409 longjmp(g_c.tip->buf, Chunk_Create);
410 }
411 }
412
413 Coroutine *cor = List_Link_Container(Coroutine, link, List_GetHead(&g_c.free));
414 assert(cor->state == Coroutine_Free);
415 cor->state = Coroutine_Idle;
416 cor->start = start;
417 cor->value = NULL;
418 List_Remove(&cor->link);
419 List_AddHead(&g_c.inactive, &cor->link);
420
421 g_c.report.coroutines_created += 1;
422
423 return cor;
424}
425
426
427void Coroutine_Delete(
428 Coroutine *cor
429){
430 Coroutines *cors = cor->coroutines;
431 _Cor_Mutex_Lock(&cors->mutex);
432 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Complete);
433 cor->state = Coroutine_Free;
434 List_Remove(&cor->link);
435 List_AddTail(&cors->free, &cor->link);
436 _Cor_Mutex_Unlock(&cors->mutex);
437}
438
439
440// Coroutine_Continue, assuming the mutex is claimed
441static void _Coroutine_Continue(
442 Coroutine *cor,
443 void *value,
444 bool early
445){
446 Coroutines *cors = cor->coroutines;
447 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Waiting);
448 cor->entry_param = value;
449 cor->state = Coroutine_Running;
450 List_Remove(&cor->link);
451 if ( early ) {
452 List_AddHead(&cors->runable, &cor->link);
453 } else {
454 List_AddTail(&cors->runable, &cor->link);
455 }
456 _Cor_Mutex_Unlock(&cors->waiting_mutex);
457}
458
459
460void Coroutine_Continue(
461 Coroutine *cor,
462 void *value,
463 bool early
464){
465 Coroutines *cors = cor->coroutines;
466 _Cor_Mutex_Lock(&cors->mutex);
467 _Coroutine_Continue(cor, value, early);
468 _Cor_Mutex_Unlock(&cors->mutex);
469}
470
471
472void *Coroutine_Yield(
473 void *value,
474 Coroutine_YieldCallback on_yield,
475 void *yield_me
476){
477 Coroutine *me = g_c.active;
478 assert(Check_Guard(me->guard));
479
480 _Cor_Mutex_Lock(&g_c.mutex);
481 Coroutines *cors = me->coroutines;
482 assert(me && me->state == Coroutine_Running && cors == &g_c);
483 me->value = value;
484 me->state = Coroutine_Waiting;
485
486 List_Remove(&me->link);
487 if (!List_IsEmpty(&cors->runable)){
488 _Cor_Mutex_Unlock(&cors->waiting_mutex);
489 }
490 List_AddTail(&cors->waiting, &me->link);
491
492 switch (setjmp(me->buf)){
493 case Chunk_Initial:
494 _Cor_Mutex_Unlock(&cors->mutex);
495 on_yield(yield_me);
496 Coroutine_RunNext();
497 case Chunk_Create:
498 assert(false);
499 case Chunk_Enter:
500 // arrive here with mutex locked
501 cors->active = me;
502 // when we return here - we are running again
503 assert(me->state == Coroutine_Running);
504 void *res = me->entry_param;
505 _Cor_Mutex_Unlock(&cors->mutex);
506 return res;
507 }
508 return NULL;
509}
510
511
512void *Coroutine_GetValue(
513 Coroutine *cor
514){
515 return cor->value;
516}
517
518
519Coroutine *Coroutine_GetActive(void)
520{
521 return g_c.active;
522}
523
524
525int Coroutine_GetStackHeadroom(void){
526 unsigned char tbuf[4];
527 return tbuf - g_c.active->guard - 4;
528}
529
530
531bool Coroutine_HasCoroutinesInFreePool(void){
532 return !List_IsEmpty(&g_c.free);
533}
534
535
536void *Coroutine_GetCStackTop(void){
537 return g_c.tip;
538}
539
540
541struct Coroutine_ChainParam {
542 Coroutine_Start start;
543 void *value;
544 Coroutine *ret;
545};
546
547
548static void *Coroutine_ChainFn(
549 void *param
550){
551 struct Coroutine_ChainParam *params = (struct Coroutine_ChainParam *)param;
552 Coroutine_Continue(params->ret, params->start(params->value), true);
553 return NULL;
554}
555
556
557static void Coroutine_ChainYield(
558 void *unused
559){
560 (void)unused;
561}
562
563
564void *Coroutine_Chain(
565 Coroutine_Start start,
566 void *value
567){
568 assert(Check_Guard(Coroutine_GetActive()->guard));
569 Coroutine *cor = Coroutine_New(Coroutine_ChainFn);
570 struct Coroutine_ChainParam params = {
571 start,
572 value,
573 Coroutine_GetActive()
574 };
575 Coroutine_Continue(cor, &params, true);
576 void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
577 Coroutine_Delete(cor);
578 return res;
579}
580
581
582bool Coroutine_IsRunning(
583 Coroutine *cor
584)
585{
586 int state = cor->state;
587 return state == Coroutine_Running || state == Coroutine_Waiting;
588}
589
590
591bool Coroutine_IsStarted(void){
592 return g_c.state == Coroutines_Active || g_c.state == Coroutines_Started;
593}
594