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