0 branches 0 tags
85
Reduce compilation warnings
jonroach 22 May 2026 08:28
1 contributor
1354 lines37.2 KB
Text Raw Blame
  • Delete
1#include "coroutine.h"
2#include <assert.h>
3#include <setjmp.h>
4#include <stdbool.h>
5#include <stddef.h>
6#include <stdio.h>
7#include "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
348static Coroutine_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 Coroutine_Err err;
384#if COROUTINE_CHECK_INTEGRITY_ON_STACK_CHECK
385 // Check all coroutines integrity
386 err = _Coroutine_CheckIntegrity();
387 if (err){
388 return err;
389 }
390#endif
391 if (me->guard){
392 err = Guard_Pattern_OK(me->guard) ? Coroutine_OK : Coroutine_Err_StackOverrun;
393 if (err){
394 printf("Guard pattern trampled\n");
395 }
396 return err;
397 }
398 err = stack_top >= me->limit ? Coroutine_OK : Coroutine_Err_StackOverrun;
399 if (err){
400 printf("Stack top beyond active stack limit\n");
401 }
402 return err;
403}
404
405#ifndef NDEBUG
406Coroutine_Err Coroutine_CheckIntegrity(void){
407 Coroutine_Err err = Coroutine_StackHasOverrun();
408#if !COROUTINE_CHECK_INTEGRITY_ON_STACK_CHECK
409 if (!err && g_c){
410 err = _Coroutine_CheckIntegrity();
411 }
412#endif
413 return err;
414}
415#endif
416
417
418static void ReserveStackSpace(
419 Coroutines *cors,
420 Coroutine *parent,
421 size_t chunk_size,
422 unsigned char *childs_limit
423){
424 unsigned char *chunk_of_stack = alloca(chunk_size);
425#if COROUTINE_RECORD_LOWEST_HEADROOM
426 for (size_t i = 0; i <= chunk_size-GUARD_PATTERN_SIZE; i += GUARD_PATTERN_SIZE){
427 Apply_Guard(&chunk_of_stack[i]);
428 }
429#else
430 Apply_Guard(chunk_of_stack);
431#endif
432 if (parent){
433 parent->guard = chunk_of_stack;
434 parent->limit = chunk_of_stack;
435 parent->base = chunk_of_stack + chunk_size;
436 }
437 stack_chunk_base(cors, parent, chunk_of_stack, childs_limit);
438}
439
440
441static void stack_chunk_base(
442 Coroutines *cors,
443 Coroutine *parent,
444 unsigned char *prev_limit,
445 unsigned char *limit
446){
447 Coroutine here;
448 here.coroutines = cors;
449 here.state = Coroutine_Free;
450 here.prev_limit = prev_limit;
451 here.size = 0;
452 here.base = NULL;
453 here.guard = limit;
454 here.limit = limit;
455 if (limit){
456 here.base = (unsigned char *)&here - cors->gap_after;
457 here.size = here.base - here.limit;
458 Apply_Guard(limit);
459 }
460
461 // insert into all list
462 if (parent){
463 Link_AddAfter(&here.all_link, &parent->all_link);
464 } else {
465 List_AddHead(&cors->all, &here.all_link);
466 }
467 // add to free list
468 List_AddTail(&cors->free, &here.link);
469
470 cors->report.coroutines_pool_size += 1;
471
472 if (!cors->tip || &here < cors->tip){
473 cors->tip = &here;
474 }
475
476 for(;;){
477 switch (setjmp(here.buf)) {
478 case Chunk_Initial:
479 if (here.state == Coroutine_Free){
480 // return to the coroutine allocator
481 longjmp(cors->chunk_allocated, 1);
482 } else {
483 MyAssert(here.state == Coroutine_Complete);
484 // we finish here to ensure the setjmp is redone
485 if (cors->primary == &here) {
486 // if primary coroutine - return to Coroutine_Run
487 longjmp(cors->controller, Coroutines_CoroutineComplete);
488 }
489 _Cor_Mutex_Unlock(&cors->mutex);
490 Coroutine_RunNext();
491 }
492 MyAssert(false);
493 break;
494 case Chunk_Create:
495 // Request to create a new chunk on the stack
496 // We're here if the coroutine is:
497 // Allocated, but not 'run' (Coroutine_Idle)
498 // Run, but not not entered yet (Coroutine_Running)
499 // Completed (Coroutine_Complete)
500 // Free, and the coroutines system is starting - we're characterising the system
501 MyAssert(here.state == Coroutine_Idle ||
502 here.state == Coroutine_Running ||
503 here.state == Coroutine_Complete ||
504 (here.state == Coroutine_Free && cors->state == Coroutines_Starting));
505 ReserveStackSpace(here.coroutines, &here, here.size, NULL);
506 MyAssert(false);
507 break;
508 case Chunk_Split:
509 // Request to split this free block into two
510 // here.size will be set to our shorter size
511 ReserveStackSpace(here.coroutines, &here, here.size, here.limit);
512 MyAssert(false);
513 break;
514 case Chunk_Enter:
515 // request to start a coroutine (ie use the chunk for a coroutine)
516 // arrive here with mutex locked
517 MyAssert(here.state == Coroutine_Running);
518 here.coroutines->active = &here;
519 _Cor_Mutex_Unlock(&cors->mutex);
520 here.value = here.start(here.entry_param);
521
522 // check the guard
523 MyAssert(Guard_Pattern_OK(here.guard));
524
525 _Cor_Mutex_Lock(&here.coroutines->mutex);
526 here.coroutines->active = NULL;
527 MyAssert(here.state == Coroutine_Running);
528 Link_Remove(&here.link);
529 here.state = Coroutine_Complete;
530 List_AddTail(&here.coroutines->inactive, &here.link);
531 // Coroutine has completed
532 // Loop round to redo the setjmp() - if this coroutine yielded, then the setjmp will
533 // need reseting
534 break;
535 }
536 }
537}
538
539
540static void Coroutine_RunNext(void)
541{
542 // arrive here with mutex unlocked
543 _Cor_Mutex_Lock(&g_c->waiting_mutex);
544 _Cor_Mutex_Lock(&g_c->mutex);
545 Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c->runable));
546 MyAssert(next->state == Coroutine_Running);
547 longjmp(next->buf, Chunk_Enter);
548 MyAssert(false);
549}
550
551
552static Coroutine_Err Coroutines_ctor(Coroutines *cors)
553{
554 cors->state = Coroutines_Starting;
555 if (_Cor_Mutex_ctor(&cors->mutex)){
556 return Coroutine_Err_CouldNotInitialiseSystem;
557 }
558 cors->tip = NULL;
559 cors->active = NULL;
560 cors->primary = NULL;
561 cors->stack_limit = g_stack_limit;
562
563 List_Init(&cors->all);
564 List_Init(&cors->free);
565 List_Init(&cors->inactive);
566 List_Init(&cors->runable);
567 List_Init(&cors->waiting);
568 if (_Cor_Mutex_ctor(&cors->waiting_mutex)){
569 _Cor_Mutex_dtor(&cors->mutex);
570 return Coroutine_Err_CouldNotInitialiseSystem;
571 }
572 if (_Cor_Mutex_Lock(&cors->waiting_mutex)){
573 _Cor_Mutex_dtor(&cors->waiting_mutex);
574 _Cor_Mutex_dtor(&cors->mutex);
575 return Coroutine_Err_CouldNotInitialiseSystem;
576 }
577
578 cors->report.coroutines_created = 0;
579 cors->report.coroutines_pool_size = 0;
580 cors->report.largest_stack = 0;
581
582 // Charactersize the system...
583 if (!setjmp(cors->chunk_allocated)){
584 ReserveStackSpace(cors, NULL, COROUTINE_STARTUP_STACK_SIZE, NULL);
585 }
586 Coroutine *cor = List_Link_Container(Coroutine, link, List_GetHead(&cors->free));
587 cor->size = COROUTINE_STARTUP_STACK_SIZE;
588 if (!setjmp(cors->chunk_allocated)){
589 longjmp(cor->buf, Chunk_Create);
590 }
591 cors->gap_before = cor->prev_limit - (unsigned char *)cor;
592 cors->gap_after = (unsigned char *)cor - cor->base;
593 // ...charactersize the system
594
595 // discard what we've just created
596 List_Init(&cors->all);
597 List_Init(&cors->free);
598 cors->tip = NULL;
599
600 cors->state = Coroutines_Started;
601 return Coroutine_OK;
602}
603
604static void Coroutines_dtor(Coroutines *cors)
605{
606 _Cor_Mutex_Lock(&cors->mutex);
607 cors->state = Coroutines_Stopping;
608
609 MyAssert(List_IsEmpty(&cors->inactive));
610 _Cor_Mutex_Unlock(&cors->waiting_mutex);
611 _Cor_Mutex_dtor(&cors->waiting_mutex);
612
613 MyAssert(cors->state == Coroutines_Stopping);
614 _Cor_Mutex_Unlock(&cors->mutex);
615 _Cor_Mutex_dtor(&cors->mutex);
616}
617
618
619Coroutine_Err Coroutine_RunSystem(Coroutine_SystemStart start, void *value)
620{
621 CHECK_SYSTEM_NOT_RUNNING
622
623 Coroutines cors;
624 Coroutine_Err err = Coroutines_ctor(&cors);
625 if (err){
626 return err;
627 }
628 g_c = &cors;
629 err = start(value);
630 g_c = NULL;
631 Coroutines_dtor(&cors);
632 return err;
633}
634
635
636void Coroutine_SetStackLimit(void *limit){
637 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);
638 g_stack_limit = limit;
639 if (g_c){
640 g_c->stack_limit = limit;
641 }
642}
643
644
645#if COROUTINE_RECORD_LOWEST_HEADROOM
646static size_t Coroutine_UpdateMinimumHeadroom(List_Head *list, size_t headroom)
647{
648 for (List_Link *link = List_Begin(list); Link_NextIsLink(link); link = Link_Next(link)){
649 Coroutine *cor = List_Link_Container(Coroutine, link, link);
650 if (cor->guard){
651 for (uintptr_t i = 4; i < cor->size-3; i += 4){
652 if (!Guard_Pattern_OK(&cor->guard[i])){
653 headroom = i < headroom ? i : headroom;
654 break;
655 }
656 }
657 }
658 }
659 return headroom;
660}
661#endif
662
663
664Coroutine_Report Coroutine_GetReport(void)
665{
666 if (g_c){
667 size_t headroom;
668#if COROUTINE_RECORD_LOWEST_HEADROOM
669 _Cor_Mutex_Lock(&g_c->mutex);
670 headroom = g_c->report.lowest_headroom;
671 headroom = Coroutine_UpdateMinimumHeadroom(&g_c->inactive, headroom);
672 headroom = Coroutine_UpdateMinimumHeadroom(&g_c->runable, headroom);
673 headroom = Coroutine_UpdateMinimumHeadroom(&g_c->waiting, headroom);
674 _Cor_Mutex_Unlock(&g_c->mutex);
675#else
676 headroom = 0;
677#endif
678 g_c->report.lowest_headroom = headroom;
679
680 return g_c->report;
681 } else {
682 Coroutine_Report ret = {0, 0, 0, 0};
683 return ret;
684 }
685}
686
687
688#ifndef NDEBUG
689static void Coroutine_ReportNonEmptyList(
690 List_Head const *head,
691 char const *tag
692){
693 List_Link *link;
694 for (link = List_Begin(head); Link_NextIsLink(link); link = Link_Next(link)){
695 Coroutine *cor = List_Link_Container(Coroutine, link, link);
696 printf("%s: %p %p %p\n", tag, cor, cor->start, cor->entry_param);
697 }
698}
699#endif
700
701Coroutine_Err Coroutine_Run_Coroutine(
702 Coroutine *cor,
703 void *value
704){
705 CHECK_SYSTEM_RUNNING
706 CHECK_COROUTINE_THREAD
707 CHECK_NO_COROUTINE_RUNNING
708
709 Coroutines *cors = cor->coroutines;
710 _Cor_Mutex_Lock(&cors->mutex);
711 cors->state = Coroutines_Active;
712 cors->primary = cor;
713
714 _Coroutine_Continue(cors, cor, value, true);
715
716 if (!setjmp(cors->controller)){
717 _Cor_Mutex_Unlock(&cors->mutex);
718
719 // start the first coroutine
720 Coroutine_RunNext();
721 }
722 // arrive here with mutex locked
723 if (!List_IsEmpty(&cors->runable) || !List_IsEmpty(&cors->waiting)){
724#ifndef NDEBUG
725 Coroutine_ReportNonEmptyList(&cors->runable, "runable");
726 Coroutine_ReportNonEmptyList(&cors->waiting, "waiting");
727#endif
728 return Coroutine_Err_ExitWithRunningCoroutines;
729 }
730 MyAssert(cors->state == Coroutines_Active);
731 cors->state = Coroutines_Started;
732 _Cor_Mutex_Unlock(&cors->mutex);
733
734 return Coroutine_OK;
735}
736
737
738struct Coroutine_Run_Params {
739 size_t stack;
740 Coroutine_Start start;
741 void *value;
742 void **result;
743};
744
745static Coroutine_Err Coroutine_Run_Starter(void *_params)
746{
747 struct Coroutine_Run_Params *params = (struct Coroutine_Run_Params *)_params;
748
749 Coroutine *cor = Coroutine_New(params->stack, params->start);
750 if (!cor){
751 // that didn't work
752 return Coroutine_Err_NoStack;
753 }
754 Coroutine_Err ret = Coroutine_Run_Coroutine(cor, params->value);
755 if (!ret && params->result){
756 *params->result = Coroutine_GetValue(cor);
757 }
758 Coroutine_Delete(cor);
759 return ret;
760}
761
762
763Coroutine_Err Coroutine_Run(
764 size_t stack,
765 Coroutine_Start start,
766 void *value,
767 void **result
768){
769 if (!g_c){
770 struct Coroutine_Run_Params params = {stack, start, value, result};
771 return Coroutine_RunSystem(Coroutine_Run_Starter, &params);
772 }
773 if (!g_c->active)
774 {
775 // system running, but no active coroutine
776 Coroutine *cor = Coroutine_New(stack, start);
777 if (!cor){
778 // that didn't work
779 return Coroutine_Err_NoStack;
780 }
781 Coroutine_Err err = Coroutine_Run_Coroutine(cor, value);
782 if (!err && result){
783 *result = Coroutine_GetValue(cor);
784 }
785 Coroutine_Delete(cor);
786 return err;
787 }
788
789 // We are in an active coroutine, so call start() directly
790 CHECK_STACK_OVERRUN
791 void *res = start(value);
792 if (result){
793 *result = res;
794 }
795
796 // no failures, so...
797 return Coroutine_OK;
798}
799
800
801static void Coroutine_FreeToIdle(
802 Coroutine *cor,
803 Coroutine_Start start
804){
805 MyAssert(cor->state == Coroutine_Free);
806 cor->state = Coroutine_Idle;
807 cor->start = start;
808 cor->value = NULL;
809 Link_Remove(&cor->link);
810 List_AddHead(&g_c->inactive, &cor->link);
811
812 g_c->report.coroutines_created += 1;
813}
814
815
816static void Coroutine_FreeToIdleSize(
817 Coroutine *cor,
818 Coroutine_Start start,
819 size_t size
820){
821 MyAssert(!cor->guard);
822 cor->size = size;
823 cor->base = (unsigned char *)cor - g_c->gap_after;
824 cor->limit = cor->base - cor->size;
825 Coroutine_FreeToIdle(cor, start);
826}
827
828
829static Coroutine *Coroutine_New_Lock_Assumed(
830 size_t size,
831 Coroutine_Start start
832){
833 List_Link *link;
834
835 if (!g_c->tip){
836 // no tip - time to create one
837
838 // we're the non-Coroutine which starts the Coroutine system.
839 // Add a single free block
840 if (!setjmp(g_c->chunk_allocated)){
841 ReserveStackSpace(g_c, NULL, COROUTINE_STARTUP_STACK_SIZE, NULL);
842 }
843 }
844
845 Coroutine *cor = NULL;
846 for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
847 Coroutine *candidate = List_Link_Container(Coroutine, link, link);
848 MyAssert(candidate->coroutines == g_c);
849 if (!candidate->guard) {
850 // this must be the tip
851 MyAssert(candidate == g_c->tip);
852
853 size_t size_to_use;
854 // If this is the only Coroutine in the system, go ahead and use it regardless of size.
855 // Note: there can only be one free block if there's no other sort of blocks as we merge on free
856 if (List_IsEmpty(&g_c->inactive) &&
857 List_IsEmpty(&g_c->runable) &&
858 List_IsEmpty(&g_c->waiting) ){
859 if (g_c->stack_limit){
860 size_t available = (unsigned char *)candidate - g_c->stack_limit - g_c->gap_after;
861 size_to_use = available < size ? available : size;
862 } else {
863 size_to_use = size;
864 }
865 Coroutine_FreeToIdleSize(candidate, start, size_to_use);
866 return candidate;
867 }
868
869 // Not the only coroutine in the system - check size
870 if (g_c->stack_limit){
871 // there's a limit - see what that space allows....
872 size_t available = (unsigned char *)candidate - g_c->stack_limit - g_c->gap_after;
873
874 if (available < size){
875 // not enough space for this coroutine
876 // printf("Not enough stack space (A) %ld\n", available);
877 return NULL;
878 }
879
880 if (available < size + g_c->gap_before + g_c->gap_after + COROUTINE_MINIMUM_STACK_SIZE) {
881 // not enough space for another coroutine - use all the space for this one
882 size_to_use = available;
883 } else {
884 size_to_use = size;
885 }
886 } else {
887 size_to_use = size;
888 }
889 Coroutine_FreeToIdleSize(candidate, start, size_to_use);
890 return candidate;
891 }
892 if (candidate->size >= size && candidate > cor){
893 // chunk big enough, and a better choice than cor
894 cor = candidate;
895 }
896 }
897
898 if (cor){
899 // - work out whether we're splitting or using the whole chunk
900 if (cor->size >= size + g_c->gap_before + g_c->gap_after + COROUTINE_MINIMUM_STACK_SIZE){
901 // enough space for a second coroutine so split this free block
902 cor->size = size;
903 if (!setjmp(g_c->chunk_allocated)){
904 longjmp(cor->buf, Chunk_Split);
905 }
906 }
907 // cor now ready to use
908 Coroutine_FreeToIdle(cor, start);
909 return cor;
910 }
911
912 // No big-enough free blocks - check if there's space beyond the tip block
913
914 if (g_c->stack_limit) {
915 ptrdiff_t available = (unsigned char *)g_c->tip->limit - g_c->gap_before - g_c->gap_after - g_c->stack_limit;
916 if (available < (ptrdiff_t)size){
917 // no space for a new stack block
918 // 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);
919 // 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);
920 return NULL;
921 }
922 }
923 Coroutine *tip = g_c->tip;
924 Coroutine *me = g_c->active;
925 if (tip == me) {
926 if (!setjmp(g_c->chunk_allocated)){
927 ReserveStackSpace(g_c, me, StackTopNow() - me->limit, NULL);
928 }
929 } else {
930 if (!setjmp(g_c->chunk_allocated)){
931 longjmp(tip->buf, Chunk_Create);
932 }
933 }
934
935 cor = List_Link_Container(Coroutine, link, List_GetTail(&g_c->free));
936 MyAssert(cor->state == Coroutine_Free);
937 cor->size = size;
938 cor->limit = (unsigned char *)cor - g_c->gap_after - size;
939 cor->state = Coroutine_Idle;
940 cor->start = start;
941 cor->value = NULL;
942 Link_Remove(&cor->link);
943 List_AddHead(&g_c->inactive, &cor->link);
944
945 g_c->report.coroutines_created += 1;
946 return cor;
947}
948
949
950Coroutine *Coroutine_New(
951 size_t stack,
952 Coroutine_Start start
953){
954 MyAssert(g_c);
955 MyAssert((g_c->state == Coroutines_Started && List_IsEmpty(&g_c->inactive)) || g_c->state == Coroutines_Active);
956 MyAssert(!Coroutine_StackHasOverrun());
957
958 _Cor_Mutex_Lock(&g_c->mutex);
959
960 Coroutine *cor = Coroutine_New_Lock_Assumed(stack, start);
961
962 if (cor && cor->size > g_c->report.largest_stack){
963 g_c->report.largest_stack = cor->size;
964 }
965
966 _Cor_Mutex_Unlock(&g_c->mutex);
967
968 return cor;
969}
970
971
972void Coroutine_Delete(
973 Coroutine *cor
974){
975 MyAssert(!Coroutine_StackHasOverrun());
976 if (cor){
977 Coroutines *cors = cor->coroutines;
978 _Cor_Mutex_Lock(&cors->mutex);
979 MyAssert(cor->state == Coroutine_Idle || cor->state == Coroutine_Complete);
980
981#if COROUTINE_RECORD_LOWEST_HEADROOM
982 if (cor->guard){
983 unsigned char *base = cor->base;
984 unsigned char *rover;
985 for (rover = cor->limit+4; rover<base; rover += 4){
986 if (!Guard_Pattern_OK(rover)){
987 break;
988 }
989 }
990 size_t myheadroom = (size_t)(rover - cor->limit);
991 if (myheadroom < g_c->report.lowest_headroom || g_c->report.lowest_headroom == 0){
992 g_c->report.lowest_headroom = myheadroom;
993 }
994 }
995#endif
996
997 cor->state = Coroutine_Free;
998 Link_Remove(&cor->link);
999
1000 // insert into free list
1001 List_AddHead(&cors->free, &cor->link);
1002
1003 // Check for merge with following Coroutine
1004 List_Link *link = Link_Next(&cor->all_link);
1005 if (Link_NextIsLink(link)){
1006 Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
1007 if (listcor->state == Coroutine_Free){
1008 // merge
1009 cor->size += cor->limit - listcor->limit;
1010 cor->limit = listcor->limit;
1011 cor->guard = listcor->guard;
1012 Link_Remove(&listcor->all_link);
1013 Link_Remove(&listcor->link);
1014 if (g_c->tip == listcor){
1015 g_c->tip = cor;
1016 }
1017 }
1018 }
1019
1020 // check for merge with prev coroutine
1021 link = Link_Prev(&cor->all_link);
1022 if (Link_PrevIsLink(link)){
1023 Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
1024 if (listcor->state == Coroutine_Free){
1025 // merge
1026 listcor->size += listcor->limit - cor->limit;
1027 listcor->limit = cor->limit;
1028 listcor->guard = cor->guard;
1029 Link_Remove(&cor->all_link);
1030 Link_Remove(&cor->link);
1031 if (g_c->tip == cor){
1032 g_c->tip = listcor;
1033 }
1034 }
1035 }
1036
1037 _Cor_Mutex_Unlock(&cors->mutex);
1038 }
1039}
1040
1041
1042// Coroutine_Continue, assuming the mutex is claimed
1043// return false for success, true for something went wrong
1044static Coroutine_Err _Coroutine_Continue(
1045 Coroutines *cors,
1046 Coroutine *cor,
1047 void *value,
1048 bool early
1049){
1050 if (cor->state == Coroutine_Running){
1051 // already running
1052 return Coroutine_OK;
1053 }
1054 if (cor->state != Coroutine_Idle && cor->state != Coroutine_Waiting){
1055 return Coroutine_Err_WrongState;
1056 }
1057 cor->entry_param = value;
1058 cor->state = Coroutine_Running;
1059 Link_Remove(&cor->link);
1060 if ( early ) {
1061 List_AddHead(&cors->runable, &cor->link);
1062 } else {
1063 List_AddTail(&cors->runable, &cor->link);
1064 }
1065 _Cor_Mutex_Unlock(&cors->waiting_mutex);
1066 return Coroutine_OK;
1067}
1068
1069
1070Coroutine_Err Coroutine_Continue(
1071 Coroutine *cor,
1072 void *value,
1073 bool early
1074){
1075 MyAssert(!Coroutine_StackHasOverrun());
1076 Coroutines *cors = cor->coroutines;
1077 _Cor_Mutex_Lock(&cors->mutex);
1078 Coroutine_Err err = _Coroutine_Continue(cors, cor, value, early);
1079 _Cor_Mutex_Unlock(&cors->mutex);
1080 return err;
1081}
1082
1083
1084void *Coroutine_Yield(
1085 void *value,
1086 Coroutine_YieldCallback on_yield,
1087 void *yield_me
1088){
1089 MyAssert(g_c);
1090 Coroutine *me = g_c->active;
1091 MyAssert(me);
1092 MyAssert(!Coroutine_StackHasOverrun());
1093
1094 _Cor_Mutex_Lock(&g_c->mutex);
1095 Coroutines *cors = me->coroutines;
1096 MyAssert(me && me->state == Coroutine_Running && cors == g_c);
1097 me->stack_top = StackTopNow();
1098 me->value = value;
1099 me->state = Coroutine_Waiting;
1100
1101 Link_Remove(&me->link);
1102 if (!List_IsEmpty(&cors->runable)){
1103 _Cor_Mutex_Unlock(&cors->waiting_mutex);
1104 }
1105 List_AddTail(&cors->waiting, &me->link);
1106
1107 switch (setjmp(me->buf)){
1108 case Chunk_Initial:
1109 _Cor_Mutex_Unlock(&cors->mutex);
1110 on_yield(yield_me);
1111 Coroutine_RunNext();
1112 MyAssert(false);
1113 break;
1114 case Chunk_Create:
1115 MyAssert(me == g_c->tip);
1116 ReserveStackSpace(me->coroutines, me, me->stack_top - me->limit, NULL);
1117 MyAssert(false);
1118 break;
1119 case Chunk_Enter:
1120 // arrive here with mutex locked
1121 cors->active = me;
1122 MyAssert(!Coroutine_StackHasOverrun());
1123 // when we return here - we are running again
1124 MyAssert(me->state == Coroutine_Running);
1125 void *res = me->entry_param;
1126 _Cor_Mutex_Unlock(&cors->mutex);
1127 return res;
1128 }
1129 MyAssert(false);
1130 return NULL;
1131}
1132
1133
1134void *Coroutine_GetValue(
1135 Coroutine *cor
1136){
1137 return cor->value;
1138}
1139
1140
1141Coroutine *Coroutine_GetActive(void)
1142{
1143 return g_c ? g_c->active : NULL;
1144}
1145
1146
1147intptr_t Coroutine_GetStackHeadroom(void){
1148 Coroutine *me = g_c ? g_c->active : NULL;
1149 if (!me){
1150 // no active coroutine
1151 if (g_stack_limit){
1152 return StackTopNow() - g_stack_limit;
1153 } else {
1154 // no information where the stack ends - return something
1155 return COROUTINE_MINIMUM_STACK_SIZE;
1156 }
1157 }
1158 return StackTopNow() - me->limit;
1159}
1160
1161
1162// This is used to avoid compiler warnings about returning the address of a local
1163static inline void *StopAddressWarnings(void *p)
1164{
1165 return p;
1166}
1167
1168
1169void *Coroutine_GetStackHWM(void){
1170 MyAssert(g_c);
1171 MyAssert(g_c->state == Coroutines_Active);
1172 MyAssert(!Coroutine_StackHasOverrun());
1173 // Find where the guards end
1174 unsigned char *guard;
1175 for (guard = g_c->active->limit; Guard_Pattern_OK(guard); guard += 4){
1176 // do nothing
1177 }
1178 return guard;
1179}
1180
1181
1182void Coroutine_ClearStackForHWM(void){
1183 MyAssert(g_c);
1184 MyAssert(g_c->state == Coroutines_Active);
1185 MyAssert(!Coroutine_StackHasOverrun());
1186 unsigned char *end = StackTopNow() - GUARD_PATTERN_SIZE;
1187 for (unsigned char *guard = g_c->active->limit; guard <= end; guard += GUARD_PATTERN_SIZE){
1188 Apply_Guard(guard);
1189 }
1190}
1191
1192
1193static bool Coroutine_CanStartCoroutine_Lock_Assumed(
1194 size_t size
1195){
1196 if (!g_c->stack_limit){
1197 return true;
1198 }
1199
1200 if (!g_c->tip){
1201 return true;
1202 }
1203
1204 if (g_c->tip->state == Coroutine_Free){
1205 // last block is free
1206 if ((unsigned char *)g_c->tip - g_c->stack_limit >= (ptrdiff_t)(g_c->gap_after + size)){
1207 // enough room in free block, which is the last block
1208 return true;
1209 }
1210 } else {
1211 // last block is allocated
1212 if (g_c->tip->limit - g_c->stack_limit >= (ptrdiff_t)(g_c->gap_before + g_c->gap_after + size)){
1213 // enough room after the last block, which is allocated
1214 return true;
1215 }
1216 }
1217
1218 // not enough room between allocated blocks and stack limit, so check free list
1219 List_Link *link;
1220 for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
1221 Coroutine *cor = List_Link_Container(Coroutine, link, link);
1222 if (cor->size >= size){
1223 return true;
1224 }
1225 }
1226
1227 return false;
1228}
1229
1230
1231bool Coroutine_CanStartCoroutine(
1232 size_t size
1233){
1234 MyAssert(g_c);
1235 MyAssert(g_c->state == Coroutines_Started || g_c->state == Coroutines_Active);
1236 MyAssert(!Coroutine_StackHasOverrun());
1237
1238 _Cor_Mutex_Lock(&g_c->mutex);
1239
1240 bool result = Coroutine_CanStartCoroutine_Lock_Assumed(size);
1241
1242 _Cor_Mutex_Unlock(&g_c->mutex);
1243
1244 return result;
1245}
1246
1247void *Coroutine_GetCStackTop(void){
1248 MyAssert(!Coroutine_StackHasOverrun());
1249 if ((g_c->state == Coroutines_Started || g_c->state == Coroutines_Active) && g_c->tip != g_c->active) {
1250 return g_c->tip->stack_top;
1251 } else {
1252 return StackTopNow();
1253 }
1254}
1255
1256
1257static unsigned char *StackTopNow(void){
1258 unsigned char here[4];
1259 return StopAddressWarnings(here);
1260}
1261
1262
1263struct Coroutine_ChainParam {
1264 Coroutine_Start start;
1265 void *value;
1266 Coroutine *ret;
1267};
1268
1269
1270static void *Coroutine_ChainFn(
1271 void *param
1272){
1273 struct Coroutine_ChainParam *params = (struct Coroutine_ChainParam *)param;
1274 return (void *)(uintptr_t)Coroutine_Continue(params->ret, params->start(params->value), true);
1275}
1276
1277
1278static void Coroutine_ChainYield(
1279 void *unused
1280){
1281 (void)unused;
1282}
1283
1284
1285Coroutine_Err Coroutine_Chain(
1286 size_t size,
1287 Coroutine_Start start,
1288 void *value,
1289 void **result
1290){
1291 MyAssert(!Coroutine_StackHasOverrun());
1292 Coroutine *cor = Coroutine_New(size, Coroutine_ChainFn);
1293 if (!cor){
1294 // failed
1295 return Coroutine_Err_NoStack;
1296 }
1297 struct Coroutine_ChainParam params = {
1298 start,
1299 value,
1300 Coroutine_GetActive()
1301 };
1302 Coroutine_Err err = Coroutine_Continue(cor, &params, true);
1303 if (err){
1304 return err;
1305 }
1306 void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
1307 err = (Coroutine_Err)(uintptr_t)Coroutine_GetValue(cor);
1308 Coroutine_Delete(cor);
1309 if (!err && result){
1310 *result = res;
1311 }
1312 // success! ...probably
1313 return err;
1314}
1315
1316
1317bool Coroutine_IsRunning(
1318 Coroutine *cor
1319)
1320{
1321 int state = cor->state;
1322 return state == Coroutine_Running || state == Coroutine_Waiting;
1323}
1324
1325
1326bool Coroutine_IsComplete(
1327 Coroutine *cor
1328)
1329{
1330 int state = cor->state;
1331 return state == Coroutine_Complete;
1332}
1333
1334
1335bool Coroutine_IsStarted(void){
1336 return g_c && (g_c->state == Coroutines_Active || g_c->state == Coroutines_Started);
1337}
1338
1339void _Coroutine_Dump(void){
1340 char *state_to_text[] = {
1341 "Free",
1342 "Idle",
1343 "Running",
1344 "Waiting",
1345 "Complete"
1346 };
1347 unsigned idx = 0;
1348 List_Link *link;
1349 for (link = List_Begin(&g_c->all); Link_NextIsLink(link); link = Link_Next(link)){
1350 Coroutine *cor = List_Link_Container(Coroutine, all_link, link);
1351 printf("%d) %p (%s) %ld%s\n", idx++, cor, state_to_text[cor->state], cor->size, cor == g_c->tip ? " (TIP)" : "");
1352 }
1353}
1354