Possible cure for memory fragmentation.

Possible cure for memory fragmentation.

[James Courtier-Dutton]

Hi,

There are two problems associated with memory fragmentation.
1) Identifying a memory fragment that one would really like to move if 
one could.
2) Actually moving the fragment.

This idea assumes that (1) has been identified, and this email explains 
how to do actually move the fragment (2).

I am suggesting we add a new memory allocation function into the kernel 
called kremalloc().

The purpose of any call to kremalloc() would mean that:
a) One really needs the memory already allocated, so don't loose it.
b) One does not mind if the memory location moves.

Now, the kernel driver module that has previously allocated a memory 
block, could at a time convenient to itself, allow the memory to be 
moved. It would simple call kremalloc() with the same size parameter as 
it originally called kmalloc(). The mm would then notice this, and then, 
if that location had been tagged with (1), the mm could then happily 
move it, and the kernel driver module would be happy. If it was not 
tagged with (1) the mm would simply return, so very little overhead.

I believe that this could be a very simple, yet painless way to 
implement memory defragmentation in the kernel. A similar method could 
be used for user land applications.

Any comments?

James

P.S. I though this topic was better for Linux-mm than LKML.


--
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-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Possible cure for memory fragmentation.

[Christoph Lameter]

On Wed, 21 Dec 2005, James Courtier-Dutton wrote:

> I am suggesting we add a new memory allocation function into the kernel
> called kremalloc().
> 
> The purpose of any call to kremalloc() would mean that:
> a) One really needs the memory already allocated, so don't loose it.
> b) One does not mind if the memory location moves.
> 
> Now, the kernel driver module that has previously allocated a memory block,
> could at a time convenient to itself, allow the memory to be moved. It
> would simple call kremalloc() with the same size parameter as it originally
> called kmalloc(). The mm would then notice this, and then, if that location
> had been tagged with (1), the mm could then happily move it, and the kernel
> driver module would be happy. If it was not tagged with (1) the mm would
> simply return, so very little overhead.

Moving regular mapped kernel memory is not trivial. See my page migration
patchsets.

Slab memory cannot be resized since the memory is managed in portions 
of fixed sizes. So if these size boundaries are violated then the 
kremalloc would degenerate into a kfree and a kmalloc. kremalloc 
would be:

void *kremalloc(void *p, int oldsize, int newsize, gfp_t f)
{
	void *new;

	if (newsize < sizeboundary)
		return p;

	new = kmalloc(size, f);

	memcpy(new, old, oldsize);

	kfree(p);

	return new;
}

--
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-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Possible cure for memory fragmentation.

[James Courtier-Dutton]

Christoph Lameter wrote:
> On Wed, 21 Dec 2005, James Courtier-Dutton wrote:
> 
> 
>>I am suggesting we add a new memory allocation function into the kernel
>>called kremalloc().
>>
>>The purpose of any call to kremalloc() would mean that:
>>a) One really needs the memory already allocated, so don't loose it.
>>b) One does not mind if the memory location moves.
>>
>>Now, the kernel driver module that has previously allocated a memory block,
>>could at a time convenient to itself, allow the memory to be moved. It
>>would simple call kremalloc() with the same size parameter as it originally
>>called kmalloc(). The mm would then notice this, and then, if that location
>>had been tagged with (1), the mm could then happily move it, and the kernel
>>driver module would be happy. If it was not tagged with (1) the mm would
>>simply return, so very little overhead.
> 
> 
> Moving regular mapped kernel memory is not trivial. See my page migration
> patchsets.
> 
> Slab memory cannot be resized since the memory is managed in portions 
> of fixed sizes. So if these size boundaries are violated then the 
> kremalloc would degenerate into a kfree and a kmalloc. kremalloc 
> would be:
> 
> void *kremalloc(void *p, int oldsize, int newsize, gfp_t f)
> {
> 	void *new;
> 
> 	if (newsize < sizeboundary)
> 		return p;
> 
> 	new = kmalloc(size, f);
> 
> 	memcpy(new, old, oldsize);
> 
> 	kfree(p);
> 
> 	return new;
> }
> 
> 
> 

I think you missed the point I was trying to make.
The driver does not call kremalloc with a different size. It calls it 
with the SAME size. Then if the kernel thinks it would benefit from 
moving the allocation to a different location, it can do:

new = kmalloc(size, f);
if (!new)
	return p;
memcpy(new, old, oldsize);
kfree(p);

If the kernel does not wish to move it, kremalloc returns without having 
done anything.

This would effectively allow for dynamic recovery from a fragmented 
memory layout.

James

--
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-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Possible cure for memory fragmentation.

[Christoph Lameter]

On Thu, 22 Dec 2005, James Courtier-Dutton wrote:

> The driver does not call kremalloc with a different size. It calls it with the
> SAME size. Then if the kernel thinks it would benefit from moving the

Umm. When would the kernel do something like that? 
Also give it different name. realloc has pretty well established 
semantics.

> If the kernel does not wish to move it, kremalloc returns without having done
> anything.

What this all comes down to is to guarantee that only a known number of 
references exist to the data element when you move it. For kremalloc these
references must be known and all the pointers to the data element must be 
updated if the data is moved. The basic problem is not solved.

--
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-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>

Re: Possible cure for memory fragmentation.

[James Courtier-Dutton]

Christoph Lameter wrote:
> Umm. When would the kernel do something like that? 
> Also give it different name. realloc has pretty well established 
> semantics.

Ok, I will call is kmovefrag() for lack of any better name at the moment.

> 
> 
>>If the kernel does not wish to move it, kremalloc returns without having done
>>anything.
> 
> 
> What this all comes down to is to guarantee that only a known number of 
> references exist to the data element when you move it. For kremalloc these
> references must be known and all the pointers to the data element must be 
> updated if the data is moved. The basic problem is not solved.
> 
> 
Surely the module that originally called kmalloc should have enough 
information to know who is then using the memory pointer, or it could be 
redesigned to know enough.
It is therefore my suggestion that the module that originally requested 
the kmalloc() call kmovefrag() at a time that suits it( probably 
periodically), therefore allowing the kernel to move the fragment if it 
wishes. The module that called kmovefrag() can then update all it's 
pointers and continue.

It requires implementing kmovefrag() calls all over the different 
modules, but this goes some way to solving the "basic problem."

James

--
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-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>