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