A question about memory fragmentation

A question about memory fragmentation

[Abel Muñoz Alcaraz]

Hi everybody,
	I have a question for you; How Linux avoids the memory fragmentation in
linked lists?

	Windows 9x/NT/2000 (sorry, ;-)), have specific functions (like List_Create,
ExInitializeSListHead, ...) to create generic linked lists but I don't find
something similar in Linux.
	Has Linux a generic linked list management API ?
	Must I develop this?
	Is the kernel memory fragmentation a solved problem in Linux? (I wish it).

	I have develop my own API but I don't know if Linux can do this for me.

Thanks in advance.

Abel Muñoz Alcaraz.
Media Security Software Developer.
mailto:abel@trymedia.com
Trymedia Systems

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: A question about memory fragmentation

[Alan Cox]

> 	Has Linux a generic linked list management API ?

Yes - if you want to use it
	<linux/list.h>

> 	Is the kernel memory fragmentation a solved problem in Linux? (I wish =

Its not a problem you can solve without causing serious performance hits so
we don't solve it. If you want to allocate large bus linear memory allocations
then tough 8). If you want large virtually linear blocks then you can use 
vmalloc

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: A question about memory fragmentation

[Erik Mouw]

On Tue, Nov 07, 2000 at 04:20:20PM +0100, Abel Muñoz Alcaraz wrote:
> 	I have a question for you; How Linux avoids the memory fragmentation in
> linked lists?
> 
> 	Windows 9x/NT/2000 (sorry, ;-)), have specific functions (like List_Create,
> ExInitializeSListHead, ...) to create generic linked lists but I don't find
> something similar in Linux.
> 	Has Linux a generic linked list management API ?

Yes.

> 	Must I develop this?

No.

> 	Is the kernel memory fragmentation a solved problem in Linux? (I wish it).

My guess is that the slab allocator solves this, but I don't know that
much about the MM.

> 	I have develop my own API but I don't know if Linux can do this for me.

Have a look in include/linux/list.h.

Or install jadetex and the DocBook style sheets and type "make psdocs"
in the kernel tree. That will create the file
Documentation/DocBook/kernel-api.ps in which the linked list API (and
much more) is described.


Erik

-- 
J.A.K. (Erik) Mouw, Information and Communication Theory Group, Department
of Electrical Engineering, Faculty of Information Technology and Systems,
Delft University of Technology, PO BOX 5031,  2600 GA Delft, The Netherlands
Phone: +31-15-2783635  Fax: +31-15-2781843  Email: J.A.K.Mouw@its.tudelft.nl
WWW: http://www-ict.its.tudelft.nl/~erik/
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: A question about memory fragmentation

[Davide Libenzi]

On Tue, 07 Nov 2000, Erik Mouw wrote:
> 
> > 	Is the kernel memory fragmentation a solved problem in Linux? (I wish it).
> 
> My guess is that the slab allocator solves this, but I don't know that
> much about the MM.

Linux lists implementation stores linking informations directly inside the
block of data We're going to link.
This has the advantage that no extra list nodes are allocated to store the data
pointer but has the drawback that if We've to link the same data to more than
one list We've to declare more than one listhead.
See at the different links We've inside the task_struct for example.



- Davide
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: A question about memory fragmentation

[Francis Galiegue]

On Tue, 7 Nov 2000, Abel Muñoz Alcaraz wrote:

> 
> 	my question is about memory fragmentation when I allocate and free a lot of
> small memory pieces in a kernel module.
> 	Can it do a memory fragmentation problem?
> 	Can I solve it using 'linux/list.h' API?

Fragmentation is not really an issue there. Linux maintains a pool of pages of
different sizes, and you will be allocated a page with the next size superior
to what you ask for. Sizes are all powers of two, so the worst case would be
that you ask 2^n+1 bytes and get a 2^(n+1) size page. When you free such a
page, it is merged if needed with a coalescent page and put back in the "upper
size" pool (not sure about this, though). So, no fragmentation is to be feared.

As to whether you use list.h or not, it really doesn't have any influence,
except that the list.h implementation is the preferred and standard way to make
doubly linked lists under Linux.

So, no, there's no need to allocate one big pool and manage it yourself. Also
remember that you can only kmalloc() up to 128k - if you want to allocate
bigger amounts of memory, use vmalloc().

Another solution: create your own slab cache for your objects.

-- 
Francis Galiegue, fg@mandrakesoft.com
"Programming is a race between programmers, who try and make more and more
idiot-proof software, and universe, which produces more and more remarkable
idiots. Until now, universe leads the race"  -- R. Cook

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

Re: A question about memory fragmentation

[Alan Cox]

> 	I think that is better to allocate a big piece of memory and get the n=
> odes
> from this buffer with my own memory management functions; Is this corre=
> ct?.

See the SLAB interface. It'll do that for you. Kmalloc uses SLAB so will do
similarly sane things

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/

A question about memory fragmentation

[Abel Muñoz Alcaraz]

Hi everybody,

	Thank you for your help!
	I am going to tell you more information.

	my question is about memory fragmentation when I allocate and free a lot of
small memory pieces in a kernel module.
	Can it do a memory fragmentation problem?
	Can I solve it using 'linux/list.h' API?

	I think that is better to allocate a big piece of memory and get the nodes
from this buffer with my own memory management functions; Is this correct?.

Thanks.

Abel Muñoz Alcaraz.
Media Security Software Developer.
mailto:abel@trymedia.com
Trymedia Systems

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
Please read the FAQ at http://www.tux.org/lkml/