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