/home/runner/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;

        let metadata_sectors = FEOX_DATA_START_BLOCK;
        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);
        }

        let best_fit = self
            .by_size
            .range((sectors_needed, 0)..)
            .next()
            .map(|((size, start), space)| (*size21.6k, *start21.6k, space21.6k.clone21.6k()));

        if let Some((size21.6k, start21.6k, space21.6k)) = 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);
            self.total_free -= space.size * FEOX_BLOCK_SIZE as u64;

            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.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 < FEOX_DATA_START_BLOCK || count == 0579 {
            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 merged573 = self.try_merge_spaces(start, count)?3;

        // 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.checked_add(size).ok_or(FeoxError::InvalidArgument)?0;

        // Overlap is rejected from these two probes, before either neighbour is
        // removed or debited, so a rejected release leaves the free list untouched.
        // Checking after the merge would already have destroyed the neighbours.
        let preceding = self
            .by_start
            .range(..start)
            .next_back()
            .map(|(_, space)| space334.clone334());
        if let Some(ref space334) = preceding {
            if space.start + space.size > start {
                return Err(FeoxError::DuplicateKey);
            }
        }

        let following = self
            .by_start
            .range(start..=end)
            .next()
            .map(|(_, space)| space125.clone125());
        if let Some(ref space125) = following {
            if space.start < end {
                return Err(FeoxError::DuplicateKey);
            }
        }

        let mut merged_start = start;
        let mut merged_size = size;

        let prev = preceding.filter(|space| space.start + space.size334 == start334);
        let next = following.filter(|space| space.start122 == end122);

        // Merge with predecessor if found
        if let Some(prev_space308) = 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;
        }265

        // Merge with successor if found
        if let Some(next_space122) = 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;
        }

        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 {
        if space.start < FEOX_DATA_START_BLOCK {
            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.checked_add(space.size).is_none() {
                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 < FEOX_DATA_START_BLOCK || 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;
            }
            match start.checked_add(count) {
                Some(end576) if end <= device_sectors576 => {}576
                _ => 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: 2026-07-31 00:13

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	285	pub fn new() -> Self {
35	285	Self {
36	285	by_size: BTreeMap::new(),
37	285	by_start: BTreeMap::new(),
38	285	total_free: 0,
39	285	device_size: 0,
40	285	fragmentation_percent: 0,
41	285	}
42	285	}
43
44		/// Initialize with device size and initial free space
45	73	pub fn initialize(&mut self, device_size: u64) -> Result<()> {
46	73	self.device_size = device_size;
47
48	73	let metadata_sectors = FEOX_DATA_START_BLOCK;
49	73	let total_sectors = device_size / FEOX_BLOCK_SIZE as u64;
50
51	73	if total_sectors <= metadata_sectors {
52	0	return Err(FeoxError::InvalidDevice);
53	73	}
54
55		// Add all space after metadata as free
56	73	let free_sectors = total_sectors - metadata_sectors;
57	73	self.insert_free_space(FreeSpace {
58	73	start: metadata_sectors,
59	73	size: free_sectors,
60	73	}) ?0 ;
61
62	73	Ok(())
63	73	}
64
65		/// Set device size for bounds checking (used when rebuilding from scan)
66	108	pub fn set_device_size(&mut self, device_size: u64) {
67	108	self.device_size = device_size;
68	108	}
69
70		/// Allocate sectors using best-fit algorithm
71	21.6k	pub fn allocate_sectors(&mut self, sectors_needed: u64) -> Result<u64> {
72	21.6k	if sectors_needed == 0 {
73	1	return Err(FeoxError::InvalidArgument);
74	21.6k	}
75
76	21.6k	let best_fit = self
77	21.6k	.by_size
78	21.6k	.range((sectors_needed, 0)..)
79	21.6k	.next()
80	21.6k	.map(\|((size, start), space)\| ( size21.6k , start21.6k , space21.6k . clone21.6k ()));
81
82	21.6k	if let Some(( size21.6k , start21.6k , space21.6k )) = best_fit {
83		// Validate the space
84	21.6k	if !self.is_valid_free_space(&space) {
85	0	return Err(FeoxError::CorruptedData);
86	21.6k	}
87
88		// Remove from both trees
89	21.6k	self.by_size.remove(&(size, start));
90	21.6k	self.by_start.remove(&space.start);
91	21.6k	self.total_free -= space.size * FEOX_BLOCK_SIZE as u64;
92
93	21.6k	let allocated_start = space.start;
94
95		// Handle remaining space if any
96	21.6k	if space.size > sectors_needed {
97	21.6k	let remaining = FreeSpace {
98	21.6k	start: space.start + sectors_needed,
99	21.6k	size: space.size - sectors_needed,
100	21.6k	};
101
102		// Insert remaining space back
103	21.6k	if let Err( e0 ) = self.insert_free_space(remaining) {
104		// Try to restore original space on error
105	0	let _ = self.insert_free_space(space);
106	0	return Err(e);
107	21.6k	}
108	23	}
109
110	21.6k	self.update_fragmentation();
111
112	21.6k	Ok(allocated_start)
113		} else {
114	9	Err(FeoxError::OutOfSpace)
115		}
116	21.6k	}
117
118		/// Release sectors back to free space pool with coalescing
119	596	pub fn release_sectors(&mut self, start: u64, count: u64) -> Result<()> {
120	596	if start < FEOX_DATA_START_BLOCK \|\| count == 0579 {
121	18	return Err(FeoxError::InvalidArgument);
122	578	}
123
124		// Validate bounds
125	578	if !self.is_valid_sector_range(start, count) {
126	2	return Err(FeoxError::InvalidArgument);
127	576	}
128
129		// Try to merge with adjacent spaces
130	576	let merged573 = self.try_merge_spaces(start, count) ?3 ;
131
132		// Insert the merged space (this will update total_free)
133	573	self.insert_free_space(merged) ?0 ;
134
135	573	self.update_fragmentation();
136
137	573	Ok(())
138	596	}
139
140		/// Try to merge with adjacent free spaces
141	576	fn try_merge_spaces(&mut self, start: u64, size: u64) -> Result<FreeSpace> {
142	576	let end = start.checked_add(size).ok_or(FeoxError::InvalidArgument) ?0 ;
143
144		// Overlap is rejected from these two probes, before either neighbour is
145		// removed or debited, so a rejected release leaves the free list untouched.
146		// Checking after the merge would already have destroyed the neighbours.
147	576	let preceding = self
148	576	.by_start
149	576	.range(..start)
150	576	.next_back()
151	576	.map(\|(_, space)\| space334 . clone334 ());
152	576	if let Some( ref space334 ) = preceding {
153	334	if space.start + space.size > start {
154	0	return Err(FeoxError::DuplicateKey);
155	334	}
156	242	}
157
158	576	let following = self
159	576	.by_start
160	576	.range(start..=end)
161	576	.next()
162	576	.map(\|(_, space)\| space125 . clone125 ());
163	576	if let Some( ref space125 ) = following {
164	125	if space.start < end {
165	3	return Err(FeoxError::DuplicateKey);
166	122	}
167	451	}
168
169	573	let mut merged_start = start;
170	573	let mut merged_size = size;
171
172	573	let prev = preceding.filter(\|space\| space.start + space.size334 == start334 );
173	573	let next = following.filter(\|space\| space.start122 == end122 );
174
175		// Merge with predecessor if found
176	573	if let Some( prev_space308 ) = prev {
177	308	// Remove from both trees
178	308	self.by_size.remove(&(prev_space.size, prev_space.start));
179	308	self.by_start.remove(&prev_space.start);
180	308
181	308	// Subtract the removed space from total_free (will be re-added when inserting merged)
182	308	self.total_free -= prev_space.size * FEOX_BLOCK_SIZE as u64;
183	308
184	308	merged_start = prev_space.start;
185	308	merged_size += prev_space.size;
186	308	}265
187
188		// Merge with successor if found
189	573	if let Some( next_space122 ) = next {
190	122	// Remove from both trees
191	122	self.by_size.remove(&(next_space.size, next_space.start));
192	122	self.by_start.remove(&next_space.start);
193	122
194	122	// Subtract the removed space from total_free (will be re-added when inserting merged)
195	122	self.total_free -= next_space.size * FEOX_BLOCK_SIZE as u64;
196	122
197	122	merged_size += next_space.size;
198	451	}
199
200	573	Ok(FreeSpace {
201	573	start: merged_start,
202	573	size: merged_size,
203	573	})
204	576	}
205
206		/// Insert a free space into both trees
207	22.2k	fn insert_free_space(&mut self, space: FreeSpace) -> Result<()> {
208	22.2k	if space.size == 0 {
209	0	return Err(FeoxError::InvalidArgument);
210	22.2k	}
211
212		// Validate the space
213	22.2k	if !self.is_valid_free_space(&space) {
214	0	return Err(FeoxError::InvalidArgument);
215	22.2k	}
216
217		// Check for duplicates
218	22.2k	if self.by_start.contains_key(&space.start) {
219	0	return Err(FeoxError::DuplicateKey);
220	22.2k	}
221
222		// Update total free space
223	22.2k	self.total_free += space.size * FEOX_BLOCK_SIZE as u64;
224
225		// Insert into both trees
226	22.2k	self.by_size
227	22.2k	.insert((space.size, space.start), space.clone());
228	22.2k	self.by_start.insert(space.start, space);
229
230	22.2k	Ok(())
231	22.2k	}
232
233		/// Check if a free space is valid
234	43.9k	fn is_valid_free_space(&self, space: &FreeSpace) -> bool {
235	43.9k	if space.start < FEOX_DATA_START_BLOCK {
236	0	return false;
237	43.9k	}
238
239		// Check device bounds
240	43.9k	if self.device_size > 0 {
241	43.9k	let device_sectors = self.device_size / FEOX_BLOCK_SIZE as u64;
242	43.9k	if space.start >= device_sectors {
243	0	return false;
244	43.9k	}
245	43.9k	if space.start.checked_add(space.size).is_none() {
246	0	return false;
247	43.9k	}
248	43.9k	if space.start + space.size > device_sectors {
249	0	return false;
250	43.9k	}
251	0	}
252
253	43.9k	true
254	43.9k	}
255
256		/// Check if a sector range is valid
257	578	fn is_valid_sector_range(&self, start: u64, count: u64) -> bool {
258	578	if start < FEOX_DATA_START_BLOCK \|\| count == 0 {
259	0	return false;
260	578	}
261
262	578	if self.device_size > 0 {
263	578	let device_sectors = self.device_size / FEOX_BLOCK_SIZE as u64;
264	578	if start >= device_sectors {
265	1	return false;
266	577	}
267	577	match start.checked_add(count) {
268	577	Some( end576 ) if end <= device_sector s576 => {}576
269	1	_ => return false,
270		}
271	0	}
272
273	576	true
274	578	}
275
276		/// Update fragmentation metric
277	22.2k	fn update_fragmentation(&mut self) {
278	22.2k	if self.total_free == 0 {
279	9	self.fragmentation_percent = 0;
280	9	return;
281	22.2k	}
282
283	22.2k	let num_chunks = self.by_start.len() as u64;
284	22.2k	if num_chunks <= 1 {
285	22.1k	self.fragmentation_percent = 0;
286	22.1k	return;
287	59	}
288
289		// Find largest free chunk
290	59	let largest = self
291	59	.by_size
292	59	.iter()
293	59	.next_back()
294	59	.map(\|(_, space)\| space.size * FEOX_BLOCK_SIZE as u64)
295	59	.unwrap_or(0);
296
297		// Calculate fragmentation as percentage of free space not in largest chunk
298	59	if self.total_free > 0 {
299	59	let fragmented = self.total_free - largest;
300	59	self.fragmentation_percent = ((fragmented * 100) / self.total_free) as u32;
301	59	}0
302	22.2k	}
303
304		/// Get total free space in bytes
305	21	pub fn get_total_free(&self) -> u64 {
306	21	self.total_free
307	21	}
308
309		/// Get fragmentation percentage
310	208	pub fn get_fragmentation(&self) -> u32 {
311	208	self.fragmentation_percent
312	208	}
313
314		/// Get number of free chunks
315	7	pub fn get_free_chunks_count(&self) -> usize {
316	7	self.by_start.len()
317	7	}
318
319		/// Get largest free chunk in bytes
320	1	pub fn get_largest_free_chunk(&self) -> u64 {
321	1	self.by_size
322	1	.iter()
323	1	.next_back()
324	1	.map(\|(_, space)\| space.size * FEOX_BLOCK_SIZE as u64)
325	1	.unwrap_or(0)
326	1	}
327		}
328
329		impl Default for FreeSpaceManager {
330	0	fn default() -> Self {
331	0	Self::new()
332	0	}
333		}