Quake++: Memory (and STL Allocators)

The original Quake uses a variety of custom memory allocators to reduce fragmentation and keep the game’s memory usage contiguous and fixed. Most of the source code for these allocators can be found in zone.h and zone.c, with the exception of some more specialized memory handlers.

Quake splits one initial chunk of memory allocated at start-up into different regions used for different types of allocations. Overall, it treats the block as a double-ended stack allocator that returns what it calls “Hunks”. The first Hunk allocated is a fixed size block that is labelled “Zone” memory. This Zone Hunk is accessed by special routines, primarily to allocate dynamic strings and small buffers. The Zone is treated as a free list with each memory block being preceded by a header containing information about the block’s size, allocation status, and a pointer to the subsequent block.

The rest of the low Hunk is initially filled with start-up allocations, including resources from disk (PAK files), models, textures, etc. The host then grabs a marker to the top of the stack before performing any client/server allocations. This lets it rapidly clear memory when starting up a new client or server. The high Hunk is used for temporary allocations, and stores the video buffer when using the software rendering engine.

The remaining memory in-between the low and high Hunks is used as Cache. Any Hunk allocations made after a Cache allocation will clear the Cache up to that point, so it’s pretty volatile. As far as I can tell, the Cache isn’t used terribly often, other than to temporarily load images and audio.

In addition to the main allocators, there is also a class called sizebuf_t that is used for a fixed-size buffers. These are allocated off of the low Hunk and are used throughout the game to handle dynamically sized data.

STL Allocators

While digging into Quake’s allocation system I kept wondering to myself what the modern C++ way to handle allocations is. It would be great to wrap the custom Quake allocation routines with a custom allocator to avoid manually requesting/freeing memory every time I construct a new object. It would also be great to be able to leverage the STL containers to safely and efficiently handle strings, linked lists, etc. Turns out that is not a simple question to answer, especially given the ever-changing landscape of STL allocators.

Pre-C++11

The STL defines a default allocator (std::allocator) that is used by all STL containers. This is a wrapper around the new operator (subject to implementation) which allocates the requested number of bytes off of the free store. This covers most usage cases, so it is pretty invisible to anyone diving into C++ for the first time. However, since game engines tend to want tight control over memory allocations (especially for consoles where a virtual memory system isn’t always guaranteed) developers usually aim to implement a custom allocator. In order to use a custom allocator with an STL container (say std::string or std::vector) you pass the allocator class as a template parameter like so: std::vector<int, MyCustomAllocator>. Prior to C++11, this custom allocator had some strict requirements about its implementation and design. It used to require a whole slew of type definitions and aliases, and it had to be stateless - aka. one instance had to be indistinguishable from another. Allocators also had to support rebinding - converting from an allocator of one type to another. A custom allocator looked something like this (with credits to Lai Shiaw San Kent):

template<typename T>
class Allocator {
public :
    //    typedefs
    typedef T value_type;
    typedef value_type* pointer;
    typedef const value_type* const_pointer;
    typedef value_type& reference;
    typedef const value_type& const_reference;
    typedef std::size_t size_type;
    typedef std::ptrdiff_t difference_type;

public :
    //    convert an allocator<T> to allocator<U>
    template<typename U>
    struct rebind {
        typedef Allocator<U> other;
    };

public :
    inline explicit Allocator() {}
    inline ~Allocator() {}
    inline explicit Allocator(Allocator const&) {}
    template<typename U>
    inline explicit Allocator(Allocator<U> const&) {}

    //    address
    inline pointer address(reference r) { return &r; }
    inline const_pointer address(const_reference r) { return &r; }

    //    memory allocation
    inline pointer allocate(size_type cnt,
       typename std::allocator<void>::const_pointer = 0) {
      return reinterpret_cast<pointer>(::operator new(cnt * sizeof (T)));
    }
    inline void deallocate(pointer p, size_type) {
        ::operator delete(p);
    }

    //    size
    inline size_type max_size() const {
        return std::numeric_limits<size_type>::max() / sizeof(T);
 }

    //    construction/destruction
    inline void construct(pointer p, const T& t) { new(p) T(t); }
    inline void destroy(pointer p) { p->~T(); }

    inline bool operator==(Allocator const&) { return true; }
    inline bool operator!=(Allocator const& a) { return !operator==(a); }
};    //    end of class Allocator

Post-C++11

In C++11, allocators got a nice buff in the form of std::allocator_traits, which meant custom allocators no longer needed the laundry list of type definitions in order to be handled correctly. Instead, std::allocator_traits would provide most of them and serve as the access point for the allocator’s functionality. Allocators could now be stateful too, so containers could keep track of their own instance of the allocator. Now a programmer could create a custom allocator, MyCustomAllocator in only a few lines, create an instance, and then pass it to containers allocating from the instance:

template <class T>
class MyCustomAllocator {
    using value_type = T;

    MyCustomAllocator();

    template <class U>
    MyCustomAllocator(const MyCustomAllocator<U>& other);

    T* allocate(std::size_t n);
    void deallocate(T* ptr, std::size_t n);
};
template <class T, class U>
bool operator==(const MyCustomAllocator<T>&, const MyCustomAllocator<U>&);
template <class T, class U>
bool operator!=(const MyCustomAllocator<T>&, const MyCustomAllocator<U>&);

// Example of using MyCustomAllocator
using MyString = std::basic_string<char, std::char_traits<char>, MyCustomAllocator<char>>;

MyCustomAllocator<char> mca{ memory_block };
MyString myString1{ "some value", mca };

Another nice addition in C++11 was the scoped_allocator_adaptor which lets containers automatically determine the allocator to use for elements that are also containers. In a nice example on Stack Overflow by Jonathan Wakely, he shows how the scoped_allocator_adaptor automatically infers the elements allocator saving on extra, error-prone, code. Before scoped_allocator_adaptor we would have to do something like:

template<typename T>
  using Allocator = SomeFancyAllocator<T>;
using String = std::basic_string<char, std::char_traits<char>, Allocator<char>>;
using Vector = std::vector<String, Allocator<String>>;

Allocator<String> as( some_memory_resource );
Allocator<char> ac(as);
Vector v(as);
v.push_back( String("hello", ac) );
v.push_back( String("world", ac) );

With scoped_allocator_adaptor, we can instead do:

template<typename T>
  using Allocator = SomeFancyAllocator<T>;
using String = std::basic_string<char, std::char_traits<char>, Allocator<char>>;
using Vector = std::vector<String, std::scoped_allocator_adaptor<Allocator<String>>>;

Allocator<String> as( some_memory_resource );
Allocator<char> ac(as);
Vector v(as);
v.push_back( String("hello") ); // no allocator argument needed!
v.push_back( String("world") ); // no allocator argument needed!

Jonathan also points out that you can drop the String(...) in the last two lines since std::basic_string is implicitly constructed from const char*.

Everything now looks fine-and-dandy, until we run into the problem that containers of identical types aren’t compatible. For example, I can create instances of MyString (allocated off of a custom free list) but I can’t use them in conjunction with a std::string (allocated off of the default std::allocator) since the compiler treats them as completely different types. The only workaround I could figure out was to construct new strings from my custom allocated one through std::string(myString1.c_str()), which incurs additional allocations, and feels like a hack.

C++17

Luckily, the issue of incompatible types was caught by the C++ standards committee and an updated design was added to the C++17 spec. The solution adds a polymorphic_allocator class template that allows containers with the same underlying type, but different allocators, to be used together. C++17 also adds aliases for STL containers that use the polymorphic allocator so that we can use the standard STL containers in harmony with the custom allocated versions.

Back to Quake

So where does all this leave things for Quake? Since C++17 isn’t here yet, it means we can get most of the way towards implementing custom allocated types, with a few rough edges around interacting with the STL. For example, I created a Z_string class that is just an alias for std::basic_string<char, std::char_traits<char>, Zone_allocator<char>>. This ensures all instances of these strings are zone allocated, avoiding the messy C-style:

var->string = reinterpret_cast<char*>(Z_Malloc(length_of_new_string));
std::copy(std::begin(new_string), std::end(new_string), std::begin(var->string));

and replacing it with:

var->string = new_string;

Like I mentioned before, we still have the ugliness of getting Z_string to work with std::string, but before long that should be smoothed over. As I dig through more of the Quake source I’m hoping to find more opportunities to leverage custom allocators. The biggest benefit is adhering to the Resource Acquisition is Initialization (RAII) ideal to avoid the mess of aliasing blocks of bytes into their desired types when creating them.