[kvm-unit-tests,RFC,v1,0/5] Rewrite the allocators

Message

Claudio Imbrenda Aug. 14, 2020, 3:10 p.m. UTC

The KVM unit tests are increasingly being used to test more than just
KVM.  They are being used to test TCG, qemu I/O device emulation, other
hypervisors, and even actual hardeware.

The existing memory allocators are becoming more and more inadequate to
the needs of the upcoming unit tests (but also some existing ones, see
below).

Some important features that are lacking:
* ability to perform a small physical page allocation with a big
  alignment withtout wasting huge amounts of memory
* ability to allocate physical pages from specific pools/areaas (e.g.
  below 16M, or 4G, etc)
* ability to reserve arbitrary pages (if free), removing them from the
  free pool

Some other features that are nice, but not so fundamental:
* no need for the generic allocator to keep track of metadata
  (i.e. allocation size), this is now handled by the lower level
  allocators
* coalescing small blocks into bigger ones, to allow contiguous memory
  freed in small blocks in a random order to be used for large
  allocations again

This is achieved in the following ways:

For the virtual allocator:
* only the virtul allocator needs one extra page of metadata, but only
  for allocations that wouldn't fit in one page

For the page allocator:
* page allocator has up to 4 memory pools, each pool has a metadata
  area; the metadata has a byte for each page in the area, describing
  the order of the block it belongs to, and whether it is free
* if there are no free blocks of the desired size, a bigger block is
  split until we reach the required size; the unused parts of the block
  are put back in the free lists
* if an allocation needs an allocation with a larger alignment than its
  size, a larger block of (at least) the required order is split; the
  unused parts put back in the free lists
* if the allocation could not be satisfied, the next allowed area is
  searched; the allocation fails only when all allowed areas have been
  tried
* new functions to perform allocations from specific areas; the areas
  are arch-dependent and should be set up by the arch code
* for now x86 has a memory area for "low" memory under 4GB and one for
  the rest, while s390x has one for under 2GB and one for the rest;
  suggestions more fine grained areas are welcome
* upon freeing a block, an attempt is made to coalesce it into the
  appropriate neighbour (if it is free), and so on for the resulting
  larger block thus obtained

For the physical allocator:
* the minimum alignment is now handled manually, since it has been
  removed from the common struct


This patchset addresses some current but otherwise unsolvable issues on
s390x, such as the need to allocate a block under 2GB for each SMP CPU
upon CPU activation.

This patch has been tested on s390x, amd64 and i386. It has also been
compiled on aarch64.

Claudio Imbrenda (5):
  lib/vmalloc: vmalloc support for handling allocation metadata
  lib/alloc_page: complete rewrite of the page allocator
  lib/alloc: simplify free and malloc
  lib/alloc.h: remove align_min from struct alloc_ops
  lib/alloc_page: allow reserving arbitrary memory ranges

 lib/alloc.h      |   3 +-
 lib/alloc_page.h |  81 +++++++-
 lib/alloc.c      |  42 +---
 lib/alloc_page.c | 510 ++++++++++++++++++++++++++++++++++++++---------
 lib/alloc_phys.c |   9 +-
 lib/arm/setup.c  |   2 +-
 lib/s390x/sclp.c |  11 +-
 lib/s390x/smp.c  |   6 +-
 lib/vmalloc.c    | 121 +++++++++--
 s390x/smp.c      |   4 +-
 10 files changed, 617 insertions(+), 172 deletions(-)

Comments

Paolo Bonzini Aug. 17, 2020, 4:44 p.m. UTC | #1

On 14/08/20 17:10, Claudio Imbrenda wrote:
> 
> The existing memory allocators are becoming more and more inadequate to
> the needs of the upcoming unit tests (but also some existing ones, see
> below).
> 
> Some important features that are lacking:
> * ability to perform a small physical page allocation with a big
>   alignment withtout wasting huge amounts of memory
> * ability to allocate physical pages from specific pools/areaas (e.g.
>   below 16M, or 4G, etc)
> * ability to reserve arbitrary pages (if free), removing them from the
>   free pool
> 
> Some other features that are nice, but not so fundamental:
> * no need for the generic allocator to keep track of metadata
>   (i.e. allocation size), this is now handled by the lower level
>   allocators
> * coalescing small blocks into bigger ones, to allow contiguous memory
>   freed in small blocks in a random order to be used for large
>   allocations again

I haven't reviewed the patches in detail, but the deficiencies of the
page allocator are of course known and it's welcome that you're
attempting to fix them!

Thanks,

Paolo