/
fibers.h
508 lines (440 loc) · 16.6 KB
/
fibers.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
//////////////////////////////////////////////////////////////////////
// fibers.h -- Fibers Class Support
// Date: Sat Apr 19 00:14:27 2014 (C) Warren Gay VE3WWG
///////////////////////////////////////////////////////////////////////
// DESCRIPTION:
//
// This is a very light weight fibers (aka coroutines) library,
// managed by a singular instance of class Fibers. This module
// depends upon two symbols in your ld script, which is usually
// mk20dx256.ld (or in my case mk20dx256_sbrk.ld).
//
// See the end of this file for more information
///////////////////////////////////////////////////////////////////////
#ifndef FIBERS_H
#define FIBERS_H
#include <stdint.h>
extern "C" {
// Your coroutine functions will use this function prototype
typedef void (*fiber_func_t)(void *arg);
}
enum FiberState {
FiberCreated, // Fiber created, but not yet started
FiberExecuting, // Fiber is executing
FiberReturned, // Fiber has terminated
FiberInvalid // Invalid fiberx value
};
struct fiber_t {
// Saved Registers
uint32_t sp; // Saved sp register
uint32_t r2; // after the function has begun
uint32_t r3; // Saved r3 etc.
uint32_t r4;
uint32_t r5;
uint32_t r6;
uint32_t r7;
uint32_t r8;
uint32_t r9;
uint32_t r10;
uint32_t r11;
uint32_t r12;
void *lr; // Return address (pc)
// Parameters
fiber_func_t funcptr; // Start function ptr
void *arg; // Startup arg value
uint32_t stack_size; // Stack size for this main/coroutine
uint32_t initial_sp; // Initial stack pointer (for restart)
// State
FiberState state; // Current fiber state
};
//////////////////////////////////////////////////////////////////////
// There must only be ONE instance of this class defined
//////////////////////////////////////////////////////////////////////
template <unsigned max_fibers=16>
class Fibers {
volatile fiber_t fibers[max_fibers]; // Collection of fiber states
volatile uint16_t n_fibers; // Number of active fibers
volatile uint16_t cur_crx; // Index to currently executing coroutine
bool instrument; // Instrument stack for stack size measurement
uint32_t pattern; // Pattern to use on stack for instrumentation
uint32_t *end_stack(); // Return end of stack address (requires _sstack)
public: Fibers(uint32_t main_stack=8192,bool instrument=false,uint32_t pattern_override=0xA5A5A5A5);
inline uint32_t size() { return n_fibers; } // Return the current # of coroutines
unsigned create(fiber_func_t func,void *arg,uint32_t stack_size);
inline unsigned current() { return cur_crx; } // Return current coroutine number (0 == main)
void yield(); // Yield CPU to next coroutine
FiberState state(uint32_t fiberx); // Return the state of a fiber
FiberState join(uint32_t fiberx); // Return when the specified fiber has ended
FiberState restart(uint32_t fiberx,fiber_func_t func,void *arg); // Restart fiber after it has terminated
uint32_t stack_size(uint32_t fiberx); // Return the approximate stack usage for specified coroutine
};
//////////////////////////////////////////////////////////////////////
// Assembler routines used:
//////////////////////////////////////////////////////////////////////
extern "C" {
extern uint32_t *fiber_getsp();
extern void fiber_set_main(uint32_t stack_size);
extern void fiber_create(volatile fiber_t *fcb,uint32_t stack_size,fiber_func_t func,void *arg);
extern void fiber_swap(volatile fiber_t *new_cr,volatile fiber_t *cur_cr);
extern void fiber_restart(volatile fiber_t *fiber,fiber_func_t func,void *arg);
}
//////////////////////////////////////////////////////////////////////
// Constructor for Fibers:
//
// main_stack Indicates # of stack bytes to reserve for main
// instrument When true, the stack is cleared with a pattern
// so that stack_size() can determine stack
// usage. (Default false)
// pattern_override Default: 0xA5A5A5A5, but can be overriden by
// the user, if false matches have been a problem
//////////////////////////////////////////////////////////////////////
template <unsigned max_fibers>
Fibers<max_fibers>::Fibers(uint32_t main_stack,bool instrument,uint32_t pattern_override) {
for (int i = 0; i < max_fibers; i++) // Initialize fibers to invalid
fibers[i].state = FiberInvalid;
pattern = pattern_override; // Fill pattern for stack (when enabled)
fiber_set_main(main_stack); // Set stack size needed by the main coroutine
n_fibers = 1; // Reserve fibers[0] for main thread
cur_crx = 0; // Main is currently in control
fibers[0].stack_size = main_stack; // Save main's stack size
fibers[0].state = FiberExecuting; // Set main's state to executing
this->instrument = instrument; // Enable/disable instrumentation
if ( instrument ) {
volatile uint32_t *ep = end_stack();
uint32_t *sp = fiber_getsp();
while ( --sp > ep )
*sp = pattern; // Fill stack with pattern
}
}
//////////////////////////////////////////////////////////////////////
// Create a new fiber:
//
// RETURNS:
// 1-n for each fiber (coroutine) created
// ~0 if we exceeded the maximum number of fibers
//
// NOTES:
// 1. Can be called from any fiber (aka coroutine)
// 2. Returns a value 1-n, for nth coroutine
// 3. Zero represents the main fiber (coroutine)
// 4. This code does not check if there is enough stack space
// for the request. Choose stack size carefully.
//////////////////////////////////////////////////////////////////////
template <unsigned max_fibers>
unsigned
Fibers<max_fibers>::create(fiber_func_t func,void *arg,uint32_t stack_size) {
// Round stack size to a word multiple
stack_size = ( stack_size + sizeof (uint32_t) ) / sizeof (uint32_t) * sizeof (uint32_t);
if ( n_fibers >= max_fibers )
return 0; // Failed: too many fibers
volatile fiber_t &new_cr = fibers[n_fibers++];
fiber_create(&new_cr,stack_size,func,arg);
new_cr.stack_size = stack_size;
return n_fibers - 1; // Return zero-based coroutine # (main == 0)
}
//////////////////////////////////////////////////////////////////////
// Yield CPU to next coroutine, round-robin
//
// NOTES:
// 1. Normally, this causes control to pass to the next fiber,
// in round-robin fashion, returning to the caller after we
// get the CPU passed back to us again.
// 2. Except when there is only the main context running, which
// then simply returns immediately to the caller again.
//////////////////////////////////////////////////////////////////////
template <unsigned max_fibers>
void
Fibers<max_fibers>::yield() {
if ( n_fibers <= 1 )
return; // There is only the main context running
uint16_t nextx = cur_crx + 1; // Compute the coroutine # of the next fiber
if ( nextx >= n_fibers )
nextx = 0; // Wrap around to main context at the end
volatile fiber_t& last_cr = fibers[cur_crx]; // Current context
volatile fiber_t& next_cr = fibers[nextx]; // Next context
cur_crx = nextx; // Change the context no.
// set previous state to created or returned
last_cr.state = last_cr.state != FiberReturned ? FiberCreated : FiberReturned;
// set current state to excuting or returned
next_cr.state = next_cr.state != FiberReturned ? FiberExecuting : FiberReturned;
fiber_swap(&next_cr,&last_cr); // Make the switch
// cur_crx has been restored by the last yield() caller
}
//////////////////////////////////////////////////////////////////////
// Determine the coroutine's stack size in bytes
//
// 1. Must have been instrumented (see constructor)
// 2. Returns approx size in bytes
// 3. Determined on a 'best effort' basis, since a false
// match on the instrumented pattern may cause a smaller
// size to be returned.
//////////////////////////////////////////////////////////////////////
template <unsigned max_fibers>
uint32_t
Fibers<max_fibers>::stack_size(uint32_t fiberx) {
if ( !instrument ) // Not instrumented
return ~0; // .. so size unknown
if ( fiberx >= n_fibers )
return ~0; // Invalid fiber/coroutine #
fiber_t& crentry = fibers[fiberx]; // Access requested coroutine
uint32_t *sp = (uint32_t *)crentry.sp; // Get it's sp
uint32_t *ep = sp - crentry.stack_size/4; // stack_size has been rounded to a word multiple
uint32_t count = 0; // Initialize count
for ( ; sp >= ep && *sp != pattern; --sp )
count += 4;
return count; // Bytes
}
//////////////////////////////////////////////////////////////////////
// Return the state of a fiber:
//
// RETURNS:
// FiberCreated Fiber created, but not yet started
// FiberExecuting Fiber is executing
// FiberReturned Fiber has terminated (returned)
// FiberInvalid Invalid fiberx value
//////////////////////////////////////////////////////////////////////
template <unsigned max_fibers>
FiberState
Fibers<max_fibers>::state(uint32_t fiberx) {
if ( fiberx >= n_fibers )
return FiberInvalid; // Invalid fiberx value given
volatile fiber_t& crentry = fibers[fiberx]; // Access requested coroutine
return crentry.state; // Return its state
}
//////////////////////////////////////////////////////////////////////
// Join with the executing fiber.
//
// RETURNS:
// FiberInvalid Fiberx does not refer to a valid fiber
// FiberReturned Fiber has terminated (successful)
//////////////////////////////////////////////////////////////////////
template <unsigned max_fibers>
FiberState
Fibers<max_fibers>::join(uint32_t fiberx) {
FiberState s;
if ( fiberx >= n_fibers )
return FiberInvalid; // Invalid fiberx: Nothing to join with
while ( (s = state(fiberx)) != FiberReturned )
this->yield(); // Keep waiting
return s;
}
//////////////////////////////////////////////////////////////////////
// Restart a terminated fiber
//////////////////////////////////////////////////////////////////////
template <unsigned max_fibers>
FiberState
Fibers<max_fibers>::restart(uint32_t fiberx,fiber_func_t func,void *arg) {
if ( fiberx >= n_fibers )
return FiberInvalid; // Invalid fiberx: Nothing to join with
volatile fiber_t& fiber = fibers[fiberx];
fiber_restart(&fiber,func,arg);
return fiber.state;
}
//////////////////////////////////////////////////////////////////////
// Protected: Return address of end of stack
//////////////////////////////////////////////////////////////////////
template <unsigned max_fibers>
uint32_t *
Fibers<max_fibers>::end_stack() {
extern uint32_t _sstack; // This comes from mk20dx256*.ld
// See fibers.hpp at end.
return &_sstack;
}
#endif // FIBERS_H
//////////////////////////////////////////////////////////////////////
// DESCRIPTION:
//
// This is a very light weight fibers (aka coroutines) library,
// managed by a singular instance of class Fibers. This module
// depends upon two symbols in your ld script, which is usually
// mk20dx256.ld (or in my case mk20dx256_sbrk.ld).
//
// The two required symbols are:
//
// _estack End stack: Which should already be defined for you
// _sstack Start stack: Which is probably not defined
//
// To add the _sstack symbol to your linking, locate your
// mk20dx256.ld (or equivalent) script:
//
// $ find <root_dir> -name 'mk20dx256*'
//
// where <root_dir> varies by platform. Using my teensy3_lib
// structure, the root_dir is likely /opt/teensy3_lib.
//
// Otherwise, using the Arduino IDE, use
// /Applications/Arduino.app for your root_dir on the Mac. On
// Windows, you'll have to sort that out for yourself.
//
// Look towards the end if the file for the section labelled .stack :
//
// .stack :
// {
// . = ALIGN(4);
// _sstack = .; /* Add this line to define the start of the stack */
// . = . + _minimum_stack_size;
// . = ALIGN(4);
// } >RAM
//
// _test_estack = ORIGIN(RAM) + LENGTH(RAM);
// _estack = ORIGIN(RAM) + 64 * 1024;
//
// The symbol for _estack should already be defined. Add the line
// above for _sstack where the comment says "Add this line", if
// necessary.
//
// The purpose of the _sstack symbol is to tell the Fibers class
// where the stack begins. This is only required if you are
// "instrumenting" the stack to later find out how much stack
// space was actually used by a given coroutine (or main
// routine). Unfortunately, this symbol is required whether you
// plan to use this feature or not.
//
// COMPILING:
// ----------
//
// When using the teensy3_lib structure, the class header should be
// includable in your C++ code as:
//
// // #include <fibers.hpp>
//
// Arduino IDE users may be out of luck, since one assembler routine
// is required (it can be done, but messing with the IDE build would
// be necessary to include that one assembled object file).
//
// LINKING:
// --------
//
// When using the teensy3_lib structure, the fibers library just needs
// the linker option added:
//
// -lfibers
//
// Fibers API Usage:
// -----------------
//
// Somewhere it is recommended that you declare one instance of
// Fibers globally. Global access makes it available from other
// modules when it is time to "yield".
//
// Global yield() Routine:
// -----------------------
//
// To make maximum use of CPU, declare this routine somewhere:
//
// void yield() {
// fibers.yield();
// }
//
// The Fibers class is a template class, requiring a template parameter,
// that declares the maximum number of fibers you intend to create.
// By default 15 fibers + main are assumed.
//
// Fibers<> fibers; // Defaults to 15 + main fibers max
// Fibers<4> fibers; // Up to 3 fibers + main
//
// By default 8K of stack is reserved for the main fiber. To change
// the allocation for main (only), specify a stack size:
//
// Fibers<4> fibers(3000); // Allocate 3000 bytes to main stack
//
// To instrument the stack for determining stack size, add the
// boolean true parameter:
//
// Fibers<4> fibers(3000,true); // Use a main stack of 3000 bytes, and
// // instrument stack for size checks
//
// Once this has been done, stack space has been reserved for the
// main thread.
//
// To create a fiber, you invoke the Fibers::create() method:
//
// fibers.create(foo,foo_arg,4000); // Stack for foo is 4000 bytes
//
// It returns an unsigned number > 0 for identification if you
// need it (main is always zero). This example will start function:
//
// void foo(void *foo_arg)
//
// with an allocated stack of 4000 bytes.
//
// Additional fiber (coroutines) can be created from any executing
// fiber context.
//
// From this point on, the main routine or the executing coroutine
// (in foo) call the yield method to give up the CPU:
//
// fibers.yield();
//
// or the global yield() function, if you set that up.
//
// Scheduling is done in round-robin fashion, giving the CPU to
// the next coroutine in sequence.
//
// FIBERS THAT "RETURN":
// =====================
//
// If a coroutine (other than main) "returns", it will simply
// it will cease to execute (it actually does execute in
// a loop which just calls yield). It's state is marked as
// FiberReturned.
//
// The fiber can be restarted using the Fibers::restart()
// method, allowing a worker fiber to be controlled.
//
// DETERMINING STACK SIZE:
// =======================
//
// The first question that arises when creating threads or fibers
// is "how much stack space do I need?" To estimate this, the
// Fibers class has the optional "instrument" boolean, which
// when enabled, causes the stack to be initialized with a "pattern".
// By default this feature is disabled (see constructor). When
// enabled the default pattern used is 0xA5A5A5A5.
//
// Allow your coroutines to run for a time and then you can:
//
// bytes = fibers.stack_size(x);
//
// where x is the coroutine number (x==0 is the main routine).
//
// This estimates usage based upon the stack pattern words being
// overwritten with something other than "pattern". Even if you
// don't use any coroutines, you should be able to estimate the
// stack use of the main program.
//
// If you suspect a false match on "pattern" has occurred,
// causing a smaller size to be returned, repeat the test using a
// different uint32_t pattern value, that is unlikely to appear
// on the stack.
//
// WARNING:
// ========
// When allocating stack space, be sure to include an extra
// amount for use by interrupt service routines.
//
// LDSCRIPT CHANGE:
// ================
//
// This package needs to know where the bottom of your stack is
// through the use of the symbol _sstack. Your current ldscript
// should already define an _estack symbol.
//
// Towards the end of the ldscript that I use, I have:
//
// /* this just checks there is enough RAM for the stack */
// .stack :
// {
// . = ALIGN(4);
// _sstack = .;
// . = . + _minimum_stack_size;
// . = ALIGN(4);
// } >RAM
//
// _estack = ORIGIN(RAM) + 64 * 1024;
//
// Notice how the _sstack symbol was inserted to identify the low
// (bottom) point of the stack.
//
//////////////////////////////////////////////////////////////////////
// End fibers.h