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