Re: fine points of dynamic memory allocation, not 80286 protected mode

John Levine <johnl@taugh.com> writes:

According to Tim Rentsch  <tr.17687@z991.linuxsc.com>:
>

Once there is a way to get additional memory from whatever underlying
environment is there, malloc() and free() can be implemented (and I
believe most often are implemented) without needing to compare
pointers.  Note:  pointers can be tested for equality without having
to compare them relationally, and testing pointers for equality is
well-defined between any two pointers (which may need to be converted
to 'void *' to avoid a type mismatch).

>
I suppose it's possible, but the versions I know keep free lists
and consolidate adjacent free chunks which requires comparing the
pointers.

It might seem that way, but it isn't so.  There is a fairly
straightforward scheme -- using a single address-sized cell
before each memory block -- that consolidates adjacent free
chunks and maintains free lists, without needing to compare
pointers (and in fact doesn't use pointers at all except for the
free lists).  Doing a malloc() needs to search an appropriate
free list for an adequately large free block, and is constant
time thereafter;  doing a free() uses constant time, including
consolidation of adjacent free chunks.  For an implementation
with 8-byte addresses, this can be done with a grain size of 16
bytes and a minimum of 32-byte blocks (of which 24 bytes can be
used by the client).  Coincidentally (or not) that matches the
sizes I see in tests done on an Ubuntu Linux system (any size
less than 25 uses 32 bytes, any size less than 41 uses 48 bytes,
etc).

The key insight is to use the preceding memory word to hold the
size of this block plus two bits: bit A is one if this block is
not free, and bit B is one if the previous block is not free.  If
bit B is zero (so the previous block is free) then the last word
of the previous block holds the size of that block.  Free lists
are maintained using the first two words in each free block (of
course plus the list headers, which is a small fixed overhead).
This information is enough to combine adjacent free blocks when a
free() is done.