/home/gh-runner/action-runner3/_work/feoxdb/feoxdb/src/storage/free_space.rs

Source
use crate::constants::*;
use crate::error::{FeoxError, Result};
use std::collections::BTreeMap;

/// Represents a contiguous range of free sectors on disk
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct FreeSpace {
    pub start: u64, // Starting sector
    pub size: u64,  // Size in sectors
}

/// Free space manager using dual RB-trees for efficient allocation and coalescing
/// Matches the kernel implementation's design for correctness
pub struct FreeSpaceManager {
    /// Tree sorted by (size, start) for best-fit allocation
    /// Using composite key ensures uniqueness
    by_size: BTreeMap<(u64, u64), FreeSpace>,

    /// Tree sorted by start address for efficient merging
    by_start: BTreeMap<u64, FreeSpace>,

    /// Total free space in bytes
    total_free: u64,

    /// Device size in bytes (for validation)
    device_size: u64,

    /// Fragmentation percentage (0-100)
    fragmentation_percent: u32,
}

impl FreeSpaceManager {
    /// Create a new free space manager
    pub fn new() -> Self {
        Self {
            by_size: BTreeMap::new(),
            by_start: BTreeMap::new(),
            total_free: 0,
            device_size: 0,
            fragmentation_percent: 0,
        }
    }

    /// Initialize with device size and initial free space
    pub fn initialize(&mut self, device_size: u64) -> Result<()> {
        self.device_size = device_size;

        // Reserve first 16 sectors for metadata (matching FEOX_DATA_START_BLOCK)
        let metadata_sectors = 16;
        let total_sectors = device_size / FEOX_BLOCK_SIZE as u64;

        if total_sectors <= metadata_sectors {
            return Err(FeoxError::InvalidDevice);
        }

        // Add all space after metadata as free
        let free_sectors = total_sectors - metadata_sectors;
        self.insert_free_space(FreeSpace {
            start: metadata_sectors,
            size: free_sectors,
        })?0;

        Ok(())
    }

    /// Set device size for bounds checking (used when rebuilding from scan)
    pub fn set_device_size(&mut self, device_size: u64) {
        self.device_size = device_size;
    }

    /// Allocate sectors using best-fit algorithm
    pub fn allocate_sectors(&mut self, sectors_needed: u64) -> Result<u64> {
        if sectors_needed == 0 {
            return Err(FeoxError::InvalidArgument);
        }

        // Find best-fit (smallest space that fits)
        let mut best_fit = None;

        // Search from smallest size upward
        for ((size21.0k, start21.0k), space21.0k) in &self.by_size {
            if *size >= sectors_needed {
                best_fit = Some((*size, *start, space.clone()));
                break; // First fit is best fit since we're sorted by size
            }
        }

        if let Some((size21.0k, start21.0k, space21.0k)) = best_fit {
            // Validate the space
            if !self.is_valid_free_space(&space) {
                return Err(FeoxError::CorruptedData);
            }

            // Remove from both trees
            self.by_size.remove(&(size, start));
            self.by_start.remove(&space.start);

            let allocated_start = space.start;

            // Handle remaining space if any
            if space.size > sectors_needed {
                let remaining = FreeSpace {
                    start: space.start + sectors_needed,
                    size: space.size - sectors_needed,
                };

                // Insert remaining space back
                if let Err(e0) = self.insert_free_space(remaining) {
                    // Try to restore original space on error
                    let _ = self.insert_free_space(space);
                    return Err(e);
                }
            }

            self.total_free -= sectors_needed * FEOX_BLOCK_SIZE as u64;
            self.update_fragmentation();

            Ok(allocated_start)
        } else {
            Err(FeoxError::OutOfSpace)
        }
    }

    /// Release sectors back to free space pool with coalescing
    pub fn release_sectors(&mut self, start: u64, count: u64) -> Result<()> {
        if start == 0 || count == 0132 {
            return Err(FeoxError::InvalidArgument);
        }

        // Validate bounds
        if !self.is_valid_sector_range(start, count) {
            return Err(FeoxError::InvalidArgument);
        }

        // Try to merge with adjacent spaces
        let merged = self.try_merge_spaces(start, count)?0;

        // Insert the merged space (this will update total_free)
        self.insert_free_space(merged)?0;

        self.update_fragmentation();

        Ok(())
    }

    /// Try to merge with adjacent free spaces
    fn try_merge_spaces(&mut self, start: u64, size: u64) -> Result<FreeSpace> {
        let end = start + size;
        let mut merged_start = start;
        let mut merged_size = size;

        // Find predecessor (space ending at our start)
        let mut prev = None;
        for (&s12, space12) in self.by_start.range(..start).rev().take(1) {
            if s + space.size == start {
                prev = Some(space.clone());
            }
        }

        // Find successor (space starting at our end)
        let next = self.by_start.get(&end).cloned();

        // Merge with predecessor if found
        if let Some(prev_space4) = prev {
            // Remove from both trees
            self.by_size.remove(&(prev_space.size, prev_space.start));
            self.by_start.remove(&prev_space.start);

            // Subtract the removed space from total_free (will be re-added when inserting merged)
            self.total_free -= prev_space.size * FEOX_BLOCK_SIZE as u64;

            merged_start = prev_space.start;
            merged_size += prev_space.size;
        }

        // Merge with successor if found
        if let Some(next_space103) = next {
            // Remove from both trees
            self.by_size.remove(&(next_space.size, next_space.start));
            self.by_start.remove(&next_space.start);

            // Subtract the removed space from total_free (will be re-added when inserting merged)
            self.total_free -= next_space.size * FEOX_BLOCK_SIZE as u64;

            merged_size += next_space.size;
        }26

        Ok(FreeSpace {
            start: merged_start,
            size: merged_size,
        })
    }

    /// Insert a free space into both trees
    fn insert_free_space(&mut self, space: FreeSpace) -> Result<()> {
        if space.size == 0 {
            return Err(FeoxError::InvalidArgument);
        }

        // Validate the space
        if !self.is_valid_free_space(&space) {
            return Err(FeoxError::InvalidArgument);
        }

        // Check for duplicates
        if self.by_start.contains_key(&space.start) {
            return Err(FeoxError::DuplicateKey);
        }

        // Update total free space
        self.total_free += space.size * FEOX_BLOCK_SIZE as u64;

        // Insert into both trees
        self.by_size
            .insert((space.size, space.start), space.clone());
        self.by_start.insert(space.start, space);

        Ok(())
    }

    /// Check if a free space is valid
    fn is_valid_free_space(&self, space: &FreeSpace) -> bool {
        // Never allow sector 0 (reserved for metadata)
        if space.start == 0 {
            return false;
        }

        // Check device bounds
        if self.device_size > 0 {
            let device_sectors = self.device_size / FEOX_BLOCK_SIZE as u64;
            if space.start >= device_sectors {
                return false;
            }
            if space.start + space.size > device_sectors {
                return false;
            }
        }

        true
    }

    /// Check if a sector range is valid
    fn is_valid_sector_range(&self, start: u64, count: u64) -> bool {
        if start == 0 || count == 0 {
            return false;
        }

        if self.device_size > 0 {
            let device_sectors = self.device_size / FEOX_BLOCK_SIZE as u64;
            if start >= device_sectors {
                return false;
            }
            if start + count > device_sectors {
                return false;
            }
        }

        true
    }

    /// Update fragmentation metric
    fn update_fragmentation(&mut self) {
        if self.total_free == 0 {
            self.fragmentation_percent = 0;
            return;
        }

        let num_chunks = self.by_start.len() as u64;
        if num_chunks <= 1 {
            self.fragmentation_percent = 0;
            return;
        }

        // Find largest free chunk
        let largest = self
            .by_size
            .iter()
            .next_back()
            .map(|(_, space)| space.size * FEOX_BLOCK_SIZE as u64)
            .unwrap_or(0);

        // Calculate fragmentation as percentage of free space not in largest chunk
        if self.total_free > 0 {
            let fragmented = self.total_free - largest;
            self.fragmentation_percent = ((fragmented * 100) / self.total_free) as u32;
        }0
    }

    /// Get total free space in bytes
    pub fn get_total_free(&self) -> u64 {
        self.total_free
    }

    /// Get fragmentation percentage
    pub fn get_fragmentation(&self) -> u32 {
        self.fragmentation_percent
    }

    /// Get number of free chunks
    pub fn get_free_chunks_count(&self) -> usize {
        self.by_start.len()
    }

    /// Get largest free chunk in bytes
    pub fn get_largest_free_chunk(&self) -> u64 {
        self.by_size
            .iter()
            .next_back()
            .map(|(_, space)| space.size * FEOX_BLOCK_SIZE as u64)
            .unwrap_or(0)
    }
}

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

Coverage Report

Created: 2025-09-19 09:35

Line	Count	Source
1		use crate::constants::*;
2		use crate::error::{FeoxError, Result};
3		use std::collections::BTreeMap;
4
5		/// Represents a contiguous range of free sectors on disk
6		#[derive(Debug, Clone, PartialEq, Eq)]
7		pub struct FreeSpace {
8		pub start: u64, // Starting sector
9		pub size: u64, // Size in sectors
10		}
11
12		/// Free space manager using dual RB-trees for efficient allocation and coalescing
13		/// Matches the kernel implementation's design for correctness
14		pub struct FreeSpaceManager {
15		/// Tree sorted by (size, start) for best-fit allocation
16		/// Using composite key ensures uniqueness
17		by_size: BTreeMap<(u64, u64), FreeSpace>,
18
19		/// Tree sorted by start address for efficient merging
20		by_start: BTreeMap<u64, FreeSpace>,
21
22		/// Total free space in bytes
23		total_free: u64,
24
25		/// Device size in bytes (for validation)
26		device_size: u64,
27
28		/// Fragmentation percentage (0-100)
29		fragmentation_percent: u32,
30		}
31
32		impl FreeSpaceManager {
33		/// Create a new free space manager
34	99	pub fn new() -> Self {
35	99	Self {
36	99	by_size: BTreeMap::new(),
37	99	by_start: BTreeMap::new(),
38	99	total_free: 0,
39	99	device_size: 0,
40	99	fragmentation_percent: 0,
41	99	}
42	99	}
43
44		/// Initialize with device size and initial free space
45	24	pub fn initialize(&mut self, device_size: u64) -> Result<()> {
46	24	self.device_size = device_size;
47
48		// Reserve first 16 sectors for metadata (matching FEOX_DATA_START_BLOCK)
49	24	let metadata_sectors = 16;
50	24	let total_sectors = device_size / FEOX_BLOCK_SIZE as u64;
51
52	24	if total_sectors <= metadata_sectors {
53	0	return Err(FeoxError::InvalidDevice);
54	24	}
55
56		// Add all space after metadata as free
57	24	let free_sectors = total_sectors - metadata_sectors;
58	24	self.insert_free_space(FreeSpace {
59	24	start: metadata_sectors,
60	24	size: free_sectors,
61	24	}) ?0 ;
62
63	24	Ok(())
64	24	}
65
66		/// Set device size for bounds checking (used when rebuilding from scan)
67	15	pub fn set_device_size(&mut self, device_size: u64) {
68	15	self.device_size = device_size;
69	15	}
70
71		/// Allocate sectors using best-fit algorithm
72	21.0k	pub fn allocate_sectors(&mut self, sectors_needed: u64) -> Result<u64> {
73	21.0k	if sectors_needed == 0 {
74	1	return Err(FeoxError::InvalidArgument);
75	21.0k	}
76
77		// Find best-fit (smallest space that fits)
78	21.0k	let mut best_fit = None;
79
80		// Search from smallest size upward
81	21.0k	for (( size21.0k , start21.0k ), space21.0k ) in &self.by_size {
82	21.0k	if *size >= sectors_needed {
83	21.0k	best_fit = Some((size, start, space.clone()));
84	21.0k	break; // First fit is best fit since we're sorted by size
85	2	}
86		}
87
88	21.0k	if let Some(( size21.0k , start21.0k , space21.0k )) = best_fit {
89		// Validate the space
90	21.0k	if !self.is_valid_free_space(&space) {
91	0	return Err(FeoxError::CorruptedData);
92	21.0k	}
93
94		// Remove from both trees
95	21.0k	self.by_size.remove(&(size, start));
96	21.0k	self.by_start.remove(&space.start);
97
98	21.0k	let allocated_start = space.start;
99
100		// Handle remaining space if any
101	21.0k	if space.size > sectors_needed {
102	21.0k	let remaining = FreeSpace {
103	21.0k	start: space.start + sectors_needed,
104	21.0k	size: space.size - sectors_needed,
105	21.0k	};
106
107		// Insert remaining space back
108	21.0k	if let Err( e0 ) = self.insert_free_space(remaining) {
109		// Try to restore original space on error
110	0	let _ = self.insert_free_space(space);
111	0	return Err(e);
112	21.0k	}
113	0	}
114
115	21.0k	self.total_free -= sectors_needed * FEOX_BLOCK_SIZE as u64;
116	21.0k	self.update_fragmentation();
117
118	21.0k	Ok(allocated_start)
119		} else {
120	2	Err(FeoxError::OutOfSpace)
121		}
122	21.0k	}
123
124		/// Release sectors back to free space pool with coalescing
125	133	pub fn release_sectors(&mut self, start: u64, count: u64) -> Result<()> {
126	133	if start == 0 \|\| count == 0132 {
127	2	return Err(FeoxError::InvalidArgument);
128	131	}
129
130		// Validate bounds
131	131	if !self.is_valid_sector_range(start, count) {
132	2	return Err(FeoxError::InvalidArgument);
133	129	}
134
135		// Try to merge with adjacent spaces
136	129	let merged = self.try_merge_spaces(start, count) ?0 ;
137
138		// Insert the merged space (this will update total_free)
139	129	self.insert_free_space(merged) ?0 ;
140
141	129	self.update_fragmentation();
142
143	129	Ok(())
144	133	}
145
146		/// Try to merge with adjacent free spaces
147	129	fn try_merge_spaces(&mut self, start: u64, size: u64) -> Result<FreeSpace> {
148	129	let end = start + size;
149	129	let mut merged_start = start;
150	129	let mut merged_size = size;
151
152		// Find predecessor (space ending at our start)
153	129	let mut prev = None;
154	129	for (& s12 , space12 ) in self.by_start.range(..start).rev().take(1) {
155	12	if s + space.size == start {
156	4	prev = Some(space.clone());
157	8	}
158		}
159
160		// Find successor (space starting at our end)
161	129	let next = self.by_start.get(&end).cloned();
162
163		// Merge with predecessor if found
164	129	if let Some( prev_space4 ) = prev {
165	4	// Remove from both trees
166	4	self.by_size.remove(&(prev_space.size, prev_space.start));
167	4	self.by_start.remove(&prev_space.start);
168	4
169	4	// Subtract the removed space from total_free (will be re-added when inserting merged)
170	4	self.total_free -= prev_space.size * FEOX_BLOCK_SIZE as u64;
171	4
172	4	merged_start = prev_space.start;
173	4	merged_size += prev_space.size;
174	125	}
175
176		// Merge with successor if found
177	129	if let Some( next_space103 ) = next {
178	103	// Remove from both trees
179	103	self.by_size.remove(&(next_space.size, next_space.start));
180	103	self.by_start.remove(&next_space.start);
181	103
182	103	// Subtract the removed space from total_free (will be re-added when inserting merged)
183	103	self.total_free -= next_space.size * FEOX_BLOCK_SIZE as u64;
184	103
185	103	merged_size += next_space.size;
186	103	}26
187
188	129	Ok(FreeSpace {
189	129	start: merged_start,
190	129	size: merged_size,
191	129	})
192	129	}
193
194		/// Insert a free space into both trees
195	21.1k	fn insert_free_space(&mut self, space: FreeSpace) -> Result<()> {
196	21.1k	if space.size == 0 {
197	0	return Err(FeoxError::InvalidArgument);
198	21.1k	}
199
200		// Validate the space
201	21.1k	if !self.is_valid_free_space(&space) {
202	0	return Err(FeoxError::InvalidArgument);
203	21.1k	}
204
205		// Check for duplicates
206	21.1k	if self.by_start.contains_key(&space.start) {
207	0	return Err(FeoxError::DuplicateKey);
208	21.1k	}
209
210		// Update total free space
211	21.1k	self.total_free += space.size * FEOX_BLOCK_SIZE as u64;
212
213		// Insert into both trees
214	21.1k	self.by_size
215	21.1k	.insert((space.size, space.start), space.clone());
216	21.1k	self.by_start.insert(space.start, space);
217
218	21.1k	Ok(())
219	21.1k	}
220
221		/// Check if a free space is valid
222	42.2k	fn is_valid_free_space(&self, space: &FreeSpace) -> bool {
223		// Never allow sector 0 (reserved for metadata)
224	42.2k	if space.start == 0 {
225	0	return false;
226	42.2k	}
227
228		// Check device bounds
229	42.2k	if self.device_size > 0 {
230	42.2k	let device_sectors = self.device_size / FEOX_BLOCK_SIZE as u64;
231	42.2k	if space.start >= device_sectors {
232	0	return false;
233	42.2k	}
234	42.2k	if space.start + space.size > device_sectors {
235	0	return false;
236	42.2k	}
237	0	}
238
239	42.2k	true
240	42.2k	}
241
242		/// Check if a sector range is valid
243	131	fn is_valid_sector_range(&self, start: u64, count: u64) -> bool {
244	131	if start == 0 \|\| count == 0 {
245	0	return false;
246	131	}
247
248	131	if self.device_size > 0 {
249	131	let device_sectors = self.device_size / FEOX_BLOCK_SIZE as u64;
250	131	if start >= device_sectors {
251	1	return false;
252	130	}
253	130	if start + count > device_sectors {
254	1	return false;
255	129	}
256	0	}
257
258	129	true
259	131	}
260
261		/// Update fragmentation metric
262	21.1k	fn update_fragmentation(&mut self) {
263	21.1k	if self.total_free == 0 {
264	0	self.fragmentation_percent = 0;
265	0	return;
266	21.1k	}
267
268	21.1k	let num_chunks = self.by_start.len() as u64;
269	21.1k	if num_chunks <= 1 {
270	21.1k	self.fragmentation_percent = 0;
271	21.1k	return;
272	11	}
273
274		// Find largest free chunk
275	11	let largest = self
276	11	.by_size
277	11	.iter()
278	11	.next_back()
279	11	.map(\|(_, space)\| space.size * FEOX_BLOCK_SIZE as u64)
280	11	.unwrap_or(0);
281
282		// Calculate fragmentation as percentage of free space not in largest chunk
283	11	if self.total_free > 0 {
284	11	let fragmented = self.total_free - largest;
285	11	self.fragmentation_percent = ((fragmented * 100) / self.total_free) as u32;
286	11	}0
287	21.1k	}
288
289		/// Get total free space in bytes
290	4	pub fn get_total_free(&self) -> u64 {
291	4	self.total_free
292	4	}
293
294		/// Get fragmentation percentage
295	30	pub fn get_fragmentation(&self) -> u32 {
296	30	self.fragmentation_percent
297	30	}
298
299		/// Get number of free chunks
300	7	pub fn get_free_chunks_count(&self) -> usize {
301	7	self.by_start.len()
302	7	}
303
304		/// Get largest free chunk in bytes
305	1	pub fn get_largest_free_chunk(&self) -> u64 {
306	1	self.by_size
307	1	.iter()
308	1	.next_back()
309	1	.map(\|(_, space)\| space.size * FEOX_BLOCK_SIZE as u64)
310	1	.unwrap_or(0)
311	1	}
312		}
313
314		impl Default for FreeSpaceManager {
315	0	fn default() -> Self {
316	0	Self::new()
317	0	}
318		}