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