0 branches 0 tags
80
Add Coroutine_GetReport
jonroach 19 Feb 2026 12:49
1 contributor
1223 lines33.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
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
276#ifndef NDEBUG
277static void CheckListIntegrity(List_Head *head, Coroutine_State state1, Coroutine_State state2){
278 for (List_Link *link = List_Begin(head); Link_NextIsLink(link); link = Link_Next(link)){
279 Coroutine *candidate = List_Link_Container(Coroutine, link, link);
280 assert(candidate->coroutines == g_c);
281 assert(candidate->state == state1 || candidate->state == state2);
282 bool found = false;
283 for (List_Link *link = List_Begin(&g_c->all); Link_NextIsLink(link); link = Link_Next(link)){
284 Coroutine *candidate2 = List_Link_Container(Coroutine, all_link, link);
285 if (candidate == candidate2){
286 found = true;
287 }
288 }
289 assert(found);
290 }
291}
292#endif
293
294
295void Coroutine_CheckIntegrity(void){
296#ifndef NDEBUG
297 CheckListIntegrity(&g_c->free, Coroutine_Free, Coroutine_Free);
298 CheckListIntegrity(&g_c->inactive, Coroutine_Idle, Coroutine_Complete);
299 CheckListIntegrity(&g_c->runable, Coroutine_Running, Coroutine_Running);
300 CheckListIntegrity(&g_c->waiting, Coroutine_Waiting, Coroutine_Waiting);
301#endif
302}
303
304
305#ifndef NDEBUG
306static bool Coroutine_StackHasOverrun(void){
307 unsigned char *stack_top = StackTopNow();
308 unsigned char *stack_limit = g_c ? g_c->stack_limit : NULL;
309 if (stack_limit && stack_top < stack_limit){
310 // printf("top %p < limit %p\n", stack_top, stack_limit);
311 // current stack top is beyond limit - we are overrunning NOW
312 return true;
313 }
314 // if (stack_limit && stack_top < stack_limit+2048){
315 // printf("Stack LOW hazard\n");
316 // }
317 Coroutine *me = g_c ? g_c->active : NULL;
318 if (!me){
319 return false;
320 }
321#if COROUTINE_CHECK_INTEGRITY_ON_STACK_CHECK
322 // Check all coroutines integrity
323 Coroutine_CheckIntegrity();
324#endif
325 if (me->guard){
326 bool ret = !Check_Guard(me->guard);
327 // if (ret){
328 // printf("Broken guard me=%p; me->guard=%p me->limit-%p stack top=%p\n", me, me->guard, me->limit, stack_top);
329 // }
330 return ret;
331 }
332 bool ret = stack_top < me->limit;
333 // if (ret){
334 // printf("stack top %p < me->limit %p\n", stack_top, me->limit);
335 // }
336 return ret;
337}
338#endif
339
340
341static void ReserveStackSpace(
342 Coroutines *cors,
343 Coroutine *parent,
344 size_t chunk_size,
345 unsigned char *childs_limit
346){
347 unsigned char *chunk_of_stack = alloca(chunk_size);
348#if COROUTINE_RECORD_LOWEST_HEADROOM
349 for (size_t i = 0; i <= chunk_size-GUARD_PATTERN_SIZE; i += GUARD_PATTERN_SIZE){
350 Apply_Guard(&chunk_of_stack[i]);
351 }
352#else
353 Apply_Guard(chunk_of_stack);
354#endif
355 if (parent){
356 parent->guard = chunk_of_stack;
357 parent->limit = chunk_of_stack;
358 parent->base = chunk_of_stack + chunk_size;
359 }
360 stack_chunk_base(cors, parent, chunk_of_stack, childs_limit);
361}
362
363
364static void stack_chunk_base(
365 Coroutines *cors,
366 Coroutine *parent,
367 unsigned char *prev_limit,
368 unsigned char *limit
369){
370 Coroutine here;
371 here.coroutines = cors;
372 here.state = Coroutine_Free;
373 here.prev_limit = prev_limit;
374 here.size = 0;
375 here.base = NULL;
376 here.guard = limit;
377 here.limit = limit;
378 if (limit){
379 here.base = (unsigned char *)&here - cors->gap_after;
380 here.size = here.base - here.limit;
381 Apply_Guard(limit);
382 }
383
384 // insert into all list
385 if (parent){
386 Link_AddAfter(&here.all_link, &parent->all_link);
387 } else {
388 List_AddHead(&cors->all, &here.all_link);
389 }
390 // add to free list
391 List_AddTail(&cors->free, &here.link);
392
393 cors->report.coroutines_pool_size += 1;
394
395 if (!cors->tip || &here < cors->tip){
396 cors->tip = &here;
397 }
398
399 for(;;){
400 switch (setjmp(here.buf)) {
401 case Chunk_Initial:
402 if (here.state == Coroutine_Free){
403 // return to the coroutine allocator
404 longjmp(cors->chunk_allocated, 1);
405 } else {
406 assert(here.state == Coroutine_Complete);
407 // we finish here to ensure the setjmp is redone
408 if (cors->primary == &here) {
409 // if primary coroutine - return to Coroutine_Run
410 longjmp(cors->controller, Coroutines_CoroutineComplete);
411 }
412 _Cor_Mutex_Unlock(&cors->mutex);
413 Coroutine_RunNext();
414 assert(false);
415 }
416 case Chunk_Create:
417 // Request to create a new chunk on the stack
418 // We're here if the coroutine is:
419 // Allocated, but not 'run' (Coroutine_Idle)
420 // Run, but not not entered yet (Coroutine_Running)
421 // Completed (Coroutine_Complete)
422 // Free, and the coroutines system is starting - we're characterising the system
423 assert(here.state == Coroutine_Idle ||
424 here.state == Coroutine_Running ||
425 here.state == Coroutine_Complete ||
426 (here.state == Coroutine_Free && cors->state == Coroutines_Starting));
427 ReserveStackSpace(here.coroutines, &here, here.size, NULL);
428 assert(false);
429 case Chunk_Split:
430 // Request to split this free block into two
431 // here.size will be set to our shorter size
432 ReserveStackSpace(here.coroutines, &here, here.size, here.limit);
433 assert(false);
434 case Chunk_Enter:
435 // request to start a coroutine (ie use the chunk for a coroutine)
436 // arrive here with mutex locked
437 assert(here.state == Coroutine_Running);
438 here.coroutines->active = &here;
439 _Cor_Mutex_Unlock(&cors->mutex);
440 here.value = here.start(here.entry_param);
441
442 // check the guard
443 assert(Check_Guard(here.guard));
444
445 _Cor_Mutex_Lock(&here.coroutines->mutex);
446 here.coroutines->active = NULL;
447 assert(here.state == Coroutine_Running);
448 Link_Remove(&here.link);
449 here.state = Coroutine_Complete;
450 List_AddTail(&here.coroutines->inactive, &here.link);
451 // Coroutine has completed
452 // Loop round to redo the setjmp() - if this coroutine yielded, then the setjmp will
453 // need reseting
454 }
455 }
456}
457
458
459static void Coroutine_RunNext(void)
460{
461 // arrive here with mutex unlocked
462 _Cor_Mutex_Lock(&g_c->waiting_mutex);
463 _Cor_Mutex_Lock(&g_c->mutex);
464 Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c->runable));
465 assert(next->state == Coroutine_Running);
466 longjmp(next->buf, Chunk_Enter);
467 assert(false);
468}
469
470
471void Coroutine_StartSystem(void)
472{
473 assert(!g_c);
474
475 Coroutines *cors = _Cor_Malloc(sizeof(*g_c));
476 assert(cors);
477
478 cors->state = Coroutines_Starting;
479 _Cor_Mutex_ctor(&cors->mutex);
480
481 cors->tip = NULL;
482 cors->active = NULL;
483 cors->primary = NULL;
484 cors->stack_limit = g_stack_limit;
485
486 List_Init(&cors->all);
487 List_Init(&cors->free);
488 List_Init(&cors->inactive);
489 List_Init(&cors->runable);
490 List_Init(&cors->waiting);
491 _Cor_Mutex_ctor(&cors->waiting_mutex);
492 _Cor_Mutex_Lock(&cors->waiting_mutex);
493
494 cors->report.coroutines_created = 0;
495 cors->report.coroutines_pool_size = 0;
496 cors->report.largest_stack = 0;
497
498 // Charactersize the system...
499 if (!setjmp(cors->chunk_allocated)){
500 ReserveStackSpace(cors, NULL, COROUTINE_STARTUP_STACK_SIZE, NULL);
501 }
502 Coroutine *cor = List_Link_Container(Coroutine, link, List_GetHead(&cors->free));
503 cor->size = COROUTINE_STARTUP_STACK_SIZE;
504 if (!setjmp(cors->chunk_allocated)){
505 longjmp(cor->buf, Chunk_Create);
506 }
507 cors->gap_before = cor->prev_limit - (unsigned char *)cor;
508 cors->gap_after = (unsigned char *)cor - cor->base;
509 // ...charactersize the system
510
511 // discard what we've just created
512 List_Init(&cors->all);
513 List_Init(&cors->free);
514 cors->tip = NULL;
515
516 cors->state = Coroutines_Started;
517
518 g_c = cors;
519}
520
521
522void Coroutine_SetStackLimit(void *limit){
523 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);
524 g_stack_limit = limit;
525 if (g_c){
526 g_c->stack_limit = limit;
527 }
528}
529
530
531#if COROUTINE_RECORD_LOWEST_HEADROOM
532static size_t Coroutine_UpdateMinimumHeadroom(List_Head *list, size_t headroom)
533{
534 for (List_Link *link = List_Begin(list); Link_NextIsLink(link); link = Link_Next(link)){
535 Coroutine *cor = List_Link_Container(Coroutine, link, link);
536 if (cor->guard){
537 for (uintptr_t i = 4; i < cor->size-3; i += 4){
538 if (!Check_Guard(&cor->guard[i])){
539 headroom = i < headroom ? i : headroom;
540 break;
541 }
542 }
543 }
544 }
545 return headroom;
546}
547#endif
548
549
550Coroutine_Report Coroutine_GetReport(void)
551{
552 assert(g_c);
553 assert(g_c->state == Coroutines_Started);
554
555 size_t headroom;
556#if COROUTINE_RECORD_LOWEST_HEADROOM
557 _Cor_Mutex_Lock(&g_c->mutex);
558 headroom = g_c->report.lowest_headroom;
559 headroom = Coroutine_UpdateMinimumHeadroom(&g_c->inactive, headroom);
560 headroom = Coroutine_UpdateMinimumHeadroom(&g_c->runable, headroom);
561 headroom = Coroutine_UpdateMinimumHeadroom(&g_c->waiting, headroom);
562 _Cor_Mutex_Unlock(&g_c->mutex);
563#else
564 headroom = 0;
565#endif
566 g_c->report.lowest_headroom = headroom;
567
568 return g_c->report;
569}
570
571
572void Coroutine_StopSystem(void)
573{
574 assert(g_c);
575 assert(g_c->state == Coroutines_Started);
576 _Cor_Mutex_Lock(&g_c->mutex);
577 g_c->state = Coroutines_Stopping;
578
579 assert(List_IsEmpty(&g_c->inactive));
580 _Cor_Mutex_Unlock(&g_c->waiting_mutex);
581 _Cor_Mutex_dtor(&g_c->waiting_mutex);
582
583 assert(g_c->state == Coroutines_Stopping);
584 _Cor_Mutex_Unlock(&g_c->mutex);
585 _Cor_Mutex_dtor(&g_c->mutex);
586
587 _Cor_Free(g_c);
588 g_c = NULL;
589}
590
591
592#ifndef NDEBUG
593static void Coroutine_ReportNonEmptyList(
594 List_Head const *head,
595 char const *tag
596){
597 List_Link *link;
598 for (link = List_Begin(head); Link_NextIsLink(link); link = Link_Next(link)){
599 Coroutine *cor = List_Link_Container(Coroutine, link, link);
600 printf("%s: %p %p %p\n", tag, cor, cor->start, cor->entry_param);
601 }
602}
603#endif
604
605void Coroutine_Run_Coroutine(
606 Coroutine *cor,
607 void *value
608){
609 Coroutines *cors = cor->coroutines;
610
611 // Can't Coroutine_Run_Coroutine() off-thread
612 assert(g_c == cors);
613
614 _Cor_Mutex_Lock(&cors->mutex);
615 assert(cors->state == Coroutines_Started);
616 cors->state = Coroutines_Active;
617 cors->primary = cor;
618
619 _Coroutine_Continue(cors, cor, value, true);
620
621 if (!setjmp(cors->controller)){
622 _Cor_Mutex_Unlock(&cors->mutex);
623
624 // start the first coroutine
625 Coroutine_RunNext();
626 }
627 // arrive here with mutex locked
628#ifndef NDEBUG
629 if (!List_IsEmpty(&cors->runable) || !List_IsEmpty(&cors->waiting)){
630 Coroutine_ReportNonEmptyList(&cors->runable, "runable");
631 Coroutine_ReportNonEmptyList(&cors->waiting, "waiting");
632 assert(false);
633 }
634#endif
635 assert(cors->state == Coroutines_Active);
636 cors->state = Coroutines_Started;
637 _Cor_Mutex_Unlock(&cors->mutex);
638}
639
640
641bool Coroutine_Run(
642 size_t stack,
643 Coroutine_Start start,
644 void *value,
645 void **result
646){
647 if (g_c && g_c->active){
648 assert(!Coroutine_StackHasOverrun());
649 void *res = start(value);
650 if (result){
651 *result = res;
652 }
653 // no failures, so...
654 return false;
655 }
656 assert(!g_c || g_c->state == Coroutines_Started);
657 bool need_start = !g_c;
658 if (need_start){
659 Coroutine_StartSystem();
660 }
661 Coroutine *cor = Coroutine_New(stack, start);
662 if (!cor){
663 // that didn't work
664 return true;
665 }
666 Coroutine_Run_Coroutine(cor, value);
667 if (result){
668 *result = Coroutine_GetValue(cor);
669 }
670 Coroutine_Delete(cor);
671 if (need_start){
672 Coroutine_StopSystem();
673 }
674 // no failures, so...
675 return false;
676}
677
678
679static void Coroutine_FreeToIdle(
680 Coroutine *cor,
681 Coroutine_Start start
682){
683 assert(cor->state == Coroutine_Free);
684 cor->state = Coroutine_Idle;
685 cor->start = start;
686 cor->value = NULL;
687 Link_Remove(&cor->link);
688 List_AddHead(&g_c->inactive, &cor->link);
689
690 g_c->report.coroutines_created += 1;
691}
692
693
694static void Coroutine_FreeToIdleSize(
695 Coroutine *cor,
696 Coroutine_Start start,
697 size_t size
698){
699 assert(!cor->guard);
700 cor->size = size;
701 cor->base = (unsigned char *)cor - g_c->gap_after;
702 cor->limit = cor->base - cor->size;
703 Coroutine_FreeToIdle(cor, start);
704}
705
706
707static Coroutine *Coroutine_New_Lock_Assumed(
708 size_t size,
709 Coroutine_Start start
710){
711 List_Link *link;
712
713 if (!g_c->tip){
714 // no tip - time to create one
715
716 // we're the non-Coroutine which starts the Coroutine system.
717 // Add a single free block
718 if (!setjmp(g_c->chunk_allocated)){
719 ReserveStackSpace(g_c, NULL, COROUTINE_STARTUP_STACK_SIZE, NULL);
720 }
721 }
722
723 Coroutine *cor = NULL;
724 for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
725 Coroutine *candidate = List_Link_Container(Coroutine, link, link);
726 assert(candidate->coroutines == g_c);
727 if (!candidate->guard) {
728 // this must be the tip
729 assert(candidate == g_c->tip);
730
731 // If this is the only Coroutine in the system, go ahead and use it regardless of size.
732 // Note: there can only be one free block if there's no other sort of blocks as we merge on free
733 if (List_IsEmpty(&g_c->inactive) &&
734 List_IsEmpty(&g_c->runable) &&
735 List_IsEmpty(&g_c->waiting) ){
736 if (g_c->stack_limit){
737 size_t available = (unsigned char *)candidate - g_c->stack_limit - g_c->gap_after;
738 size = available < size ? available : size;
739 }
740 Coroutine_FreeToIdleSize(candidate, start, size);
741 return candidate;
742 }
743
744 // Not the only coroutine in the system - check size
745 if (g_c->stack_limit){
746 // there's a limit - see what that space allows....
747 size_t available = (unsigned char *)candidate - g_c->stack_limit - g_c->gap_after;
748
749 if (available < size){
750 // not enough space for this coroutine
751 // printf("Not enough stack space (A) %ld\n", available);
752 return NULL;
753 }
754
755 if (available < size + g_c->gap_before + g_c->gap_after + COROUTINE_MINIMUM_STACK_SIZE) {
756 // not enough space for another coroutine - use all the space for this one
757 size = available;
758 }
759 }
760 Coroutine_FreeToIdleSize(candidate, start, size);
761 return candidate;
762 }
763 if (candidate->size >= size && candidate > cor){
764 // chunk big enough, and a better choice than cor
765 cor = candidate;
766 }
767 }
768
769 if (cor){
770 // - work out whether we're splitting or using the whole chunk
771 if (cor->size >= size + g_c->gap_before + g_c->gap_after + COROUTINE_MINIMUM_STACK_SIZE){
772 // enough space for a second coroutine so split this free block
773 cor->size = size;
774 if (!setjmp(g_c->chunk_allocated)){
775 longjmp(cor->buf, Chunk_Split);
776 }
777 }
778 // cor now ready to use
779 Coroutine_FreeToIdle(cor, start);
780 return cor;
781 }
782
783 // No big-enough free blocks - check if there's space beyond the tip block
784
785 if (g_c->stack_limit) {
786 ptrdiff_t available = (unsigned char *)g_c->tip->limit - g_c->gap_before - g_c->gap_after - g_c->stack_limit;
787 if (available < (ptrdiff_t)size){
788 // no space for a new stack block
789 // printf("Not enough stack space (B) %p %zu %zu %p %ld\n", g_c->tip->limit, g_c->gap_before, g_c->gap_after, g_c->stack_limit, available);
790 // printf("g_c->tip = %p; tip-limit = %ld; tip->size = %zu\n", g_c->tip, (unsigned char *)g_c->tip - g_c->tip->limit, g_c->tip->size);
791 return NULL;
792 }
793 }
794 Coroutine *tip = g_c->tip;
795 Coroutine *me = g_c->active;
796 if (tip == me) {
797 if (!setjmp(g_c->chunk_allocated)){
798 ReserveStackSpace(g_c, me, StackTopNow() - me->limit, NULL);
799 }
800 } else {
801 if (!setjmp(g_c->chunk_allocated)){
802 longjmp(tip->buf, Chunk_Create);
803 }
804 }
805
806 cor = List_Link_Container(Coroutine, link, List_GetTail(&g_c->free));
807 assert(cor->state == Coroutine_Free);
808 cor->size = size;
809 cor->limit = (unsigned char *)cor - g_c->gap_after - size;
810 cor->state = Coroutine_Idle;
811 cor->start = start;
812 cor->value = NULL;
813 Link_Remove(&cor->link);
814 List_AddHead(&g_c->inactive, &cor->link);
815
816 g_c->report.coroutines_created += 1;
817 return cor;
818}
819
820
821Coroutine *Coroutine_New(
822 size_t stack,
823 Coroutine_Start start
824){
825 assert(g_c);
826 assert((g_c->state == Coroutines_Started && List_IsEmpty(&g_c->inactive)) || g_c->state == Coroutines_Active);
827 assert(!Coroutine_StackHasOverrun());
828
829 _Cor_Mutex_Lock(&g_c->mutex);
830
831 Coroutine *cor = Coroutine_New_Lock_Assumed(stack, start);
832
833 if (cor && cor->size > g_c->report.largest_stack){
834 g_c->report.largest_stack = cor->size;
835 }
836
837 _Cor_Mutex_Unlock(&g_c->mutex);
838
839 return cor;
840}
841
842
843void Coroutine_Delete(
844 Coroutine *cor
845){
846 assert(!Coroutine_StackHasOverrun());
847 if (cor){
848 Coroutines *cors = cor->coroutines;
849 _Cor_Mutex_Lock(&cors->mutex);
850 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Complete);
851
852#if COROUTINE_RECORD_LOWEST_HEADROOM
853 if (cor->guard){
854 unsigned char *base = cor->base;
855 unsigned char *rover;
856 for (rover = cor->limit+4; rover<base; rover += 4){
857 if (!Check_Guard(rover)){
858 break;
859 }
860 }
861 size_t myheadroom = (size_t)(rover - cor->limit);
862 if (myheadroom < g_c->report.lowest_headroom || g_c->report.lowest_headroom == 0){
863 g_c->report.lowest_headroom = myheadroom;
864 }
865 }
866#endif
867
868 cor->state = Coroutine_Free;
869 Link_Remove(&cor->link);
870
871 // insert into free list
872 List_AddHead(&cors->free, &cor->link);
873
874 // Check for merge with following Coroutine
875 List_Link *link = Link_Next(&cor->all_link);
876 if (Link_NextIsLink(link)){
877 Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
878 if (listcor->state == Coroutine_Free){
879 // merge
880 cor->size += cor->limit - listcor->limit;
881 cor->limit = listcor->limit;
882 cor->guard = listcor->guard;
883 Link_Remove(&listcor->all_link);
884 Link_Remove(&listcor->link);
885 if (g_c->tip == listcor){
886 g_c->tip = cor;
887 }
888 }
889 }
890
891 // check for merge with prev coroutine
892 link = Link_Prev(&cor->all_link);
893 if (Link_PrevIsLink(link)){
894 Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
895 if (listcor->state == Coroutine_Free){
896 // merge
897 listcor->size += listcor->limit - cor->limit;
898 listcor->limit = cor->limit;
899 listcor->guard = cor->guard;
900 Link_Remove(&cor->all_link);
901 Link_Remove(&cor->link);
902 if (g_c->tip == cor){
903 g_c->tip = listcor;
904 }
905 }
906 }
907
908 _Cor_Mutex_Unlock(&cors->mutex);
909 }
910}
911
912
913// Coroutine_Continue, assuming the mutex is claimed
914// return false for success, true for something went wrong
915static bool _Coroutine_Continue(
916 Coroutines *cors,
917 Coroutine *cor,
918 void *value,
919 bool early
920){
921 if (cor->state == Coroutine_Free || cor->state == Coroutine_Complete){
922 return true;
923 }
924 if (cor->state == Coroutine_Running){
925 // already running
926 return false;
927 }
928 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Waiting);
929 cor->entry_param = value;
930 cor->state = Coroutine_Running;
931 Link_Remove(&cor->link);
932 if ( early ) {
933 List_AddHead(&cors->runable, &cor->link);
934 } else {
935 List_AddTail(&cors->runable, &cor->link);
936 }
937 _Cor_Mutex_Unlock(&cors->waiting_mutex);
938 return false;
939}
940
941
942bool Coroutine_Continue(
943 Coroutine *cor,
944 void *value,
945 bool early
946){
947 assert(!Coroutine_StackHasOverrun());
948 Coroutines *cors = cor->coroutines;
949 _Cor_Mutex_Lock(&cors->mutex);
950 bool ret = _Coroutine_Continue(cors, cor, value, early);
951 _Cor_Mutex_Unlock(&cors->mutex);
952 return ret;
953}
954
955
956void *Coroutine_Yield(
957 void *value,
958 Coroutine_YieldCallback on_yield,
959 void *yield_me
960){
961 assert(g_c);
962 Coroutine *me = g_c->active;
963 assert(me);
964 assert(!Coroutine_StackHasOverrun());
965
966 _Cor_Mutex_Lock(&g_c->mutex);
967 Coroutines *cors = me->coroutines;
968 assert(me && me->state == Coroutine_Running && cors == g_c);
969 me->stack_top = StackTopNow();
970 me->value = value;
971 me->state = Coroutine_Waiting;
972
973 Link_Remove(&me->link);
974 if (!List_IsEmpty(&cors->runable)){
975 _Cor_Mutex_Unlock(&cors->waiting_mutex);
976 }
977 List_AddTail(&cors->waiting, &me->link);
978
979 switch (setjmp(me->buf)){
980 case Chunk_Initial:
981 _Cor_Mutex_Unlock(&cors->mutex);
982 on_yield(yield_me);
983 Coroutine_RunNext();
984 assert(false);
985 case Chunk_Create:
986 assert(me == g_c->tip);
987 ReserveStackSpace(me->coroutines, me, me->stack_top - me->limit, NULL);
988 assert(false);
989 case Chunk_Enter:
990 // arrive here with mutex locked
991 cors->active = me;
992 assert(!Coroutine_StackHasOverrun());
993 // when we return here - we are running again
994 assert(me->state == Coroutine_Running);
995 void *res = me->entry_param;
996 _Cor_Mutex_Unlock(&cors->mutex);
997 return res;
998 }
999 return NULL;
1000}
1001
1002
1003void *Coroutine_GetValue(
1004 Coroutine *cor
1005){
1006 return cor->value;
1007}
1008
1009
1010Coroutine *Coroutine_GetActive(void)
1011{
1012 return g_c ? g_c->active : NULL;
1013}
1014
1015
1016intptr_t Coroutine_GetStackHeadroom(void){
1017 assert(g_c);
1018 assert(!Coroutine_StackHasOverrun());
1019 Coroutine *me = g_c->active;
1020 if (!me){
1021 // no active coroutine
1022 unsigned char *stack_limit = g_c->stack_limit;
1023 if (stack_limit){
1024 return StackTopNow() - stack_limit;
1025 } else {
1026 // no information where the stack ends - return something
1027 return COROUTINE_MINIMUM_STACK_SIZE;
1028 }
1029 }
1030 return StackTopNow() - me->limit;
1031}
1032
1033
1034// This is used to avoid compiler warnings about returning the address of a local
1035static inline void *StopAddressWarnings(void *p)
1036{
1037 return p;
1038}
1039
1040
1041void *Coroutine_GetStackHWM(void){
1042 assert(g_c);
1043 assert(g_c->state == Coroutines_Active);
1044 assert(!Coroutine_StackHasOverrun());
1045 // Find where the guards end
1046 unsigned char *guard;
1047 for (guard = g_c->active->guard; Check_Guard(guard); guard += 4){
1048 // do nothing
1049 }
1050 return guard;
1051}
1052
1053
1054void Coroutine_ClearStackForHWM(void){
1055 assert(g_c);
1056 assert(g_c->state == Coroutines_Active);
1057 assert(!Coroutine_StackHasOverrun());
1058 unsigned char *end = StackTopNow() - GUARD_PATTERN_SIZE;
1059 for (unsigned char *guard = g_c->active->guard+GUARD_PATTERN_SIZE; guard <= end; guard += GUARD_PATTERN_SIZE){
1060 Apply_Guard(guard);
1061 }
1062}
1063
1064
1065static bool Coroutine_CanStartCoroutine_Lock_Assumed(
1066 size_t size
1067){
1068 if (!g_c->stack_limit){
1069 return true;
1070 }
1071
1072 if (!g_c->tip){
1073 return true;
1074 }
1075
1076 if (g_c->tip->state == Coroutine_Free){
1077 // last block is free
1078 if ((unsigned char *)g_c->tip - g_c->stack_limit >= (ptrdiff_t)(g_c->gap_after + size)){
1079 // enough room in free block, which is the last block
1080 return true;
1081 }
1082 } else {
1083 // last block is allocated
1084 if (g_c->tip->limit - g_c->stack_limit >= (ptrdiff_t)(g_c->gap_before + g_c->gap_after + size)){
1085 // enough room after the last block, which is allocated
1086 return true;
1087 }
1088 }
1089
1090 // not enough room between allocated blocks and stack limit, so check free list
1091 List_Link *link;
1092 for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
1093 Coroutine *cor = List_Link_Container(Coroutine, link, link);
1094 if (cor->size >= size){
1095 return true;
1096 }
1097 }
1098
1099 return false;
1100}
1101
1102
1103bool Coroutine_CanStartCoroutine(
1104 size_t size
1105){
1106 assert(g_c);
1107 assert(g_c->state == Coroutines_Started || g_c->state == Coroutines_Active);
1108 assert(!Coroutine_StackHasOverrun());
1109
1110 _Cor_Mutex_Lock(&g_c->mutex);
1111
1112 bool result = Coroutine_CanStartCoroutine_Lock_Assumed(size);
1113
1114 _Cor_Mutex_Unlock(&g_c->mutex);
1115
1116 return result;
1117}
1118
1119void *Coroutine_GetCStackTop(void){
1120 assert(!Coroutine_StackHasOverrun());
1121 if ((g_c->state == Coroutines_Started || g_c->state == Coroutines_Active) && g_c->tip != g_c->active) {
1122 return g_c->tip->stack_top;
1123 } else {
1124 return StackTopNow();
1125 }
1126}
1127
1128
1129static unsigned char *StackTopNow(void){
1130 unsigned char here[4];
1131 return StopAddressWarnings(here);
1132}
1133
1134
1135struct Coroutine_ChainParam {
1136 Coroutine_Start start;
1137 void *value;
1138 Coroutine *ret;
1139};
1140
1141
1142static void *Coroutine_ChainFn(
1143 void *param
1144){
1145 struct Coroutine_ChainParam *params = (struct Coroutine_ChainParam *)param;
1146 Coroutine_Continue(params->ret, params->start(params->value), true);
1147 return NULL;
1148}
1149
1150
1151static void Coroutine_ChainYield(
1152 void *unused
1153){
1154 (void)unused;
1155}
1156
1157
1158bool Coroutine_Chain(
1159 size_t size,
1160 Coroutine_Start start,
1161 void *value,
1162 void **result
1163){
1164 assert(Check_Guard(Coroutine_GetActive()->guard));
1165 Coroutine *cor = Coroutine_New(size, Coroutine_ChainFn);
1166 if (!cor){
1167 // failed
1168 return true;
1169 }
1170 struct Coroutine_ChainParam params = {
1171 start,
1172 value,
1173 Coroutine_GetActive()
1174 };
1175 Coroutine_Continue(cor, &params, true);
1176 void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
1177 Coroutine_Delete(cor);
1178 if (result){
1179 *result = res;
1180 }
1181 // success!
1182 return false;
1183}
1184
1185
1186bool Coroutine_IsRunning(
1187 Coroutine *cor
1188)
1189{
1190 int state = cor->state;
1191 return state == Coroutine_Running || state == Coroutine_Waiting;
1192}
1193
1194
1195bool Coroutine_IsComplete(
1196 Coroutine *cor
1197)
1198{
1199 int state = cor->state;
1200 return state == Coroutine_Complete;
1201}
1202
1203
1204bool Coroutine_IsStarted(void){
1205 return g_c && (g_c->state == Coroutines_Active || g_c->state == Coroutines_Started);
1206}
1207
1208void _Coroutine_Dump(void){
1209 char *state_to_text[] = {
1210 "Free",
1211 "Idle",
1212 "Running",
1213 "Waiting",
1214 "Complete"
1215 };
1216 unsigned idx = 0;
1217 List_Link *link;
1218 for (link = List_Begin(&g_c->all); Link_NextIsLink(link); link = Link_Next(link)){
1219 Coroutine *cor = List_Link_Container(Coroutine, all_link, link);
1220 printf("%d) %p (%s) %ld%s\n", idx++, cor, state_to_text[cor->state], cor->size, cor == g_c->tip ? " (TIP)" : "");
1221 }
1222}
1223