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