feat(kernel/vm): allocate virtual memory spot

Implement the `find_spot` method that searches the augmented wavltree of mappings for a suitable gap given a `Layout`. The resulting spot will be randomized, but left-leaning. Further method accepts an `entropy_bits` parameter that can be used to tune the sparseness of produced allocations. More consideration for this parameter can be found in the docs (docs/aslr.md)
JonasKruckenberg · JonasKruckenberg · Dec 15, 2024 · Nov 23, 2024 · Nov 23, 2024 · Nov 23, 2024
commit 7401f98539d6db73f2ca6380cd8c8ee11576c1ed
diff --git a/kernel/src/vm.rs b/kernel/src/vm.rs
@@ -281,6 +281,143 @@ impl AddressSpace {
     pub fn decommit(&mut self, range: Range<VirtualAddress>) {
         todo!()
     }
+
+    // behaviour:
+    // - find the leftmost gap that satisfies the size and alignment requirements
+    //      - starting at the root,
+    pub fn find_spot(&mut self, layout: Layout, entropy: u8) -> VirtualAddress {
+        log::trace!("finding spot for {layout:?} entropy {entropy}");
+
+        let max_candidate_spaces: usize = 1 << entropy;
+        log::trace!("max_candidate_spaces {max_candidate_spaces}");
+
+        let selected_index: usize = self
+            .prng
+            .as_mut()
+            .map(|prng| prng.sample(Uniform::new(0, max_candidate_spaces)))
+            .unwrap_or_default();
+
+        let spot = match self.find_spot_at_index(selected_index, layout) {
+            Ok(spot) => spot,
+            Err(0) => panic!("out of virtual memory"),
+            Err(candidate_spot_count) => {
+                log::trace!("couldn't find spot in first attempt (max_candidate_spaces {max_candidate_spaces}), retrying with (candidate_spot_count {candidate_spot_count})");
+                let selected_index: usize = self
+                    .prng
+                    .as_mut()
+                    .unwrap()
+                    .sample(Uniform::new(0, candidate_spot_count));
+
+                self.find_spot_at_index(selected_index, layout).unwrap()
+            }
+        };
+        log::trace!("picked spot {spot:?}");
+
+        spot
+    }
+
+    pub fn find_spot_at_index(
+        &self,
+        mut target_index: usize,
+        layout: Layout,
+    ) -> Result<VirtualAddress, usize> {
+        log::trace!("attempting to find spot for {layout:?} at index {target_index}");
+
+        let spots_in_range = |layout: Layout, range: Range<VirtualAddress>| -> usize {
+            ((range.end.sub_addr(range.start) - layout.size()) >> layout.align().ilog2()) + 1
+        };
+
+        let mut candidate_spot_count = 0;
+
+        const KERNEL_ASPACE_BASE: VirtualAddress = VirtualAddress::new(0xffffffc000000000);
+
+        // see if there is a suitable gap between the start of the address space and the first mapping
+        if let Some(root) = self.tree.root().get() {
+            let gap_size = root.min_first_byte.sub_addr(KERNEL_ASPACE_BASE);
+            let aligned_gap = KERNEL_ASPACE_BASE.align_up(layout.align())
+                ..KERNEL_ASPACE_BASE.add(gap_size).align_down(layout.align());
+            let spot_count = spots_in_range(layout, aligned_gap.clone());
+            candidate_spot_count += spot_count;
+            if target_index < spot_count {
+                return Ok(aligned_gap
+                    .start
+                    .add(target_index << layout.align().ilog2()));
+            }
+            target_index -= spot_count;
+        }
+
+        let mut maybe_node = self.tree.root().get();
+        let mut already_visited = VirtualAddress::default();
+
+        while let Some(node) = maybe_node {
+            if node.max_gap >= layout.size() {
+                if let Some(left) = node.links.left() {
+                    let left = unsafe { left.as_ref() };
+
+                    if left.max_gap >= layout.size() && left.max_last_byte > already_visited {
+                        maybe_node = Some(left);
+                        continue;
+                    }
+
+                    let gap_base = left.max_last_byte;
+                    let gap_size = node.range.end.sub_addr(left.max_last_byte);
+                    let aligned_gap = gap_base.align_up(layout.align())
+                        ..gap_base.add(gap_size).align_down(layout.align());
+                    let spot_count = spots_in_range(layout, aligned_gap.clone());
+
+                    candidate_spot_count += spot_count;
+                    if target_index < spot_count {
+                        return Ok(aligned_gap
+                            .start
+                            .add(target_index << layout.align().ilog2()));
+                    }
+                    target_index -= spot_count;
+                }
+
+                if let Some(right) = node.links.right() {
+                    let right = unsafe { right.as_ref() };
+
+                    let gap_base = node.range.end;
+                    let gap_size = right.min_first_byte.sub_addr(node.range.end);
+                    let aligned_gap = gap_base.align_up(layout.align())
+                        ..gap_base.add(gap_size).align_down(layout.align());
+                    let spot_count = spots_in_range(layout, aligned_gap.clone());
+
+                    candidate_spot_count += spot_count;
+                    if target_index < spot_count {
+                        return Ok(aligned_gap
+                            .start
+                            .add(target_index << layout.align().ilog2()));
+                    }
+                    target_index -= spot_count;
+
+                    if right.max_gap >= layout.size() && right.max_last_byte > already_visited {
+                        maybe_node = Some(right);
+                        continue;
+                    }
+                }
+            }
+            already_visited = node.max_last_byte;
+            maybe_node = node.links.parent().map(|ptr| unsafe { ptr.as_ref() });
+        }
+
+        // see if there is a suitable gap between the end of the last mapping and the end of the address space
+        if let Some(root) = self.tree.root().get() {
+            let gap_size = usize::MAX - root.max_last_byte.as_raw();
+            let aligned_gap = root.max_last_byte.align_up(layout.align())
+                ..root.max_last_byte.add(gap_size).align_down(layout.align());
+            let spot_count = spots_in_range(layout, aligned_gap.clone());
+            candidate_spot_count += spot_count;
+            if target_index < spot_count {
+                return Ok(aligned_gap
+                    .start
+                    .add(target_index << layout.align().ilog2()));
+            }
+            target_index -= spot_count;
+        }
+
+        Err(candidate_spot_count)
+    }
 }
 
 pin_project! {

diff --git a/manual/src/SUMMARY.md b/manual/src/SUMMARY.md
@@ -13,6 +13,7 @@
 
 - [Overview of k23's Architecture](overview.md)
 - [Boot Flow](boot_flow.md)
+- [Address Space Layout Randomization (ASLR)](aslr.md)
 
 # CPU Architectures
 

diff --git a/manual/src/aslr.md b/manual/src/aslr.md
@@ -0,0 +1,49 @@
+# Address Space Layout Randomization
+
+Address-space layout randomization is a security technique that - as the name implies - randomizes
+the placement of various objects in virtual memory. This well known technique defends against attacks such as 
+return-oriented programming (ROP) where an attacker chains together instruction sequences of legitimate programs 
+(called "gadgets") to archive privilege escalation.
+
+Randomizing the placement of objects makes these techniques much harder since now an attacker has to correctly guess 
+the address from a potentially huge number of possibilities.
+
+## KASLR
+
+k23 randomizes the location of the kernel, stacks, TLS regions and heap at boot time.
+
+## ASLR in k23
+
+k23 implements more advanced userspace ASLR that other operating systems, it not only randomizes the placement of 
+WASM executable code, tables, globals, and memories; but also the location of individual WASM functions at each program 
+startup (a similar technique is used by the Linux kernel called function-grained kernel address space layout randomization (FGKASLR))
+
+TODO explain more in detail
+
+## ASLR Entropy
+
+Entropy determines how "spread out" allocations are in the address space
+higher values mean a more sparse address space, this is configured through the `entropy_bits` option (TODO).
+
+Ideally the number would be as high as possible, since more entropy means harder to defeat
+ASLR. However, a sparser address space requires more memory for page tables and a higher
+value for entropy means allocating virtual memory takes longer (more misses the search function
+that searches for free gaps). The maximum entropy value also depends on the target architecture
+and chosen memory mode:
+
+| Architecture           | Virtual Address Usable Bits | Max Entropy Bits |
+|------------------------|-----------------------------|------------------|
+| Riscv32 Sv32           | 32                          | 19               |
+| Riscv64 Sv39           | 39                          | 26               |
+| Riscv64 Sv48           | 48                          | 35               |
+| Riscv64 Sv57           | 57                          | 44               |
+| x86_64                 | 48                          | 35               |
+| aarch64 3 TLB lvls     | 39                          | 26               |
+| aarch64 4 TLB lvls     | 48                          | 35               |
+
+In conclusion, the best value for `entropy_bits` depends on a lot of factors and should be tuned
+for best results trading off sparseness and runtime complexity for better security.
+
+Note also that for e.g. Riscv64 Sv57 it might not even be desirable to use all 44 bits of
+available entropy since the address space itself is already huge and performance might degrade
+too much.