Project 1

The system you are implementing should support reference counting. This means that each object has an associated counter that tracks the number of pointers to that object. When an object is created, its reference count is 0. Its count can subsequently be manipulated by the functions retain() and release() which increments respectively decrements a reference count by 1.

If release() is called on an object with a reference count of 1, the object is considered garbage and shall be free’d.

Calling retain() and release() on NULL is supported and should simply be ignored.

For simplicity, we will only count pointers on the heap. If an object is allocated and never retained(), it can be deleted by calling deallocate(). Calling deallocate() on an object with a non-zero reference count is an error.

The system you are implementing should support destructor functions. This means that each object (may) have one associated function that is called right before the object’s memory is free’d.

Destructors are useful for resource management, including freeing complicated data structures. For example, consider a linked list. The destructor for a link should be a function that calls release() on the link’s next pointer². Similarly, the destructor for the list head calls release() on both first and last.

Consider the linked list example above: if implemented naively, freeing a very large linked list (think millions of elements) will at best cause the program to spend many consecutive cycles on freeing links, and at worst cause the program to run out of stack space. Neither behaviour is acceptable.

The system you are implementing must avoid both these pathological cases, by supporting setting an upper limit on how many objects are free’d at once (set_cascade_limit()).

To avoid oversubscribing to memory, you can delay outstanding free’s until next allocation. When freeing in conjunction with allocation, the cascade limit must be respected as usual, unless the amount of memory free’d is less than the bytes requested for allocation. In that case, your system is allowed to free objects until the requested number of bytes have been free’d or there are no more objects to free.

To reduce memory pressure, the system should also provide a cleanup() function that free’s all objects whose reference count is 0, regardless of the cascade limit.

#pragma once

typedef void obj;
typedef void(*function1_t)(obj *);

void retain(obj *);
void release(obj *);
size_t rc(obj *);
obj *allocate(size_t bytes, function1_t destructor);
obj *allocate_array(size_t elements, size_t elem_size, function1_t destructor);
void deallocate(obj *);
void set_cascade_limit(size_t);
size_t get_cascade_limit();
void cleanup();
void shutdown();

The function rc() returns an object’s reference count. The allocate() function is the equivalent of malloc() and takes a function pointer to a destructor function, possibly NULL. The allocate_array() function is the equivalent of calloc() and too takes a function pointer to a destructor function, possibly NULL, which is called for each non-NULL element. The function deallocate() is the equivalent of free() but is only allowed to be called on objects p for which rc(p) = 0. Calling deallocate() on an object runs its destructor (if any).

Note: You are allowed³ to call malloc(), calloc() and free() under the hood to allocate and return memory. Think of these as low-level functions whose existence you are hiding from your users.

Naturally, the size of the reference counter is an important design choice. For example, choosing an 8 bit integer, we keep the memory overhead small but are then only allowed 255 incoming references to each object⁴. Choose the size of your reference counter wisely and document the choice and explain how your system handles (or not) reference counter overflow.

Amortising the memory management overhead over the program run-time means that the cost of managing memory is distributed relatively evenly over the the program’s execution. Contrast this with automatic garbage collectors that suspend the program completely to manage memory from time to time.

You achieve this by properly respecting the cascade limit (see above).

You may only use a constant factor of memory overhead in your implementation, relative to malloc() / calloc(). For example, a program that uses B bytes of memory with malloc() / calloc() may only use k * B bytes using your system. Additionally, k may not be larger than 2.

You must hand in a convincing proof/back-of-envelope calculation that explains why your implementation satisfies this requirement⁵.

For the sake of the calculation, you may assume that no allocation is smaller than 8 bytes⁶, but you may not assume a limit on the number of allocations made by programs using the system, nor a limit on the amount of live objects or the amount of (logical) garbage.

Keeping memory overhead low is important, but ignore that in your first prototype. Solve the problem of getting something up and running first, then figure out how to optimise. Here are some tricks you can use to keep memory overhead small. These may or may not be usable together:

1. Use a small scalar value for your reference count.
2. When an object is garbage, you can reuse its memory – including its reference counter – to store whetever you want.
3. If the number of destructors is small, there might be a more compact representation to store them than through a pointer.

Try to make the simplest and smallest number of optimisations needed to satisfy the requirements. Remember that keeping the code readable is of paramount importance! Don’t go XOR’ing pointers or anything until you actually need to⁷.

Since you are providing a low-level service on top of which many other services are expected to build, your implementation must be rock solid. You must provide a comprehensive set of tests that demonstrate the stability of your system, and the fulfilment of its specification. Use a combination of CUnit and valgrind to harden your implementation.

You must document code coverage for your tests.

Sticking with the \(o\) example from above, in this implementation, we need to look at all possible pointers in \(o\) – essentially all sizeof(void *) blocks that could possibly hold a pointer, e.g., all starting addresses \(o+i\) where \(i\) denotes all offsets into \(o\) where a pointer could be stored. (Note that alignment rules for structs impose restrictions on the starting addresses of fields based on the sizes of fields.)

For each possible pointer, we need to check whether the data we are looking at is a pointer or not. For example, let’s say that we look at sizeof(void *) bytes starting at \(o+4\) (e.g., void *possible_pointer = o + 4;) – how can we know if that is a pointer to something, or the list’s size field? One possibility to answer this question with relatively high probability is to keep track of where we have allocated data. Since all allocations go through our own functions, we can simply store that somewhere.

Now, the algorithm is essentially this:

1. For each possible starting location \(p\) of a pointer inside \(o\):
   1. check if \(p\) is an address where we currently have allocated memory
      1. if so, treat \(p\) as a valid pointer and call release() on it
      2. if not, ignore \(p\) and move on to the next \(p\)

This also requires:

• Whenever we allocate at an address \(p\), remember \(p\) in some collection \(A\).
• Whenever we free an object at an address \(p\), remove \(p\) from \(A\).
• Add the size of each object to its metadata.

Aside: We would like to store \(A\) in an efficient way. Naturally, we only optimise once we have something that works, so think of that second, not first. (A bitmap is a good idea.)

Feel free to improve on this technique if you want to!

A problem with the technique above is that it is approximate. If we happen to have an integer field in a place where a pointer could be stored, and the value of that integer happens to be a an address in \(A\), then we might cause an error in the program due to premature deallocation.

An alternative approach is to require the programmer to specify where in the struct pointers are stored⁸. This can be handled in several ways. One method is explained in painful detail in Project 2, another way is to add a metadata function that uses C macros and require that the programmer names the fields which contain pointers, e.g., like this:

// Register metadata about the pointer fields f1 .. fn of type type
register_typeN(type, f1, f2, ... fn); 
// Allocate using a registered type 
allocate_from_type(type);

If these calls are implemented as macros, they can be turned into calls to the “actual methods”, here named with prefixing __.

__register_typeN(#type, sizeof(type), offsetof(type, f1), offsetof(type, f2), ... offsetof(type, fn));
__allocate_from_type(#type);

Note that #int in a macro returns the string "int" so if I write

register_type2(list_t, first, last);
allocate_from_type(list_t);

and my macro is defined thus (fill in the blanks for allocate_from_type()):

#define register_type2(type, f1, f2) \
   __register_type2(#type, sizeof(type), offsetof(type, f1), offsetof(type, f2))

the resulting call after macro expansion is this:

__register_type2("list_t", 24, 0, 8);
__allocate_from_type("list_t");

if the size of list_t is 24 bytes and the offsets of the fields are 0 and 8 respectively. The offsetof() macro calculates the starting point of a field \(f\) in a type \(t\), so basically gives you the \(i\)’s discussed in the scanning strategy.

To support different numbers of fields, you either implement several functions for registering and allocating, e.g., register_type1(), register_type2(), …, register_typeN(), or use a trick to get overloading based on the number of arguments.

The key difficulty with this implementation is to store the metadata somewhere. For this, we can use the hash table from Assignment 1 where the keys are the types and the values is the size of the types the offsets of the pointer fields. Abstractly speaking, __register_type2("list_t", 24, 0, 8); will map “list_t” to [24, 0, 8] and  __allocate_from_type("list_t"); will look up 24 to know how many bytes to allocate.

Each object now needs to know its type so that when an object \(o\) is destroyed we can do the following:

1. Get \(o\)’s type \(t\)
2. Use \(t\) in the global hash map to get the offsets \(i_1...i_n\) of all the pointer fields in \(t\)
3. For each offset \(i\), call release(o+i).

To make memory leaks easier to detect, we should also remove the hash table etc. in the shutdown() function whose job it is to completely tear down the library and its associated data.

It should be possible to allocate an object and get a default destructor “for free”. What “for free” means depends on your implementation. Strategy 1 (scanning) is truly for free but may under rare circumstances not work out in practise. Strategy 2 (meta data) is a little harder on the programmer, but less brittle – unless you use union types, in which case you need to fall back on explicit constructors. Feel free to come up with alternative ways of implementing support for default constructors. Always start by doing the simplest thing possible and once that works, move to e.g. a more efficient or general solution.

Questions about stuff on these pages? Use our Piazza forum.

Want to report a bug? Please place an issue here. Pull requests are graciously accepted (hint, hint).

Nerd fact: These pages are generated using org-mode in Emacs, a modified ReadTheOrg template, and a bunch of scripts.

Ended up here randomly? These are the pages for a one-semester course at 67% speed on imperative and object-oriented programming at the department of Information Technology at Uppsala University, ran by Tobias Wrigstad.