PoprC Runtime Operation Part 2: Memory Management
Memory management in the PoprC runtime is done using a custom allocator, based on a ring of cells. It’s fairly simple, but it works, and I’m not yet to the point where it needs to be optimized. Memory allocation must be handled carefully, because I want PoprC to be able to produce code suitable for embedded devices, which have very little memory, and need real-time guarantees.
The runtime’s garbage collection is based on reference counting to minimize memory usage, to avoid unpredictable pauses, and also because it’s simple. In addition, the reference count can be used to determine when it is okay to modify a closure, rather than making a modified copy. This is an effective optimization because most closures only have a single reference.
At startup, all cells are added to a free ring by cells_init().
void cells_init() {
int i;
const unsigned int n = LENGTH(cells)-1;
// zero the cells
memset(&cells, 0, sizeof(cells));
memset(&alt_live, 0, sizeof(alt_live));
// set up doubly-linked pointer ring
for(i = 0; i < n; i++) {
cells[i].prev = &cells[i-1];
cells[i].next = &cells[i+1];
}
cells[0].prev = &cells[n-1];
cells[n-1].next = &cells[0];
cells_ptr = &cells[0];
alt_cnt = 0;
}cells_init is fairly straightforward; the cells are zeroed, each cell is linked to its neighbor (n-1 and n+1 modulo the number of cells), and cells_ptr, the point from with cells are added and removed, is set to point to cells[0]. alt_cnt counts the number of alternatives (explained later) allocated.
cells_next() is used to obtain a point in the ring from which to allocate. It simply returns cells_ptr and advances cells_ptr to its next pointer.
cell_t *cells_next() {
cell_t *p = cells_ptr;
assert(is_cell(p) &&
!is_closure(p) &&
is_cell(cells_ptr->next));
cells_ptr = cells_ptr->next;
return p;
}cell_alloc(c) removes the cell_t pointer c from the ring. It also keeps track of allocation metrics.
void cell_alloc(cell_t *c) {
assert(is_cell(c) && !is_closure(c));
cell_t *prev = c->prev;
assert(is_cell(prev) && !is_closure(prev));
cell_t *next = c->next;
assert(is_cell(next) && !is_closure(next));
if(cells_ptr == c) cells_next();
prev->next = next;
next->prev = prev;
measure.alloc_cnt++;
if(++measure.current_alloc_cnt > measure.max_alloc_cnt)
measure.max_alloc_cnt = measure.current_alloc_cnt;
}Allocation from the free ring is handled by closure_alloc(args), where args is the number of arguments required by the closure.
cell_t *closure_alloc(int args) {
cell_t *c = closure_alloc_cells(calculate_cells(args));
c->size = args;
return c;
}
cell_t *closure_alloc_cells(int size) {
cell_t *ptr = cells_next(), *c = ptr;
cell_t *mark = ptr;
int cnt = 0;
(void)mark;
// search for contiguous chunk
while(cnt < size) {
if(is_cell(ptr) && !is_closure(ptr)) {
cnt++;
ptr++;
} else {
cnt = 0;
c = ptr = cells_next();
assert(c != mark);
}
}
// remove the found chunk
int i;
for(i = 0; i < size; i++) {
cell_alloc(&c[i]);
}
memset(c, 0, sizeof(cell_t)*size);
return c;
}closure_alloc uses calculate_cells to determine the number of cells required, and calls closure_alloc_cells(size), where size is the number of cells. This function looks for a contiguous chunk of cells that is large enough to fit the new closure. It starts from the pointer returned from cells_next(), and then looks to see if there are enough unallocated cells after it. If it fails, it pulls the next pointer from cells_next(). mark is used to avoid an infinite loop if no chunk that is large enough exists.
cell_t *func(reduce_t *f, unsigned int in, unsigned int out) {
assert(out > 0);
unsigned int args = in + out - 1;
cell_t *c = closure_alloc(args);
c->out = out - 1;
c->func = f;
if(args) c->arg[0] = (cell_t *)(intptr_t)(args - 1);
closure_set_ready(c, !args && f != func_placeholder);
return c;
}After allocation using closure_alloc(n), the new cell is filled with zeroes, except c->size == n. func(f, in, out) wraps closure_alloc to provide a simple way to make incomplete (with missing arguments) closures. f is a reduction function (reduce_t), and in and out are the number of in and out arguments, respectively. c->arg[0] is set to the offset of the first argument (closures fill right to left.) The closure is marked as incomplete by setting the low bit of c->func unless the function requires no arguments or the closure is a placeholder.
Then the arg function can be used to load the arguments from right to left.
/* arg is destructive to *cp */
void arg(cell_t **cp, cell_t *a) {
cell_t *c = *cp;
assert(is_closure(c) && is_closure(a));
assert(!closure_is_ready(c));
int i = closure_next_child(c);
// *** shift args if placeholder
if(is_placeholder(c) &&
(closure_in(c) == 0 ||
closure_is_ready(c->arg[0]))) {
c = expand_inplace(c, 1);
c->arg[0] = a;
} else if(!is_data(c->arg[i])) {
c->arg[0] = (cell_t *)(intptr_t)
(i - (closure_is_ready(a) ? 1 : 0));
c->arg[i] = a;
if(i == 0 && !is_placeholder(c))
closure_set_ready(c, closure_is_ready(a));
} else {
arg(&c->arg[i], a);
if(!is_placeholder(c) &&
closure_is_ready(c->arg[i])) {
if(i == 0) closure_set_ready(c, true);
else --*(intptr_t *)&c->arg[0]; // decrement offset
}
}
*cp = c;
}arg(&c, a) is pretty complex because it needs to handle placeholders. It works its way down the left side of the graph, looking for the innermost function lacking an argument, and then inserts a into that closure. Intuitively, it simply concatenates the argument a to c. Note that c is passed as a reference. This is because c could be moved to accommodate an expanding placeholder.
cell_t *ref(cell_t *c) {
return(refn(c, 1));
}
cell_t *refn(cell_t *c, unsigned int n) {
c = clear_ptr(c, 3);
if(c) {
assert(is_closure(c));
c->n += n;
}
return c;
}References are made by incrementing c->n. The number of references are c->n + 1, because the reference count will never reach zero; it will be immediately freed. This means !c->n indicates that a closure is only referenced once, and can be modified in place. clear_ptr(ptr, bits) clears marker bits in ptr (used by other functions).
void drop(cell_t *c) {
if(!is_cell(c) || !is_closure(c)) return;
if(!c->n) {
cell_t *p;
traverse(c, {
cell_t *x = clear_ptr(*p, 3);
/* !is_marked condition needed */
/* during _modify_copy2 */
if(!is_marked(*p, 2)) {
drop(x);
}
}, ALT | ARGS_IN | PTRS);
if(is_dep(c) && !is_reduced(p = c->arg[0]) && is_closure(p)) {
/* mark dep arg as gone */
int n = closure_args(p);
while(n--) {
if(p->arg[n] == c) {
p->arg[n] = 0;
break;
}
}
}
if(is_reduced(c)) alt_set_drop(c->alt_set);
if(c->func == func_id) alt_set_drop((alt_set_t)c->arg[1]);
closure_free(c);
} else {
--c->n;
}
}Dropping (or removing a reference) is accomplished using the drop(c) function, where c is the cell to drop. It drops c. If c->n == 0, it recursively drops all the arguments of an unevaluated function, or the items in a list, as well as the alternative pointer.
#define traverse(r, action, flags) \
do { \
cell_t **p; \
if(is_reduced(r)) { \
if(((flags) & PTRS) && \
is_list(r)) { \
int i, n = list_size(r); \
for(i = 0; i < n; ++i) { \
p = (r)->ptr + i; \
action \
} \
} \
} else if((flags) & (ARGS | ARGS_IN)) { \
int i, n = ((flags) & ARGS_IN) ? \
closure_in(r) : \
closure_args(r); \
for(i = closure_next_child(r); i < n; ++i) { \
p = (r)->arg + i; \
if(*p) {action} \
} \
} \
if((flags) & ALT) { \
p = &(r)->alt; \
action \
} \
} while(0)The traverse(r, action, flags) macro traverses the cell r and applies action to the parts of r indicated by flags. This makes the drop function (and many others) less tedious.
void closure_shrink(cell_t *c, int s) {
if(!is_cell(c)) return;
int i, size = closure_cells(c);
if(size > s) {
assert(is_closure(c));
for(i = s; i < size; i++) {
c[i].func = 0;
c[i].prev = &c[i-1];
c[i].next = &c[i+1];
}
c[s].prev = cells_ptr->prev;
cells_ptr->prev->next = &c[s];
c[size-1].next = cells_ptr;
cells_ptr->prev = &c[size-1];
measure.current_alloc_cnt -= size - s;
}
}
void closure_free(cell_t *c) {
closure_shrink(c, 0);
}closure_shrink(c, s) shrinks the closure c to s cells, adding the extra cells back to the free ring. closure_free(c) then, which deallocates c entirely, is trivially implemented with closure_shrink(c, 0).
That covers the basics of the memory management functions of the PoprC runtime. The next article in this series will explain quotes (also called lists).