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