Repository files navigation

This code was integrated into the Zig Standard Library inPull Request #5998.

This repository is no longer maintained.

This is the code formy Zig Live Coding Stream.

This is a work-in-progress general purpose allocator intended to be eventually mergedinto theZig standard library, with the focus on these goals:

• Detect double free, and print stack trace of:

  • Where it was first allocated
  • Where it was freed the first time
  • Where it was freed the second time

• Detect leaks and print stack trace of:

  • Where it was allocated

• When a page of memory is no longer needed, give it back to resident memory,but keep it mapped with no permissions (read/write/exec) so that it causespage faults when used.

• Make pointer math errors unlikely to harm memory fromunrelated allocations

• It's OK for these mechanisms to cost some extra bytes and formemory to become a little fragmented.

• OK for performance cost for these mechanisms.

• Rogue memory writes should not harm the allocator's state.

• Cross platform. Allowed to take advatage of a specific operating system'sfeatures, but should work everywhere, even freestanding, by wrapping anexisting allocator.

• Compile-time configuration, including:

  • Whether the allocatior is to be thread-safe. If thread-safety is disabled,then the debug allocator will detect invalid thread usage with it.
  • How many stack frames to collect.

ReleaseFast and ReleaseSmall Modes:

• Low fragmentation is primary concern
• Performance of worst-case latency is secondary concern
• Performance of average-case latency is next
• Finally, having freed memory unmapped, and pointer math errors unlikely toharm memory from unrelated allocations are nice-to-haves.

ReleaseSafe Mode:

• Low fragmentation is primary concern
• All the safety mechanisms from Debug Mode are the next concern.
• It's OK for these mechanisms to take up some percent overheadof memory, but not at the cost of fragmentation, which can causethe equivalent of memory leaks.

• POSIX-only so far.
• Most basic functionality works. See Roadmap below for what's left to do.
• Not well tested yet.

Memory leak detection:

Double free detection:

Small allocations are divided into buckets:

index obj_size0     11     22     43     84     165     326     647     1288     2569     51210    102411    2048

The main allocator state has an array of all the "current" buckets for eachsize class. Each slot in the array can be null, meaning the bucket for thatsize class is not allocated. When the first object is allocated for a givensize class, it allocates 1 page of memory from the OS. This page isdivided into "slots" - one per allocated object. Along with the page of memoryfor object slots, as many pages as necessary are allocated to store theBucketHeader, followed by "used bits", and two stack traces for each slot(allocation trace and free trace).

The "used bits" are 1 bit per slot representing whether the slot is used.Allocations use the data to iterate to find a free slot. Frees assert that thecorresponding bit is 1 and set it to 0.

The memory for the allocator goes on its own page, with no write permissions.On call to reallocFn and shrinkFn, the allocator uses mprotect to make its own statewritable, and then removes write permissions before returning. However bucketmetadata is not protected in this way yet.

Buckets have prev and next pointers. When there is only one bucket for a givensize class, both prev and next point to itself. When all slots of a bucket areused, a new bucket is allocated, and enters the doubly linked list. The mainallocator state tracks the "current" bucket for each size class. Leak detectioncurrently only checks the current bucket.

Reallocation detects if the size class is unchanged, in which case the samepointer is returned unmodified. If a different size class is required, theallocator attempts to allocate a new slot, copy the bytes, and then free theold slot.

Large objects are allocated directly usingmmap and their metadata is storedin astd.HashMap backed by a simple direct allocator. The hash map's datais memory protected with the same strategy as the allocator's state.

• Port to Windows
  • Make sure that use after free tests work.
• Test mmap hints on other platforms:
  • macOS
  • FreeBSD
• Ability to print stats
  • Requested Bytes Allocated (total of n for every alloc minus n for every free)
  • Resident Bytes (pagesize * number of pages mmapped for slots)
  • Overhead Bytes (how much memory the allocator state is using)
• Validation fuzz testing
  • vary the size and alignment of allocations
  • vary the number of and kind of operations in between allocations andcorresponding frees
  • vary whether or not the backing allocator succeeds
  • how much memory capacity it goes up to
• When allocating new pages for small objects, if virtual address space isexhausted, fall back to using the oldest freed memory, whether that beunused pages, or freed slots.
• When falling back to old unused pages, if we get an error from the OS fromreactivating the page, then fall back to a freed slot.
• Implement handling of multiple threads.
• On invalid free, print nearest allocation/deallocation stack trace
• Do the memory protection for bucket metadata too
• Catch the error when wrong size or wrong alignment is given to free or realloc/shrink.
• Performance benchmarking
  • Do we need meta-buckets?
• Iterate over usize instead of u8 for used bits
• When configured to be non-thread-safe, then detect usage with multiple threads,and print stack traces showing where it was used in each thread.
• Write unit tests / regression tests
• Makestd.HashMap return bytes back to the allocator when the hash map getssmaller.
• Make deallocated but still mapped bytes be0xdd.
• Detect when client uses the wrongold_align orold_mem.len.
• Keep track of first allocation stack trace as well as reallocation stack tracefor large objects.
• Test whether it is an improvement to try to use an mmap hint when growinga large object and it has to mmap more.
• Once a bucket becomes full, remove it from the linked list of buckets that areused to find allocation slots.