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