hiv - hecc's standard library

hiv (as opposed to std) is hecc's standard library: a reimplementation of the C standard library that makes explicit the two things about memory that C hides. It is written in hecc, so its functions carry ownership decorators natively, and because hecc transpiles to ordinary C, hiv is usable by plain C projects too.

hiv is one half of a pair. Its companion, hecc, is an experimental C compiler that adds static ownership, borrows, and bounds analysis to C; hiv is the standard library built to pair with it. That relationship is described near the end.

The standard library hides two different things about memory, and hiv addresses them separately. Consider strdup():

char* copy = strdup(string);

The first thing hidden is ownership: nothing in that call says the caller now owns the returned allocation and must release it. The second is the allocator: strdup uses whatever the library's global heap is, and a program with its own arena or pool cannot redirect this one call without writing another version of the function.

Two variants

hiv gives every memory-touching function two forms.

The default form keeps the C signature and adds ownership information:

char* copy = strdup(string);

The signature is unchanged, so this compiles in any C program. Built with hecc the function carries ownership decorators: the result is owned, the caller must release it, and hecc can check that.

The _with form takes an explicit allocator as its first argument:

char* copy = strdup_with(&allocator, string);

Now the caller also decides where the memory comes from. Every function that allocates or frees has both forms -- malloc / malloc_with, strdup / strdup_with, free / free_with, and so on. Functions that touch no memory have neither; they stay exactly as they are.

Ownership is explicit for everyone by default; the allocator is explicit when the caller asks for it. That matches how hecc works: the default is drop-in, and the explicit form is an opt-in upgrade.

The default allocator

A default call does not name an allocator; it uses a program-wide default. The allocation is still visible, since you called malloc or strdup as in ordinary C, and so is the ownership, since the decorators say who owns a result and what a free consumes and hecc checks it. Only the choice of allocator is implicit, and _with makes it explicit wherever you want it.

The program sets the default allocator once. A hosted program can leave it as the conventional heap. A freestanding one, a kernel or bare metal, has no global heap to assume, so it installs a default before using the default forms, or uses _with throughout.

allocator_t

Allocators are represented by allocator_t. An allocator provides the operations used to allocate, resize, and release memory:

struct allocator_t
{
    void* (*alloc)(struct allocator_t* allocator, size_t size);
    void* (*realloc)( struct allocator_t* allocator, void* buffer, size_t size);
    void (*free)( struct allocator_t* allocator, void* buffer);

    void* (*realloc_sized)(struct allocator_t* allocator, void* buffer, size_t old_size, size_t new_size);
    void (*free_sized)(struct allocator_t* allocator, void* buffer, size_t size);
};

The callbacks are used to implement an allocator. A program writing its own allocator provides those functions:

void* my_alloc(struct allocator_t* allocator, size_t size)
{
    // ...
}

and then constructs an allocator using them:

struct allocator_t allocator =
{
    .alloc = &my_alloc
};

Code using the allocator does not normally call its callbacks directly. The callbacks are the implementation of the allocator, while the rest of the program uses the standard interface -- the _with form when it wants this particular allocator:

void* buffer = malloc_with(&allocator, 1024);

or installs it as the program default, so the ordinary malloc(1024) routes through it. Either way, an allocator can be backed by anything without changing the code using it: a conventional heap, a fixed memory region, an arena, a pool, or something specific to the environment. As far as hiv is concerned, it only needs an implementation of the required operations.

malloc() and free()

The default forms look exactly like C, and carry ownership:

void* buffer = malloc(1024);   /* default allocator; the result is owned */

/* ... */

free(buffer);                  /* consumes ownership */

The _with forms name the allocator:

void* buffer = malloc_with(&arena, 1024);

/* ... */

free_with(&arena, buffer);

Multiple allocators coexist through the _with forms without touching any global state:

void* temporary = malloc_with(&temporary_allocator, 1024);
void* permanent = malloc_with(&permanent_allocator, 1024);

/* ... */

free_with(&temporary_allocator, temporary);
free_with(&permanent_allocator, permanent);

The two allocations can have completely different implementations. temporary_allocator might allocate from an arena while permanent_allocator uses a conventional heap. Neither becomes special to the rest of the program simply because it was used for one allocation.

Memory must be released through the allocator it came from: something allocated with the default malloc is freed with the default free, and something allocated with malloc_with(&a, …) is freed with free_with(&a, …). hiv does not store the allocator inside the allocation so that free can recover it later; keeping allocation and release on the same allocator is the programmer's responsibility, exactly as knowing where a pointer came from already is. The ownership decorators are what let hecc check that the release happens at all.

Sized operations

A program will often know the size of a buffer even when the function receiving the pointer does not. Consider:

char buffer[6] = "hello";

The program knows that buffer occupies six bytes. A normal string function only receives a pointer:

strlen(buffer);

and has no information about where the underlying object ends. It reads until it finds a null terminator.

hiv provides _sized variants for operations where knowing the size of a buffer is useful:

strdup_sized(buffer, sizeof(buffer));

The size passed to a sized operation is the exact size of the buffer in bytes. It is not a string length and does not imply anything about the contents of the buffer. A six-byte buffer may contain:

h e l l o \0

but it may just as easily contain six non-null bytes. A sized string operation knows that it may inspect six bytes and no more. If it needs to find a null terminator, it can determine whether one exists within those bounds instead of continuing into unrelated memory.

_sized and _with are independent suffixes that compose. The default sized form takes just the size; the explicit form takes the allocator too:

free_sized(buffer, size);
free_with_sized(&allocator, buffer, size);

Likewise, resizing an allocation can provide both the old and new sizes:

buffer = realloc_sized(buffer, old_size, new_size);
buffer = realloc_with_sized(&allocator, buffer, old_size, new_size);

The ordinary versions still exist for when the size is not available. The sized versions exist because the size is sometimes information the caller already has and the allocator can make use of it directly.

Strings

A C string is a char* and a set of conventions the type does not state: NUL-terminated, of some length, owned by someone. Everything that goes wrong with C strings lives in what the char* leaves unsaid -- whether the buffer is terminated, how big it is, and who frees it. hiv does not replace it with a new string value. A string stays a char*, so every existing function still takes one and the representation is unchanged; what hiv adds is the missing facts, using machinery hecc already has.

Three of the four facts are not string-specific and are already tracked. Ownership -- an owned string is freed when its owner ends, a borrowed one is not -- is hecc's ordinary ownership, the same as any char* from strdup. Capacity -- how many bytes the buffer holds -- is bounds, the same extent the _sized forms already pass around. Maybe-null is nullability. Only the fourth is specific to strings: NUL-termination, whether the buffer is known to hold a terminator within its bounds. That is the invariant C never checks, and hecc tracks it as one more fact alongside ownership and bounds.

string is hiv's name for a char* carrying those facts -- owned, NUL-terminated, capacity-known -- and it erases back to char*:

string s = strdup("hello");   /* owned, NUL-terminated */

A function that only reads takes a borrow, and can require the terminator it depends on:

size_t length(const string s);   /* borrows s; requires it terminated */

Handing length a buffer that is not known-terminated is then a provable mistake, the same kind hecc flags for a use-after-free, instead of a read that wanders off the end of the allocation.

The distinction that catches the most bugs is capacity versus length. Capacity is the size of the buffer and is static -- it is bounds. Length is the bytes up to the NUL and is runtime data. hiv tracks capacity at compile time and the terminated fact as a yes or no; the length itself, and the length <= capacity that must hold, are what a safe build checks at runtime. String literals need no checking: "hello" is const, terminated, of known length, with a static origin, all known already.

A growable string is the same char* owned, resized through the round-trip owner parameter:

bool append(string <-> s, const char* tail);

Ownership of the buffer leaves and returns through s, so a reallocation is accounted for, exactly as with any other growing allocation.

Two things hiv's string is deliberately not. It is not a fat pointer -- no { ptr, len } value -- because that would change the representation, break the C ABI, and stop being a char*; the length rides in the bounds facts and the terminator, not in a wider value. And it is not a Unicode type. A string is a byte buffer with a termination invariant; UTF-8 is something a library does to those bytes, not what the type is. Keeping it byte-level is what keeps it C.

Memory safety

Making memory operations explicit does not make C memory-safe by itself. A program can still dereference an invalid pointer, write past the end of an array, use memory after it has been released, or otherwise violate C's memory rules. hiv does not, on its own, change the language's pointer model or introduce compile-time ownership tracking -- that is hecc's role, and hiv is written to plug into it (see hecc below).

What it does provide is a common interface through which the standard library's memory operations can be controlled. A normal libc uses its own allocator internally, so even a program with a custom allocator gains nothing from a call like strdup(string) -- the allocation belongs to the libc's own system. In hiv, the allocator is either the program default or the one passed to a _with call, and in both cases it is an allocator the program chose. That allocator can do more than return memory: it can validate operations, track allocations, enforce limits, or deliberately change how memory is handled in order to detect bugs.

A debugging allocator, for example, can keep track of every allocation it owns. When memory is released:

free_with(&debug_allocator, buffer);

it can verify that buffer is actually one of its allocations, detecting invalid frees, double frees, and attempts to release memory through the wrong allocator. Installed as the program default, the same allocator checks the ordinary free(buffer) calls too, so a codebase does not have to be rewritten to _with forms to get the checking.

Sized operations give the allocator more to validate. Given:

free_with_sized(&allocator, buffer, 128);

the allocator receives both the address being released and the size the caller believes belongs to that allocation, and an allocator that tracks its allocations can verify it rather than ignore it. The same applies to realloc_with_sized(), where the allocator can confirm that old_size describes the allocation being resized.

An allocator can also make bugs easier to catch -- poisoning released memory, quarantining it instead of reusing it immediately, or placing it behind inaccessible pages on systems with virtual memory, so an out-of-bounds access faults instead of quietly corrupting another allocation. And it can enforce policy unrelated to debugging: a limited allocator caps how much memory a part of a program may use; an arena makes every allocation performed during an operation share one lifetime; separate allocators represent separate memory domains:

char* temporary = strdup_with(&temporary_allocator, string);
char* request_copy = strdup_with(&request_allocator, string);

The important part is that the standard library participates in this model. Without allocator-aware library functions, calls into the standard library escape the program's memory model and allocate somewhere else. hiv provides a common point through which those operations pass, so the same interface works with an ordinary allocator, an arena, a debugging allocator, a guarded allocator, or one that enforces limits -- the meaning of strdup() never changes, only where its memory comes from and what is checked along the way. This makes memory-safety mechanisms composable with the standard library instead of requiring it to be rewritten for every allocator, and it pairs with hecc: static ownership from the compiler, runtime checking from a guarding allocator.

hecc

hiv and hecc are two halves of the same experiment. hecc is an experimental C compiler that adds static ownership, borrows, and bounds analysis to C; hiv is the C standard library built to be used with it, and is itself written in hecc.

Because it is written in hecc, hiv's functions carry hecc's ownership decorators as part of their source -- which arguments are consumed, which returns are owned, which are borrows and from where -- rather than having them bolted on afterward. This matters because hecc's analysis is only as good as the contracts on the functions a program calls, and most of those calls land in the standard library. A libc hecc cannot see into is a boundary the analysis goes dark at; hiv is that boundary made explicit. And since hecc transpiles to ordinary C, hiv is not restricted to hecc users: the transpiled output is a normal C library.

The layers are complementary. hecc tracks who owns and who frees; hiv states the ownership of every call and makes the allocator reachable through _with. The _sized operations give hecc's bounds analysis the extents it wants. And an hiv guarding allocator -- poisoning freed memory, quarantining, guard pages, double-free detection -- is the runtime safety net for exactly the code hecc's static analysis cannot prove. Neither requires the other, but together they are one memory story: static ownership and bounds from hecc, explicit allocation and runtime checking from hiv.

Library functions

The two forms are added only where they mean something. Functions that neither allocate nor release memory stay exactly as they are, with no _with variant:

memcpy(destination, source, size);
memset(destination, value, size);
strlen(string);
strcmp(left, right);

There is no allocator involved in copying bytes between existing buffers, so nothing would be made more explicit. Functions that do perform a memory operation get both forms -- a default that carries ownership and a _with that also names the allocator. This distinction is what keeps hiv from turning into a different version of C. Most of the standard library still looks like the standard library; the interfaces grow a second form only where the library actually touches memory.

Objects and allocators

Passing an allocator to a function does not associate that allocator with the object it returns. If a file is opened with a particular allocator:

FILE* file = fopen_with(&allocator, "example.txt", "r");

hiv does not keep allocator inside file so it can silently use it later. A later operation that needs to release memory is given the allocator again:

fclose_with(&allocator, file);

Remembering the allocator inside the object would make later memory operations implicit again -- fclose(file) could free memory without anything at the call site showing which allocator was involved. hiv avoids that: the allocator is part of the operation, not hidden state on the object. An object opened with a _with form is closed with the matching _with; an object opened with the default form is closed with the default. The allocator is supplied when an operation needs it, not kept around for convenience.

Portability

hiv is intended to implement the ISO C standard library rather than POSIX. It should work in a conventional hosted program, but that is not the only target: custom operating systems, kernels, freestanding programs, and bare-metal environments should be able to use it without first providing a POSIX-compatible runtime.

This is also why the allocator model matters. hiv cannot assume a conventional heap already exists. A bare-metal program may have a fixed block of RAM; a kernel may have its own page allocator; another environment may want an arena for everything. In such environments there is no sensible program-wide default, so the default forms are unavailable until one is installed, and code uses _with to name the allocator appropriate to the memory it has. In a hosted program the default is simply the conventional heap and the default forms work out of the box. Either way, hiv does not decide what the environment's memory system looks like.

Why reimplement libc?

There are much easier ways to use a custom allocator. A program can write allocator-aware functions, use its own allocation API, or replace the global allocator. Reimplementing an entire standard library is obviously excessive if the only goal is to allocate memory differently.

The interesting part is applying the idea consistently. Writing this:

char* strdup(const char* string);                          /* default: carries ownership */
char* strdup_with(struct allocator_t* allocator, const char* string);

is trivial. Applying the same rule to an entire standard library is not. Some functions obviously allocate because they return a newly allocated pointer. Others create objects with internal state, allocate while performing an operation, or release memory as part of destroying something. Once the rule is applied everywhere, the less obvious cases become the interesting ones.

hiv is mostly an attempt to find those cases and figure out whether making them explicit produces a library that is actually nicer to use. The result might be more annoying than a normal libc in places, and that is part of the experiment too. The point is not verbosity for its own sake, but to see whether a standard library can expose its memory behaviour -- ownership always, the allocator on demand -- without losing the simplicity that makes C's library useful in the first place.

Ownership is never hidden, and the allocator is never out of reach.