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