Skip to content

vulkan/malloc: completely rewrite memory allocator

Niklas Haas requested to merge vk_malloc_rewrite into master

Switch to a completely different approach.

The old allocator used logarithmically growing list of slabs, from which regions are sliced with byte-level granularity and the free space map is kept track of using an array of structs. This had the advantage of being relatively flexible to the demand, but the disadvantage of being horrendeously slow and CPU-intensive due to O(n^2) algorithms - bad enough to notice, especially when freeing lots of small allocations.

The new allocator uses conceptually simpler state tracking. New slabs are just collections of uniformly sized pages, and allocations are always served one page at a time. This allows us to keep track of the spacemap using a bitset, which is extremely efficient. The disadvantage is that differently-sized allocations would end up in lots of different slabs, without some mechanism of grouping them together. Mitigate this by rounding up allocation sizes to 4K chunks, garbage collecting unused slabs, and trimming the number of pages to allocate by default (increasing exponentially as the pool for a given page size gets exhausted).

Re-evaluate and tune the various limits, and also improve diagnostics and debug messages throughout.

Edited by Niklas Haas

Merge request reports

Loading