fxfs/object_store/data_object_handle/
allocated_ranges.rs

1// Copyright 2024 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5use std::ops::Range;
6
7/// Whether this particular logical file range is in overwrite or CoW mode. Overwrite mode ranges
8/// have overwrite extents already allocated, and should use multi_overwrite. CoW mode ranges
9/// should use multi_write, and might or might not have extents in the region already.
10#[derive(Debug, Clone, PartialEq, Eq)]
11pub enum RangeType {
12    Cow(Range<u64>),
13    Overwrite(Range<u64>),
14}
15
16/// AllocatedRanges tracks the logical ranges of a file which are pre-allocated using allocate, in
17/// other words, the ranges of the file with overwrite extents. It's used by PagedObjectHandle to
18/// split writes to CoW ranges and writes to overwrite ranges into separate batches so they can
19/// have different transaction options.
20#[derive(Debug, Default, PartialEq, Eq)]
21pub struct AllocatedRanges {
22    ranges: Vec<Range<u64>>,
23}
24
25/// An iterator over the types of ranges within a particular query range. The range types can be
26/// CoW or overwrite.
27pub struct RangeOverlapIter<'a> {
28    query_range: Range<u64>,
29    index: usize,
30    ranges: &'a [Range<u64>],
31}
32
33impl<'a> Iterator for RangeOverlapIter<'a> {
34    type Item = RangeType;
35
36    fn next(&mut self) -> Option<Self::Item> {
37        if self.query_range.start == self.query_range.end {
38            return None;
39        }
40
41        if self.index == self.ranges.len() || self.query_range.start < self.ranges[self.index].start
42        {
43            let range = self.query_range.start
44                ..std::cmp::min(
45                    self.query_range.end,
46                    self.ranges.get(self.index).map(|r| r.start).unwrap_or(self.query_range.end),
47                );
48            self.query_range.start = range.end;
49            return Some(RangeType::Cow(range));
50        }
51
52        let range = self.query_range.start
53            ..std::cmp::min(self.query_range.end, self.ranges[self.index].end);
54        self.query_range.start = range.end;
55        self.index += 1;
56
57        Some(RangeType::Overwrite(range))
58    }
59}
60
61impl AllocatedRanges {
62    pub fn empty() -> Self {
63        Self { ranges: Vec::new() }
64    }
65
66    pub fn new(ranges_to_apply: &[Range<u64>]) -> Self {
67        let mut ranges = Vec::new();
68        for range_to_apply in ranges_to_apply {
69            Self::apply_range_to(&mut ranges, range_to_apply.clone());
70        }
71        Self { ranges }
72    }
73
74    pub fn clear(&mut self) {
75        self.ranges.clear();
76    }
77
78    pub fn is_empty(&self) -> bool {
79        self.ranges.is_empty()
80    }
81
82    /// Find the overlapping overwrite ranges in the given range for this file, so writes can be
83    /// split between them appropriately. Ranges with RangeType::Overwrite should be written to
84    /// with multi_overwrite and RangeType::Cow should use multi_write.
85    pub fn overlap<'a>(&'a self, query_range: Range<u64>) -> RangeOverlapIter<'a> {
86        let index = match self.ranges.binary_search_by_key(&query_range.start, |r| r.end) {
87            // If the start of the query range is exactly at the end of a range, there is zero
88            // overlap with that range, so start with the next one.
89            Ok(pos) => pos + 1,
90            Err(pos) => pos,
91        };
92        RangeOverlapIter { query_range, index, ranges: &self.ranges }
93    }
94
95    /// Apply range takes a single, valid file range and inserts it into the list of ranges it's
96    /// storing. This list of ranges, so it's easy to insert and search, is kept sorted and merged,
97    /// so that the list has no overlapping ranges.
98    pub fn apply_range(&mut self, new_range: Range<u64>) {
99        Self::apply_range_to(&mut self.ranges, new_range);
100    }
101
102    pub fn apply_range_to(ranges: &mut Vec<Range<u64>>, new_range: Range<u64>) {
103        let merge_start = match ranges.binary_search_by_key(&new_range.start, |r| r.end) {
104            // Ok means the returned index has a range that ends where this new one starts, which
105            // is handled fine by the logic below.
106            Ok(pos) => pos,
107            Err(pos) => pos,
108        };
109        if merge_start == ranges.len() {
110            // The new ranges starts beyond the end of all the current ranges.
111            ranges.push(new_range);
112            return;
113        }
114
115        if ranges[merge_start].start <= new_range.start {
116            // If the new range start is past (or at) the start but before the end, this is the
117            // first range that needs to get merged.
118            ranges[merge_start].end = std::cmp::max(ranges[merge_start].end, new_range.end);
119        } else {
120            // The new range starts before this one. Insert it at this spot, and merge from here.
121            ranges.insert(merge_start, new_range);
122        }
123
124        let mut merge_index = merge_start + 1;
125        while merge_index < ranges.len() && ranges[merge_index].start <= ranges[merge_start].end {
126            ranges[merge_start].end =
127                std::cmp::max(ranges[merge_start].end, ranges[merge_index].end);
128            merge_index += 1;
129        }
130        ranges.drain(merge_start + 1..merge_index);
131    }
132
133    /// For when a file is truncated. Drop any ranges past the cutoff point. If a range covers the
134    /// cutoff point, it is modified to end at the cutoff.
135    ///
136    /// Additionally, this returns true if there were previously tracked ranges but they were all
137    /// completely removed by this truncate call. In this case, metadata for a file will need to be
138    /// updated since there are no longer any overwrite ranges.
139    pub fn truncate(&mut self, cutoff: u64) -> bool {
140        if self.ranges.is_empty() {
141            // Nothing to do, return early. Since there were no ranges, we didn't _remove_ all the
142            // ranges which is the specific case we want to flag on return.
143            return false;
144        }
145        let mut index = match self.ranges.binary_search_by_key(&cutoff, |r| r.end) {
146            // If the cutoff is exactly at the end of a range, that range doesn't change, so start
147            // with the next one.
148            Ok(pos) => pos + 1,
149            Err(pos) => pos,
150        };
151        // If the index points at the end of the list, the cutoff is after all the ranges.
152        if index == self.ranges.len() {
153            return false;
154        }
155        // Handle the cutoff being partway through a range.
156        if ranges_at_index_or_truncate(&mut self.ranges, cutoff, index) {
157            index += 1;
158        }
159
160        self.ranges.truncate(index);
161        // If at this point our index is zero, then we completely dropped all the ranges, and there
162        // were some ranges, because we would have returned early if it was empty to begin with.
163        index == 0
164    }
165}
166
167fn ranges_at_index_or_truncate(ranges: &mut [Range<u64>], cutoff: u64, index: usize) -> bool {
168    if ranges[index].start < cutoff {
169        ranges[index].end = cutoff;
170        true
171    } else {
172        false
173    }
174}
175
176#[cfg(test)]
177mod tests {
178    use super::{AllocatedRanges, RangeType};
179    use std::ops::Range;
180
181    #[fuchsia::test]
182    fn test_allocated_ranges() {
183        struct Case {
184            applied_ranges: Vec<Range<u64>>,
185            expected_ranges: Vec<Range<u64>>,
186        }
187        let cases = [
188            Case { applied_ranges: vec![0..1], expected_ranges: vec![0..1] },
189            Case { applied_ranges: vec![0..1, 2..3], expected_ranges: vec![0..1, 2..3] },
190            Case {
191                applied_ranges: vec![0..1, 2..3, 4..5],
192                expected_ranges: vec![0..1, 2..3, 4..5],
193            },
194            Case {
195                applied_ranges: vec![4..5, 2..3, 0..1],
196                expected_ranges: vec![0..1, 2..3, 4..5],
197            },
198            Case {
199                applied_ranges: vec![0..1, 4..5, 2..3],
200                expected_ranges: vec![0..1, 2..3, 4..5],
201            },
202            Case { applied_ranges: vec![0..10, 20..30], expected_ranges: vec![0..10, 20..30] },
203            Case { applied_ranges: vec![0..5, 0..5], expected_ranges: vec![0..5] },
204            Case { applied_ranges: vec![0..5, 0..1], expected_ranges: vec![0..5] },
205            Case { applied_ranges: vec![0..5, 0..10], expected_ranges: vec![0..10] },
206            Case { applied_ranges: vec![3..4, 2..3], expected_ranges: vec![2..4] },
207            Case { applied_ranges: vec![2..3, 3..4], expected_ranges: vec![2..4] },
208            Case { applied_ranges: vec![2..3, 3..4, 4..5, 1..2], expected_ranges: vec![1..5] },
209            Case { applied_ranges: vec![1..10, 2..4, 8..9, 2..9], expected_ranges: vec![1..10] },
210            Case { applied_ranges: vec![2..3, 3..4, 1..2, 0..10], expected_ranges: vec![0..10] },
211            Case {
212                applied_ranges: vec![1..2, 3..4, 5..6, 7..8],
213                expected_ranges: vec![1..2, 3..4, 5..6, 7..8],
214            },
215            Case {
216                applied_ranges: vec![1..2, 3..4, 5..6, 7..8, 0..10],
217                expected_ranges: vec![0..10],
218            },
219            Case { applied_ranges: vec![4..8, 6..10], expected_ranges: vec![4..10] },
220            Case { applied_ranges: vec![4..8, 2..6], expected_ranges: vec![2..8] },
221            Case {
222                applied_ranges: vec![2..5, 7..11, 13..18, 20..30, 40..45, 10..25],
223                expected_ranges: vec![2..5, 7..30, 40..45],
224            },
225        ];
226
227        for case in cases {
228            let ranges = AllocatedRanges::new(&case.applied_ranges);
229            assert_eq!(ranges.ranges, case.expected_ranges);
230        }
231    }
232
233    #[fuchsia::test]
234    fn test_allocated_ranges_overlap() {
235        let mut ranges = AllocatedRanges::new(&[]);
236        // With no overwrite ranges recorded, all overlap calls should return the same range
237        // wrapped with Cow.
238        assert_eq!(ranges.overlap(0..1).collect::<Vec<_>>(), vec![RangeType::Cow(0..1)]);
239        assert_eq!(ranges.overlap(10..20).collect::<Vec<_>>(), vec![RangeType::Cow(10..20)]);
240
241        ranges.apply_range(10..20);
242        assert_eq!(ranges.overlap(30..35).collect::<Vec<_>>(), vec![RangeType::Cow(30..35)]);
243        assert_eq!(ranges.overlap(20..30).collect::<Vec<_>>(), vec![RangeType::Cow(20..30)]);
244        assert_eq!(ranges.overlap(0..5).collect::<Vec<_>>(), vec![RangeType::Cow(0..5)]);
245        assert_eq!(ranges.overlap(0..10).collect::<Vec<_>>(), vec![RangeType::Cow(0..10)]);
246
247        assert_eq!(ranges.overlap(12..13).collect::<Vec<_>>(), vec![RangeType::Overwrite(12..13)]);
248        assert_eq!(ranges.overlap(10..20).collect::<Vec<_>>(), vec![RangeType::Overwrite(10..20)]);
249
250        assert_eq!(
251            ranges.overlap(5..15).collect::<Vec<_>>(),
252            vec![RangeType::Cow(5..10), RangeType::Overwrite(10..15)]
253        );
254        assert_eq!(
255            ranges.overlap(5..20).collect::<Vec<_>>(),
256            vec![RangeType::Cow(5..10), RangeType::Overwrite(10..20)]
257        );
258        assert_eq!(
259            ranges.overlap(5..25).collect::<Vec<_>>(),
260            vec![RangeType::Cow(5..10), RangeType::Overwrite(10..20), RangeType::Cow(20..25)]
261        );
262
263        assert_eq!(ranges.overlap(10..15).collect::<Vec<_>>(), vec![RangeType::Overwrite(10..15)]);
264        assert_eq!(ranges.overlap(10..20).collect::<Vec<_>>(), vec![RangeType::Overwrite(10..20)]);
265        assert_eq!(
266            ranges.overlap(10..25).collect::<Vec<_>>(),
267            vec![RangeType::Overwrite(10..20), RangeType::Cow(20..25)]
268        );
269
270        assert_eq!(ranges.overlap(15..20).collect::<Vec<_>>(), vec![RangeType::Overwrite(15..20)]);
271        assert_eq!(
272            ranges.overlap(15..25).collect::<Vec<_>>(),
273            vec![RangeType::Overwrite(15..20), RangeType::Cow(20..25)]
274        );
275
276        assert_eq!(ranges.overlap(20..25).collect::<Vec<_>>(), vec![RangeType::Cow(20..25)]);
277
278        ranges.apply_range(30..40);
279        ranges.apply_range(50..60);
280
281        assert_eq!(
282            ranges.overlap(15..35).collect::<Vec<_>>(),
283            vec![
284                RangeType::Overwrite(15..20),
285                RangeType::Cow(20..30),
286                RangeType::Overwrite(30..35)
287            ]
288        );
289        assert_eq!(
290            ranges.overlap(25..45).collect::<Vec<_>>(),
291            vec![RangeType::Cow(25..30), RangeType::Overwrite(30..40), RangeType::Cow(40..45)]
292        );
293        assert_eq!(
294            ranges.overlap(0..70).collect::<Vec<_>>(),
295            vec![
296                RangeType::Cow(0..10),
297                RangeType::Overwrite(10..20),
298                RangeType::Cow(20..30),
299                RangeType::Overwrite(30..40),
300                RangeType::Cow(40..50),
301                RangeType::Overwrite(50..60),
302                RangeType::Cow(60..70)
303            ]
304        );
305
306        ranges.apply_range(0..100);
307        assert_eq!(ranges.overlap(0..100).collect::<Vec<_>>(), vec![RangeType::Overwrite(0..100)]);
308    }
309
310    #[fuchsia::test]
311    fn test_trim_ranges() {
312        struct Case {
313            applied: Vec<Range<u64>>,
314            cutoff: u64,
315            expected: Vec<Range<u64>>,
316            dropped_all: bool,
317        }
318
319        let cases = [
320            Case { applied: vec![], cutoff: 10, expected: vec![], dropped_all: false },
321            Case { applied: vec![0..20], cutoff: 0, expected: vec![], dropped_all: true },
322            Case { applied: vec![0..20], cutoff: 10, expected: vec![0..10], dropped_all: false },
323            Case { applied: vec![0..20], cutoff: 20, expected: vec![0..20], dropped_all: false },
324            Case { applied: vec![0..20], cutoff: 30, expected: vec![0..20], dropped_all: false },
325            Case { applied: vec![0..20, 30..50], cutoff: 0, expected: vec![], dropped_all: true },
326            Case {
327                applied: vec![0..20, 30..50],
328                cutoff: 10,
329                expected: vec![0..10],
330                dropped_all: false,
331            },
332            Case {
333                applied: vec![0..20, 30..50],
334                cutoff: 30,
335                expected: vec![0..20],
336                dropped_all: false,
337            },
338            Case {
339                applied: vec![0..20, 30..50],
340                cutoff: 40,
341                expected: vec![0..20, 30..40],
342                dropped_all: false,
343            },
344            Case {
345                applied: vec![30..50, 60..80, 90..100],
346                cutoff: 29,
347                expected: vec![],
348                dropped_all: true,
349            },
350            Case {
351                applied: vec![30..50, 60..80, 90..100],
352                cutoff: 30,
353                expected: vec![],
354                dropped_all: true,
355            },
356            Case {
357                applied: vec![30..50, 60..80, 90..100],
358                cutoff: 31,
359                expected: vec![30..31],
360                dropped_all: false,
361            },
362            Case {
363                applied: vec![30..50, 60..80, 90..100],
364                cutoff: 70,
365                expected: vec![30..50, 60..70],
366                dropped_all: false,
367            },
368            Case {
369                applied: vec![30..50, 60..80, 90..100],
370                cutoff: 110,
371                expected: vec![30..50, 60..80, 90..100],
372                dropped_all: false,
373            },
374        ];
375
376        for (i, case) in cases.into_iter().enumerate() {
377            let mut ranges = AllocatedRanges::new(&case.applied);
378            assert_eq!(ranges.truncate(case.cutoff), case.dropped_all, "failed case # {i}");
379            assert_eq!(ranges.ranges, case.expected, "failed case # {i}");
380        }
381    }
382}
fxfs/object_store/data_object_handle/allocated_ranges.rs

fxfs/object_store/data_object_handle/
allocated_ranges.rs
