0 branches 0 tags
78
Allow failures to be returned
jonroach 11 Feb 2026 10:05
1 contributor
1119 lines29.8 KB
Newer
Older
Text Raw Blame
  • Delete
-
+
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 months ago
6
 #include <stdio.h>
8 months ago
7
 #include "cor_platform.h"
9 months ago
4
8
7 months ago
9
 // see CPython again, this time from ctypes.h
10
 #if (defined (__SVR4) && defined (__sun)) || defined(COROUTINE_HAVE_ALLOCA_H)
11
 # include <alloca.h>
12
 #elif defined(MS_WIN32)
13
 # include <malloc.h>
14
 #endif
9 months ago
4
15
7 months ago
16
 /* If the system does not define alloca(), we have to hope for a compiler builtin. */
17
 #ifndef alloca
18
 # if defined __GNUC__ || (__clang_major__ >= 4)
19
 # define alloca __builtin_alloca
20
 # else
21
 # error "Could not define alloca() on your platform."
22
 # endif
23
 #endif
24
4 months ago
25
 typedef struct Coroutines Coroutines;
26
8 months ago
27
 static void Coroutine_RunNext(void);
4 months ago
28
 static bool _Coroutine_Continue(Coroutines *cors, Coroutine *cor, void *value, bool early);
7 months ago
29
 static unsigned char *StackTopNow(void);
9 months ago
30
9 months ago
4
31
 ///////////////////////////////////////////////////////////////////////////////
32
 // 2-way linked lists...
33
 //
9 months ago
34
 // Brought inline here to avoid namespace polution
9 months ago
4
35
 ///////////////////////////////////////////////////////////////////////////////
36
37
 typedef struct List_Link List_Link;
38
 struct List_Link {
39
 List_Link *next;
40
 List_Link *prev;
41
 };
42
43
 typedef struct List_Head List_Head;
44
 struct List_Head {
45
 union {
46
 struct {
47
 List_Link link;
48
 List_Link *filler;
49
 } fwd;
50
 struct {
51
 List_Link *filler;
52
 List_Link link;
53
 } back;
54
 };
55
 };
56
9 months ago
57
58
 static inline bool List_IsEmpty(
59
 const List_Head *list
60
 ){
9 months ago
4
61
 return list->fwd.link.next == &list->back.link;
62
 }
63
9 months ago
64
65
 static inline List_Link *List_GetHead(
66
 const List_Head *list
67
 ){
9 months ago
4
68
 return List_IsEmpty(list) ? NULL : list->fwd.link.next;
69
 }
9 months ago
70
71
6 months ago
72
 static inline List_Link *List_Begin(
73
 const List_Head *list
74
 ){
75
 return list->fwd.link.next;
76
 }
77
78
79
 static inline bool Link_NextIsLink(
80
 const List_Link *link
81
 ){
82
 return link->next != NULL;
83
 }
84
85
86
 static inline List_Link *Link_Next(
87
 List_Link *link
88
 ){
89
 return link->next;
90
 }
91
92
93
 static inline bool Link_PrevIsLink(
94
 const List_Link *link
95
 ){
96
 return link->prev != NULL;
97
 }
98
99
100
 static inline List_Link *Link_Prev(
101
 List_Link *link
102
 ){
103
 return link->prev;
104
 }
105
6 months ago
106
 static inline List_Link *List_GetTail(
107
 const List_Head *list
108
 ){
109
 return List_IsEmpty(list) ? NULL : list->back.link.prev;
110
 }
9 months ago
111
112
9 months ago
4
113
 #define OFFSETOF(Container, Field) ((char *)&((Container *)4)->Field - (char *)(Container *)4)
114
 #define List_Link_Container(Container, Link, link) ((Container *)((char *)(link) - OFFSETOF(Container, Link)))
115
9 months ago
116
117
 static inline void List_Init(
118
 List_Head *list
119
 ){
9 months ago
4
120
 list->fwd.link.next = &list->back.link;
121
 list->fwd.link.prev = NULL;
122
 list->back.link.prev = &list->fwd.link;
123
 }
124
9 months ago
125
6 months ago
126
 static inline void Link_AddAfter(
127
 List_Link *link,
128
 List_Link *after
129
 ){
130
 link->next = after->next;
131
 link->prev = after;
132
 after->next->prev = link;
133
 after->next = link;
134
 }
135
136
9 months ago
137
 static inline void List_AddHead(
138
 List_Head *list,
139
 List_Link *link
140
 ){
6 months ago
141
 Link_AddAfter(link, &list->fwd.link);
9 months ago
4
142
 }
143
9 months ago
144
6 months ago
145
 static inline void Link_AddBefore(
146
 List_Link *link,
147
 List_Link *before
148
 ){
149
 link->prev = before->prev;
150
 link->next = before;
151
 before->prev->next = link;
152
 before->prev = link;
153
 }
154
155
9 months ago
156
 static inline void List_AddTail(
157
 List_Head *list,
158
 List_Link *link
159
 ){
6 months ago
160
 Link_AddBefore(link, &list->back.link);
9 months ago
4
161
 }
162
9 months ago
163
6 months ago
164
 static inline void Link_Remove(
9 months ago
165
 List_Link *link
166
 ){
9 months ago
4
167
 link->prev->next = link->next;
168
 link->next->prev = link->prev;
169
 }
170
171
 ///////////////////////////////////////////////////////////////////////////////
172
 // ...2-way linked lists
173
 ///////////////////////////////////////////////////////////////////////////////
174
175
 enum {
176
 Coroutines_Starting,
177
 Coroutines_Started,
178
 Coroutines_Active,
179
 Coroutines_Stopping
180
 };
181
182
 enum {
183
 Chunk_Initial,
184
 Chunk_Create,
6 months ago
185
 Chunk_Split,
9 months ago
4
186
 Chunk_Enter
187
 };
188
9 months ago
189
 typedef enum Coroutine_State {
9 months ago
4
190
 Coroutine_Free,
191
 Coroutine_Idle,
192
 Coroutine_Running,
193
 Coroutine_Waiting,
194
 Coroutine_Complete
9 months ago
195
 } Coroutine_State;
9 months ago
4
196
197
 enum {
198
 Coroutines_Init,
199
 Coroutines_AllocatedChunk,
200
 Coroutines_CoroutineComplete,
201
 };
202
203
 struct Coroutine {
7 months ago
204
 Coroutines *coroutines; // so can work with it off-thread
205
 List_Link link; // for whichever list it's on
6 months ago
206
 List_Link all_link; // list of all Coroutines
7 months ago
207
 jmp_buf buf; // how to get back to it
6 months ago
208
 unsigned char *prev_limit; // the previous Coroutine's stack limit
209
 unsigned char *base; // where the base (high address) of this Coroutine's stack is
210
 unsigned char *limit; // where the limit (low address) of this Coroutine's stack is
7 months ago
211
 unsigned char *guard; // where the stack overrun guard is
6 months ago
212
 size_t size;
7 months ago
213
 Coroutine_Start start; // entry point
214
 void *entry_param; // to pass to start
215
 void *value; // yielded/returned
216
 unsigned char *stack_top; // recorded at yield
9 months ago
217
 Coroutine_State state;
9 months ago
4
218
 };
219
220
 struct Coroutines {
8 months ago
221
 _Cor_Mutex mutex;
9 months ago
222
 jmp_buf controller; // to return from Coroutine_Run
223
 jmp_buf chunk_allocated;// for chunk allocation
6 months ago
224
 size_t gap_before; // bytes between previous's stack_top and next's Coroutine
225
 size_t gap_after; // bytes between Coroutine and stack_base
9 months ago
4
226
227
 // singletons
228
 Coroutine *tip; // top of stack chunk
229
 Coroutine *active; // currently running coroutine
230
 Coroutine *primary; // Coroutine_Run coroutine
7 months ago
231
 unsigned char *stack_limit; // when not NULL, where the stack finishes
9 months ago
4
232
233
 // lists
6 months ago
234
 List_Head all; // all Coroutines (in address order)
235
 List_Head free; // free Coroutines
9 months ago
4
236
 List_Head inactive; // idle or complete
237
 List_Head runable; // running or waiting to run
238
 List_Head waiting; // yielded / waiting to run
8 months ago
239
 _Cor_Mutex waiting_mutex;
9 months ago
4
240
9 months ago
241
 // Summary of the system
242
 Coroutine_Report report;
243
9 months ago
4
244
 // state
245
 char state;
246
 };
247
6 months ago
248
 _Cor_thread_local Coroutines *g_c;
5 months ago
249
 _Cor_thread_local unsigned char *g_stack_limit;
9 months ago
4
250
6 months ago
251
 static void ReserveStackSpace(Coroutines *cors, Coroutine *parent, size_t chunk_size, unsigned char *childs_limit);
6 months ago
252
 static void stack_chunk_base(Coroutines *cors, Coroutine *parent, unsigned char *prev_limit, unsigned char *limit);
9 months ago
4
253
9 months ago
254
7 months ago
255
 #define GUARD_PATTERN_SIZE (4)
9 months ago
256
 // Check whether the guard is intact
257
 static inline bool Check_Guard(
258
 unsigned char *guard
259
 ){
7 months ago
260
 return !guard ||
261
 (guard[0] == 0xde &&
262
 guard[1] == 0xad &&
263
 guard[2] == 0xbe &&
264
 guard[3] == 0xef);
9 months ago
265
 }
266
267
7 months ago
268
 static inline void Apply_Guard(unsigned char *guard){
269
 guard[0] = 0xde;
270
 guard[1] = 0xad;
271
 guard[2] = 0xbe;
272
 guard[3] = 0xef;
273
 }
274
275
6 months ago
276
 static bool Coroutine_StackHasOverrun(void){
7 months ago
277
 unsigned char *stack_top = StackTopNow();
6 months ago
278
 unsigned char *stack_limit = g_c ? g_c->stack_limit : NULL;
7 months ago
279
 if (stack_limit && stack_top < stack_limit){
280
 // current stack top is beyond limit - we are overrunning NOW
6 months ago
281
 return true;
7 months ago
282
 }
6 months ago
283
 Coroutine *me = g_c ? g_c->active : NULL;
7 months ago
284
 if (!me){
6 months ago
285
 return false;
7 months ago
286
 }
287
 if (me->guard){
6 months ago
288
 return !Check_Guard(me->guard);
7 months ago
289
 }
6 months ago
290
 return stack_top < me->limit;
7 months ago
291
 }
292
293
6 months ago
294
 static void ReserveStackSpace(
295
 Coroutines *cors,
7 months ago
296
 Coroutine *parent,
6 months ago
297
 size_t chunk_size,
298
 unsigned char *childs_limit
9 months ago
299
 ){
7 months ago
300
 unsigned char *chunk_of_stack = alloca(chunk_size);
301
 #if COROUTINE_RECORD_LOWEST_HEADROOM
302
 for (size_t i = 0; i <= chunk_size-GUARD_PATTERN_SIZE; i += GUARD_PATTERN_SIZE){
303
 Apply_Guard(&chunk_of_stack[i]);
304
 }
305
 #else
7 months ago
306
 Apply_Guard(chunk_of_stack);
7 months ago
307
 #endif
6 months ago
308
 if (parent){
309
 parent->guard = chunk_of_stack;
310
 parent->limit = chunk_of_stack;
311
 parent->base = chunk_of_stack + chunk_size;
312
 }
6 months ago
313
 stack_chunk_base(cors, parent, chunk_of_stack, childs_limit);
9 months ago
4
314
 }
315
9 months ago
316
317
 static void stack_chunk_base(
6 months ago
318
 Coroutines *cors,
6 months ago
319
 Coroutine *parent,
6 months ago
320
 unsigned char *prev_limit,
321
 unsigned char *limit
9 months ago
322
 ){
9 months ago
4
323
 Coroutine here;
6 months ago
324
 here.coroutines = cors;
7 months ago
325
 here.state = Coroutine_Free;
6 months ago
326
 here.prev_limit = prev_limit;
327
 here.size = 0;
328
 here.base = NULL;
329
 here.guard = limit;
330
 here.limit = limit;
331
 if (limit){
332
 here.base = (unsigned char *)&here - cors->gap_after;
333
 here.size = here.base - here.limit;
334
 Apply_Guard(limit);
335
 }
336
6 months ago
337
 // insert into all list
338
 if (parent){
339
 Link_AddAfter(&here.all_link, &parent->all_link);
340
 } else {
341
 List_AddHead(&cors->all, &here.all_link);
6 months ago
342
 }
6 months ago
343
 // add to free list
344
 List_AddTail(&cors->free, &here.link);
6 months ago
345
346
 cors->report.coroutines_pool_size += 1;
347
348
 if (!cors->tip || &here < cors->tip){
349
 cors->tip = &here;
350
 }
351
7 months ago
352
 for(;;){
353
 switch (setjmp(here.buf)) {
354
 case Chunk_Initial:
7 months ago
355
 if (here.state == Coroutine_Free){
7 months ago
356
 // return to the coroutine allocator
6 months ago
357
 longjmp(cors->chunk_allocated, 1);
7 months ago
358
 } else {
359
 assert(here.state == Coroutine_Complete);
360
 // we finish here to ensure the setjmp is redone
6 months ago
361
 if (cors->primary == &here) {
7 months ago
362
 // if primary coroutine - return to Coroutine_Run
6 months ago
363
 longjmp(cors->controller, Coroutines_CoroutineComplete);
7 months ago
364
 }
6 months ago
365
 _Cor_Mutex_Unlock(&cors->mutex);
7 months ago
366
 Coroutine_RunNext();
367
 assert(false);
368
 }
369
 case Chunk_Create:
7 months ago
370
 // Request to create a new chunk on the stack
371
 // We're here if the coroutine is:
372
 // Allocated, but not 'run' (Coroutine_Idle)
373
 // Run, but not not entered yet (Coroutine_Running)
374
 // Completed (Coroutine_Complete)
6 months ago
375
 // Free, and the coroutines system is starting - we're characterising the system
376
 assert(here.state == Coroutine_Idle ||
377
 here.state == Coroutine_Running ||
378
 here.state == Coroutine_Complete ||
379
 (here.state == Coroutine_Free && cors->state == Coroutines_Starting));
380
 ReserveStackSpace(here.coroutines, &here, here.size, NULL);
7 months ago
381
 assert(false);
6 months ago
382
 case Chunk_Split:
383
 // Request to split this free block into two
384
 // here.size will be set to our shorter size
385
 ReserveStackSpace(here.coroutines, &here, here.size, here.limit);
386
 assert(false);
7 months ago
387
 case Chunk_Enter:
388
 // request to start a coroutine (ie use the chunk for a coroutine)
389
 // arrive here with mutex locked
390
 assert(here.state == Coroutine_Running);
6 months ago
391
 here.coroutines->active = &here;
392
 _Cor_Mutex_Unlock(&cors->mutex);
7 months ago
393
 here.value = here.start(here.entry_param);
9 months ago
394
7 months ago
395
 // check the guard
396
 assert(Check_Guard(here.guard));
9 months ago
397
6 months ago
398
 _Cor_Mutex_Lock(&here.coroutines->mutex);
399
 here.coroutines->active = NULL;
7 months ago
400
 assert(here.state == Coroutine_Running);
6 months ago
401
 Link_Remove(&here.link);
7 months ago
402
 here.state = Coroutine_Complete;
6 months ago
403
 List_AddTail(&here.coroutines->inactive, &here.link);
7 months ago
404
 // Coroutine has completed
405
 // Loop round to redo the setjmp() - if this coroutine yielded, then the setjmp will
406
 // need reseting
9 months ago
4
407
 }
408
 }
409
 }
410
9 months ago
411
8 months ago
412
 static void Coroutine_RunNext(void)
9 months ago
413
 {
414
 // arrive here with mutex unlocked
6 months ago
415
 _Cor_Mutex_Lock(&g_c->waiting_mutex);
416
 _Cor_Mutex_Lock(&g_c->mutex);
417
 Coroutine *next = List_Link_Container(Coroutine, link, List_GetHead(&g_c->runable));
9 months ago
418
 assert(next->state == Coroutine_Running);
419
 longjmp(next->buf, Chunk_Enter);
420
 assert(false);
421
 }
422
423
8 months ago
424
 void Coroutine_StartSystem(void)
9 months ago
4
425
 {
6 months ago
426
 assert(!g_c);
9 months ago
427
6 months ago
428
 Coroutines *cors = _Cor_Malloc(sizeof(*g_c));
429
 assert(cors);
9 months ago
430
6 months ago
431
 cors->state = Coroutines_Starting;
432
 _Cor_Mutex_ctor(&cors->mutex);
9 months ago
433
6 months ago
434
 cors->tip = NULL;
435
 cors->active = NULL;
6 months ago
436
 cors->primary = NULL;
5 months ago
437
 cors->stack_limit = g_stack_limit;
9 months ago
4
438
6 months ago
439
 List_Init(&cors->all);
6 months ago
440
 List_Init(&cors->free);
441
 List_Init(&cors->inactive);
442
 List_Init(&cors->runable);
443
 List_Init(&cors->waiting);
444
 _Cor_Mutex_ctor(&cors->waiting_mutex);
445
 _Cor_Mutex_Lock(&cors->waiting_mutex);
9 months ago
4
446
6 months ago
447
 cors->report.coroutines_created = 0;
448
 cors->report.coroutines_pool_size = 0;
449
 cors->report.largest_stack = 0;
450
451
 // Charactersize the system...
452
 if (!setjmp(cors->chunk_allocated)){
453
 ReserveStackSpace(cors, NULL, COROUTINE_STARTUP_STACK_SIZE, NULL);
9 months ago
4
454
 }
6 months ago
455
 Coroutine *cor = List_Link_Container(Coroutine, link, List_GetHead(&cors->free));
456
 cor->size = COROUTINE_STARTUP_STACK_SIZE;
457
 if (!setjmp(cors->chunk_allocated)){
458
 longjmp(cor->buf, Chunk_Create);
459
 }
460
 cors->gap_before = cor->prev_limit - (unsigned char *)cor;
461
 cors->gap_after = (unsigned char *)cor - cor->base;
462
 // ...charactersize the system
9 months ago
463
6 months ago
464
 // discard what we've just created
6 months ago
465
 List_Init(&cors->all);
6 months ago
466
 List_Init(&cors->free);
467
 cors->tip = NULL;
468
469
 cors->state = Coroutines_Started;
470
471
 g_c = cors;
9 months ago
4
472
 }
473
9 months ago
474
7 months ago
475
 void Coroutine_SetStackLimit(void *limit){
5 months ago
476
 assert(!limit || !g_c || !(g_c->state == Coroutines_Started || g_c->state == Coroutines_Active) || (unsigned char *)limit < (unsigned char *)g_c->tip || !g_c->tip);
477
 g_stack_limit = limit;
478
 if (g_c){
479
 g_c->stack_limit = limit;
480
 }
7 months ago
481
 }
482
483
8 months ago
484
 Coroutine_Report Coroutine_StopSystem(void)
9 months ago
4
485
 {
6 months ago
486
 assert(g_c);
487
 assert(g_c->state == Coroutines_Started);
488
 _Cor_Mutex_Lock(&g_c->mutex);
489
 g_c->state = Coroutines_Stopping;
9 months ago
4
490
6 months ago
491
 uintptr_t stackminheadroom;
7 months ago
492
 #if COROUTINE_RECORD_LOWEST_HEADROOM
6 months ago
493
 stackminheadroom = g_c->report.largest_stack;
494
 for (List_Link *link = g_c->free.fwd.link.next; Link_NextIsLink(link); link = Link_Next(link)){
9 months ago
495
 Coroutine *cor = List_Link_Container(Coroutine, link, link);
7 months ago
496
 if (cor->guard){
6 months ago
497
 for (uintptr_t i = 4; i < cor->size-3; i += 4){
7 months ago
498
 if (!Check_Guard(&cor->guard[i])){
499
 stackminheadroom = i < stackminheadroom ? i : stackminheadroom;
500
 break;
501
 }
9 months ago
502
 }
503
 }
504
 }
7 months ago
505
 #else
506
 stackminheadroom = 0;
507
 #endif
6 months ago
508
 g_c->report.lowest_headroom = stackminheadroom;
9 months ago
509
6 months ago
510
 assert(List_IsEmpty(&g_c->inactive));
511
 _Cor_Mutex_Unlock(&g_c->waiting_mutex);
512
 _Cor_Mutex_dtor(&g_c->waiting_mutex);
9 months ago
4
513
6 months ago
514
 assert(g_c->state == Coroutines_Stopping);
515
 _Cor_Mutex_Unlock(&g_c->mutex);
516
 _Cor_Mutex_dtor(&g_c->mutex);
9 months ago
517
6 months ago
518
 Coroutine_Report ret = g_c->report;
519
520
 _Cor_Free(g_c);
521
 g_c = NULL;
522
523
 return ret;
9 months ago
4
524
 }
525
9 months ago
526
9 months ago
527
 void Coroutine_Run_Coroutine(
528
 Coroutine *cor,
9 months ago
529
 void *value
530
 ){
531
 Coroutines *cors = cor->coroutines;
6 months ago
532
533
 // Can't Coroutine_Run_Coroutine() off-thread
534
 assert(g_c == cors);
535
8 months ago
536
 _Cor_Mutex_Lock(&cors->mutex);
9 months ago
537
 assert(cors->state == Coroutines_Started);
538
 cors->state = Coroutines_Active;
539
 cors->primary = cor;
9 months ago
540
4 months ago
541
 _Coroutine_Continue(cors, cor, value, true);
9 months ago
4
542
9 months ago
543
 if (!setjmp(cors->controller)){
8 months ago
544
 _Cor_Mutex_Unlock(&cors->mutex);
9 months ago
545
9 months ago
4
546
 // start the first coroutine
547
 Coroutine_RunNext();
548
 }
9 months ago
549
 // arrive here with mutex locked
9 months ago
550
 assert(List_IsEmpty(&cors->runable));
551
 assert(List_IsEmpty(&cors->waiting));
552
 assert(cors->state == Coroutines_Active);
553
 cors->state = Coroutines_Started;
8 months ago
554
 _Cor_Mutex_Unlock(&cors->mutex);
9 months ago
555
 }
556
557
6 months ago
558
 bool Coroutine_Run(
6 months ago
559
 size_t stack,
9 months ago
560
 Coroutine_Start start,
6 months ago
561
 void *value,
562
 void **result
9 months ago
563
 ){
6 months ago
564
 if (g_c && g_c->active){
5 months ago
565
 assert(!Coroutine_StackHasOverrun());
6 months ago
566
 void *res = start(value);
567
 if (result){
568
 *result = res;
569
 }
570
 // no failures, so...
571
 return false;
7 months ago
572
 }
6 months ago
573
 assert(!g_c || g_c->state == Coroutines_Started);
574
 bool need_start = !g_c;
7 months ago
575
 if (need_start){
576
 Coroutine_StartSystem();
577
 }
6 months ago
578
 Coroutine *cor = Coroutine_New(stack, start);
6 months ago
579
 if (!cor){
580
 // that didn't work
581
 return true;
582
 }
9 months ago
583
 Coroutine_Run_Coroutine(cor, value);
6 months ago
584
 if (result){
585
 *result = Coroutine_GetValue(cor);
586
 }
9 months ago
587
 Coroutine_Delete(cor);
7 months ago
588
 if (need_start){
589
 Coroutine_StopSystem();
590
 }
6 months ago
591
 // no failures, so...
592
 return false;
9 months ago
4
593
 }
594
595
6 months ago
596
 static void Coroutine_FreeToIdle(
597
 Coroutine *cor,
9 months ago
598
 Coroutine_Start start
599
 ){
6 months ago
600
 assert(cor->state == Coroutine_Free);
601
 cor->state = Coroutine_Idle;
602
 cor->start = start;
603
 cor->value = NULL;
604
 Link_Remove(&cor->link);
605
 List_AddHead(&g_c->inactive, &cor->link);
9 months ago
606
6 months ago
607
 g_c->report.coroutines_created += 1;
608
 }
609
610
611
 static void Coroutine_FreeToIdleSize(
612
 Coroutine *cor,
613
 Coroutine_Start start,
614
 size_t size
615
 ){
616
 assert(!cor->guard);
617
 cor->size = size;
618
 cor->base = (unsigned char *)cor - g_c->gap_after;
619
 cor->limit = cor->base - cor->size;
620
 Coroutine_FreeToIdle(cor, start);
621
 }
622
623
624
 static Coroutine *Coroutine_New_Lock_Assumed(
625
 size_t size,
626
 Coroutine_Start start
627
 ){
628
 List_Link *link;
629
630
 if (!g_c->tip){
631
 // no tip - time to create one
632
633
 // we're the non-Coroutine which starts the Coroutine system.
634
 // Add a single free block
635
 if (!setjmp(g_c->chunk_allocated)){
636
 ReserveStackSpace(g_c, NULL, COROUTINE_STARTUP_STACK_SIZE, NULL);
6 months ago
637
 }
6 months ago
638
 }
639
6 months ago
640
 Coroutine *cor = NULL;
6 months ago
641
 for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
6 months ago
642
 Coroutine *candidate = List_Link_Container(Coroutine, link, link);
643
 if (!candidate->guard) {
6 months ago
644
 // this must be the tip
6 months ago
645
 assert(candidate == g_c->tip);
6 months ago
646
647
 // If this is the only Coroutine in the system, go ahead and use it regardless of size.
648
 // Note: there can only be one free block if there's no other sort of blocks as we merge on free
649
 if (List_IsEmpty(&g_c->inactive) &&
650
 List_IsEmpty(&g_c->runable) &&
651
 List_IsEmpty(&g_c->waiting) ){
652
 if (g_c->stack_limit){
6 months ago
653
 size_t available = (unsigned char *)candidate - g_c->stack_limit - g_c->gap_after;
6 months ago
654
 size = available < size ? available : size;
655
 }
6 months ago
656
 Coroutine_FreeToIdleSize(candidate, start, size);
657
 return candidate;
7 months ago
658
 }
6 months ago
659
660
 // Not the only coroutine in the system - check size
661
 if (g_c->stack_limit){
662
 // there's a limit - see what that space allows....
6 months ago
663
 size_t available = (unsigned char *)candidate - g_c->stack_limit - g_c->gap_after;
6 months ago
664
665
 if (available < size){
666
 // not enough space for this coroutine
667
 return NULL;
668
 }
669
5 months ago
670
 if (available < size + g_c->gap_before + g_c->gap_after + COROUTINE_MINIMUM_STACK_SIZE) {
6 months ago
671
 // not enough space for another coroutine - use all the space for this one
672
 size = available;
673
 }
7 months ago
674
 }
6 months ago
675
 Coroutine_FreeToIdleSize(candidate, start, size);
676
 return candidate;
9 months ago
4
677
 }
6 months ago
678
 if (candidate->size >= size && candidate > cor){
679
 // chunk big enough, and a better choice than cor
680
 cor = candidate;
681
 }
682
 }
683
684
 if (cor){
685
 // - work out whether we're splitting or using the whole chunk
686
 if (cor->size >= size + g_c->gap_before + g_c->gap_after + COROUTINE_MINIMUM_STACK_SIZE){
687
 // enough space for a second coroutine so split this free block
688
 cor->size = size;
689
 if (!setjmp(g_c->chunk_allocated)){
690
 longjmp(cor->buf, Chunk_Split);
6 months ago
691
 }
692
 }
6 months ago
693
 // cor now ready to use
694
 Coroutine_FreeToIdle(cor, start);
695
 return cor;
9 months ago
4
696
 }
697
6 months ago
698
 // No big-enough free blocks - check if there's space beyond the tip block
699
5 months ago
700
 if (g_c->stack_limit) {
701
 ptrdiff_t available = (unsigned char *)g_c->tip->limit - g_c->gap_before - g_c->gap_after - g_c->stack_limit;
702
 if (available < (ptrdiff_t)size){
703
 // no space for a new stack block
704
 return NULL;
705
 }
6 months ago
706
 }
707
 Coroutine *tip = g_c->tip;
708
 Coroutine *me = g_c->active;
709
 if (tip == me) {
710
 if (!setjmp(g_c->chunk_allocated)){
711
 ReserveStackSpace(g_c, me, StackTopNow() - me->limit, NULL);
712
 }
713
 } else {
714
 if (!setjmp(g_c->chunk_allocated)){
715
 longjmp(tip->buf, Chunk_Create);
716
 }
717
 }
718
6 months ago
719
 cor = List_Link_Container(Coroutine, link, List_GetTail(&g_c->free));
9 months ago
4
720
 assert(cor->state == Coroutine_Free);
6 months ago
721
 cor->size = size;
722
 cor->limit = (unsigned char *)cor - g_c->gap_after - size;
9 months ago
4
723
 cor->state = Coroutine_Idle;
724
 cor->start = start;
725
 cor->value = NULL;
6 months ago
726
 Link_Remove(&cor->link);
727
 List_AddHead(&g_c->inactive, &cor->link);
9 months ago
4
728
6 months ago
729
 g_c->report.coroutines_created += 1;
730
 return cor;
731
 }
9 months ago
732
6 months ago
733
734
 Coroutine *Coroutine_New(
735
 size_t stack,
736
 Coroutine_Start start
737
 ){
738
 assert(g_c);
739
 assert((g_c->state == Coroutines_Started && List_IsEmpty(&g_c->inactive)) || g_c->state == Coroutines_Active);
740
 assert(!Coroutine_StackHasOverrun());
741
742
 _Cor_Mutex_Lock(&g_c->mutex);
743
744
 Coroutine *cor = Coroutine_New_Lock_Assumed(stack, start);
745
746
 if (cor && cor->size > g_c->report.largest_stack){
747
 g_c->report.largest_stack = cor->size;
748
 }
749
750
 _Cor_Mutex_Unlock(&g_c->mutex);
751
9 months ago
4
752
 return cor;
753
 }
754
9 months ago
755
756
 void Coroutine_Delete(
757
 Coroutine *cor
758
 ){
6 months ago
759
 assert(!Coroutine_StackHasOverrun());
6 months ago
760
 if (cor){
761
 Coroutines *cors = cor->coroutines;
762
 _Cor_Mutex_Lock(&cors->mutex);
763
 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Complete);
764
 cor->state = Coroutine_Free;
6 months ago
765
 Link_Remove(&cor->link);
766
6 months ago
767
 // insert into free list
768
 List_AddHead(&cors->free, &cor->link);
6 months ago
769
770
 // Check for merge with following Coroutine
6 months ago
771
 List_Link *link = Link_Next(&cor->all_link);
6 months ago
772
 if (Link_NextIsLink(link)){
6 months ago
773
 Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
774
 if (listcor->state == Coroutine_Free){
6 months ago
775
 // merge
6 months ago
776
 cor->size += cor->limit - listcor->limit;
6 months ago
777
 cor->limit = listcor->limit;
778
 cor->guard = listcor->guard;
6 months ago
779
 Link_Remove(&listcor->all_link);
6 months ago
780
 Link_Remove(&listcor->link);
6 months ago
781
 if (g_c->tip == listcor){
782
 g_c->tip = cor;
783
 }
6 months ago
784
 }
785
 }
786
787
 // check for merge with prev coroutine
6 months ago
788
 link = Link_Prev(&cor->all_link);
6 months ago
789
 if (Link_PrevIsLink(link)){
6 months ago
790
 Coroutine *listcor = List_Link_Container(Coroutine, all_link, link);
791
 if (listcor->state == Coroutine_Free){
6 months ago
792
 // merge
6 months ago
793
 listcor->size += listcor->limit - cor->limit;
6 months ago
794
 listcor->limit = cor->limit;
795
 listcor->guard = cor->guard;
6 months ago
796
 Link_Remove(&cor->all_link);
6 months ago
797
 Link_Remove(&cor->link);
6 months ago
798
 if (g_c->tip == cor){
799
 g_c->tip = listcor;
800
 }
6 months ago
801
 }
802
 }
803
6 months ago
804
 _Cor_Mutex_Unlock(&cors->mutex);
805
 }
9 months ago
4
806
 }
807
9 months ago
808
8 months ago
809
 // Coroutine_Continue, assuming the mutex is claimed
4 months ago
810
 static bool _Coroutine_Continue(
811
 Coroutines *cors,
9 months ago
812
 Coroutine *cor,
813
 void *value,
814
 bool early
815
 ){
4 months ago
816
 if (cor->state == Coroutine_Free || cor->state == Coroutine_Complete){
817
 return true;
818
 }
819
 if (cor->state == Coroutine_Running){
820
 // already running
821
 return false;
822
 }
9 months ago
4
823
 assert(cor->state == Coroutine_Idle || cor->state == Coroutine_Waiting);
824
 cor->entry_param = value;
825
 cor->state = Coroutine_Running;
6 months ago
826
 Link_Remove(&cor->link);
9 months ago
4
827
 if ( early ) {
9 months ago
828
 List_AddHead(&cors->runable, &cor->link);
9 months ago
4
829
 } else {
9 months ago
830
 List_AddTail(&cors->runable, &cor->link);
9 months ago
4
831
 }
8 months ago
832
 _Cor_Mutex_Unlock(&cors->waiting_mutex);
4 months ago
833
 return false;
8 months ago
834
 }
835
836
4 months ago
837
 bool Coroutine_Continue(
8 months ago
838
 Coroutine *cor,
839
 void *value,
840
 bool early
841
 ){
6 months ago
842
 assert(!Coroutine_StackHasOverrun());
8 months ago
843
 Coroutines *cors = cor->coroutines;
8 months ago
844
 _Cor_Mutex_Lock(&cors->mutex);
4 months ago
845
 bool ret = _Coroutine_Continue(cors, cor, value, early);
8 months ago
846
 _Cor_Mutex_Unlock(&cors->mutex);
4 months ago
847
 return ret;
9 months ago
4
848
 }
849
9 months ago
850
851
 void *Coroutine_Yield(
852
 void *value,
853
 Coroutine_YieldCallback on_yield,
9 months ago
854
 void *yield_me
9 months ago
855
 ){
6 months ago
856
 assert(g_c);
857
 Coroutine *me = g_c->active;
7 months ago
858
 assert(me);
6 months ago
859
 assert(!Coroutine_StackHasOverrun());
9 months ago
860
6 months ago
861
 _Cor_Mutex_Lock(&g_c->mutex);
9 months ago
862
 Coroutines *cors = me->coroutines;
6 months ago
863
 assert(me && me->state == Coroutine_Running && cors == g_c);
7 months ago
864
 me->stack_top = StackTopNow();
9 months ago
4
865
 me->value = value;
866
 me->state = Coroutine_Waiting;
9 months ago
867
6 months ago
868
 Link_Remove(&me->link);
8 months ago
869
 if (!List_IsEmpty(&cors->runable)){
8 months ago
870
 _Cor_Mutex_Unlock(&cors->waiting_mutex);
8 months ago
871
 }
9 months ago
872
 List_AddTail(&cors->waiting, &me->link);
9 months ago
873
9 months ago
874
 switch (setjmp(me->buf)){
875
 case Chunk_Initial:
8 months ago
876
 _Cor_Mutex_Unlock(&cors->mutex);
9 months ago
877
 on_yield(yield_me);
9 months ago
4
878
 Coroutine_RunNext();
7 months ago
879
 assert(false);
9 months ago
880
 case Chunk_Create:
6 months ago
881
 assert(me == g_c->tip);
882
 ReserveStackSpace(me->coroutines, me, me->stack_top - me->limit, NULL);
9 months ago
883
 assert(false);
884
 case Chunk_Enter:
885
 // arrive here with mutex locked
9 months ago
886
 cors->active = me;
6 months ago
887
 assert(!Coroutine_StackHasOverrun());
9 months ago
888
 // when we return here - we are running again
889
 assert(me->state == Coroutine_Running);
890
 void *res = me->entry_param;
8 months ago
891
 _Cor_Mutex_Unlock(&cors->mutex);
9 months ago
892
 return res;
9 months ago
4
893
 }
9 months ago
894
 return NULL;
9 months ago
4
895
 }
896
9 months ago
897
898
 void *Coroutine_GetValue(
899
 Coroutine *cor
900
 ){
9 months ago
4
901
 return cor->value;
902
 }
903
9 months ago
904
8 months ago
905
 Coroutine *Coroutine_GetActive(void)
9 months ago
4
906
 {
6 months ago
907
 return g_c ? g_c->active : NULL;
9 months ago
4
908
 }
909
9 months ago
910
8 months ago
911
 intptr_t Coroutine_GetStackHeadroom(void){
6 months ago
912
 assert(g_c);
913
 assert(!Coroutine_StackHasOverrun());
914
 Coroutine *me = g_c->active;
7 months ago
915
 if (!me){
916
 // no active coroutine
6 months ago
917
 unsigned char *stack_limit = g_c->stack_limit;
7 months ago
918
 if (stack_limit){
919
 // no stack limit - assume we'll use COROUTINE_STACK_SIZE
920
 return StackTopNow() - stack_limit;
921
 } else {
922
 // no information where the stack ends - return something
6 months ago
923
 return COROUTINE_MINIMUM_STACK_SIZE;
7 months ago
924
 }
925
 }
6 months ago
926
 return StackTopNow() - me->limit;
9 months ago
927
 }
928
929
7 months ago
930
 // This is used to avoid compiler warnings about returning the address of a local
931
 static inline void *StopAddressWarnings(void *p)
932
 {
933
 return p;
9 months ago
934
 }
935
936
7 months ago
937
 void *Coroutine_GetStackHWM(void){
6 months ago
938
 assert(g_c);
939
 assert(g_c->state == Coroutines_Active);
940
 assert(!Coroutine_StackHasOverrun());
7 months ago
941
 // Find where the guards end
942
 unsigned char *guard;
6 months ago
943
 for (guard = g_c->active->guard; Check_Guard(guard); guard += 4){
7 months ago
944
 // do nothing
945
 }
946
 return guard;
947
 }
8 months ago
948
949
7 months ago
950
 void Coroutine_ClearStackForHWM(void){
6 months ago
951
 assert(g_c);
952
 assert(g_c->state == Coroutines_Active);
953
 assert(!Coroutine_StackHasOverrun());
7 months ago
954
 unsigned char *end = StackTopNow() - GUARD_PATTERN_SIZE;
6 months ago
955
 for (unsigned char *guard = g_c->active->guard+GUARD_PATTERN_SIZE; guard <= end; guard += GUARD_PATTERN_SIZE){
7 months ago
956
 Apply_Guard(guard);
7 months ago
957
 }
958
 }
959
960
6 months ago
961
 static bool Coroutine_CanStartCoroutine_Lock_Assumed(
962
 size_t size
963
 ){
964
 assert(g_c);
965
 assert(g_c->state == Coroutines_Started || g_c->state == Coroutines_Active);
966
 assert(!Coroutine_StackHasOverrun());
967
968
 if (!g_c->stack_limit){
7 months ago
969
 return true;
970
 }
7 months ago
971
6 months ago
972
 if (!g_c->tip){
973
 return true;
974
 }
975
976
 if (g_c->tip->state == Coroutine_Free){
977
 // last block is free
978
 if ((unsigned char *)g_c->tip - g_c->stack_limit >= (ptrdiff_t)(g_c->gap_after + size)){
979
 // enough room in free block, which is the last block
980
 return true;
981
 }
982
 } else {
983
 // last block is allocated
984
 if (g_c->tip->limit - g_c->stack_limit >= (ptrdiff_t)(g_c->gap_before + g_c->gap_after + size)){
985
 // enough room after the last block, which is allocated
986
 return true;
987
 }
988
 }
989
990
 // not enough room between allocated blocks and stack limit, so check free list
991
 List_Link *link;
992
 for (link = List_Begin(&g_c->free); Link_NextIsLink(link); link = Link_Next(link)){
993
 Coroutine *cor = List_Link_Container(Coroutine, link, link);
994
 if (cor->size >= size){
995
 return true;
996
 }
997
 }
998
999
 return false;
7 months ago
1000
 }
1001
1002
6 months ago
1003
 bool Coroutine_CanStartCoroutine(
1004
 size_t size
1005
 ){
1006
 _Cor_Mutex_Lock(&g_c->mutex);
1007
1008
 bool result = Coroutine_CanStartCoroutine_Lock_Assumed(size);
1009
1010
 _Cor_Mutex_Unlock(&g_c->mutex);
1011
1012
 return result;
1013
 }
1014
8 months ago
1015
 void *Coroutine_GetCStackTop(void){
6 months ago
1016
 assert(!Coroutine_StackHasOverrun());
1017
 if ((g_c->state == Coroutines_Started || g_c->state == Coroutines_Active) && g_c->tip != g_c->active) {
1018
 return g_c->tip->stack_top;
7 months ago
1019
 } else {
1020
 return StackTopNow();
1021
 }
9 months ago
1022
 }
1023
1024
7 months ago
1025
 static unsigned char *StackTopNow(void){
7 months ago
1026
 unsigned char here[4];
1027
 return StopAddressWarnings(here);
1028
 }
1029
1030
9 months ago
1031
 struct Coroutine_ChainParam {
1032
 Coroutine_Start start;
1033
 void *value;
1034
 Coroutine *ret;
1035
 };
1036
1037
1038
 static void *Coroutine_ChainFn(
1039
 void *param
1040
 ){
1041
 struct Coroutine_ChainParam *params = (struct Coroutine_ChainParam *)param;
1042
 Coroutine_Continue(params->ret, params->start(params->value), true);
1043
 return NULL;
1044
 }
1045
1046
1047
 static void Coroutine_ChainYield(
1048
 void *unused
1049
 ){
1050
 (void)unused;
1051
 }
1052
1053
6 months ago
1054
 bool Coroutine_Chain(
6 months ago
1055
 size_t size,
9 months ago
1056
 Coroutine_Start start,
6 months ago
1057
 void *value,
1058
 void **result
9 months ago
1059
 ){
8 months ago
1060
 assert(Check_Guard(Coroutine_GetActive()->guard));
6 months ago
1061
 Coroutine *cor = Coroutine_New(size, Coroutine_ChainFn);
6 months ago
1062
 if (!cor){
1063
 // failed
1064
 return true;
1065
 }
9 months ago
1066
 struct Coroutine_ChainParam params = {
1067
 start,
1068
 value,
1069
 Coroutine_GetActive()
1070
 };
1071
 Coroutine_Continue(cor, &params, true);
1072
 void *res = Coroutine_Yield(NULL, Coroutine_ChainYield, NULL);
1073
 Coroutine_Delete(cor);
6 months ago
1074
 if (result){
1075
 *result = res;
1076
 }
1077
 // success!
1078
 return false;
9 months ago
1079
 }
1080
1081
9 months ago
1082
 bool Coroutine_IsRunning(
1083
 Coroutine *cor
1084
 )
9 months ago
4
1085
 {
9 months ago
1086
 int state = cor->state;
1087
 return state == Coroutine_Running || state == Coroutine_Waiting;
9 months ago
4
1088
 }
9 months ago
1089
1090
7 months ago
1091
 bool Coroutine_IsComplete(
1092
 Coroutine *cor
1093
 )
1094
 {
1095
 int state = cor->state;
1096
 return state == Coroutine_Complete;
1097
 }
1098
1099
8 months ago
1100
 bool Coroutine_IsStarted(void){
6 months ago
1101
 return g_c && (g_c->state == Coroutines_Active || g_c->state == Coroutines_Started);
9 months ago
1102
 }
6 months ago
1103
1104
 void _Coroutine_Dump(void){
1105
 char *state_to_text[] = {
1106
 "Free",
1107
 "Idle",
1108
 "Running",
1109
 "Waiting",
1110
 "Complete"
1111
 };
1112
 unsigned idx = 0;
1113
 List_Link *link;
1114
 for (link = List_Begin(&g_c->all); Link_NextIsLink(link); link = Link_Next(link)){
1115
 Coroutine *cor = List_Link_Container(Coroutine, all_link, link);
1116
 printf("%d) %p (%s) %ld%s\n", idx++, cor, state_to_text[cor->state], cor->size, cor == g_c->tip ? " (TIP)" : "");
1117
 }
1118
 }
1119