FPooledVirtualMemoryAllocator

This class pools OS allocations made from FMallocBinned2.

The class fulfills FMallocBinned2 requirements of returning a 64KB-aligned address and it also avoids fragmenting the memory into too many small VMAs (virtual memory areas).

The logic is like follows:

There are N buckets that represent allocation sizes from 64KB to N*64 KB. Each bucket is a linked list of pools that hold varied number of same-sized allocations (called blocks). Each bucket starts empty (linked list is empty).

Whenever an allocation request arrives, it is first bucketed based on its size (if it is larger than the largest bucket, it is passed through to a caching OS allocator). Then, the linked list of that bucket is walked, and the allocation is fulfilled by the first pool that has empty "blocks". If there are no such pool, a new pool is created (with number of blocks being possibly larger than in the existing list, if any), this pool becomes the new head of the list and the allocation happens there.

Whenever a free request arrives, it is again first bucketed based on the size (which must be passed in and must match allocation size). If it is larger than the largest bucket, it is passed through to a platform function BinnedFreeToOS(). Otherwise, the appropriate bucket's list of pools is walked to find the pool where the allocation belongs, and the appropriate block becomes free (a platform-specific function is called to evict the memory range from the RAM). If this was the last used block in the pool, the whole pool is destroyed and the list shrinks by one.

So, to visualize an example state:

64KB bucket: Head -> [ A pool of 200 64KB "blocks", of which 50 are empty ] -> [ A pool of 100 64KB blocks, of which 30 are empty ] -> null 128KB bucket: Head -> [ A pool of 60 128KB "blocks", of which 25 are empty ] -> null 192KB bucket: Head -> null 256KB bucket: Head -> [ A pool of 40 256KB "blocks", of which 10 are empty ] -> [ A pool of 20 256KB blocks, of which 10 are emtpy ] -> [ A pool of 4 256 KB blocks of which 0 are empty ] -> null ... 4MB bucket: Head -> [ A pool of 2 4MB "blocks", of which 1 is empty ] -> null

Each pool uses one distinct VMA on Linux (or one distinct VirtualAlloc on Windows).

The class also maintains an idea of what current size of each pool (per bucket) should be. Each time we add a new pool to a particular bucket, this size can grow (exponentially or otherwise). Each time we delete a pool from a particular bucket, this size can shrink. The logic that handles that is in DecideOnTheNextPoolSize().

Right now the class is less multithread friendly than it could be. There are per-bucket locks so allocations of different sizes would not block each other if happening on different threads. It is possible to make allocations within one bucket lock-free as well (e.g. with hazard pointers), but since FMallocBinned2 itself needs a lock to maintain its own structures when making a call here, the point is moot.

This class is somewhat similar to FCachedOSPageAllocator. However, unlike FCOSPA, this is not a cache and we cannot "trim" anything here. Also, it does not make sense to put the global cap on the pooled memory since BinnedAllocFromOS() can support only a limited number of allocations on some platforms.

CachedOSPageAllocator sits "below" this and is used for allocs larger than the largest bucketed.