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