The XamOS — Let’s Build an OS!!!
The 8th step of OS development — “page_frame_allocation”
Welcome back, Readers!!!
If you’re new to OS development and my article series you better come from this first article.Otherwise it would be hard to understand what’s going on.🤔
Today’s flow:
1️⃣▶️ Managing Available Memory
▶️ How Much Memory is There?
▶️ Managing Available Memory
2️⃣▶️ How Can We Access a Page Frame?
3️⃣▶️ A Kernel Heap
Managing Available Memory
How does the OS know which sections of memory are free to utilize while utilizing virtual memory? The page frame allocator does this job.
How Much Memory is There?
First, we must determine how much memory is accessible on the machine on which the OS is installed. Reading it from the multiboot structure provided to us by GRUB is the simplest method to do it. GRUB gathers the memory information we require, such as what is reserved, I/O mapped, read-only, and so on. We must additionally ensure that the memory utilized by the kernel is not marked as free (because GRUB does not identify this memory as reserved). Exporting labels at the beginning and end of the kernel binary from the linker script is one approach to figure out how much memory the kernel uses:
These labels can be read straight from assembly code and placed into the stack so that C code may access them:
extern kernel_virtual_start
extern kernel_virtual_end
extern kernel_physical_start
extern kernel_physical_end; …push kernel_physical_end
push kernel_physical_start
push kernel_virtual_end
push kernel_virtual_startcall kmain
We can obtain the labels as arguments to kmain this way. Declare the labels as functions and take the addresses of these functions if you wish to use C instead of assembly code:
void kernel_virtual_start(void); /* … */ unsigned int vaddr = (unsigned int) &kernel_virtual_start;
When we’re using GRUB modules, we should ensure sure the memory they utilize is also declared as reserved. It’s worth noting that the available memory doesn’t have to be in any particular order. There are numerous I/Omapped memory regions in the first 1 MB, as well as memory utilized by GRUB and the BIOS. Other sections of the memory may be inaccessible in a similar way. Because we can’t map parts of pages into memory, it’s easier to split the memory portions into entire page frames.
Managing Available Memory
What method do we use to determine which page frames are in use? The page frame allocator must keep track of which frames are available for use and which are not. There are numerous methods for doing this, including bitmaps, linked lists, trees, and the Buddy System. Bitmaps are quite simple to use. Each page frame has one bit, and one or more page frames are allocated to storing the bitmap.
▶️Bitmap
As a large bit map of memory use, a large array of N/8 bytes is utilized that is, bit I in byte #n represents the state of page #n*8+i. Allocating a page may take time (O(N)), while changing the state of a particular page is quick (O(1(N)).
- An uint32 t comparison may test up to 32 bits at once, making allocations faster.
- Keeping a pointer to the last allocated bit can help the next search run faster.It is keeping information about the fact all the previous bytes were searched unsuccessfully
▶️Stack/List of pages
A stack-like dynamic structure is used to hold the address of each accessible physical frame. Allocating and releasing pages are both fast (O(1)), but verifying the status of a page is not feasible unless extra metadata sorted by physical address is kept.
▶️Sized Portion Scheme
You divide a 16-kilobyte area into parts of 1 8-kilobytes and 2 4-kilobytes, for example. After that, you give each chunk to a different person. You’ll be able to discover more accurate fits if you do it this way. So there will be less waste. Let’s suppose you’ve got a 32kb area. For each section, you can have one, two, three, four, or even more different layouts. You’ll be able to pick from a wider range of sizes.
▶️Buddy Allocation System
This is the Linux kernel’s physical memory allocator. Note that depending on whether the memory is appropriate for ISA DMA, comes from ‘high physical memory,’ or is merely ‘regular,’ Linux has multiple buddys. Each buddy has k bitmaps, each of which indicates the presence of 2i-sized and 2i aligned blocks of free pages. Linux often utilizes 4K to 512K chunks.
A buddy for N pages is roughly double the size of a bitmap for the same region, but it allows for quicker collection page finding. A 4-buddy is depicted in the diagram above, with free pages/blocks marked as. Also, I used # to signify pages/blocks. A block is marked as used when it contains at least one used sub-block, and sub-blocks that are part of a bigger block are likewise marked as used x in the figure. If we wish to give this buddy a 12-K area, we’ll look at the bitmap of free 16K blocks, which shows that we have one starting at page #12 and another starting at page #36. After that, buddy[2]->bit[4] is set to ‘used’. Now that we only need three of the four pages we received, the remaining page is returned to the appropriate buddy bitmap (e.g. the single pages map). The resulting buddy is,
Note that only the biggest areas are available at first, so if buddy[0] seems to be empty, we must examine buddy[1], then buddy[2], and so on until we find a free block to divide.
▶️Hybrid scheme
Allocators can be linked together such that a stack, for example, only includes the most recent actions and the ‘bottom’ of the stack is committed to a bitmap for compact storage. If the stack is missing pages, it can scan the bitmap in the background to find some.
▶️Hybrid scheme #2
Instead of keeping track of simply bits representing pages or just page numbers on a stack, represent the memory using a large array of structs. Store a single link to the next page pointer-sized and an 8–16 bit information block indicating its state in these page frame structs. Include the virtual page pointer as well as the TCB where the page number is assigned. Maintain references to the beginning and end of each type of page’s list. You can easily show information about their content, the number of pages accessible for each kind, combine types, allow dynamic cleaning threads, conduct copy-on-write reasonably quickly, and maintain clear & simple overviews of the pages this way. It works as a reverse page mapping table that also identifies page kinds. See AtlantisOS 0.0.2 or above for an example implementation.
Note that this is only one method; other ideas may be more effective and enjoyable to apply.
How Can We Access a Page Frame?
The page frame allocator delivers the page frame’s physical start address. There is no page table that points to this page frame since it is not mapped in. What is the best way to read and write data to the frame? We must map the page frame into virtual memory by changing the kernel’s PDT and/or PT. What if all of the accessible page tables are already occupied? Then we can’t map the page frame into memory since we’d have to create a new page table, which would take up a whole page frame, and we’d have to map this page frame’s page frame to write to it. This cyclic reliance must be broken in some way.
One approach is to set aside a portion of the kernel’s first-page table or another higher-half page table for temporarily mapping page frames in order to make them accessible. The kernel contains at least one-page table if it is mapped to the 0xC0000000 page directory entry with index 768 and 4 KB page frames are utilized. We can allocate the last item 1023 of this page table to temporary mappings if we assume — or limit ourselves to — a kernel with a maximum size of 4 MB minus 4 KB. The virtual address of pages mapped in with the kernel’s PT’s final entry will be:
(768 << 22) | (1023 << 12) | 0x000 = 0xC03FF000We can add the page frame we wish to use as a page table to the paging directory and remove the temporary mapping once we’ve temporarily mapped it and set it up to map in our initial page frame.
A Kernel Heap
We’ve only been able to operate with fixed-size data or raw memory up until now. We can implement malloc and free to use in the kernel now that we have a page frame allocator. The only change we need to do is to invoke the page frame allocator instead of sbrk/brk when extra memory is required. The page frames provided by the page frame allocator must also be mapped to virtual addresses. When sufficiently large blocks of memory are freed, a good implementation should also return page frames to the page frame allocator on call to free.
References
Thank you very much for reading!
I’ll hope to get back to you with the article number nine as soon as possible.Till then,
Stay Safe!!! 👋
-Nipuni Perera-
