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