Heap-dynamic memory allocation for Quake III: Arena game engine

Purpose

To be a masochist.

Background

Quake III game engine lacks a malloc() function.

Advantages of no malloc():

• Enforced safer programming by requiring staticly-allocated memory.
• Increased speed by use of static allocation.
• Eliminated any kind of external memory fragmentation introduced by any heap-memory allocation mechanism.
• Avoided the inevitable headaches and problems of dealing with calculated array boundaries, dangling pointers, and pointers jumping off into hyperspace.

Disadvantages of no malloc():

• Arbitrarily limited array sizes.
• Hard-coded truncating of strings.
• Much wasted memory (internal fragmentation) to deal with "largest possible size".

Overview

The following functions become available to Quake III modifications:

• void *malloc(size_t size) -- allocates block of size bytes on the heap and returns pointer to the block.
• void *calloc(size_t nmemb, size_t size) -- allocates block of nmemb members each size bytes large. The content is zeroed before the pointer to the block is returned.
• void *realloc(void *ptr, size_t size) -- given old pointer ptr, attempt to resize the block to size bytes. Content is preserved as much as possible. The new location may or may not be the same location as ptr, so the return value of realloc() should be reassigned back to the same pointer variable (e.g. foo = realloc(foo, 1000);).
• void free(void* ptr) -- frees memory associated with malloc'd pointer ptr.
• void alloca(size_t size) -- this is supposed to act like a malloc with an automagic call to free() at the end of the function. The alloca implementation here fakes alloca by using a global ring buffer to store malloc calls, then free()'s malloc blocks as the ring buffer becomes full. All ring-stored blocks are free()d if size is a negative number. This function was added for Ogg Vorbis support.
• void alloca_reset() -- HACK. Forces the freeing of allocated blocks on the (fake)alloca ring buffer. Same as alloca(-1). This function was added for Ogg Vorbis support.

The functions with a return value will return NULL if memory could not be allocated. A common usage is:
char *s;
if (!s = malloc(1024))
    { return 0; }
strcpy(s, "What is six times nine?");
.... (and so on) ...

Programming Notes

This is not true heap memory. A large array of bytes is allocated in the data segment (i.e. a global variable), and then treated as [limited-size] heap memory. One heap-allocated block takes at least 32 bytes. This means with a 256KB heap, only a maximum of about 8000 malloc() calls can be made if no free() calls are ever made.

The heap-memory size (malloc arena) is changeable by altering MALLOC_ARENA in qmalloc.h.

The functions have not been thoroughly stress-tested. I have performed only basic correctness test. In particular, I have not tested these functions when the heap has actually depleted, so borderline cases when heap is almost full may start causing bizarre behavior (such as crashing).

(2002.02.20) The malloc strategy is somewhat saner than the previous version. In short, it's first-fit allocation with fixed-sized pages. Metadata and data are kept in separate arrays to minimize the impact of buffer overruns.

Minor change to speed up subsequent mallocs (by using a last-allocated pointer).
qmalloc3.c, qmalloc.h

This is the second version of malloc that adds alloca:
qmalloc2.c and qmalloc.h (same link as below, but updated file)

Since no files are actually patched per se, the two relevant files are posted as-is:
qmalloc1.c and qmalloc.h