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