0 branches 0 tags
53
Check guard more often & fix bug with Coroutine freeing
jonroach 3 Nov 2025 14:24
1 contributor
654 lines16.9 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 Coroutine *cor = Coroutine_New(start);
404 Coroutine_Run_Coroutine(cor, value);
405 void *res = Coroutine_GetValue(cor);
406 Coroutine_Delete(cor);
407 return res;
408}
409
410
411Coroutine *Coroutine_New(
412 Coroutine_Start start
413){
414 assert((g_c.state == Coroutines_Started && List_IsEmpty(&g_c.inactive)) || g_c.state == Coroutines_Active);
415 assert(!g_c.active || Check_Guard(g_c.active->guard));
416
417 // if none free - add one
418 if (List_IsEmpty(&g_c.free)){
419 Coroutine *tip = g_c.tip;
420 if (!setjmp(g_c.chunk_allocated)){
421 longjmp(tip->buf, Chunk_Create);
422 }
423 if (g_c.report.stack_per_coroutine == 0){
424 g_c.report.stack_per_coroutine = (unsigned char *)tip - (unsigned char *)g_c.tip;
425 }
426 }
427
428 Coroutine *cor = List_Link_Container(Coroutine, link, List_GetHead(&g_c.free));
429 assert(cor->state == Coroutine_Free);
430 cor->state = Coroutine_Idle;
431 cor->start = start;
432 cor->value = NULL;
433 List_Remove(&cor->link);
434 List_AddHead(&g_c.inactive, &cor->link);
435
436 g_c.report.coroutines_created += 1;
437
438 return cor;
439}
440
441
442void Coroutine_Delete(
443 Coroutine *cor
444){
445 assert(!g_c.active || Check_Guard(g_c.active->guard));
446 Coroutines *cors = cor->coroutines;
447 _Cor_Mutex_Lock(&cors->mutex);
448 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Complete);
449 cor->state = Coroutine_Free;
450 List_Remove(&cor->link);
451 List_AddTail(&cors->free, &cor->link);
452 _Cor_Mutex_Unlock(&cors->mutex);
453}
454
455
456// Coroutine_Continue, assuming the mutex is claimed
457static void _Coroutine_Continue(
458 Coroutine *cor,
459 void *value,
460 bool early
461){
462 Coroutines *cors = cor->coroutines;
463 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Waiting);
464 cor->entry_param = value;
465 cor->state = Coroutine_Running;
466 List_Remove(&cor->link);
467 if ( early ) {
468 List_AddHead(&cors->runable, &cor->link);
469 } else {
470 List_AddTail(&cors->runable, &cor->link);
471 }
472 _Cor_Mutex_Unlock(&cors->waiting_mutex);
473}
474
475
476void Coroutine_Continue(
477 Coroutine *cor,
478 void *value,
479 bool early
480){
481 assert(!g_c.active || Check_Guard(g_c.active->guard));
482 Coroutines *cors = cor->coroutines;
483 _Cor_Mutex_Lock(&cors->mutex);
484 _Coroutine_Continue(cor, value, early);
485 _Cor_Mutex_Unlock(&cors->mutex);
486}
487
488
489void *Coroutine_Yield(
490 void *value,
491 Coroutine_YieldCallback on_yield,
492 void *yield_me
493){
494 Coroutine *me = g_c.active;
495 assert(Check_Guard(me->guard));
496
497 _Cor_Mutex_Lock(&g_c.mutex);
498 Coroutines *cors = me->coroutines;
499 assert(me && me->state == Coroutine_Running && cors == &g_c);
500 me->value = value;
501 me->state = Coroutine_Waiting;
502
503 List_Remove(&me->link);
504 if (!List_IsEmpty(&cors->runable)){
505 _Cor_Mutex_Unlock(&cors->waiting_mutex);
506 }
507 List_AddTail(&cors->waiting, &me->link);
508
509 switch (setjmp(me->buf)){
510 case Chunk_Initial:
511 _Cor_Mutex_Unlock(&cors->mutex);
512 on_yield(yield_me);
513 Coroutine_RunNext();
514 case Chunk_Create:
515 assert(false);
516 case Chunk_Enter:
517 // arrive here with mutex locked
518 cors->active = me;
519 assert(Check_Guard(me->guard));
520 // when we return here - we are running again
521 assert(me->state == Coroutine_Running);
522 void *res = me->entry_param;
523 _Cor_Mutex_Unlock(&cors->mutex);
524 return res;
525 }
526 return NULL;
527}
528
529
530void *Coroutine_GetValue(
531 Coroutine *cor
532){
533 return cor->value;
534}
535
536
537Coroutine *Coroutine_GetActive(void)
538{
539 return g_c.active;
540}
541
542
543intptr_t Coroutine_GetStackHeadroom(void){
544 unsigned char tbuf[4];
545 return g_c.active ? tbuf - g_c.active->guard - 4 : COROUTINE_STACK_SIZE;
546}
547
548
549// This is used to avoid compiler warnings about returning the address of a local
550static inline void *StopAddressWarnings(void *p)
551{
552 return p;
553}
554
555
556void *Coroutine_GetStackHWM(void){
557 assert(g_c.state == Coroutines_Active);
558 // Find where the guards end
559 unsigned char *guard;
560 for (guard = g_c.active->guard; Check_Guard(guard); guard += 4){
561 // do nothing
562 }
563 return guard;
564}
565
566
567void Coroutine_ClearStackForHWM(void){
568 assert(g_c.state == Coroutines_Active);
569 assert(Check_Guard(g_c.active->guard));
570 unsigned char *end = StackTopNow() - GUARD_PATTERN_SIZE;
571 for (unsigned char *guard = g_c.active->guard+GUARD_PATTERN_SIZE; guard <= end; guard += GUARD_PATTERN_SIZE){
572 Apply_Guard(guard);
573 }
574}
575
576
577bool Coroutine_CanStartCoroutine(void *stack_end){
578 assert(g_c.state == Coroutines_Active);
579 assert(Check_Guard(g_c.active->guard));
580 if (!List_IsEmpty(&g_c.free)){
581 return true;
582 }
583 uintptr_t overhead_per_coroutine = g_c.report.stack_per_coroutine-COROUTINE_STACK_SIZE;
584 intptr_t stack_available_for_new_coroutines = (char *)g_c.tip - (char *)stack_end - overhead_per_coroutine;
585 return stack_available_for_new_coroutines > (intptr_t)g_c.report.stack_per_coroutine;
586}
587
588
589void *Coroutine_GetCStackTop(void){
590 assert(!g_c.active || Check_Guard(g_c.active->guard));
591 return (g_c.state == Coroutines_Started || g_c.state == Coroutines_Active) ? (void *)g_c.tip : StackTopNow();
592}
593
594
595static void *StackTopNow(void){
596 unsigned char here[4];
597 return StopAddressWarnings(here);
598}
599
600
601struct Coroutine_ChainParam {
602 Coroutine_Start start;
603 void *value;
604 Coroutine *ret;
605};
606
607
608static void *Coroutine_ChainFn(
609 void *param
610){
611 struct Coroutine_ChainParam *params = (struct Coroutine_ChainParam *)param;
612 Coroutine_Continue(params->ret, params->start(params->value), true);
613 return NULL;
614}
615
616
617static void Coroutine_ChainYield(
618 void *unused
619){
620 (void)unused;
621}
622
623
624void *Coroutine_Chain(
625 Coroutine_Start start,
626 void *value
627){
628 assert(Check_Guard(Coroutine_GetActive()->guard));
629 Coroutine *cor = Coroutine_New(Coroutine_ChainFn);
630 struct Coroutine_ChainParam params = {
631 start,
632 value,
633 Coroutine_GetActive()
634 };
635 Coroutine_Continue(cor, &params, true);
636 void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
637 Coroutine_Delete(cor);
638 return res;
639}
640
641
642bool Coroutine_IsRunning(
643 Coroutine *cor
644)
645{
646 int state = cor->state;
647 return state == Coroutine_Running || state == Coroutine_Waiting;
648}
649
650
651bool Coroutine_IsStarted(void){
652 return g_c.state == Coroutines_Active || g_c.state == Coroutines_Started;
653}
654