sbpf_common/
syscalls_map.rs

1use syscall_map::murmur3_32;
2
3// Simple const hashmap implementation using binary search on sorted array
4// Supports both static (compile-time) and dynamic (runtime) syscall lists via lifetimes
5pub struct SyscallMap<'a> {
6    entries: &'a [(u32, &'a str)],
7}
8
9impl<'a> SyscallMap<'a> {
10    /// Create from a pre-sorted slice of (hash, name) pairs
11    /// Works for both static and dynamic lifetimes
12    pub const fn from_entries(entries: &'a [(u32, &'a str)]) -> Self {
13        // Check for hash conflicts
14        let mut i = 0;
15        while i < entries.len() - 1 {
16            if entries[i].0 == entries[i + 1].0 {
17                panic!("Hash conflict detected between syscalls");
18            }
19            i += 1;
20        }
21
22        Self { entries }
23    }
24
25    pub const fn get(&self, hash: u32) -> Option<&'a str> {
26        // Binary search in const context
27        let mut left = 0;
28        let mut right = self.entries.len();
29
30        while left < right {
31            let mid = (left + right) / 2;
32            if self.entries[mid].0 == hash {
33                return Some(self.entries[mid].1);
34            } else if self.entries[mid].0 < hash {
35                left = mid + 1;
36            } else {
37                right = mid;
38            }
39        }
40        None
41    }
42
43    pub const fn len(&self) -> usize {
44        self.entries.len()
45    }
46
47    pub const fn is_empty(&self) -> bool {
48        self.entries.is_empty()
49    }
50}
51
52/// Runtime-mutable syscall map that owns its data
53/// This allows for dynamic updates at runtime
54pub struct DynamicSyscallMap {
55    // Store entries as (hash, name) pairs, kept sorted by hash
56    entries: Vec<(u32, String)>,
57}
58
59impl DynamicSyscallMap {
60    /// Create a new dynamic syscall map from owned strings
61    pub fn new(syscalls: Vec<String>) -> Result<Self, String> {
62        let mut entries: Vec<(u32, String)> = syscalls
63            .into_iter()
64            .map(|name| (murmur3_32(&name), name))
65            .collect();
66
67        entries.sort_by_key(|(hash, _)| *hash);
68
69        // Check for conflicts
70        for i in 0..entries.len().saturating_sub(1) {
71            if entries[i].0 == entries[i + 1].0 {
72                return Err(format!(
73                    "Hash conflict detected between syscalls '{}' and '{}'",
74                    entries[i].1,
75                    entries[i + 1].1
76                ));
77            }
78        }
79
80        Ok(Self { entries })
81    }
82
83    /// Create from string slices (convenience method)
84    pub fn from_names(names: &[&str]) -> Result<Self, String> {
85        Self::new(names.iter().map(|&s| s.to_string()).collect())
86    }
87
88    /// Look up a syscall by hash
89    pub fn get(&self, hash: u32) -> Option<&str> {
90        match self.entries.binary_search_by_key(&hash, |(h, _)| *h) {
91            Ok(idx) => Some(&self.entries[idx].1),
92            Err(_) => None,
93        }
94    }
95
96    /// Add a new syscall at runtime
97    pub fn add(&mut self, name: String) -> Result<(), String> {
98        let hash = murmur3_32(&name);
99
100        // Check if it already exists or would conflict
101        match self.entries.binary_search_by_key(&hash, |(h, _)| *h) {
102            Ok(_) => Err(format!(
103                "Hash conflict: '{}' conflicts with existing syscall",
104                name
105            )),
106            Err(pos) => {
107                self.entries.insert(pos, (hash, name));
108                Ok(())
109            }
110        }
111    }
112
113    pub fn len(&self) -> usize {
114        self.entries.len()
115    }
116
117    pub fn is_empty(&self) -> bool {
118        self.entries.is_empty()
119    }
120}
121
122/// Convert a static SyscallMap to a dynamic one
123impl<'a> From<&SyscallMap<'a>> for DynamicSyscallMap {
124    fn from(static_map: &SyscallMap<'a>) -> Self {
125        let entries = static_map
126            .entries
127            .iter()
128            .map(|(hash, name)| (*hash, name.to_string()))
129            .collect();
130
131        Self { entries }
132    }
133}
134
135/// Helper function for compile-time syscall map creation
136/// Computes hashes and sorts entries at compile time
137pub const fn compute_syscall_entries_const<'a, const N: usize>(
138    syscalls: &'a [&'a str],
139) -> [(u32, &'a str); N] {
140    let mut entries: [(u32, &str); N] = [(0, ""); N];
141    let mut i = 0;
142    while i < N {
143        entries[i] = (murmur3_32(syscalls[i]), syscalls[i]);
144        i += 1;
145    }
146
147    // Sort the entries at compile time using bubble sort
148    let mut i = 0;
149    while i < N {
150        let mut j = 0;
151        while j < N - i - 1 {
152            if entries[j].0 > entries[j + 1].0 {
153                let temp = entries[j];
154                entries[j] = entries[j + 1];
155                entries[j + 1] = temp;
156            }
157            j += 1;
158        }
159        i += 1;
160    }
161
162    entries
163}
164
165/// Runtime helper for dynamic syscall lists
166/// Computes hashes and sorts entries, borrowing from the input
167///
168/// The caller must own the string data (e.g., Vec<String>) and pass references.
169/// This function returns references to those owned strings.
170pub fn compute_syscall_entries<'a, T: AsRef<str>>(syscalls: &'a [T]) -> Vec<(u32, &'a str)> {
171    let mut entries: Vec<(u32, &'a str)> = syscalls
172        .iter()
173        .map(|name| (murmur3_32(name.as_ref()), name.as_ref()))
174        .collect();
175
176    entries.sort_by_key(|(hash, _)| *hash);
177
178    // Check for conflicts
179    for i in 0..entries.len().saturating_sub(1) {
180        if entries[i].0 == entries[i + 1].0 {
181            panic!(
182                "Hash conflict detected between syscalls '{}' and '{}'",
183                entries[i].1,
184                entries[i + 1].1
185            );
186        }
187    }
188
189    entries
190}
191
192#[cfg(test)]
193mod tests {
194    use {
195        super::*,
196        crate::syscalls::{REGISTERED_SYSCALLS, SYSCALLS},
197        syscall_map::murmur3_32,
198    };
199
200    #[test]
201    fn test_syscall_lookup() {
202        // Test that all syscalls can be found
203        for &name in REGISTERED_SYSCALLS.iter() {
204            let hash = murmur3_32(name);
205            assert_eq!(
206                SYSCALLS.get(hash),
207                Some(name),
208                "Failed to find syscall: {}",
209                name
210            );
211        }
212    }
213
214    #[test]
215    fn test_const_evaluation() {
216        // Verify const evaluation works at compile time
217        const ABORT_HASH: u32 = murmur3_32("abort");
218        const SOL_LOG_HASH: u32 = murmur3_32("sol_log_");
219
220        // Verify the hashes are computed correctly and can look up syscalls
221        assert_eq!(SYSCALLS.get(ABORT_HASH), Some("abort"));
222        assert_eq!(SYSCALLS.get(SOL_LOG_HASH), Some("sol_log_"));
223    }
224
225    #[test]
226    fn test_nonexistent_syscall() {
227        // Test that non-existent syscalls return None
228        assert_eq!(SYSCALLS.get(0xDEADBEEF), None);
229    }
230
231    #[test]
232    fn test_dynamic_syscalls() {
233        // Example: Create a dynamic syscall map with owned strings
234        // The caller owns the strings (e.g., from user input, config file, etc.)
235        let owned_syscalls: Vec<String> = vec![
236            String::from("my_custom_syscall"),
237            String::from("another_syscall"),
238        ];
239
240        // Compute entries - they borrow from owned_syscalls
241        let entries = compute_syscall_entries(&owned_syscalls);
242
243        // Create the map - it borrows from entries
244        let map = SyscallMap::from_entries(&entries);
245
246        // Verify lookups work
247        let hash1 = murmur3_32("my_custom_syscall");
248        let hash2 = murmur3_32("another_syscall");
249
250        assert_eq!(map.get(hash1), Some("my_custom_syscall"));
251        assert_eq!(map.get(hash2), Some("another_syscall"));
252
253        // The lifetimes ensure owned_syscalls outlives both entries and map
254    }
255
256    #[test]
257    fn test_dynamic_syscalls_with_str_slices() {
258        // Also works with &str slices
259        let syscalls: Vec<&str> = vec!["syscall_a", "syscall_b", "syscall_c"];
260
261        let entries = compute_syscall_entries(&syscalls);
262        let map = SyscallMap::from_entries(&entries);
263
264        assert_eq!(map.get(murmur3_32("syscall_a")), Some("syscall_a"));
265        assert_eq!(map.get(murmur3_32("syscall_b")), Some("syscall_b"));
266        assert_eq!(map.get(murmur3_32("syscall_c")), Some("syscall_c"));
267    }
268
269    #[test]
270    fn test_static_custom_map() {
271        // Example: Create a static custom syscall map at compile time
272        const CUSTOM_SYSCALLS: &[&str; 2] = &["test1", "test2"];
273        const CUSTOM_ENTRIES: &[(u32, &str); 2] = &compute_syscall_entries_const(CUSTOM_SYSCALLS);
274        const CUSTOM_MAP: SyscallMap<'static> = SyscallMap::from_entries(CUSTOM_ENTRIES);
275
276        assert_eq!(CUSTOM_MAP.get(murmur3_32("test1")), Some("test1"));
277        assert_eq!(CUSTOM_MAP.get(murmur3_32("test2")), Some("test2"));
278    }
279
280    #[test]
281    fn test_dynamic_mutable_map() {
282        // Example: Create a fully dynamic, mutable syscall map
283        let mut map = DynamicSyscallMap::from_names(&["initial_syscall"]).unwrap();
284
285        // Initial lookup works
286        assert_eq!(
287            map.get(murmur3_32("initial_syscall")),
288            Some("initial_syscall")
289        );
290
291        // Add new syscalls at runtime
292        map.add("runtime_syscall_1".to_string()).unwrap();
293        map.add("runtime_syscall_2".to_string()).unwrap();
294
295        // All lookups work
296        assert_eq!(
297            map.get(murmur3_32("initial_syscall")),
298            Some("initial_syscall")
299        );
300        assert_eq!(
301            map.get(murmur3_32("runtime_syscall_1")),
302            Some("runtime_syscall_1")
303        );
304        assert_eq!(
305            map.get(murmur3_32("runtime_syscall_2")),
306            Some("runtime_syscall_2")
307        );
308
309        // Non-existent syscall returns None
310        assert_eq!(map.get(0xDEADBEEF), None);
311
312        // Verify count
313        assert_eq!(map.len(), 3);
314    }
315
316    #[test]
317    fn test_dynamic_map_with_owned_strings() {
318        // Create from owned strings directly
319        let syscalls = vec![
320            String::from("custom_1"),
321            String::from("custom_2"),
322            String::from("custom_3"),
323        ];
324
325        let mut map = DynamicSyscallMap::new(syscalls).unwrap();
326
327        assert_eq!(map.get(murmur3_32("custom_1")), Some("custom_1"));
328        assert_eq!(map.get(murmur3_32("custom_2")), Some("custom_2"));
329        assert_eq!(map.get(murmur3_32("custom_3")), Some("custom_3"));
330
331        // Add more at runtime
332        map.add("custom_4".to_string()).unwrap();
333        assert_eq!(map.get(murmur3_32("custom_4")), Some("custom_4"));
334    }
335
336    #[test]
337    fn test_convert_static_to_dynamic() {
338        // Start with the static syscall map
339        let dynamic = DynamicSyscallMap::from(&SYSCALLS);
340
341        // Verify all static syscalls are present
342        for &name in REGISTERED_SYSCALLS.iter() {
343            let hash = murmur3_32(name);
344            assert_eq!(
345                dynamic.get(hash),
346                Some(name),
347                "Failed to find syscall: {}",
348                name
349            );
350        }
351
352        // Verify we can add new syscalls to it
353        let mut dynamic_mut = dynamic;
354        dynamic_mut.add("my_custom_syscall".to_string()).unwrap();
355
356        assert_eq!(
357            dynamic_mut.get(murmur3_32("my_custom_syscall")),
358            Some("my_custom_syscall")
359        );
360
361        // Original static syscalls still work
362        assert_eq!(dynamic_mut.get(murmur3_32("abort")), Some("abort"));
363
364        // Count should be original + 1
365        assert_eq!(dynamic_mut.len(), REGISTERED_SYSCALLS.len() + 1);
366    }
367
368    #[test]
369    fn test_syscall_map_len_and_is_empty() {
370        // Test static map
371        assert!(!SYSCALLS.is_empty());
372
373        // Test map with single element
374        const SINGLE_ENTRIES: &[(u32, &str)] = &[(123, "test")];
375        const SINGLE_MAP: SyscallMap = SyscallMap::from_entries(SINGLE_ENTRIES);
376        assert_eq!(SINGLE_MAP.len(), 1);
377        assert!(!SINGLE_MAP.is_empty());
378    }
379
380    #[test]
381    fn test_dynamic_map_len_and_is_empty() {
382        // Test empty dynamic map
383        let empty_map = DynamicSyscallMap::new(vec![]).unwrap();
384        assert_eq!(empty_map.len(), 0);
385        assert!(empty_map.is_empty());
386
387        // Test non-empty dynamic map
388        let map = DynamicSyscallMap::from_names(&["test"]).unwrap();
389        assert_eq!(map.len(), 1);
390        assert!(!map.is_empty());
391    }
392
393    #[test]
394    fn test_dynamic_map_add_duplicate() {
395        let mut map = DynamicSyscallMap::from_names(&["existing"]).unwrap();
396        let result = map.add("existing".to_string());
397        assert!(result.is_err());
398    }
399
400    #[test]
401    fn test_dynamic_map_hash_conflict_in_creation() {
402        let syscalls = vec![String::from("test"), String::from("test")];
403        let result = DynamicSyscallMap::new(syscalls);
404        // Should error due to duplicate hash
405        assert!(result.is_err());
406        if let Err(msg) = result {
407            assert!(msg.contains("Hash conflict"));
408            assert!(msg.contains("test"));
409        }
410    }
411}
sbpf_common/syscalls_map.rs

sbpf_common/
syscalls_map.rs
