Page 1 of 1

Kernel memory allocator

Posted: Wed Feb 28, 2001 12:00 am
by Thomas
I'm actually trying to write a kernel memory allocator, and I don't know which type to choose. Some time ago I saw the SunOS Slab Allocator, and I think it is quite good. What do you think about it ? Maybe a Linux-like memory allocator would be better ?

RE:Kernel memory allocator

Posted: Thu Mar 01, 2001 12:00 am
by Chase
>On 2001-02-28 15:03:10, Thomas wrote:
>I'm actually trying to write a kernel memory
>allocator, and I don't know which type to choose.
>Some time ago I saw the SunOS Slab Allocator, and
>I think it is quite good. What do you think about
>it ? Maybe a Linux-like memory allocator would be
>better ?

What are the differances between the two?

RE:Kernel memory allocator

Posted: Thu Mar 01, 2001 12:00 am
by Guest
>On 2001-03-01 11:46:25, Chase wrote:
>>On 2001-02-28 15:03:10, Thomas wrote:
>>I'm actually trying to write a kernel memory
>>allocator, and I don't know which type to choose.
>>Some time ago I saw the SunOS Slab Allocator, and
>>I think it is quite good. What do you think about
>>it ? Maybe a Linux-like memory allocator would be
>>better ?
>
>What are the differances between the two?

Like I said, I'm not an expert in this matter, but AFAIK the SunOS allocator uses caches and, what is the most significant difference, chunks of memory of the same size, it also uses constructor and destructor functions on the allocated objects. And if I'm not wrong, the Linux allocator does not use this functions, and allocates chunks of random size. The Slab Allocator paper says that this type of allocator is faster and doesn't leave to much unused memory, but... Which type do you use in your OS ?

RE:Kernel memory allocator

Posted: Sat Mar 03, 2001 12:00 am
by Nick
>On 2001-03-01 14:20:33, Anonymous wrote:

>Like I said, I'm not an expert in this matter,
>but AFAIK the SunOS allocator uses caches and,
>what is the most significant difference, chunks
>of memory of the same size, it also uses
>constructor and destructor functions on the
>allocated objects. And if I'm not wrong, the
>Linux allocator does not use this functions, and
>allocates chunks of random size.

I thought Linux used a "buddy algorithm" and
allcoated chunks in a size that was a power of
two, eg, 4 bytes, 8 bytes, 16 bytes ... 512kb ...

--Nick

> The Slab
> Allocator paper says that this type of allocator is faster and doesn't leave to much unused memory, but... Which type do you use in your OS ?

RE:Kernel memory allocator

Posted: Mon Mar 05, 2001 12:00 am
by Guest
>On 2001-03-03 20:36:18, Nick wrote:
>>On 2001-03-01 14:20:33, Anonymous wrote:
>
>>Like I said, I'm not an expert in this matter,
>>but AFAIK the SunOS allocator uses caches and,
>>what is the most significant difference, chunks
>>of memory of the same size, it also uses
>>constructor and destructor functions on the
>>allocated objects. And if I'm not wrong, the
>>Linux allocator does not use this functions, and
>>allocates chunks of random size.
>
>I thought Linux used a "buddy algorithm" and
>allcoated chunks in a size that was a power of
>two, eg, 4 bytes, 8 bytes, 16 bytes ... 512kb ...
>
>--Nick
>
>> The Slab
>> Allocator paper says that this type of allocator is faster and doesn't leave to much unused memory, but... Which type do you use in your OS ?

Yeah, you're right, only for me a power of two is almost a random size :) Seriously speaking, I think that the word "random" wasn't a good choice in this case, but I supose you know what I was trying to say.

RE:Kernel memory allocator

Posted: Mon Mar 05, 2001 12:00 am
by Nick
>On 2001-03-05 08:51:14, Anonymous wrote:
>
>Yeah, you're right, only for me a power of two is
>almost a random size :) Seriously speaking, I think
>that the word "random" wasn't a good choice in this
>case, but I supose you know what I was trying to
>say.

Yeah, I understand :)

--Nick

RE:Kernel memory allocator

Posted: Wed Mar 07, 2001 12:00 am
by Guest
>On 2001-03-05 22:06:00, Nick wrote:
>>On 2001-03-05 08:51:14, Anonymous wrote:
>>
>>Yeah, you're right, only for me a power of two is
>>almost a random size :) Seriously speaking, I think
>>that the word "random" wasn't a good choice in this
>>case, but I supose you know what I was trying to
>>say.
>
>Yeah, I understand :)
>
>--Nick
As for kernel allocators - hey, Chase, are you out there ? Sorry for bothering but you're the expert here :)

RE:Kernel memory allocator

Posted: Wed Mar 07, 2001 12:00 am
by J. Weeks
How 'bout this folks, here's how my memory management
works:

It's virtual paged, so I've got two kernel functions:
addr = allocate4kPagesAbove1MB(num);
addr = allocate4kPagesBelow1MB(num);

The later is mostly for allocating pages that
_must_ be in conventional memory (for DMA, etc).

A program may only allocate 4k chunks at a time,
so it's up to the programmer to decide how to manage
them. However, my default API provides a mechanism
for managing these 4k pages (to elimate a char, or a
long taking up a 4k page, and wasting space).

The API will allocate one 4k page which will be used
for tiny allocations, until it gets full, and then
another 4k page will be allocated.

For larger allocations, the api will just allocate
enough 4k pages. Some memory will be wasted, but
in the long run, it wont be much.

Hope that makes sense,
Jeff

RE:Kernel memory allocator

Posted: Thu Mar 08, 2001 12:00 am
by Guest
>On 2001-03-07 21:17:55, J. Weeks wrote:
>How 'bout this folks, here's how my memory management
>works:
>
>It's virtual paged, so I've got two kernel functions:
>addr = allocate4kPagesAbove1MB(num);
>addr = allocate4kPagesBelow1MB(num);
>
>The later is mostly for allocating pages that
>_must_ be in conventional memory (for DMA, etc).
>
>A program may only allocate 4k chunks at a time,
>so it's up to the programmer to decide how to manage
>them. However, my default API provides a mechanism
>for managing these 4k pages (to elimate a char, or a
>long taking up a 4k page, and wasting space).
>
>The API will allocate one 4k page which will be used
>for tiny allocations, until it gets full, and then
>another 4k page will be allocated.
>
>For larger allocations, the api will just allocate
>enough 4k pages. Some memory will be wasted, but
>in the long run, it wont be much.
>
>Hope that makes sense,
>Jeff

It does, but I have no (practical) experience with kernel memory allocators so my question is - should I use an allocator that splits a 4kb page into objects of the same size, or should I rather try to write one that can allocate "random" (eg. the "power of two" buddy algorithm) chunks of memory ? Which one is better, in your opinion ?

RE:Kernel memory allocator

Posted: Sun Mar 11, 2001 12:00 am
by j. weeks
>> [ snipped [
>>
>>Hope that makes sense,
>>Jeff
>
>It does, but I have no (practical) experience with
>kernel memory allocators so my question is - should I
>use an allocator that splits a 4kb page into objects
>of the same size, or should I rather try to write
>one that can allocate "random" (eg. the "power of two"
>buddy algorithm) chunks of memory ? Which one is better,
>in your opinion ?

Well, in my opinion, no matter what you do, every memory
allocation should be dword aligned. In other words,
if you make sure every memory allocation is a multiple
of 4 bytes, you're all good there.

Reason: 32-bit accesses do nasty things to the bus
if they aren't dword aligned :)

As for the other issue; myself, I'd definitly
try to divide up the 4k page as much as possible,
so you don't waste memory (but don't try to
eliminate _all_ memory waste... I think that
would result in being too complicated and kludgy
for what it's worth).

So...
- If you use paging, you'll have to work around 4k pages.
- I'd recommend dividing them up into multiples of 4, 8, or 16, though,
whenever possible. In other words, if the program
requests 12 bytes... allocate 16 (the first larger
multiple of 4).

That's my opinion anyway,
Jeff