lcpfs 2026.1.102

// Copyright 2025 LunaOS Contributors
// SPDX-License-Identifier: Apache-2.0

//! # Deduplication Table (DDT)
//!
//! This module implements block-level deduplication for LCPFS.
//!
//! ## Overview
//!
//! Deduplication identifies and eliminates duplicate blocks by storing
//! only one copy of each unique block. When a duplicate block is written,
//! LCPFS returns a reference to the existing block instead of allocating
//! new storage.
//!
//! ## How It Works
//!
//! 1. When a block is written, compute its SHA-256 hash
//! 2. Look up the hash in the DDT
//! 3. If found: increment reference count, return existing DVA
//! 4. If not found: allocate new block, register in DDT
//!
//! ```text
//! ┌─────────────────────────────────────────────────────────────┐
//! │                    Deduplication Flow                        │
//! ├─────────────────────────────────────────────────────────────┤
//! │                                                             │
//! │   Write Block ──► Hash (SHA-256) ──► DDT Lookup             │
//! │                                          │                  │
//! │                         ┌────────────────┴─────────────┐    │
//! │                         ▼                              ▼    │
//! │                   [Found]                        [Not Found]│
//! │                      │                               │      │
//! │                      ▼                               ▼      │
//! │              Increment RefCount            Allocate Block   │
//! │              Return Existing DVA           Register in DDT  │
//! │                                           Return New DVA    │
//! └─────────────────────────────────────────────────────────────┘
//! ```
//!
//! ## Space Savings
//!
//! Deduplication is most effective for:
//! - Backup storage (many similar files)
//! - Virtual machine images (common OS blocks)
//! - Development environments (similar codebases)
//!
//! ## Memory Usage
//!
//! The DDT requires approximately 320 bytes per unique block:
//! - 32 bytes: SHA-256 hash
//! - 12 bytes: DVA (vdev + offset)
//! - 8 bytes: reference count
//! - Overhead: BTreeMap node structure
//!
//! For a 1TB pool with 128KB blocks, the DDT uses ~26 MB of RAM.

use crate::fscore::structs::Dva;
use alloc::collections::BTreeMap;
use lazy_static::lazy_static;
use spin::Mutex;

// ═══════════════════════════════════════════════════════════════════════════════
// DDT ENTRY
// ═══════════════════════════════════════════════════════════════════════════════

/// Entry in the deduplication table.
///
/// Each unique block has one DDT entry that tracks its location and
/// how many references point to it.
pub struct DdtEntry {
    /// Device Virtual Address where the block is stored.
    pub dva: Dva,
    /// Number of references to this block.
    ///
    /// When ref_count reaches 0, the block can be freed.
    pub ref_count: u64,
}

// ═══════════════════════════════════════════════════════════════════════════════
// DEDUP TABLE
// ═══════════════════════════════════════════════════════════════════════════════

/// Deduplication table - maps content hashes to block locations.
///
/// The DDT is a critical data structure for deduplication. It must be
/// persisted to disk to survive reboots.
pub struct DedupTable {
    /// Mapping from SHA-256 hash to DDT entry.
    pub table: BTreeMap<[u8; 32], DdtEntry>,
    /// Total number of blocks saved through deduplication.
    pub saved_blocks: u64,
}

lazy_static! {
    /// Global deduplication table instance.
    ///
    /// All deduplication operations go through this shared table.
    pub static ref DDT: Mutex<DedupTable> = Mutex::new(DedupTable::new());
}

impl DedupTable {
    /// Create a new, empty deduplication table.
    pub fn new() -> Self {
        Self {
            table: BTreeMap::new(),
            saved_blocks: 0,
        }
    }

    /// Attempt to deduplicate a block.
    ///
    /// Computes the SHA-256 hash of the data and looks it up in the DDT.
    /// If found, increments the reference count and returns the existing DVA.
    ///
    /// # Arguments
    ///
    /// * `data` - Block data to deduplicate
    ///
    /// # Returns
    ///
    /// - `Some(dva)` - Block already exists, use this DVA
    /// - `None` - Block is unique, caller should allocate new storage
    ///
    /// # Example
    ///
    /// ```rust,ignore
    /// let mut ddt = DDT.lock();
    ///
    /// if let Some(existing_dva) = ddt.dedup(&block_data) {
    ///     // Block already exists, no allocation needed
    ///     return existing_dva;
    /// } else {
    ///     // Block is unique, allocate and register
    ///     let new_dva = allocate_block(&block_data)?;
    ///     ddt.register(&block_data, new_dva);
    ///     return new_dva;
    /// }
    /// ```
    pub fn dedup(&mut self, data: &[u8]) -> Option<Dva> {
        let hash = self.calculate_sha256(data);
        if let Some(entry) = self.table.get_mut(&hash) {
            entry.ref_count += 1;
            self.saved_blocks += 1;
            return Some(entry.dva);
        }
        None
    }

    /// Register a new unique block in the DDT.
    ///
    /// Called after allocating storage for a block that wasn't found
    /// in the deduplication table.
    ///
    /// # Arguments
    ///
    /// * `data` - Block data (for computing hash)
    /// * `dva` - Location where the block was stored
    pub fn register(&mut self, data: &[u8], dva: Dva) {
        let hash = self.calculate_sha256(data);
        self.table.insert(hash, DdtEntry { dva, ref_count: 1 });
    }

    /// Decrement the reference count for a block.
    ///
    /// Called when a block is freed. If the reference count reaches 0,
    /// the block's storage can be reclaimed.
    ///
    /// # Arguments
    ///
    /// * `data` - Block data (for computing hash)
    ///
    /// # Returns
    ///
    /// - `Some(dva)` - Block can be freed (ref_count reached 0)
    /// - `None` - Block still has references
    pub fn unref(&mut self, data: &[u8]) -> Option<Dva> {
        let hash = self.calculate_sha256(data);
        if let Some(entry) = self.table.get_mut(&hash) {
            entry.ref_count = entry.ref_count.saturating_sub(1);
            if entry.ref_count == 0 {
                let dva = entry.dva;
                self.table.remove(&hash);
                return Some(dva);
            }
        }
        None
    }

    /// Get deduplication statistics.
    ///
    /// # Returns
    ///
    /// Tuple of (unique_blocks, saved_blocks, dedup_ratio)
    pub fn stats(&self) -> (usize, u64, f64) {
        let unique = self.table.len();
        let ratio = if unique > 0 {
            (unique as u64 + self.saved_blocks) as f64 / unique as f64
        } else {
            1.0
        };
        (unique, self.saved_blocks, ratio)
    }

    /// Calculate SHA-256 hash of block data.
    ///
    /// Uses the sha2 crate's Sha256 implementation for cryptographic security.
    /// This is essential for deduplication correctness - weak hashes cause
    /// false positives (data corruption) or false negatives (wasted space).
    fn calculate_sha256(&self, data: &[u8]) -> [u8; 32] {
        use sha2::{Digest, Sha256};

        let mut hasher = Sha256::new();
        hasher.update(data);
        let result = hasher.finalize();

        let mut hash = [0u8; 32];
        hash.copy_from_slice(&result);
        hash
    }
}

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