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