Initrd and physical memory manager.

[Sourcer]

Another question:
Does your kernel provide a function for allocating a contionous chunk of physical pages?

If so, how does your algorithm of finding a continous chunk works?
I'm trying to figure our weither my approch of trying to O(n) the **** of the algorithm is too much and hurts readability. Maybe O(number_of_pages * N) is better?

[Boris]

Hi,
For each 256Mb of memory, I keep sorted lists of pointers pointing to free areas of contiguous physical memory.
It takes only a short to represent a 4kb page in a 256Mb memory area.
I have 64k entries for pointers for 4kb free areas,
32k entries for pointers to 8kb free areas ...
16k entries for pointers to 16kb
8k entries for pointers of size 32kb
and so on, until
2 entries for 128Mb free pointers.
I have a 64kb entry list that keep track of allocated pointer sizes. Which enables to check free errors.
This allocator costs me roughly 500Kb each 256Mb of physical ram.
When I alloc, I can split areas from upper lists.
When I free, I can merge blocks and give them to upper lists.
I can easily allocate 4kb, 2Mb for paging.

Allocation is in O(1).
Freeing is a little costly because you may end up to have many blocks to merge.. But you can imagine to let a worker thread with priority proportional to the amount of things to merge...

[Sourcer]

Hi,
For each 256Mb of memory, I keep sorted lists of pointers pointing to free areas of contiguous physical memory.
It takes only a short to represent a 4kb page in a 256Mb memory area.
I have 64k entries for pointers for 4kb free areas,
32k entries for pointers to 8kb free areas ...
16k entries for pointers to 16kb
8k entries for pointers of size 32kb
and so on, until
2 entries for 128Mb free pointers.
I have a 64kb entry list that keep track of allocated pointer sizes. Which enables to check free errors.
This allocator costs me roughly 500Kb each 256Mb of physical ram.
When I alloc, I can split areas from upper lists.
When I free, I can merge blocks and give them to upper lists.
I can easily allocate 4kb, 2Mb for paging.

Allocation is in O(1).
Freeing is a little costly because you may end up to have many blocks to merge.. But you can imagine to let a worker thread with priority proportional to the amount of things to merge...

Are you describing the 'buddy allocator' approach?

[Brendan]

Hi,

Another question:
Does your kernel provide a function for allocating a contionous chunk of physical pages?

If so, how does your algorithm of finding a continous chunk works?
I'm trying to figure our weither my approch of trying to O(n) the **** of the algorithm is too much and hurts readability. Maybe O(number_of_pages * N) is better?

I typically split physical memory into 3 zones:

• 0x00000000 to 0x00FFFFFF: Managed with "1 bit per page" bitmap, handles allocations that have unusual requirements (physically contiguous pages, ISA DMA chip "64 KiB boundaries", AP CPU startup trampolines)
  0x01000000 to 0xFFFFFFFF: Managed with free page stacks. Handles non-contiguous pages that must have a 32-bit physical address (page directory pointer tables when using PAE for paging, pages for old "32-bit addressing only" PCI devices).
  0x10000000000000000 or above: Managed with free page stacks.

Of course when allocating pages I use "highest zone that can satisfy requirements is checked first"; so that RAM in the more versatile zones isn't used unnecessarily. For my next kernel, I'm planning to make the boundary between the first and second zone adjustable, so that the size of the size of the first zone can be increased or decreased after the kernel's physical memory manager is initialised (so kernel can make "versatility vs. performance" adjustments in response to actual usage/utilisation).


Cheers,

Brendan

[Sourcer]

Hi,

Another question:
Does your kernel provide a function for allocating a contionous chunk of physical pages?

If so, how does your algorithm of finding a continous chunk works?
I'm trying to figure our weither my approch of trying to O(n) the **** of the algorithm is too much and hurts readability. Maybe O(number_of_pages * N) is better?

I typically split physical memory into 3 zones:

• 0x00000000 to 0x00FFFFFF: Managed with "1 bit per page" bitmap, handles allocations that have unusual requirements (physically contiguous pages, ISA DMA chip "64 KiB boundaries", AP CPU startup trampolines)
  0x01000000 to 0xFFFFFFFF: Managed with free page stacks. Handles non-contiguous pages that must have a 32-bit physical address (page directory pointer tables when using PAE for paging, pages for old "32-bit addressing only" PCI devices).
  0x10000000000000000 or above: Managed with free page stacks.

Of course when allocating pages I use "highest zone that can satisfy requirements is checked first"; so that RAM in the more versatile zones isn't used unnecessarily. For my next kernel, I'm planning to make the boundary between the first and second zone adjustable, so that the size of the size of the first zone can be increased or decreased after the kernel's physical memory manager is initialised (so kernel can make "versatility vs. performance" adjustments in response to actual usage/utilisation).


Cheers,

Brendan

Hey, what is your algorithm of finding continous available pages when using bitmaps? I'm bitwising the **** out of this for efficeincy, but maybe theres a better solution?

I mean, suppose the user wants 16 straight pages, this would be easy since 16 % 8 = 0, so i just fince 16 / 8 straight bytes that are available.
But what happens when the user wants 23 straight pages? 23 % 8 = 7, i need a byte that has 7 straight available bits, and 2 straight available bytes.

Theres a trivial algorithm which i think i don't need to write here since you can all think about it. But maybe theres a better one?

[Brendan]

Hi,

Hey, what is your algorithm of finding continous available pages when using bitmaps? I'm bitwising the **** out of this for efficeincy, but maybe theres a better solution?

I just find the first bit, then check the next N bits to see if I have "N contiguous bits". If not I start finding another first bit (from the end of the last run of "<N bits").

Note that (on an average computer) you'd be lucky to find 5 device drivers that want one contiguous buffer each (during boot); so it's not worth caring about performance for this.


Cheers,

Brendan