lcpfs 2026.1.102

// Copyright 2025 LunaOS Contributors
// SPDX-License-Identifier: Apache-2.0
//
// Fast Dedup (RAM-only DDT)
// RAM-only deduplication table for hot data.

use alloc::collections::BTreeMap;
use alloc::vec::Vec;
use lazy_static::lazy_static;
use spin::Mutex;

/// Fast dedup entry (in-memory only)
#[derive(Debug, Clone)]
pub struct FastDedupEntry {
    /// Block checksum (SHA-256)
    pub checksum: [u8; 32],
    /// Physical block pointer
    pub block_ptr: u64,
    /// Reference count
    pub refcount: u32,
    /// Last access timestamp (for LRU)
    pub last_access: u64,
    /// Access frequency (for hot data detection)
    pub access_count: u32,
}

lazy_static! {
    /// Global fast dedup table
    static ref FAST_DEDUP: Mutex<FastDedupTable> = Mutex::new(FastDedupTable::new());
}

/// Fast dedup table (RAM-only)
pub struct FastDedupTable {
    /// In-memory dedup table (checksum -> entry)
    table: BTreeMap<[u8; 32], FastDedupEntry>,
    /// Maximum entries (memory limit)
    max_entries: usize,
    /// Current timestamp counter
    timestamp: u64,
    /// Hit counter
    hits: u64,
    /// Miss counter
    misses: u64,
    /// Eviction counter
    evictions: u64,
}

impl Default for FastDedupTable {
    fn default() -> Self {
        Self::new()
    }
}

impl FastDedupTable {
    /// Default maximum entries (64K entries = ~2 MB RAM)
    const DEFAULT_MAX_ENTRIES: usize = 65536;

    /// Create new fast dedup table
    pub fn new() -> Self {
        Self {
            table: BTreeMap::new(),
            max_entries: Self::DEFAULT_MAX_ENTRIES,
            timestamp: 0,
            hits: 0,
            misses: 0,
            evictions: 0,
        }
    }

    /// Create fast dedup table with custom size
    pub fn with_capacity(max_entries: usize) -> Self {
        Self {
            table: BTreeMap::new(),
            max_entries,
            timestamp: 0,
            hits: 0,
            misses: 0,
            evictions: 0,
        }
    }

    /// Lookup block in fast dedup table
    ///
    /// # Arguments
    /// * `checksum` - Block checksum (SHA-256)
    ///
    /// # Returns
    /// * `Some(block_ptr)` - Dedup hit, returns physical block pointer
    /// * `None` - Dedup miss
    pub fn lookup(&mut self, checksum: &[u8; 32]) -> Option<u64> {
        if let Some(entry) = self.table.get_mut(checksum) {
            // Update access tracking
            self.timestamp += 1;
            entry.last_access = self.timestamp;
            entry.access_count += 1;
            self.hits += 1;
            Some(entry.block_ptr)
        } else {
            self.misses += 1;
            None
        }
    }

    /// Insert block into fast dedup table
    ///
    /// # Arguments
    /// * `checksum` - Block checksum
    /// * `block_ptr` - Physical block pointer
    ///
    /// # Returns
    /// * `true` - Entry inserted
    /// * `false` - Table full, eviction needed
    pub fn insert(&mut self, checksum: [u8; 32], block_ptr: u64) -> bool {
        // Check if already exists (update instead)
        if let Some(entry) = self.table.get_mut(&checksum) {
            self.timestamp += 1;
            entry.last_access = self.timestamp;
            entry.refcount += 1;
            return true;
        }

        // Check if table is full
        if self.table.len() >= self.max_entries {
            self.evict_lru();
        }

        // Insert new entry
        self.timestamp += 1;
        let entry = FastDedupEntry {
            checksum,
            block_ptr,
            refcount: 1,
            last_access: self.timestamp,
            access_count: 1,
        };

        self.table.insert(checksum, entry);
        true
    }

    /// Increment reference count for a block
    ///
    /// # Arguments
    /// * `checksum` - Block checksum
    pub fn incref(&mut self, checksum: &[u8; 32]) {
        if let Some(entry) = self.table.get_mut(checksum) {
            entry.refcount += 1;
        }
    }

    /// Decrement reference count for a block
    ///
    /// # Arguments
    /// * `checksum` - Block checksum
    ///
    /// # Returns
    /// * `true` - Entry still exists (refcount > 0)
    /// * `false` - Entry removed (refcount reached 0)
    pub fn decref(&mut self, checksum: &[u8; 32]) -> bool {
        if let Some(entry) = self.table.get_mut(checksum) {
            entry.refcount -= 1;
            if entry.refcount == 0 {
                self.table.remove(checksum);
                return false;
            }
            return true;
        }
        false
    }

    /// Evict least recently used entry
    fn evict_lru(&mut self) {
        // Find entry with oldest timestamp
        let oldest = self
            .table
            .iter()
            .min_by_key(|(_, entry)| entry.last_access)
            .map(|(checksum, _)| *checksum);

        if let Some(checksum) = oldest {
            self.table.remove(&checksum);
            self.evictions += 1;
        }
    }

    /// Promote hot entries (called periodically)
    ///
    /// Identifies frequently accessed blocks and ensures they stay in cache
    ///
    /// # Arguments
    /// * `hot_threshold` - Access count threshold for "hot" data
    pub fn promote_hot_entries(&mut self, hot_threshold: u32) {
        for entry in self.table.values_mut() {
            if entry.access_count >= hot_threshold {
                // Refresh timestamp to prevent eviction
                self.timestamp += 1;
                entry.last_access = self.timestamp;
            }
        }
    }

    /// Get dedup statistics
    ///
    /// # Returns
    /// (hits, misses, entries, evictions, hit_rate)
    pub fn get_stats(&self) -> (u64, u64, usize, u64, f64) {
        let total = self.hits + self.misses;
        let hit_rate = if total > 0 {
            (self.hits as f64 / total as f64) * 100.0
        } else {
            0.0
        };

        (
            self.hits,
            self.misses,
            self.table.len(),
            self.evictions,
            hit_rate,
        )
    }

    /// Clear all entries
    pub fn clear(&mut self) {
        self.table.clear();
        self.timestamp = 0;
        self.hits = 0;
        self.misses = 0;
        self.evictions = 0;
    }

    /// Get dedup ratio
    ///
    /// # Returns
    /// Estimated dedup ratio (e.g., 2.0 = 50% space savings)
    pub fn dedup_ratio(&self) -> f64 {
        if self.table.is_empty() {
            return 1.0;
        }

        let total_refs: u32 = self.table.values().map(|e| e.refcount).sum();
        let unique_blocks = self.table.len();

        total_refs as f64 / unique_blocks as f64
    }
}

/// Global fast dedup operations
pub struct FastDedupEngine;

impl FastDedupEngine {
    /// Initialize fast dedup with custom size
    pub fn init(max_entries: usize) {
        let mut dedup = FAST_DEDUP.lock();
        *dedup = FastDedupTable::with_capacity(max_entries);
    }

    /// Lookup block in fast dedup
    pub fn lookup(checksum: &[u8; 32]) -> Option<u64> {
        let mut dedup = FAST_DEDUP.lock();
        dedup.lookup(checksum)
    }

    /// Insert block into fast dedup
    pub fn insert(checksum: [u8; 32], block_ptr: u64) -> bool {
        let mut dedup = FAST_DEDUP.lock();
        dedup.insert(checksum, block_ptr)
    }

    /// Increment reference count
    pub fn incref(checksum: &[u8; 32]) {
        let mut dedup = FAST_DEDUP.lock();
        dedup.incref(checksum);
    }

    /// Decrement reference count
    pub fn decref(checksum: &[u8; 32]) -> bool {
        let mut dedup = FAST_DEDUP.lock();
        dedup.decref(checksum)
    }

    /// Get statistics
    pub fn get_stats() -> (u64, u64, usize, u64, f64) {
        let dedup = FAST_DEDUP.lock();
        dedup.get_stats()
    }

    /// Promote hot entries
    pub fn promote_hot(hot_threshold: u32) {
        let mut dedup = FAST_DEDUP.lock();
        dedup.promote_hot_entries(hot_threshold);
    }

    /// Clear all entries
    pub fn clear() {
        let mut dedup = FAST_DEDUP.lock();
        dedup.clear();
    }

    /// Get dedup ratio
    pub fn dedup_ratio() -> f64 {
        let dedup = FAST_DEDUP.lock();
        dedup.dedup_ratio()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_fast_dedup_insert_lookup() {
        let mut dedup = FastDedupTable::new();

        let checksum = [0x42u8; 32];
        let block_ptr = 12345;

        // Insert
        assert!(dedup.insert(checksum, block_ptr));

        // Lookup should hit
        assert_eq!(dedup.lookup(&checksum), Some(block_ptr));
        assert_eq!(dedup.hits, 1);
        assert_eq!(dedup.misses, 0);
    }

    #[test]
    fn test_fast_dedup_miss() {
        let mut dedup = FastDedupTable::new();
        let checksum = [0x42u8; 32];

        // Lookup non-existent entry
        assert_eq!(dedup.lookup(&checksum), None);
        assert_eq!(dedup.hits, 0);
        assert_eq!(dedup.misses, 1);
    }

    #[test]
    fn test_fast_dedup_refcount() {
        let mut dedup = FastDedupTable::new();
        let checksum = [0x42u8; 32];

        dedup.insert(checksum, 100);

        // Increment refcount
        dedup.incref(&checksum);
        assert_eq!(
            dedup
                .table
                .get(&checksum)
                .expect("test: operation should succeed")
                .refcount,
            2
        );

        // Decrement refcount
        assert!(dedup.decref(&checksum)); // Still exists
        assert_eq!(
            dedup
                .table
                .get(&checksum)
                .expect("test: operation should succeed")
                .refcount,
            1
        );

        assert!(!dedup.decref(&checksum)); // Removed
        assert!(!dedup.table.contains_key(&checksum));
    }

    #[test]
    fn test_fast_dedup_eviction() {
        let mut dedup = FastDedupTable::with_capacity(2);

        let cs1 = [0x01u8; 32];
        let cs2 = [0x02u8; 32];
        let cs3 = [0x03u8; 32];

        // Fill table
        dedup.insert(cs1, 100);
        dedup.insert(cs2, 200);

        // Access cs2 to make it more recent
        dedup.lookup(&cs2);

        // Insert cs3 should evict cs1 (LRU)
        dedup.insert(cs3, 300);

        assert!(!dedup.table.contains_key(&cs1)); // Evicted
        assert!(dedup.table.contains_key(&cs2)); // Kept (more recent)
        assert!(dedup.table.contains_key(&cs3)); // New
        assert_eq!(dedup.evictions, 1);
    }

    #[test]
    fn test_fast_dedup_stats() {
        let mut dedup = FastDedupTable::new();
        let cs1 = [0x01u8; 32];

        dedup.insert(cs1, 100);
        dedup.lookup(&cs1); // Hit
        dedup.lookup(&[0x02u8; 32]); // Miss

        let (hits, misses, entries, evictions, hit_rate) = dedup.get_stats();
        assert_eq!(hits, 1);
        assert_eq!(misses, 1);
        assert_eq!(entries, 1);
        assert_eq!(evictions, 0);
        assert_eq!(hit_rate, 50.0); // 1 hit out of 2 total
    }

    #[test]
    fn test_dedup_ratio() {
        let mut dedup = FastDedupTable::new();

        let cs1 = [0x01u8; 32];
        dedup.insert(cs1, 100);
        dedup.incref(&cs1); // refcount = 2

        let cs2 = [0x02u8; 32];
        dedup.insert(cs2, 200); // refcount = 1

        // Total refs = 3, unique blocks = 2
        // Ratio = 3/2 = 1.5
        assert_eq!(dedup.dedup_ratio(), 1.5);
    }

    #[test]
    fn test_promote_hot_entries() {
        let mut dedup = FastDedupTable::new();

        let cs1 = [0x01u8; 32];
        dedup.insert(cs1, 100);

        // Simulate multiple accesses
        for _ in 0..10 {
            dedup.lookup(&cs1);
        }

        let old_timestamp = dedup
            .table
            .get(&cs1)
            .expect("test: operation should succeed")
            .last_access;

        // Promote hot entries (access_count >= 5)
        dedup.promote_hot_entries(5);

        let new_timestamp = dedup
            .table
            .get(&cs1)
            .expect("test: operation should succeed")
            .last_access;
        assert!(new_timestamp > old_timestamp); // Timestamp refreshed
    }
}