The lone lisp heap

The lone lisp heap

Like many dynamic languages out there,<br>lone started out<br>simple. It was essentially a collection of data structures written in<br>C, an union comprising all of those types, a typed value<br>structure containing the union plus metadata, and a custom language<br>whose entire purpose is to bring all these values together into<br>patterns that resemble working programs.

struct lone_lisp_list { /* ... */ };<br>struct lone_lisp_vector { /* ... */ };<br>struct lone_lisp_table { /* ... */ };<br>/* ... */

enum lone_lisp_heap_value_type {<br>LONE_LISP_TYPE_LIST,<br>LONE_LISP_TYPE_VECTOR,<br>LONE_LISP_TYPE_TABLE,<br>/* ... */<br>};

struct lone_lisp_heap_value {<br>bool live: 1;<br>bool marked: 1;<br>/* ... */

enum lone_lisp_heap_value_type type;

union {<br>struct lone_lisp_list list;<br>struct lone_lisp_vector vector;<br>struct lone_lisp_table table;<br>/* ... */<br>} as;<br>};

When I put it this way, the language itself seems almost incidental to<br>the virtual machine work. That's because it is. Lone was in fact not<br>designed ahead of time. It was and still is being constructed in real<br>time. It's almost as if the language itself is arising<br>as a consequence of its own implementation. It grows in complexity<br>alongside the knowledge and understanding of its creator.

At first I was a neophyte. I was attracted to ideas that were almost<br>painfully simple, almost too naive to cope with the harsh reality of<br>the world. The code reflected that.

Take the above structures, for example. How are such values created?<br>My first instinct is to simply allocate some memory for each object.<br>Call malloc with the size of the structure, then<br>initialize the memory it returns. It's that easy.

Right?

Memory allocation

Lone is a lisp interpreter written in freestanding C. There is no<br>dynamic memory allocation in freestanding C. There is no such thing as<br>malloc. There is no libc. There is only me<br>and the code. If I wanted malloc, I would have to write<br>it myself.

So I wrote it. I read up on everything I could find online about<br>memory and its allocation. Then I made my own memory allocator.

To manage a memory block, the allocator needs to describe it. Let's<br>start with the basics. The most basic information about a piece of<br>data is its location and its size.

struct lone_memory {<br>size_t size;<br>unsigned char pointer[];<br>};

The allocator must also keep track of whether the block is free or<br>currently in use. Otherwise, there would be chaos .

struct lone_memory {<br>bool free;<br>size_t size;<br>unsigned char pointer[];<br>};

This is enough to manage any one block of memory. If it's free, then<br>the allocator can give the block to whoever asks. If it's not free,<br>then it can't. If they ask for less or exactly as much memory as this<br>block contains, then it can be given out. If they ask for more, then<br>it can't.

I started from literally nothing. Now I've got the one. Time to handle<br>infinity.

struct lone_memory {<br>struct lone_memory *prev, *next;<br>bool free;<br>size_t size;<br>unsigned char pointer[];<br>};

Simply link the blocks to each other. Now if some code requests a<br>block, the allocator can walk through the list of all blocks and<br>search for any block that fits.

And that's exactly what the allocator does.

for (block = system->memory; block; block = block->next)<br>if (block->free && block->size >= size)<br>break;

if (!block) { return 0; }

block->free = false;<br>return block->pointer;

Searches the list of blocks and literally returns the first block that<br>fits. This thing could end up returning 16 KiB blocks for 64 byte<br>requests. Crude, but effective. Incredibly wasteful, of course.<br>Potentially more wasteful than mmaping pages for every<br>single allocation.

The memory allocator can do better than this. Why not cut the block up<br>into smaller chunks?

block->free = false;<br>lone_memory_split(block, size);<br>return block->pointer;

Split the block into two blocks: an allocated block of exactly the<br>requested size, and a new free block for any excess memory that might<br>remain.

size_t excess = block->size - size;

/* create a new block only if there's enough<br>space for memory block descriptor + 1 byte */

if (excess >= sizeof(struct lone_memory) + 1) {<br>new = (struct lone_memory *) (block->pointer + size);

/* weave the new block into the linked lists */

new->free = true;<br>new->size = excess - sizeof(struct lone_memory);<br>block->size = size;

The excess memory block gets conjured up out of thin air: the<br>allocator simply drops a new memory block descriptor right after the<br>end of the previous memory block. When the links are established, the<br>excess memory can be allocated like any other memory block.

Memory deallocation is even simpler: just mark the block as free. The<br>block descriptor is just behind the pointer, trivially reachable.

struct lone_memory *block = ((struct lone_memory *) pointer) - 1;<br>block->free = true;

This is enough, but the allocator can do better. It can check if<br>surrounding blocks are also free, and undo the split if that is...