Idea to improve the performance of the Kernel Memory Allocation

Idea to improve the performance of the Kernel Memory Allocation

[Guilherme Carvalho]

[-- Attachment #1: Type: text/plain, Size: 1422 bytes --]

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

[-- Attachment #2: arv-list.jpg --]
[-- Type: image/jpeg, Size: 21036 bytes --]

Re: Idea to improve the performance of the Kernel Memory Allocation

[Stephen C. Tweedie]

Hi,

On Sun, May 14, 2000 at 11:34:45PM -0300, Guilherme Carvalho wrote:
> 
> 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.

No.  The free pages are held on linked lists, one list for each size.
We never have to follow free page chains looking for pages.  We just
allocate the first available free 4k page, and if no such page exists,
we find an 8k page, split it, and return one of the 4k subpages (the
other one is placed on the 4k free page list).

We never have to walk over more than one page of any given size.

--Stephen
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux.eu.org/Linux-MM/