New zone allocator implemented

[Matthieu Lemerre]

Hi,

As we have already discussed in this mailing list, we've been planning
to rewrite the zone allocator to permit constraint on allocated
address.

This constraint are bits which have to be on or off in the returned
address. This is useful for instance when implementing page coloring,
or for requesting DMA'ble memory.

To sum up, the algorithm I propose is a variation of the buddy system,
using a binary tree instead of block list. Each level of the binary
tree can be think as a block list in the buddy system.

Each node represents a zone of size 2^k in memory, self-aligned, and
may have two sons, each representing a zone of size 2^(k-1).

Each node contains a field present_sizes, which enable to find quickly
whether or not we will be able to find a zone of the wanted size in
the memory region.

The algorithm is O(M-p) when there is no constraints, with 2^M >=
memory size and 2^p the size of a page. So this is logarithmic
complexity.

I attach the Changelog and the patch.

Thanks,
Matthieu


2005-06-24  Matthieu Lemerre  <address@hidden>

        * zalloc.c: Rewritten for the new zone allocator algorithm.
        * zalloc.h (zalloc): New arguments, comments change.
        (zfree): Comments change.
        (zset_initial_memory, zinit): New declarations.
        * physmem.c (get_all_memory): Changed initialisation for the new
        zone allocator.
        * frame.c (frame_memory_alloc): Added new arguments to zalloc.
        * mmap.c (mmap): Likewise.

patch
Description: Binary data