Previous Up Next

8  Memory Management Via Regions

8.1  Introduction

C gives programmers complete control over how memory is managed. An expert programmer can exploit this to write very fast and/or space-efficient programs. However, bugs that creep into memory-management code can cause crashes and are notoriously hard to debug.

Languages like Java and ML use garbage collectors instead of leaving memory management in the hands of ordinary programmers. This makes memory management much safer, since the garbage collector is written by experts, and it is used, and, therefore, debugged, by every program. However, removing memory management from the control of the applications programmer can make for slower programs.

Safety is the main goal of Cyclone, so we provide a garbage collector. But, like C, we also want to give programmers as much control over memory management as possible, without sacrificing safety. Cyclone's region system is a way to give programmers more explicit control over memory management.

In Cyclone, objects are placed into regions. A region is simply an area of memory that is allocated and deallocated all at once (but not for our two special regions; see below). So to deallocate an object, you deallocate its region, and when you deallocate a region, you deallocate all of the objects in the region. Regions are sometimes called ``arenas'' or ``zones.''

Cyclone has six kinds of region:
Stack regions
As in C, local variables are allocated on the runtime stack; the stack grows when a block is entered, and it shrinks when the block exits. We call the area on the stack allocated for the local variables of a block the stack region of the block. A stack region has a fixed size---it is just large enough to hold the locals of the block, and no more objects can be placed into it. The region is deallocated when the block containing the declarations of the local variables finishes executing. With respect to regions, the parameters of a function are considered locals---when a function is called, its actual parameters are placed in the same stack region as the variables declared at the start of the function.

Lexical regions
Cyclone also has lexical regions, which are so named because, like stack regions, their lifetime is delimited by the surrounding scope. Unlike stack regions, however, you can can add new objects to a lexical region over time. You create a lexical region in Cyclone with a statement, 
  region  identifier;  statement
This declares and allocates a new dynamic region, named identifier, and executes statement. After statement finishes executing, the region is deallocated. Within statement, objects can be added to the region, as we will explain below.

Typically, statement is a compound statement: 
  { region identifier;
     statement1
    ...
     statementn
  }


The heap region
Cyclone has a special region called the heap. There is only one heap, whose type is denoted `H, and it is never deallocated. New objects can be added to the heap at any time (the heap can grow). Cyclone uses a garbage collector to automatically remove objects from the heap when they are no longer needed. You can think of garbage collection as an optimization that tries to keep the size of the heap small. (Alternatively, you can avoid garbage collection all together by specifying the -nogc flag when building the executable.)

Dynamic regions
Stack and lexical regions obey a strictly last-in-first-out (LIFO) lifetime discipline. This is often convenient for storing temporary data, but sometimes, the lifetime of data cannot be statically determined. Such data can be allocated in a dynamic region. A dynamic region supports deallocation at (essentially) any program point. However, before the data in a dynamic region may be accessed, the dynamic region must be opened. The open operation fails by throwing an exception if the dynamic region has already been freed. Note that each data access within a dynamic region does not require a check. Rather, you can open a given dynamic region once, access the data many times with no additional cost, and then exit the scope of the open. Thus, dynamic regions amortize the cost of checking whether or not data are still live and localize failure points.

The unique region
All of the regions mentioned thus far only permit deallocation en masse. Cyclone also defines the unique region, whose type is denoted `U, which allows objects to be deallocated individually, using the function ufree. For freeing objects to be safe, we only allow access to objects in `U via unique pointers. That is, only a single pointer may be used to access the object at any given time; this trivially guarantees that if the object is freed through its unique pointer, no other access to the object beyond that point is possible. Objects that become unreachable but are not freed manually will be freed by the garbage collector (assuming it's not removed with -nogc).

The reference-counted region
The reference-counted region, denoted `RC, also permits freeing individual objects. Unlike the unique region, multiple pointers to a single object are permitted, the number of which is tracked dynamically via a hidden reference count stored with the object. Additional pointers to an object are created explicitly via a call to alias_refptr, which increases the reference count. Individual pointers are removed via a call to drop_refptr; when the last pointer is removed (i.e. the reference count is 0), the object is freed. Like the unique region, objects that become unreachable will be freed by the garbage collector.
Cyclone forbids dereferencing dangling pointers. This restriction is part of the type system: it's a compile-time error if a dangling pointer (a pointer into a deallocated region or to a deallocated object) might be dereferenced. There are no run-time checks of the form, ``is this pointing into a live region?'' As explained below, each pointer type has a region and objects of the type may only point into that region.

8.2  Allocation

You can create a new object on the heap using one of a few kinds of expression: Unique pointers can be allocated just as with the heap, but the context must make clear that a unique pointer is desired. For example, in the following the variable temp is allocated in the heap: 
  t * temp = malloc(sizeof(t));
Modifying it slightly, we allocate into the unique region instead: 
  t *`U temp  =        malloc(sizeof(t));
  t *   temp2 = (t *`U)malloc(sizeof(t));
Unfortunately, our type inference system for allocation is overly simple, so you can't do something like: 
  t * temp = malloc(sizeof(t));
  ufree(temp);
In an ideal world, the fact that temp was passed to ufree would signal that it is a unique pointer, rather than a heap pointer.

Objects within lexical and reference-counted regions can be created using the following analogous expressions. Note that new, malloc, calloc, rnew, rmalloc and rcalloc are keywords.

Here, the first argument specifies a region handle. The Cyclone library has global variables Core::heap_region, Core::unique_region, and Core::refcnt_region, which are handles for the heap, unique, and reference-counted regions, respectively. So, for example, rnew (refcnt_region) expr allocates memory in the reference-counted region which is initialized with expr. Moreover, new expr can be replaced with rnew(heap_region) expr.

To allocate an object inside a dynamic region, it must first be opened, revealing its region handle. At that point, it is treated just as if it were a lexical region. The process of creating, opening, and freeing dynamic regions is explained more below.

The only way to create an object in a stack region is declaring it as a local variable. Cyclone does not currently support salloc; use a lexical region instead.

8.3  Common Uses

Although the type system associated with regions is complicated, there are some simple common idioms. If you understand these idioms, you should be able to easily write programs using regions, and port many legacy C programs to Cyclone. The next subsection will explain the usage patterns of unique and reference-counted pointers, since they are substantially more restrictive than other pointers.

Remember that every pointer points into a region, and although the pointer can be updated, it must always point into that same region (or a region known to outlive that region). The region that the pointer points to is indicated in its type, but omitted regions are filled in by the compiler according to context.

When regions are omitted from pointer types in function bodies, the compiler tries to infer the region. However, it can sometimes be too ``eager'' and end up rejecting code. For example, in 
void f1(int * x) {
  int * y = new 42;
  y = &x;
}
the compiler uses y's initializer to decide that y's type is int * `H. Hence the assignment is illegal, the parameter's region (called `f1) does not outlive the heap. On the other hand, this function type-checks: 
void f2(int x) {
  int * y = &x;
  y = new 42;
}
because y's type is inferred to be int * `f2 and the assignment makes y point into a region that outlives `f2. We can fix our first function by being more explicit: 
void f1(int * x) {
  int *`f1 y = new 42;
  y = &x;
}
Function bodies are the only places where the compiler tries to infer the region by how a pointer is used. In function prototypes, type declarations, and top-level global declarations, the rules for the meaning of omitted region annotations are fixed. This is necessary for separate compilation: we often have no information other than the prototype or declaration.

In the absence of region annotations, function-parameter pointers are assumed to point into any possible region. Hence, given 
void f(int * x, int * y);
we could call f with two stack pointers, a lexical-region pointer and a heap-pointer, etc. Hence this type is the ``most useful'' type from the caller's perspective. But the callee's body (f) may not type-check with this type. For example, x cannot be assigned a heap pointer because we do not know that x points into the heap. If this is necessary, we must give x the type int *`H. Other times, we may not care what region x and y are in so long as they are the same region. Again, our prototype for f does not indicate this, but we could rewrite it as 
void f(int *`r x, int *`r y);
Finally, we may need to refer to the region for x or y in the function body. If we omit the names (relying on the compiler to make up names), then we obviously won't be able to do so.

Formally, omitted regions in function parameters are filled in by fresh region names and the function is ``region polymorphic'' over these names (as well as all explicit regions).

In the absence of region annotations, function-return pointers are assumed to point into the heap. Hence the following function will not type-check: 
int * f(int * x) { return x; }
Both of these functions will type-check: 
int * f(int *`H x) { return x; }
int *`r f(int *`r x) {return x; }
The second one is more useful because it can be called with any region.

In type declarations (including typedef) and top-level variables, omitted region annotations are assumed to point into the heap. In the future, the meaning of typedef may depend on where the typedef is used. In the meantime, the following code will type-check because it is equivalent to the first function in the previous example: 
typedef int * foo_t;
foo_t f(foo_t x) { return x; }
If you want to write a function that creates new objects in a region determined by the caller, your function should take a region handle as one of its arguments.2 The type of a handle is region_t<`r>, where `r is the region information associated with pointers into the region. For example, this function allocates a pair of integers into the region whose handle is r: 
  $(int,int)*`r f(region_t<`r> r, int x, int y) { 
     return rnew(r) $(x,y);
  }
Notice that we used the same `r for the handle and the return type. We could have also passed the object back through a pointer parameter like this: 
  void f2(region_t<`r> r,int x,int y,$(int,int)*`r *`s p){ 
    *p = rnew(r) $(7,9); 
  }
Notice that we have been careful to indicate that the region where *p lives (corresponding to `s) may be different from the region for which r is the handle (corresponding to `r). Here's how to use f2: 
  { region rgn;
    $(int,int) *`rgn x = NULL; 
    f2(rgn,3,4,&x);
  }
The `s and `rgn in our example are unnecessary because they would be inferred.

typedef, struct, and datatype declarations can all be parameterized by regions, just as they can be parameterized by types. For example, here is part of the list library. 
  struct List<`a,`r>{`a hd; struct List<`a,`r> *`r tl;};
  typedef struct List<`a,`r> *`r list_t<`a,`r>;

  // return a fresh copy of the list in r2
  list_t<`a,`r2> rcopy(region_t<`r2> r2, list_t<`a> x) {
    list_t result, prev;

    if (x == NULL) return NULL;
    result = rnew(r2) List{.hd=x->hd,.tl=NULL};
    prev = result;
    for (x=x->tl; x != NULL; x=x->tl) {
      prev->tl = rnew(r2) List(x->hd,NULL);
      prev = prev->tl;
    }
    return result;
  }  
  list_t<`a> copy(list_t<`a> x) {
    return rcopy(heap_region, x);
  }

  // Return the length of a list. 
  int length(list_t x) {
    int i = 0;
    while (x != NULL) {
      ++i;
      x = x->tl;
    }
    return i;
  }
The type list_t<type,rgn> describes pointers to lists whose elements have type type and whose ``spines'' are in rgn.

The functions are interesting for what they don't say. Specifically, when types and regions are omitted from a type instantiation, the compiler uses rules similar to those used for omitted regions on pointer types. More explicit versions of the functions would look like this: 
  list_t<`a,`r2> rcopy(region_t<`r2> r2, list_t<`a,`r1> x) {
    list_t<`a,`r2> result, prev;
    ...
  }
  list_t<`a,`H> copy(list_t<`a,`r> x) { ... }
  int length(list_t<`a,`r> x) { ... }

8.4  Unique Pointers

The main benefit of the regions described thus far is also their drawback: to free data you must free an entire region. This implies that to amortize the cost of creating a region, one needs to allocate into it many times. Furthermore, the objects allocated in a region should be mostly in use until the region is freed, or else memory will be wasted in the region that is unused by the program.

For the cases in which neither situation holds, we can use the unique region, which allows unique pointers to be freed individually. To prevent dangling pointers, a static analysis ensures that objects in the unique region (unique objects) can only ever be accessed through one pointer at any time. At the time it is freed, this pointer is invalidated, thus preventing all future accesses to the object.

To ease programming with unique pointers and allow reuse of library code, unique pointers can be aliased temporarily within a designated lexical scope using a special alias pattern. If this kind of aliasing is not sufficient, users can choose to allocate reference-counted objects; this idea is explained in the next subsection. We also define syntax a :=: b to allow two unique pointers a and b to be atomically swapped. Careful use of the swap operator allows us to store unique pointers in objects that are not themselves uniquely pointed to. Finally, to properly deal with polymorphism, particularly when performing allocation, we introduce new kinds for describing regions. In practice, all of these mechanisms are necessary for writing useful and reusable code.

8.4.1  Simple Unique Pointers

Having a unique pointer ensures the object pointed to is not reachable by any other means. When pointers are first allocated, e.g. using malloc, they are unique. Such pointers are allowed to be read through (that is, dereferenced or indexed) but not copied, as the following example shows: 
  char *@fat`U buf = malloc(3*sizeof(char));
  buf[0] = 'h';
  buf[1] = 'i';
  buf[2] = '\0';
  ...
  ufree(buf);
This piece of code allocates a unique buffer, and then indexes that buffer three times to initialize it. Because the process of storing to the buffer does not copy its unique pointer, it can be safely freed.

When a unique pointer is copied, e.g. when passed as a parameter to a function or stored in a datastructure, we say it has been consumed. We ensure that consumed pointers are not read through or copied via a dataflow analysis. When a consumed pointer is assigned to, very often it can be unconsumed, making it accessible again. Here is a simple example that initializes a datastructure with unique pointers: 
 1  struct pair { int *`U x; int *`U y; } p;
 2  int *`U x = new 1;  // initializes x
 3  p.x = x;            // consumes x
 4  x = new 2;          // unconsumes x
 5  p.y = x;            // consumes x
If an attempt was made to read through or copy x between lines 3 and 4 or after line 5, the flow analysis would reject the code, as in 
  int *`U x = new 1;  // initializes x
  p.x = x;            // consumes x
  p.y = x;            // rejected! x has been consumed already
When a multi-word data structure is assigned to another one, all of the unique pointers it contains are consumed. For example: 
 1  struct pair { int *`U x; int *`U y; } p, q;
 2  p.x = new 1; p.y = new 2;
 3  q = p;              // consumes p.x and p.y
By default, when a unique pointer is passed to a function, we assume that the function will free the pointer, store it in a data structure, or otherwise make it unavailable to the caller. You can override this behavior using the attribute noconsume, which indicates that a particular argument should be available to the caller after the call. For example: 
void foo(int *`U x) __attribute__((noconsume(1))) {
  *x = 1;
}
void bar() {
  int *`U x = malloc(sizeof(int));
  foo(x);
  ufree(x);
}
Here, the noconsume(1) attribute in the definition of foo indicates that the first argument should not be consumed within the function body. The flow analysis verifies that this is indeed the case. As a result, the call to foo within bar does not consume x, so it can be freed afterwards.

Note that if you fail to free a unique pointer, it will eventually be garbage collected.

Unique pointers have some restrictions. In particular:

8.4.2  Nested Unique Pointers

Directly reading a unique pointer is only allowed along a unique path. A unique path u has the form
u ::= x | u.m | u->m | *u
where x is a local variable, and u is a unique pointer. To appreciate the unique-path restriction, consider this incorrect code: 
int f(int *`U *`r x) {
  int *`U *`r y = x;  //x and y are aliases
  int *`U z = *y;
  ufree(z);
  return **x;  //accesses deallocated storage!
}
Here, x is a pointer into a conventional region `r and thus its value can be freely copied to y. We then extract a unique pointer pointed to by y and free it. Then we attempt to access the deallocated storage through x.

If a unique pointer is not accessible via a unique path, it must be swapped out atomically to be used; in Cyclone this is expressed with syntax :=:. In particular, the code a :=:b will swap the contents of a and b. We can use this to swap out a nested unique pointer, and replace it with a different one; we will often swap in NULL, since this is a unique pointer that is always unconsumed. For example, in the code below, we define a queue type for queues that contain unique pointers, and a function take for removing the first element from the queue. 
struct Queue<`a,`r> { 
  list_t<`a *`U,`r> front; 
  list_t<`a *`U,`r> rear; 
};
typedef struct Queue<`a,`r> *`r queue_t<`a,`r>;

`a *`U take(queue_t<`a> q) {
  if (q->front == NULL)
    throw &Empty_val;  // exception: def not shown
  else {
    let elem = NULL;
    elem :=: q->front->hd;
    q->front = q->front->tl;
    if (q->front == NULL) q->rear = NULL;
    return elem;
  }
}
Here, in order to extract the element stored in the queue (the hd portion of the underlying list), we need to use swap, because q->front is a non-unique pointer, and therefore q->front->hd is not a unique path.

Note that this code is not as polymorphic as it could be. In particular, the above queue definition requires its elements to be nullable unique pointers, when they could just as easily be non-unique pointers, or even reference-counted pointers (illustrated later), and the code for take would still work. This problem can be addressed, and its solution is described in Section 8.4.5.

8.4.3  Pattern Matching on Unique Pointers

As described in Section 5, Cyclone supports pattern matching on structured data with let declarations and switch statements. Unique pointers, or structures containing unique pointers, can be matched against, while still ensuring that only one legal pointer to a unique object exists at any given time.

In the simplest case, when a unique pointer to a structure is matched against, the matching operation is treated just like a dereference. Therefore, the pointer itself is not consumed. For example: 
struct pair { int x; int y; };
void foo() {
  struct pair @`U p = new pair(1,2);
  let &pair{.x=x, .y=y} = p;
  ufree(p);
}
Here, we match against the unique pointer p's two fields x and y. Because we don't make a copy of p, but rather only of its fields, p is not consumed. Therefore, p can be safely freed.

Because each of the fields matched against is assigned to the pattern variables, unique paths through the original pointer are consumed by virtue of being assigned. At the conclusion of the scope of the pattern, we can unconsume any location whose pattern variable has not been consumed or assigned to, as long as the parent pointer has not been consumed or assigned to. Here's an example: 
struct Foo { int *`U x; int *`U y; };
void foo(struct Foo *`U p) {
  { let &Foo{.x=x, .y=y} = p; // consumes p->x and p->y
    ufree(x);                 // consumes x
  }                           // p->y is unconsumed
  ufree(p->y);                // p->y consumed
  ufree(p);                   // p consumed
}
The initial match against p consumes p->x and p->y, whose contents are copied to x and y, respectively. At the conclusion of the block, p->y is unconsumed because it did not change, whereas p->x is not, because x was freed within the block.

Note that the following code is illegal: 
void foo(struct Foo *`H p) {
 let &Foo{.x=x, .y=y} = p; // non-unique path!
 ...
}
To see why, notice that this is equivalent to 
void foo(struct Foo *`H p) {
 let x = p->x;
 let y = p->y;
 ...
}
This code is illegal because neither p->x nor p->y is a unique path. We also do not allow * patterns to create aliases of the original unique pointer, for the same reason we forbid &e when e is a unique pointer. Unfortunately, this means we don't provide a way to assign to matched-against fields. However, in the case of the matched-against struct, we can just do this with regular paths. In the above example pattern block, we could do p->y = new 1 or something like that (even within the scope of the pattern).

Matching against tagged unions is essentially like matching against structures, as just described. Since we do not allow unique pointers to be stored within datatypes, there is no change to how datatypes are matched.

8.4.4  Aliasing Unique Pointers

Programmers often write code that aliases values temporarily, e.g. by storing them in loop iterator variables or by passing them to functions. Such reasonable uses would be severely hampered by ``no alias'' restrictions on unique pointers. To address this problem, we introduce a special alias pattern variable that permits temporary aliasing of a unique pointer. Here is a simple example: 
  char *@fat`U dst, *@fat`U src = ...
  { let alias <`r>char *@fat`r x = src; // consumes src
    memcpy(dst,x,numelts(x)); }
  // src unconsumed
  ...
  ufree(src);
In general, an alias pattern has form alias <`r>t x, where `r is a fresh region variable, and t is the type of x, which may mention `r. The alias pattern introduces a region `r, copies src to x which is treated as having the designated type char *@fat`r. Because `r is non-unique, x can be freely aliased. As such, we can pass x to the memcpy function. The matching operation consumes src during the block, and unconsumes it upon exit, so that src can be ultimately freed.

Alias pattern variables are similar to regular pattern variables. Like regular pattern variables, the matched-against expression (i.e. src in the above example) must be a unique path, and is consumed as a result of the match. As well, this expression can be unconsumed at the conclusion of the surrounding block as long as it hasn't been overwritten. However, in the case of regular pattern variables, unconsumption also requires that the pattern variable itself (i.e. x in the above example) hasn't changed within the block, while this requirement is unnecessary for alias patterns.

Intuitively, alias pattern variables are sound because we cast a unique pointer to instead point into a fresh region, for which there is no possibility of either creating new values or storing existing values into escaping data structures. As such we cannot create aliases that persist beyond the surrounding scope. However, we must take care when aliasing data having recursive type. For example, the following code is unsound: 
  void foo(list_t<`a,`U> l) {
    alias <`r> x = (list_t<`a,`r>)l;
    x->tl = x; // unsound: creates alias!
  }
In this case, the alias effectively created many values in the fresh region `r: one for each element of the list. This allows storing an alias in an element reachable from the original expression l, so that when the block is exited, this alias escapes.

To prevent this, we only allow ``deep'' aliasing when the aliased pointers are immutable. For example, if we have a list structure whose tail pointers are const, call it clist_t, we rule out the above code because the assignment to x->tl would be forbidden. Here is an example implementation of a length function that is amenable to deep aliasing: 
  int length(clist_t<`a,`r> l) {
    int len = 0;
    while (l != NULL) {
      len++;
      l = l->tl;
    }
    return len;
  }

  int foo() {
    list_t<int,`U> l = new List(1,new List(2,NULL));
    let alias <`r>clist_t<int,`r> x = l;
    return length(x);
  }
Here, the length function works on constant lists, and the foo function aliases a unique, mutable list l to call length.

For improved programmer convenience, the Cyclone typechecker optimistically inserts alias blocks around function-call arguments that are unique pointers when the formal-parameter type is polymorphic in the pointer's region. If this modified call does not type-check, we remove the inserted alias. For example, the alias pattern in the foo function above could be inferred, so we could instead write: 
  int foo() {
    list_t<int,`U> l = new List(1,new List(2,NULL));
    return length(l);
  }
Right now, alias inference in Cyclone is fairly primitive, but could be extended to more contexts. We plan to improve this feature in future releases.

8.4.5  Polymorphism

As described in Section 8.3, we can write functions that take as arguments a region handle to allocate into. For example, we wrote a function rcopy that copies a list into some region `r2. However, we didn't provide the full story that accounts for the unique region. In particular, consider the following function: 
  $(int @`r, int @`r) make_pair(region_t<`r> rgn) {
    int @x = rnew (rgn) 1;
    return $(x, x);
  }
This function will return a pair of pointers to the same object. If we pass in something other than the unique region, this function will behave properly: 
  $(int @,int@) pair = make_pair(heap_region);
However, things can go badly wrong if we pass in the unique region instead: 
  $(int @`U,int @`U) pair = make_pair(unique_region);
  ufree(pair[0]);
  int x = pair[1]; // error! dereferences freed pointer
The problem is that make_pair creates an alias; if we pass in the unique region for rgn, we can free one of these aliases (e.g. the pointer via the first element of the pair), but then dereference the other (i.e. via the second pair element).

To prevent this behavior, we have to classify the different kinds of regions that we support: aliasable regions, whose pointers can be freely aliased, and unique regions, whose pointers cannot be aliased, and can form part of unique paths. To do this, we define kinds R for aliasable regions and UR for unique ones. We can then classify a polymorphic region variable with the proper kind. This allows us to change the make_pair function as follows: 
  $(int @`r, int @`r) make_pair(region_t<`r::R> rgn) {
    int @x = rnew (rgn) 1;
    return $(x, x);
  }
Now we have specified specifically that `r must be an aliasable region (in fact, when not specified, this is the default for function parameters). As such, the illegal code above will not typecheck because we are attempting to instantiate a unique region (having kind UR) for an aliasable one, which is disallowed.

For generality, we introduce a third region kind TR (which stands for ``top region''); TR is a ``super-kind'' of R and UR, meaning that types having TR kind can be used in places expecting types of R or UR kind. This also means that we cannot allow pointers into a TR-kinded region to be aliased, nor can we assume they do not have aliases (and so they cannot safely form part of a unique path). This is because we might instantiate either the unique region (whose pointers cannot be aliased) or an aliasable region (whose pointers might be aliased) in place of the TR-kinded variable.

We can now generalize the rcopy example above: 
  struct List<`a,`r::TR>{`a hd; struct List<`a,`r> *`r tl;};
  typedef struct List<`a,`r> *`r list_t<`a,`r>;

  // return a fresh copy of the list in r2
  list_t<`a,`r2> rcopy(region_t<`r2::TR> r2, list_t<`a> x) {
    if (x == NULL) return NULL;
    else {
      list_t rest = rcopy(r2,x->tl);
      return rnew(r2) List{.hd=x->hd,.tl=rest};
    }
  }
  list_t<`a> copy(list_t<`a> x) {
    return rcopy(heap_region, x);
  }
We have made three key changes to the prior version of rcopy:
  1. The definition of List has been generalized so that its `r region variable now has kind TR. This implies that lists can point into any region, whether unique or aliasable. Actually, we need not include the ::TR kind annotation on region type variables in typedefs; this is the default (since it allows instantation of any region parameter).
  2. The region handle r2 now has kind TR, rather than the default R. This means that we can pass in any region handle, and thus copy a list into any kind of region.
  3. We have made rcopy's implementation recursive. This was necessary to avoid creating aliases to the newly created list. In particular, if we were to have used a prev pointer as in the version from Section 8.3, we would have two pointers to the last-copied element: the tl field of the element before it in the list, and the current iterator variable prev. The use of recursion allows us to iterate to the end of the list and construct it back to front, in which no aliases are required. The cost is we need to do extra stack allocation. This example illustrates that it is sometimes difficult to program using no-alias pointers. This is why, in cases other than allocation, we would prefer to use the alias construct to allow temporary aliasing.
In addition to needing polymorphism for region allocation, for the same reasons we need polymorphism for arbitrary values which might be pointers into either unique or aliasable regions. For example, consider the following code analogous to the make_pair function above: 
  $(`a,`a) pair(`a x) {
    return $(x,x);
  }
Now consider what happens if we call pair with a unique pointer: 
  int @`U p = new 1;
  $(int @`U,int @`U) pair = pair(p);
  ufree(pair[0]);
  int x = pair[1]; // error! dereferences freed pointer
Again, the problem is that we have not restricted the kinds of things that can be used to instantiate polymorphic variables. We extend our solution for region kinds, above, to all of Cyclone's kinds. For example, Cyclone's ``box-kind'' B, which classifies word-sized values, must be extended so that B refers to aliasable word-sized values, while UB refers to non-aliasable word-sized values, and TB is the super-kind of both. A similar extension occurs for kind M (memory-kinds, having arbitrary size), and kind A (any-kinds, for abstract, arbitrary-sized data). With this, we can fix the pair function to be: 
  $(`a,`a) pair(`a::B x) {
    return $(x,x);
  }
This would prevent the call to pair(p) in the code snippet above. Actually, as with regions, aliasable kinds are the default, so the ::B can be elided.

8.5  Reference-counted Pointers

Cyclone also supports reference-counted pointers, which are treated quite similarly to unique pointers. Reference-counted objects are allocated in the reference-counted region, named `RC. This region has kind TR, which ensures that pointers into it cannot be aliased implicitly, but aliases might exist, meaning they cannot form part of unique paths. Similarly, reference-counted pointers have kind TB. We define the constant Core::refcount_region, having type region_t<`RC>, for creating reference-counted pointers. The caveat here is that when you allocate something in this region, an extra word will be prepended to your data, which contains the reference count, initialized to 1.

As with unique pointers, no pointer arithmetic is allowed, for similar reasons: it can occlude where the "head" of the object is, and thus make it impossible to find the hidden reference count. The reference count can be accessed via the routine Core::refptr_count: 
  int refptr_count(`a::TA ?`RC ptr)
    __attribute__((noconsume(1)));
The constant NULL is allowed to have type `a::A ?`RC, and its reference count is always 0. The noconsume attribute ensures that the pointer is not consumed by the call. Like unique pointers, implicit aliasing is not allowed. Aliases are created explicitly using the routine Core::alias_refptr: 
  `a ?`RC alias_refptr(`a::TA ?`RC ptr)
    __attribute__((noconsume(1)));
This routine returns a copy of its argument, which is itself not consumed. Furthermore, the reference count will be incremented by one. Reference counts are reduced explicitly by the routine drop_refptr: 
  void drop_refptr(`a::TA ?`RC ptr);
In the case that the provided object's reference count is 1 (and is thus dropped to zero), the provided pointer is freed. The flow analysis will consume the passed pointer (as is always the case for function arguments), so you won't be able to use it afterwards. Just like unique pointers, you can ``forget'' reference-counted pointers without decrementing the count; this just means you'll never be able to free the pointer explicitly, but the GC will get it once it becomes unreachable.

Just like unique pointers, reference-counted pointers can be stored in normal, aliasable datastructures, and accessed using swap (e.g. x :=: y). Because NULL is a `a::TA ?`RC pointer, we can always cheaply construct a pointer to swap in. Also, alias pattern variables can work to create temporary (non-counted) aliases of a reference-counted pointer.

A good example of the use of unique pointers and reference-counted pointers is in the Cyclone distribution's tests directory---the file streambuff.cyc. This is an implementation of a packet manipulation library with a representation for packets (called streambuff_t's) that is similar to Linux's skbuff_t's. It uses a combination of unique header structures and reference-counted data structures.

8.6  Dynamic Regions

Dynamic regions combine reference-counted or unique pointers and lexical regions together to essentially create reference-counted or unique regions; that is, the region is completely first class, and can be created or freed at conceptually any program point. This is done by representing a dynamic region as a unique (or reference-counted) pointer to an abstract struct DynamicRegion (which internally just contains the handle to a lexical region). The unique (or ref-counted) pointer is called the key. The key serves as a run-time capability that grants access to the region. At run-time, a key can be presented to a special open primitive, described later, that grants lexical access to the region.

The operation new_ukey() creates a fresh dynamic region and returns a unique key for the region; new_rckey() creates a fresh dynamic region and returns a ref-counted key for the region. The operations free_ukey() and free_rckey() are used to destroy unique and ref-counted keys respectively. The free_ukey() operation reclaims the key's region, as well as the storage for the key. The free_rckey() operation decrements the reference count, and if it's zero, reclaims the key's region as well as the storage for the key. Because ref-counted keys are pointers, you can use alias_refptr to make a copy of a ref-counted key. (Obviously, you can't make a copy of a unique key.) By the same token, you can pass a ref-counted key to drop_refptr (and you can pass a unique key to ufree), but doing so won't actually deallocate the region, but rather only the key.

Given a key k, a user can access the contents of its region by temporarily `opening the region' within a lexical scope. This is done with the syntax region r = open k. That is, within the remainder of the current scope, the region handle r can be used to access k's region. The key k is temporarily consumed throughout the scope, and then unconsumed at its conclusion. This prevents you from opening up the dynamic region, and then freeing it while it's still in use. Note that open is very similar to alias in this way.

Here is a small example of the use of dynamic regions. 
int main() {
  // Create a new dynamic region
  let NewDynamicRegion{<`r> key} = new_ukey();

  // At this point, we refer to the region `r to
  // specify types, but we cannot actually access
  // `r (i.e. it's not in our "static capability,"
  // a concept explained later)

  list_t<int,`r> x = NULL;

  // We can access x by opening the region, which
  // temporarily consumes the key
  { region h = open(key);
    x = rnew(h) List(3,x);
  }

  // Now we can access the key again, but not x.
  // So we have to open the region to increment
  // its contents
  { region h = open(key);
    int i = x->hd + 1;
    x = rnew (h) List(i,x);
  }

  // Finally, destroy the key and the region
  free_ukey(key);
}
First, we allocate a new unique key and open it up, to reveal the name of the key's region (`r), and the key itself. Because `r is now in scope, we can declare a variable x that refers to it. However, because the key key must be opened before `r becomes accessible, we cannot actually do anything with x yet (like dereference it).

Next, we open up the region using key, assigning its handle to the vairable h. Now, key is inaccessible (consumed) in the surrounding block, which prevents us from doing anything that might cause it to be freed while it's in use. We can use h to allocate into `r, so we allocate a list element and store it in x.

At the conclusion of the block, the region `r becomes inaccessible again, so once again we cannot dereference x. However, key can now be accessed again, so we can open it again in the following block, to add a new list cell to x. At the conclusion of this block, key is unconsumed once again, so we legally call free_ukey. This frees the key and the region `r.

You can "share" a dynamic region key by placing it in some shared data structure, like a global variable. Of course, you'll then have to swap with NULL to get it in and out of the shared data structure, as the following code demonstrates: 
struct MyContainer { <`r>
  uregion_key_t<`r> key;
  list_t<int,`r> data;
} *`U global = NULL;

int main() {
  // allocate a dynamic region, and create a list
  let NewDynamicRegion{<`r> key} = new_ukey();
  list_t<int,`r> x = NULL;
  { region h = open(key);
    x = rnew(h) List(3,x);
  }

  // Stick the key and list in a global data
  // structure. We've now lost direct access to
  // the key and x.
  global = new MyContainer{key,x};

  // But we can regain it by swapping for the
  // container.
  struct MyContainer *`U p = NULL;
  global :=: p;

  // Now we can use it as above
  let MyContainer{<`r2> key2, data2} = *p;
  list_t<int,`r2> d = data2;
  { region h = open(key2);
    int i = d->hd + 1;
    d = rnew (h) List(i,d);
  }
}
Here, we define a global variable having type MyContainer, which consists of a key and some data into that key's region. The main function allocates a unique as before, and allocates some data into its region. Then we create a container for that key and data, and store it into the global variable; this consumes key, making it inaccessible, and effectively preventing access of x as well.

But we can then get the container back out of the global variable by swapping its contents with NULL. Then we can open up the container, and use the key and data as before. This way, a single dynamic region can be used by many different functions in the program. They simply swap out the global when they need it, operate on it, and then swap in the result.

One problem with using this technique with unique keys arises when you need to open the same region multiple times. The problem, of course, is that if you swap in NULL, then whoever tries to swap it out will fail. In other words, you can't really do recursive opens with `U keys. However, you can do this with `RC keys! Swap out the key, make a copy of it, swap it back in, and use the copy for the open (making sure to destroy the copy after the open).

One disadvantage of dynamic regions, which is inherited from unique and reference-counted pointers, is that if you put a key in some shared storage in a region `r, then it is not the case that when `r is deallocated that the key will be destroyed automatically. It's up to you to do the right thing or let the GC eventually collect it. In the long run, the right thing to do is add a finalizer interface for regions so that we can register a routine to deallocate a dynamic region whenever we put it in a shared data structure. The same goes for any unique pointer --- we ought to have a way to register a finalizer. This is on our To-do list.

8.7  Type-Checking Regions

Because of recursive functions, there can be any number of live regions at run time. The compiler uses the following general strategy to ensure that only pointers into live regions are dereferenced: This strategy is probably too vague to make sense at this point, but it may help to refer back to it as we explain specific aspects of the type system.

Note that in the rest of the documentation (and in common parlance) we abuse the word ``region'' to refer both to region names and to run-time collections of objects. Similarly, we confuse a block of declarations, its region-name, and the run-time space allocated for the block. (With loops and recursive functions, ``the space allocated'' for the block is really any number of distinct regions.) But in the rest of this section, we painstakingly distinguish region names, regions, etc.

8.7.1  Region Names

Given a function, we associate a distinct region name with each program point that creates a region, as follows: The region name for the heap is `H, the region name for the unique region in `U, and the region name for the reference-counted region is `RC. Region names associated with program points within a function should be distinct from each other, distinct from any region names appearing in the function's prototype, and should not be `H, `U, or `RC. (So you cannot use H as a label name, for example.) Because the function's return type cannot mention a region name for a block or region-construct in the function, it is impossible to return a pointer to deallocated storage.

In region r <`r> s, region r s, and region r = open(k) s the type of r is region_t<`r> (assuming, that k has type region_key_t<`r,_>). In other words, the handle is decorated with the region name for the construct. Pointer types' region names are explicit, although you generally rely on inference to put in the correct one for you.

8.7.2  Capabilities

In the absence of explicit effects (see below), the capability for a program point includes exactly: For each dereference or allocation operation, we simply check that the region name for the type of the object is in the capability. It takes extremely tricky code (such as existential region names) to make the check fail.

8.7.3  Assignment and Outlives

A pointer type's region name is part of the type. If e1 and e2 are pointers, then e1 = e2 is well-typed only if the region name for e2's type ``outlives'' the region name for e1's type. By outlives, we intuitively mean the region corresponding to one region name will be deallocated after the region corresponding to the other region name. The rules for outlives are as follows: For handles, if `r is a region name, there is at most one value of type region_t<`r> (there are 0 if `r is a block's name), so there is little use in creating variables of type region_t<`r>.

8.7.4  Type Declarations

A struct, typedef, or datatype declaration may be parameterized by any number of region names. The region names are placed in the list of type parameters. They may be followed by their kind; i.e. either ``::R'', ``::UR'', or ``::TR''. If no region kind is provided, TR is the default. In typedef declarations, region names that appear as parameters inherit their kind from the the specification of that region name in the underlying type. For example, given 
  struct List<`a,`r>{`a hd; struct List<`a,`r> *`r tl;};
the type struct List<int,`H> is for a list of ints in the heap, while the type struct List<int,`U> is for a list of ints in the unique region. Notice that all of the ``cons cells'' of the List will be in the same region (the type of the tl field uses the same region name `r that is used to instantiate the recursive instance of struct List<`a,`r>). However, we could instantiate `a with a pointer type that has a different region name, as long as that region has kind R.

8.7.5  Function Calls

If a function parameter or result has type int *`r or region_t<`r>, the function is polymorphic over the region name `r. That is, the caller can instantiate `r with any region in the caller's current capability as long as the region has the correct kind. This instantiation is usually implicit, so the caller just calls the function and the compiler uses the types of the actual arguments to infer the instantiation of the region names (just like it infers the instantiation of type variables).

The callee is checked knowing nothing about `r except that it is in its capability (plus whatever can be determined from explicit outlives assumptions), and that it has the given kind. For example, it will be impossible to assign a parameter of type int*`r to a global variable. Why? Because the global would have to have a type that allowed it to point into any region. There is no such type because we could never safely follow such a pointer (since it could point into a deallocated region).

8.7.6  Explicit and Default Effects

If you are not using existential types, you now know everything you need to know about Cyclone regions and memory management. Even if you are using these types and functions over them (such as the closure library in the Cyclone library), you probably don't need to know much more than ``provide a region that the hidden types outlive''.

The problem with existential types is that when you ``unpack'' the type, you no longer know that the regions into which the fields point are allocated. We are sound because the corresponding region names are not in the capability, but this makes the fields unusable. To make them usable, we do not hide the capability needed to use them. Instead, we use a region bound that is not existentially bound.

If the contents of existential packages contain only heap pointers, then `H is a fine choice for a region bound.

These issues are discussed in Section 12.

Previous Up Next

Web Accessibility