Yielding C Fun

Introduction

Yielding C Fun (YCF) is a tool that transforms functions written in a subset of the C programming language so that they become yieldable. A yieldable function can be suspended/yielded/paused/trapped (either automatically or where the user has inserted a particular statement) and then be resumed at a later point. Yileldable functions are also called coroutines.

Difference Between Yielding C Fun and Coroutine Libraries

Several libraries implement coroutine support for the C programming language (e.g., [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]). These libraries either rely on platform-specific code or do not save call stack variables. Yielding C Fun (YCF) does not have any of these two limitations. YCF can accomplish this as it is a source-to-source transformation tool and not only a library.

YCF has been created to make it easier to implement yielding Erlang NIFs and BIFs (i.e., Erlang functions that are written in C). Below are examples of YCF features that are useful when implementing yielding Erlang NIFs and BIFs:

• YCF automatically generates a destroy function for each yieldable function. The destroy function frees resources that are used by a suspended function. The destroy function is useful when a suspended function needs to abort (e.g., when the Erlang process that invoked the function has died).

• YCF can automatically insert code that yields functions after a user specifiable number of loop iterations and goto statements.

• YCF has a hook system that lets the user insert code that is triggered when certain events happen (e.g., when a function yields).

The main limitations of YCF are that it cannot handle all valid C code and that it cannot make library functions without source code yieldable. Pointers to stack-allocated data are also not allowed (YCF has a memory allocation function called YCF_STACK_ALLOC to work around this issue).

Requirements

• A C99 compatible C compiler
• make (optional but useful for building)

Compile and Test

Build the executable $YCF_ROOT/bin/yielding_c_fun.bin:

make

Build the executable and run all tests:

make test

Getting Started

A brief introduction tutorial can be found here. This tutorial is a perfect place to start!

The "test/examples/" folder in this repository contains many small examples that are useful when learning about YCF. YCF's automatic tests use these examples as well. The driver for these tests is located in test/test.sh.

This Erlang NIF example shows how one can use YCF to write a yielding Erlang NIF library.

Command Line Parameters

Usage: yielding_c_fun [-h]
       yielding_c_fun [-use_gc [-print_gc_info]]
                      [-log_max_mem_usage log_file]
                      [(( -f | -frec | -fnoauto ) function_name)...
                       [-output_file_name output_file]
                       [-header_file_name header_file]
                       [-debug]
                       [-only_yielding_funs]
                       [-static_aux_funs]
                       input_c_file]]

• -h

  Print help text

• -use_gc

  Use garbage collection. The garbage collection system assumes that the C call stack consists of a continuous memory block and is therefore not enabled by default even though this assumption is valid on all major platforms. YCF does not reclaim any allocated memory if the -use_gc flag is not set.

• -print_gc_info

  (For debugging) Print garbage collection information to stderr

• -log_max_mem_usage log_file

  (For debugging) Print the peak memory usage of the tool to the file log_file

• -fnoauto function_name

  Generate a yieldable version of the function named function_name. The user can use YCF_YIELD(), YCF_YIELD_NO_REDS(), and YCF_CONSUME_REDS(N) to control when and where the function should yield. See the section titled "Special Statements and Macros" for more information.

• -f function_name

  Generate a yieldable version of the function named function_name. The generated function automatically decrements the reduction counter by one at the beginning of loop bodies and before goto statements. The function yields automatically if the reduction counter reaches a value that is zero or smaller after it has been decremented.

• -frec function_name

  Same as the -f option with the exception that the generated function also decrements one reduction before calls to other yieldable functions and before returning. The function yields automatically if the reduction counter reaches a value that is zero or smaller after it has been decremented.

• -fexternal function_name

  YCF expects that a yielding version of the function called function_name is generated externally. Calls to the function called function_name from yielding functions calls the externally generated yielding version of the function called function_name.

• -output_file_name output_file

  Output the generated code to a file named output_file. The output is printed to standard output if this parameter is unspecified.

• -header_file_name header_file

  Generate a header file containing only declarations for the generated functions and write the header file to the file named header_file.

• -debug

  Generate debug code that executes when a function yields. The debug code searches the call stack of the yielding functions for pointers to data that is allocated on the call stack. The program crashes with an error message if any such pointer is found.

  The generated debug code depends on that a function called ycf_debug_get_stack_start() is declared somewhere in the program. The ycf_debug_get_stack_start() functions should return a value of type void*. Example:

      static _Thread_local void* ycf_debug_global_stack_start_ptr = NULL;
      void* ycf_debug_get_stack_start() {
          return ycf_debug_global_stack_start_ptr;
      }
  

  If ycf_debug_get_stack_start() returns NULL, the value of the ycf_yield_state parameter will be used as the start of the stack (it is assumed that the stack grows towards lower addresses). If ycf_debug_get_stack_start() returns something different than NULL, that value will be used as the start of the stack. To check that nested yielding functions do not have pointers to the call stack, one have to make sure that ycf_debug_get_stack_start() returns something different than NULL (otherwise, each function will just check for pointers to its own frame). Example:

      ycf_debug_global_stack_start_ptr = &wb;
      ret = fun_ycf_gen_yielding(&nr_of_reductions,&wb,NULL,allocator,freer,NULL,0,NULL,1);
      ycf_debug_global_stack_start_ptr = NULL;
  

• -only_yielding_funs

  Print only the generated functions and struct declarations. The default behavior is to insert the generated functions into a copy of the input source file.

• -static_aux_funs

  Make the generated auxiliary functions static (i.e., local to the C compilation unit)

• input_c_file

  The source file containing the functions that YCF shall create yieldable versions of. YCF does not do any macro expansions. There are several restrictions on the code that YCF can handle that are described in the "Code Restrictions" section below.

Generated Functions

YCF generates three functions for each function name that it is given. These functions have the original function name as prefix and different suffixes. Descriptions of the functions that YCF generates follows below:

/* Shall return a pointer to a memory block of size size bytes. */
typedef void* (*ycf_yield_alloc_type) (size_t size ,void* ctx);
/* Shall free the memory block which block points to. */
typedef void (*ycf_yield_free_type) (void* block,void* ctx);

return_type_of_orginal_fun
original_fun_name_ycf_gen_yielding(
               long * ycf_nr_of_reductions,
               void ** ycf_yield_state,
               void * ycf_extra_context,
               ycf_yield_alloc_type ycf_yield_alloc,
               ycf_yield_free_type ycf_yield_free,
               void * ycf_yield_alloc_free_context,
               size_t ycf_stack_alloc_size_or_max_size,
               void* ycf_stack_alloc_data
               paremeters_of_orginal_function);

The generated function with suffix _ycf_gen_yielding initiates the call of a yieldable function. Its parameters and return types are described below:

• return_type_of_orginal_fun

  The return type is the same as the return type of the original function. The return value is the return value of the function if the _ycf_gen_yielding function returns without yielding and is uninitialized otherwise.

• long * ycf_nr_of_reductions

  (input/output parameter) Gives the yieldable function the number of reductions it can consume before yielding and is also used to write back the number of reductions that are left when the function returns or yields.

• void ** ycf_yield_state

  (input/output parameter) Should be a pointer to a pointer to NULL when the _ycf_gen_yielding function is called. The value pointed to by ycf_yield_state is NULL when the _ycf_gen_yielding function has returned if it did not yield and points to the yield state otherwise.

• void * ycf_extra_context

  This parameter is useful if the yieldable function needs to access data that may change when it resumes after having been yielded. The extra context can be accessed from within the yieldable function with the YCF_GET_EXTRA_CONTEXT() function.

• ycf_yield_alloc_type ycf_yield_alloc

  A memory allocator function that is used by the yieldable function to allocate memory (e.g., to save the state when the function yields).

• ycf_yield_free ycf_yield_free

  A memory free function that should free a memory block that has been allocated with ycf_yield_alloc.

• void * ycf_yield_alloc_free_context

  A context that is passed as the second argument to ycf_yield_alloc and ycf_yield_free.

• size_t ycf_stack_alloc_size_or_max_size

  The max number of total bytes that can be allocated with the special allocator YCF_STACK_ALLOC(n). This can be set to 0 if YCF_STACK_ALLOC(n) is unused. See the documentation of YCF_STACK_ALLOC(n) below for more information.

• void* ycf_stack_alloc_data

  A pointer to a data block that will be used by YCF_STACK_ALLOC(n). The value of ycf_stack_alloc_data should be NULL or a pointer to a data block that is least ycf_stack_alloc_size_or_max_size bytes large if YCF_STACK_ALLOC(n) is used within the yieldable function or any yieldable function that is called by the yieldable function. The ycf_yield_alloc and ycf_yield_free functions will be used to automatically alloc and free a data block when needed, if ycf_stack_alloc_data is set to NULL. The value of ycf_stack_alloc_data does not matter if YCF_STACK_ALLOC(n) is unused.

• paremeters_of_orginal_function

  Parameters that the original function takes will be placed in the end of the parameter list of the ycf_gen_yielding function.

return_type_of_orginal_fun
original_fun_name_ycf_gen_continue(
                     long * ycf_nr_of_reduction,
                     void ** ycf_yield_state,
                     void * ycf_extra_context);

The generated function with the suffix _ycf_gen_continue is used to resume a yielded function. The descriptions of the parameters and return type for the _ycf_gen_yielding function above are valid for the _ycf_gen_continue function as well, with the exception that the parameter ycf_yield_state should point to a pointer to a yield state (created in the previous call to _ycf_gen_yielding or _ycf_gen_continue).

void original_fun_name_ycf_gen_destroy(void * ycf_yield_state);

The _gen_destroy function frees the state of a yieldable function that has been suspended. This function should only be called when one wants to cancel a yielded call before completion. Notice that the parameter ycf_yield_state points directly to the yield state, unlike the parameter of the _ycf_gen_yielding and _ycf_gen_continue functions with the same name. The _gen_destroy function automatically calls the destroy function for active subcalls to yieldable functions.

The YCF_YIELD_CODE_GENERATED Macro

YCF also generates code that defines the macro YCF_YIELD_CODE_GENERATED. This macro may be useful if one wants to compile one version of a program with yieldable functions and another without yieldable functions.

Special Statements and Macros

Some special statements and macros can be used from within a yieldable function. Descriptions of those follow below:

• YCF_YIELD();

  The YCF_YIELD(); statement sets the reduction counter to zero and yields the function when it is executed.

• YCF_YIELD_NO_REDS();

  The YCF_YIELD_NO_REDS(); statement yields the function without changing the reduction counter when it is executed.

• YCF_CONSUME_REDS(N);

  The YCF_CONSUME_REDS(N); statement decrements the reductions counter by N and yields if the reduction counter is less than or equal to zero after the decrement.

• YCF_STACK_ALLOC(N)

  The YCF_STACK_ALLOC(N) macro uses an allocator that is included in the code generated by YCF to allocate a block with N + (sizeof(void * ) - (N % sizeof(void*))) bytes and return a pointer to these bytes. A block that has been allocated with YCF_STACK_ALLOC(N) is automatically freed when the function that allocated the block returns. Memory blocks that are allocated with YCF_STACK_ALLOC(N) do not move when a yieldable function yields and then resumes again. In contrast, data that is allocated directly on the call stack may move when a function yields and resumes. YCF_STACK_ALLOC(N) can thus be useful if one wants to port C code that has variables that point to data that is allocated on the call stack. The parameters ycf_stack_alloc_size_or_max_size and ycf_stack_alloc_data of the _ycf_gen_yielding function need to be set correctly if YCF_STACK_ALLOC(N) is used. Please see the description of the _ycf_gen_yielding function in the "Generated Functions" section above for details about those parameters. Notice also that the -debug flag that is described in the "Command Line Parameters" section above can be useful when one wants to find out if a function points to data that is allocated on the call stack of a yieldable function.

• YCF_GET_EXTRA_CONTEXT()

  The YCF_GET_EXTRA_CONTEXT() macro returns the value of the ycf_extra_context parameter that was passed to the latest call of one of the corresponding _ycf_gen_yielding or _ycf_gen_continue functions. See the "Generated Functions" section above for information about the parameters of _ycf_gen_yielding and _ycf_gen_continue functions.

• YCF_NR_OF_REDS_LEFT()

  The YCF_NR_OF_REDS_LEFT() macro returns the current value of the reduction counter (a value of type long).

• YCF_SET_NR_OF_REDS_LEFT(NEW_NR_OF_REDS_LEFT)

  The YCF_SET_NR_OF_REDS_LEFT(NEW_NR_OF_REDS_LEFT) macro sets the value that the reduction counter (which stores a value of type long) to NEW_NR_OF_REDS_LEFT.

• YCF_MAX_NR_OF_REDS

  The YCF_MAX_NR_OF_REDS macro returns the maximum value that the reduction counter may have.

Code Restrictions

YCF cannot parse all valid C code. The code restrictions that yieldable functions need to follow are described below. It is recommended to check that the generated code is correct.

• Declarations

  Variable declarations and parameters of yieldable functions need to be in the following form:

  "(optional) type descriptor (i.e., struct, union or enum)"
  
  "type name"
  
  "(optional) one or more star characters (i.e., *)"
  
  "variable name"
  
  "(optional) one or more square brackets with a number inside (e.g, [3])"
  
  "(optional) one or more empty square brackets (e.g, [])"
  
  "(optional) equal sign followed by an expression (automatic array
  initialization and struct initialization of the form
  {.filed_name=value...} are not allowed)"
  
  "semicolon"
  

  Here are some examples of declarations that are correct:

  int var1;
  int var2 = 1;
  int var3 = var2 + 1;
  int var4 = function(var3);
  int * var5 = malloc(sizeof(int*));
  int ** var6 = malloc(sizeof(int*)*10);
  int ***** var7;
  struct struct_name var8;
  struct struct_name var9 = function2();
  double var10[128];
  double var11[128][];
  double * var12[128];

  Here are examples of declarations that are incorrect:

  int var1, var2;
  int var1 = 1, var2 = 10;
  void (*printer_t)(int);

  Note that one has to use a typedef to be able to declare a function pointer variable.

• Pointers

  Pointers to call-stack-allocated data are not allowed. The YCF_YIELD_ALLOC(N) function, which is described in the "Special Statements and Macros" section above, can be used to work around this limitation. The -debug flag that is described in the "Command Line Parameters" section above, can be useful when one wants to find out if a yieldable function points to call-stack-allocated data.

• Macros

  YCF does not expand macros so macros in functions that YCF transforms should not "hide" variables or any other code that is relevant for yielding.

• Calls to a Yieldable Function from Another Yieldable Function

  Calls to a yieldable function from another yieldable function need to be in a form that YCF recognizes. Such calls need to be in one of the following forms:

  • As a separate statement:

    Examples:

    my_fun(my_param_expression + 1, 10);
    my_fun2();

  • A separate assignment statement to a variable. The function call expression may be negated but is not allowed to be nested in other types of expressions.

    Examples of correct ways of calling yieldable functions:

    int var_name_1 = my_fun();
    int var_name_2 = !my_fun();
    var_name_3 = my_fun();
    var_name_4 = !my_fun();

    Examples of incorrect ways of calling yieldable functions:

    int var_name_1 = (my_fun());
    var_name_2 = 1 + my_fun();
    t->name = my_fun();
    *ptr = my_fun();

  • As the expression of while-statements, do-while-statements or 'if`-statements:

    Examples of correct ways of calling yieldable functions:

    if(my_fun()) printf("hej\n");
    if(0) else if(my_fun()) printf("hej\n");
    while(!my_fun()) printf("hej\n");
    do { printf("hej\n"); } while(my_fun());
    var_name_3 = my_fun();
    var_name_4 = !my_fun();

    Examples of incorrect ways of calling yieldable functions:

    if(3+my_fun()) printf("hej\n");
    if(hej=my_fun()) printf("hej\n");
    

    YCF prints a message to standard error and exits with an error code if it finds a call to a yieldable function that it cannot transform.

Hooks

It is possible to insert special hooks in yieldable functions. Hooks execute when certain events are happening. Hooks may read and write to variables (changes to variables are visible after the code block has executed). Hooks can be placed anywhere one can place a normal statement within the function body. There are two ways to write hooks:

Hook Style 1:

  YCF_SPECIAL_CODE_START(ON_EVENT_NAME);
  printf("This will be printed when EVENT_NAME is happening\n");
  YCF_SPECIAL_CODE_END();

Hook Style 2:

  /*special_code_start:ON_EVENT_NAME*/
  if(0){
    printf("This will be printed when EVENT_NAME is happening\n");
  }
  /*special_code_end*/

The following hook events are currently available:

• ON_SAVE_YIELD_STATE

  Triggered when the function yields.

• ON_RESTORE_YIELD_STATE

  Triggered before a function resumes after a yield.

• ON_DESTROY_STATE

  Triggered if and when the corresponding _ycf_gen_destroy function is executing.

• ON_DESTROY_STATE_OR_RETURN

  Triggered if and when the corresponding _ycf_gen_destroy function for the function is executing or when the function is returning.

• ON_RETURN

  Triggered when the function is returning.

License

Yielding C Fun is released under the Apache License 2.0.

Copyright Ericsson AB and Kjell Winblad 2019. All Rights Reserved.

Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except in compliance with the License. You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software distributed under the License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the License for the specific language governing permissions and limitations under the License.