[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

New zone allocator implemented

From: Matthieu Lemerre
Subject: New zone allocator implemented
Date: Fri, 24 Jun 2005 22:36:18 +0200
User-agent: Gnus/5.11 (Gnus v5.11) Emacs/22.0.50 (gnu/linux)


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

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

I attach the Changelog and the patch.


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.

Attachment: patch
Description: Binary data

reply via email to

[Prev in Thread] Current Thread [Next in Thread]