fxfs/object_store/data_object_handle/
allocated_ranges.rs

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

fxfs/object_store/data_object_handle/
allocated_ranges.rs
