Memory Management: Slab allocator

Last time we saw we could speed up memory allocations dramatically by using a pool allocator. I had a nagging feeling though. My pool allocator uses a std::vector, and it's doing all kinds of things behind the scenes. Resizing on the fly is cheating and undesired. Another thing that's certainly not right is that we're manually calling the destructor, while the object is alive and well, and present in the vector. This ultimately leads to the double destruction of objects once the pool is destructed; the destructor of the pool destructs the vector, which in turn destructs all objects it holds—effectively destructing objects twice. Double destruction is not a problem when your destructors are coded neatly, but it is something that normally is not supposed to happen. That's a big FIXME remark that needs to be addressed.

As a proposed fix for the problem, let's do away with std::vector altogether. Let's change the vector into a fixed size array. Upon initialization, the space for the array is preallocated, but no objects are created, no constructors are being run. When an object is allocated from the array, its constructor is invoked via placement new. When the (fixed size) array runs out space, allocate a new ‘subpool’ and chainlink them together as a linked list.
When an object is freed, you can look at the address and work out which array slot it came from. When all is well, manually call the destructor. If that pointer came from somewhere else, generate a fatal error.

This is a slab allocator. There is an opportunity here to implement garbage collection, and it's not as difficult as it may seem. All the allocator needs to do is keep track of which slots are allocated, and which slots are free—and it already needs to do that anyway. Once we get that right, garbage collection is simply destroying any objects that are still lingering around when the pool is destructed.

In order to track which slots are free, you could keep a small bitmap. If there are eight slots per slab, the bitmap is as small as one single byte. If you choose a single 64-bit int for a bitmap, the slab can hold 64 slots. That's a big slab. Personally, I went for sixteen objects in a slab.
Although a bitmap is perfectly okay for tracking free slots, you'll need to run through lots of bit shifting loops for the bookkeeping. The performance can be greatly improved by employing a different technique.

I know the Linux kernel internally uses a slab allocator, and therefore I took a peek in the book Understanding the Linux Kernel. It's in there alright, but unfortunately I couldn't make any sense of it. This stuff is hard. Or maybe not so much, I did find a rather good explanation on the web in the documentation on kernel.org.

What happens in the kernel is that each slab has a freelist, which is an array of integers (since we store only small numbers, these can be bytes rather than 64-bit ints). Each entry in the array represents an index to the next free slot. So, the index functions somewhat as a pointer to a list of free objects.
The final entry in the freelist array is -1, marking the end, when the slab runs out of memory. Additionally, there is an integer free_slot which denotes the first free slot. Since this is always the index of the first free slot, all the allocator does is access this number when an object is requested. It doesn't even have to search a free block, it already knows which object slot is free.
It's not described exactly in the kernel documentation, but at this point you should mark the freelist slot as being in use. Again, this is important for garbage collection.
[In the kernel source the member is actually called free, which in my code would inconveniently clash with the std::free() function, as well as my Slab<T>::free() method. Even though C++ has namespacing I still went with free_slot instead.]

For illustration purposes, consider what happens when we have a slab allocator with four object slots. Upon initialisation:

free_slot: 0
free_list: { 1, 2, 3, END }

Now, let's allocate an object.

free_slot: 1
free_list: { IN_USE, 2, 3, END }

Let's allocate one more.

free_slot: 2
free_list: { IN_USE, IN_USE, 3, END }

When memory is freed, look at the address to find out to which slab it belongs, and which slot it is. The free_slot pointer points at the first next free object; insert this number into the freelist slot. This effectively marks the slot as free again. If the slot was not marked as in use, something would be terribly wrong and the program should abort immediately. The free_slot pointer now becomes the slot number itself, thus the first free object is the object we just freed. Note how the freelist works in a LIFO fashion.

When we free the first allocated object, the result is:

free_slot: 0
free_list: { 2, IN_USE, 3, END }

If we want to garbage collect at this point, we can easily see that the object in slot #1 is still hanging around. We can garbage collect by freeing it. The situation then becomes as follows:

free_slot: 1
free_list: { 2, 0, 3, END }

The freelist now appears shuffled, but that doesn't matter; it operates as a LIFO queue. If we now allocate an object again, it fetches the object in slot #1.

Managing the freelist like this is deceivingly simple. This slab allocator greatly outperforms our previous solution.
Combining everything said here, the data structure in code is:

template <typename T>
struct Slab {
    Slab<T>* next;
    signed short free_slot;
    signed char free_list[NUM_OBJECTS];
    T objects[NUM_OBJECTS];
};

What I initially did here is use fixed size arrays. In the Linux kernel however, the only constant is the size of the memory page for the slab. It calculates how many objects of the desired object size can fit onto that page, taking into account the size of the metadata and necessary alignment. It crams as many objects as possible into a page, but note that the precise amount is different for every type T. For instance, many small objects of type A may fit into a single memory page, while another slab can hold a few large objects of type B.

The Linux kernel improves efficiency of the allocator even more by keeping three separate lists to manage slabs: lists for empty, full, and partially full slabs. On top of that, it keeps caches of slabs, so it always has quick access to them in case of need.
I simply couldn't resist the temptation, so the updated version is:

template <typename T>
struct Slab {
    Slab<T>* prev, *next;
    unsigned short num_objects, num_free;
    unsigned short free_slot;
    // compiler may insert padding here
    // free_list is directly behind the struct in memory
    // objects are behind the free_list in memory
};

Slab<T>* empty, *full, *partial;

[Now, num_objects isn't really a property of the slab; it's a property of the slab type. So why is it implemented as such? The reason is it's not a straightforward constexpr due to alignment, and the freelist having a maximum limit (we're using bytes as slot index, that's only 8 bits). The slab is written as a self-contained object allocator, and therefore it knows how many objects it can contain. In the Linux kernel, each slab also knows its object size. Since we're using C++ templates here, we can simply get away with sizeof(T).]

And you know what they say, safety first. The metadata is kept inside the slab, as well as the objects that are handed out to the application side of things. A badly behaving application may well overwrite other objects, or worse, our freelist. To guard against this, my slab allocator implements red zoning and object markers; magic numbers are inserted in between, and they are checked every single time.
For game code, the extra checks are #ifdef-ed out in a release build, but for other kinds of applications it's probably best to leave them in anyway.
Moreover, be mindful that a memory allocator should always zero the memory: not only when handing out objects, but also when they are freed. If you don't, you will get a massive Heartbleed disaster—the baddest security bug of 2014, the decade, and maybe of all computing history.

Happy holidays, and be careful with fireworks on New Year's Eve. You will need those fingers to do some more programming in 2015.

Memory Management: Pool Allocator

I want to get back to game programming, so I had another look at the quad-tree. I did a post on quad-trees in August last year. Remember that it's a technique for grouping objects together by chopping up 2D spaces into four quarters. Each interesting quarter is again divided into four parts. This basically goes on until max_depth is reached. The purpose of this space partitioning is grouping objects for the sake of collision testing; objects that are near each other may collide and are worth testing for collisions. Objects that are not near each other can not possibly collide, so we skip those when collision testing.

Having lots of moving objects, it's easiest to construct the quad-tree on every frame, or game tick. Now imagine that they are slow moving objects. If the objects are moving slowly, chances are that the quad-tree will look exactly the same at every frame. So why would you spend all that time building up and tearing down the same quad-tree on every frame? Unfortunately, we have to, and trying to bend an existing quad-tree into shape is much more difficult than simply rebuilding it from scratch. But we can optimize in another way.
The process of rebuilding the quad-tree takes a lot of malloc() and free() calls, and they are not cheap functions. If you want 60 fps, you will want to spend your time better than calling malloc() and free() all the time.
Rather than trying to reuse the entire quad-tree, let's reuse the timber that it's made of. Let's grab the objects that represent the quad-tree nodes and leafs from a pool allocator.

A pool allocator is simply a stack of pointers to objects in memory. Rather than freeing the memory, you push the object onto a stack. Next, when you need to allocate an object, you pop it from the stack. If the stack runs out of memory, you simply allocate a new object using malloc().
A pool allocator only allocates objects for a specific data type. All the objects in the pool are of the same type and size. By no means try to make it a generic allocator, or you'll be writing you own fragmenting memory manager.

In C, you might have:

static QuadTree *qt_pool[MAX_QT_POOL];
static int qt_pool_idx = 0;

QuadTree *qt_alloc(void);
void qt_free(QuadTree *);

Things get quite interesting when you move to C++. First of all, C++ has a std::vector class that you can use as a dynamic array, meaning that you can grow the pool as large as is necessary without having to worry too much about what the exact limit should be.
Secondly, C++ has template classes for generic programming. A templated Pool class can work with all kinds of types: QuadTrees, Monsters, Bullets, Explosions, etcetera.
Thirdly, C++ classes have constructors and destructors. In order to do this right, the pool allocator must properly construct and destruct objects when they are allocated and freed. In C++, placement new takes some already allocated memory, and calls the constructor for it. And in case you're wondering, manually calling a destructor requires no special trickery.

template <typename T>
class Pool {
public:
    // insert boilerplate here ...

    T* alloc(void) {
        if (v_.empty()) {
            // allocate new object
            return new T();
        }

        // take last object in pool
        size_t idx = v_.size() - 1;

        // use placement new to construct
        T* t = new (v_[idx]) T();

        // remove item from vector
        v_.erase(v_.begin() + idx);

        // return object pointer
        return t;
    }

    void free(T* t) {
        v_.push_back(t);
        // destruct t
        t->~T();
    }

private:
    std::vector<T*> v_;
};

This code works with raw pointers, and you can get philosophical and argue that these should be std::unique_ptr<T> objects, that are std::move()d around. And with C++14, you can use std::make_unique<T>().
[I didn't bother because personally, I'm no fan of std::unique_ptr. I think the syntax is horrid, and I wish they would have invented a new keyword instead for strong referencing pointers.]

Growing the vector means doing implicit memory allocations, something that we were trying to avoid in the first place..! Luckily, this will only happen the first time around; the pool will grow to a certain size and then stay that size as objects start being reused. An optimization would be to reserve chunks of space in advance, so that the vector need not be resized as often.
You can avoid working with pool arrays altogether, by chain linking objects to a free-list. This requires the objects to have a pointer member though (to make the chain link), and this breaks the generic nature of the Pool template class that is shown above. It would be an elegant solution for plain C however.

Round Balls and Flat Disks

I used to call gluSphere() to render simple planets in 3D space programs. For reasons beyond me, this function has been deprecated. Apparently, all GLU functions have been scrapped in the newer OpenGL standard. I've been told by an expert that OpenGL maintains backward compatibility by using version numbering, meaning that you should still be able to use old OpenGL 2, as long as you don't try to mix it with OpenGL 4 functions. GLU and GLUT are not really part of the OpenGL standard so that's where the story ends, I suppose. The problem is, I found myself being unable to compile older programs anymore after upgrading the operating system — totally unexpected, an unpleasant surprise. Searching for an answer, I found StackOverflow. The answer: “Do the math.”

I had to scratch my head a little there. I have to admit, it's been a while since I ‘did the math’ on anything, really. A visit to MathWorld turned up some nice formulas. Now, how to put that into code.

Implementing gluSphere()

As you can see in wireframe mode, the gluSphere is built up from quads. Clearly, triangle strips speed up the process. It should be possible to use a single triangle strip, but I didn't bother trying to figure that one out. So I went for stacked triangle strips that wrap around the sphere. This method uses slices and stacks (similar to lines of longitude and latitude) just like gluSphere() does.

Anyway, the math. We need to calculate all the vertices for the triangle strips that make up the sphere. A sphere is like rotating a vector 360 degrees around in a horizontal plane (left, right), while rotating a vector 180 degrees up and down in a vertical plane. We'll call the first angle alpha and the second beta. The size of the sphere is determined by radius r. Any point (x, y, z) on the sphere is given by:

    x = r ⋅ cos α ⋅ sin β
    y = r ⋅ cos β
    z = r ⋅ sin α ⋅ sin β

One caveat is that the angles should be given in radians rather than degrees for the C math library, so use M_PI. Another is the OpenGL coordinate system; you may have to work with -z, or like in my case, I had to exchange the Y and Z-axis to get the desired result.

Knowing this, calculating all vertices is easy. Setup a double loop that calculates all coordinates, taking into a account the number of stacks and slices that you wish to have.

    for(beta = 0.0; beta <= M_PI; beta += M_PI/num_stacks) {
        for(alpha = 0.0; alpha <= 2.0*M_PI; alpha += 2.0*M_PI/num_slices) {
            calculate x, y, z
            store in vertex array
        }
    }

Calculating Sphere Normals
The get good lighting on the sphere, we need to know the normal vectors. The normal at each vertex is given by normalize(x,y,z). That's easy.

Calculating Sphere Texture Coordinates
Having planets without texture is not fun. Texture coordinates run from 0.0 to 1.0.

    x = alpha / (2.0 * M_PI)
    y = (M_PI - beta) / M_PI

Implementing gluDisk()

For the rings of Saturn, it's easy to use a gluDisk. gluDisk() renders a flat disk, with an inner hole in the center. In math terms, the disk uses a circle formula, and there are two radii (one for the outer circle, one for the inner hole). So a gluDisk is really nothing but a single triangle strip that loops around, and its vertices are determined by two circles with radius r1 and r2.
The vertices are given by:

    // inner vertex
    ax = r1 ⋅ cos α
    ay = r1 ⋅ sin α
    az = 0.0

    // outer vertex
    bx = r2 ⋅ cos α
    by = r2 ⋅ sin α
    bz = 0.0

Calculating Disk Normals

The disk is really a 2D object in 3D space. The normals point to +Z, they are all defined as (0, 0, 1).

Calculating Disk Texture Coordinates
Texturing a disk is not at all like texturing a sphere. When you put a texture on a gluDisk, it's like sticking a label onto a DVD. You can take a rectangular image and put it onto the circular disk without distorting the image or wrapping it around the object. The texture is mapped to the bounding rectangle of the disk, which is two times the outer radius.

    x = ax / (2.0 * r2) + 0.5
    y = ay / (2.0 * r2) + 0.5

Do the same for bx and by. Note the plus one half, you want to be in the center of the texel or else OpenGL may show artifacts.

Implementing gluCylinder()

I did not implement gluCylinder(), but with the information given for gluDisk() you should be able to pull it off. It's just two circles and an added Z-axis.

Roundup
So, that's it. A bit of simple math, but still a sizable amount of work to get spheres going again in OpenGL. It's something that any serious 3D programmer should be able to do, but I still feel a bit bummed that they just deprecated those really useful functions.

On a final note I'd like to mention that there is another way of creating spheres, one that presumably looks better. Imagine an icosahedron, and subdividing each face into more triangles to enhance resolution. You can subdivide as many times as you like, and at a certain point it will be a good approximation of a sphere. This method is described in the Red Book.

How To strcpy()

I've written a lot about strcpy() already, the tiny but famous C library function for copying strings. There is a lot to say about its (in)security, and ways to improve on that. I didn't realize before that implementing your own strcpy() function could be part of a job interview for a programmer position. If I were asked to rewrite strcpy(), I would at least put in an abort() (for lack of exceptions) when passing in a NULL pointer. Moreover, I would add a length parameter for doing bounds checking — albeit that might be considered cheating, because it would change the function declaration; the signature of the function.

Rather than zooming in on this rather old topic, I'm going to be lazy for once and just link to this excellent post that tells the story of the solutions given by job applicants for the problem of writing your own strcpy() function. It's a must read, hilarious, but also somewhat alerting.

How Do I Copy Thee? Let Me Count the Ways by David Avraamides