652 lines16.1 KB
Newer
Older
-
+
commited
{line.log.rev}
on
9 months ago
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>
9 months ago
7
#include <pthread.h>
8
#include <stdlib.h>
9 months ago
9
#include "cor_thread_local.h"
9 months ago
4
10
11
9 months ago
12
static void *mustmalloc(size_t size){
13
void *p = malloc(size);
14
assert(p);
15
return p;
16
}
17
18
#define New(type, ...) (type##_ctor((type *)mustmalloc(sizeof(type), ## __VA_ARGS__)))
19
#define Delete(ptr, type) ((ptr) ? (type##_dtor(ptr), free(ptr), (ptr) = NULL) : (void)0)
9 months ago
20
static void Coroutine_RunNext();
8 months ago
21
static void _Coroutine_Continue(Coroutine *cor, void *value, bool early);
9 months ago
22
9 months ago
4
23
///////////////////////////////////////////////////////////////////////////////
24
// 2-way linked lists...
25
//
9 months ago
26
// Brought inline here to avoid namespace polution
9 months ago
4
27
///////////////////////////////////////////////////////////////////////////////
28
29
typedef struct List_Link List_Link;
30
struct List_Link {
31
List_Link *next;
32
List_Link *prev;
33
};
34
35
typedef struct List_Head List_Head;
36
struct List_Head {
37
union {
38
struct {
39
List_Link link;
40
List_Link *filler;
41
} fwd;
42
struct {
43
List_Link *filler;
44
List_Link link;
45
} back;
46
};
47
};
48
9 months ago
49
50
static inline bool List_IsEmpty(
51
const List_Head *list
52
){
9 months ago
4
53
return list->fwd.link.next == &list->back.link;
54
}
55
9 months ago
56
57
static inline List_Link *List_GetHead(
58
const List_Head *list
59
){
9 months ago
4
60
return List_IsEmpty(list) ? NULL : list->fwd.link.next;
61
}
9 months ago
62
63
64
// static inline List_Link *List_GetTail(
65
// const List_Head *list
66
// ){
9 months ago
67
// return List_IsEmpty(list) ? NULL : list->back.link.prev;
68
// }
9 months ago
69
70
9 months ago
4
71
#define OFFSETOF(Container, Field) ((char *)&((Container *)4)->Field - (char *)(Container *)4)
72
#define List_Link_Container(Container, Link, link) ((Container *)((char *)(link) - OFFSETOF(Container, Link)))
73
9 months ago
74
75
static inline void List_Init(
76
List_Head *list
77
){
9 months ago
4
78
list->fwd.link.next = &list->back.link;
79
list->fwd.link.prev = NULL;
80
list->back.link.prev = &list->fwd.link;
81
}
82
9 months ago
83
84
static inline void List_AddHead(
85
List_Head *list,
86
List_Link *link
87
){
9 months ago
4
88
List_Link *first = list->fwd.link.next;
89
link->next = first;
90
link->prev = &list->fwd.link;
91
first->prev = link;
92
list->fwd.link.next = link;
93
}
94
9 months ago
95
96
static inline void List_AddTail(
97
List_Head *list,
98
List_Link *link
99
){
9 months ago
4
100
List_Link *last = list->back.link.prev;
101
link->prev = last;
102
link->next = &list->back.link;
103
last->next = link;
104
list->back.link.prev = link;
105
}
106
9 months ago
107
108
static inline void List_Remove(
109
List_Link *link
110
){
9 months ago
4
111
link->prev->next = link->next;
112
link->next->prev = link->prev;
113
}
114
115
///////////////////////////////////////////////////////////////////////////////
116
// ...2-way linked lists
117
///////////////////////////////////////////////////////////////////////////////
118
9 months ago
119
typedef struct Coroutines Coroutines;
9 months ago
4
120
121
enum {
122
Coroutines_Idle,
123
Coroutines_Starting,
124
Coroutines_Started,
125
Coroutines_Active,
126
Coroutines_Stopping
127
};
128
129
enum {
130
Chunk_Initial,
131
Chunk_Create,
132
Chunk_Enter
133
};
134
9 months ago
135
typedef enum Coroutine_State {
9 months ago
4
136
Coroutine_Constructing,
137
Coroutine_Free,
138
Coroutine_Idle,
139
Coroutine_Running,
140
Coroutine_Waiting,
141
Coroutine_Complete
9 months ago
142
} Coroutine_State;
9 months ago
4
143
144
enum {
145
Coroutines_Init,
146
Coroutines_AllocatedChunk,
147
Coroutines_CoroutineComplete,
148
};
149
150
struct Coroutine {
9 months ago
151
Coroutines *coroutines; // so can work with it off-thread
152
List_Link link; // for whichever list it's on
153
jmp_buf buf; // how to get back to it
154
unsigned char *guard; // where the stack overrun guard is
155
Coroutine_Start start; // entry point
156
void *entry_param; // to pass to start
157
void *value; // yielded/returned
158
Coroutine_State state;
9 months ago
4
159
};
160
161
struct Coroutines {
9 months ago
162
pthread_mutex_t mutex;
9 months ago
163
jmp_buf controller; // to return from Coroutine_Run
164
jmp_buf chunk_allocated;// for chunk allocation
165
unsigned char *guard; // the stack guard for the startup sequence
9 months ago
4
166
167
// singletons
168
Coroutine *tip; // top of stack chunk
169
Coroutine *active; // currently running coroutine
170
Coroutine *primary; // Coroutine_Run coroutine
171
172
// lists
173
List_Head free;
174
List_Head inactive; // idle or complete
175
List_Head runable; // running or waiting to run
176
List_Head waiting; // yielded / waiting to run
8 months ago
177
pthread_mutex_t waiting_mutex;
9 months ago
4
178
9 months ago
179
// Summary of the system
180
Coroutine_Report report;
181
9 months ago
4
182
// state
183
char state;
184
};
185
9 months ago
186
_Cor_thread_local Coroutines *g_c;
9 months ago
4
187
188
static void stack_chunk_chunk(Coroutine *parent);
9 months ago
189
static void stack_chunk_base(Coroutine *parent, unsigned char *guard);
9 months ago
4
190
9 months ago
191
9 months ago
192
// Check whether the guard is intact
193
static inline bool Check_Guard(
194
unsigned char *guard
195
){
196
return guard[0] == 0xde &&
197
guard[1] == 0xad &&
198
guard[2] == 0xbe &&
199
guard[3] == 0xef;
200
}
201
202
9 months ago
4
203
static void Coroutine_PrimeStackChunks()
204
{
9 months ago
205
unsigned char chunk_of_stack[COROUTINE_STARTUP_STACK_SIZE];
206
for (int i = 0; i < COROUTINE_STARTUP_STACK_SIZE-3; i += 4){
207
chunk_of_stack[i+0] = 0xde;
208
chunk_of_stack[i+1] = 0xad;
209
chunk_of_stack[i+2] = 0xbe;
210
chunk_of_stack[i+3] = 0xef;
211
}
212
assert(Check_Guard(chunk_of_stack));
213
214
// Stacks grow down in memory (almost always), so if the caller of this function changes
215
// the guard before entering the coroutine system, it has overrun the startup stack
216
g_c->guard = chunk_of_stack;
217
218
stack_chunk_base(NULL, NULL);
9 months ago
4
219
}
220
9 months ago
221
222
static void stack_chunk_chunk(
223
Coroutine *parent
224
){
9 months ago
4
225
unsigned char chunk_of_stack[COROUTINE_STACK_SIZE];
9 months ago
226
for (int i = 0; i < COROUTINE_STACK_SIZE-3; i += 4){
227
chunk_of_stack[i+0] = 0xde;
228
chunk_of_stack[i+1] = 0xad;
229
chunk_of_stack[i+2] = 0xbe;
230
chunk_of_stack[i+3] = 0xef;
9 months ago
231
}
9 months ago
232
stack_chunk_base(parent, chunk_of_stack);
9 months ago
4
233
}
234
9 months ago
235
236
static void stack_chunk_base(
9 months ago
237
Coroutine *parent,
238
unsigned char *guard
9 months ago
239
){
9 months ago
4
240
Coroutine here;
241
here.state = Coroutine_Constructing;
242
switch (setjmp(here.buf)) {
243
case Chunk_Initial:
244
// got here for the first time
245
// parent now has a chunk_of_stack - add it to the free list
246
if (parent) {
247
assert(parent->state == Coroutine_Constructing);
9 months ago
248
assert(Check_Guard(guard));
249
parent->guard = guard;
9 months ago
4
250
parent->state = Coroutine_Free;
9 months ago
251
List_AddHead(&g_c->free, &parent->link);
9 months ago
252
g_c->report.coroutines_pool_size += 1;
9 months ago
4
253
}
254
// note that here is the tip of the chunk-claim stack
9 months ago
255
here.coroutines = g_c;
256
g_c->tip = &here;
9 months ago
4
257
258
// return to the coroutine allocator
9 months ago
259
longjmp(g_c->chunk_allocated, 1);
9 months ago
4
260
case Chunk_Create:
261
// request to create a new chunk on the stack
262
assert(here.state == Coroutine_Constructing);
263
stack_chunk_chunk(&here);
264
assert(false);
265
case Chunk_Enter:
266
// request to start a coroutine (ie use the chunk for a coroutine)
9 months ago
267
// arrive here with mutex locked
9 months ago
4
268
assert(here.state == Coroutine_Running);
9 months ago
269
g_c->active = &here;
270
int r = pthread_mutex_unlock(&g_c->mutex);
9 months ago
271
assert(r == 0);
9 months ago
4
272
here.value = here.start(here.entry_param);
9 months ago
273
274
// check the guard
275
if (!Check_Guard(here.guard)){
276
printf("Coroutine has overrun its stack - checked after returning from coroutine function\n");
277
exit(EXIT_FAILURE);
278
}
279
280
r = pthread_mutex_lock(&g_c->mutex);
9 months ago
281
assert(r == 0);
9 months ago
282
g_c->active = NULL;
9 months ago
4
283
assert(here.state == Coroutine_Running);
284
List_Remove(&here.link);
285
here.state = Coroutine_Complete;
9 months ago
286
List_AddTail(&g_c->inactive, &here.link);
9 months ago
4
287
// coroutine has completed
9 months ago
288
if (g_c->primary == &here) {
9 months ago
4
289
// if primary coroutine - return to Coroutine_Run
9 months ago
290
longjmp(g_c->controller, Coroutines_CoroutineComplete);
9 months ago
4
291
}
9 months ago
292
r = pthread_mutex_unlock(&g_c->mutex);
9 months ago
293
assert(r == 0);
9 months ago
4
294
Coroutine_RunNext();
295
assert(false);
296
}
297
}
298
9 months ago
299
9 months ago
300
static void Coroutine_RunNext()
301
{
302
// arrive here with mutex unlocked
303
int r;
8 months ago
304
r = pthread_mutex_lock(&g_c->waiting_mutex);
305
assert(r == 0);
9 months ago
306
r = pthread_mutex_lock(&g_c->mutex);
307
assert(r == 0);
308
Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c->runable));
309
assert(next->state == Coroutine_Running);
310
longjmp(next->buf, Chunk_Enter);
311
assert(false);
312
}
313
314
9 months ago
4
315
void Coroutine_StartSystem()
316
{
9 months ago
317
assert(!g_c);
318
g_c = mustmalloc(sizeof(Coroutines));
9 months ago
319
9 months ago
320
g_c->state = Coroutines_Starting;
321
8 months ago
322
int r;
323
r = pthread_mutex_init(&g_c->mutex, NULL);
9 months ago
324
assert(r == 0);
325
9 months ago
326
g_c->tip = NULL;
327
g_c->active = NULL;
9 months ago
4
328
9 months ago
329
List_Init(&g_c->free);
330
List_Init(&g_c->inactive);
331
List_Init(&g_c->runable);
332
List_Init(&g_c->waiting);
8 months ago
333
r = pthread_mutex_init(&g_c->waiting_mutex, NULL);
9 months ago
334
assert(r == 0);
8 months ago
335
r = pthread_mutex_lock(&g_c->waiting_mutex);
336
assert(r == 0);
9 months ago
4
337
9 months ago
338
g_c->report.coroutines_created = 0;
339
g_c->report.coroutines_pool_size = 0;
340
g_c->report.lowest_headroom = COROUTINE_STACK_SIZE;
341
9 months ago
4
342
// prime the chunk system
9 months ago
343
if (!setjmp(g_c->chunk_allocated)){
9 months ago
4
344
Coroutine_PrimeStackChunks();
345
assert(false);
346
}
9 months ago
347
348
assert(g_c->state == Coroutines_Starting);
349
g_c->state = Coroutines_Started;
9 months ago
4
350
}
351
9 months ago
352
9 months ago
353
Coroutine_Report Coroutine_StopSystem()
9 months ago
4
354
{
9 months ago
355
int r = pthread_mutex_lock(&g_c->mutex);
9 months ago
356
assert(r == 0);
9 months ago
357
assert(g_c->state == Coroutines_Started);
358
g_c->state = Coroutines_Stopping;
9 months ago
4
359
9 months ago
360
int stackminheadroom = COROUTINE_STACK_SIZE;
361
for (List_Link *link = g_c->free.fwd.link.next; link->next; link = link->next){
362
Coroutine *cor = List_Link_Container(Coroutine, link, link);
363
for (int i = 4; i < COROUTINE_STACK_SIZE-3; i += 4){
364
if (!Check_Guard(&cor->guard[i])){
365
stackminheadroom = i < stackminheadroom ? i : stackminheadroom;
366
break;
367
}
368
}
369
}
370
g_c->report.lowest_headroom = stackminheadroom;
371
9 months ago
372
assert(List_IsEmpty(&g_c->inactive));
8 months ago
373
r = pthread_mutex_unlock(&g_c->waiting_mutex);
9 months ago
374
assert(r == 0);
8 months ago
375
r = pthread_mutex_destroy(&g_c->waiting_mutex);
376
assert(r == 0);
9 months ago
4
377
9 months ago
378
assert(g_c->state == Coroutines_Stopping);
379
pthread_mutex_unlock(&g_c->mutex);
9 months ago
380
assert(r == 0);
9 months ago
381
g_c->state = Coroutines_Idle;
382
r = pthread_mutex_destroy(&g_c->mutex);
9 months ago
383
assert(r == 0);
9 months ago
384
385
Coroutine_Report res = g_c->report;
386
9 months ago
387
free(g_c);
388
g_c = NULL;
9 months ago
389
390
return res;
9 months ago
4
391
}
392
9 months ago
393
9 months ago
394
void Coroutine_Run_Coroutine(
395
Coroutine *cor,
9 months ago
396
void *value
397
){
398
Coroutines *cors = cor->coroutines;
399
assert(g_c == cors);
400
int r = pthread_mutex_lock(&cors->mutex);
9 months ago
401
assert(r == 0);
9 months ago
402
assert(cors->state == Coroutines_Started);
403
cors->state = Coroutines_Active;
404
cors->primary = cor;
9 months ago
405
8 months ago
406
_Coroutine_Continue(cor, value, true);
9 months ago
4
407
9 months ago
408
if (!setjmp(cors->controller)){
409
pthread_mutex_unlock(&cors->mutex);
9 months ago
410
assert(r == 0);
9 months ago
411
412
// check the guard
413
if (!Check_Guard(g_c->guard)){
414
printf("Coroutine startup stack as has overrun - checked on entering the main coroutine\n");
415
exit(EXIT_FAILURE);
416
}
417
9 months ago
4
418
// start the first coroutine
419
Coroutine_RunNext();
420
}
9 months ago
421
// arrive here with mutex locked
9 months ago
422
assert(List_IsEmpty(&cors->runable));
423
assert(List_IsEmpty(&cors->waiting));
424
assert(cors->state == Coroutines_Active);
425
cors->state = Coroutines_Started;
426
pthread_mutex_unlock(&cors->mutex);
9 months ago
427
assert(r == 0);
9 months ago
428
}
429
430
431
void *Coroutine_Run(
432
Coroutine_Start start,
433
void *value
434
){
435
Coroutine *cor = Coroutine_New(start);
436
Coroutine_Run_Coroutine(cor, value);
9 months ago
437
void *res = Coroutine_GetValue(cor);
438
Coroutine_Delete(cor);
439
return res;
9 months ago
4
440
}
441
442
9 months ago
443
Coroutine *Coroutine_New(
444
Coroutine_Start start
445
){
9 months ago
446
assert((g_c->state == Coroutines_Started && List_IsEmpty(&g_c->inactive)) || g_c->state == Coroutines_Active);
9 months ago
447
9 months ago
4
448
// if none free - add one
9 months ago
449
if (List_IsEmpty(&g_c->free)){
450
if (!setjmp(g_c->chunk_allocated)){
451
longjmp(g_c->tip->buf, Chunk_Create);
9 months ago
4
452
}
453
}
454
9 months ago
455
Coroutine *cor = List_Link_Container(Coroutine, link, List_GetHead(&g_c->free));
9 months ago
4
456
assert(cor->state == Coroutine_Free);
457
cor->state = Coroutine_Idle;
458
cor->start = start;
459
cor->value = NULL;
460
List_Remove(&cor->link);
9 months ago
461
List_AddHead(&g_c->inactive, &cor->link);
9 months ago
4
462
9 months ago
463
g_c->report.coroutines_created += 1;
464
9 months ago
4
465
return cor;
466
}
467
9 months ago
468
469
void Coroutine_Delete(
470
Coroutine *cor
471
){
472
Coroutines *cors = cor->coroutines;
473
int r = pthread_mutex_lock(&cors->mutex);
474
assert(r == 0);
9 months ago
4
475
assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Complete);
476
cor->state = Coroutine_Free;
477
List_Remove(&cor->link);
9 months ago
478
List_AddTail(&cors->free, &cor->link);
479
r = pthread_mutex_unlock(&cors->mutex);
480
assert(r == 0);
9 months ago
4
481
}
482
9 months ago
483
8 months ago
484
// Coroutine_Continue, assuming the mutex is claimed
485
static void _Coroutine_Continue(
9 months ago
486
Coroutine *cor,
487
void *value,
488
bool early
489
){
490
Coroutines *cors = cor->coroutines;
9 months ago
4
491
assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Waiting);
492
cor->entry_param = value;
493
cor->state = Coroutine_Running;
494
List_Remove(&cor->link);
495
if ( early ) {
9 months ago
496
List_AddHead(&cors->runable, &cor->link);
9 months ago
4
497
} else {
9 months ago
498
List_AddTail(&cors->runable, &cor->link);
9 months ago
4
499
}
8 months ago
500
int r;
8 months ago
501
r = pthread_mutex_unlock(&cors->waiting_mutex);
8 months ago
502
assert(r == 0);
503
}
504
505
506
void Coroutine_Continue(
507
Coroutine *cor,
508
void *value,
509
bool early
510
){
511
Coroutines *cors = cor->coroutines;
512
int r = pthread_mutex_lock(&cors->mutex);
513
assert(r == 0);
514
_Coroutine_Continue(cor, value, early);
9 months ago
515
r = pthread_mutex_unlock(&cors->mutex);
9 months ago
516
assert(r == 0);
9 months ago
4
517
}
518
9 months ago
519
520
void *Coroutine_Yield(
521
void *value,
522
Coroutine_YieldCallback on_yield,
9 months ago
523
void *yield_me
9 months ago
524
){
9 months ago
525
Coroutine *me = g_c->active;
526
if (!Check_Guard(me->guard)){
527
printf("Coroutine has overrun its stack - checked when yielding coroutine\n");
528
exit(EXIT_FAILURE);
529
}
530
9 months ago
531
int r = pthread_mutex_lock(&g_c->mutex);
9 months ago
532
assert(r == 0);
9 months ago
533
Coroutines *cors = me->coroutines;
534
assert(me && me->state == Coroutine_Running && cors == g_c);
9 months ago
4
535
me->value = value;
536
me->state = Coroutine_Waiting;
9 months ago
537
9 months ago
4
538
List_Remove(&me->link);
8 months ago
539
if (!List_IsEmpty(&cors->runable)){
540
r = pthread_mutex_unlock(&cors->waiting_mutex);
541
assert(r == 0);
542
}
9 months ago
543
List_AddTail(&cors->waiting, &me->link);
9 months ago
544
9 months ago
545
switch (setjmp(me->buf)){
546
case Chunk_Initial:
9 months ago
547
r = pthread_mutex_unlock(&cors->mutex);
9 months ago
548
assert(r == 0);
9 months ago
549
on_yield(yield_me);
9 months ago
4
550
Coroutine_RunNext();
9 months ago
551
case Chunk_Create:
552
assert(false);
553
case Chunk_Enter:
554
// arrive here with mutex locked
9 months ago
555
cors->active = me;
9 months ago
556
// when we return here - we are running again
557
assert(me->state == Coroutine_Running);
558
void *res = me->entry_param;
9 months ago
559
r = pthread_mutex_unlock(&cors->mutex);
9 months ago
560
assert(r == 0);
561
return res;
9 months ago
4
562
}
9 months ago
563
return NULL;
9 months ago
4
564
}
565
9 months ago
566
567
void *Coroutine_GetValue(
568
Coroutine *cor
569
){
9 months ago
4
570
return cor->value;
571
}
572
9 months ago
573
9 months ago
4
574
Coroutine *Coroutine_GetActive()
575
{
9 months ago
576
return g_c->active;
9 months ago
4
577
}
578
9 months ago
579
9 months ago
580
int Coroutine_GetStackHeadroom(){
581
unsigned char tbuf[4];
582
return tbuf - g_c->active->guard - 4;
583
}
584
585
586
bool Coroutine_HasCoroutinesInFreePool(){
587
return !List_IsEmpty(&g_c->free);
588
}
589
590
591
void *Coroutine_GetCStackTop(){
592
return g_c->tip;
593
}
594
595
596
struct Coroutine_ChainParam {
597
Coroutine_Start start;
598
void *value;
599
Coroutine *ret;
600
};
601
602
603
static void *Coroutine_ChainFn(
604
void *param
605
){
606
struct Coroutine_ChainParam *params = (struct Coroutine_ChainParam *)param;
607
Coroutine_Continue(params->ret, params->start(params->value), true);
608
return NULL;
609
}
610
611
612
static void Coroutine_ChainYield(
613
void *unused
614
){
615
(void)unused;
616
}
617
618
619
void *Coroutine_Chain(
620
Coroutine_Start start,
621
void *value
622
){
623
if (!Check_Guard(Coroutine_GetActive()->guard)){
624
printf("Coroutine has overrun its stack - checked when chaining\n");
625
exit(EXIT_FAILURE);
626
}
627
Coroutine *cor = Coroutine_New(Coroutine_ChainFn);
628
struct Coroutine_ChainParam params = {
629
start,
630
value,
631
Coroutine_GetActive()
632
};
633
Coroutine_Continue(cor, &params, true);
634
void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
635
Coroutine_Delete(cor);
636
return res;
637
}
638
639
9 months ago
640
bool Coroutine_IsRunning(
641
Coroutine *cor
642
)
9 months ago
4
643
{
9 months ago
644
int state = cor->state;
645
return state == Coroutine_Running || state == Coroutine_Waiting;
9 months ago
4
646
}
9 months ago
647
648
649
bool Coroutine_IsStarted(){
650
return g_c != NULL;
651
}
652