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