0 branches 0 tags
96
Define convenience names for the namespace names to help code clarity
jonroach 15 Jun 2026 16:44
1 contributor
1588 lines39.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#include "coroutine_names_def.h"
11
12// see CPython again, this time from ctypes.h
13#if (defined (__SVR4) && defined (__sun)) || defined(COROUTINE_HAVE_ALLOCA_H)
14# include <alloca.h>
15#elif defined(MS_WIN32)
16# include <malloc.h>
17#endif
18
19/* If the system does not define alloca(), we have to hope for a compiler builtin. */
20#ifndef alloca
21# if defined __GNUC__ || (__clang_major__ >= 4)
22# define alloca __builtin_alloca
23# else
24# error "Could not define alloca() on your platform."
25# endif
26#endif
27
28typedef struct Coroutines Coroutines;
29
30static void Coroutine_RunNext(void);
31static Coroutine_Err Coroutine_Continue_(Coroutines *cors, Coroutine *cor, void *value, bool early);
32static uintptr_t StackTopNow(void);
33
34#ifndef NDEBUG
35 // In debug builds, use the built-in assert
36 #define MyAssert assert
37#else
38 #if 1
39 // In non-debug builds, normally use this - all the asserts are disabled
40 #define MyAssert(cond)
41 #else
42 // In non-debug builds with stack problems, you can use this.
43 // This activates all the asserts, and gives a line to put a
44 // breakpoint in your debugger.
45 static void _MyAssert(bool cond, char const *msg)
46 {
47 if (!cond){
48 fputs("Assertion failed: ", stdout);
49 fputs(msg, stdout);
50 fputs("\n", stdout);
51 }
52 }
53 #define MyAssert(cond) _MyAssert(cond, #cond)
54 #endif
55#endif
56
57static inline ptrdiff_t
58StackPointerDiff
59(
60 unsigned char *a,
61 unsigned char *b
62){
63#if COROUTINE_STACK_GROWS_UP
64 return a - b;
65#else
66 return b - a;
67#endif
68}
69
70static inline unsigned char *
71StackPointerAdd
72(
73 unsigned char *a,
74 ptrdiff_t b
75){
76#if COROUTINE_STACK_GROWS_UP
77 return a + b;
78#else
79 return a - b;
80#endif
81}
82
83// Unused...
84// static inline unsigned char *
85// StackBaseEnd
86// (
87// unsigned char *memlo,
88// unsigned char *memhi
89// ){
90// #if COROUTINE_STACK_GROWS_UP
91// (void)memhi;
92// return memlo;
93// #else
94// (void)memlo;
95// return memhi-1;
96// #endif
97// }
98// ...unused
99
100static inline unsigned char *
101StackLimitEnd
102(
103 unsigned char *memlo,
104 unsigned char *memhi
105){
106#if COROUTINE_STACK_GROWS_UP
107 (void)memlo;
108 return memhi;
109#else
110 (void)memhi;
111 return memlo-1;
112#endif
113}
114
115#define CHECK_SYSTEM_RUNNING \
116 if (!g_c){ \
117 return Coroutine_Err_SystemNotRunning; \
118 }
119#define CHECK_SYSTEM_NOT_RUNNING \
120 if (g_c){ \
121 return Coroutine_Err_SystemRunning; \
122 }
123#define CHECK_COROUTINE_THREAD \
124 if (cor->coroutines != g_c){ \
125 return Coroutine_Err_CoroutineFromWrongThread; \
126 }
127#define CHECK_NO_COROUTINE_RUNNING \
128 if (g_c->state != Coroutines_Started){ \
129 return Coroutine_Err_ACoroutineIsAlreadyRunning; \
130 }
131#define CHECK_STACK_OVERRUN \
132 { \
133 Coroutine_Err err = Coroutine_StackHasOverrun(); \
134 if (err){ \
135 return err; \
136 } \
137 } while (0);
138
139
140static inline void ready_jmp_buf(jmp_buf buf) {
141#if defined(_M_X64) || defined(_M_ARM64)
142 // Win64:
143 // Set Frame to 0 on Windows 64 bit to prevent C++ stack unwinding in longjmp().
144 // Win32:
145 // Doesn't do this, so only needed on the 2 64 bit Windows versions
146 ((_JUMP_BUFFER*)buf)->Frame = 0;
147#else
148 (void)buf;
149#endif
150}
151
152///////////////////////////////////////////////////////////////////////////////
153// 2-way linked lists...
154//
155// Brought inline here to avoid namespace polution
156///////////////////////////////////////////////////////////////////////////////
157
158typedef struct List_Link List_Link;
159struct List_Link {
160 List_Link *next;
161 List_Link *prev;
162};
163
164typedef struct List_Head List_Head;
165struct List_Head {
166 union {
167 struct {
168 List_Link link;
169 List_Link *filler;
170 } fwd;
171 struct {
172 List_Link *filler;
173 List_Link link;
174 } back;
175 };
176};
177
178
179static inline bool List_IsEmpty(
180 const List_Head *list
181){
182 return list->fwd.link.next == &list->back.link;
183}
184
185
186static inline List_Link *List_GetHead(
187 const List_Head *list
188){
189 return List_IsEmpty(list) ? NULL : list->fwd.link.next;
190}
191
192
193static inline List_Link *List_Begin(
194 const List_Head *list
195){
196 return list->fwd.link.next;
197}
198
199
200static inline bool Link_NextIsLink(
201 const List_Link *link
202){
203 return link->next != NULL;
204}
205
206
207static inline List_Link *Link_Next(
208 List_Link *link
209){
210 return link->next;
211}
212
213
214static inline bool Link_PrevIsLink(
215 const List_Link *link
216){
217 return link->prev != NULL;
218}
219
220
221static inline List_Link *Link_Prev(
222 List_Link *link
223){
224 return link->prev;
225}
226
227// Unused...
228// static inline List_Link *List_GetTail(
229// const List_Head *list
230// ){
231// return List_IsEmpty(list) ? NULL : list->back.link.prev;
232// }
233// ...unused
234
235
236#define OFFSETOF(Container, Field) ((char *)&((Container *)4)->Field - (char *)(Container *)4)
237#define List_Link_Container(Container, Link, link) ((Container *)((char *)(link) - OFFSETOF(Container, Link)))
238
239
240static inline void
241List_Init(
242 List_Head *list
243){
244 list->fwd.link.next = &list->back.link;
245 list->fwd.link.prev = NULL;
246 list->back.link.prev = &list->fwd.link;
247}
248
249
250static inline void
251Link_AddAfter(
252 List_Link *link,
253 List_Link *after
254){
255 link->next = after->next;
256 link->prev = after;
257 after->next->prev = link;
258 after->next = link;
259}
260
261
262static inline void
263List_AddHead(
264 List_Head *list,
265 List_Link *link
266){
267 Link_AddAfter(link, &list->fwd.link);
268}
269
270
271static inline void
272Link_AddBefore(
273 List_Link *link,
274 List_Link *before
275){
276 link->prev = before->prev;
277 link->next = before;
278 before->prev->next = link;
279 before->prev = link;
280}
281
282
283static inline void
284List_AddTail(
285 List_Head *list,
286 List_Link *link
287){
288 Link_AddBefore(link, &list->back.link);
289}
290
291
292static inline void
293Link_Remove(
294 List_Link *link
295){
296 link->prev->next = link->next;
297 link->next->prev = link->prev;
298}
299
300///////////////////////////////////////////////////////////////////////////////
301// ...2-way linked lists
302///////////////////////////////////////////////////////////////////////////////
303
304enum {
305 Coroutines_Started,
306 Coroutines_Stopping
307};
308
309enum {
310 Chunk_Initial,
311 Chunk_Split,
312 Chunk_Enter
313};
314
315typedef enum Coroutine_State {
316 Coroutine_Free,
317 Coroutine_Idle,
318 Coroutine_Running,
319 Coroutine_Waiting,
320 Coroutine_Complete
321} Coroutine_State;
322
323enum {
324 Coroutines_Init,
325 Coroutines_AllocatedChunk,
326 Coroutines_CoroutineComplete,
327};
328
329struct Coroutine {
330 size_t min_size;
331 size_t min_headroom;
332 Coroutines *coroutines; // so can work with it off-thread
333 List_Link link; // for whichever list it's on
334 List_Link all_link; // list of all Coroutines
335 jmp_buf buf; // how to get back to it
336 unsigned char *base; // where the base of this Coroutine's stack is (= previous block's limit)
337 unsigned char *limit; // where the limit of this Coroutine's stack is (= next block's base)
338 unsigned char *guard; // where the stack overrun guard is
339 Coroutine_Start start; // entry point
340 void *entry_param; // to pass to start
341 void *value; // yielded/returned
342 unsigned char *stack_top; // recorded at yield
343 Coroutine_State state;
344
345 int sequence;
346};
347
348struct Coroutines {
349 _Cor_Mutex mutex;
350 jmp_buf controller; // to return from Coroutine_Run
351 jmp_buf chunk_allocated;// for chunk allocation
352 size_t size_to_retain; // for Chunk_Split
353
354 // singletons
355 Coroutine *tip; // top of stack chunk
356 Coroutine *active; // currently running coroutine
357 Coroutine *primary; // Coroutine_Run coroutine
358 unsigned char *stack_limit; // when not NULL, where the stack finishes
359
360 Coroutine *spare; // spare struct Coroutine (instead of having to malloc & fail)
361
362 // lists
363 List_Head all; // all Coroutines (in address order)
364 List_Head free; // free Coroutines
365 List_Head inactive; // idle or complete
366 List_Head runable; // running or waiting to run
367 List_Head waiting; // yielded / waiting to run
368 _Cor_Mutex waiting_mutex;
369
370 Coroutine *root; // The coroutine for the thread which started Coroutines
371
372 // Summary of the system
373 Coroutine_Report report;
374
375 // state
376 char state;
377
378 int sequence;
379};
380
381_Cor_thread_local Coroutines *g_c;
382_Cor_thread_local unsigned char *g_stack_limit;
383
384static void ReserveStackSpace(Coroutines *cors, Coroutine *parent, size_t chunk_size, unsigned char *childs_limit);
385static void stack_chunk_base(Coroutines *cors, Coroutine *parent, unsigned char *prev_limit, unsigned char *limit);
386
387
388static size_t
389Coroutine_Size
390(
391 Coroutine *cor
392){
393 if (cor->limit){
394 return (size_t)StackPointerDiff(cor->limit, cor->base);
395 } else {
396 return SIZE_MAX;
397 }
398}
399
400
401static size_t
402TrimmableSize(
403 Coroutine *cor
404){
405 size_t current_used = StackPointerDiff(cor->stack_top, cor->base);
406 size_t min_size = current_used + cor->min_headroom;
407 if (min_size < cor->min_size){
408 min_size = cor->min_size;
409 }
410
411 if (cor->limit){
412 if (Coroutine_Size(cor) < min_size + COROUTINE_MINIMUM_STACK_SIZE){
413 return 0;
414 }
415 }
416 return min_size;
417}
418
419
420#define GUARD_PATTERN_SIZE (4)
421/// @brief Checks whether a guard pattern is OK
422/// @param guard The address of the stack base end of the pattern
423/// @return true pattern is ok; false pattern is broken
424static inline bool
425Guard_Pattern_OK(
426 unsigned char *guard
427){
428 return !guard ||
429 (*StackPointerAdd(guard, 0) == 0xde &&
430 *StackPointerAdd(guard, 1) == 0xad &&
431 *StackPointerAdd(guard, 2) == 0xbe &&
432 *StackPointerAdd(guard, 3) == 0xef);
433}
434
435
436/// @brief Writes a guard pattern
437/// @param guard Where to write the guard pattern (stack base end)
438static inline void
439Apply_Guard(unsigned char *guard){
440 *StackPointerAdd(guard, 0) = 0xde;
441 *StackPointerAdd(guard, 1) = 0xad;
442 *StackPointerAdd(guard, 2) = 0xbe;
443 *StackPointerAdd(guard, 3) = 0xef;
444}
445
446
447#ifndef NDEBUG
448/// @brief Checks a list of Coroutines to see whether it's OK
449/// @param head The list to check
450/// @param state1 One of the states Coroutines in the list are allowed
451/// @param state2 One of the states Coroutines in the list are allowed
452/// @return Coroutine_OK the is OK; other the list is broken
453static Coroutine_Err
454CheckListIntegrity(
455 List_Head *head,
456 Coroutine_State state1,
457 Coroutine_State state2
458){
459 for (List_Link *link = List_Begin(head); Link_NextIsLink(link); link = Link_Next(link)){
460 Coroutine *candidate = List_Link_Container(Coroutine, link, link);
461 if (candidate->coroutines != g_c){
462 return Coroutine_Err_InternalInsistency;
463 }
464 if(candidate->state != state1 && candidate->state != state2){
465 return Coroutine_Err_InternalInsistency;
466 }
467 bool found = false;
468 for (List_Link *link = List_Begin(&g_c->all); Link_NextIsLink(link); link = Link_Next(link)){
469 Coroutine *candidate2 = List_Link_Container(Coroutine, all_link, link);
470 if (candidate == candidate2){
471 found = true;
472 }
473 }
474 if (!found){
475 return Coroutine_Err_InternalInsistency;
476 }
477 }
478 return Coroutine_OK;
479}
480
481
482/// @brief Check the integrity of this thread's coroutine system
483/// @return Coroutine_OK everything's OK; other something was wrong
484static Coroutine_Err
485Coroutine_CheckIntegrity_(
486 void
487){
488 Coroutine_Err err;
489 err = CheckListIntegrity(&g_c->free, Coroutine_Free, Coroutine_Free);
490 if (err){
491 return err;
492 }
493 err = CheckListIntegrity(&g_c->inactive, Coroutine_Idle, Coroutine_Complete);
494 if (err){
495 return err;
496 }
497 err = CheckListIntegrity(&g_c->runable, Coroutine_Running, Coroutine_Running);
498 if (err){
499 return err;
500 }
501 err = CheckListIntegrity(&g_c->waiting, Coroutine_Waiting, Coroutine_Waiting);
502 return err;
503}
504#endif
505
506
507/// @brief Check whether the stack has overrun
508/// @return Coroutine_OK the stack hasn't; other it has
509static Coroutine_Err
510Coroutine_StackHasOverrun(
511 void
512){
513 unsigned char *stack_top = (unsigned char *)StackTopNow();
514 unsigned char *stack_limit = g_c ? g_c->stack_limit : NULL;
515 if (stack_limit && StackPointerDiff(stack_limit, stack_top) < 0){
516 // current stack top is beyond limit - we are overrunning NOW
517 return Coroutine_Err_StackOverrun;
518 }
519 Coroutine *me = g_c ? g_c->active : NULL;
520 if (!me){
521 return Coroutine_OK;
522 }
523#if COROUTINE_CHECK_INTEGRITY_ON_STACK_CHECK
524 // Check all coroutines integrity
525 Coroutine_Err err = Coroutine_CheckIntegrity_();
526 if (err){
527 return err;
528 }
529#endif
530 if (me->guard){
531 if (StackPointerDiff(me->guard, stack_top) < 0){
532 // Stack top beyond active stack limit
533 return Coroutine_Err_StackOverrun;
534 }
535 if (!Guard_Pattern_OK(me->guard)){
536 // Guard pattern trampled
537 return Coroutine_Err_StackOverrun;
538 }
539 }
540 return Coroutine_OK;
541}
542
543#ifndef NDEBUG
544/// @brief Check system integrity - does stack overrun check and internals check
545/// @return Coroutine_OK all is OK; other something was wrong
546Coroutine_Err
547Coroutine_CheckIntegrity(
548 void
549){
550 Coroutine_Err err = Coroutine_StackHasOverrun();
551#if !COROUTINE_CHECK_INTEGRITY_ON_STACK_CHECK
552 if (!err && g_c){
553 err = Coroutine_CheckIntegrity_();
554 }
555#endif
556 return err;
557}
558#endif
559
560
561static void
562ReserveStackSpace(
563 Coroutines *cors,
564 Coroutine *parent,
565 size_t chunk_size,
566 unsigned char *childs_limit
567){
568 unsigned char *chunk_of_stack = alloca(chunk_size);
569 unsigned char *limit = StackLimitEnd(chunk_of_stack, chunk_of_stack+chunk_size);
570 unsigned char *guard = StackPointerAdd(limit, -GUARD_PATTERN_SIZE);
571#if COROUTINE_RECORD_LOWEST_HEADROOM
572 for (size_t i = 0; i <= chunk_size-GUARD_PATTERN_SIZE; i += GUARD_PATTERN_SIZE){
573 Apply_Guard(StackPointerAdd(guard, -i));
574 }
575#else
576 Apply_Guard(guard);
577#endif
578 if (parent){
579 parent->limit = limit;
580 parent->guard = guard;
581 }
582 stack_chunk_base(cors, parent, limit, childs_limit);
583}
584
585
586static void
587stack_chunk_base(
588 Coroutines *cors,
589 Coroutine *parent,
590 unsigned char *prev_limit,
591 unsigned char *limit
592){
593 MyAssert(cors->spare);
594 Coroutine *here = cors->spare;
595 cors->spare = NULL;
596 here->coroutines = cors;
597 here->sequence = cors->sequence++;
598 here->state = Coroutine_Free;
599 here->base = prev_limit;
600 here->limit = limit;
601 here->stack_top = (unsigned char *)StackTopNow();
602 if (limit){
603 here->guard = StackPointerAdd(limit, -GUARD_PATTERN_SIZE);
604 Apply_Guard(limit);
605 } else {
606 here->guard = NULL;
607 }
608
609 // insert into all list
610 if (parent){
611 Link_AddAfter(&here->all_link, &parent->all_link);
612 } else {
613 List_AddHead(&cors->all, &here->all_link);
614 }
615 // add to free list
616 List_AddTail(&cors->free, &here->link);
617
618 cors->report.coroutines_pool_size += 1;
619
620 if (!cors->tip || !Link_NextIsLink(Link_Next(&here->all_link))){
621 cors->tip = here;
622 }
623
624 for(;;){
625 switch (setjmp(here->buf)) {
626 case Chunk_Initial:
627 ready_jmp_buf(here->buf);
628 if (here->state == Coroutine_Free){
629 // return to the coroutine allocator
630 longjmp(cors->chunk_allocated, 1);
631 } else {
632 MyAssert(here->state == Coroutine_Complete);
633 // we finish here to ensure the setjmp is redone
634 if (cors->primary == here) {
635 // if primary coroutine - return to Coroutine_Run
636 longjmp(cors->controller, Coroutines_CoroutineComplete);
637 }
638 _Cor_Mutex_Unlock(&cors->mutex);
639 Coroutine_RunNext();
640 }
641 MyAssert(false);
642 break;
643 case Chunk_Split:
644 // Request to split this idle block into two
645 // g_c->size_to_retain will be set to our shorter size
646 ReserveStackSpace(here->coroutines, here, g_c->size_to_retain, here->limit);
647 MyAssert(false);
648 break;
649 case Chunk_Enter:
650 // request to start a coroutine (ie use the chunk for a coroutine)
651 // arrive here with mutex locked
652 MyAssert(here->state == Coroutine_Running);
653 here->coroutines->active = here;
654 _Cor_Mutex_Unlock(&cors->mutex);
655 here->value = here->start(here->entry_param);
656
657 // check the guard
658 MyAssert(Guard_Pattern_OK(here->guard));
659
660 here->stack_top = (unsigned char *)StackTopNow();
661 _Cor_Mutex_Lock(&here->coroutines->mutex);
662 here->coroutines->active = NULL;
663 MyAssert(here->state == Coroutine_Running);
664 Link_Remove(&here->link);
665 here->state = Coroutine_Complete;
666 List_AddTail(&here->coroutines->inactive, &here->link);
667 // Coroutine has completed
668 // Loop round to redo the setjmp() - if this coroutine yielded, then the setjmp will
669 // need reseting
670 break;
671 }
672 }
673}
674
675
676static void
677Coroutine_RunNext(
678 void
679){
680 // arrive here with mutex unlocked
681 _Cor_Mutex_Lock(&g_c->waiting_mutex);
682 _Cor_Mutex_Lock(&g_c->mutex);
683 Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c->runable));
684 MyAssert(next->state == Coroutine_Running);
685 longjmp(next->buf, Chunk_Enter);
686 MyAssert(false);
687}
688
689
690/// @brief Ensures there's a spare Coroutine for cors
691/// @param cors The Coroutines to ensure a spare for
692/// @return true there is a spare; false there isn't
693static inline bool
694EnsureSpare
695(
696 Coroutines *cors
697){
698 if (cors->spare){
699 return true;
700 }
701 cors->spare = malloc(sizeof(*cors->spare));
702 return cors->spare != NULL;
703}
704
705
706static Coroutine_Err
707Coroutines_ctor(
708 Coroutines *cors,
709 size_t min_size,
710 size_t min_headroom
711){
712 if (_Cor_Mutex_ctor(&cors->mutex)){
713 goto error;
714 }
715 cors->primary = NULL;
716 cors->stack_limit = g_stack_limit;
717
718 List_Init(&cors->all);
719 List_Init(&cors->free);
720 List_Init(&cors->inactive);
721 List_Init(&cors->runable);
722 List_Init(&cors->waiting);
723 if (_Cor_Mutex_ctor(&cors->waiting_mutex)){
724 goto error1;
725 }
726 if (_Cor_Mutex_Lock(&cors->waiting_mutex)){
727 goto error2;
728 }
729
730 cors->report.coroutines_created = 0;
731 cors->report.coroutines_pool_size = 0;
732 cors->report.largest_stack = 0;
733 cors->spare = NULL;
734 cors->sequence = 0;
735
736 Coroutine *cor = malloc(sizeof(*cor));
737 cor->min_size = min_size;
738 cor->min_headroom = min_headroom;
739 cor->coroutines = cors;
740 cor->sequence = cors->sequence++;
741 cor->state = Coroutine_Running;
742 cor->base = (unsigned char *)&cor;
743 if (cors->stack_limit){
744 cor->limit = cors->stack_limit;
745 cor->guard = StackPointerAdd(cor->limit, -GUARD_PATTERN_SIZE);
746 Apply_Guard(cor->guard);
747 } else {
748 cor->limit = cor->guard = NULL;
749 }
750 cors->root = cor;
751 List_AddHead(&cors->all, &cor->all_link);
752 List_AddTail(&cors->runable, &cor->link);
753 cors->tip = cors->active = cor;
754
755 cors->report.coroutines_pool_size += 1;
756
757 cors->state = Coroutines_Started;
758 return Coroutine_OK;
759error2:
760 _Cor_Mutex_dtor(&cors->waiting_mutex);
761error1:
762 _Cor_Mutex_dtor(&cors->mutex);
763error:
764 return Coroutine_Err_CouldNotInitialiseSystem;
765}
766
767static void
768Coroutines_dtor(
769 Coroutines *cors
770){
771 _Cor_Mutex_Lock(&cors->mutex);
772 cors->state = Coroutines_Stopping;
773
774 MyAssert(List_IsEmpty(&cors->inactive));
775
776 // free the spare
777 if (cors->spare){
778 free(cors->spare);
779 }
780
781 // free all non-spares
782 List_Link *link;
783 List_Link *next;
784 for (link = List_Begin(&cors->all); Link_NextIsLink(link); link = next){
785 next = Link_Next(link);
786 Coroutine *cor = List_Link_Container(Coroutine, all_link, link) ;
787 free(cor);
788 }
789
790 _Cor_Mutex_Unlock(&cors->waiting_mutex);
791 _Cor_Mutex_dtor(&cors->waiting_mutex);
792
793 MyAssert(cors->state == Coroutines_Stopping);
794 _Cor_Mutex_Unlock(&cors->mutex);
795 _Cor_Mutex_dtor(&cors->mutex);
796}
797
798
799Coroutine_Err
800Coroutine_RunSystem(
801 size_t min_size,
802 size_t min_headroom,
803 Coroutine_SystemStart start,
804 void *value
805){
806 CHECK_SYSTEM_NOT_RUNNING
807
808 Coroutines cors;
809 Coroutine_Err err = Coroutines_ctor(&cors, min_size, min_headroom);
810 if (err){
811 return err;
812 }
813 g_c = &cors;
814 err = start(value, cors.root);
815 g_c = NULL;
816 Coroutines_dtor(&cors);
817 return err;
818}
819
820
821void
822Coroutine_SetStackLimit(
823 void *limit
824){
825 MyAssert(!limit || !g_c || (unsigned char *)limit >= (unsigned char *)g_c->tip->limit);
826 g_stack_limit = limit;
827 if (g_c){
828 g_c->stack_limit = limit;
829 if (g_c->tip){
830 g_c->tip->limit = limit;
831 g_c->tip->guard = StackPointerAdd(limit, -GUARD_PATTERN_SIZE);
832 Apply_Guard(g_c->tip->guard);
833 }
834 }
835}
836
837
838#if COROUTINE_RECORD_LOWEST_HEADROOM
839static size_t
840Coroutine_UpdateMinimumHeadroom(
841 List_Head *list,
842 size_t headroom
843){
844 for (List_Link *link = List_Begin(list); Link_NextIsLink(link); link = Link_Next(link)){
845 Coroutine *cor = List_Link_Container(Coroutine, link, link);
846 if (cor->guard){
847 size_t chunk_size = Coroutine_Size(cor);
848 for (size_t i = 0; i <= chunk_size-GUARD_PATTERN_SIZE; i += GUARD_PATTERN_SIZE){
849 if (!Guard_Pattern_OK(StackPointerAdd(cor->guard, -i))){
850 headroom = i < headroom ? i : headroom;
851 break;
852 }
853 }
854 }
855 }
856 return headroom;
857}
858#endif
859
860
861Coroutine_Report
862Coroutine_GetReport(
863 void
864){
865 if (g_c){
866 size_t headroom;
867#if COROUTINE_RECORD_LOWEST_HEADROOM
868 _Cor_Mutex_Lock(&g_c->mutex);
869 headroom = g_c->report.lowest_headroom;
870 headroom = Coroutine_UpdateMinimumHeadroom(&g_c->inactive, headroom);
871 headroom = Coroutine_UpdateMinimumHeadroom(&g_c->runable, headroom);
872 headroom = Coroutine_UpdateMinimumHeadroom(&g_c->waiting, headroom);
873 _Cor_Mutex_Unlock(&g_c->mutex);
874#else
875 headroom = 0;
876#endif
877 g_c->report.lowest_headroom = headroom;
878
879 return g_c->report;
880 } else {
881 Coroutine_Report ret = {0, 0, 0, 0};
882 return ret;
883 }
884}
885
886
887#ifndef NDEBUG
888static void
889Coroutine_ReportNonEmptyList(
890 List_Head const *head,
891 char const *tag
892){
893 List_Link *link;
894 for (link = List_Begin(head); Link_NextIsLink(link); link = Link_Next(link)){
895 Coroutine *cor = List_Link_Container(Coroutine, link, link);
896 printf("%s: %p %p %p\n", tag, cor, cor->start, cor->entry_param);
897 }
898}
899#endif
900
901Coroutine_Err
902Coroutine_Run_Coroutine(
903 Coroutine *cor,
904 void *value
905){
906 CHECK_SYSTEM_RUNNING
907 CHECK_COROUTINE_THREAD
908 CHECK_NO_COROUTINE_RUNNING
909
910 Coroutines *cors = cor->coroutines;
911 _Cor_Mutex_Lock(&cors->mutex);
912 cors->primary = cor;
913
914 Coroutine_Continue_(cors, cor, value, true);
915
916 if (!setjmp(cors->controller)){
917 ready_jmp_buf(cors->controller);
918 _Cor_Mutex_Unlock(&cors->mutex);
919
920 // start the first coroutine
921 Coroutine_RunNext();
922 }
923 // arrive here with mutex locked
924 if (!List_IsEmpty(&cors->runable) || !List_IsEmpty(&cors->waiting)){
925#ifndef NDEBUG
926 Coroutine_ReportNonEmptyList(&cors->runable, "runable");
927 Coroutine_ReportNonEmptyList(&cors->waiting, "waiting");
928#endif
929 return Coroutine_Err_ExitWithRunningCoroutines;
930 }
931 _Cor_Mutex_Unlock(&cors->mutex);
932
933 return Coroutine_OK;
934}
935
936
937struct Coroutine_Run_Params {
938 Coroutine_Start start;
939 void *value;
940 void **result;
941};
942
943static Coroutine_Err
944Coroutine_Run_Starter(
945 void *_params,
946 Coroutine *root
947){
948 (void)root;
949 struct Coroutine_Run_Params *params = (struct Coroutine_Run_Params *)_params;
950
951 void *res = params->start(params->value);
952 if (params->result){
953 *params->result = res;
954 }
955
956 return Coroutine_OK;
957}
958
959
960Coroutine_Err Coroutine_Run(
961 size_t min_size,
962 size_t min_headroom,
963 Coroutine_Start start,
964 void *value,
965 void **result
966){
967 if (!g_c){
968 struct Coroutine_Run_Params params = {start, value, result};
969 return Coroutine_RunSystem(min_size, min_headroom, Coroutine_Run_Starter, &params);
970 }
971
972 // We are in an active coroutine, so call start() directly
973 CHECK_STACK_OVERRUN
974 void *res = start(value);
975 if (result){
976 *result = res;
977 }
978
979 // no failures, so...
980 return Coroutine_OK;
981}
982
983
984static Coroutine *Coroutine_New_Lock_Assumed(
985 size_t min_size,
986 size_t min_headroom,
987 Coroutine_Start start
988){
989 List_Link *link;
990
991 if (!EnsureSpare(g_c)){
992 return NULL;
993 }
994
995 Coroutine *cor = NULL;
996 for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
997 Coroutine *candidate = List_Link_Container(Coroutine, link, link);
998 MyAssert(candidate->coroutines == g_c);
999 MyAssert(candidate->state == Coroutine_Free);
1000 if (candidate->limit){
1001 size_t candidate_size = Coroutine_Size(candidate);
1002 if (candidate_size < min_size){
1003 continue;
1004 }
1005 }
1006 // candidate has no limit, or is big enough
1007
1008 // check if it's 'better' (lower in the C stack) than cor
1009 if (!cor || StackPointerDiff(candidate->base, cor->base) < 0){
1010 // chunk big enough, and a better choice than cor
1011 cor = candidate;
1012 }
1013 }
1014
1015 if (!cor){
1016 return NULL;
1017 }
1018
1019 // use the whole block - the tail will be freed in (New) or (Yield)
1020 cor->min_size = min_size;
1021 cor->min_headroom = min_headroom;
1022 cor->state = Coroutine_Idle;
1023 cor->start = start;
1024 cor->value = NULL;
1025 Link_Remove(&cor->link);
1026 List_AddHead(&g_c->inactive, &cor->link);
1027
1028 // trim down to an appropriate size
1029 size_t trimmable_size = TrimmableSize(cor);
1030 if (trimmable_size){
1031 // split block into two
1032 if (EnsureSpare(g_c)){
1033 g_c->size_to_retain = trimmable_size;
1034 if (!setjmp(g_c->chunk_allocated)){
1035 ready_jmp_buf(g_c->chunk_allocated);
1036 longjmp(cor->buf, Chunk_Split);
1037 }
1038 }
1039 }
1040
1041 g_c->report.coroutines_created += 1;
1042
1043 return cor;
1044}
1045
1046
1047static void
1048TrimActiveIfPossible
1049(
1050 void
1051){
1052 MyAssert(g_c);
1053
1054 // If we're the active coroutine, free the tail
1055 Coroutine *active = g_c->active;
1056 MyAssert(active);
1057
1058 active->stack_top = (unsigned char *)StackTopNow();
1059 ptrdiff_t timmablesize = TrimmableSize(active);
1060 if (!timmablesize){
1061 return;
1062 }
1063
1064 if (!EnsureSpare(g_c)){
1065 return;
1066 }
1067
1068 // enough space for a second coroutine so free the unused stack space from active
1069 if (!setjmp(g_c->chunk_allocated)){
1070 ready_jmp_buf(g_c->chunk_allocated);
1071 ReserveStackSpace(g_c, active, timmablesize - StackPointerDiff(active->stack_top, active->base), active->limit);
1072 MyAssert(false);
1073 }
1074}
1075
1076
1077static void
1078EnlargeActiveIfPossible(
1079 void
1080){
1081 MyAssert(g_c);
1082 Coroutine *active = g_c->active;
1083 MyAssert(active);
1084
1085 List_Link *next = Link_Next(&active->all_link);
1086 if (!Link_NextIsLink(next)){
1087 return;
1088 }
1089 Coroutine *cor = List_Link_Container(Coroutine, all_link, next);
1090 if (cor->state != Coroutine_Free){
1091 return;
1092 }
1093
1094 // Following block is free, merge with this
1095 active->limit = cor->limit;
1096 active->guard = cor->guard;
1097 Link_Remove(&cor->link);
1098 Link_Remove(&cor->all_link);
1099 if (g_c->tip == cor){
1100 g_c->tip = active;
1101 }
1102 if (g_c->spare){
1103 free(cor);
1104 } else {
1105 g_c->spare = cor;
1106 }
1107}
1108
1109
1110Coroutine *
1111Coroutine_New(
1112 size_t min_size,
1113 size_t min_headroom,
1114 Coroutine_Start start
1115){
1116 MyAssert(g_c && g_c->state == Coroutines_Started);
1117 MyAssert(!Coroutine_StackHasOverrun());
1118
1119 // Make the paramaters make sense
1120 if (min_size < min_headroom){
1121 min_size = min_headroom;
1122 }
1123
1124 _Cor_Mutex_Lock(&g_c->mutex);
1125
1126 TrimActiveIfPossible();
1127
1128 Coroutine *cor = Coroutine_New_Lock_Assumed(min_size, min_headroom, start);
1129
1130 if (cor && Coroutine_Size(cor) > g_c->report.largest_stack){
1131 g_c->report.largest_stack = Coroutine_Size(cor);
1132 }
1133
1134 EnlargeActiveIfPossible();
1135
1136 _Cor_Mutex_Unlock(&g_c->mutex);
1137
1138 return cor;
1139}
1140
1141
1142void
1143Coroutine_Delete(
1144 Coroutine *cor
1145){
1146 MyAssert(!Coroutine_StackHasOverrun());
1147 if (cor){
1148 Coroutines *cors = cor->coroutines;
1149 _Cor_Mutex_Lock(&cors->mutex);
1150 MyAssert(cor->state == Coroutine_Idle || cor->state == Coroutine_Complete);
1151
1152#if COROUTINE_RECORD_LOWEST_HEADROOM
1153 if (cor->guard){
1154 unsigned char *guard = cor->guard;
1155 ptrdiff_t chunk_size = Coroutine_Size(cor);
1156 ptrdiff_t myheadroom;
1157 for (myheadroom = 0; myheadroom <= chunk_size-(ptrdiff_t)GUARD_PATTERN_SIZE; myheadroom += GUARD_PATTERN_SIZE){
1158 if (!Guard_Pattern_OK(StackPointerAdd(guard, -myheadroom))){
1159 break;
1160 }
1161 }
1162 if (myheadroom < (ptrdiff_t)g_c->report.lowest_headroom || g_c->report.lowest_headroom == 0){
1163 g_c->report.lowest_headroom = myheadroom;
1164 }
1165 }
1166#endif
1167
1168 cor->state = Coroutine_Free;
1169 Link_Remove(&cor->link);
1170
1171 // insert into free list
1172 List_AddHead(&cors->free, &cor->link);
1173
1174 // Check for merge with following Coroutine
1175 List_Link *link = Link_Next(&cor->all_link);
1176 if (Link_NextIsLink(link)){
1177 Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
1178 if (listcor->state == Coroutine_Free){
1179 // merge
1180 cor->limit = listcor->limit;
1181 cor->guard = listcor->guard;
1182 Link_Remove(&listcor->all_link);
1183 Link_Remove(&listcor->link);
1184 if (g_c->tip == listcor){
1185 g_c->tip = cor;
1186 }
1187
1188 // free up the now unused struct
1189 if (g_c->spare){
1190 free(listcor);
1191 } else {
1192 g_c->spare = listcor;
1193 }
1194 }
1195 }
1196
1197 // check for merge with prev coroutine
1198 link = Link_Prev(&cor->all_link);
1199 if (Link_PrevIsLink(link)){
1200 Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
1201 if (listcor->state == Coroutine_Free){
1202 // merge
1203 listcor->limit = cor->limit;
1204 listcor->guard = cor->guard;
1205 Link_Remove(&cor->all_link);
1206 Link_Remove(&cor->link);
1207 if (g_c->tip == cor){
1208 g_c->tip = listcor;
1209 }
1210
1211 // free up the now unused struct
1212 if (g_c->spare){
1213 free(cor);
1214 } else {
1215 g_c->spare = cor;
1216 }
1217 }
1218 }
1219
1220 EnlargeActiveIfPossible();
1221
1222 _Cor_Mutex_Unlock(&cors->mutex);
1223 }
1224}
1225
1226
1227// Coroutine_Continue, assuming the mutex is claimed
1228// return false for success, true for something went wrong
1229static Coroutine_Err
1230Coroutine_Continue_(
1231 Coroutines *cors,
1232 Coroutine *cor,
1233 void *value,
1234 bool early
1235){
1236 if (cor->state == Coroutine_Running){
1237 // already running
1238 return Coroutine_OK;
1239 }
1240 if (cor->state != Coroutine_Idle && cor->state != Coroutine_Waiting){
1241 return Coroutine_Err_WrongState;
1242 }
1243 cor->entry_param = value;
1244 cor->state = Coroutine_Running;
1245 Link_Remove(&cor->link);
1246 if ( early ) {
1247 List_AddHead(&cors->runable, &cor->link);
1248 } else {
1249 List_AddTail(&cors->runable, &cor->link);
1250 }
1251 _Cor_Mutex_Unlock(&cors->waiting_mutex);
1252 return Coroutine_OK;
1253}
1254
1255
1256Coroutine_Err
1257Coroutine_Continue(
1258 Coroutine *cor,
1259 void *value,
1260 bool early
1261){
1262 MyAssert(!Coroutine_StackHasOverrun());
1263 Coroutines *cors = cor->coroutines;
1264 _Cor_Mutex_Lock(&cors->mutex);
1265 Coroutine_Err err = Coroutine_Continue_(cors, cor, value, early);
1266 _Cor_Mutex_Unlock(&cors->mutex);
1267 return err;
1268}
1269
1270
1271void *
1272Coroutine_Yield(
1273 void *value,
1274 Coroutine_YieldCallback on_yield,
1275 void *yield_me
1276){
1277 MyAssert(g_c);
1278 Coroutine *me = g_c->active;
1279 MyAssert(me);
1280 MyAssert(!Coroutine_StackHasOverrun());
1281
1282 _Cor_Mutex_Lock(&g_c->mutex);
1283 Coroutines *cors = me->coroutines;
1284 MyAssert(me && me->state == Coroutine_Running && cors == g_c);
1285 me->stack_top = (unsigned char *)StackTopNow();
1286 me->value = value;
1287 me->state = Coroutine_Waiting;
1288
1289 TrimActiveIfPossible();
1290
1291 Link_Remove(&me->link);
1292 if (!List_IsEmpty(&cors->runable)){
1293 _Cor_Mutex_Unlock(&cors->waiting_mutex);
1294 }
1295 List_AddTail(&cors->waiting, &me->link);
1296
1297 switch (setjmp(me->buf)){
1298 case Chunk_Initial:
1299 ready_jmp_buf(me->buf);
1300 _Cor_Mutex_Unlock(&cors->mutex);
1301 on_yield(yield_me);
1302 Coroutine_RunNext();
1303 MyAssert(false);
1304 break;
1305 case Chunk_Enter:
1306 // arrive here with mutex locked
1307 cors->active = me;
1308 MyAssert(!Coroutine_StackHasOverrun());
1309 // when we return here - we are running again
1310 MyAssert(me->state == Coroutine_Running);
1311 EnlargeActiveIfPossible();
1312 void *res = me->entry_param;
1313 _Cor_Mutex_Unlock(&cors->mutex);
1314 return res;
1315 }
1316 MyAssert(false);
1317 return NULL;
1318}
1319
1320
1321void *
1322Coroutine_GetValue(
1323 Coroutine *cor
1324){
1325 return cor->value;
1326}
1327
1328
1329Coroutine *
1330Coroutine_GetActive(
1331 void
1332){
1333 return g_c ? g_c->active : NULL;
1334}
1335
1336
1337ptrdiff_t
1338Coroutine_GetStackHeadroom(
1339 void
1340){
1341 Coroutine *me = g_c ? g_c->active : NULL;
1342 if (!me){
1343 // no active coroutine
1344 if (g_stack_limit){
1345 return StackPointerDiff(g_stack_limit, (unsigned char *)StackTopNow());
1346 } else {
1347 // no information where the stack ends - return something
1348 // The biggest ptrdiff_t possible
1349 return PTRDIFF_MAX;
1350 }
1351 } else {
1352 if (me->guard){
1353 return StackPointerDiff(me->guard, (unsigned char *)StackTopNow());
1354 } else {
1355 // The biggest ptrdiff_t possible
1356 return PTRDIFF_MAX;
1357 }
1358 }
1359}
1360
1361
1362void *
1363Coroutine_GetStackHWM(
1364 void
1365){
1366 MyAssert(g_c);
1367 MyAssert(g_c->state == Coroutines_Started);
1368 MyAssert(!Coroutine_StackHasOverrun());
1369 // Find where the guards end
1370 unsigned char *guard = g_c->active->guard;
1371 if (guard){
1372 ptrdiff_t headroom = Coroutine_GetStackHeadroom();
1373 for (ptrdiff_t i = 0; i <= headroom; i += GUARD_PATTERN_SIZE){
1374 if (!Guard_Pattern_OK(StackPointerAdd(guard, -i))){
1375 return StackPointerAdd(guard, i);
1376 }
1377 }
1378 }
1379 return guard;
1380}
1381
1382
1383void
1384Coroutine_ClearStackForHWM(
1385 void
1386){
1387 MyAssert(g_c);
1388 MyAssert(!Coroutine_StackHasOverrun());
1389 unsigned char *guard = g_c->active->guard;
1390 if (guard){
1391 ptrdiff_t headroom = Coroutine_GetStackHeadroom();
1392 for (ptrdiff_t i = 0; i <= headroom; i += GUARD_PATTERN_SIZE){
1393 Apply_Guard(StackPointerAdd(guard, -i));
1394 }
1395 }
1396}
1397
1398
1399static bool
1400Coroutine_CanStartCoroutine_Lock_Assumed(
1401 size_t min_size
1402){
1403 if (!g_c->stack_limit){
1404 return true;
1405 }
1406
1407 // check free list
1408 List_Link *link;
1409 for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
1410 Coroutine *cor = List_Link_Container(Coroutine, link, link);
1411 size_t cor_size = Coroutine_Size(cor);
1412 if (cor_size >= min_size){
1413 return true;
1414 }
1415 }
1416
1417 // Check if this coroutine has enough size
1418 Coroutine *me = g_c->active;
1419 me->stack_top = (unsigned char *)StackTopNow();
1420 ptrdiff_t reduced_size = TrimmableSize(g_c->active);
1421 if (reduced_size && StackPointerDiff(g_c->active->limit, g_c->active->base) - reduced_size > (ptrdiff_t)min_size){
1422 return true;
1423 }
1424
1425 return false;
1426}
1427
1428
1429bool
1430Coroutine_CanStartCoroutine(
1431 size_t size
1432){
1433 MyAssert(g_c && g_c->state == Coroutines_Started);
1434 MyAssert(!Coroutine_StackHasOverrun());
1435
1436 _Cor_Mutex_Lock(&g_c->mutex);
1437
1438 bool result = Coroutine_CanStartCoroutine_Lock_Assumed(size);
1439
1440 _Cor_Mutex_Unlock(&g_c->mutex);
1441
1442 return result;
1443}
1444
1445void *
1446Coroutine_GetCStackTop(
1447 void
1448){
1449 if (!g_c || g_c->tip == g_c->active){
1450 return (void *)StackTopNow();
1451 }
1452
1453 return g_c->tip->stack_top;
1454}
1455
1456
1457// Inspired by cpython...
1458#ifdef __has_builtin
1459# define Coroutine__has_builtin(x) __has_builtin(x)
1460#else
1461# define Coroutine__has_builtin(x) 0
1462#endif
1463
1464#if !Coroutine__has_builtin(__builtin_frame_address) && !defined(__GNUC__) && !defined(_MSC_VER)
1465static uintptr_t return_pointer_as_int(char* p) {
1466 return (uintptr_t)p;
1467}
1468#endif
1469
1470static inline uintptr_t
1471StackTopNow(void) {
1472#if Coroutine__has_builtin(__builtin_frame_address) || defined(__GNUC__)
1473 return (uintptr_t)__builtin_frame_address(0);
1474#elif defined(_MSC_VER)
1475 return (uintptr_t)_AddressOfReturnAddress();
1476#else
1477 char here;
1478 /* Avoid compiler warning about returning stack address */
1479 return return_pointer_as_int(&here);
1480#endif
1481}
1482// ...inspired by cpython
1483
1484
1485struct Coroutine_ChainParam {
1486 Coroutine_Start start;
1487 void *value;
1488 Coroutine *ret;
1489};
1490
1491
1492static void *
1493Coroutine_ChainFn(
1494 void *param
1495){
1496 struct Coroutine_ChainParam *params = (struct Coroutine_ChainParam *)param;
1497 void *res = params->start(params->value);
1498 return (void *)(uintptr_t)Coroutine_Continue(params->ret, res, true);
1499}
1500
1501
1502static void
1503Coroutine_ChainYield(
1504 void *unused
1505){
1506 (void)unused;
1507}
1508
1509
1510Coroutine_Err
1511Coroutine_Chain(
1512 size_t min_size,
1513 size_t min_headroom,
1514 Coroutine_Start start,
1515 void *value,
1516 void **result
1517){
1518 MyAssert(!Coroutine_StackHasOverrun());
1519 Coroutine *cor = Coroutine_New(min_size, min_headroom, Coroutine_ChainFn);
1520 if (!cor){
1521 // failed
1522 return Coroutine_Err_NoStack;
1523 }
1524 struct Coroutine_ChainParam params = {
1525 start,
1526 value,
1527 Coroutine_GetActive()
1528 };
1529 Coroutine_Err err = Coroutine_Continue(cor, &params, true);
1530 if (err){
1531 goto error;
1532 }
1533 void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
1534 err = (Coroutine_Err)(uintptr_t)Coroutine_GetValue(cor);
1535error:
1536 Coroutine_Delete(cor);
1537 if (!err && result){
1538 *result = res;
1539 }
1540 // success! ...probably
1541 return err;
1542}
1543
1544
1545bool
1546Coroutine_IsRunning(
1547 Coroutine *cor
1548){
1549 int state = cor->state;
1550 return state == Coroutine_Running || state == Coroutine_Waiting;
1551}
1552
1553
1554bool Coroutine_IsComplete(
1555 Coroutine *cor
1556){
1557 int state = cor->state;
1558 return state == Coroutine_Complete;
1559}
1560
1561
1562bool
1563Coroutine_IsStarted(
1564 void
1565){
1566 return g_c && g_c->state == Coroutines_Started;
1567}
1568
1569void
1570Coroutine_Dump_(
1571 void
1572){
1573 char *state_to_text[] = {
1574 "Free",
1575 "Idle",
1576 "Running",
1577 "Waiting",
1578 "Complete"
1579 };
1580 unsigned idx = 0;
1581 List_Link *link;
1582 for (link = List_Begin(&g_c->all); Link_NextIsLink(link); link = Link_Next(link)){
1583 Coroutine *cor = List_Link_Container(Coroutine, all_link, link);
1584 printf("%d) %p (%s) %s\n", idx++, cor, state_to_text[cor->state], cor == g_c->tip ? " (TIP)" : "");
1585 }
1586}
1587#include "coroutine_names_undef.h"
1588