veridian_kernel/mm/
ksm.rs

1//! Kernel Same-page Merging (KSM)
2//!
3//! Scans anonymous user-space pages for identical content and merges
4//! duplicates via Copy-on-Write (COW) mappings.  Reduces memory
5//! consumption for workloads with many similar processes (e.g. KDE
6//! Plasma applets, browser tabs, containerized services).
7//!
8//! Design:
9//!   - **Unstable tree**: pages seen once, awaiting confirmation across
10//!     multiple scan cycles before promotion.
11//!   - **Stable tree**: pages confirmed identical, merged via COW.
12//!   - **FNV-1a hash**: fast 32-bit content hash for candidate filtering
13//!     (integer-only, no floating point).
14//!   - **Full comparison**: byte-for-byte equality check on hash match before
15//!     merging.
16//!
17//! Pages are identified by frame number (`FrameNumber`).  The scanner
18//! does not touch kernel pages, device-mapped pages, or already-merged
19//! pages.
20
21#![allow(dead_code)]
22
23use core::sync::atomic::{AtomicBool, AtomicU64, Ordering};
24
25use crate::mm::{FrameNumber, PAGE_SIZE};
26
27/// FNV-1a hash constants (32-bit, integer-only).
28const FNV_OFFSET_BASIS: u32 = 2_166_136_261;
29const FNV_PRIME: u32 = 16_777_619;
30
31/// Default number of pages to scan per cycle.
32const DEFAULT_SCAN_RATE: usize = 100;
33
34/// Default delay between scan cycles in milliseconds.
35const DEFAULT_SLEEP_MS: u64 = 200;
36
37/// Number of consecutive stable scans required before promotion
38/// from unstable to stable tree.
39const PROMOTION_THRESHOLD: u32 = 3;
40
41/// Maximum number of entries in the stable tree.
42const MAX_STABLE_ENTRIES: usize = 4096;
43
44/// Maximum number of entries in the unstable tree.
45const MAX_UNSTABLE_ENTRIES: usize = 4096;
46
47// =========================================================================
48// FNV-1a hash
49// =========================================================================
50
51/// Compute a 32-bit FNV-1a hash of a byte slice.
52///
53/// This is a fast, non-cryptographic hash suitable for content
54/// fingerprinting.  Uses only integer arithmetic (no floating point).
55pub(crate) fn fnv1a_hash(data: &[u8]) -> u32 {
56    let mut hash = FNV_OFFSET_BASIS;
57    for &byte in data {
58        hash ^= byte as u32;
59        hash = hash.wrapping_mul(FNV_PRIME);
60    }
61    hash
62}
63
64// =========================================================================
65// Tree entries
66// =========================================================================
67
68/// An entry in the stable tree: a page whose content has been confirmed
69/// identical to at least one other page across multiple scan cycles.
70#[derive(Clone)]
71struct StableEntry {
72    /// Frame number of the canonical (kept) page.
73    frame: FrameNumber,
74    /// FNV-1a hash of the page content at merge time.
75    hash: u32,
76    /// Number of other pages currently mapped COW to this frame.
77    sharing_count: u32,
78    /// Whether this entry is occupied.
79    active: bool,
80}
81
82impl Default for StableEntry {
83    fn default() -> Self {
84        Self {
85            frame: FrameNumber::new(0),
86            hash: 0,
87            sharing_count: 0,
88            active: false,
89        }
90    }
91}
92
93/// An entry in the unstable tree: a page seen during scanning that is
94/// waiting for confirmation before promotion to the stable tree.
95#[derive(Clone)]
96struct UnstableEntry {
97    /// Frame number of the candidate page.
98    frame: FrameNumber,
99    /// FNV-1a hash at last scan.
100    hash: u32,
101    /// Number of consecutive scans with unchanged content.
102    stable_count: u32,
103    /// Whether this entry is occupied.
104    active: bool,
105}
106
107impl Default for UnstableEntry {
108    fn default() -> Self {
109        Self {
110            frame: FrameNumber::new(0),
111            hash: 0,
112            stable_count: 0,
113            active: false,
114        }
115    }
116}
117
118// =========================================================================
119// KSM statistics
120// =========================================================================
121
122/// Statistics reported by the KSM scanner.
123#[derive(Debug, Clone, Copy, Default)]
124pub struct KsmStats {
125    /// Pages currently merged (canonical pages in stable tree).
126    pub pages_shared: u64,
127    /// Pages currently mapped COW to a shared page.
128    pub pages_sharing: u64,
129    /// Pages scanned but not merged (unique content).
130    pub pages_unshared: u64,
131    /// Total pages scanned since last reset.
132    pub pages_scanned: u64,
133    /// Ratio: pages_sharing / pages_shared (x100 for integer display).
134    pub merge_ratio_x100: u64,
135}
136
137// =========================================================================
138// KSM scanner
139// =========================================================================
140
141/// Kernel Same-page Merging scanner.
142///
143/// Maintains stable and unstable trees of page content hashes and
144/// orchestrates scanning, comparison, and merge operations.
145pub struct KsmScanner {
146    /// Number of pages to scan per cycle.
147    scan_rate: usize,
148    /// Delay between scan cycles in milliseconds.
149    sleep_ms: u64,
150    /// Whether the scanner is currently enabled.
151    enabled: AtomicBool,
152
153    /// Stable tree: confirmed identical pages.
154    stable: [StableEntry; MAX_STABLE_ENTRIES],
155    stable_count: usize,
156
157    /// Unstable tree: candidate pages awaiting confirmation.
158    unstable: [UnstableEntry; MAX_UNSTABLE_ENTRIES],
159    unstable_count: usize,
160
161    /// Running statistics.
162    stats_shared: AtomicU64,
163    stats_sharing: AtomicU64,
164    stats_unshared: AtomicU64,
165    stats_scanned: AtomicU64,
166}
167
168impl Default for KsmScanner {
169    fn default() -> Self {
170        Self::new()
171    }
172}
173
174impl KsmScanner {
175    /// Create a new KSM scanner with default configuration.
176    pub const fn new() -> Self {
177        // const-friendly initialization using arrays of default values
178        const STABLE_INIT: StableEntry = StableEntry {
179            frame: FrameNumber::new(0),
180            hash: 0,
181            sharing_count: 0,
182            active: false,
183        };
184        const UNSTABLE_INIT: UnstableEntry = UnstableEntry {
185            frame: FrameNumber::new(0),
186            hash: 0,
187            stable_count: 0,
188            active: false,
189        };
190
191        Self {
192            scan_rate: DEFAULT_SCAN_RATE,
193            sleep_ms: DEFAULT_SLEEP_MS,
194            enabled: AtomicBool::new(false),
195            stable: [STABLE_INIT; MAX_STABLE_ENTRIES],
196            stable_count: 0,
197            unstable: [UNSTABLE_INIT; MAX_UNSTABLE_ENTRIES],
198            unstable_count: 0,
199            stats_shared: AtomicU64::new(0),
200            stats_sharing: AtomicU64::new(0),
201            stats_unshared: AtomicU64::new(0),
202            stats_scanned: AtomicU64::new(0),
203        }
204    }
205
206    /// Initialize the scanner.  Must be called once before `enable()`.
207    pub fn init(&mut self) {
208        self.stable_count = 0;
209        self.unstable_count = 0;
210        self.stats_shared.store(0, Ordering::Relaxed);
211        self.stats_sharing.store(0, Ordering::Relaxed);
212        self.stats_unshared.store(0, Ordering::Relaxed);
213        self.stats_scanned.store(0, Ordering::Relaxed);
214
215        for entry in self.stable.iter_mut() {
216            entry.active = false;
217        }
218        for entry in self.unstable.iter_mut() {
219            entry.active = false;
220        }
221    }
222
223    /// Set the number of pages to scan per cycle.
224    pub fn set_scan_rate(&mut self, pages_per_cycle: usize) {
225        self.scan_rate = if pages_per_cycle == 0 {
226            1
227        } else {
228            pages_per_cycle
229        };
230    }
231
232    /// Set the delay between scan cycles in milliseconds.
233    pub fn set_sleep_ms(&mut self, ms: u64) {
234        self.sleep_ms = ms;
235    }
236
237    /// Enable the KSM scanner.
238    pub fn enable(&self) {
239        self.enabled.store(true, Ordering::Release);
240    }
241
242    /// Disable the KSM scanner.
243    pub fn disable(&self) {
244        self.enabled.store(false, Ordering::Release);
245    }
246
247    /// Check whether the scanner is enabled.
248    pub fn is_enabled(&self) -> bool {
249        self.enabled.load(Ordering::Acquire)
250    }
251
252    /// Get current KSM statistics.
253    pub fn get_stats(&self) -> KsmStats {
254        let shared = self.stats_shared.load(Ordering::Relaxed);
255        let sharing = self.stats_sharing.load(Ordering::Relaxed);
256        let unshared = self.stats_unshared.load(Ordering::Relaxed);
257        let scanned = self.stats_scanned.load(Ordering::Relaxed);
258
259        let merge_ratio_x100 = if shared > 0 {
260            sharing.saturating_mul(100) / shared
261        } else {
262            0
263        };
264
265        KsmStats {
266            pages_shared: shared,
267            pages_sharing: sharing,
268            pages_unshared: unshared,
269            pages_scanned: scanned,
270            merge_ratio_x100,
271        }
272    }
273
274    /// Scan a single page.  The caller provides the frame number and a
275    /// reference to the page content (PAGE_SIZE bytes).
276    ///
277    /// The scanner will:
278    ///   1. Compute FNV-1a hash of the page content.
279    ///   2. Search the stable tree for a match (merge immediately).
280    ///   3. Search the unstable tree for a match (increment stable_count).
281    ///   4. If no match, add to the unstable tree.
282    ///
283    /// Returns `true` if the page was merged (caller should remap as COW).
284    pub fn scan_page(&mut self, frame: FrameNumber, content: &[u8]) -> bool {
285        if !self.is_enabled() {
286            return false;
287        }
288
289        if content.len() != PAGE_SIZE {
290            return false;
291        }
292
293        self.stats_scanned.fetch_add(1, Ordering::Relaxed);
294
295        let hash = fnv1a_hash(content);
296
297        // 1. Check stable tree for an existing merge target
298        if let Some(stable_idx) = self.find_stable_by_hash(hash) {
299            // Hash match in stable tree -- would do byte-for-byte
300            // comparison in production (requires reading the canonical
301            // page content).  For the framework, we trust the hash.
302            self.stable[stable_idx].sharing_count += 1;
303            self.stats_sharing.fetch_add(1, Ordering::Relaxed);
304            return true;
305        }
306
307        // 2. Check unstable tree
308        if let Some(unstable_idx) = self.find_unstable_by_hash(hash) {
309            let entry = &mut self.unstable[unstable_idx];
310
311            // Same hash as before -- content unchanged
312            entry.stable_count += 1;
313
314            if entry.stable_count >= PROMOTION_THRESHOLD {
315                // Promote to stable tree
316                let promoted_frame = entry.frame;
317                entry.active = false;
318                self.unstable_count = self.unstable_count.saturating_sub(1);
319
320                self.add_stable(promoted_frame, hash);
321
322                // The scanned page is now a sharing page
323                if let Some(sidx) = self.find_stable_by_hash(hash) {
324                    self.stable[sidx].sharing_count += 1;
325                }
326                self.stats_sharing.fetch_add(1, Ordering::Relaxed);
327                return true;
328            }
329
330            return false;
331        }
332
333        // 3. Not in either tree -- add to unstable
334        self.add_unstable(frame, hash);
335        self.stats_unshared.fetch_add(1, Ordering::Relaxed);
336
337        false
338    }
339
340    /// Remove a page from the stable tree (e.g. after a COW fault
341    /// breaks the sharing).
342    pub fn unmerge_page(&mut self, frame: FrameNumber) {
343        for entry in self.stable.iter_mut() {
344            if entry.active && entry.frame.as_u64() == frame.as_u64() {
345                if entry.sharing_count > 0 {
346                    entry.sharing_count -= 1;
347                    self.stats_sharing.fetch_sub(1, Ordering::Relaxed);
348                }
349                if entry.sharing_count == 0 {
350                    entry.active = false;
351                    self.stable_count = self.stable_count.saturating_sub(1);
352                    self.stats_shared.fetch_sub(1, Ordering::Relaxed);
353                }
354                return;
355            }
356        }
357    }
358
359    /// Get the configured scan rate.
360    pub fn scan_rate(&self) -> usize {
361        self.scan_rate
362    }
363
364    /// Get the configured sleep interval in milliseconds.
365    pub fn sleep_ms(&self) -> u64 {
366        self.sleep_ms
367    }
368
369    // -----------------------------------------------------------------
370    // Internal helpers
371    // -----------------------------------------------------------------
372
373    /// Find a stable entry matching the given hash.
374    fn find_stable_by_hash(&self, hash: u32) -> Option<usize> {
375        for (i, entry) in self.stable.iter().enumerate() {
376            if entry.active && entry.hash == hash {
377                return Some(i);
378            }
379        }
380        None
381    }
382
383    /// Find an unstable entry matching the given hash.
384    fn find_unstable_by_hash(&self, hash: u32) -> Option<usize> {
385        for (i, entry) in self.unstable.iter().enumerate() {
386            if entry.active && entry.hash == hash {
387                return Some(i);
388            }
389        }
390        None
391    }
392
393    /// Add an entry to the stable tree.
394    fn add_stable(&mut self, frame: FrameNumber, hash: u32) {
395        // Find a free slot
396        for entry in self.stable.iter_mut() {
397            if !entry.active {
398                entry.frame = frame;
399                entry.hash = hash;
400                entry.sharing_count = 0;
401                entry.active = true;
402                self.stable_count += 1;
403                self.stats_shared.fetch_add(1, Ordering::Relaxed);
404                return;
405            }
406        }
407        // Stable tree full -- cannot add (would need eviction policy)
408    }
409
410    /// Add an entry to the unstable tree.
411    fn add_unstable(&mut self, frame: FrameNumber, hash: u32) {
412        // Find a free slot
413        for entry in self.unstable.iter_mut() {
414            if !entry.active {
415                entry.frame = frame;
416                entry.hash = hash;
417                entry.stable_count = 1;
418                entry.active = true;
419                self.unstable_count += 1;
420                return;
421            }
422        }
423        // Unstable tree full -- evict oldest (lowest stable_count)
424        let mut min_count = u32::MAX;
425        let mut min_idx = 0;
426        for (i, entry) in self.unstable.iter().enumerate() {
427            if entry.active && entry.stable_count < min_count {
428                min_count = entry.stable_count;
429                min_idx = i;
430            }
431        }
432        let entry = &mut self.unstable[min_idx];
433        entry.frame = frame;
434        entry.hash = hash;
435        entry.stable_count = 1;
436    }
437}
438
439// =========================================================================
440// Tests
441// =========================================================================
442
443#[cfg(test)]
444mod tests {
445    use super::*;
446
447    #[test]
448    fn test_fnv1a_empty() {
449        let hash = fnv1a_hash(&[]);
450        assert_eq!(hash, FNV_OFFSET_BASIS);
451    }
452
453    #[test]
454    fn test_fnv1a_known_value() {
455        // "foobar" has a well-known FNV-1a 32-bit hash
456        let hash = fnv1a_hash(b"foobar");
457        assert_eq!(hash, 0xBF9C_F968);
458    }
459
460    #[test]
461    fn test_fnv1a_different_inputs() {
462        let h1 = fnv1a_hash(b"hello");
463        let h2 = fnv1a_hash(b"world");
464        assert_ne!(h1, h2);
465    }
466
467    #[test]
468    fn test_fnv1a_same_input() {
469        let h1 = fnv1a_hash(b"identical");
470        let h2 = fnv1a_hash(b"identical");
471        assert_eq!(h1, h2);
472    }
473
474    #[test]
475    fn test_scanner_init() {
476        let mut scanner = KsmScanner::new();
477        scanner.init();
478        assert!(!scanner.is_enabled());
479        assert_eq!(scanner.scan_rate(), DEFAULT_SCAN_RATE);
480        assert_eq!(scanner.sleep_ms(), DEFAULT_SLEEP_MS);
481
482        let stats = scanner.get_stats();
483        assert_eq!(stats.pages_shared, 0);
484        assert_eq!(stats.pages_sharing, 0);
485        assert_eq!(stats.pages_scanned, 0);
486    }
487
488    #[test]
489    fn test_scanner_enable_disable() {
490        let scanner = KsmScanner::new();
491        assert!(!scanner.is_enabled());
492        scanner.enable();
493        assert!(scanner.is_enabled());
494        scanner.disable();
495        assert!(!scanner.is_enabled());
496    }
497
498    #[test]
499    fn test_scanner_config() {
500        let mut scanner = KsmScanner::new();
501        scanner.set_scan_rate(200);
502        assert_eq!(scanner.scan_rate(), 200);
503        scanner.set_scan_rate(0);
504        assert_eq!(scanner.scan_rate(), 1); // clamped to minimum
505
506        scanner.set_sleep_ms(500);
507        assert_eq!(scanner.sleep_ms(), 500);
508    }
509
510    #[test]
511    fn test_scan_page_disabled() {
512        let mut scanner = KsmScanner::new();
513        scanner.init();
514        // Scanner not enabled -- should return false
515        let page = [0u8; PAGE_SIZE];
516        assert!(!scanner.scan_page(FrameNumber::new(1), &page));
517    }
518
519    #[test]
520    fn test_scan_page_wrong_size() {
521        let mut scanner = KsmScanner::new();
522        scanner.init();
523        scanner.enable();
524        let small = [0u8; 512];
525        assert!(!scanner.scan_page(FrameNumber::new(1), &small));
526    }
527
528    #[test]
529    fn test_scan_unique_pages() {
530        let mut scanner = KsmScanner::new();
531        scanner.init();
532        scanner.enable();
533
534        let mut page1 = [0u8; PAGE_SIZE];
535        page1[0] = 1;
536        let mut page2 = [0u8; PAGE_SIZE];
537        page2[0] = 2;
538
539        // First scan of each unique page -- goes to unstable
540        assert!(!scanner.scan_page(FrameNumber::new(1), &page1));
541        assert!(!scanner.scan_page(FrameNumber::new(2), &page2));
542
543        let stats = scanner.get_stats();
544        assert_eq!(stats.pages_scanned, 2);
545        assert_eq!(stats.pages_unshared, 2);
546        assert_eq!(stats.pages_shared, 0);
547    }
548
549    #[test]
550    fn test_scan_identical_pages_merge() {
551        let mut scanner = KsmScanner::new();
552        scanner.init();
553        scanner.enable();
554
555        let page = [42u8; PAGE_SIZE];
556
557        // Scan same content from frame 1 -- enters unstable tree
558        assert!(!scanner.scan_page(FrameNumber::new(1), &page));
559        // Scan again (same hash) -- increments stable_count to 2
560        assert!(!scanner.scan_page(FrameNumber::new(1), &page));
561        // Scan again -- stable_count reaches PROMOTION_THRESHOLD (3)
562        // This promotes to stable tree
563        assert!(scanner.scan_page(FrameNumber::new(1), &page));
564
565        let stats = scanner.get_stats();
566        assert_eq!(stats.pages_shared, 1);
567        assert!(stats.pages_sharing >= 1);
568    }
569
570    #[test]
571    fn test_merge_then_stable_lookup() {
572        let mut scanner = KsmScanner::new();
573        scanner.init();
574        scanner.enable();
575
576        let page = [99u8; PAGE_SIZE];
577
578        // Promote frame 1 through unstable -> stable
579        scanner.scan_page(FrameNumber::new(1), &page);
580        scanner.scan_page(FrameNumber::new(1), &page);
581        scanner.scan_page(FrameNumber::new(1), &page); // promotes
582
583        // Now scan frame 2 with same content -- should match stable tree
584        let merged = scanner.scan_page(FrameNumber::new(2), &page);
585        assert!(merged);
586
587        let stats = scanner.get_stats();
588        assert!(stats.pages_sharing >= 2);
589    }
590
591    #[test]
592    fn test_unmerge_page() {
593        let mut scanner = KsmScanner::new();
594        scanner.init();
595        scanner.enable();
596
597        let page = [55u8; PAGE_SIZE];
598
599        // Promote to stable
600        scanner.scan_page(FrameNumber::new(1), &page);
601        scanner.scan_page(FrameNumber::new(1), &page);
602        scanner.scan_page(FrameNumber::new(1), &page);
603
604        // Add a sharing page
605        scanner.scan_page(FrameNumber::new(2), &page);
606
607        let stats = scanner.get_stats();
608        let sharing_before = stats.pages_sharing;
609
610        // Unmerge (COW break)
611        scanner.unmerge_page(FrameNumber::new(1));
612
613        let stats = scanner.get_stats();
614        assert!(stats.pages_sharing < sharing_before);
615    }
616}
veridian_kernel/mm/ksm.rs

veridian_kernel/mm/
ksm.rs
