Buddy Allocation

[jensvdb]

Hello,

Working on my own OS (written in C++), I've come to a point to write a memory manager, and I've decided to go for buddy allocation. I only have one issue with this principle; imagine the following situation:

(# = used block; . = free block; xxK = block size)

Code: Select all

4K  ########
8K  # # # #
16K #   #
32K #

Let's say we want to free 20K (=5 blocks of 4K) starting on with the second block; we now have this situation:

Code: Select all

4K  #.....##
8K  # # # #
16K #   #
32K #

Now one would say a block of 16K has been made available, while actually, there isn't (because there is no sequence of 4 free blocks on a 16K boundary)!
I could move other 4K blocks (or larger pieces of memory) around; but in my opinion this would cause problems, for example:

Code: Select all

Object *obj = (Object *)alloc(sizeof(Object));

where 'alloc' returns the starting address of the allocated memory. If I move used chunks of memory around, then 'obj' won't be pointing to the actual object anymore!

Am I missing something or is this a negative side-effect of buddy allocation?

jensvdb

[Combuster]

People use Paging so that the addresses used does not need to match the physical address.

[jensvdb]

Yes, I do understand the principle of paging, however then (with your explanation) I don't really see the benefits of using a buddy allocator.
The way I understand the wiki is like this:

* Paging splits the system RAM into "blocks" of memory (4K or 4MB or even 1G pages)
* This way, one can set up a virtual address space for each process (yes, this isn't position dependent anymore)
* how do we allocate pages? (I read the wiki page on "Page Frame Allocation") --> here comes my buddy allocator

Thus I made my allocator like this:

For the "4K" chunks of memory:
at physical memory address 0x0000 0000 is the first block; sized 0x1000 (4K; 1 page)
at physical memory address 0x0000 1000 is the second block; sized 0x1000 [...]

For the "8K" chunks of memory, it goes like this:
first block @ 0x0000 0000 physical
second block @ 0x0000 2000 physical [...]

And so on for 16K, 32K, 64K, 128K, 256K and 512K (like the Linux kernel did/does).

However, and here is my problem, when you PHYSICALLY move a page from one physical address to another; pointers and stuff like that get messed up?

It could be of course that I'm mixing "virtual" and "physical" memory, in which case: shame on me! But the way I understood the wiki is that a page frame allocator manages the PHYSICAL frames (thus pages) in memory...

[NickJohnson]

It could be of course that I'm mixing "virtual" and "physical" memory, in which case: shame on me! But the way I understood the wiki is that a page frame allocator manages the PHYSICAL frames (thus pages) in memory..

I guess shame on you then - that is the flaw in your reasoning. When paging is enabled, pointers refer to virtual addresses, not physical ones (which is basically the definition of paging). You can't move frames from one physical address to another either (without physically moving memory chips around). You can however map physical frames to different pages, which moves them around within a virtual address space.

[jensvdb]

It could be of course that I'm mixing "virtual" and "physical" memory, in which case: shame on me! But the way I understood the wiki is that a page frame allocator manages the PHYSICAL frames (thus pages) in memory..

I guess shame on you then - that is the flaw in your reasoning. When paging is enabled, pointers refer to virtual addresses, not physical ones (which is basically the definition of paging). You can't move frames from one physical address to another either (without physically moving memory chips around). You can however map physical frames to different pages, which moves them around within a virtual address space.

I think I got it now

Thank you!