1686 lines42.1 KB

Text Raw Blame

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 <stdlib.h>
8	#include "cor_platform.h"
9
10	#include "coroutine_names_def.h"
11
12	// see CPython again, this time from ctypes.h
13	#if (defined (__SVR4) && defined (__sun)) \|\| defined(COROUTINE_HAVE_ALLOCA_H)
14	# include <alloca.h>
15	#elif defined(MS_WIN32)
16	# include <malloc.h>
17	#endif
18
19	/* If the system does not define alloca(), we have to hope for a compiler builtin. */
20	#ifndef alloca
21	# if defined __GNUC__ \|\| (__clang_major__ >= 4)
22	# define alloca __builtin_alloca
23	# else
24	# error "Could not define alloca() on your platform."
25	# endif
26	#endif
27
28	typedef struct Coroutines Coroutines;
29
30	static void Coroutine_RunNext(void);
31	static Coroutine_Err Coroutine_Continue_(Coroutines cors, Coroutine cor, void *value, bool early);
32	static uintptr_t StackTopNow(void);
33	static void TrimActiveIfPossible(void);
34	static void EnlargeActiveIfPossible(void);
35
36	#ifndef NDEBUG
37	// In debug builds, use the built-in assert
38	#define MyAssert assert
39	#else
40	#if 1
41	// In non-debug builds, normally use this - all the asserts are disabled
42	#define MyAssert(cond)
43	#else
44	// In non-debug builds with stack problems, you can use this.
45	// This activates all the asserts, and gives a line to put a
46	// breakpoint in your debugger.
47	static void _MyAssert(bool cond, char const *msg)
48	{
49	if (!cond){
50	fputs("Assertion failed: ", stdout);
51	fputs(msg, stdout);
52	fputs("\n", stdout);
53	}
54	}
55	#define MyAssert(cond) _MyAssert(cond, #cond)
56	#endif
57	#endif
58
59	static inline ptrdiff_t
60	StackPointerDiff
61	(
62	unsigned char *a,
63	unsigned char *b
64	){
65	#if COROUTINE_STACK_GROWS_UP
66	return a - b;
67	#else
68	return b - a;
69	#endif
70	}
71
72	static inline unsigned char *
73	StackPointerAdd
74	(
75	unsigned char *a,
76	ptrdiff_t b
77	){
78	#if COROUTINE_STACK_GROWS_UP
79	return a + b;
80	#else
81	return a - b;
82	#endif
83	}
84
85	// Unused...
86	// static inline unsigned char *
87	// StackBaseEnd
88	// (
89	// unsigned char *memlo,
90	// unsigned char *memhi
91	// ){
92	// #if COROUTINE_STACK_GROWS_UP
93	// (void)memhi;
94	// return memlo;
95	// #else
96	// (void)memlo;
97	// return memhi-1;
98	// #endif
99	// }
100	// ...unused
101
102	static inline unsigned char *
103	StackLimitEnd
104	(
105	unsigned char *memlo,
106	unsigned char *memhi
107	){
108	#if COROUTINE_STACK_GROWS_UP
109	(void)memlo;
110	return memhi;
111	#else
112	(void)memhi;
113	return memlo-1;
114	#endif
115	}
116
117	#define CHECK_SYSTEM_RUNNING \
118	if (!g_c){ \
119	return Coroutine_Err_SystemNotRunning; \
120	}
121	#define CHECK_SYSTEM_NOT_RUNNING \
122	if (g_c){ \
123	return Coroutine_Err_SystemRunning; \
124	}
125	#define CHECK_COROUTINE_THREAD \
126	if (cor->coroutines != g_c){ \
127	return Coroutine_Err_CoroutineFromWrongThread; \
128	}
129	#define CHECK_NO_COROUTINE_RUNNING \
130	if (g_c->state != Coroutines_Started){ \
131	return Coroutine_Err_ACoroutineIsAlreadyRunning; \
132	}
133	#define CHECK_STACK_OVERRUN \
134	{ \
135	Coroutine_Err err = Coroutine_StackHasOverrun(); \
136	if (err){ \
137	return err; \
138	} \
139	} while (0);
140
141
142	static inline void ready_jmp_buf(jmp_buf buf) {
143	#if defined(_M_X64) \|\| defined(_M_ARM64)
144	// Win64:
145	// Set Frame to 0 on Windows 64 bit to prevent C++ stack unwinding in longjmp().
146	// Win32:
147	// Doesn't do this, so only needed on the 2 64 bit Windows versions
148	((_JUMP_BUFFER*)buf)->Frame = 0;
149	#else
150	(void)buf;
151	#endif
152	}
153
154	///////////////////////////////////////////////////////////////////////////////
155	// 2-way linked lists...
156	//
157	// Brought inline here to avoid namespace polution
158	///////////////////////////////////////////////////////////////////////////////
159
160	typedef struct List_Link List_Link;
161	struct List_Link {
162	List_Link *next;
163	List_Link *prev;
164	};
165
166	typedef struct List_Head List_Head;
167	struct List_Head {
168	union {
169	struct {
170	List_Link link;
171	List_Link *filler;
172	} fwd;
173	struct {
174	List_Link *filler;
175	List_Link link;
176	} back;
177	};
178	};
179
180
181	static inline bool List_IsEmpty(
182	const List_Head *list
183	){
184	return list->fwd.link.next == &list->back.link;
185	}
186
187
188	static inline List_Link *List_GetHead(
189	const List_Head *list
190	){
191	return List_IsEmpty(list) ? NULL : list->fwd.link.next;
192	}
193
194
195	static inline List_Link *List_Begin(
196	const List_Head *list
197	){
198	return list->fwd.link.next;
199	}
200
201
202	static inline bool Link_NextIsLink(
203	const List_Link *link
204	){
205	return link->next != NULL;
206	}
207
208
209	static inline List_Link *Link_Next(
210	List_Link *link
211	){
212	return link->next;
213	}
214
215
216	static inline bool Link_PrevIsLink(
217	const List_Link *link
218	){
219	return link->prev != NULL;
220	}
221
222
223	static inline List_Link *Link_Prev(
224	List_Link *link
225	){
226	return link->prev;
227	}
228
229	// Unused...
230	// static inline List_Link *List_GetTail(
231	// const List_Head *list
232	// ){
233	// return List_IsEmpty(list) ? NULL : list->back.link.prev;
234	// }
235	// ...unused
236
237
238	#define OFFSETOF(Container, Field) ((char )&((Container )4)->Field - (char )(Container )4)
239	#define List_Link_Container(Container, Link, link) ((Container )((char )(link) - OFFSETOF(Container, Link)))
240
241
242	static inline void
243	List_Init(
244	List_Head *list
245	){
246	list->fwd.link.next = &list->back.link;
247	list->fwd.link.prev = NULL;
248	list->back.link.prev = &list->fwd.link;
249	}
250
251
252	static inline void
253	Link_AddAfter(
254	List_Link *link,
255	List_Link *after
256	){
257	link->next = after->next;
258	link->prev = after;
259	after->next->prev = link;
260	after->next = link;
261	}
262
263
264	static inline void
265	List_AddHead(
266	List_Head *list,
267	List_Link *link
268	){
269	Link_AddAfter(link, &list->fwd.link);
270	}
271
272
273	static inline void
274	Link_AddBefore(
275	List_Link *link,
276	List_Link *before
277	){
278	link->prev = before->prev;
279	link->next = before;
280	before->prev->next = link;
281	before->prev = link;
282	}
283
284
285	static inline void
286	List_AddTail(
287	List_Head *list,
288	List_Link *link
289	){
290	Link_AddBefore(link, &list->back.link);
291	}
292
293
294	static inline void
295	Link_Remove(
296	List_Link *link
297	){
298	link->prev->next = link->next;
299	link->next->prev = link->prev;
300	}
301
302	///////////////////////////////////////////////////////////////////////////////
303	// ...2-way linked lists
304	///////////////////////////////////////////////////////////////////////////////
305
306	enum {
307	Coroutines_Started,
308	Coroutines_Stopping
309	};
310
311	enum {
312	Chunk_Initial,
313	Chunk_Split,
314	Chunk_Enter
315	};
316
317	typedef enum Coroutine_State {
318	Coroutine_Free,
319	Coroutine_Idle,
320	Coroutine_Running,
321	Coroutine_Waiting,
322	Coroutine_Complete
323	} Coroutine_State;
324
325	enum {
326	Coroutines_Init,
327	Coroutines_AllocatedChunk,
328	Coroutines_CoroutineComplete,
329	};
330
331	struct Coroutine {
332	size_t min_size;
333	size_t min_headroom;
334	Coroutines *coroutines; // so can work with it off-thread
335	List_Link link; // for whichever list it's on
336	List_Link all_link; // list of all Coroutines
337	jmp_buf buf; // how to get back to it
338	unsigned char *base; // where the base of this Coroutine's stack is (= previous block's limit)
339	unsigned char *limit; // where the limit of this Coroutine's stack is (= next block's base)
340	unsigned char *guard; // where the stack overrun guard is
341	Coroutine_Start start; // entry point
342	void *entry_param; // to pass to start
343	void *value; // yielded/returned
344	unsigned char *stack_top; // recorded at yield
345	struct Coroutine *chain_root; // The root (entry) of a series of chained coroutines
346	struct Coroutine *chain_tip; // The tip (yielder) of a series of chained coroutines
347	Coroutine_State state;
348
349	int sequence;
350	};
351
352	struct Coroutines {
353	_Cor_Mutex mutex;
354	jmp_buf controller; // to return from Coroutine_Run
355	jmp_buf chunk_allocated;// for chunk allocation
356	size_t size_to_retain; // for Chunk_Split
357
358	// singletons
359	Coroutine *tip; // top of stack chunk
360	Coroutine *active; // currently running coroutine
361	Coroutine *primary; // Coroutine_Run coroutine
362	unsigned char *stack_limit; // when not NULL, where the stack finishes
363
364	Coroutine *spare; // spare struct Coroutine (instead of having to malloc & fail)
365
366	// lists
367	List_Head all; // all Coroutines (in address order)
368	List_Head free; // free Coroutines
369	List_Head inactive; // idle or complete
370	List_Head runable; // running or waiting to run
371	List_Head waiting; // yielded / waiting to run
372	_Cor_Mutex waiting_mutex;
373
374	Coroutine *root; // The coroutine for the thread which started Coroutines
375
376	// Summary of the system
377	Coroutine_Report report;
378
379	// state
380	char state;
381
382	int sequence;
383	};
384
385	_Cor_thread_local Coroutines *g_c;
386	_Cor_thread_local unsigned char *g_stack_limit;
387
388	static void ReserveStackSpace(Coroutines cors, Coroutine parent, size_t chunk_size, unsigned char childs_limit, unsigned char childs_guard);
389	static void stack_chunk_base(Coroutines cors, Coroutine parent, unsigned char prev_limit, unsigned char limit, unsigned char *guard);
390
391
392	static size_t
393	Coroutine_Size
394	(
395	Coroutine *cor
396	){
397	if (cor->limit){
398	return (size_t)StackPointerDiff(cor->limit, cor->base);
399	} else {
400	return SIZE_MAX;
401	}
402	}
403
404
405	static size_t
406	TrimmableSize(
407	Coroutine *cor
408	){
409	size_t current_used = StackPointerDiff(cor->stack_top, cor->base);
410	size_t min_size = current_used + cor->min_headroom;
411	if (min_size < cor->min_size){
412	min_size = cor->min_size;
413	}
414
415	if (cor->limit){
416	// If this coroutine's stack chunk does not have enough space for:
417	// * itself (min_size)
418	// * a potential new coroutine (COROUTINE_MINIMUM_STACK_SIZE)
419	// then return 0, ie not trimable
420	if (Coroutine_Size(cor) < min_size + COROUTINE_MINIMUM_STACK_SIZE){
421	return 0;
422	}
423	}
424	return min_size;
425	}
426
427
428	#define GUARD_PATTERN_SIZE (4)
429	/// @brief Checks whether a guard pattern is OK
430	/// @param guard The address of the stack base end of the pattern
431	/// @return true pattern is ok; false pattern is broken
432	static inline bool
433	Guard_Pattern_OK(
434	unsigned char *guard
435	){
436	return !guard \|\|
437	(*StackPointerAdd(guard, 0) == 0xde &&
438	*StackPointerAdd(guard, 1) == 0xad &&
439	*StackPointerAdd(guard, 2) == 0xbe &&
440	*StackPointerAdd(guard, 3) == 0xef);
441	}
442
443
444	/// @brief Writes a guard pattern
445	/// @param guard Where to write the guard pattern (stack base end)
446	static inline void
447	Apply_Guard(unsigned char *guard){
448	*StackPointerAdd(guard, 0) = 0xde;
449	*StackPointerAdd(guard, 1) = 0xad;
450	*StackPointerAdd(guard, 2) = 0xbe;
451	*StackPointerAdd(guard, 3) = 0xef;
452	}
453
454
455	#ifndef NDEBUG
456	/// @brief Checks a list of Coroutines to see whether it's OK
457	/// @param head The list to check
458	/// @param state1 One of the states Coroutines in the list are allowed
459	/// @param state2 One of the states Coroutines in the list are allowed
460	/// @return Coroutine_OK the is OK; other the list is broken
461	static Coroutine_Err
462	CheckListIntegrity(
463	List_Head *head,
464	Coroutine_State state1,
465	Coroutine_State state2
466	){
467	for (List_Link *link = List_Begin(head); Link_NextIsLink(link); link = Link_Next(link)){
468	Coroutine *candidate = List_Link_Container(Coroutine, link, link);
469	if (candidate->coroutines != g_c){
470	return Coroutine_Err_InternalInsistency;
471	}
472	if(candidate->state != state1 && candidate->state != state2){
473	return Coroutine_Err_InternalInsistency;
474	}
475	bool found = false;
476	for (List_Link *link = List_Begin(&g_c->all); Link_NextIsLink(link); link = Link_Next(link)){
477	Coroutine *candidate2 = List_Link_Container(Coroutine, all_link, link);
478	if (candidate == candidate2){
479	found = true;
480	}
481	}
482	if (!found){
483	return Coroutine_Err_InternalInsistency;
484	}
485	}
486	return Coroutine_OK;
487	}
488
489
490	/// @brief Check the integrity of this thread's coroutine system
491	/// @return Coroutine_OK everything's OK; other something was wrong
492	static Coroutine_Err
493	Coroutine_CheckIntegrity_(
494	void
495	){
496	Coroutine_Err err;
497	err = CheckListIntegrity(&g_c->free, Coroutine_Free, Coroutine_Free);
498	if (err){
499	return err;
500	}
501	err = CheckListIntegrity(&g_c->inactive, Coroutine_Idle, Coroutine_Complete);
502	if (err){
503	return err;
504	}
505	err = CheckListIntegrity(&g_c->runable, Coroutine_Running, Coroutine_Running);
506	if (err){
507	return err;
508	}
509	err = CheckListIntegrity(&g_c->waiting, Coroutine_Waiting, Coroutine_Waiting);
510	return err;
511	}
512	#endif
513
514
515	/// @brief Check whether the stack has overrun
516	/// @return Coroutine_OK the stack hasn't; other it has
517	static Coroutine_Err
518	Coroutine_StackHasOverrun(
519	void
520	){
521	unsigned char stack_top = (unsigned char )StackTopNow();
522	unsigned char *stack_limit = g_c ? g_c->stack_limit : NULL;
523	if (stack_limit && StackPointerDiff(stack_limit, stack_top) < 0){
524	// current stack top is beyond limit - we are overrunning NOW
525	return Coroutine_Err_StackOverrun;
526	}
527	Coroutine *me = g_c ? g_c->active : NULL;
528	if (!me){
529	return Coroutine_OK;
530	}
531	#if COROUTINE_CHECK_INTEGRITY_ON_STACK_CHECK
532	// Check all coroutines integrity
533	Coroutine_Err err = Coroutine_CheckIntegrity_();
534	if (err){
535	return err;
536	}
537	#endif
538	if (me->guard){
539	if (StackPointerDiff(me->guard, stack_top) < 0){
540	// Stack top beyond active stack limit
541	return Coroutine_Err_StackOverrun;
542	}
543	if (!Guard_Pattern_OK(me->guard)){
544	// Guard pattern trampled
545	return Coroutine_Err_StackOverrun;
546	}
547	}
548	return Coroutine_OK;
549	}
550
551	#ifndef NDEBUG
552	/// @brief Check system integrity - does stack overrun check and internals check
553	/// @return Coroutine_OK all is OK; other something was wrong
554	Coroutine_Err
555	Coroutine_CheckIntegrity(
556	void
557	){
558	Coroutine_Err err = Coroutine_StackHasOverrun();
559	#if !COROUTINE_CHECK_INTEGRITY_ON_STACK_CHECK
560	if (!err && g_c){
561	err = Coroutine_CheckIntegrity_();
562	}
563	#endif
564	return err;
565	}
566	#endif
567
568
569	static void
570	ReserveStackSpace(
571	Coroutines *cors,
572	Coroutine *parent,
573	size_t chunk_size,
574	unsigned char *childs_limit,
575	unsigned char *childs_guard
576	){
577	unsigned char *chunk_of_stack = alloca(chunk_size);
578	unsigned char *limit = StackLimitEnd(chunk_of_stack, chunk_of_stack+chunk_size);
579	unsigned char *guard = StackPointerAdd(limit, -GUARD_PATTERN_SIZE);
580	#if COROUTINE_RECORD_LOWEST_HEADROOM
581	for (size_t i = 0; i <= chunk_size-GUARD_PATTERN_SIZE; i += GUARD_PATTERN_SIZE){
582	Apply_Guard(StackPointerAdd(guard, -(ptrdiff_t)i));
583	}
584	#else
585	Apply_Guard(guard);
586	#endif
587	if (parent){
588	parent->limit = limit;
589	parent->guard = guard;
590	}
591	stack_chunk_base(cors, parent, limit, childs_limit, childs_guard);
592	}
593
594
595	static void
596	stack_chunk_base(
597	Coroutines *cors,
598	Coroutine *parent,
599	unsigned char *prev_limit,
600	unsigned char *limit,
601	unsigned char *guard
602	){
603	MyAssert(cors->spare);
604	Coroutine *here = cors->spare;
605	cors->spare = NULL;
606	here->coroutines = cors;
607	here->sequence = cors->sequence++;
608	here->state = Coroutine_Free;
609	here->base = prev_limit;
610	here->limit = limit;
611	here->guard = guard;
612	here->stack_top = (unsigned char *)StackTopNow();
613
614	// insert into all list
615	if (parent){
616	Link_AddAfter(&here->all_link, &parent->all_link);
617	} else {
618	List_AddHead(&cors->all, &here->all_link);
619	}
620	// add to free list
621	List_AddTail(&cors->free, &here->link);
622
623	cors->report.coroutines_pool_size += 1;
624
625	if (!cors->tip \|\| !Link_NextIsLink(Link_Next(&here->all_link))){
626	cors->tip = here;
627	}
628
629	for(;;){
630	switch (setjmp(here->buf)) {
631	case Chunk_Initial:
632	ready_jmp_buf(here->buf);
633	if (here->state == Coroutine_Free){
634	// return to the coroutine allocator
635	longjmp(cors->chunk_allocated, 1);
636	} else {
637	MyAssert(here->state == Coroutine_Complete);
638	// we finish here to ensure the setjmp is redone
639	if (cors->primary == here) {
640	// if primary coroutine - return to Coroutine_Run
641	longjmp(cors->controller, Coroutines_CoroutineComplete);
642	}
643	_Cor_Mutex_Unlock(&cors->mutex);
644	Coroutine_RunNext();
645	}
646	MyAssert(false);
647	break;
648	case Chunk_Split:
649	// Request to split this idle block into two
650	// g_c->size_to_retain will be set to our shorter size
651	ReserveStackSpace(here->coroutines, here, g_c->size_to_retain, here->limit, here->guard);
652	MyAssert(false);
653	break;
654	case Chunk_Enter:
655	// request to start a coroutine (ie use the chunk for a coroutine)
656	// arrive here with mutex locked
657	MyAssert(here->state == Coroutine_Running);
658	here->coroutines->active = here;
659	EnlargeActiveIfPossible();
660	_Cor_Mutex_Unlock(&cors->mutex);
661	here->value = here->start(here->entry_param);
662
663	// check the guard
664	MyAssert(Guard_Pattern_OK(here->guard));
665
666	here->stack_top = (unsigned char *)StackTopNow();
667	_Cor_Mutex_Lock(&here->coroutines->mutex);
668	TrimActiveIfPossible();
669	here->coroutines->active = NULL;
670	MyAssert(here->state == Coroutine_Running);
671	Link_Remove(&here->link);
672	here->state = Coroutine_Complete;
673	List_AddTail(&here->coroutines->inactive, &here->link);
674	// Coroutine has completed
675	// Loop round to redo the setjmp() - if this coroutine yielded, then the setjmp will
676	// need reseting
677	break;
678	}
679	}
680	}
681
682
683	static void
684	Coroutine_RunNext(
685	void
686	){
687	// arrive here with mutex unlocked
688	_Cor_Mutex_Lock(&g_c->waiting_mutex);
689	_Cor_Mutex_Lock(&g_c->mutex);
690	Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c->runable));
691	MyAssert(next->state == Coroutine_Running);
692	longjmp(next->buf, Chunk_Enter);
693	MyAssert(false);
694	}
695
696
697	/// @brief Ensures there's a spare Coroutine for cors
698	/// @param cors The Coroutines to ensure a spare for
699	/// @return true there is a spare; false there isn't
700	static inline bool
701	EnsureSpare
702	(
703	Coroutines *cors
704	){
705	if (cors->spare){
706	return true;
707	}
708	cors->spare = malloc(sizeof(*cors->spare));
709	return cors->spare != NULL;
710	}
711
712
713	static Coroutine_Err
714	Coroutines_ctor(
715	Coroutines *cors,
716	size_t min_size,
717	size_t min_headroom
718	){
719	if (_Cor_Mutex_ctor(&cors->mutex)){
720	goto error;
721	}
722	cors->primary = NULL;
723	cors->stack_limit = g_stack_limit;
724
725	List_Init(&cors->all);
726	List_Init(&cors->free);
727	List_Init(&cors->inactive);
728	List_Init(&cors->runable);
729	List_Init(&cors->waiting);
730	if (_Cor_Mutex_ctor(&cors->waiting_mutex)){
731	goto error1;
732	}
733	if (_Cor_Mutex_Lock(&cors->waiting_mutex)){
734	goto error2;
735	}
736
737	cors->report.coroutines_created = 0;
738	cors->report.coroutines_pool_size = 0;
739	cors->report.largest_stack = 0;
740	cors->spare = NULL;
741	cors->sequence = 0;
742
743	Coroutine cor = malloc(sizeof(cor));
744	cor->min_size = min_size;
745	cor->min_headroom = min_headroom;
746	cor->coroutines = cors;
747	cor->sequence = cors->sequence++;
748	cor->state = Coroutine_Running;
749	cor->base = (unsigned char *)&cor;
750	cor->chain_root = cor;
751	cor->chain_tip = cor;
752	if (cors->stack_limit){
753	cor->limit = cors->stack_limit;
754	#if COROUTINE_GUARD_AT_C_STACK_LIMIT
755	cor->guard = StackPointerAdd(cor->limit, -GUARD_PATTERN_SIZE);
756	Apply_Guard(cor->guard);
757	#else
758	cor->guard = NULL;
759	#endif
760	} else {
761	cor->limit = cor->guard = NULL;
762	}
763	cors->root = cor;
764	List_AddHead(&cors->all, &cor->all_link);
765	List_AddTail(&cors->runable, &cor->link);
766	cors->tip = cors->active = cor;
767
768	cors->report.coroutines_pool_size += 1;
769
770	cors->state = Coroutines_Started;
771	return Coroutine_OK;
772	error2:
773	_Cor_Mutex_dtor(&cors->waiting_mutex);
774	error1:
775	_Cor_Mutex_dtor(&cors->mutex);
776	error:
777	return Coroutine_Err_CouldNotInitialiseSystem;
778	}
779
780	static void
781	Coroutines_dtor(
782	Coroutines *cors
783	){
784	_Cor_Mutex_Lock(&cors->mutex);
785	cors->state = Coroutines_Stopping;
786
787	MyAssert(List_IsEmpty(&cors->inactive));
788
789	// free the spare
790	if (cors->spare){
791	free(cors->spare);
792	}
793
794	// free all non-spares
795	List_Link *link;
796	List_Link *next;
797	for (link = List_Begin(&cors->all); Link_NextIsLink(link); link = next){
798	next = Link_Next(link);
799	Coroutine *cor = List_Link_Container(Coroutine, all_link, link) ;
800	free(cor);
801	}
802
803	_Cor_Mutex_Unlock(&cors->waiting_mutex);
804	_Cor_Mutex_dtor(&cors->waiting_mutex);
805
806	MyAssert(cors->state == Coroutines_Stopping);
807	_Cor_Mutex_Unlock(&cors->mutex);
808	_Cor_Mutex_dtor(&cors->mutex);
809	}
810
811
812	Coroutine_Err
813	Coroutine_RunSystem(
814	size_t min_size,
815	size_t min_headroom,
816	Coroutine_SystemStart start,
817	void *value
818	){
819	CHECK_SYSTEM_NOT_RUNNING
820
821	Coroutines cors;
822	Coroutine_Err err = Coroutines_ctor(&cors, min_size, min_headroom);
823	if (err){
824	return err;
825	}
826	g_c = &cors;
827	err = start(value, cors.root);
828	g_c = NULL;
829	Coroutines_dtor(&cors);
830	return err;
831	}
832
833
834	void
835	Coroutine_SetStackLimit(
836	void *limit
837	){
838	MyAssert(!limit \|\| !g_c \|\| !g_stack_limit \|\| StackPointerDiff((unsigned char )limit, (unsigned char )g_stack_limit) <= 0);
839	g_stack_limit = limit;
840	if (g_c){
841	g_c->stack_limit = limit;
842	if (g_c->tip){
843	g_c->tip->limit = limit;
844	#if COROUTINE_GUARD_AT_C_STACK_LIMIT
845	g_c->tip->guard = StackPointerAdd(limit, -GUARD_PATTERN_SIZE);
846	Apply_Guard(g_c->tip->guard);
847	#else
848	g_c->tip->guard = NULL;
849	#endif
850	}
851	}
852	}
853
854
855	#if COROUTINE_RECORD_LOWEST_HEADROOM
856	static size_t
857	Coroutine_UpdateMinimumHeadroom(
858	List_Head *list,
859	size_t headroom
860	){
861	for (List_Link *link = List_Begin(list); Link_NextIsLink(link); link = Link_Next(link)){
862	Coroutine *cor = List_Link_Container(Coroutine, link, link);
863	if (cor->guard){
864	size_t chunk_size = Coroutine_Size(cor);
865	for (size_t i = 0; i <= chunk_size-GUARD_PATTERN_SIZE; i += GUARD_PATTERN_SIZE){
866	if (!Guard_Pattern_OK(StackPointerAdd(cor->guard, -(ptrdiff_t)i))){
867	headroom = i < headroom ? i : headroom;
868	break;
869	}
870	}
871	}
872	}
873	return headroom;
874	}
875	#endif
876
877
878	Coroutine_Report
879	Coroutine_GetReport(
880	void
881	){
882	if (g_c){
883	size_t headroom;
884	#if COROUTINE_RECORD_LOWEST_HEADROOM
885	_Cor_Mutex_Lock(&g_c->mutex);
886	headroom = g_c->report.lowest_headroom;
887	headroom = Coroutine_UpdateMinimumHeadroom(&g_c->inactive, headroom);
888	headroom = Coroutine_UpdateMinimumHeadroom(&g_c->runable, headroom);
889	headroom = Coroutine_UpdateMinimumHeadroom(&g_c->waiting, headroom);
890	_Cor_Mutex_Unlock(&g_c->mutex);
891	#else
892	headroom = 0;
893	#endif
894	g_c->report.lowest_headroom = headroom;
895
896	return g_c->report;
897	} else {
898	Coroutine_Report ret = {0, 0, 0, 0};
899	return ret;
900	}
901	}
902
903
904	struct Coroutine_Run_Params {
905	Coroutine_Start start;
906	void *value;
907	void **result;
908	};
909
910	static Coroutine_Err
911	Coroutine_Run_Starter(
912	void *_params,
913	Coroutine *root
914	){
915	(void)root;
916	struct Coroutine_Run_Params params = (struct Coroutine_Run_Params )_params;
917
918	void *res = params->start(params->value);
919	if (params->result){
920	*params->result = res;
921	}
922
923	return Coroutine_OK;
924	}
925
926
927	Coroutine_Err Coroutine_Run(
928	size_t min_size,
929	size_t min_headroom,
930	Coroutine_Start start,
931	void *value,
932	void **result
933	){
934	if (!g_c){
935	struct Coroutine_Run_Params params = {start, value, result};
936	return Coroutine_RunSystem(min_size, min_headroom, Coroutine_Run_Starter, &params);
937	}
938
939	// We are in an active coroutine, so call start() directly
940	CHECK_STACK_OVERRUN
941	void *res = start(value);
942	if (result){
943	*result = res;
944	}
945
946	// no failures, so...
947	return Coroutine_OK;
948	}
949
950
951	static Coroutine *Coroutine_New_Lock_Assumed(
952	size_t min_size,
953	size_t min_headroom,
954	Coroutine_Start start
955	){
956	List_Link *link;
957
958	if (!EnsureSpare(g_c)){
959	return NULL;
960	}
961
962	Coroutine *cor = NULL;
963	for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
964	Coroutine *candidate = List_Link_Container(Coroutine, link, link);
965	MyAssert(candidate->coroutines == g_c);
966	MyAssert(candidate->state == Coroutine_Free);
967	if (candidate->limit){
968	size_t candidate_size = Coroutine_Size(candidate);
969	if (candidate_size < min_size){
970	continue;
971	}
972	}
973	// candidate has no limit, or is big enough
974
975	// check if it's 'better' (lower in the C stack) than cor
976	if (!cor \|\| StackPointerDiff(candidate->base, cor->base) < 0){
977	// chunk big enough, and a better choice than cor
978	cor = candidate;
979	}
980	}
981
982	if (!cor){
983	return NULL;
984	}
985
986	// use this free block
987	cor->min_size = min_size;
988	cor->min_headroom = min_headroom;
989	cor->state = Coroutine_Idle;
990	cor->start = start;
991	cor->value = NULL;
992	cor->chain_root = cor;
993	cor->chain_tip = cor;
994	Link_Remove(&cor->link);
995	List_AddHead(&g_c->inactive, &cor->link);
996
997	// trim down to an appropriate size
998	size_t trimmable_size = TrimmableSize(cor);
999	if (trimmable_size){
1000	// split block into two
1001	if (EnsureSpare(g_c)){
1002	g_c->size_to_retain = trimmable_size;
1003	if (!setjmp(g_c->chunk_allocated)){
1004	ready_jmp_buf(g_c->chunk_allocated);
1005	longjmp(cor->buf, Chunk_Split);
1006	}
1007	}
1008	}
1009
1010	g_c->report.coroutines_created += 1;
1011
1012	return cor;
1013	}
1014
1015
1016	static void
1017	TrimActiveIfPossible
1018	(
1019	void
1020	){
1021	MyAssert(g_c);
1022
1023	// If we're the active coroutine, free the tail
1024	Coroutine *active = g_c->active;
1025	MyAssert(active);
1026
1027	active->stack_top = (unsigned char *)StackTopNow();
1028	ptrdiff_t timmablesize = TrimmableSize(active);
1029	if (!timmablesize){
1030	return;
1031	}
1032
1033	if (!EnsureSpare(g_c)){
1034	return;
1035	}
1036
1037	// enough space for a second coroutine so free the unused stack space from active
1038	if (!setjmp(g_c->chunk_allocated)){
1039	ready_jmp_buf(g_c->chunk_allocated);
1040	ReserveStackSpace(g_c, active, timmablesize - StackPointerDiff(active->stack_top, active->base), active->limit, active->guard);
1041	MyAssert(false);
1042	}
1043	}
1044
1045
1046	static void
1047	EnlargeActiveIfPossible(
1048	void
1049	){
1050	MyAssert(g_c);
1051	Coroutine *active = g_c->active;
1052	MyAssert(active);
1053
1054	List_Link *next = Link_Next(&active->all_link);
1055	if (!Link_NextIsLink(next)){
1056	return;
1057	}
1058	Coroutine *cor = List_Link_Container(Coroutine, all_link, next);
1059	if (cor->state != Coroutine_Free){
1060	return;
1061	}
1062
1063	// Following block is free, merge with this
1064	active->limit = cor->limit;
1065	active->guard = cor->guard;
1066	Link_Remove(&cor->link);
1067	Link_Remove(&cor->all_link);
1068	if (g_c->tip == cor){
1069	g_c->tip = active;
1070	}
1071	if (g_c->spare){
1072	free(cor);
1073	} else {
1074	g_c->spare = cor;
1075	}
1076	}
1077
1078
1079	Coroutine *
1080	Coroutine_New(
1081	size_t min_size,
1082	size_t min_headroom,
1083	Coroutine_Start start
1084	){
1085	MyAssert(g_c && g_c->state == Coroutines_Started);
1086	MyAssert(!Coroutine_StackHasOverrun());
1087
1088	// Make the paramaters make sense
1089	if (min_size < min_headroom){
1090	min_size = min_headroom;
1091	}
1092
1093	_Cor_Mutex_Lock(&g_c->mutex);
1094
1095	TrimActiveIfPossible();
1096
1097	Coroutine *cor = Coroutine_New_Lock_Assumed(min_size, min_headroom, start);
1098
1099	if (cor && Coroutine_Size(cor) > g_c->report.largest_stack){
1100	g_c->report.largest_stack = Coroutine_Size(cor);
1101	}
1102
1103	EnlargeActiveIfPossible();
1104
1105	_Cor_Mutex_Unlock(&g_c->mutex);
1106
1107	return cor;
1108	}
1109
1110
1111	void
1112	Coroutine_Delete(
1113	Coroutine *cor
1114	){
1115	MyAssert(!Coroutine_StackHasOverrun());
1116	if (cor){
1117	Coroutines *cors = cor->coroutines;
1118	_Cor_Mutex_Lock(&cors->mutex);
1119	MyAssert(cor->state == Coroutine_Idle \|\| cor->state == Coroutine_Complete);
1120
1121	#if COROUTINE_RECORD_LOWEST_HEADROOM
1122	if (cor->guard){
1123	unsigned char *guard = cor->guard;
1124	ptrdiff_t chunk_size = Coroutine_Size(cor);
1125	ptrdiff_t myheadroom;
1126	for (myheadroom = 0; myheadroom <= chunk_size-(ptrdiff_t)GUARD_PATTERN_SIZE; myheadroom += GUARD_PATTERN_SIZE){
1127	if (!Guard_Pattern_OK(StackPointerAdd(guard, -myheadroom))){
1128	break;
1129	}
1130	}
1131	if (myheadroom < (ptrdiff_t)g_c->report.lowest_headroom \|\| g_c->report.lowest_headroom == 0){
1132	g_c->report.lowest_headroom = myheadroom;
1133	}
1134	}
1135	#endif
1136
1137	cor->state = Coroutine_Free;
1138	Link_Remove(&cor->link);
1139
1140	// insert into free list
1141	List_AddHead(&cors->free, &cor->link);
1142
1143	// Check for merge with following Coroutine
1144	List_Link *link = Link_Next(&cor->all_link);
1145	if (Link_NextIsLink(link)){
1146	Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
1147	if (listcor->state == Coroutine_Free){
1148	// merge
1149	cor->limit = listcor->limit;
1150	cor->guard = listcor->guard;
1151	Link_Remove(&listcor->all_link);
1152	Link_Remove(&listcor->link);
1153	if (g_c->tip == listcor){
1154	g_c->tip = cor;
1155	}
1156
1157	// free up the now unused struct
1158	if (g_c->spare){
1159	free(listcor);
1160	} else {
1161	g_c->spare = listcor;
1162	}
1163	}
1164	}
1165
1166	// check for merge with prev coroutine
1167	link = Link_Prev(&cor->all_link);
1168	if (Link_PrevIsLink(link)){
1169	Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
1170	if (listcor->state == Coroutine_Free){
1171	// merge
1172	listcor->limit = cor->limit;
1173	listcor->guard = cor->guard;
1174	Link_Remove(&cor->all_link);
1175	Link_Remove(&cor->link);
1176	if (g_c->tip == cor){
1177	g_c->tip = listcor;
1178	}
1179
1180	// free up the now unused struct
1181	if (g_c->spare){
1182	free(cor);
1183	} else {
1184	g_c->spare = cor;
1185	}
1186	}
1187	}
1188
1189	EnlargeActiveIfPossible();
1190
1191	_Cor_Mutex_Unlock(&cors->mutex);
1192	}
1193	}
1194
1195
1196	// Coroutine_Continue, assuming the mutex is claimed
1197	// return false for success, true for something went wrong
1198	static Coroutine_Err
1199	Coroutine_Continue_(
1200	Coroutines *cors,
1201	Coroutine *cor,
1202	void *value,
1203	bool early
1204	){
1205	cor = cor->chain_tip;
1206	if (cor->state == Coroutine_Running){
1207	// already running
1208	return Coroutine_OK;
1209	}
1210	if (cor->state != Coroutine_Idle && cor->state != Coroutine_Waiting){
1211	return Coroutine_Err_WrongState;
1212	}
1213	cor->entry_param = value;
1214	cor->state = Coroutine_Running;
1215	Link_Remove(&cor->link);
1216	if ( early ) {
1217	List_AddHead(&cors->runable, &cor->link);
1218	} else {
1219	List_AddTail(&cors->runable, &cor->link);
1220	}
1221	_Cor_Mutex_Unlock(&cors->waiting_mutex);
1222	return Coroutine_OK;
1223	}
1224
1225
1226	Coroutine_Err
1227	Coroutine_Continue(
1228	Coroutine *cor,
1229	void *value,
1230	bool early
1231	){
1232	MyAssert(!Coroutine_StackHasOverrun());
1233	Coroutines *cors = cor->coroutines;
1234	_Cor_Mutex_Lock(&cors->mutex);
1235	Coroutine_Err err = Coroutine_Continue_(cors, cor, value, early);
1236	_Cor_Mutex_Unlock(&cors->mutex);
1237	return err;
1238	}
1239
1240
1241	void *
1242	Coroutine_Yield(
1243	void *value,
1244	Coroutine_YieldCallback on_yield,
1245	void *yield_me
1246	){
1247	MyAssert(g_c);
1248	Coroutine *me = g_c->active;
1249	MyAssert(me);
1250	MyAssert(!Coroutine_StackHasOverrun());
1251
1252	_Cor_Mutex_Lock(&g_c->mutex);
1253	Coroutines *cors = me->coroutines;
1254	MyAssert(me && me->state == Coroutine_Running && cors == g_c);
1255	me->stack_top = (unsigned char *)StackTopNow();
1256	me->value = NULL;
1257	me->chain_root->value = value;
1258	Coroutine *prev_tip = me->chain_root->chain_tip;
1259	me->chain_root->chain_tip = me;
1260	me->state = Coroutine_Waiting;
1261
1262	TrimActiveIfPossible();
1263
1264	Link_Remove(&me->link);
1265	if (!List_IsEmpty(&cors->runable)){
1266	_Cor_Mutex_Unlock(&cors->waiting_mutex);
1267	}
1268	List_AddTail(&cors->waiting, &me->link);
1269
1270	switch (setjmp(me->buf)){
1271	case Chunk_Initial:
1272	ready_jmp_buf(me->buf);
1273	_Cor_Mutex_Unlock(&cors->mutex);
1274	on_yield(yield_me);
1275	Coroutine_RunNext();
1276	MyAssert(false);
1277	break;
1278	case Chunk_Enter:
1279	// arrive here with mutex locked
1280	cors->active = me;
1281	MyAssert(!Coroutine_StackHasOverrun());
1282	// when we return here - we are running again
1283	MyAssert(me->state == Coroutine_Running);
1284	EnlargeActiveIfPossible();
1285	me->chain_root->chain_tip = prev_tip;
1286	void *res = me->entry_param;
1287	_Cor_Mutex_Unlock(&cors->mutex);
1288	return res;
1289	}
1290	MyAssert(false);
1291	return NULL;
1292	}
1293
1294
1295	void *
1296	Coroutine_GetValue(
1297	Coroutine *cor
1298	){
1299	return cor->value;
1300	}
1301
1302
1303	Coroutine *
1304	Coroutine_GetActive(
1305	void
1306	){
1307	return g_c ? g_c->active->chain_root : NULL;
1308	}
1309
1310
1311	ptrdiff_t
1312	Coroutine_GetStackHeadroom(
1313	void
1314	){
1315	Coroutine *me = g_c ? g_c->active : NULL;
1316	if (me){
1317	// active coroutine
1318	if (me->guard){
1319	return StackPointerDiff(me->guard, (unsigned char *)StackTopNow());
1320	} else if (me->limit) {
1321	return StackPointerDiff(me->limit, (unsigned char *)StackTopNow());
1322	}
1323	} else {
1324	// no active coroutine
1325	if (g_stack_limit){
1326	return StackPointerDiff(g_stack_limit, (unsigned char *)StackTopNow());
1327	}
1328	}
1329	// The biggest ptrdiff_t possible
1330	return PTRDIFF_MAX;
1331	}
1332
1333
1334	void *
1335	Coroutine_GetStackHWM(
1336	void
1337	){
1338	MyAssert(g_c);
1339	MyAssert(g_c->state == Coroutines_Started);
1340	MyAssert(!Coroutine_StackHasOverrun());
1341	// Find where the guards end
1342	unsigned char *guard = g_c->active->guard;
1343	if (guard){
1344	ptrdiff_t headroom = Coroutine_GetStackHeadroom();
1345	for (ptrdiff_t i = 0; i <= headroom; i += GUARD_PATTERN_SIZE){
1346	if (!Guard_Pattern_OK(StackPointerAdd(guard, -i))){
1347	return StackPointerAdd(guard, i);
1348	}
1349	}
1350	}
1351	return guard;
1352	}
1353
1354
1355	void
1356	Coroutine_ClearStackForHWM(
1357	void
1358	){
1359	MyAssert(g_c);
1360	MyAssert(!Coroutine_StackHasOverrun());
1361	unsigned char *guard = g_c->active->guard;
1362	if (guard){
1363	ptrdiff_t headroom = Coroutine_GetStackHeadroom();
1364	for (ptrdiff_t i = 0; i <= headroom; i += GUARD_PATTERN_SIZE){
1365	Apply_Guard(StackPointerAdd(guard, -i));
1366	}
1367	}
1368	}
1369
1370
1371	static bool
1372	Coroutine_CanStartCoroutine_Lock_Assumed(
1373	size_t min_size
1374	){
1375	if (!g_c->stack_limit){
1376	return true;
1377	}
1378
1379	// check free list
1380	List_Link *link;
1381	for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
1382	Coroutine *cor = List_Link_Container(Coroutine, link, link);
1383	size_t cor_size = Coroutine_Size(cor);
1384	if (cor_size >= min_size){
1385	return true;
1386	}
1387	}
1388
1389	// Check if this coroutine has enough size
1390	Coroutine *me = g_c->active;
1391	me->stack_top = (unsigned char *)StackTopNow();
1392	ptrdiff_t reduced_size = TrimmableSize(g_c->active);
1393	if (reduced_size && StackPointerDiff(g_c->active->limit, g_c->active->base) - reduced_size > (ptrdiff_t)min_size){
1394	return true;
1395	}
1396
1397	return false;
1398	}
1399
1400	bool
1401	Coroutine_CanStartCoroutine(
1402	size_t size
1403	){
1404	MyAssert(g_c && g_c->state == Coroutines_Started);
1405	MyAssert(!Coroutine_StackHasOverrun());
1406
1407	_Cor_Mutex_Lock(&g_c->mutex);
1408
1409	bool result = Coroutine_CanStartCoroutine_Lock_Assumed(size);
1410
1411	_Cor_Mutex_Unlock(&g_c->mutex);
1412
1413	return result;
1414	}
1415
1416	static bool
1417	Coroutine_GetUsefulFreeSpace_Lock_Assumed(
1418	size_t min_size,
1419	size_t overhead
1420	){
1421	if (!g_c->stack_limit){
1422	return SIZE_MAX;
1423	}
1424
1425	size_t total = 0;
1426
1427	// check free list
1428	List_Link *link;
1429	for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
1430	Coroutine *cor = List_Link_Container(Coroutine, link, link);
1431	size_t cor_size = Coroutine_Size(cor);
1432	if (cor_size >= min_size){
1433	total += cor_size - overhead;
1434	}
1435	}
1436
1437	return total;
1438	}
1439
1440	size_t
1441	Coroutine_GetUsefulFreeSpace(
1442	size_t min_size,
1443	size_t overhead
1444	){
1445	MyAssert(g_c && g_c->state == Coroutines_Started);
1446	MyAssert(!Coroutine_StackHasOverrun());
1447
1448	if (min_size < overhead){
1449	min_size = overhead;
1450	}
1451
1452	_Cor_Mutex_Lock(&g_c->mutex);
1453
1454	size_t result = Coroutine_GetUsefulFreeSpace_Lock_Assumed(min_size, overhead);
1455
1456	_Cor_Mutex_Unlock(&g_c->mutex);
1457
1458	return result;
1459	}
1460
1461	void *
1462	Coroutine_GetCStackTop(
1463	void
1464	){
1465	if (!g_c \|\| g_c->tip == g_c->active){
1466	return (void *)StackTopNow();
1467	}
1468
1469	return g_c->tip->stack_top;
1470	}
1471
1472
1473	// Inspired by cpython...
1474	#ifdef __has_builtin
1475	# define Coroutine__has_builtin(x) __has_builtin(x)
1476	#else
1477	# define Coroutine__has_builtin(x) 0
1478	#endif
1479
1480	#if !Coroutine__has_builtin(__builtin_frame_address) && !defined(__GNUC__) && !defined(_MSC_VER)
1481	static uintptr_t return_pointer_as_int(char* p) {
1482	return (uintptr_t)p;
1483	}
1484	#endif
1485
1486	static inline uintptr_t
1487	StackTopNow(void) {
1488	#if Coroutine__has_builtin(__builtin_frame_address) \|\| defined(__GNUC__)
1489	return (uintptr_t)__builtin_frame_address(0);
1490	#elif defined(_MSC_VER)
1491	return (uintptr_t)_AddressOfReturnAddress();
1492	#else
1493	char here;
1494	/* Avoid compiler warning about returning stack address */
1495	return return_pointer_as_int(&here);
1496	#endif
1497	}
1498	// ...inspired by cpython
1499
1500
1501	struct Coroutine_ChainParam {
1502	Coroutine_Start start;
1503	void *value;
1504	Coroutine *ret;
1505	};
1506
1507
1508	static void *
1509	Coroutine_ChainFn(
1510	void *param
1511	){
1512	struct Coroutine_ChainParam params = (struct Coroutine_ChainParam )param;
1513	void *res = params.start(params.value);
1514	params.ret->chain_tip = params.ret;
1515	return (void *)(uintptr_t)Coroutine_Continue(params.ret, res, true);
1516	}
1517
1518
1519	static void
1520	Coroutine_ChainYield(
1521	void *unused
1522	){
1523	(void)unused;
1524	}
1525
1526
1527	Coroutine_Err
1528	Coroutine_Chain(
1529	size_t min_size,
1530	size_t min_headroom,
1531	Coroutine_Start start,
1532	void *value,
1533	void **result
1534	){
1535	MyAssert(!Coroutine_StackHasOverrun());
1536	Coroutine *cor = Coroutine_New(min_size, min_headroom, Coroutine_ChainFn);
1537	if (!cor){
1538	// failed
1539	return Coroutine_Err_NoStack;
1540	}
1541	cor->chain_root = g_c->active->chain_root;
1542	g_c->active->chain_tip = cor;
1543	struct Coroutine_ChainParam params = {
1544	start,
1545	value,
1546	g_c->active,
1547	};
1548	Coroutine_Err err = Coroutine_Continue(cor, &params, true);
1549	if (!err){
1550	void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
1551	err = (Coroutine_Err)(uintptr_t)Coroutine_GetValue(cor);
1552	if (!err && result){
1553	*result = res;
1554	}
1555	}
1556	Coroutine_Delete(cor);
1557	// success! ...probably
1558	return err;
1559	}
1560
1561
1562	static Coroutine *
1563	Coroutine_BiggestFreeBlock_Lock_Assumed(
1564	void
1565	){
1566	// check free list
1567	Coroutine *best = NULL;
1568	size_t best_size = 0;
1569	List_Link *link;
1570	for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
1571	Coroutine *cor = List_Link_Container(Coroutine, link, link);
1572	size_t cor_size = Coroutine_Size(cor);
1573	if (cor_size > best_size){
1574	best = cor;
1575	best_size = cor_size;
1576	}
1577	}
1578
1579	return best;
1580	}
1581
1582
1583	Coroutine_Err
1584	Coroutine_CallWithMaxStack(
1585	Coroutine_Start start,
1586	void *value,
1587	void **result
1588	){
1589	MyAssert(!Coroutine_StackHasOverrun());
1590	size_t headroom = (size_t)Coroutine_GetStackHeadroom();
1591	if (headroom != PTRDIFF_MAX){
1592	_Cor_Mutex_Lock(&g_c->mutex);
1593
1594	Coroutine *cor = Coroutine_BiggestFreeBlock_Lock_Assumed();
1595
1596	if (cor && Coroutine_Size(cor) > headroom){
1597	// use cor for chaining
1598	Coroutine *active = Coroutine_GetActive();
1599	cor->min_size = active->min_size;
1600	cor->min_headroom = active->min_headroom;
1601	cor->state = Coroutine_Idle;
1602	cor->start = Coroutine_ChainFn;
1603	cor->value = NULL;
1604	cor->chain_root = g_c->active->chain_root;
1605	cor->chain_tip = cor;
1606	g_c->active->chain_tip = cor;
1607	Link_Remove(&cor->link);
1608	List_AddHead(&g_c->inactive, &cor->link);
1609	g_c->report.coroutines_created += 1;
1610	} else {
1611	cor = NULL;
1612	}
1613
1614	_Cor_Mutex_Unlock(&g_c->mutex);
1615
1616	if (cor){
1617	// we're chaining, not calling
1618	struct Coroutine_ChainParam params = {
1619	start,
1620	value,
1621	g_c->active
1622	};
1623	Coroutine_Err err = Coroutine_Continue(cor, &params, true);
1624	if (!err){
1625	void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
1626	err = (Coroutine_Err)(uintptr_t)Coroutine_GetValue(cor);
1627	if (!err && result){
1628	*result = res;
1629	}
1630	}
1631	Coroutine_Delete(cor);
1632	return err;
1633	}
1634	}
1635	void *ret = start(value);
1636	if (result){
1637	*result = ret;
1638	}
1639	return Coroutine_OK;
1640	}
1641
1642
1643	bool
1644	Coroutine_IsRunning(
1645	Coroutine *cor
1646	){
1647	int state = cor->chain_tip->state;
1648	return state == Coroutine_Running \|\| state == Coroutine_Waiting;
1649	}
1650
1651
1652	bool Coroutine_IsComplete(
1653	Coroutine *cor
1654	){
1655	int state = cor->chain_tip->state;
1656	return state == Coroutine_Complete;
1657	}
1658
1659
1660	bool
1661	Coroutine_IsStarted(
1662	void
1663	){
1664	return g_c && g_c->state == Coroutines_Started;
1665	}
1666
1667	void
1668	Coroutine_Dump_(
1669	void
1670	){
1671	char *state_to_text[] = {
1672	"Free",
1673	"Idle",
1674	"Running",
1675	"Waiting",
1676	"Complete"
1677	};
1678	unsigned idx = 0;
1679	List_Link *link;
1680	for (link = List_Begin(&g_c->all); Link_NextIsLink(link); link = Link_Next(link)){
1681	Coroutine *cor = List_Link_Container(Coroutine, all_link, link);
1682	printf("%d) %p %p %zu (%s) %s\n", idx++, cor, cor->base, StackPointerDiff(cor->limit, cor->base), state_to_text[cor->state], cor == g_c->tip ? " (TIP)" : "");
1683	}
1684	}
1685	#include "coroutine_names_undef.h"
1686