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