include: add ilog2()

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
include: add count_trailing_zeros() functions

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mempool: remove unused function debug_memory_pool()

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mempool: introduce new page range allocator

The main goal of the new page range allocator is to improve computational
complexity. To achieve that N (currently N = 16) doubly linked lists are
used, list i contains areas which size is in range [2^i, 2^(i+1)). Huge
areas (i.e. too large for any list) are kept in a multiset sorted by their
sizes.

When a memroy block of size M is requested the allocator gets an area
from a not empty list that contains smallest objects greater or equal
2^ceil(log2(M)). If there is no such list an area is taken from a tree
of huge areas. If still allocator cannot find appropriate area the
temporary solution is to search list floor(log2(M)). That, obviously
ruins worst case computational complexity of the algorithm but can be
replaced by the fallback to non-contiguous once it is implemented.

When a memory block is freed allocator checks if it can be merged with
an neighbouring areas (at most 2) and then puts a resulting area in
an appropriate container. To quickly (O(1)) find whether there
neighbouring unallocated areas a bitmap is maintained where each bit
represents one page. If the bit is set the page is not allocated.
Moreover, each unallocated page range contains a valid header at the
beginning and at its very end (&pr + pr.size - sizeof(page_range**))
a pointer to its header.

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
mempool: use new page range allocator

Signed-off-by: Paweł Dziepak <pdziepak@quarnos.org>
Signed-off-by: Avi Kivity <avi@cloudius-systems.com>
Improve complexity of the large allocator

From: Paweł Dziepak <pdziepak@quarnos.org>

This patch series improves complexity of the large allocator to O(1) for large
objects that are small and O(log n) for large objects that are not small. There
is still one fallback that makes the worst case complexity O(n), but that can
be easily improved once falling back to non-contiguous allocations is
implemented.

The details of the allocator are described in the fourth patch of this series
(i.e. "mempool: introduce new page range allocator"), hopefully. this time not
stopped by the spam filter.

Signed-off-by: Avi Kivity <avi@cloudius-systems.com>