Consider using mesh style allocator for pinned objects
Fragmentation of pinned objects is a serious problem (#13630) but it's also a lot of effort to change ByteString to use an unpinned representation.
Another approach is to use a mesh allocation strategy just for pinned blocks (https://raw.githubusercontent.com/plasma-umass/Mesh/master/mesh-pldi19-powers.pdf)
The idea of the strategy is that objects are allocated at random into a special block. Blocks can be meshed together if they don't overlap each other at all. In order to retain the virtual addresses of a pinned object, the virtual address of the meshed blocks is updated to point to the new physical block.
I will summarise the idea here best I can in the context of how it could work for GHC.
- The mesh allocator is only used for pinned memory.
- Meshing operates on the level of blocks.
- Blocks are split up into fixed sizes, for
i = 2,4,8,16,32
. The megablock keeps a randomised freelist of blocks (see section 3.1). 7: Blocks are not created using anonymous memory mapping but bymemfd_create
, so there is a physical backing for pinned blocks. This is important for meshing. - Therefore allocations of pinned objects of size greater than BLOCK_SIZE/2 are treated as large objects (as opposed to 0.8 * BLOCK_SIZE as of now)
- When a pinned object is allocated, a partially full block from the freelist is chosen and the object allocated at a random offset into it. The offset is chosen from a randomised list of offsets.
- Meshing: Either concurrently or after a GC, then blocks of the same slot size are attempted to be meshed together. Spans are compared pairwise to see whether they can be meshed - parameters control how much time is attempted spending meshing. Long-lived date will eventually be meshed.
- When two blocks A, and B are meshed then firstly the contents of A is copied into B. Then, the virtual address range of A is set to map to the physical page B, using
mmap
with flagsMAP_FIXED
andMAP_SHARED
.MAP_FIXED
is used so that the same virtual address range for A is used but now it just maps toB
. The physical page forA
is then freed.