Problems with arena allocation
==============================

Main problems with the most naive solution:
1. Unused space at the end
2. Pointer-chasing across *all* allocated pages.
3. Large data structures can get splitted many times.


Possible solution to:

1 and 2:
- Use the tail space for book-keeping of following chunks.
  (e.g. an array of offsets)

1:
- In the last chunk, we can track the amount of free space in the previous
  chunk (perhaps it could be a pointer to the first free byte -- the amount
  of free space can be calculated as roundup(freeptr,4k)-freeptr )
    - The check could be implemented as:
        if ((lastptr&0xFFF)+requested_size >= 0x1000)
- This pointer can be re-purposed as a next-pointer (which will always point
  to an even 4kB address)
    - At this point, the chunk would be "locked", except for tail allocations
      via the following chunk (as described in the point above).
- This pointer could possibly be stored at the end.
    - That way it can be repurposed as storage space, if the following chunk
      can be allocated adjacent to the chunk.
    - This gives worse cache efficiency, though

2:
- For sequentially mmap'ed chunks, we can have a length field
  in the first chunk.

3:
- Have a special type qualifier for non-addressible data
  (or even more specific: non-addressible OR non-arena-addressible data)
- Allow chunk headers to be omitted for "middle chunks" in arrays of
  non-addressible data.
- Store arena meta-data at a fixed virtual address offset (e.g. +1GB
  on 32-bit platforms or perhaps +1TB on 64 bit platforms).
  Note that this requires MAP_FIXED_NOREPLACE support in mmap, to
  protect existing mappings from getting overwritten.

Possible problem with arena chunk information and CHERI
-------------------------------------------------------

Each arena chunk contains some info at the beginning, and the address
to this area is computed by masking the low-order bits of a pointer
(to round down to the arena chunk size, e.g. 4 KiB).

* Does this work with CHERI?
* Perhaps a parameter passed as "arena" should give access to the whole
  arena? (i.e. all chunks)