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