Hi,

I had an idea to improve the performance of the Kernel Memory
Allocation...
If I am right, the buddy allocation algorithm first searches for blocks
of pages of the size requested and follows the chain of free pages that
is queued on the list element of the the free_area data structure. If no
blocks of pages of the requested size are free, blocks of the next size
are looked for...

free_area:
|  4096  | -> |  8  | -> | 1024  | -> | 8192  | -> | 2  | -> | 4  | -> |
2  | -> | 256  | -> | 512  | -> | 4  | -> | 8  | -> | 16  | ->

in this case, if we request 32 pages, the algorithm will scan the chain
4 times to find the right block.
I think this chain isn't the best structure to do it.

the idea is to make a tree of chains as it is in the attach
(arv-list.jpg).
this tree should be an AVL tree for better performance.

Each element of the tree would be an chain
Each element of the chain would be

Struct free_area_struct {
 struct page *next;
 struct page *prev;                //      <- Free area element
 unsigned int *map;
 unsigned long count;
// +
struct page *next_in_chain;       //     <- pointer to the next free
area with the same size
 };

the old pointers would remain because the deallocation process need
them, to recombine them in larger blocks.

I am a linux code beginner, so I don't know how to put it on linux (and
keep it working too).
Are Anyone interested in try it?

Guilherme Carvalho