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