Track small allocations in cache separately from large ones, ensure than no more than N% of cache is used for small allocations. Then allocator overhead should be less than N% (assuming the allocator is near perfect for larger allocations).

Since we already track page image sizes separately from the rest of a page, it may be simplest to account for the total size of page images, then we're trying to bound cache_size - sum(page image size).