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