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