simple slab alloc question

simple slab alloc question

[Jeff Garzik]

kmalloc seems to allocate against various kmem_cache sizes: 32,
64...1024...65536...

Does this mean that allocations of various sizes are stored in different
"buckets"?  Would that not reduce fragmentation and the need for a zone
allocator?

Enlightenment from MM gurus appreciated :)

Regards,

	Jeff




-- 
Custom driver development	|    Never worry about theory as long
Open source programming		|    as the machinery does what it's
				|    supposed to do.  -- R. A. Heinlein
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: simple slab alloc question

[Andi Kleen]

On Mon, Oct 11, 1999 at 12:09:47AM +0200, Jeff Garzik wrote:
> kmalloc seems to allocate against various kmem_cache sizes: 32,
> 64...1024...65536...
> 
> Does this mean that allocations of various sizes are stored in different
> "buckets"?  Would that not reduce fragmentation and the need for a zone
> allocator?

kmalloc uses these buckets. Other clients use their own slab pool (e.g.
skb headers etc.). This is a variant of a zone allocator, but only
for relatively small objects.

Slab sits on top of the page allocator and is on its mercy.

Even other major users get their pages from the page allocator directly
(inodes, dcache). These used to be (still are?) a major source of 
fragmentation, because they tend to wire whole pages down even where there
is only a single active inode/dentry on it.

The page allocator uses the buddy algorithm, which is very prone
to fragmentation. Usually when you suffer from fragmentation there are 
simply not enough continous pages left, and the Linux MM datastructures
are not suited to do some organized effort to get them back.

The basic idea is to replace the buddy with another zone allocator.


> 
> Enlightenment from MM gurus appreciated :)

I'm not a mm guru, but I hope it was helpful.

-Andi

-- 
This is like TV. I don't like TV.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://humbolt.geo.uu.nl/Linux-MM/

Re: simple slab alloc question

[Rik van Riel]

On Mon, 11 Oct 1999, Andi Kleen wrote:
> On Mon, Oct 11, 1999 at 12:09:47AM +0200, Jeff Garzik wrote:
> > kmalloc seems to allocate against various kmem_cache sizes: 32,
> > 64...1024...65536...
> > 
> > Does this mean that allocations of various sizes are stored in different
> > "buckets"?  Would that not reduce fragmentation and the need for a zone
> > allocator?
> 
> kmalloc uses these buckets. Other clients use their own slab pool
> (e.g. skb headers etc.). This is a variant of a zone allocator,
> but only for relatively small objects.
> 
> Slab sits on top of the page allocator and is on its mercy.

Indeed.

> Even other major users get their pages from the page allocator
> directly (inodes, dcache). These used to be (still are?) a major
> source of fragmentation, because they tend to wire whole pages
> down even where there is only a single active inode/dentry on it.

A zone allocator would not help in this case. A zone
which has only one active inode/dentry on it is just
as wired down as a normal page.

What we need here is a trick to emergency-recycle the
last two(?) inodes on a page when memory is short. Of
course the real number should be calculated by memory
pressure, but I don't have time to think about that
now :)

> The page allocator uses the buddy algorithm, which is very prone
> to fragmentation.

> The basic idea is to replace the buddy with another zone allocator.

I hope to be working on a design for something like that from
december onwards. With a bit of luck the first code will be
ready just before we begin the 2.5 development cycle.

(doing things earlier doesn't make much sense and we're too
late for 2.4 anyway)

cheers,

Rik
--
The Internet is not a network of computers. It is a network
of people. That is its real strength.
--
work at:	http://www.reseau.nl/
home at:	http://www.nl.linux.org/~riel/

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

Re: simple slab alloc question

[Stephen C. Tweedie]

Hi,

On Mon, 11 Oct 1999 20:11:38 +0200 (CEST), Rik van Riel
<riel@nl.linux.org> said:

>> Even other major users get their pages from the page allocator
>> directly (inodes, dcache). These used to be (still are?) a major
>> source of fragmentation, because they tend to wire whole pages
>> down even where there is only a single active inode/dentry on it.

> A zone allocator would not help in this case. A zone
> which has only one active inode/dentry on it is just
> as wired down as a normal page.

It would help.  The problem is that single wired pages make it
impossible to use the adjacent page for larger allocations such as for
kernel stacks or big network frames.  The VM causes the same problem but
to a much lesser extend, as in general we can swap out any VM page given
enough effort.  The fragmentation caused by a pinned inode or dcache
page causes unrecoverable fragmentation.

With a zoned allocater, we can keep these two cases in separate zones
and enormously increase our ability to defragment memory by cleaning VM
pages.

--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://humbolt.geo.uu.nl/Linux-MM/