1689 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);
389	static void stack_chunk_base(Coroutines cors, Coroutine parent, unsigned char prev_limit, unsigned char limit);
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	){
576	unsigned char *chunk_of_stack = alloca(chunk_size);
577	unsigned char *limit = StackLimitEnd(chunk_of_stack, chunk_of_stack+chunk_size);
578	unsigned char *guard = StackPointerAdd(limit, -GUARD_PATTERN_SIZE);
579	#if COROUTINE_RECORD_LOWEST_HEADROOM
580	for (size_t i = 0; i <= chunk_size-GUARD_PATTERN_SIZE; i += GUARD_PATTERN_SIZE){
581	Apply_Guard(StackPointerAdd(guard, -(ptrdiff_t)i));
582	}
583	#else
584	Apply_Guard(guard);
585	#endif
586	if (parent){
587	parent->limit = limit;
588	parent->guard = guard;
589	}
590	stack_chunk_base(cors, parent, limit, childs_limit);
591	}
592
593
594	static void
595	stack_chunk_base(
596	Coroutines *cors,
597	Coroutine *parent,
598	unsigned char *prev_limit,
599	unsigned char *limit
600	){
601	MyAssert(cors->spare);
602	Coroutine *here = cors->spare;
603	cors->spare = NULL;
604	here->coroutines = cors;
605	here->sequence = cors->sequence++;
606	here->state = Coroutine_Free;
607	here->base = prev_limit;
608	here->limit = limit;
609	here->stack_top = (unsigned char *)StackTopNow();
610	if (limit){
611	here->guard = StackPointerAdd(limit, -GUARD_PATTERN_SIZE);
612	Apply_Guard(here->guard);
613	} else {
614	here->guard = NULL;
615	}
616
617	// insert into all list
618	if (parent){
619	Link_AddAfter(&here->all_link, &parent->all_link);
620	} else {
621	List_AddHead(&cors->all, &here->all_link);
622	}
623	// add to free list
624	List_AddTail(&cors->free, &here->link);
625
626	cors->report.coroutines_pool_size += 1;
627
628	if (!cors->tip \|\| !Link_NextIsLink(Link_Next(&here->all_link))){
629	cors->tip = here;
630	}
631
632	for(;;){
633	switch (setjmp(here->buf)) {
634	case Chunk_Initial:
635	ready_jmp_buf(here->buf);
636	if (here->state == Coroutine_Free){
637	// return to the coroutine allocator
638	longjmp(cors->chunk_allocated, 1);
639	} else {
640	MyAssert(here->state == Coroutine_Complete);
641	// we finish here to ensure the setjmp is redone
642	if (cors->primary == here) {
643	// if primary coroutine - return to Coroutine_Run
644	longjmp(cors->controller, Coroutines_CoroutineComplete);
645	}
646	_Cor_Mutex_Unlock(&cors->mutex);
647	Coroutine_RunNext();
648	}
649	MyAssert(false);
650	break;
651	case Chunk_Split:
652	// Request to split this idle block into two
653	// g_c->size_to_retain will be set to our shorter size
654	ReserveStackSpace(here->coroutines, here, g_c->size_to_retain, here->limit);
655	MyAssert(false);
656	break;
657	case Chunk_Enter:
658	// request to start a coroutine (ie use the chunk for a coroutine)
659	// arrive here with mutex locked
660	MyAssert(here->state == Coroutine_Running);
661	here->coroutines->active = here;
662	EnlargeActiveIfPossible();
663	_Cor_Mutex_Unlock(&cors->mutex);
664	here->value = here->start(here->entry_param);
665
666	// check the guard
667	MyAssert(Guard_Pattern_OK(here->guard));
668
669	here->stack_top = (unsigned char *)StackTopNow();
670	_Cor_Mutex_Lock(&here->coroutines->mutex);
671	TrimActiveIfPossible();
672	here->coroutines->active = NULL;
673	MyAssert(here->state == Coroutine_Running);
674	Link_Remove(&here->link);
675	here->state = Coroutine_Complete;
676	List_AddTail(&here->coroutines->inactive, &here->link);
677	// Coroutine has completed
678	// Loop round to redo the setjmp() - if this coroutine yielded, then the setjmp will
679	// need reseting
680	break;
681	}
682	}
683	}
684
685
686	static void
687	Coroutine_RunNext(
688	void
689	){
690	// arrive here with mutex unlocked
691	_Cor_Mutex_Lock(&g_c->waiting_mutex);
692	_Cor_Mutex_Lock(&g_c->mutex);
693	Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c->runable));
694	MyAssert(next->state == Coroutine_Running);
695	longjmp(next->buf, Chunk_Enter);
696	MyAssert(false);
697	}
698
699
700	/// @brief Ensures there's a spare Coroutine for cors
701	/// @param cors The Coroutines to ensure a spare for
702	/// @return true there is a spare; false there isn't
703	static inline bool
704	EnsureSpare
705	(
706	Coroutines *cors
707	){
708	if (cors->spare){
709	return true;
710	}
711	cors->spare = malloc(sizeof(*cors->spare));
712	return cors->spare != NULL;
713	}
714
715
716	static Coroutine_Err
717	Coroutines_ctor(
718	Coroutines *cors,
719	size_t min_size,
720	size_t min_headroom
721	){
722	if (_Cor_Mutex_ctor(&cors->mutex)){
723	goto error;
724	}
725	cors->primary = NULL;
726	cors->stack_limit = g_stack_limit;
727
728	List_Init(&cors->all);
729	List_Init(&cors->free);
730	List_Init(&cors->inactive);
731	List_Init(&cors->runable);
732	List_Init(&cors->waiting);
733	if (_Cor_Mutex_ctor(&cors->waiting_mutex)){
734	goto error1;
735	}
736	if (_Cor_Mutex_Lock(&cors->waiting_mutex)){
737	goto error2;
738	}
739
740	cors->report.coroutines_created = 0;
741	cors->report.coroutines_pool_size = 0;
742	cors->report.largest_stack = 0;
743	cors->spare = NULL;
744	cors->sequence = 0;
745
746	Coroutine cor = malloc(sizeof(cor));
747	cor->min_size = min_size;
748	cor->min_headroom = min_headroom;
749	cor->coroutines = cors;
750	cor->sequence = cors->sequence++;
751	cor->state = Coroutine_Running;
752	cor->base = (unsigned char *)&cor;
753	cor->chain_root = cor;
754	cor->chain_tip = cor;
755	if (cors->stack_limit){
756	cor->limit = cors->stack_limit;
757	#if COROUTINE_GUARD_AT_C_STACK_LIMIT
758	cor->guard = StackPointerAdd(cor->limit, -GUARD_PATTERN_SIZE);
759	Apply_Guard(cor->guard);
760	#else
761	cor->guard = NULL;
762	#endif
763	} else {
764	cor->limit = cor->guard = NULL;
765	}
766	cors->root = cor;
767	List_AddHead(&cors->all, &cor->all_link);
768	List_AddTail(&cors->runable, &cor->link);
769	cors->tip = cors->active = cor;
770
771	cors->report.coroutines_pool_size += 1;
772
773	cors->state = Coroutines_Started;
774	return Coroutine_OK;
775	error2:
776	_Cor_Mutex_dtor(&cors->waiting_mutex);
777	error1:
778	_Cor_Mutex_dtor(&cors->mutex);
779	error:
780	return Coroutine_Err_CouldNotInitialiseSystem;
781	}
782
783	static void
784	Coroutines_dtor(
785	Coroutines *cors
786	){
787	_Cor_Mutex_Lock(&cors->mutex);
788	cors->state = Coroutines_Stopping;
789
790	MyAssert(List_IsEmpty(&cors->inactive));
791
792	// free the spare
793	if (cors->spare){
794	free(cors->spare);
795	}
796
797	// free all non-spares
798	List_Link *link;
799	List_Link *next;
800	for (link = List_Begin(&cors->all); Link_NextIsLink(link); link = next){
801	next = Link_Next(link);
802	Coroutine *cor = List_Link_Container(Coroutine, all_link, link) ;
803	free(cor);
804	}
805
806	_Cor_Mutex_Unlock(&cors->waiting_mutex);
807	_Cor_Mutex_dtor(&cors->waiting_mutex);
808
809	MyAssert(cors->state == Coroutines_Stopping);
810	_Cor_Mutex_Unlock(&cors->mutex);
811	_Cor_Mutex_dtor(&cors->mutex);
812	}
813
814
815	Coroutine_Err
816	Coroutine_RunSystem(
817	size_t min_size,
818	size_t min_headroom,
819	Coroutine_SystemStart start,
820	void *value
821	){
822	CHECK_SYSTEM_NOT_RUNNING
823
824	Coroutines cors;
825	Coroutine_Err err = Coroutines_ctor(&cors, min_size, min_headroom);
826	if (err){
827	return err;
828	}
829	g_c = &cors;
830	err = start(value, cors.root);
831	g_c = NULL;
832	Coroutines_dtor(&cors);
833	return err;
834	}
835
836
837	void
838	Coroutine_SetStackLimit(
839	void *limit
840	){
841	MyAssert(!limit \|\| !g_c \|\| !g_stack_limit \|\| StackPointerDiff((unsigned char )limit, (unsigned char )g_stack_limit) <= 0);
842	g_stack_limit = limit;
843	if (g_c){
844	g_c->stack_limit = limit;
845	if (g_c->tip){
846	g_c->tip->limit = limit;
847	#if COROUTINE_GUARD_AT_C_STACK_LIMIT
848	g_c->tip->guard = StackPointerAdd(limit, -GUARD_PATTERN_SIZE);
849	Apply_Guard(g_c->tip->guard);
850	#else
851	g_c->tip->guard = NULL;
852	#endif
853	}
854	}
855	}
856
857
858	#if COROUTINE_RECORD_LOWEST_HEADROOM
859	static size_t
860	Coroutine_UpdateMinimumHeadroom(
861	List_Head *list,
862	size_t headroom
863	){
864	for (List_Link *link = List_Begin(list); Link_NextIsLink(link); link = Link_Next(link)){
865	Coroutine *cor = List_Link_Container(Coroutine, link, link);
866	if (cor->guard){
867	size_t chunk_size = Coroutine_Size(cor);
868	for (size_t i = 0; i <= chunk_size-GUARD_PATTERN_SIZE; i += GUARD_PATTERN_SIZE){
869	if (!Guard_Pattern_OK(StackPointerAdd(cor->guard, -(ptrdiff_t)i))){
870	headroom = i < headroom ? i : headroom;
871	break;
872	}
873	}
874	}
875	}
876	return headroom;
877	}
878	#endif
879
880
881	Coroutine_Report
882	Coroutine_GetReport(
883	void
884	){
885	if (g_c){
886	size_t headroom;
887	#if COROUTINE_RECORD_LOWEST_HEADROOM
888	_Cor_Mutex_Lock(&g_c->mutex);
889	headroom = g_c->report.lowest_headroom;
890	headroom = Coroutine_UpdateMinimumHeadroom(&g_c->inactive, headroom);
891	headroom = Coroutine_UpdateMinimumHeadroom(&g_c->runable, headroom);
892	headroom = Coroutine_UpdateMinimumHeadroom(&g_c->waiting, headroom);
893	_Cor_Mutex_Unlock(&g_c->mutex);
894	#else
895	headroom = 0;
896	#endif
897	g_c->report.lowest_headroom = headroom;
898
899	return g_c->report;
900	} else {
901	Coroutine_Report ret = {0, 0, 0, 0};
902	return ret;
903	}
904	}
905
906
907	struct Coroutine_Run_Params {
908	Coroutine_Start start;
909	void *value;
910	void **result;
911	};
912
913	static Coroutine_Err
914	Coroutine_Run_Starter(
915	void *_params,
916	Coroutine *root
917	){
918	(void)root;
919	struct Coroutine_Run_Params params = (struct Coroutine_Run_Params )_params;
920
921	void *res = params->start(params->value);
922	if (params->result){
923	*params->result = res;
924	}
925
926	return Coroutine_OK;
927	}
928
929
930	Coroutine_Err Coroutine_Run(
931	size_t min_size,
932	size_t min_headroom,
933	Coroutine_Start start,
934	void *value,
935	void **result
936	){
937	if (!g_c){
938	struct Coroutine_Run_Params params = {start, value, result};
939	return Coroutine_RunSystem(min_size, min_headroom, Coroutine_Run_Starter, &params);
940	}
941
942	// We are in an active coroutine, so call start() directly
943	CHECK_STACK_OVERRUN
944	void *res = start(value);
945	if (result){
946	*result = res;
947	}
948
949	// no failures, so...
950	return Coroutine_OK;
951	}
952
953
954	static Coroutine *Coroutine_New_Lock_Assumed(
955	size_t min_size,
956	size_t min_headroom,
957	Coroutine_Start start
958	){
959	List_Link *link;
960
961	if (!EnsureSpare(g_c)){
962	return NULL;
963	}
964
965	Coroutine *cor = NULL;
966	for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
967	Coroutine *candidate = List_Link_Container(Coroutine, link, link);
968	MyAssert(candidate->coroutines == g_c);
969	MyAssert(candidate->state == Coroutine_Free);
970	if (candidate->limit){
971	size_t candidate_size = Coroutine_Size(candidate);
972	if (candidate_size < min_size){
973	continue;
974	}
975	}
976	// candidate has no limit, or is big enough
977
978	// check if it's 'better' (lower in the C stack) than cor
979	if (!cor \|\| StackPointerDiff(candidate->base, cor->base) < 0){
980	// chunk big enough, and a better choice than cor
981	cor = candidate;
982	}
983	}
984
985	if (!cor){
986	return NULL;
987	}
988
989	// use this free block
990	cor->min_size = min_size;
991	cor->min_headroom = min_headroom;
992	cor->state = Coroutine_Idle;
993	cor->start = start;
994	cor->value = NULL;
995	cor->chain_root = cor;
996	cor->chain_tip = cor;
997	Link_Remove(&cor->link);
998	List_AddHead(&g_c->inactive, &cor->link);
999
1000	// trim down to an appropriate size
1001	size_t trimmable_size = TrimmableSize(cor);
1002	if (trimmable_size){
1003	// split block into two
1004	if (EnsureSpare(g_c)){
1005	g_c->size_to_retain = trimmable_size;
1006	if (!setjmp(g_c->chunk_allocated)){
1007	ready_jmp_buf(g_c->chunk_allocated);
1008	longjmp(cor->buf, Chunk_Split);
1009	}
1010	}
1011	}
1012
1013	g_c->report.coroutines_created += 1;
1014
1015	return cor;
1016	}
1017
1018
1019	static void
1020	TrimActiveIfPossible
1021	(
1022	void
1023	){
1024	MyAssert(g_c);
1025
1026	// If we're the active coroutine, free the tail
1027	Coroutine *active = g_c->active;
1028	MyAssert(active);
1029
1030	active->stack_top = (unsigned char *)StackTopNow();
1031	ptrdiff_t timmablesize = TrimmableSize(active);
1032	if (!timmablesize){
1033	return;
1034	}
1035
1036	if (!EnsureSpare(g_c)){
1037	return;
1038	}
1039
1040	// enough space for a second coroutine so free the unused stack space from active
1041	if (!setjmp(g_c->chunk_allocated)){
1042	ready_jmp_buf(g_c->chunk_allocated);
1043	ReserveStackSpace(g_c, active, timmablesize - StackPointerDiff(active->stack_top, active->base), active->limit);
1044	MyAssert(false);
1045	}
1046	}
1047
1048
1049	static void
1050	EnlargeActiveIfPossible(
1051	void
1052	){
1053	MyAssert(g_c);
1054	Coroutine *active = g_c->active;
1055	MyAssert(active);
1056
1057	List_Link *next = Link_Next(&active->all_link);
1058	if (!Link_NextIsLink(next)){
1059	return;
1060	}
1061	Coroutine *cor = List_Link_Container(Coroutine, all_link, next);
1062	if (cor->state != Coroutine_Free){
1063	return;
1064	}
1065
1066	// Following block is free, merge with this
1067	active->limit = cor->limit;
1068	active->guard = cor->guard;
1069	Link_Remove(&cor->link);
1070	Link_Remove(&cor->all_link);
1071	if (g_c->tip == cor){
1072	g_c->tip = active;
1073	}
1074	if (g_c->spare){
1075	free(cor);
1076	} else {
1077	g_c->spare = cor;
1078	}
1079	}
1080
1081
1082	Coroutine *
1083	Coroutine_New(
1084	size_t min_size,
1085	size_t min_headroom,
1086	Coroutine_Start start
1087	){
1088	MyAssert(g_c && g_c->state == Coroutines_Started);
1089	MyAssert(!Coroutine_StackHasOverrun());
1090
1091	// Make the paramaters make sense
1092	if (min_size < min_headroom){
1093	min_size = min_headroom;
1094	}
1095
1096	_Cor_Mutex_Lock(&g_c->mutex);
1097
1098	TrimActiveIfPossible();
1099
1100	Coroutine *cor = Coroutine_New_Lock_Assumed(min_size, min_headroom, start);
1101
1102	if (cor && Coroutine_Size(cor) > g_c->report.largest_stack){
1103	g_c->report.largest_stack = Coroutine_Size(cor);
1104	}
1105
1106	EnlargeActiveIfPossible();
1107
1108	_Cor_Mutex_Unlock(&g_c->mutex);
1109
1110	return cor;
1111	}
1112
1113
1114	void
1115	Coroutine_Delete(
1116	Coroutine *cor
1117	){
1118	MyAssert(!Coroutine_StackHasOverrun());
1119	if (cor){
1120	Coroutines *cors = cor->coroutines;
1121	_Cor_Mutex_Lock(&cors->mutex);
1122	MyAssert(cor->state == Coroutine_Idle \|\| cor->state == Coroutine_Complete);
1123
1124	#if COROUTINE_RECORD_LOWEST_HEADROOM
1125	if (cor->guard){
1126	unsigned char *guard = cor->guard;
1127	ptrdiff_t chunk_size = Coroutine_Size(cor);
1128	ptrdiff_t myheadroom;
1129	for (myheadroom = 0; myheadroom <= chunk_size-(ptrdiff_t)GUARD_PATTERN_SIZE; myheadroom += GUARD_PATTERN_SIZE){
1130	if (!Guard_Pattern_OK(StackPointerAdd(guard, -myheadroom))){
1131	break;
1132	}
1133	}
1134	if (myheadroom < (ptrdiff_t)g_c->report.lowest_headroom \|\| g_c->report.lowest_headroom == 0){
1135	g_c->report.lowest_headroom = myheadroom;
1136	}
1137	}
1138	#endif
1139
1140	cor->state = Coroutine_Free;
1141	Link_Remove(&cor->link);
1142
1143	// insert into free list
1144	List_AddHead(&cors->free, &cor->link);
1145
1146	// Check for merge with following Coroutine
1147	List_Link *link = Link_Next(&cor->all_link);
1148	if (Link_NextIsLink(link)){
1149	Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
1150	if (listcor->state == Coroutine_Free){
1151	// merge
1152	cor->limit = listcor->limit;
1153	cor->guard = listcor->guard;
1154	Link_Remove(&listcor->all_link);
1155	Link_Remove(&listcor->link);
1156	if (g_c->tip == listcor){
1157	g_c->tip = cor;
1158	}
1159
1160	// free up the now unused struct
1161	if (g_c->spare){
1162	free(listcor);
1163	} else {
1164	g_c->spare = listcor;
1165	}
1166	}
1167	}
1168
1169	// check for merge with prev coroutine
1170	link = Link_Prev(&cor->all_link);
1171	if (Link_PrevIsLink(link)){
1172	Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
1173	if (listcor->state == Coroutine_Free){
1174	// merge
1175	listcor->limit = cor->limit;
1176	listcor->guard = cor->guard;
1177	Link_Remove(&cor->all_link);
1178	Link_Remove(&cor->link);
1179	if (g_c->tip == cor){
1180	g_c->tip = listcor;
1181	}
1182
1183	// free up the now unused struct
1184	if (g_c->spare){
1185	free(cor);
1186	} else {
1187	g_c->spare = cor;
1188	}
1189	}
1190	}
1191
1192	EnlargeActiveIfPossible();
1193
1194	_Cor_Mutex_Unlock(&cors->mutex);
1195	}
1196	}
1197
1198
1199	// Coroutine_Continue, assuming the mutex is claimed
1200	// return false for success, true for something went wrong
1201	static Coroutine_Err
1202	Coroutine_Continue_(
1203	Coroutines *cors,
1204	Coroutine *cor,
1205	void *value,
1206	bool early
1207	){
1208	cor = cor->chain_tip;
1209	if (cor->state == Coroutine_Running){
1210	// already running
1211	return Coroutine_OK;
1212	}
1213	if (cor->state != Coroutine_Idle && cor->state != Coroutine_Waiting){
1214	return Coroutine_Err_WrongState;
1215	}
1216	cor->entry_param = value;
1217	cor->state = Coroutine_Running;
1218	Link_Remove(&cor->link);
1219	if ( early ) {
1220	List_AddHead(&cors->runable, &cor->link);
1221	} else {
1222	List_AddTail(&cors->runable, &cor->link);
1223	}
1224	_Cor_Mutex_Unlock(&cors->waiting_mutex);
1225	return Coroutine_OK;
1226	}
1227
1228
1229	Coroutine_Err
1230	Coroutine_Continue(
1231	Coroutine *cor,
1232	void *value,
1233	bool early
1234	){
1235	MyAssert(!Coroutine_StackHasOverrun());
1236	Coroutines *cors = cor->coroutines;
1237	_Cor_Mutex_Lock(&cors->mutex);
1238	Coroutine_Err err = Coroutine_Continue_(cors, cor, value, early);
1239	_Cor_Mutex_Unlock(&cors->mutex);
1240	return err;
1241	}
1242
1243
1244	void *
1245	Coroutine_Yield(
1246	void *value,
1247	Coroutine_YieldCallback on_yield,
1248	void *yield_me
1249	){
1250	MyAssert(g_c);
1251	Coroutine *me = g_c->active;
1252	MyAssert(me);
1253	MyAssert(!Coroutine_StackHasOverrun());
1254
1255	_Cor_Mutex_Lock(&g_c->mutex);
1256	Coroutines *cors = me->coroutines;
1257	MyAssert(me && me->state == Coroutine_Running && cors == g_c);
1258	me->stack_top = (unsigned char *)StackTopNow();
1259	me->value = NULL;
1260	me->chain_root->value = value;
1261	Coroutine *prev_tip = me->chain_root->chain_tip;
1262	me->chain_root->chain_tip = me;
1263	me->state = Coroutine_Waiting;
1264
1265	TrimActiveIfPossible();
1266
1267	Link_Remove(&me->link);
1268	if (!List_IsEmpty(&cors->runable)){
1269	_Cor_Mutex_Unlock(&cors->waiting_mutex);
1270	}
1271	List_AddTail(&cors->waiting, &me->link);
1272
1273	switch (setjmp(me->buf)){
1274	case Chunk_Initial:
1275	ready_jmp_buf(me->buf);
1276	_Cor_Mutex_Unlock(&cors->mutex);
1277	on_yield(yield_me);
1278	Coroutine_RunNext();
1279	MyAssert(false);
1280	break;
1281	case Chunk_Enter:
1282	// arrive here with mutex locked
1283	cors->active = me;
1284	MyAssert(!Coroutine_StackHasOverrun());
1285	// when we return here - we are running again
1286	MyAssert(me->state == Coroutine_Running);
1287	EnlargeActiveIfPossible();
1288	me->chain_root->chain_tip = prev_tip;
1289	void *res = me->entry_param;
1290	_Cor_Mutex_Unlock(&cors->mutex);
1291	return res;
1292	}
1293	MyAssert(false);
1294	return NULL;
1295	}
1296
1297
1298	void *
1299	Coroutine_GetValue(
1300	Coroutine *cor
1301	){
1302	return cor->value;
1303	}
1304
1305
1306	Coroutine *
1307	Coroutine_GetActive(
1308	void
1309	){
1310	return g_c ? g_c->active->chain_root : NULL;
1311	}
1312
1313
1314	ptrdiff_t
1315	Coroutine_GetStackHeadroom(
1316	void
1317	){
1318	Coroutine *me = g_c ? g_c->active : NULL;
1319	if (me){
1320	// active coroutine
1321	if (me->guard){
1322	return StackPointerDiff(me->guard, (unsigned char *)StackTopNow());
1323	} else if (me->limit) {
1324	return StackPointerDiff(me->limit, (unsigned char *)StackTopNow());
1325	}
1326	} else {
1327	// no active coroutine
1328	if (g_stack_limit){
1329	return StackPointerDiff(g_stack_limit, (unsigned char *)StackTopNow());
1330	}
1331	}
1332	// The biggest ptrdiff_t possible
1333	return PTRDIFF_MAX;
1334	}
1335
1336
1337	void *
1338	Coroutine_GetStackHWM(
1339	void
1340	){
1341	MyAssert(g_c);
1342	MyAssert(g_c->state == Coroutines_Started);
1343	MyAssert(!Coroutine_StackHasOverrun());
1344	// Find where the guards end
1345	unsigned char *guard = g_c->active->guard;
1346	if (guard){
1347	ptrdiff_t headroom = Coroutine_GetStackHeadroom();
1348	for (ptrdiff_t i = 0; i <= headroom; i += GUARD_PATTERN_SIZE){
1349	if (!Guard_Pattern_OK(StackPointerAdd(guard, -i))){
1350	return StackPointerAdd(guard, i);
1351	}
1352	}
1353	}
1354	return guard;
1355	}
1356
1357
1358	void
1359	Coroutine_ClearStackForHWM(
1360	void
1361	){
1362	MyAssert(g_c);
1363	MyAssert(!Coroutine_StackHasOverrun());
1364	unsigned char *guard = g_c->active->guard;
1365	if (guard){
1366	ptrdiff_t headroom = Coroutine_GetStackHeadroom();
1367	for (ptrdiff_t i = 0; i <= headroom; i += GUARD_PATTERN_SIZE){
1368	Apply_Guard(StackPointerAdd(guard, -i));
1369	}
1370	}
1371	}
1372
1373
1374	static bool
1375	Coroutine_CanStartCoroutine_Lock_Assumed(
1376	size_t min_size
1377	){
1378	if (!g_c->stack_limit){
1379	return true;
1380	}
1381
1382	// check free list
1383	List_Link *link;
1384	for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
1385	Coroutine *cor = List_Link_Container(Coroutine, link, link);
1386	size_t cor_size = Coroutine_Size(cor);
1387	if (cor_size >= min_size){
1388	return true;
1389	}
1390	}
1391
1392	// Check if this coroutine has enough size
1393	Coroutine *me = g_c->active;
1394	me->stack_top = (unsigned char *)StackTopNow();
1395	ptrdiff_t reduced_size = TrimmableSize(g_c->active);
1396	if (reduced_size && StackPointerDiff(g_c->active->limit, g_c->active->base) - reduced_size > (ptrdiff_t)min_size){
1397	return true;
1398	}
1399
1400	return false;
1401	}
1402
1403	bool
1404	Coroutine_CanStartCoroutine(
1405	size_t size
1406	){
1407	MyAssert(g_c && g_c->state == Coroutines_Started);
1408	MyAssert(!Coroutine_StackHasOverrun());
1409
1410	_Cor_Mutex_Lock(&g_c->mutex);
1411
1412	bool result = Coroutine_CanStartCoroutine_Lock_Assumed(size);
1413
1414	_Cor_Mutex_Unlock(&g_c->mutex);
1415
1416	return result;
1417	}
1418
1419	static bool
1420	Coroutine_GetUsefulFreeSpace_Lock_Assumed(
1421	size_t min_size,
1422	size_t overhead
1423	){
1424	if (!g_c->stack_limit){
1425	return SIZE_MAX;
1426	}
1427
1428	size_t total = 0;
1429
1430	// check free list
1431	List_Link *link;
1432	for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
1433	Coroutine *cor = List_Link_Container(Coroutine, link, link);
1434	size_t cor_size = Coroutine_Size(cor);
1435	if (cor_size >= min_size){
1436	total += cor_size - overhead;
1437	}
1438	}
1439
1440	return total;
1441	}
1442
1443	size_t
1444	Coroutine_GetUsefulFreeSpace(
1445	size_t min_size,
1446	size_t overhead
1447	){
1448	MyAssert(g_c && g_c->state == Coroutines_Started);
1449	MyAssert(!Coroutine_StackHasOverrun());
1450
1451	if (min_size < overhead){
1452	min_size = overhead;
1453	}
1454
1455	_Cor_Mutex_Lock(&g_c->mutex);
1456
1457	size_t result = Coroutine_GetUsefulFreeSpace_Lock_Assumed(min_size, overhead);
1458
1459	_Cor_Mutex_Unlock(&g_c->mutex);
1460
1461	return result;
1462	}
1463
1464	void *
1465	Coroutine_GetCStackTop(
1466	void
1467	){
1468	if (!g_c \|\| g_c->tip == g_c->active){
1469	return (void *)StackTopNow();
1470	}
1471
1472	return g_c->tip->stack_top;
1473	}
1474
1475
1476	// Inspired by cpython...
1477	#ifdef __has_builtin
1478	# define Coroutine__has_builtin(x) __has_builtin(x)
1479	#else
1480	# define Coroutine__has_builtin(x) 0
1481	#endif
1482
1483	#if !Coroutine__has_builtin(__builtin_frame_address) && !defined(__GNUC__) && !defined(_MSC_VER)
1484	static uintptr_t return_pointer_as_int(char* p) {
1485	return (uintptr_t)p;
1486	}
1487	#endif
1488
1489	static inline uintptr_t
1490	StackTopNow(void) {
1491	#if Coroutine__has_builtin(__builtin_frame_address) \|\| defined(__GNUC__)
1492	return (uintptr_t)__builtin_frame_address(0);
1493	#elif defined(_MSC_VER)
1494	return (uintptr_t)_AddressOfReturnAddress();
1495	#else
1496	char here;
1497	/* Avoid compiler warning about returning stack address */
1498	return return_pointer_as_int(&here);
1499	#endif
1500	}
1501	// ...inspired by cpython
1502
1503
1504	struct Coroutine_ChainParam {
1505	Coroutine_Start start;
1506	void *value;
1507	Coroutine *ret;
1508	};
1509
1510
1511	static void *
1512	Coroutine_ChainFn(
1513	void *param
1514	){
1515	struct Coroutine_ChainParam params = (struct Coroutine_ChainParam )param;
1516	void *res = params.start(params.value);
1517	params.ret->chain_tip = params.ret;
1518	return (void *)(uintptr_t)Coroutine_Continue(params.ret, res, true);
1519	}
1520
1521
1522	static void
1523	Coroutine_ChainYield(
1524	void *unused
1525	){
1526	(void)unused;
1527	}
1528
1529
1530	Coroutine_Err
1531	Coroutine_Chain(
1532	size_t min_size,
1533	size_t min_headroom,
1534	Coroutine_Start start,
1535	void *value,
1536	void **result
1537	){
1538	MyAssert(!Coroutine_StackHasOverrun());
1539	Coroutine *cor = Coroutine_New(min_size, min_headroom, Coroutine_ChainFn);
1540	if (!cor){
1541	// failed
1542	return Coroutine_Err_NoStack;
1543	}
1544	cor->chain_root = g_c->active->chain_root;
1545	g_c->active->chain_tip = cor;
1546	struct Coroutine_ChainParam params = {
1547	start,
1548	value,
1549	g_c->active,
1550	};
1551	Coroutine_Err err = Coroutine_Continue(cor, &params, true);
1552	if (!err){
1553	void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
1554	err = (Coroutine_Err)(uintptr_t)Coroutine_GetValue(cor);
1555	if (!err && result){
1556	*result = res;
1557	}
1558	}
1559	Coroutine_Delete(cor);
1560	// success! ...probably
1561	return err;
1562	}
1563
1564
1565	static Coroutine *
1566	Coroutine_BiggestFreeBlock_Lock_Assumed(
1567	void
1568	){
1569	// check free list
1570	Coroutine *best = NULL;
1571	size_t best_size = 0;
1572	List_Link *link;
1573	for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
1574	Coroutine *cor = List_Link_Container(Coroutine, link, link);
1575	size_t cor_size = Coroutine_Size(cor);
1576	if (cor_size > best_size){
1577	best = cor;
1578	best_size = cor_size;
1579	}
1580	}
1581
1582	return best;
1583	}
1584
1585
1586	Coroutine_Err
1587	Coroutine_CallWithMaxStack(
1588	Coroutine_Start start,
1589	void *value,
1590	void **result
1591	){
1592	MyAssert(!Coroutine_StackHasOverrun());
1593	size_t headroom = (size_t)Coroutine_GetStackHeadroom();
1594	if (headroom != PTRDIFF_MAX){
1595	_Cor_Mutex_Lock(&g_c->mutex);
1596
1597	Coroutine *cor = Coroutine_BiggestFreeBlock_Lock_Assumed();
1598
1599	if (cor && Coroutine_Size(cor) > headroom){
1600	// use cor for chaining
1601	Coroutine *active = Coroutine_GetActive();
1602	cor->min_size = active->min_size;
1603	cor->min_headroom = active->min_headroom;
1604	cor->state = Coroutine_Idle;
1605	cor->start = Coroutine_ChainFn;
1606	cor->value = NULL;
1607	cor->chain_root = g_c->active->chain_root;
1608	cor->chain_tip = cor;
1609	g_c->active->chain_tip = cor;
1610	Link_Remove(&cor->link);
1611	List_AddHead(&g_c->inactive, &cor->link);
1612	g_c->report.coroutines_created += 1;
1613	} else {
1614	cor = NULL;
1615	}
1616
1617	_Cor_Mutex_Unlock(&g_c->mutex);
1618
1619	if (cor){
1620	// we're chaining, not calling
1621	struct Coroutine_ChainParam params = {
1622	start,
1623	value,
1624	g_c->active
1625	};
1626	Coroutine_Err err = Coroutine_Continue(cor, &params, true);
1627	if (!err){
1628	void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
1629	err = (Coroutine_Err)(uintptr_t)Coroutine_GetValue(cor);
1630	if (!err && result){
1631	*result = res;
1632	}
1633	}
1634	Coroutine_Delete(cor);
1635	return err;
1636	}
1637	}
1638	void *ret = start(value);
1639	if (result){
1640	*result = ret;
1641	}
1642	return Coroutine_OK;
1643	}
1644
1645
1646	bool
1647	Coroutine_IsRunning(
1648	Coroutine *cor
1649	){
1650	int state = cor->chain_tip->state;
1651	return state == Coroutine_Running \|\| state == Coroutine_Waiting;
1652	}
1653
1654
1655	bool Coroutine_IsComplete(
1656	Coroutine *cor
1657	){
1658	int state = cor->chain_tip->state;
1659	return state == Coroutine_Complete;
1660	}
1661
1662
1663	bool
1664	Coroutine_IsStarted(
1665	void
1666	){
1667	return g_c && g_c->state == Coroutines_Started;
1668	}
1669
1670	void
1671	Coroutine_Dump_(
1672	void
1673	){
1674	char *state_to_text[] = {
1675	"Free",
1676	"Idle",
1677	"Running",
1678	"Waiting",
1679	"Complete"
1680	};
1681	unsigned idx = 0;
1682	List_Link *link;
1683	for (link = List_Begin(&g_c->all); Link_NextIsLink(link); link = Link_Next(link)){
1684	Coroutine *cor = List_Link_Container(Coroutine, all_link, link);
1685	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)" : "");
1686	}
1687	}
1688	#include "coroutine_names_undef.h"
1689