---
# System prepended metadata

title: 'SMP: Paging + Physical Frames Buddy Allocator'

---

# Paging in Unikraft - Summary

- In order to add a mapping for a virtual address range in the page table, the paging support exposes the `ukplat_page_mapx()` function.
This function will travel through the page table levels until the last level and call the physical frames allocator for allocating the physical pages.
In this process, every time a page entry is found empty on a level, the physical frames allocator is called in order to allocate the next level page table corresponding to that entry.

- For unmapping a virtual address range, the `ukplat_page_unmap() `function is exposed.
This function will travel through the page table levels until the last level and call the physical frames allocator for freeing the physical pages.
After this, the page table is traversed backwards, so that any page tables that have no more valid entries after this free operation will be freed.

# Synchronization Proposal

At this point, I don't see an optimized way of synchronizing the page table accesses.

During the mapping process, the page table traversal needs to be completely serialized.
Otherwise, two different threads that follow the same path up to a level could see an invalid page table entry at the same time.
If this is the case, the threads allocate the same page table twice.
Even worse, they will try to write the same page table entry in parallel.

During the unmapping process, one thread may decide that all the entries in a page table are invalid.
Thus, the page table will be freed.
Two race conditions are possible in this case:
- A mapping happens in parallel on another thread.
In this case, the other thread may try to complete an entry in the page table while it is freed. Therefore, a race condition occurs.
- An unmapping happens in parallel on another thread.
This may result in two different threads trying to free the same table.

For these reasons, I suggest starting with using a single lock for the entire `ukplat_page_mapx()` and `ukplat_page_unmap()` functions.
This could be a solution so that we have things prepared in time for the 1.0 release.
Then, we can start considering researching if we can change the page table structures, so that they allow for a more efficient synchronization.

One interesting point to start from is the Linux kernel, which initially implemented a single-lock approach too, and then moved on to [splitted page table locks](https://www.kernel.org/doc/html/v5.7/vm/split_page_table_lock.html).

# Impact on the physical allocator synchronization

Since the physical frames buddy allocator is mostly called by `ukplat_page_unmap()` and `ukplat_page_mapx()`, serializing these functions means that the calls to the physical frames allocator will be serialized too.
Therefore, I propose the following steps, in this order:
1. integrate an intial synchronization that uses a single lock (as described above)
2. do the research for efficient synchronization of the page tables (and implement it)
3. implement efficient synchronization for the frames buddy allocator, based on the experience gained while working on the binary buddy allocator