README.md
1Yielding C Fun
2==============
3
4Introduction
5------------
6
7Yielding C Fun (YCF) is a tool that transforms functions written in a
8subset of the C programming language so that they become yieldable. A
9yieldable function can be suspended/yielded/paused/trapped (either
10automatically or where the user has inserted a particular statement)
11and then be resumed at a later point. Yileldable functions are also
12called [coroutines](https://en.wikipedia.org/wiki/Coroutine).
13
14Difference Between Yielding C Fun and Coroutine Libraries
15---------------------------------------------------------
16
17Several libraries implement [coroutine support for the C programming
18language](https://en.wikipedia.org/wiki/Coroutine#Implementations_for_C)
19(e.g., \[[1], [2], [3], [4], [5], [6], [7], [8], [9], [10], [11],
20[12], [13]\]). These libraries either rely on platform-specific code
21or do not save call stack variables. Yielding C Fun (YCF) does not
22have any of these two limitations. YCF can accomplish this as it is a
23source-to-source transformation tool and not only a library.
24
25YCF has been created to make it easier to implement yielding Erlang
26[NIFs](http://erlang.org/doc/tutorial/nif.html) and
27[BIFs](http://erlang.org/pipermail/erlang-questions/2009-October/046899.html)
28(i.e., Erlang functions that are written in C). Below are examples of
29YCF features that are useful when implementing yielding Erlang NIFs
30and BIFs:
31
32 * YCF automatically generates a destroy function for each yieldable
33 function. The destroy function frees resources that are used by a
34 suspended function. The destroy function is useful when a suspended
35 function needs to abort (e.g., when the Erlang process that invoked
36 the function has died).
37
38 * YCF can automatically insert code that yields functions after a
39 user specifiable number of loop iterations and goto statements.
40
41 * YCF has a hook system that lets the user insert code that is
42 triggered when certain events happen (e.g., when a function
43 yields).
44
45The main limitations of YCF are that it cannot handle all valid C code
46and that it cannot make library functions without source code
47yieldable. Pointers to stack-allocated data are also not allowed (YCF
48has a memory allocation function called `YCF_STACK_ALLOC` to work
49around this issue).
50
51Requirements
52------------
53
54* A C99 compatible C compiler
55* make (optional but useful for building)
56
57Compile and Test
58----------------
59
60Build the executable `$YCF_ROOT/bin/yielding_c_fun.bin`:
61
62 make
63
64Build the executable and run all tests:
65
66 make test
67
68Getting Started
69---------------
70
71A brief introduction tutorial can be found
72[here](doc/thread_tutorial.md). This tutorial is a perfect place to
73start!
74
75The "[test/examples/](test/examples/)" folder in this repository
76contains many small examples that are useful when learning about
77YCF. YCF's automatic tests use these examples as well. The driver for
78these tests is located in `test/test.sh`.
79
80[This Erlang NIF example](test/examples/sha256_erlang_nif/) shows how
81one can use YCF to write a yielding Erlang NIF library.
82
83
84Command Line Parameters
85-----------------------
86
87```
88Usage: yielding_c_fun [-h]
89 yielding_c_fun [-use_gc [-print_gc_info]]
90 [-log_max_mem_usage log_file]
91 [(( -f | -frec | -fnoauto ) function_name)...
92 [-output_file_name output_file]
93 [-header_file_name header_file]
94 [-debug]
95 [-only_yielding_funs]
96 [-static_aux_funs]
97 input_c_file]]
98```
99
100* `-h`
101
102 Print help text
103
104* `-use_gc`
105
106 Use garbage collection. The garbage collection system assumes that
107 the C call stack consists of a continuous memory block and is
108 therefore not enabled by default even though this assumption is
109 valid on all major platforms. YCF does not reclaim any allocated
110 memory if the `-use_gc` flag is not set.
111
112* `-print_gc_info`
113
114 (For debugging) Print garbage collection information to `stderr`
115
116* `-log_max_mem_usage log_file`
117
118 (For debugging) Print the peak memory usage of the tool to the file
119 `log_file`
120
121* `-fnoauto function_name`
122
123 Generate a yieldable version of the function named
124 function_name. The user can use `YCF_YIELD()`,
125 `YCF_YIELD_NO_REDS()`, and `YCF_CONSUME_REDS(N)` to control
126 when and where the function should yield. See the section titled
127 "Special Statements and Macros" for more information.
128
129* `-f function_name`
130
131 Generate a yieldable version of the function named
132 `function_name`. The generated function automatically decrements the
133 reduction counter by one at the beginning of loop bodies and before
134 goto statements. The function yields automatically if the reduction
135 counter reaches a value that is zero or smaller after it has been
136 decremented.
137
138* `-frec function_name`
139
140 Same as the `-f` option with the exception that the generated function
141 also decrements one reduction before calls to other yieldable
142 functions and before returning. The function yields automatically if
143 the reduction counter reaches a value that is zero or smaller after
144 it has been decremented.
145
146* `-fexternal function_name`
147
148 YCF expects that a yielding version of the function called
149 `function_name` is generated externally. Calls to the function
150 called `function_name` from yielding functions calls the externally
151 generated yielding version of the function called `function_name`.
152
153* `-output_file_name output_file`
154
155 Output the generated code to a file named output_file. The output
156 is printed to standard output if this parameter is unspecified.
157
158* `-header_file_name header_file`
159
160 Generate a header file containing only declarations for the generated
161 functions and write the header file to the file named header_file.
162
163* `-debug`
164
165 Generate debug code that executes when a function yields. The debug
166 code searches the call stack of the yielding functions for pointers
167 to data that is allocated on the call stack. The program crashes
168 with an error message if any such pointer is found.
169
170 The generated debug code depends on that a function called
171 `ycf_debug_get_stack_start()` is declared somewhere in the
172 program. The `ycf_debug_get_stack_start()` functions should return a
173 value of type `void*`. Example:
174
175 static _Thread_local void* ycf_debug_global_stack_start_ptr = NULL;
176 void* ycf_debug_get_stack_start() {
177 return ycf_debug_global_stack_start_ptr;
178 }
179
180 If `ycf_debug_get_stack_start()` returns `NULL`, the value of the
181 `ycf_yield_state` parameter will be used as the start of the stack (it
182 is assumed that the stack grows towards lower addresses). If
183 `ycf_debug_get_stack_start()` returns something different than `NULL`,
184 that value will be used as the start of the stack. To check that
185 nested yielding functions do not have pointers to the call stack,
186 one have to make sure that `ycf_debug_get_stack_start()` returns
187 something different than `NULL` (otherwise, each function will just
188 check for pointers to its own frame). Example:
189
190 ycf_debug_global_stack_start_ptr = &wb;
191 ret = fun_ycf_gen_yielding(&nr_of_reductions,&wb,NULL,allocator,freer,NULL,0,NULL,1);
192 ycf_debug_global_stack_start_ptr = NULL;
193
194* `-only_yielding_funs`
195
196 Print only the generated functions and struct declarations. The
197 default behavior is to insert the generated functions into a copy of
198 the input source file.
199
200* `-static_aux_funs`
201
202 Make the generated auxiliary functions static (i.e., local to the C
203 compilation unit)
204
205* `input_c_file`
206
207 The source file containing the functions that YCF shall create
208 yieldable versions of. YCF does not do any macro expansions. There
209 are several restrictions on the code that YCF can handle that are
210 described in the "Code Restrictions" section below.
211
212Generated Functions
213-------------------
214
215YCF generates three functions for each function name that it is
216given. These functions have the original function name as prefix and
217different suffixes. Descriptions of the functions that YCF generates
218follows below:
219
220
221```c
222
223/* Shall return a pointer to a memory block of size size bytes. */
224typedef void* (*ycf_yield_alloc_type) (size_t size ,void* ctx);
225/* Shall free the memory block which block points to. */
226typedef void (*ycf_yield_free_type) (void* block,void* ctx);
227
228return_type_of_orginal_fun
229original_fun_name_ycf_gen_yielding(
230 long * ycf_nr_of_reductions,
231 void ** ycf_yield_state,
232 void * ycf_extra_context,
233 ycf_yield_alloc_type ycf_yield_alloc,
234 ycf_yield_free_type ycf_yield_free,
235 void * ycf_yield_alloc_free_context,
236 size_t ycf_stack_alloc_size_or_max_size,
237 void* ycf_stack_alloc_data
238 paremeters_of_orginal_function);
239```
240
241The generated function with suffix `_ycf_gen_yielding` initiates the
242call of a yieldable function. Its parameters and return types are
243described below:
244
245* `return_type_of_orginal_fun`
246
247 The return type is the same as the return type of the original
248 function. The return value is the return value of the function if
249 the `_ycf_gen_yielding` function returns without yielding and is
250 uninitialized otherwise.
251
252* `long * ycf_nr_of_reductions`
253
254 (input/output parameter) Gives the yieldable function the number of
255 reductions it can consume before yielding and is also used to write
256 back the number of reductions that are left when the function
257 returns or yields.
258
259* `void ** ycf_yield_state`
260
261 (input/output parameter) Should be a pointer to a pointer to NULL
262 when the `_ycf_gen_yielding` function is called. The value pointed
263 to by ycf_yield_state is NULL when the `_ycf_gen_yielding` function
264 has returned if it did not yield and points to the yield state
265 otherwise.
266
267* `void * ycf_extra_context`
268
269 This parameter is useful if the yieldable function needs to access
270 data that may change when it resumes after having been yielded. The
271 extra context can be accessed from within the yieldable function
272 with the `YCF_GET_EXTRA_CONTEXT()` function.
273
274* `ycf_yield_alloc_type ycf_yield_alloc`
275
276 A memory allocator function that is used by the yieldable function
277 to allocate memory (e.g., to save the state when the function
278 yields).
279
280* `ycf_yield_free ycf_yield_free`
281
282 A memory free function that should free a memory block that has been
283 allocated with ycf_yield_alloc.
284
285* `void * ycf_yield_alloc_free_context`
286
287 A context that is passed as the second argument to `ycf_yield_alloc`
288 and `ycf_yield_free`.
289
290* `size_t ycf_stack_alloc_size_or_max_size`
291
292 The max number of total bytes that can be allocated with the special
293 allocator `YCF_STACK_ALLOC(n)`. This can be set to 0 if
294 `YCF_STACK_ALLOC(n)` is unused. See the documentation of
295 `YCF_STACK_ALLOC(n)` below for more information.
296
297* `void* ycf_stack_alloc_data`
298
299 A pointer to a data block that will be used by
300 `YCF_STACK_ALLOC(n)`. The value of `ycf_stack_alloc_data` should be
301 `NULL` or a pointer to a data block that is least
302 `ycf_stack_alloc_size_or_max_size` bytes large if
303 `YCF_STACK_ALLOC(n)` is used within the yieldable function or any
304 yieldable function that is called by the yieldable function. The
305 `ycf_yield_alloc` and `ycf_yield_free` functions will be used to
306 automatically alloc and free a data block when needed, if
307 `ycf_stack_alloc_data` is set to `NULL`. The value of
308 `ycf_stack_alloc_data` does not matter if `YCF_STACK_ALLOC(n)` is
309 unused.
310
311* `paremeters_of_orginal_function`
312
313 Parameters that the original function takes will be placed in the
314 end of the parameter list of the `ycf_gen_yielding` function.
315
316
317```c
318return_type_of_orginal_fun
319original_fun_name_ycf_gen_continue(
320 long * ycf_nr_of_reduction,
321 void ** ycf_yield_state,
322 void * ycf_extra_context);
323```
324
325The generated function with the suffix `_ycf_gen_continue` is used to
326resume a yielded function. The descriptions of the parameters and
327return type for the `_ycf_gen_yielding` function above are valid for
328the `_ycf_gen_continue` function as well, with the exception that the
329parameter `ycf_yield_state` should point to a pointer to a yield state
330(created in the previous call to `_ycf_gen_yielding` or
331`_ycf_gen_continue`).
332
333```c
334void original_fun_name_ycf_gen_destroy(void * ycf_yield_state);
335```
336
337The `_gen_destroy` function frees the state of a yieldable function
338that has been suspended. This function should only be called when one
339wants to cancel a yielded call before completion. Notice that the
340parameter `ycf_yield_state` points directly to the yield state, unlike
341the parameter of the `_ycf_gen_yielding` and `_ycf_gen_continue`
342functions with the same name. The `_gen_destroy` function
343automatically calls the destroy function for active subcalls to
344yieldable functions.
345
346
347
348The `YCF_YIELD_CODE_GENERATED` Macro
349------------------------------------
350
351YCF also generates code that defines the macro
352`YCF_YIELD_CODE_GENERATED`. This macro may be useful if one wants to
353compile one version of a program with yieldable functions and another
354without yieldable functions.
355
356Special Statements and Macros
357-----------------------------
358
359Some special statements and macros can be used from within a yieldable
360function. Descriptions of those follow below:
361
362* `YCF_YIELD();`
363
364 The `YCF_YIELD();` statement sets the reduction counter to zero
365 and yields the function when it is executed.
366
367* `YCF_YIELD_NO_REDS();`
368
369 The `YCF_YIELD_NO_REDS();` statement yields the function
370 without changing the reduction counter when it is executed.
371
372* `YCF_CONSUME_REDS(N);`
373
374 The `YCF_CONSUME_REDS(N);` statement decrements the
375 reductions counter by N and yields if the reduction counter is less
376 than or equal to zero after the decrement.
377
378* `YCF_STACK_ALLOC(N)`
379
380 The `YCF_STACK_ALLOC(N)` macro uses an allocator that is included in
381 the code generated by YCF to allocate a block with `N +
382 (sizeof(void * ) - (N % sizeof(void*)))` bytes and return a pointer
383 to these bytes. A block that has been allocated with
384 `YCF_STACK_ALLOC(N)` is automatically freed when the function that
385 allocated the block returns. Memory blocks that are allocated with
386 `YCF_STACK_ALLOC(N)` do not move when a yieldable function yields
387 and then resumes again. In contrast, data that is allocated directly
388 on the call stack may move when a function yields and
389 resumes. `YCF_STACK_ALLOC(N)` can thus be useful if one wants to
390 port C code that has variables that point to data that is allocated
391 on the call stack. The parameters `ycf_stack_alloc_size_or_max_size`
392 and `ycf_stack_alloc_data` of the `_ycf_gen_yielding` function need
393 to be set correctly if `YCF_STACK_ALLOC(N)` is used. Please see the
394 description of the `_ycf_gen_yielding` function in the "Generated
395 Functions" section above for details about those parameters. Notice
396 also that the `-debug` flag that is described in the "Command Line
397 Parameters" section above can be useful when one wants to find out
398 if a function points to data that is allocated on the call stack of
399 a yieldable function.
400
401* `YCF_GET_EXTRA_CONTEXT()`
402
403 The `YCF_GET_EXTRA_CONTEXT()` macro returns the value of the
404 `ycf_extra_context` parameter that was passed to the latest call of
405 one of the corresponding `_ycf_gen_yielding` or `_ycf_gen_continue`
406 functions. See the "Generated Functions" section above for
407 information about the parameters of `_ycf_gen_yielding` and
408 `_ycf_gen_continue` functions.
409
410* `YCF_NR_OF_REDS_LEFT()`
411
412 The `YCF_NR_OF_REDS_LEFT()` macro returns the current value of
413 the reduction counter (a value of type `long`).
414
415* `YCF_SET_NR_OF_REDS_LEFT(NEW_NR_OF_REDS_LEFT)`
416
417 The `YCF_SET_NR_OF_REDS_LEFT(NEW_NR_OF_REDS_LEFT)` macro sets
418 the value that the reduction counter (which stores a value of type
419 `long`) to `NEW_NR_OF_REDS_LEFT`.
420
421* `YCF_MAX_NR_OF_REDS`
422
423 The `YCF_MAX_NR_OF_REDS` macro returns the maximum value that the
424 reduction counter may have.
425
426Code Restrictions
427-----------------
428
429YCF cannot parse all valid C code. The code restrictions that
430yieldable functions need to follow are described below. It is
431recommended to check that the generated code is correct.
432
433* **Declarations**
434
435 Variable declarations and parameters of yieldable functions need to
436 be in the following form:
437
438 ```
439 "(optional) type descriptor (i.e., struct, union or enum)"
440
441 "type name"
442
443 "(optional) one or more star characters (i.e., *)"
444
445 "variable name"
446
447 "(optional) one or more square brackets with a number inside (e.g, [3])"
448
449 "(optional) one or more empty square brackets (e.g, [])"
450
451 "(optional) equal sign followed by an expression (automatic array
452 initialization and struct initialization of the form
453 {.filed_name=value...} are not allowed)"
454
455 "semicolon"
456 ```
457
458 Here are some examples of declarations that are **correct**:
459
460 ```c
461 int var1;
462 int var2 = 1;
463 int var3 = var2 + 1;
464 int var4 = function(var3);
465 int * var5 = malloc(sizeof(int*));
466 int ** var6 = malloc(sizeof(int*)*10);
467 int ***** var7;
468 struct struct_name var8;
469 struct struct_name var9 = function2();
470 double var10[128];
471 double var11[128][];
472 double * var12[128];
473 ```
474
475 Here are examples of declarations that are **incorrect**:
476
477 ```c
478 int var1, var2;
479 int var1 = 1, var2 = 10;
480 void (*printer_t)(int);
481 ```
482
483 Note that one has to use a `typedef` to be able to declare a
484 function pointer variable.
485
486* **Pointers**
487
488 Pointers to call-stack-allocated data are not allowed. The
489 `YCF_YIELD_ALLOC(N)` function, which is described in the "Special
490 Statements and Macros" section above, can be used to work around
491 this limitation. The `-debug` flag that is described in the "Command
492 Line Parameters" section above, can be useful when one wants to find
493 out if a yieldable function points to call-stack-allocated data.
494
495
496* **Macros**
497
498 YCF does not expand macros so macros in functions that YCF
499 transforms should not "hide" variables or any other code that is
500 relevant for yielding.
501
502* **Calls to a Yieldable Function from Another Yieldable Function**
503
504 Calls to a yieldable function from another yieldable function need
505 to be in a form that YCF recognizes. Such calls need to be in one of
506 the following forms:
507
508 * As a separate statement:
509
510 Examples:
511 ```c
512 my_fun(my_param_expression + 1, 10);
513 my_fun2();
514 ```
515
516 * A separate assignment statement to a variable. The function call
517 expression may be negated but is not allowed to be nested in other
518 types of expressions.
519
520 Examples of **correct** ways of calling yieldable functions:
521 ```c
522 int var_name_1 = my_fun();
523 int var_name_2 = !my_fun();
524 var_name_3 = my_fun();
525 var_name_4 = !my_fun();
526 ```
527
528 Examples of **incorrect** ways of calling yieldable functions:
529 ```c
530 int var_name_1 = (my_fun());
531 var_name_2 = 1 + my_fun();
532 t->name = my_fun();
533 *ptr = my_fun();
534 ```
535
536 * As the expression of `while`-statements, `do-while`-statements or
537 'if`-statements:
538
539 Examples of **correct** ways of calling yieldable functions:
540 ```c
541 if(my_fun()) printf("hej\n");
542 if(0) else if(my_fun()) printf("hej\n");
543 while(!my_fun()) printf("hej\n");
544 do { printf("hej\n"); } while(my_fun());
545 var_name_3 = my_fun();
546 var_name_4 = !my_fun();
547 ```
548
549 Examples of **incorrect** ways of calling yieldable functions:
550 ```
551 if(3+my_fun()) printf("hej\n");
552 if(hej=my_fun()) printf("hej\n");
553 ```
554
555 YCF prints a message to standard error and exits with an error
556 code if it finds a call to a yieldable function that it cannot
557 transform.
558
559Hooks
560-----
561
562It is possible to insert special hooks in yieldable functions. Hooks
563execute when certain events are happening. Hooks may read and write to
564variables (changes to variables are visible after the code block has
565executed). Hooks can be placed anywhere one can place a normal
566statement within the function body. There are two ways to write hooks:
567
568**Hook Style 1:**
569
570```c
571 YCF_SPECIAL_CODE_START(ON_EVENT_NAME);
572 printf("This will be printed when EVENT_NAME is happening\n");
573 YCF_SPECIAL_CODE_END();
574```
575
576**Hook Style 2:**
577
578```c
579 /*special_code_start:ON_EVENT_NAME*/
580 if(0){
581 printf("This will be printed when EVENT_NAME is happening\n");
582 }
583 /*special_code_end*/
584```
585
586The following hook events are currently available:
587
588* `ON_SAVE_YIELD_STATE`
589
590 Triggered when the function yields.
591
592* `ON_RESTORE_YIELD_STATE`
593
594 Triggered before a function resumes after a yield.
595
596* `ON_DESTROY_STATE`
597
598 Triggered if and when the corresponding `_ycf_gen_destroy` function
599 is executing.
600
601* `ON_DESTROY_STATE_OR_RETURN`
602
603 Triggered if and when the corresponding `_ycf_gen_destroy` function
604 for the function is executing or when the function is returning.
605
606* `ON_RETURN`
607
608 Triggered when the function is returning.
609
610License
611-------
612
613Yielding C Fun is released under the [Apache License
6142.0](http://www.apache.org/licenses/LICENSE-2.0).
615
616
617> Copyright Ericsson AB and Kjell Winblad 2019. All Rights Reserved.
618>
619> Licensed under the Apache License, Version 2.0 (the "License");
620> you may not use this file except in compliance with the License.
621> You may obtain a copy of the License at
622>
623> http://www.apache.org/licenses/LICENSE-2.0
624>
625> Unless required by applicable law or agreed to in writing, software
626> distributed under the License is distributed on an "AS IS" BASIS,
627> WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
628> See the License for the specific language governing permissions and
629> limitations under the License.
630
631
632
633[1]: http://swtch.com/libtask/ "libtask"
634[2]: http://xmailserver.org/libpcl.html
635[3]: https://web.archive.org/web/20060110123338/http://www.goron.de/~froese/coro/
636[4]: https://github.com/halayli/lthread
637[5]: http://dekorte.com/projects/opensource/libcoroutine/
638[6]: http://code.google.com/p/libconcurrency/libconcurrency
639[7]: http://software.schmorp.de/pkg/libcoro.html
640[8]: https://github.com/Adaptv/ribs2
641[9]: http://libdill.org/
642[10]: https://github.com/hnes/libaco
643[11]: https://byuu.org/library/libco/
644[12]: http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html
645[13]: https://github.com/jsseldenthuis/coroutine
646