Section 2: Arena allocator

Skills

• Demonstrate the impact of a dynamic memory allocators on application performance.
• Implement a simple arena allocator.
• Use unions and pointers.

Background

Linked Lists

Linked lists are different than arrays because they are dynamically allocated. When creating an array, you have to set aside a chunk of memory of a static size, but for a linked list, you just add elements in as you go.

In a singly linked list, each element of the list points to the next element of the list like so:

struct list_element {
    int id;
    char letter;
    struct list_element* next;
};

If you need to be able to find out what the previous element in the list is, you should use a doubly linked list. In a doubly linked list, each element of the list has two pointers: one to the previous element and one to the next element, like so:

struct list_element {
    int id;
    char letter;
    struct list_element* prev;
    struct list_element* next;
};

To keep track of a linked list, you really only need one pointer:

struct list_element* head;

head points to the first element of the list.

Unions

Unions and structs are defined in similar ways:

union info_union {
    short a;
    int b;
    char c[5];
};

The difference between union and struct is that the contents of a struct are stored one after another while a union can realistically only store one value at a time. Whatever is stored in this memory can be interpreted in different ways depending on the type, but the actual contents of the memory will be the same. What this means is that the contents of a union all share the same memory space. For example, for the above union info, this program:

union info_union info;
info.a = 72;
printf("%hi\n", info.a);
info.b = 73;
printf("%d\n", info.b);
strcpy(info.c, "abcd");
printf("%s\n", info.c);

outputs the following:

72
73
abcd

While this program:

union info_union info;
strcpy(info.c, "abcd");
info.b = 73;
info.a = 72;
printf("%hi\n", info.a);
printf("%d\n", info.b);
printf("%s\n", info.c);

outputs the following:

72
72
H

This is because the last value assigned in the union was to a, so the values of all elements of the union are dependent on the contents of the memory last defined. 72 is H in ASCII.

Assignment

Pull the latest version of the sections repository. If you have not cloned it yet, open terminal and enter

git clone <https://github.com/cs61/cs61-sections.git>

The cs61-sections/s02 directory contains a program called membench that benchmarks dynamic memory allocators. Your task is to complete the simple arena allocator in arena.c, making it beat the performance of malloc without leaking memory.

An arena (also called a zone, area, pool, memory context, etc.) represents a group of allocated objects. Often an arena holds related objects, such as a set of objects that all have the same type, or a set of objects that will all be freed at the same time. Special functions are used to allocate and free objects from the arena. These functions can be faster, more convenient, and sometimes safer than general-purpose malloc and free, because they can make assumptions about the kind of objects being allocated.

arena.c` contains the start of an arena allocator for `chunk

objects—but it leaks memory (in some senses), and is slower than it needs to be. You should fix this by introducing a free list. Your allocator should:

• Allocate a chunk in O(1) time.
• Free a chunk in O(1) time.
• Use memory proportional to the peak number of actively allocated chunks (rather than, say, the total number of allocated chunks).
• Run out of memory only if the system has no more memory available.

(More on arenas)

Test your arena allocator by running ./membench-arena with different arguments. The arguments are:

• -n N: Run N operations (default 50,000,000).
• -k K: Allocate at most K chunks at a time (default 4096). (The handout code only works when K=1.)
• -j J: Run with J threads (default 1).

And use command-line tools to test your allocator’s performance and memory usage. A particularly useful command is time, which comes in two varieties. Simply running time COMMAND reports the amount of time it took to run a command. (The real number is what you want; we’ll hear more about the others later). Running /usr/bin/time COMMAND reports more information, including memory usage. On my laptop:

$ /usr/bin/time ./membench-malloc -k1
1.72user 0.00system 0:01.72elapsed 99%CPU (0avgtext+0avgdata 5932maxresident)k
0inputs+0outputs (0major+90minor)pagefaults 0swaps

The maxresident number is the maximum amount of memory used in kilobytes; this program used about 6MB. And use make SANITIZE=1 or valgrind --tool=memcheck to check for memory leaks. (NB: make SANITIZE=1 only finds memory leaks on Linux.)

Comprehension questions

• The handout code leaks memory, but not in all senses. These questions concern exactly how it does so.
  • When can memory freed by membench_free be reused?
  • What function call makes arena memory reusable for other allocations that use the same arena?
  • What function call makes arena memory reusable for allocations that use other arenas, or that don’t use arenas at all?

• The handout code does not have O(1) allocation. What is the computational complexity of allocation in the handout code, and why?
  • What is the smallest change you can think of that would give the handout code O(1) allocation complexity?

Advanced features for optional after-class work

(1) Change the interface of membench_arena_new to take a size_t sz argument. An arena of size sz should allocate objects of size

sz`, meaning every object returned by `membench_alloc(arena)

should have size sz.

(2) Implement an arena allocator that can efficiently allocate objects smaller than a pointer (for instance, an allocator for single ints).