0 branches 0 tags
72
Fix assertion when setting stack limit
jonroach 29 Dec 2025 16:41
1 contributor
1105 lines29.4 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 unsigned char *guard; // the stack guard for the startup sequence
225 size_t gap_before; // bytes between previous's stack_top and next's Coroutine
226 size_t gap_after; // bytes between Coroutine and stack_base
227
228 // singletons
229 Coroutine *tip; // top of stack chunk
230 Coroutine *active; // currently running coroutine
231 Coroutine *primary; // Coroutine_Run coroutine
232 unsigned char *stack_limit; // when not NULL, where the stack finishes
233
234 // lists
235 List_Head all; // all Coroutines (in address order)
236 List_Head free; // free Coroutines
237 List_Head inactive; // idle or complete
238 List_Head runable; // running or waiting to run
239 List_Head waiting; // yielded / waiting to run
240 _Cor_Mutex waiting_mutex;
241
242 // Summary of the system
243 Coroutine_Report report;
244
245 // state
246 char state;
247};
248
249_Cor_thread_local Coroutines *g_c;
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
437 List_Init(&cors->all);
438 List_Init(&cors->free);
439 List_Init(&cors->inactive);
440 List_Init(&cors->runable);
441 List_Init(&cors->waiting);
442 _Cor_Mutex_ctor(&cors->waiting_mutex);
443 _Cor_Mutex_Lock(&cors->waiting_mutex);
444
445 cors->report.coroutines_created = 0;
446 cors->report.coroutines_pool_size = 0;
447 cors->report.largest_stack = 0;
448
449 // Charactersize the system...
450 if (!setjmp(cors->chunk_allocated)){
451 ReserveStackSpace(cors, NULL, COROUTINE_STARTUP_STACK_SIZE, NULL);
452 }
453 Coroutine *cor = List_Link_Container(Coroutine, link, List_GetHead(&cors->free));
454 cor->size = COROUTINE_STARTUP_STACK_SIZE;
455 if (!setjmp(cors->chunk_allocated)){
456 longjmp(cor->buf, Chunk_Create);
457 }
458 cors->gap_before = cor->prev_limit - (unsigned char *)cor;
459 cors->gap_after = (unsigned char *)cor - cor->base;
460 // ...charactersize the system
461
462 // discard what we've just created
463 List_Init(&cors->all);
464 List_Init(&cors->free);
465 cors->tip = NULL;
466
467 cors->state = Coroutines_Started;
468
469 g_c = cors;
470}
471
472
473void Coroutine_SetStackLimit(void *limit){
474 assert(g_c);
475 assert(!limit || !(g_c->state == Coroutines_Started || g_c->state == Coroutines_Active) || (unsigned char *)limit < (unsigned char *)g_c->tip || !g_c->tip);
476 g_c->stack_limit = limit;
477}
478
479
480Coroutine_Report Coroutine_StopSystem(void)
481{
482 assert(g_c);
483 assert(g_c->state == Coroutines_Started);
484 _Cor_Mutex_Lock(&g_c->mutex);
485 g_c->state = Coroutines_Stopping;
486
487 uintptr_t stackminheadroom;
488#if COROUTINE_RECORD_LOWEST_HEADROOM
489 stackminheadroom = g_c->report.largest_stack;
490 for (List_Link *link = g_c->free.fwd.link.next; Link_NextIsLink(link); link = Link_Next(link)){
491 Coroutine *cor = List_Link_Container(Coroutine, link, link);
492 if (cor->guard){
493 for (uintptr_t i = 4; i < cor->size-3; i += 4){
494 if (!Check_Guard(&cor->guard[i])){
495 stackminheadroom = i < stackminheadroom ? i : stackminheadroom;
496 break;
497 }
498 }
499 }
500 }
501#else
502 stackminheadroom = 0;
503#endif
504 g_c->report.lowest_headroom = stackminheadroom;
505
506 assert(List_IsEmpty(&g_c->inactive));
507 _Cor_Mutex_Unlock(&g_c->waiting_mutex);
508 _Cor_Mutex_dtor(&g_c->waiting_mutex);
509
510 assert(g_c->state == Coroutines_Stopping);
511 _Cor_Mutex_Unlock(&g_c->mutex);
512 _Cor_Mutex_dtor(&g_c->mutex);
513
514 Coroutine_Report ret = g_c->report;
515
516 _Cor_Free(g_c);
517 g_c = NULL;
518
519 return ret;
520}
521
522
523void Coroutine_Run_Coroutine(
524 Coroutine *cor,
525 void *value
526){
527 Coroutines *cors = cor->coroutines;
528
529 // Can't Coroutine_Run_Coroutine() off-thread
530 assert(g_c == cors);
531
532 _Cor_Mutex_Lock(&cors->mutex);
533 assert(cors->state == Coroutines_Started);
534 cors->state = Coroutines_Active;
535 cors->primary = cor;
536
537 _Coroutine_Continue(cor, value, true);
538
539 if (!setjmp(cors->controller)){
540 _Cor_Mutex_Unlock(&cors->mutex);
541
542 // check the guard
543 assert(Check_Guard(cors->guard));
544
545 // start the first coroutine
546 Coroutine_RunNext();
547 }
548 // arrive here with mutex locked
549 assert(List_IsEmpty(&cors->runable));
550 assert(List_IsEmpty(&cors->waiting));
551 assert(cors->state == Coroutines_Active);
552 cors->state = Coroutines_Started;
553 _Cor_Mutex_Unlock(&cors->mutex);
554}
555
556
557bool Coroutine_Run(
558 size_t stack,
559 Coroutine_Start start,
560 void *value,
561 void **result
562){
563 if (g_c && g_c->active){
564 void *res = start(value);
565 if (result){
566 *result = res;
567 }
568 // no failures, so...
569 return false;
570 }
571 assert(!g_c || g_c->state == Coroutines_Started);
572 bool need_start = !g_c;
573 if (need_start){
574 Coroutine_StartSystem();
575 }
576 Coroutine *cor = Coroutine_New(stack, start);
577 if (!cor){
578 // that didn't work
579 return true;
580 }
581 Coroutine_Run_Coroutine(cor, value);
582 if (result){
583 *result = Coroutine_GetValue(cor);
584 }
585 Coroutine_Delete(cor);
586 if (need_start){
587 Coroutine_StopSystem();
588 }
589 // no failures, so...
590 return false;
591}
592
593
594static void Coroutine_FreeToIdle(
595 Coroutine *cor,
596 Coroutine_Start start
597){
598 assert(cor->state == Coroutine_Free);
599 cor->state = Coroutine_Idle;
600 cor->start = start;
601 cor->value = NULL;
602 Link_Remove(&cor->link);
603 List_AddHead(&g_c->inactive, &cor->link);
604
605 g_c->report.coroutines_created += 1;
606}
607
608
609static void Coroutine_FreeToIdleSize(
610 Coroutine *cor,
611 Coroutine_Start start,
612 size_t size
613){
614 assert(!cor->guard);
615 cor->size = size;
616 cor->base = (unsigned char *)cor - g_c->gap_after;
617 cor->limit = cor->base - cor->size;
618 Coroutine_FreeToIdle(cor, start);
619}
620
621
622static Coroutine *Coroutine_New_Lock_Assumed(
623 size_t size,
624 Coroutine_Start start
625){
626 List_Link *link;
627
628 if (!g_c->tip){
629 // no tip - time to create one
630
631 // we're the non-Coroutine which starts the Coroutine system.
632 // Add a single free block
633 if (!setjmp(g_c->chunk_allocated)){
634 ReserveStackSpace(g_c, NULL, COROUTINE_STARTUP_STACK_SIZE, NULL);
635 }
636 }
637
638 Coroutine *cor = NULL;
639 for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
640 Coroutine *candidate = List_Link_Container(Coroutine, link, link);
641 if (!candidate->guard) {
642 // this must be the tip
643 assert(candidate == g_c->tip);
644
645 // If this is the only Coroutine in the system, go ahead and use it regardless of size.
646 // Note: there can only be one free block if there's no other sort of blocks as we merge on free
647 if (List_IsEmpty(&g_c->inactive) &&
648 List_IsEmpty(&g_c->runable) &&
649 List_IsEmpty(&g_c->waiting) ){
650 if (g_c->stack_limit){
651 size_t available = (unsigned char *)candidate - g_c->stack_limit - g_c->gap_after;
652 size = available < size ? available : size;
653 }
654 Coroutine_FreeToIdleSize(candidate, start, size);
655 return candidate;
656 }
657
658 // Not the only coroutine in the system - check size
659 if (g_c->stack_limit){
660 // there's a limit - see what that space allows....
661 size_t available = (unsigned char *)candidate - g_c->stack_limit - g_c->gap_after;
662
663 if (available < size){
664 // not enough space for this coroutine
665 return NULL;
666 }
667
668 if (available >= size + g_c->gap_before + g_c->gap_after + COROUTINE_MINIMUM_STACK_SIZE) {
669 // not enough space for another coroutine - use all the space for this one
670 size = available;
671 }
672 }
673 Coroutine_FreeToIdleSize(candidate, start, size);
674 return candidate;
675 }
676 if (candidate->size >= size && candidate > cor){
677 // chunk big enough, and a better choice than cor
678 cor = candidate;
679 }
680 }
681
682 if (cor){
683 // - work out whether we're splitting or using the whole chunk
684 if (cor->size >= size + g_c->gap_before + g_c->gap_after + COROUTINE_MINIMUM_STACK_SIZE){
685 // enough space for a second coroutine so split this free block
686 cor->size = size;
687 if (!setjmp(g_c->chunk_allocated)){
688 longjmp(cor->buf, Chunk_Split);
689 }
690 }
691 // cor now ready to use
692 Coroutine_FreeToIdle(cor, start);
693 return cor;
694 }
695
696 // No big-enough free blocks - check if there's space beyond the tip block
697
698 if (g_c->stack_limit && g_c->stack_limit > (unsigned char *)g_c->tip->limit - sizeof(Coroutine) - size){
699 // no space for a new stack block
700 return NULL;
701 }
702 Coroutine *tip = g_c->tip;
703 Coroutine *me = g_c->active;
704 if (tip == me) {
705 if (!setjmp(g_c->chunk_allocated)){
706 ReserveStackSpace(g_c, me, StackTopNow() - me->limit, NULL);
707 }
708 } else {
709 if (!setjmp(g_c->chunk_allocated)){
710 longjmp(tip->buf, Chunk_Create);
711 }
712 }
713
714 cor = List_Link_Container(Coroutine, link, List_GetTail(&g_c->free));
715 assert(cor->state == Coroutine_Free);
716 cor->size = size;
717 cor->limit = (unsigned char *)cor - g_c->gap_after - size;
718 cor->state = Coroutine_Idle;
719 cor->start = start;
720 cor->value = NULL;
721 Link_Remove(&cor->link);
722 List_AddHead(&g_c->inactive, &cor->link);
723
724 g_c->report.coroutines_created += 1;
725 return cor;
726}
727
728
729Coroutine *Coroutine_New(
730 size_t stack,
731 Coroutine_Start start
732){
733 assert(g_c);
734 assert((g_c->state == Coroutines_Started && List_IsEmpty(&g_c->inactive)) || g_c->state == Coroutines_Active);
735 assert(!Coroutine_StackHasOverrun());
736
737 _Cor_Mutex_Lock(&g_c->mutex);
738
739 Coroutine *cor = Coroutine_New_Lock_Assumed(stack, start);
740
741 if (cor && cor->size > g_c->report.largest_stack){
742 g_c->report.largest_stack = cor->size;
743 }
744
745 _Cor_Mutex_Unlock(&g_c->mutex);
746
747 return cor;
748}
749
750
751void Coroutine_Delete(
752 Coroutine *cor
753){
754 assert(!Coroutine_StackHasOverrun());
755 if (cor){
756 Coroutines *cors = cor->coroutines;
757 _Cor_Mutex_Lock(&cors->mutex);
758 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Complete);
759 cor->state = Coroutine_Free;
760 Link_Remove(&cor->link);
761
762 // insert into free list
763 List_AddHead(&cors->free, &cor->link);
764
765 // Check for merge with following Coroutine
766 List_Link *link = Link_Next(&cor->all_link);
767 if (Link_NextIsLink(link)){
768 Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
769 if (listcor->state == Coroutine_Free){
770 // merge
771 cor->size += cor->limit - listcor->limit;
772 cor->limit = listcor->limit;
773 cor->guard = listcor->guard;
774 Link_Remove(&listcor->all_link);
775 Link_Remove(&listcor->link);
776 if (g_c->tip == listcor){
777 g_c->tip = cor;
778 }
779 }
780 }
781
782 // check for merge with prev coroutine
783 link = Link_Prev(&cor->all_link);
784 if (Link_PrevIsLink(link)){
785 Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
786 if (listcor->state == Coroutine_Free){
787 // merge
788 listcor->size += listcor->limit - cor->limit;
789 listcor->limit = cor->limit;
790 listcor->guard = cor->guard;
791 Link_Remove(&cor->all_link);
792 Link_Remove(&cor->link);
793 if (g_c->tip == cor){
794 g_c->tip = listcor;
795 }
796 }
797 }
798
799 _Cor_Mutex_Unlock(&cors->mutex);
800 }
801}
802
803
804// Coroutine_Continue, assuming the mutex is claimed
805static void _Coroutine_Continue(
806 Coroutine *cor,
807 void *value,
808 bool early
809){
810 Coroutines *cors = cor->coroutines;
811 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Waiting);
812 cor->entry_param = value;
813 cor->state = Coroutine_Running;
814 Link_Remove(&cor->link);
815 if ( early ) {
816 List_AddHead(&cors->runable, &cor->link);
817 } else {
818 List_AddTail(&cors->runable, &cor->link);
819 }
820 _Cor_Mutex_Unlock(&cors->waiting_mutex);
821}
822
823
824void Coroutine_Continue(
825 Coroutine *cor,
826 void *value,
827 bool early
828){
829 assert(!Coroutine_StackHasOverrun());
830 Coroutines *cors = cor->coroutines;
831 _Cor_Mutex_Lock(&cors->mutex);
832 _Coroutine_Continue(cor, value, early);
833 _Cor_Mutex_Unlock(&cors->mutex);
834}
835
836
837void *Coroutine_Yield(
838 void *value,
839 Coroutine_YieldCallback on_yield,
840 void *yield_me
841){
842 assert(g_c);
843 Coroutine *me = g_c->active;
844 assert(me);
845 assert(!Coroutine_StackHasOverrun());
846
847 _Cor_Mutex_Lock(&g_c->mutex);
848 Coroutines *cors = me->coroutines;
849 assert(me && me->state == Coroutine_Running && cors == g_c);
850 me->stack_top = StackTopNow();
851 me->value = value;
852 me->state = Coroutine_Waiting;
853
854 Link_Remove(&me->link);
855 if (!List_IsEmpty(&cors->runable)){
856 _Cor_Mutex_Unlock(&cors->waiting_mutex);
857 }
858 List_AddTail(&cors->waiting, &me->link);
859
860 switch (setjmp(me->buf)){
861 case Chunk_Initial:
862 _Cor_Mutex_Unlock(&cors->mutex);
863 on_yield(yield_me);
864 Coroutine_RunNext();
865 assert(false);
866 case Chunk_Create:
867 assert(me == g_c->tip);
868 ReserveStackSpace(me->coroutines, me, me->stack_top - me->limit, NULL);
869 assert(false);
870 case Chunk_Enter:
871 // arrive here with mutex locked
872 cors->active = me;
873 assert(!Coroutine_StackHasOverrun());
874 // when we return here - we are running again
875 assert(me->state == Coroutine_Running);
876 void *res = me->entry_param;
877 _Cor_Mutex_Unlock(&cors->mutex);
878 return res;
879 }
880 return NULL;
881}
882
883
884void *Coroutine_GetValue(
885 Coroutine *cor
886){
887 return cor->value;
888}
889
890
891Coroutine *Coroutine_GetActive(void)
892{
893 return g_c ? g_c->active : NULL;
894}
895
896
897intptr_t Coroutine_GetStackHeadroom(void){
898 assert(g_c);
899 assert(!Coroutine_StackHasOverrun());
900 Coroutine *me = g_c->active;
901 if (!me){
902 // no active coroutine
903 unsigned char *stack_limit = g_c->stack_limit;
904 if (stack_limit){
905 // no stack limit - assume we'll use COROUTINE_STACK_SIZE
906 return StackTopNow() - stack_limit;
907 } else {
908 // no information where the stack ends - return something
909 return COROUTINE_MINIMUM_STACK_SIZE;
910 }
911 }
912 return StackTopNow() - me->limit;
913}
914
915
916// This is used to avoid compiler warnings about returning the address of a local
917static inline void *StopAddressWarnings(void *p)
918{
919 return p;
920}
921
922
923void *Coroutine_GetStackHWM(void){
924 assert(g_c);
925 assert(g_c->state == Coroutines_Active);
926 assert(!Coroutine_StackHasOverrun());
927 // Find where the guards end
928 unsigned char *guard;
929 for (guard = g_c->active->guard; Check_Guard(guard); guard += 4){
930 // do nothing
931 }
932 return guard;
933}
934
935
936void Coroutine_ClearStackForHWM(void){
937 assert(g_c);
938 assert(g_c->state == Coroutines_Active);
939 assert(!Coroutine_StackHasOverrun());
940 unsigned char *end = StackTopNow() - GUARD_PATTERN_SIZE;
941 for (unsigned char *guard = g_c->active->guard+GUARD_PATTERN_SIZE; guard <= end; guard += GUARD_PATTERN_SIZE){
942 Apply_Guard(guard);
943 }
944}
945
946
947static bool Coroutine_CanStartCoroutine_Lock_Assumed(
948 size_t size
949){
950 assert(g_c);
951 assert(g_c->state == Coroutines_Started || g_c->state == Coroutines_Active);
952 assert(!Coroutine_StackHasOverrun());
953
954 if (!g_c->stack_limit){
955 return true;
956 }
957
958 if (!g_c->tip){
959 return true;
960 }
961
962 if (g_c->tip->state == Coroutine_Free){
963 // last block is free
964 if ((unsigned char *)g_c->tip - g_c->stack_limit >= (ptrdiff_t)(g_c->gap_after + size)){
965 // enough room in free block, which is the last block
966 return true;
967 }
968 } else {
969 // last block is allocated
970 if (g_c->tip->limit - g_c->stack_limit >= (ptrdiff_t)(g_c->gap_before + g_c->gap_after + size)){
971 // enough room after the last block, which is allocated
972 return true;
973 }
974 }
975
976 // not enough room between allocated blocks and stack limit, so check free list
977 List_Link *link;
978 for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
979 Coroutine *cor = List_Link_Container(Coroutine, link, link);
980 if (cor->size >= size){
981 return true;
982 }
983 }
984
985 return false;
986}
987
988
989bool Coroutine_CanStartCoroutine(
990 size_t size
991){
992 _Cor_Mutex_Lock(&g_c->mutex);
993
994 bool result = Coroutine_CanStartCoroutine_Lock_Assumed(size);
995
996 _Cor_Mutex_Unlock(&g_c->mutex);
997
998 return result;
999}
1000
1001void *Coroutine_GetCStackTop(void){
1002 assert(!Coroutine_StackHasOverrun());
1003 if ((g_c->state == Coroutines_Started || g_c->state == Coroutines_Active) && g_c->tip != g_c->active) {
1004 return g_c->tip->stack_top;
1005 } else {
1006 return StackTopNow();
1007 }
1008}
1009
1010
1011static unsigned char *StackTopNow(void){
1012 unsigned char here[4];
1013 return StopAddressWarnings(here);
1014}
1015
1016
1017struct Coroutine_ChainParam {
1018 Coroutine_Start start;
1019 void *value;
1020 Coroutine *ret;
1021};
1022
1023
1024static void *Coroutine_ChainFn(
1025 void *param
1026){
1027 struct Coroutine_ChainParam *params = (struct Coroutine_ChainParam *)param;
1028 Coroutine_Continue(params->ret, params->start(params->value), true);
1029 return NULL;
1030}
1031
1032
1033static void Coroutine_ChainYield(
1034 void *unused
1035){
1036 (void)unused;
1037}
1038
1039
1040bool Coroutine_Chain(
1041 size_t size,
1042 Coroutine_Start start,
1043 void *value,
1044 void **result
1045){
1046 assert(Check_Guard(Coroutine_GetActive()->guard));
1047 Coroutine *cor = Coroutine_New(size, Coroutine_ChainFn);
1048 if (!cor){
1049 // failed
1050 return true;
1051 }
1052 struct Coroutine_ChainParam params = {
1053 start,
1054 value,
1055 Coroutine_GetActive()
1056 };
1057 Coroutine_Continue(cor, &params, true);
1058 void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
1059 Coroutine_Delete(cor);
1060 if (result){
1061 *result = res;
1062 }
1063 // success!
1064 return false;
1065}
1066
1067
1068bool Coroutine_IsRunning(
1069 Coroutine *cor
1070)
1071{
1072 int state = cor->state;
1073 return state == Coroutine_Running || state == Coroutine_Waiting;
1074}
1075
1076
1077bool Coroutine_IsComplete(
1078 Coroutine *cor
1079)
1080{
1081 int state = cor->state;
1082 return state == Coroutine_Complete;
1083}
1084
1085
1086bool Coroutine_IsStarted(void){
1087 return g_c && (g_c->state == Coroutines_Active || g_c->state == Coroutines_Started);
1088}
1089
1090void _Coroutine_Dump(void){
1091 char *state_to_text[] = {
1092 "Free",
1093 "Idle",
1094 "Running",
1095 "Waiting",
1096 "Complete"
1097 };
1098 unsigned idx = 0;
1099 List_Link *link;
1100 for (link = List_Begin(&g_c->all); Link_NextIsLink(link); link = Link_Next(link)){
1101 Coroutine *cor = List_Link_Container(Coroutine, all_link, link);
1102 printf("%d) %p (%s) %ld%s\n", idx++, cor, state_to_text[cor->state], cor->size, cor == g_c->tip ? " (TIP)" : "");
1103 }
1104}
1105