# malloc

The world of the C language is deeply intimate with the word "malloc". This is
by far the most popular way of dynamically allocating memory in this world. Dusk
implements a similar API with the words "malloc", "realloc" and "free".

These words live at [mem/malloc.fs]. Unlike the Arena and scratchpad allocators,
this allocator is not based on the Allocator structure from [doc/mem/alloc].

Malloc allows memory of arbitrary size to be allocated. It allocates that memory
into buffers that grow on demand, directly from system memory.

Those buffers can be marked as free through the same API by passing it the
address that was returned when malloc was called. This allows this buffer to be
reused by a future malloc if it's big enough.

Those buffers are a linked list with 3 fields:

next  Address of next buffer
size  Size of the buffer in bytes
used  1=buffer is used 0=buffer is free

Those buffers are managed in an absolutely dumb manner, that is, whatever size
is requested is the size we'll allocate for a buffer.

If no buffer in the list can accomodate that size, we allocate a new buffer from
the system memory.

If a buffer is found that can accomodate the size, we use it regardless of how
much more memory than requested it contains.

This system has the advantage of being simple, but it's also inefficient. If
used for many small allocation, it will use more memory than it should and
allocations will become time consuming after a while.

This kind of allocations, however inefficient they are, can nevertheless be
useful in some situations, for example reallocateable arrays of unpredictable
(depends on data) sizes. Because array elements need to be contiguous, arenas
don't work. Because their size is unpredictable, scratchpads and static memory
can't work either. Because we need to possibly reallocate them with a different
size, we can't simply squander resources by allocating system memory.

One such example is the array of Line structures in text/ed. We don't know
beforehand how many lines we'll have. Even worse: the user might add lines when
using the application. The Line structure doesn't include text data, so
allocating many lines isn't overly prohibitive, but we still don't want to go
crazy and allocate a million Lines. What we want to do is to pre-allocate a
number of Lines that seem reasonable (let's say 3000) *but*, at the same time,
have the possibility to reallocate that array to a bigger one if the input data
requires it. Malloc allow that.

## malloc API

malloc ( sz -- a )
  Allocate a new zone of sz bytes of contiguous memory at address "a".

free ( a -- )
  Mark an address "a" previously allocated through malloc as unused.

realloc ( a sz -- a )
  Given that "a" was previously allocated with malloc, if "sz" is smaller than
  currently allocated zone, simply shrink the zone. Otherwise, free it,
  reallocate a new one and copy the contents to the new zone.

## C API

"needsh mem/malloc" provides:

void* malloc(int sz)
void* realloc(int sz, void* ptr)
void free(void *ptr)
