Coalescing allocator with a free list

This is a popular allocator and similar to the one implemented in dlmalloc which is at the heart of many allocator implementations in use today including glibc.

It is based on the constant time coalescing scheme described by Donald Knuth in The Art of Computer Programming, Vol I, Fundamental Algorithms, Addison-Wesley, Reading, MA, 1968.

The major departures from the scheme presented in dlmalloc is that this allocator doesn't try to merge new segments and tries to free similarly to slab allocators (Slab allocator) wherein we keep a list of empty segments that can be re-used and a user-settable number of them are freed to the OS at a user-settable interval.

Segment sizes acquired for this allocator are user-settable also.

This allocator works by keeping a boundary tag for each allocation which holds the information about the chunk to which it points.

In actuality, each tag holds the information about the previous chunk also. This allocator has a minimum alignment of 16 bytes which yields four free bits in every address.

1. 0th bit: Used to store whether a chunk has a chunk before it in the segment.
2. 1st bit: Used to store whether a chunk has a chunk after it in the segment.
3. 2nd bit: Used to store whether a chunk is allocated or free.
4. Rest of the bits store the size of the allocated chunk.

There is a bit still unused which is always 0. This is exploited by the overall malloc implementation to distinguish memory allocated by coalescing allocators from other schemes.

In conjunction with the chunks, the 16 byte alignment also allows us to store a doubly linked free list on x64 platforms within the overhead of any allocated chunk.

Allocation is done by traversing the free list to find the first chunk of the required or higher size.

Freeing is done by marking the chunk as free, merging with neighbouring chunks if they are free and if the chunk is the first and last chunk in a segment, we migrate the segment to the list of free segments.

Coalescing allocator roots have two lists of segments

1. NonEmpty: List of non-empty segments.
2. Empty: List of completely empty segments.

When there are more than a user-settable number of empty segments, the slab allocator will free another user-settable number of them. The default is for both number to be equal, which means every so often, a slab allocator will return all its free pages to the OS.

This allocator can be made thread safe upon request.