Nothing to see here, move along meow
1use std::collections::HashMap;
2
3use lancer_core::cap_table::{CapRef, CapSlot, Rights};
4use lancer_core::cnode::{self, CNodeStore, MAX_RESOLVE_DEPTH};
5use lancer_core::error::KernelError;
6use lancer_core::object_tag::ObjectTag;
7use lancer_core::types::{Generation, ObjPhys};
8use proptest::prelude::*;
9
10struct MockCNodeStore {
11 nodes: HashMap<(u32, u32), (Vec<CapSlot>, u8)>,
12}
13
14impl MockCNodeStore {
15 fn new() -> Self {
16 Self {
17 nodes: HashMap::new(),
18 }
19 }
20
21 fn insert_cnode(&mut self, id: u32, gen_val: u32, size_bits: u8, slots: Vec<CapSlot>) {
22 self.nodes.insert((id, gen_val), (slots, size_bits));
23 }
24}
25
26impl CNodeStore for MockCNodeStore {
27 fn read_slot(
28 &self,
29 cnode_phys: ObjPhys,
30 cnode_gen: Generation,
31 index: usize,
32 ) -> Result<CapSlot, KernelError> {
33 let key = (cnode_phys.raw() as u32, cnode_gen.raw() as u32);
34 let (slots, size_bits) = self.nodes.get(&key).ok_or(KernelError::StaleGeneration)?;
35 let max = 1usize << *size_bits;
36 match index < max && index < slots.len() {
37 true => Ok(slots[index]),
38 false => Err(KernelError::InvalidSlot),
39 }
40 }
41
42 fn size_bits(&self, cnode_phys: ObjPhys, cnode_gen: Generation) -> Result<u8, KernelError> {
43 let key = (cnode_phys.raw() as u32, cnode_gen.raw() as u32);
44 self.nodes
45 .get(&key)
46 .map(|(_, sb)| *sb)
47 .ok_or(KernelError::StaleGeneration)
48 }
49}
50
51fn id(v: u32) -> ObjPhys {
52 ObjPhys::new(v as u64)
53}
54
55fn generation(v: u32) -> Generation {
56 Generation::new(v)
57}
58
59proptest! {
60 #[test]
61 fn guard_mismatch_always_errors(
62 guard_bits in 1u8..=16,
63 size_bits in 1u8..=8,
64 guard_value in 0u64..=0xFFFF,
65 mismatch_delta in 1u64..=0xFF,
66 ) {
67 let total = guard_bits + size_bits;
68 prop_assume!(total <= 64);
69 prop_assume!(guard_bits < 64);
70
71 let max_guard = (1u64 << guard_bits) - 1;
72 let gv = guard_value & max_guard;
73 let wrong_guard = (gv ^ mismatch_delta) & max_guard;
74 prop_assume!(wrong_guard != gv);
75
76 let slot_count = 1usize << size_bits;
77 let mut store = MockCNodeStore::new();
78 store.insert_cnode(0, 0, size_bits, vec![CapSlot::Empty; slot_count]);
79
80 let address = wrong_guard << size_bits;
81 let result = cnode::resolve(
82 &store, id(0), generation(0), address, total, gv, guard_bits,
83 );
84 prop_assert!(matches!(result, Err(KernelError::GuardMismatch)));
85 }
86
87 #[test]
88 fn correct_address_resolves_to_correct_slot(
89 size_bits in 1u8..=8,
90 guard_bits in 0u8..=8,
91 slot_idx in 0u16..256,
92 ) {
93 let total = guard_bits as u16 + size_bits as u16;
94 prop_assume!(total <= 64);
95
96 let slot_count = 1usize << size_bits;
97 let idx = (slot_idx as usize) % slot_count;
98
99 let guard_value = match guard_bits {
100 0 => 0u64,
101 64 => 0u64,
102 b => 0x5u64 & ((1u64 << b) - 1),
103 };
104
105 let address = (guard_value << size_bits) | (idx as u64);
106
107 let ep_cap = CapRef::new(ObjectTag::Endpoint, id(42), Rights::ALL, generation(0));
108 let mut slots = vec![CapSlot::Empty; slot_count];
109 slots[idx] = CapSlot::Active(ep_cap);
110
111 let mut store = MockCNodeStore::new();
112 store.insert_cnode(0, 0, size_bits, slots);
113
114 let result = cnode::resolve(
115 &store, id(0), generation(0), address, total as u8, guard_value, guard_bits,
116 );
117 match result {
118 Ok(CapSlot::Active(cap)) => {
119 prop_assert_eq!(cap.phys(), id(42));
120 prop_assert_eq!(cap.tag(), ObjectTag::Endpoint);
121 }
122 Ok(CapSlot::Empty) => {
123 prop_assert_eq!(idx, 0);
124 }
125 Err(e) => prop_assert!(false, "unexpected error: {:?}", e),
126 }
127 }
128
129 #[test]
130 fn two_level_resolution_correct(
131 outer_bits in 1u8..=4,
132 inner_bits in 1u8..=4,
133 outer_guard in 0u8..=4,
134 inner_guard in 0u8..=4,
135 ) {
136 let outer_total = outer_guard as u16 + outer_bits as u16;
137 let inner_total = inner_guard as u16 + inner_bits as u16;
138 let total_depth = outer_total + inner_total;
139 prop_assume!(total_depth <= 32);
140
141 let outer_slot_count = 1usize << outer_bits;
142 let inner_slot_count = 1usize << inner_bits;
143
144 let outer_gv = match outer_guard {
145 0 => 0u64,
146 b => 1u64 & ((1u64 << b) - 1),
147 };
148 let inner_gv = match inner_guard {
149 0 => 0u64,
150 b => 1u64 & ((1u64 << b) - 1),
151 };
152
153 let outer_idx = 0usize;
154 let inner_idx = 0usize;
155
156 let ep_cap = CapRef::new(ObjectTag::Endpoint, id(99), Rights::ALL, generation(0));
157 let mut inner_slots = vec![CapSlot::Empty; inner_slot_count];
158 inner_slots[inner_idx] = CapSlot::Active(ep_cap);
159
160 let inner_cnode_cap = CapRef::new_with_guard(
161 ObjectTag::CNode, id(1), Rights::ALL, generation(0), inner_gv, inner_guard,
162 );
163 let mut outer_slots = vec![CapSlot::Empty; outer_slot_count];
164 outer_slots[outer_idx] = CapSlot::Active(inner_cnode_cap);
165
166 let mut store = MockCNodeStore::new();
167 store.insert_cnode(0, 0, outer_bits, outer_slots);
168 store.insert_cnode(1, 0, inner_bits, inner_slots);
169
170 let address = (outer_gv << (outer_bits as u64 + inner_total as u64))
171 | ((outer_idx as u64) << inner_total as u64)
172 | (inner_gv << inner_bits)
173 | (inner_idx as u64);
174
175 let result = cnode::resolve(
176 &store, id(0), generation(0), address, total_depth as u8, outer_gv, outer_guard,
177 );
178 match result {
179 Ok(CapSlot::Active(cap)) => {
180 prop_assert_eq!(cap.phys(), id(99));
181 }
182 Ok(CapSlot::Empty) => {}
183 Err(e) => prop_assert!(false, "unexpected error: {:?}", e),
184 }
185 }
186
187 #[test]
188 fn bit_consumption_exhaustive(
189 guard_bits in 0u8..=8,
190 size_bits in 1u8..=8,
191 ) {
192 let total = guard_bits as u16 + size_bits as u16;
193 prop_assume!(total <= 64);
194
195 let guard_value = match guard_bits {
196 0 => 0u64,
197 b => 0u64 & ((1u64 << b) - 1),
198 };
199
200 let slot_count = 1usize << size_bits;
201 let mut store = MockCNodeStore::new();
202 store.insert_cnode(0, 0, size_bits, vec![CapSlot::Empty; slot_count]);
203
204 let address = guard_value << size_bits;
205 let result = cnode::resolve(
206 &store, id(0), generation(0), address, total as u8, guard_value, guard_bits,
207 );
208
209 prop_assert!(result.is_ok(), "guard_bits({}) + size_bits({}) = depth({}) should resolve", guard_bits, size_bits, total);
210 }
211
212 #[test]
213 fn excess_remaining_bits_without_cnode_errors(
214 size_bits in 1u8..=4,
215 extra_bits in 1u8..=4,
216 ) {
217 let total = size_bits as u16 + extra_bits as u16;
218 prop_assume!(total <= 32);
219
220 let slot_count = 1usize << size_bits;
221 let ep_cap = CapRef::new(ObjectTag::Endpoint, id(7), Rights::ALL, generation(0));
222 let mut slots = vec![CapSlot::Empty; slot_count];
223 slots[0] = CapSlot::Active(ep_cap);
224
225 let mut store = MockCNodeStore::new();
226 store.insert_cnode(0, 0, size_bits, slots);
227
228 let result = cnode::resolve(
229 &store, id(0), generation(0), 0, total as u8, 0, 0,
230 );
231 prop_assert!(matches!(result, Err(KernelError::InvalidSlot)),
232 "non-CNode with remaining bits should return InvalidSlot, got {:?}", result);
233 }
234}
235
236#[test]
237fn max_recursion_depth_exceeded() {
238 let chain_len = (MAX_RESOLVE_DEPTH + 1) as u32;
239 let size_bits = 1u8;
240
241 let mut store = MockCNodeStore::new();
242
243 (0..chain_len).for_each(|i| {
244 let next = i + 1;
245 let cap =
246 CapRef::new_with_guard(ObjectTag::CNode, id(next), Rights::ALL, generation(0), 0, 0);
247 store.insert_cnode(i, 0, size_bits, vec![CapSlot::Active(cap), CapSlot::Empty]);
248 });
249
250 store.insert_cnode(chain_len, 0, size_bits, vec![CapSlot::Empty; 2]);
251
252 let total_depth = ((chain_len + 1) as u32 * size_bits as u32).min(64) as u8;
253 let result = cnode::resolve(&store, id(0), generation(0), 0, total_depth, 0, 0);
254 assert!(
255 matches!(result, Err(KernelError::InvalidSlot)),
256 "chain of {} CNodes should exceed max recursion depth, got {:?}",
257 chain_len,
258 result
259 );
260}