- Generated by
1.9.1
|
ssm
0.0.2
Runtime Library for the Sparse Synchronous Model
|
The SSM runtime supports closures, a runtime representation for functions. These encapsulate a function pointer (specifically, an enter function pointer) and a vector of partially-applied arguments (referred to as argv).
When closures are applied to arguments, they may or may not reduce. When a reduction takes place, a child process is created: the enter function pointer is applied to argv, and the resulting activation record is scheduled via ssm_activate(). If this happens, the caller must yield (i.e., set the program counter and return) so that the child process may run to completion before the caller resumes.
It might be possible to statically determine whether a caller needs to yield, so in the general case, the caller should yield conditionally, using ssm_has_children() to determine whether any reduction took place. Optimizations may eliminate this check.
Closures are allocated with enough space for all eventual arguments to be stored in argv, which is in turn passed to the callee. Though this wastes extra space, it vastly increases opportunities to reuse the same closure (if it is uniquely owned by the caller).
Closures' ssm_mm headers are vector-flavored; the cap field indicates how many arguments the closure is allocated with (i.e., how many can be applied to it), while the count field indicates how many arguments are currently applied. cap is used to determine the size, while count is used to determine how many valid values the garbage collector needs to scan when a closure is deallocated.
The "template" for each closure's memory layout is defined by ssm_closure1; closures with more argument capacity look like ssm_closure1 with a longer argv.
The function ssm_closure_apply() applies a closure to an argument, with or without reduction. The SSM runtime library defines many helper interfaces to allow compilers to generate optimized code for interacting with closures. For example, ssm_closure_push() and ssm_closure_pop() directly add and remove arguments to argv without any runtime checks or function call overhead. ssm_closure_apply() is implemented in terms of these helpers, and should be inlined by an optimizing code generator where appropriate.
Meanwhile, ssm_closure_apply_final() optimizes the last time a closure value is used. It assumes that the caller is releasing the last remaining reference to a closure, so that the closure may be safely modified in-place.
When process a applies function f to argument x, and saves the result to r, the most general case (omitting reference-counting) looks like:
where N is the running program counter.
For convenience, _auto variants of ssm_closure_apply() and ssm_closure_apply_final() call ssm_dup() on the argument.
Data Structures | |
| struct | ssm_closure1 |
| The struct template of a heap-allocated closure object. More... | |
Macros | |
| #define | ssm_closure_arg_count(v) (container_of((v).heap_ptr, struct ssm_closure1, mm)->mm.info.vector.count) |
| Obtain the number of argument values owned by a closure. More... | |
| #define | ssm_closure_arg_cap(v) (container_of((v).heap_ptr, struct ssm_closure1, mm)->mm.info.vector.cap) |
| Obtain the number of argument values accommodated by a closure. More... | |
| #define | ssm_closure_func(v) (container_of((v).heap_ptr, struct ssm_closure1, mm)->f) |
| Obtain the enter function pointer of a closure. More... | |
| #define | ssm_closure_argv(v) (&*container_of((v).heap_ptr, struct ssm_closure1, mm)->argv) |
| Retrieve the argument array of a closure. More... | |
| #define | ssm_closure_arg(v, i) ssm_closure_argv(v)[i] |
| Obtain the ith argument of a closure. More... | |
| #define | ssm_closure_size(val_count) (sizeof(struct ssm_closure1) + (sizeof(ssm_value_t) * ((val_count)-1))) |
| Compute the size of a closure object. More... | |
| #define | ssm_closure_heap_size(v) ssm_closure_size(ssm_closure_arg_cap(v)) |
| Compute the size of a closure already allocated on the heap. More... | |
| #define | ssm_closure_push(closure, arg) |
| Add an argument to a closure. More... | |
| #define | ssm_closure_pop(closure) |
| Remove an argument from a closure. More... | |
| #define | ssm_closure_activate(closure, parent, prio, depth, ret) |
| Spawn and schedule a new child process from a fully-applied closure. More... | |
| #define | ssm_new_closure(f, args) |
| #define | ssm_closure_apply_auto(closure, arg, parent, prio, depth, ret) |
| Closure application with automatic memory management. More... | |
| #define | ssm_closure_apply_final_auto(closure, arg, parent, prio, depth, ret) |
| In-place closure application with automatic memory management. More... | |
| #define | ssm_closure_free(closure) |
| Helper to free a closure (without reference counting). More... | |
Typedefs | |
| typedef ssm_act_t *(* | ssm_func_t) (ssm_act_t *parent, ssm_priority_t prio, ssm_depth_t depth, ssm_value_t *argv, ssm_value_t *ret) |
| The type signature for all SSM enter functions. More... | |
Functions | |
| ssm_value_t | ssm_new_closure_int (ssm_func_t f, uint8_t arg_cap) |
| Allocate a closure on the heap. More... | |
| ssm_value_t | ssm_closure_clone (ssm_value_t closure) |
| Create a copy of a closure. More... | |
| void | ssm_closure_apply (ssm_value_t closure, ssm_value_t arg, ssm_act_t *parent, ssm_priority_t prio, ssm_depth_t depth, ssm_value_t *ret) |
| Apply an argument to a closure. More... | |
| void | ssm_closure_apply_final (ssm_value_t closure, ssm_value_t arg, ssm_act_t *parent, ssm_priority_t prio, ssm_depth_t depth, ssm_value_t *ret) |
| Apply an argument to a closure that is used for the last time. More... | |
| #define ssm_closure_arg_count | ( | v | ) | (container_of((v).heap_ptr, struct ssm_closure1, mm)->mm.info.vector.count) |
| #define ssm_closure_arg_cap | ( | v | ) | (container_of((v).heap_ptr, struct ssm_closure1, mm)->mm.info.vector.cap) |
| #define ssm_closure_func | ( | v | ) | (container_of((v).heap_ptr, struct ssm_closure1, mm)->f) |
| #define ssm_closure_argv | ( | v | ) | (&*container_of((v).heap_ptr, struct ssm_closure1, mm)->argv) |
| #define ssm_closure_arg | ( | v, | |
| i | |||
| ) | ssm_closure_argv(v)[i] |
| #define ssm_closure_size | ( | val_count | ) | (sizeof(struct ssm_closure1) + (sizeof(ssm_value_t) * ((val_count)-1))) |
| #define ssm_closure_heap_size | ( | v | ) | ssm_closure_size(ssm_closure_arg_cap(v)) |
| #define ssm_closure_push | ( | closure, | |
| arg | |||
| ) |
Add an argument to a closure.
Note that this helper increments the arg_count of closure but does not perform memory management, i.e., does not ssm_dup() arg. It also does not check whether closure has capacity for arg.
| #define ssm_closure_pop | ( | closure | ) |
Remove an argument from a closure.
Note that this helper decrements the arg_count of closure but does not perform memory management, i.e., does not ssm_drop() arg. It also does not check whether closure has a non-zero number of arguments already applied.
| #define ssm_closure_activate | ( | closure, | |
| parent, | |||
| prio, | |||
| depth, | |||
| ret | |||
| ) |
Spawn and schedule a new child process from a fully-applied closure.
Note that this helper does not perform any memory management, nor does it ensure that closure has all arguments applied.
| #define ssm_new_closure | ( | f, | |
| args | |||
| ) |
| #define ssm_closure_apply_auto | ( | closure, | |
| arg, | |||
| parent, | |||
| prio, | |||
| depth, | |||
| ret | |||
| ) |
Closure application with automatic memory management.
ssm_dup() is called on a before f is applied to it; see ssm_closure_apply().
| closure | the closure to be applied. |
| arg | the argument closure is applied to. |
| parent | the current process performing the application. |
| prio | priority of the current process. |
| depth | depth of the current process. |
| ret | pointer to the return value. |
| #define ssm_closure_apply_final_auto | ( | closure, | |
| arg, | |||
| parent, | |||
| prio, | |||
| depth, | |||
| ret | |||
| ) |
In-place closure application with automatic memory management.
ssm_dup() is called on a before f is applied to it; see ssm_closure_apply_final().
| closure | the closure to be applied. |
| arg | the argument closure is applied to. |
| parent | the current process performing the application. |
| prio | priority of the current process. |
| depth | depth of the current process. |
| ret | pointer to the return value. |
| #define ssm_closure_free | ( | closure | ) |
Helper to free a closure (without reference counting).
| typedef ssm_act_t*(* ssm_func_t) (ssm_act_t *parent, ssm_priority_t prio, ssm_depth_t depth, ssm_value_t *argv, ssm_value_t *ret) |
The type signature for all SSM enter functions.
This type standardizes the "calling convention" of SSM functions, so that they can be stored in generic closures and treated uniformly.
| parent | the activation record of the caller. |
| prio | the priority of the callee. |
| depth | the depth of the callee. |
| argv | an array of ssm_value_t arguments given to the callee. |
| ret | the return value address that the callee should write to. |
| ssm_value_t ssm_new_closure_int | ( | ssm_func_t | f, |
| uint8_t | arg_cap | ||
| ) |
| ssm_value_t ssm_closure_clone | ( | ssm_value_t | closure | ) |
Create a copy of a closure.
| closure | the closure to be copied. |
Definition at line 12 of file ssm-closure.c.
| void ssm_closure_apply | ( | ssm_value_t | closure, |
| ssm_value_t | arg, | ||
| ssm_act_t * | parent, | ||
| ssm_priority_t | prio, | ||
| ssm_depth_t | depth, | ||
| ssm_value_t * | ret | ||
| ) |
Apply an argument to a closure.
The behavior depends on whether closure needs to be activated after being applied to arg, i.e., whether all of its arguments have arrived.
If closure is activated, a child process will be scheduled, so the caller must yield to the scheduler to allow the child process to run. The child process will write its return value to ret.
If closure is not activated, a copy of it (via ssm_closure_clone()) with arg pushed to its argv will be written to ret.
In both cases, all values in closure's argv will have ssm_dup() called on them, since application will result in those values being shared in a new context, either from a child process or from the cloned closure. Note that ssm_dup() is not called on arg; to do so automatically, use ssm_closure_apply_auto().
| closure | the closure to be applied. |
| arg | the argument closure is applied to. |
| parent | the current process performing the application. |
| prio | priority of the current process. |
| depth | depth of the current process. |
| ret | pointer to the return value. |
Definition at line 25 of file ssm-closure.c.
| void ssm_closure_apply_final | ( | ssm_value_t | closure, |
| ssm_value_t | arg, | ||
| ssm_act_t * | parent, | ||
| ssm_priority_t | prio, | ||
| ssm_depth_t | depth, | ||
| ssm_value_t * | ret | ||
| ) |
Apply an argument to a closure that is used for the last time.
An optimized version of ssm_closure_apply(), to be used only provided:
This implementation should be used as the fast path when those conditions hold; it improves upon the more general ssm_closure_apply() by using closure in-place, and avoiding unnecessary ssm_dup() and ssm_drop() called. After this is called, closure will not need to be dropped.
The behavior of this function is equivalent to:
Like ssm_closure_apply(), this function does not ssm_drop() arg; to do so automatically, use ssm_closure_apply_final_auto().
| closure | the closure to be applied. |
| arg | the argument closure is applied to. |
| parent | the current process performing the application. |
| prio | priority of the current process. |
| depth | depth of the current process. |
| ret | pointer to the return value. |
Definition at line 43 of file ssm-closure.c.
1.9.1