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