hiv - hecc's standard library

hiv (as opposed to std) is hecc's standard library. it's a reimplementation of the c standard library that makes two things about memory explicit, two things c normally keeps hidden. it's written in hecc, so its functions carry ownership decorators natively. and because hecc transpiles to ordinary c, plain c projects can use hiv too.

hiv is half of a pair. the other half is hecc, an experimental c compiler that adds static ownership, borrows, and bounds analysis to c, and hiv is the standard library built to go with it. there's more on how the two fit together near the end.

the standard library hides two separate things about memory, and hiv deals with them separately. take strdup().

char* copy = strdup(string);

the first hidden thing is ownership. nothing in that call tells you the caller now owns the returned allocation and has to 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 can't redirect this one call without writing its own version of the function.

two variants

every function in hiv that touches memory comes in two forms.

the default form keeps the c signature and adds ownership information.

char* copy = strdup(string);

the signature hasn't changed, so this compiles in any c program. built with hecc, though, the function carries ownership decorators. the result is owned, the caller has to release it, and hecc can check that it does.

the _with form takes an explicit allocator as its first argument.

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

now the caller also gets to decide where the memory comes from. every function that allocates or frees has both forms (malloc and malloc_with, strdup and strdup_with, free and free_with, and so on). functions that don't touch memory have neither and stay exactly as they are.

so ownership is always explicit, and the allocator is explicit when you ask for it. that's the same way hecc works. the default drops in, and the explicit form is an upgrade you opt into.

the default allocator

a default call doesn't name an allocator. it uses a program-wide default instead. the allocation is still visible, since you called malloc or strdup like you would in ordinary c. the ownership is visible too, since the decorators say who owns a result and what a free consumes, and hecc checks it. the only implicit part is which allocator gets used, and _with makes that explicit wherever you want.

the program sets the default allocator once. a hosted program can just leave it as the usual heap. a freestanding one (a kernel, or bare metal) has no global heap to assume, so it either installs a default before using the default forms or uses _with everywhere.

allocator_t

allocators are represented by allocator_t. an allocator provides the operations for allocating, resizing, and releasing 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 how you implement an allocator. if you're writing your own, you write those functions.

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

then you build an allocator out of them.

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

code that uses the allocator doesn't normally call the callbacks directly, since they're the allocator's implementation. the rest of the program goes through the standard interface. it either uses the _with form when it wants this specific allocator

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

or installs it as the program default, so a plain malloc(1024) goes through it. either way, an allocator can be backed by anything without changing the code that uses it. it could be a normal heap, a fixed region of memory, an arena, a pool, or something specific to the environment. all hiv cares about is that the required operations are implemented.

malloc() and free()

the default forms look exactly like c, and they 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);

several allocators can live side by side 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 hand out memory from an arena while permanent_allocator uses a normal heap. using one of them for one allocation doesn't make it special to the rest of the program.

memory has to go back to the allocator it came from. something allocated with the default malloc is freed with the default free, and something from malloc_with(&a, …) is freed with free_with(&a, …). hiv doesn't stash the allocator inside the allocation so free can find it later. keeping allocation and release on the same allocator is the programmer's job, the same way knowing where a pointer came from already is. what the ownership decorators add is that hecc can check the release actually happens.

sized operations

a program often knows how big a buffer is even when the function receiving the pointer doesn't. say you have this.

char buffer[6] = "hello";

the program knows buffer is six bytes. a normal string function only gets a pointer

strlen(buffer);

and has no idea where the underlying object ends. it just reads until it hits a null terminator.

hiv has _sized variants for the operations where knowing the buffer size helps.

strdup_sized(buffer, sizeof(buffer));

the size you pass to a sized operation is the exact size of the buffer in bytes. it isn't a string length and says nothing about what's in the buffer. a six-byte buffer might hold this

h e l l o \0

but it could just as easily hold six bytes with no null in them. a sized string operation knows it can look at six bytes and no more. if it needs a null terminator, it can check whether there is one inside those bounds instead of running off into unrelated memory.

_sized and _with are independent suffixes, and they compose. the default sized form takes just the size, and the explicit one takes the allocator as well.

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

resizing an allocation can pass both the old and the new size the same way.

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

the plain versions are still there for when you don't have the size. the sized ones exist because sometimes the caller already knows the size, and the allocator can use it directly.

strings

a c string is a char* plus a bunch of conventions the type never states. it's nul-terminated, it has some length, and somebody owns it. everything that goes wrong with c strings comes from what the char* leaves out, which is whether the buffer is terminated, how big it is, and who frees it. hiv doesn't replace it with a new string type. a string is still a char*, so every existing function still takes one and the representation doesn't change. what hiv adds is the missing facts, using machinery hecc already has.

three of those four facts aren't specific to strings, and hecc already tracks them. ownership (an owned string gets freed when its owner ends, a borrowed one doesn't) is just hecc's normal ownership, same as any char* you get 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, and that's nul-termination, whether the buffer is known to have a terminator inside its bounds. c never checks that, and hecc tracks it as one more fact next to ownership and bounds.

string is hiv's name for a char* that carries those facts (owned, nul-terminated, known capacity), and it erases back to char*.

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

a function that only reads takes a borrow, and it can require the terminator it relies on.

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

passing length a buffer that isn't known to be terminated is then a provable mistake, the same kind of thing 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. it's static, and it's bounds. length is the number of bytes up to the nul, and it's runtime data. hiv tracks capacity at compile time and tracks termination as a yes or no. the length itself, and the length <= capacity rule that has to hold, are what a safe build checks at runtime. string literals don't need checking at all. "hello" is const, terminated, and has a known length and a static origin, so everything about it is already known.

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

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

ownership of the buffer leaves through s and comes back through s, so a reallocation is accounted for just like any other growing allocation.

there are two things hiv's string intentionally isn't. it's not a fat pointer. there's no { ptr, len } value, because that would change the representation, break the c abi, and stop it being a char*. the length lives in the bounds facts and the terminator, not in a wider value. it's also not a unicode type. a string is a byte buffer with a termination invariant, and utf-8 is something a library does with those bytes, not what the type is. keeping it at the byte level is what keeps it c.

memory safety

making memory operations explicit doesn't make c memory-safe on its own. a program can still dereference a bad pointer, write past the end of an array, use memory after releasing it, or break c's memory rules in plenty of other ways. hiv by itself doesn't change the language's pointer model or add compile-time ownership tracking. that's hecc's job, and hiv is written to plug into it (see hecc below).

what hiv does give you is one interface that the standard library's memory operations all go through, and that you control. a normal libc uses its own allocator internally, so even if your program has a custom allocator, a call like strdup(string) won't use it. that allocation belongs to libc. in hiv the allocator is either the program default or the one passed to a _with call, and either way it's one the program picked. that allocator can do more than hand out memory. it can validate operations, track allocations, enforce limits, or change how memory is handled on purpose to shake out bugs.

for example, a debugging allocator can keep track of every allocation it owns. when memory is released

free_with(&debug_allocator, buffer);

it can check that buffer really is one of its allocations, which catches invalid frees, double frees, and memory being released through the wrong allocator. install it as the program default and it checks the plain free(buffer) calls too, so you don't have to rewrite a codebase to use _with forms just to get the checking.

sized operations give the allocator more to check. given this call

free_with_sized(&allocator, buffer, 128);

the allocator gets both the address being released and the size the caller thinks the allocation is, and an allocator that tracks its allocations can verify that instead of ignoring it. realloc_with_sized() works the same way, where the allocator can confirm that old_size matches the allocation being resized.

an allocator can also make bugs easier to catch. it can poison released memory, quarantine it instead of reusing it right away, or put it behind inaccessible pages on systems with virtual memory, so an out-of-bounds access faults instead of quietly corrupting some other allocation. it can also enforce policy that has nothing to do with debugging. a limited allocator caps how much memory part of a program can use. an arena gives every allocation made during an operation the same lifetime. separate allocators can stand for separate memory domains.

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

what matters is that the standard library takes part in all of this. without allocator-aware library functions, every call into the standard library escapes the program's memory model and allocates somewhere else. hiv gives those operations one place to pass through, so the same interface works with a normal allocator, an arena, a debugging allocator, a guarded one, or one that enforces limits. what strdup() means never changes. only where its memory comes from and what gets checked along the way does. that lets memory-safety tools work with the standard library instead of needing it rewritten for every allocator, and it pairs well with hecc. the compiler does static ownership, and a guarding allocator does runtime checking.

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 it's written in hecc itself.

since it's written in hecc, hiv's functions have hecc's ownership decorators right in their source (which arguments are consumed, which returns are owned, which are borrows and from where) instead of having them bolted on later. that matters because hecc's analysis is only as good as the contracts on the functions a program calls, and most of those calls end up in the standard library. a libc that hecc can't see into is a spot where the analysis goes blind, and hiv makes that boundary explicit. and because hecc transpiles to ordinary c, hiv isn't only for hecc users. the transpiled output is a normal c library.

the two complement each other. hecc tracks who owns what and who frees it. 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 needs. an hiv guarding allocator (poisoning freed memory, quarantining, guard pages, double-free detection) is the runtime safety net for the code hecc can't prove anything about statically. neither one needs the other, but together they cover memory from both sides, with static ownership and bounds from hecc and explicit allocation and runtime checks from hiv.

library functions

the two forms only get added where they mean something. functions that don't allocate or release memory stay the same, with no _with variant.

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

copying bytes between buffers that already exist doesn't involve an allocator, so there's nothing to make 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. that's what keeps hiv from turning into a different flavour of c. most of the standard library still looks like the standard library, and an interface only grows a second form where the library actually touches memory.

objects and allocators

passing an allocator to a function doesn't attach that allocator to the object it returns. say a file gets opened with a particular allocator.

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

hiv doesn't keep allocator inside file to quietly use it later. when a later operation needs to release memory, it gets the allocator passed in again.

fclose_with(&allocator, file);

if the object remembered its allocator, later memory operations would be implicit again. fclose(file) could free memory without anything at the call site showing which allocator was involved. hiv avoids that by making the allocator part of the operation instead of hidden state on the object. something opened with a _with form gets closed with the matching _with, and something opened with the default form gets closed with the default. the allocator gets passed in when an operation needs it. it isn't kept around for convenience.

portability

hiv aims to implement the iso c standard library, not posix. it should work in a normal hosted program, but that isn't the only target. custom operating systems, kernels, freestanding programs, and bare-metal environments should all be able to use it without first having to provide a posix-compatible runtime.

this is also why the allocator model matters. hiv can't assume there's already a normal heap. a bare-metal program might have one fixed block of ram, a kernel might have its own page allocator, and some other environment might want an arena for everything. in those cases there's no sensible program-wide default, so the default forms aren't available until one is installed, and code uses _with to name whichever allocator fits the memory it has. in a hosted program the default is just the normal heap, and the default forms work out of the box. either way, hiv doesn't get to decide what the environment's memory looks like.

why reimplement libc?

there are way easier ways to use a custom allocator. a program can write allocator-aware functions, use its own allocation api, or swap out the global allocator. reimplementing an entire standard library is obviously overkill if all you want is to allocate memory differently.

the interesting part is applying the idea consistently. writing this much

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

is trivial. applying the same rule across a whole standard library isn't. some functions obviously allocate, because they return a freshly allocated pointer. others create objects with internal state, allocate in the middle of doing something, or release memory as part of tearing something down. once the rule is applied everywhere, the less obvious cases are where it gets interesting.

hiv is mostly an attempt to find those cases and see whether making them explicit gives you a library that's actually nicer to use. it might end up more annoying than a normal libc in places, and finding that out is part of the experiment too. i'm not after verbosity for its own sake. i want to see whether a standard library can be upfront about how it handles memory (ownership always, the allocator when you ask for it) without losing the simplicity that made c's library useful in the first place.

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