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