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