Skip to content

GitLab

Open
Opened by Matthew Pickering@mpickeringDeveloper

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.

  1. The mesh allocator is only used for pinned memory.
  2. Meshing operates on the level of blocks.
  3. 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 by memfd_create, so there is a physical backing for pinned blocks. This is important for meshing.
  4. 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)
  5. 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.
  6. 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.
  7. 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 flags MAP_FIXED and MAP_SHARED. MAP_FIXED is used so that the same virtual address range for A is used but now it just maps to B. The physical page for A is then freed.