OSDev.org

I'm trying to figure out how Linux stores his physical page structs. Currently I am initializing an array where MAX_NR_PAGES equals the size of RAM divided by the size of a physical page frame (1GiB / 4KiB), which is a little over 250.000 in size. This is a rather lame and costly approach, so I am trying to find out how Linux manages his mem_map array.

In this file, Linux declares its pointer to the page structs array: There are some references to this variable, but I cannot seem to find out how all over 250.000 page structs are lined up there. It is a pretty cost saving approach regarding memory, since the single pointer does not use as much space as my array, but I don't know where all the other page structs for the whole physical RAM are stored.

In my approach, I am initializing a buddy allocator which assigns information to a struct page (physical address, order, ...). So to assign those informations to each of the structs, I would need to iterate over my whole 250.000 sized array. Where in Linux does this happen, or if not, how exactly does Linux initialize all page structs, especially at a point where allocation is not set up yet? (Since allocation would only work when page structs are available?)

Hope, you could enlighten me in this pretty crucial matter.

In the simplest configuration, the initialization is here. On more complex configurations, such as NUMA machines, architectures with large memory holes, hot-plug memory, etc - this variable (i.e. mem_map) is essentially unused. Note that the allocation from the same function reserves space for one page structure per page frame, as you can see just a few lines above.

If you want to dig deeper into the subject, you can investigate the page frame to page structure translations here. That is, observe what __pfn_to_page uses to map a page frame into a page descriptor. There are 4 models that handle physical memory sparseness in different ways. But all of them reserve one page metadata structure per one physical page frame.

Thanks for your answer.

I looked into the source code myself and realized that I had the wrong assumption about how the mem_map array is initialized. Initially I thought the memory manager would be initialized _BEFORE_ the mem_map array is allocated, because, well yeah, for an array you would need some sort of an allocator. Upon looking further into the code I stumbled upon the struct memblock, which is used to add and remove as well as combine memory sections directly from the multiboot info struct (or in linux, directly from the INT 15, EAX E820 instruction). There the linux kernel obtains a large continuous block of memory directly from the memory map provided by the multiboot struct / E820.

By doing so the Linux kernel is able to reserve and allocate memory before the memory manager and any allocator is initialized. This seems to be quite the hassle, but I also assume that this is a kind of chicken-egg problem, because the buddy allocator returns a struct page, but the page struct does not miraculously create itself, so the memory for this page struct must come from somewhere else.

I am now using a simplified form of the implementation used in linux, using memblock structs to keep track of the memory regions before the allocators are set up.