In today’s somewhat delayed post, I will be talking about the page allocator that I wrote to port the Palacios VMM to the Nautilus kernel.
In operating systems and kernels, a page refers to a block of memory. It’s a basic unit of memory chunk that the kernel uses to allocate memory to user level programs. Kernels need units of memory, and these are often allocated in terms of pages. For example, a page table is usually allocated within a page by the kernel. Page size may differ across different platforms (ex. 4KB on a Linux kernel) and the size affects the performance of the kernel page allocator.
A page allocator on the other hand, is what divides up the virtual memory into chunks and then allocate them to the kernel. In my project, Palacios VMM needs its own page allocator, because Nautilus and Palacios have different page sizes. Nautilus has a page size of 2MB, which is 500 times greater than that of Palacios, which is the standard 4KB pages that Linux kernels use. This means that if Palacios ask for a page from its host, Nautilus, it will receive 2MB pages instead of 4KB. When Palacios was ported to the Linux kernel, this was not a problem because page sizes are 4KB in Linux kernels – however, I need a page allocator that can allocate a certain number of 2MB pages and then reallocate it for the guest in chunks of 4KB. This process is (somewhat) better shown in the diagram below.
There are numerous algorithms that exist for this, and one of the best known algorithms for doing this is the buddy allocator. I was tempted to use this algorithm at first, but my advisor Prof. Peter Dinda suggested using a simple allocator “that works” first. This is because if I happen to have a bug in the page allocator itself, I wouldn’t be able to proceed until I catch this bug. Or even worse, it might seem to not have any bugs at the time I write it but actually have a bug that doesn’t get revealed until later stage in the research, which would be hard to track down and fix. Taking his advice, I decided to use the simplest allocator possible, which is the bitmap allocator. This algorithm uses a single bit to indicate whether a page is free or not (1 or 0). Hence, it significantly reduces the extra space I need for this allocator itself. (A memory allocator takes up memory itself) The diagram below shows how this algorithm works in a visual way.
Red = Allocated, Green = Free
My implementation of bitmap page allocator has an array of bits, each bit representing a page on Palacios. The first row shows a state – it has some pages allocated to the kernel, and most of them free. If Palacios calls alloc(2), which means “give me 2 pages”, the allocator goes through each bit and sees if there are 2 contiguous bits that are marked as 0 (green). It reaches the third bit and sees that it is free, but the next one is already occupied. Hence this page cannot be allocated. It keeps going, until it sees the 8th bit, which does have 2 contiguous bits that are free. It then allocates this particular page and marks them as allocated (colored orange on the second row in the diagram above). Similarly, if another request comes in to allocate 1 page, it can now allocate the page referred by the 3rd bit, since it only needs 1 pages.
It is important to note that this algorithm is not a particularly efficient one in terms of performance, because it tries to search the entire bits one by one in a linear time (actually, quadratic in my initial implementation but I fixed it) However, it is very simple and simplicity prevents bugs from happening (~150 lines of C code) Eventually I am planning to dig further into this and write an optimized allocator that best suits the need of this particular project, but decided to move on for now.