doc on memory management

doc on memory management

[Vincent Guffens]

hi,

I have written some doc about mm in grub2. I know this is not the most 
important think to do now but I had it in mind so I thought it would not 
be lost. The document is in latex, there is a makefile to create a pdf, 
dvi, ps and html. Let me know if you want to add this document somewhere 
and you need some other format.

The pdf can be found here : 
http://www.auto.ucl.ac.be/~guffens/article/grub_mm_doc.pdf

and the tgz with the source :
http://www.auto.ucl.ac.be/~guffens/article/grub_mm_doc.tgz


-- 
				Vincent Guffens
				PhD Student UCL/CESAME
				tel:   +32 10 47 80 30
Value your freedom, or you will lose it, teaches history.
"Don't bother us with politics," respond those who don't want to learn.
	      	-- Richard M. Stallman

Re: doc on memory management

[Vladimir Serbinenko]

You made an error in grub_memalign prototype:
it's
void *grub_memalign (grub_size_t align, grub_size_t size);
Not:
void grub_memalign (grub_size_t align, grub_size_t size);
                                                                        
               Vladimir

Re: doc on memory management

[Vincent Pelletier]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain; charset=us-ascii, Size: 2058 bytes --]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Vincent Guffens wrote:
> I have written some doc about mm in grub2.

Nice work, explained with nice and clear schematics.
Now I understand that piece of code :).
I had trouble understanding :
 the macro you explain in "Allocation memory"
 the reason why the first free chunk of the ring is sometime moved
 the reason why alloc'ed chunks were removed from the list

I wonder why the region header contains, to me, a useless field : addr.
It is only set in grub_mm_init_region, invariably to the first header
which is invariably at the same offset from the region beginning,
defined by GRUB_MM_ALIGN. I don't think loosing sizeof(int) bytes is
critical, though, as it would be padded anyway. It only made my
comprehension of what's going on a little harder :).

I see a light improvement in grub_mm_init_region :
  /* If this region is too small, ignore it.  */
  if (size < GRUB_MM_ALIGN * 2)
    return;
If the region is 2*GRUB_MM_ALIGN, we can put a grub_mm_header_t plus a
grub_mm_region_t, and it would be full. Maybe adding 1 byte (or more)
might make more sense (but has it any practical impact...).

My realloc implementation handled the case where the realloc'ed block
had enough space after to expand. I might send a patch for this someday
if anyone finds it interesting to add.

I also implemented a memory defrag that merges successive free chunks in
one bigger. Although it relied on the fact both alloc'ed and free chucks
are known I think it can be adapted (if h->next != h+h->size*16, don't
merge h and h->next) and even a bit faster (as we only see free chunks).

Vincent Pelletier
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFC75z7FEQoKRQyjtURAla2AJ9SZk9V8RSHhDHm0hajC5uOA+f28wCglptX
mpVBwRDWdcPc+uAxuSvJcWA=
=1Sd1
-----END PGP SIGNATURE-----

	

	
		
___________________________________________________________________________ 
Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenger 
Téléchargez cette version sur http://fr.messenger.yahoo.com

Re: doc on memory management

[Vincent Guffens]

Vincent Pelletier wrote:
> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA1
> 
> Vincent Guffens wrote:
> 
>>I have written some doc about mm in grub2.
> 
> 
> Nice work, explained with nice and clear schematics.
> Now I understand that piece of code :).
> I had trouble understanding :
>  the macro you explain in "Allocation memory"

Is it the calculation of the number of blocks n to allocate ?

>  the reason why the first free chunk of the ring is sometime moved

I found one reason in the Knuth's book I mentioned in the introduction 
but I'm not too sure it really applies. The argument is that if you 
always start looking at the same first header, you will tend to 
accumulate after a few  allocations/deallocations a long list of free 
small chunks after the first free chunk. So if you have to allocate a 
bigger block, you will have to traverse this list first.

>  the reason why alloc'ed chunks were removed from the list

It makes the allocation faster as the list you have to traverse is smaller.

> I wonder why the region header contains, to me, a useless field : addr.
> It is only set in grub_mm_init_region, invariably to the first header
> which is invariably at the same offset from the region beginning,
> defined by GRUB_MM_ALIGN. I don't think loosing sizeof(int) bytes is
> critical, though, as it would be padded anyway. It only made my
> comprehension of what's going on a little harder :).

yes, it is not used anywhere !


> I see a light improvement in grub_mm_init_region :
>   /* If this region is too small, ignore it.  */
>   if (size < GRUB_MM_ALIGN * 2)
>     return;
> If the region is 2*GRUB_MM_ALIGN, we can put a grub_mm_header_t plus a
> grub_mm_region_t, and it would be full. Maybe adding 1 byte (or more)
> might make more sense (but has it any practical impact...).
> 
> My realloc implementation handled the case where the realloc'ed block
> had enough space after to expand. I might send a patch for this someday
> if anyone finds it interesting to add.

That would probably be a better way of doing it.

> I also implemented a memory defrag that merges successive free chunks in
> one bigger. Although it relied on the fact both alloc'ed and free chucks
> are known I think it can be adapted (if h->next != h+h->size*16, don't
> merge h and h->next) and even a bit faster (as we only see free chunks).

I don't think this is needed in this case as all the necessary merging 
is done when a  chunk is freed.

> Vincent Pelletier
> -----BEGIN PGP SIGNATURE-----
> Version: GnuPG v1.4.1 (GNU/Linux)
> 
> iD8DBQFC75z7FEQoKRQyjtURAla2AJ9SZk9V8RSHhDHm0hajC5uOA+f28wCglptX
> mpVBwRDWdcPc+uAxuSvJcWA=
> =1Sd1
> -----END PGP SIGNATURE-----
> 
> 	
> 
> 	
> 		
> ___________________________________________________________________________ 
> Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenger 
> Téléchargez cette version sur http://fr.messenger.yahoo.com
> 
> 
> 
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel
> 


-- 
				Vincent Guffens
				PhD Student UCL/CESAME
				tel:   +32 10 47 80 30
Value your freedom, or you will lose it, teaches history.
"Don't bother us with politics," respond those who don't want to learn.
	      	-- Richard M. Stallman

Re: doc on memory management

[Vincent Guffens]

thanks, this is corrected now !


Vladimir Serbinenko wrote:
> You made an error in grub_memalign prototype:
> it's
> void *grub_memalign (grub_size_t align, grub_size_t size);
> Not:
> void grub_memalign (grub_size_t align, grub_size_t size);
>                                                                         
>                Vladimir
> 
> 
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel
> 


-- 
				Vincent Guffens
				PhD Student UCL/CESAME
				tel:   +32 10 47 80 30
Value your freedom, or you will lose it, teaches history.
"Don't bother us with politics," respond those who don't want to learn.
	      	-- Richard M. Stallman

Re: doc on memory management

[Vincent Pelletier]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Vincent Guffens wrote:
>Vincent Pelletier wrote:
>> I had trouble understanding :

I meant, before I read your doc :).

Vincent Pelletier
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFC78hgFEQoKRQyjtURAuo5AKCNOkr2v6F7FyrFmKGEXOKOMqyYbgCgj3mW
BO6EUWBC7yVFWqjuL429/xE=
=pSME
-----END PGP SIGNATURE-----

	

	
		
___________________________________________________________________________ 
Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenger 
Téléchargez cette version sur http://fr.messenger.yahoo.com

Re: doc on memory management

[Yoshinori K. Okuji]

On Tuesday 02 August 2005 18:19, Vincent Pelletier wrote:
> I wonder why the region header contains, to me, a useless field : addr.

It is useful when debugging the code.

> I see a light improvement in grub_mm_init_region :
>   /* If this region is too small, ignore it.  */
>   if (size < GRUB_MM_ALIGN * 2)
>     return;
> If the region is 2*GRUB_MM_ALIGN, we can put a grub_mm_header_t plus a
> grub_mm_region_t, and it would be full. Maybe adding 1 byte (or more)
> might make more sense (but has it any practical impact...).

That check is put only to avoid a strange error.

> My realloc implementation handled the case where the realloc'ed block
> had enough space after to expand. I might send a patch for this someday
> if anyone finds it interesting to add.

I'm not sure if it is really meaningful. Only if you can prove that your 
implementation improves something (such as memory efficiency), I will 
incorporate it.

> I also implemented a memory defrag that merges successive free chunks in
> one bigger. Although it relied on the fact both alloc'ed and free chucks
> are known I think it can be adapted (if h->next != h+h->size*16, don't
> merge h and h->next) and even a bit faster (as we only see free chunks).

The current implementation merges free regions. What is bad?

Okuji

Re: doc on memory management

[Marco Gerards]

Vincent Guffens <guffens@inma.ucl.ac.be> writes:

Hi Vincent,

> I have written some doc about mm in grub2. I know this is not the most
> important think to do now but I had it in mind so I thought it would
> not be lost. The document is in latex, there is a makefile to create a
> pdf, dvi, ps and html. Let me know if you want to add this document
> somewhere and you need some other format.
>
> The pdf can be found here :
> http://www.auto.ucl.ac.be/~guffens/article/grub_mm_doc.pdf
>
> and the tgz with the source :
> http://www.auto.ucl.ac.be/~guffens/article/grub_mm_doc.tgz

It's a really nice document.  Thanks a lot!

--
Marco

Re: doc on memory management

[Vincent Pelletier]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Yoshinori K. Okuji wrote:
> I'm not sure if it is really meaningful. Only if you can prove that your 
> implementation improves something (such as memory efficiency), I will 
> incorporate it.

The test case might be hard to make.
The idea is :
if (size > h->size &&
    h->next->magic == FREE &&
    size < h->size + h->next->size)
{
  h->size += h->next->size + GRUB_MM_ALIGN;
  h->next = h->next->next;
  return h;
}

But should be done smarter, to avoid using a huge free chunk to just
increase the size by, say, 1 byte... I'll do some tests.

> The current implementation merges free regions. What is bad?

Oops, I missed it (again).

Vincent Pelletier
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.1 (GNU/Linux)

iD8DBQFC8SXBFEQoKRQyjtURAqdBAJ9fUKks5Vip45BsCeSBDrvzfUzuMACeKmT+
UyPhKLMNHvmBVqkskF5hL0E=
=4LKn
-----END PGP SIGNATURE-----

	

	
		
___________________________________________________________________________ 
Appel audio GRATUIT partout dans le monde avec le nouveau Yahoo! Messenger 
Téléchargez cette version sur http://fr.messenger.yahoo.com

Re: doc on memory management

[Vincent Guffens]

Hi,

I put the document on the wiki:

http://www.autistici.org/grub/moin.cgi/MemoryManagement

However, the links to the images points to my website as I found no 
other way to inline images. Is it possible to upload these images on the 
wiki server ?

thanks,

Marco Gerards wrote:
> Vincent Guffens <guffens@inma.ucl.ac.be> writes:
> 
> Hi Vincent,
> 
> 
>>I have written some doc about mm in grub2. I know this is not the most
>>important think to do now but I had it in mind so I thought it would
>>not be lost. The document is in latex, there is a makefile to create a
>>pdf, dvi, ps and html. Let me know if you want to add this document
>>somewhere and you need some other format.
>>
>>The pdf can be found here :
>>http://www.auto.ucl.ac.be/~guffens/article/grub_mm_doc.pdf
>>
>>and the tgz with the source :
>>http://www.auto.ucl.ac.be/~guffens/article/grub_mm_doc.tgz
> 
> 
> It's a really nice document.  Thanks a lot!
> 
> --
> Marco
> 
> 
> 
> _______________________________________________
> Grub-devel mailing list
> Grub-devel@gnu.org
> http://lists.gnu.org/mailman/listinfo/grub-devel
> 


-- 
				Vincent Guffens
				PhD Student UCL/CESAME
				tel:   +32 10 47 80 30
Value your freedom, or you will lose it, teaches history.
"Don't bother us with politics," respond those who don't want to learn.
	      	-- Richard M. Stallman