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