0 branches 0 tags
60
Tidy up function declaratio
jonroach 18 Nov 2025 13:51
1 contributor
767 lines20.4 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(void);
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(void){
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 void
278){
279 Coroutine here;
280 here.state = Coroutine_Free;
281 here.guard = NULL;
282 here.coroutines = &g_c;
283 List_AddHead(&g_c.free, &here.link);
284 g_c.report.coroutines_pool_size += 1;
285 g_c.tip = &here;
286 for(;;){
287 switch (setjmp(here.buf)) {
288 case Chunk_Initial:
289 if (here.state == Coroutine_Free){
290 // return to the coroutine allocator
291 longjmp(g_c.chunk_allocated, 1);
292 } else {
293 assert(here.state == Coroutine_Complete);
294 // we finish here to ensure the setjmp is redone
295 if (g_c.primary == &here) {
296 // if primary coroutine - return to Coroutine_Run
297 longjmp(g_c.controller, Coroutines_CoroutineComplete);
298 }
299 _Cor_Mutex_Unlock(&g_c.mutex);
300 Coroutine_RunNext();
301 assert(false);
302 }
303 case Chunk_Create:
304 // Request to create a new chunk on the stack
305 // We're here if the coroutine is:
306 // Allocated, but not 'run' (Coroutine_Idle)
307 // Run, but not not entered yet (Coroutine_Running)
308 // Completed (Coroutine_Complete)
309 assert(here.state == Coroutine_Idle || here.state == Coroutine_Running || here.state == Coroutine_Complete);
310 unsigned char *ideal_limit = (unsigned char *)&here - COROUTINE_STACK_SIZE;
311 stack_chunk_chunk(&here, StackTopNow() - ideal_limit);
312 assert(false);
313 case Chunk_Enter:
314 // request to start a coroutine (ie use the chunk for a coroutine)
315 // arrive here with mutex locked
316 assert(here.state == Coroutine_Running);
317 g_c.active = &here;
318 _Cor_Mutex_Unlock(&g_c.mutex);
319 here.value = here.start(here.entry_param);
320
321 // check the guard
322 assert(Check_Guard(here.guard));
323
324 _Cor_Mutex_Lock(&g_c.mutex);
325 g_c.active = NULL;
326 assert(here.state == Coroutine_Running);
327 List_Remove(&here.link);
328 here.state = Coroutine_Complete;
329 List_AddTail(&g_c.inactive, &here.link);
330 // Coroutine has completed
331 // Loop round to redo the setjmp() - if this coroutine yielded, then the setjmp will
332 // need reseting
333 }
334 }
335}
336
337
338static void Coroutine_RunNext(void)
339{
340 // arrive here with mutex unlocked
341 _Cor_Mutex_Lock(&g_c.waiting_mutex);
342 _Cor_Mutex_Lock(&g_c.mutex);
343 Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c.runable));
344 assert(next->state == Coroutine_Running);
345 longjmp(next->buf, Chunk_Enter);
346 assert(false);
347}
348
349
350void Coroutine_StartSystem(void)
351{
352 assert(g_c.state == Coroutines_Idle);
353 g_c.state = Coroutines_Starting;
354
355 _Cor_Mutex_ctor(&g_c.mutex);
356
357 g_c.tip = NULL;
358 g_c.active = NULL;
359
360 List_Init(&g_c.free);
361 List_Init(&g_c.inactive);
362 List_Init(&g_c.runable);
363 List_Init(&g_c.waiting);
364 _Cor_Mutex_ctor(&g_c.waiting_mutex);
365 _Cor_Mutex_Lock(&g_c.waiting_mutex);
366
367 g_c.report.coroutines_created = 0;
368 g_c.report.coroutines_pool_size = 0;
369
370 // prime the chunk system
371 if (!setjmp(g_c.chunk_allocated)){
372 Coroutine_PrimeStackChunks();
373 assert(false);
374 }
375
376 assert(g_c.state == Coroutines_Starting);
377 g_c.state = Coroutines_Started;
378}
379
380
381void Coroutine_SetStackLimit(void *limit){
382 assert(!limit || (unsigned char *)limit < (unsigned char *)g_c.tip);
383 g_c.stack_limit = limit;
384}
385
386
387Coroutine_Report Coroutine_StopSystem(void)
388{
389 _Cor_Mutex_Lock(&g_c.mutex);
390 assert(g_c.state == Coroutines_Started);
391 g_c.state = Coroutines_Stopping;
392
393 uintptr_t stackminheadroom;;
394#if COROUTINE_RECORD_LOWEST_HEADROOM
395 stackminheadroom = COROUTINE_STACK_SIZE;
396 for (List_Link *link = g_c.free.fwd.link.next; link->next; link = link->next){
397 Coroutine *cor = List_Link_Container(Coroutine, link, link);
398 if (cor->guard){
399 for (uintptr_t i = 4; i < COROUTINE_STACK_SIZE-3; i += 4){
400 if (!Check_Guard(&cor->guard[i])){
401 stackminheadroom = i < stackminheadroom ? i : stackminheadroom;
402 break;
403 }
404 }
405 }
406 }
407#else
408 stackminheadroom = 0;
409#endif
410 g_c.report.lowest_headroom = stackminheadroom;
411
412 assert(List_IsEmpty(&g_c.inactive));
413 _Cor_Mutex_Unlock(&g_c.waiting_mutex);
414 _Cor_Mutex_dtor(&g_c.waiting_mutex);
415
416 assert(g_c.state == Coroutines_Stopping);
417 g_c.state = Coroutines_Idle;
418 _Cor_Mutex_Unlock(&g_c.mutex);
419 _Cor_Mutex_dtor(&g_c.mutex);
420
421 return g_c.report;
422}
423
424
425void Coroutine_Run_Coroutine(
426 Coroutine *cor,
427 void *value
428){
429 Coroutines *cors = cor->coroutines;
430 assert(&g_c == cors);
431 _Cor_Mutex_Lock(&cors->mutex);
432 assert(cors->state == Coroutines_Started);
433 cors->state = Coroutines_Active;
434 cors->primary = cor;
435
436 _Coroutine_Continue(cor, value, true);
437
438 if (!setjmp(cors->controller)){
439 _Cor_Mutex_Unlock(&cors->mutex);
440
441 // check the guard
442 assert(Check_Guard(cors->guard));
443
444 // start the first coroutine
445 Coroutine_RunNext();
446 }
447 // arrive here with mutex locked
448 assert(List_IsEmpty(&cors->runable));
449 assert(List_IsEmpty(&cors->waiting));
450 assert(cors->state == Coroutines_Active);
451 cors->state = Coroutines_Started;
452 _Cor_Mutex_Unlock(&cors->mutex);
453}
454
455
456void *Coroutine_Run(
457 Coroutine_Start start,
458 void *value
459){
460 if (g_c.active){
461 return start(value);
462 }
463 assert(g_c.state == Coroutines_Idle || g_c.state == Coroutines_Started);
464 bool need_start = g_c.state == Coroutines_Idle;
465 if (need_start){
466 Coroutine_StartSystem();
467 }
468 Coroutine *cor = Coroutine_New(start);
469 Coroutine_Run_Coroutine(cor, value);
470 void *res = Coroutine_GetValue(cor);
471 Coroutine_Delete(cor);
472 if (need_start){
473 Coroutine_StopSystem();
474 }
475 return res;
476}
477
478
479Coroutine *Coroutine_New(
480 Coroutine_Start start
481){
482 assert((g_c.state == Coroutines_Started && List_IsEmpty(&g_c.inactive)) || g_c.state == Coroutines_Active);
483 assert(Coroutine_StackHasNotOverrun());
484 assert(Coroutine_CanStartCoroutine());
485
486 // if none free - add one
487 if (List_IsEmpty(&g_c.free)){
488 Coroutine *tip = g_c.tip;
489 Coroutine *me = g_c.active;
490 if (tip == me) {
491 if (!setjmp(g_c.chunk_allocated)){
492 unsigned char *ideal_limit = (unsigned char *)me - COROUTINE_STACK_SIZE;
493 stack_chunk_chunk(me, StackTopNow() - ideal_limit);
494 }
495 } else {
496 if (!setjmp(g_c.chunk_allocated)){
497 longjmp(tip->buf, Chunk_Create);
498 }
499 }
500 }
501
502 Coroutine *cor = List_Link_Container(Coroutine, link, List_GetHead(&g_c.free));
503 assert(cor->state == Coroutine_Free);
504 cor->state = Coroutine_Idle;
505 cor->start = start;
506 cor->value = NULL;
507 List_Remove(&cor->link);
508 List_AddHead(&g_c.inactive, &cor->link);
509
510 g_c.report.coroutines_created += 1;
511
512 return cor;
513}
514
515
516void Coroutine_Delete(
517 Coroutine *cor
518){
519 assert(Coroutine_StackHasNotOverrun());
520 Coroutines *cors = cor->coroutines;
521 _Cor_Mutex_Lock(&cors->mutex);
522 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Complete);
523 cor->state = Coroutine_Free;
524 List_Remove(&cor->link);
525 List_AddTail(&cors->free, &cor->link);
526 _Cor_Mutex_Unlock(&cors->mutex);
527}
528
529
530// Coroutine_Continue, assuming the mutex is claimed
531static void _Coroutine_Continue(
532 Coroutine *cor,
533 void *value,
534 bool early
535){
536 Coroutines *cors = cor->coroutines;
537 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Waiting);
538 cor->entry_param = value;
539 cor->state = Coroutine_Running;
540 List_Remove(&cor->link);
541 if ( early ) {
542 List_AddHead(&cors->runable, &cor->link);
543 } else {
544 List_AddTail(&cors->runable, &cor->link);
545 }
546 _Cor_Mutex_Unlock(&cors->waiting_mutex);
547}
548
549
550void Coroutine_Continue(
551 Coroutine *cor,
552 void *value,
553 bool early
554){
555 assert(Coroutine_StackHasNotOverrun());
556 Coroutines *cors = cor->coroutines;
557 _Cor_Mutex_Lock(&cors->mutex);
558 _Coroutine_Continue(cor, value, early);
559 _Cor_Mutex_Unlock(&cors->mutex);
560}
561
562
563void *Coroutine_Yield(
564 void *value,
565 Coroutine_YieldCallback on_yield,
566 void *yield_me
567){
568 Coroutine *me = g_c.active;
569 assert(me);
570 assert(Coroutine_StackHasNotOverrun());
571
572 _Cor_Mutex_Lock(&g_c.mutex);
573 Coroutines *cors = me->coroutines;
574 assert(me && me->state == Coroutine_Running && cors == &g_c);
575 me->stack_top = StackTopNow();
576 me->value = value;
577 me->state = Coroutine_Waiting;
578
579 List_Remove(&me->link);
580 if (!List_IsEmpty(&cors->runable)){
581 _Cor_Mutex_Unlock(&cors->waiting_mutex);
582 }
583 List_AddTail(&cors->waiting, &me->link);
584
585 switch (setjmp(me->buf)){
586 case Chunk_Initial:
587 _Cor_Mutex_Unlock(&cors->mutex);
588 on_yield(yield_me);
589 Coroutine_RunNext();
590 assert(false);
591 case Chunk_Create:
592 assert(me == g_c.tip);
593 unsigned char *ideal_limit = (unsigned char *)me - COROUTINE_STACK_SIZE;
594 stack_chunk_chunk(me, me->stack_top - ideal_limit);
595 assert(false);
596 case Chunk_Enter:
597 // arrive here with mutex locked
598 cors->active = me;
599 assert(Coroutine_StackHasNotOverrun());
600 // when we return here - we are running again
601 assert(me->state == Coroutine_Running);
602 void *res = me->entry_param;
603 _Cor_Mutex_Unlock(&cors->mutex);
604 return res;
605 }
606 return NULL;
607}
608
609
610void *Coroutine_GetValue(
611 Coroutine *cor
612){
613 return cor->value;
614}
615
616
617Coroutine *Coroutine_GetActive(void)
618{
619 return g_c.active;
620}
621
622
623intptr_t Coroutine_GetStackHeadroom(void){
624 assert(Coroutine_StackHasNotOverrun());
625 Coroutine *me = g_c.active;
626 if (!me){
627 // no active coroutine
628 unsigned char *stack_limit = g_c.stack_limit;
629 if (stack_limit){
630 // no stack limit - assume we'll use COROUTINE_STACK_SIZE
631 return StackTopNow() - stack_limit;
632 } else {
633 // no information where the stack ends - return something
634 return COROUTINE_STACK_SIZE;
635 }
636 }
637 unsigned char *stack_top = StackTopNow();
638 if (me->guard){
639 // guard established - that's where we'll measure to
640 return stack_top - me->guard;
641 }
642 intptr_t used = (unsigned char *)me - stack_top;
643 unsigned char *stack_limit = g_c.stack_limit;
644 if (!stack_limit){
645 // no stack limit - assume we'll use COROUTINE_STACK_SIZE
646 return COROUTINE_STACK_SIZE - used;
647 }
648 intptr_t available = (unsigned char *)me - stack_limit;
649 if (available < 2*COROUTINE_STACK_SIZE){
650 // can't start another coroutine, so whatever's left in the C stack is what we've got
651 return available - used;
652 }
653 // can start another coroutine, so limit ourselves to a coroutine stack size's worth
654 return COROUTINE_STACK_SIZE - used;
655}
656
657
658// This is used to avoid compiler warnings about returning the address of a local
659static inline void *StopAddressWarnings(void *p)
660{
661 return p;
662}
663
664
665void *Coroutine_GetStackHWM(void){
666 assert(g_c.state == Coroutines_Active);
667 assert(Coroutine_StackHasNotOverrun());
668 // Find where the guards end
669 unsigned char *guard;
670 for (guard = g_c.active->guard; Check_Guard(guard); guard += 4){
671 // do nothing
672 }
673 return guard;
674}
675
676
677void Coroutine_ClearStackForHWM(void){
678 assert(g_c.state == Coroutines_Active);
679 assert(Coroutine_StackHasNotOverrun());
680 unsigned char *end = StackTopNow() - GUARD_PATTERN_SIZE;
681 for (unsigned char *guard = g_c.active->guard+GUARD_PATTERN_SIZE; guard <= end; guard += GUARD_PATTERN_SIZE){
682 Apply_Guard(guard);
683 }
684}
685
686
687bool Coroutine_CanStartCoroutine(){
688 assert(g_c.state == Coroutines_Started || g_c.state == Coroutines_Active);
689 assert(Coroutine_StackHasNotOverrun());
690 if (!List_IsEmpty(&g_c.free)){
691 return true;
692 }
693
694 return !g_c.stack_limit || g_c.stack_limit <= (unsigned char *)g_c.tip - 2*COROUTINE_STACK_SIZE;
695}
696
697
698void *Coroutine_GetCStackTop(void){
699 assert(Coroutine_StackHasNotOverrun());
700 if ((g_c.state == Coroutines_Started || g_c.state == Coroutines_Active) && g_c.tip != g_c.active) {
701 return g_c.tip->stack_top;
702 } else {
703 return StackTopNow();
704 }
705}
706
707
708static unsigned char *StackTopNow(void){
709 unsigned char here[4];
710 return StopAddressWarnings(here);
711}
712
713
714struct Coroutine_ChainParam {
715 Coroutine_Start start;
716 void *value;
717 Coroutine *ret;
718};
719
720
721static void *Coroutine_ChainFn(
722 void *param
723){
724 struct Coroutine_ChainParam *params = (struct Coroutine_ChainParam *)param;
725 Coroutine_Continue(params->ret, params->start(params->value), true);
726 return NULL;
727}
728
729
730static void Coroutine_ChainYield(
731 void *unused
732){
733 (void)unused;
734}
735
736
737void *Coroutine_Chain(
738 Coroutine_Start start,
739 void *value
740){
741 assert(Check_Guard(Coroutine_GetActive()->guard));
742 Coroutine *cor = Coroutine_New(Coroutine_ChainFn);
743 struct Coroutine_ChainParam params = {
744 start,
745 value,
746 Coroutine_GetActive()
747 };
748 Coroutine_Continue(cor, &params, true);
749 void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
750 Coroutine_Delete(cor);
751 return res;
752}
753
754
755bool Coroutine_IsRunning(
756 Coroutine *cor
757)
758{
759 int state = cor->state;
760 return state == Coroutine_Running || state == Coroutine_Waiting;
761}
762
763
764bool Coroutine_IsStarted(void){
765 return g_c.state == Coroutines_Active || g_c.state == Coroutines_Started;
766}
767