367 lines9.8 KB

Newer

Older

Text Raw Blame

8 months ago		Moving things around	4	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 <semaphore.h>
				8	#include <fcntl.h>
				9	#include <unistd.h>
				10
				11	#define COROUTINE_STACK_SIZE 16384
				12	#define COROUTINE_STARTUP_STACK_SIZE 1024
				13
				14
				15	///////////////////////////////////////////////////////////////////////////////
				16	// 2-way linked lists...
				17	//
				18	// Broght inline here to avoid namespace polution
				19	///////////////////////////////////////////////////////////////////////////////
				20
				21	typedef struct List_Link List_Link;
				22	struct List_Link {
				23	List_Link *next;
				24	List_Link *prev;
				25	};
				26
				27	typedef struct List_Head List_Head;
				28	struct List_Head {
				29	union {
				30	struct {
				31	List_Link link;
				32	List_Link *filler;
				33	} fwd;
				34	struct {
				35	List_Link *filler;
				36	List_Link link;
				37	} back;
				38	};
				39	};
				40
				41	static inline bool List_IsEmpty(const List_Head *list) {
				42	return list->fwd.link.next == &list->back.link;
				43	}
				44
				45	static inline List_Link List_GetHead(const List_Head list) {
				46	return List_IsEmpty(list) ? NULL : list->fwd.link.next;
				47	}
				48	static inline List_Link List_GetTail(const List_Head list) {
				49	return List_IsEmpty(list) ? NULL : list->back.link.prev;
				50	}
				51	#define OFFSETOF(Container, Field) ((char )&((Container )4)->Field - (char )(Container )4)
				52	#define List_Link_Container(Container, Link, link) ((Container )((char )(link) - OFFSETOF(Container, Link)))
				53
				54	static inline void List_Init(List_Head *list)
				55	{
				56	list->fwd.link.next = &list->back.link;
				57	list->fwd.link.prev = NULL;
				58	list->back.link.prev = &list->fwd.link;
				59	}
				60
				61	static inline void List_AddHead(List_Head list, List_Link link)
				62	{
				63	List_Link *first = list->fwd.link.next;
				64	link->next = first;
65	link->prev = &list->fwd.link;
66	first->prev = link;
67	list->fwd.link.next = link;
68	}
69
70	static inline void List_AddTail(List_Head list, List_Link link)
71	{
72	List_Link *last = list->back.link.prev;
73	link->prev = last;
74	link->next = &list->back.link;
75	last->next = link;
76	list->back.link.prev = link;
77	}
78
79	static inline void List_Remove(List_Link *link)
80	{
81	link->prev->next = link->next;
82	link->next->prev = link->prev;
83	}
84
85	///////////////////////////////////////////////////////////////////////////////
86	// ...2-way linked lists
87	///////////////////////////////////////////////////////////////////////////////
88
89
90	enum {
91	Coroutines_Idle,
92	Coroutines_Starting,
93	Coroutines_Started,
94	Coroutines_Active,
95	Coroutines_Stopping
96	};
97
98	enum {
99	Chunk_Initial,
100	Chunk_Create,
101	Chunk_Enter
102	};
103
104	enum {
105	Coroutine_Constructing,
106	Coroutine_Free,
107	Coroutine_Idle,
108	Coroutine_Running,
109	Coroutine_Waiting,
110	Coroutine_Complete
111	};
112
113	enum {
114	Coroutines_Init,
115	Coroutines_AllocatedChunk,
116	Coroutines_CoroutineComplete,
117	};
118
119	struct Coroutine {
120	List_Link link;
121	jmp_buf buf;
122	void *this;
123	Coroutine_YieldCallback on_yield;
124	Coroutine_Start start;
125	void *entry_param;
126	void *value;
127	char state;
128	char action;
129	};
130
131	typedef struct Coroutines Coroutines;
132
133	struct Coroutines {
134	jmp_buf controller;
135	jmp_buf chunk_allocated;
136
137	// singletons
138	Coroutine *tip; // top of stack chunk
139	Coroutine *active; // currently running coroutine
140	Coroutine *primary; // Coroutine_Run coroutine
141
142	// lists
143	List_Head free;
144	List_Head inactive; // idle or complete
145	List_Head runable; // running or waiting to run
146	List_Head waiting; // yielded / waiting to run
147	sem_t *waiting_sem;
148
149	// state
150	char state;
151	};
152
153	Coroutines g_c;
154
155	static void stack_chunk_chunk(Coroutine *parent);
156	static void stack_chunk_base(Coroutine *parent);
157
158	static void Coroutine_PrimeStackChunks()
159	{
160	unsigned char chunk_of_stack[COROUTINE_STACK_SIZE];
161	chunk_of_stack[0] = 0xde;
162	chunk_of_stack[1] = 0xad;
163	chunk_of_stack[2] = 0xbe;
164	chunk_of_stack[3] = 0xef;
165	chunk_of_stack[COROUTINE_STACK_SIZE - 4] = 0xde;
166	chunk_of_stack[COROUTINE_STACK_SIZE - 3] = 0xad;
167	chunk_of_stack[COROUTINE_STACK_SIZE - 2] = 0xbe;
168	chunk_of_stack[COROUTINE_STACK_SIZE - 1] = 0xef;
169	stack_chunk_base(NULL);
170	}
171
172	static void stack_chunk_chunk(Coroutine *parent){
173	unsigned char chunk_of_stack[COROUTINE_STACK_SIZE];
174	chunk_of_stack[0] = 0xde;
175	chunk_of_stack[1] = 0xad;
176	chunk_of_stack[2] = 0xbe;
177	chunk_of_stack[3] = 0xef;
178	chunk_of_stack[COROUTINE_STACK_SIZE - 4] = 0xde;
179	chunk_of_stack[COROUTINE_STACK_SIZE - 3] = 0xad;
180	chunk_of_stack[COROUTINE_STACK_SIZE - 2] = 0xbe;
181	chunk_of_stack[COROUTINE_STACK_SIZE - 1] = 0xef;
182	stack_chunk_base(parent);
183	}
184
185	static void Coroutine_RunNext()
186	{
187	sem_wait(g_c.waiting_sem);
188	assert(!List_IsEmpty(&g_c.runable));
189	Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c.runable));
190	assert(next->state == Coroutine_Running);
191	longjmp(next->buf, Chunk_Enter);
192	assert(false);
193	}
194
195	static void stack_chunk_base(Coroutine *parent){
196	Coroutine here;
197	here.state = Coroutine_Constructing;
198	switch (setjmp(here.buf)) {
199	case Chunk_Initial:
200	// got here for the first time
201	// parent now has a chunk_of_stack - add it to the free list
202	if (parent) {
203	assert(parent->state == Coroutine_Constructing);
204	parent->state = Coroutine_Free;
205	List_AddHead(&g_c.free, &parent->link);
206	}
207	// note that here is the tip of the chunk-claim stack
208	g_c.tip = &here;
209
210	// return to the coroutine allocator
211	longjmp(g_c.chunk_allocated, 1);
212	case Chunk_Create:
213	// request to create a new chunk on the stack
214	assert(here.state == Coroutine_Constructing);
215	stack_chunk_chunk(&here);
216	assert(false);
217	case Chunk_Enter:
218	// request to start a coroutine (ie use the chunk for a coroutine)
219	assert(here.state == Coroutine_Running);
220	g_c.active = &here;
221	here.value = here.start(here.entry_param);
222	g_c.active = NULL;
223	assert(here.state == Coroutine_Running);
224	List_Remove(&here.link);
225	here.state = Coroutine_Complete;
226	List_AddTail(&g_c.inactive, &here.link);
227	// coroutine has completed
228	if (g_c.primary == &here) {
229	// if primary coroutine - return to Coroutine_Run
230	longjmp(g_c.controller, Coroutines_CoroutineComplete);
231	}
232	Coroutine_RunNext();
233	assert(false);
234	}
235	}
236
237	void Coroutine_StartSystem()
238	{
239	assert(g_c.state == Coroutines_Idle);
240	g_c.state = Coroutines_Starting;
241
242	g_c.tip = NULL;
243	g_c.active = NULL;
244
245	List_Init(&g_c.free);
246	List_Init(&g_c.inactive);
247	List_Init(&g_c.runable);
248	List_Init(&g_c.waiting);
249	char tbuf[256];
250	snprintf(tbuf, sizeof(tbuf), "/coroutine_waiting_sem_%d", getpid());
251	g_c.waiting_sem = sem_open(tbuf, O_CREAT, 0644, 0);
252	sem_unlink(tbuf);
253	assert(g_c.waiting_sem != SEM_FAILED);
254
255	// prime the chunk system
256	if (!setjmp(g_c.chunk_allocated)){
257	Coroutine_PrimeStackChunks();
258	assert(false);
259	}
260	assert(g_c.state == Coroutines_Starting);
261	g_c.state = Coroutines_Started;
262	}
263
264	void Coroutine_StopSystem()
265	{
266	assert(g_c.state == Coroutines_Started);
267	g_c.state = Coroutines_Stopping;
268
269	assert(List_IsEmpty(&g_c.inactive));
270	sem_close(g_c.waiting_sem);
271	g_c.waiting_sem = NULL;
272
273	assert(g_c.state == Coroutines_Stopping);
274	g_c.state = Coroutines_Idle;
275	}
276
277	void Coroutine_Run(Coroutine cor, void *value){
278	assert(g_c.state == Coroutines_Started);
279	g_c.state = Coroutines_Active;
280	g_c.primary = cor;
281	Coroutine_Continue(g_c.primary, value, true);
282
283	if (!setjmp(g_c.controller)){
284	// start the first coroutine
285	Coroutine_RunNext();
286	}
287	assert(List_IsEmpty(&g_c.runable));
288	assert(List_IsEmpty(&g_c.waiting));
289	assert(g_c.state == Coroutines_Active);
290	g_c.state = Coroutines_Started;
291	return Coroutine_GetValue(cor);
292	}
293
294	Coroutine Coroutine_New(void this, Coroutine_YieldCallback on_yield, Coroutine_Start start){
295	assert(g_c.state == Coroutines_Started \|\| g_c.state == Coroutines_Active);
296
297	// if none free - add one
298	if (List_IsEmpty(&g_c.free)){
299	if (!setjmp(g_c.chunk_allocated)){
300	longjmp(g_c.tip->buf, Chunk_Create);
301	}
302	}
303
304	Coroutine *cor = List_Link_Container(Coroutine, link, List_GetHead(&g_c.free));
305	assert(cor->state == Coroutine_Free);
306	cor->state = Coroutine_Idle;
307	cor->this = this;
308	cor->start = start;
309	cor->on_yield = on_yield;
310	cor->value = NULL;
311	List_Remove(&cor->link);
312	List_AddHead(&g_c.inactive, &cor->link);
313
314	return cor;
315	}
316
317	void Coroutine_Delete(Coroutine *cor){
318	assert(cor->state == Coroutine_Idle \|\| cor->state == Coroutine_Complete);
319	cor->state = Coroutine_Free;
320	List_Remove(&cor->link);
321	List_AddTail(&g_c.free, &cor->link);
322	}
323
324	void Coroutine_Continue(Coroutine cor, void value, bool early){
325	assert(cor->state == Coroutine_Idle \|\| cor->state == Coroutine_Waiting);
326	cor->entry_param = value;
327	cor->state = Coroutine_Running;
328	List_Remove(&cor->link);
329	if ( early ) {
330	List_AddHead(&g_c.runable, &cor->link);
331	} else {
332	List_AddTail(&g_c.runable, &cor->link);
333	}
334	sem_post(g_c.waiting_sem);
335	}
336
337	void Coroutine_Yield(void value){
338	Coroutine *me = g_c.active;
339	assert(me && me->state == Coroutine_Running);
340	me->value = value;
341	me->state = Coroutine_Waiting;
342	List_Remove(&me->link);
343	List_AddTail(&g_c.waiting, &me->link);
344	if (!setjmp(me->buf)){
345	me->on_yield(me->this);
346	Coroutine_RunNext();
347	}
348	g_c.active = me;
349	// when we return here - we are running again
350	assert(me->state == Coroutine_Running);
351	return me->entry_param;
352	}
353
354	void Coroutine_GetValue(Coroutine cor){
355	return cor->value;
356	}
357
358	Coroutine *Coroutine_GetActive()
359	{
360	return g_c.active;
361	}
362
363	bool Coroutine_IsRunning(Coroutine *cor)
364	{
365	return cor->state == Coroutine_Running \|\| cor->state == Coroutine_Waiting;
366	}
367