1use crate::checksum::{Checksums, ChecksumsV32, ChecksumsV37, ChecksumsV38};
8use crate::lsm_tree::types::{OrdLowerBound, OrdUpperBound};
9use crate::round::{round_down, round_up};
10use crate::serialized_types::{migrate_to_version, Migrate};
11use bit_vec::BitVec;
12use fprint::TypeFingerprint;
13use serde::{Deserialize, Serialize};
14use std::cmp::{max, min};
15use std::hash::Hash;
16use std::ops::Range;
17
18pub const DEFAULT_DATA_ATTRIBUTE_ID: u64 = 0;
20
21pub const BLOB_MERKLE_ATTRIBUTE_ID: u64 = 1;
25
26pub const FSVERITY_MERKLE_ATTRIBUTE_ID: u64 = 2;
29
30pub type ExtentKey = ExtentKeyV32;
33
34#[derive(Clone, Debug, Eq, Hash, PartialEq, Serialize, Deserialize, TypeFingerprint)]
35#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
36pub struct ExtentKeyV32 {
37 pub range: Range<u64>,
38}
39
40const EXTENT_HASH_BUCKET_SIZE: u64 = 1 * 1024 * 1024;
41
42pub struct ExtentKeyPartitionIterator {
43 range: Range<u64>,
44}
45
46impl Iterator for ExtentKeyPartitionIterator {
47 type Item = Range<u64>;
48
49 fn next(&mut self) -> Option<Self::Item> {
50 if self.range.start >= self.range.end {
51 None
52 } else {
53 let start = self.range.start;
54 self.range.start = start.saturating_add(EXTENT_HASH_BUCKET_SIZE);
55 let end = std::cmp::min(self.range.start, self.range.end);
56 Some(start..end)
57 }
58 }
59}
60
61impl ExtentKey {
62 pub fn new(range: std::ops::Range<u64>) -> Self {
64 Self { range }
65 }
66
67 pub fn overlap(&self, other: &ExtentKey) -> Option<Range<u64>> {
69 if self.range.end <= other.range.start || self.range.start >= other.range.end {
70 None
71 } else {
72 Some(max(self.range.start, other.range.start)..min(self.range.end, other.range.end))
73 }
74 }
75
76 pub fn search_key(&self) -> Self {
83 assert_ne!(self.range.start, self.range.end);
84 ExtentKey::search_key_from_offset(self.range.start)
85 }
86
87 pub fn search_key_from_offset(offset: u64) -> Self {
90 Self { range: 0..offset + 1 }
91 }
92
93 pub fn key_for_merge_into(&self) -> Self {
100 Self { range: 0..self.range.start }
101 }
102
103 pub fn fuzzy_hash_partition(&self) -> ExtentKeyPartitionIterator {
105 ExtentKeyPartitionIterator {
106 range: round_down(self.range.start, EXTENT_HASH_BUCKET_SIZE)
107 ..round_up(self.range.end, EXTENT_HASH_BUCKET_SIZE).unwrap_or(u64::MAX),
108 }
109 }
110}
111
112impl OrdUpperBound for ExtentKey {
117 fn cmp_upper_bound(&self, other: &ExtentKey) -> std::cmp::Ordering {
118 self.range.end.cmp(&other.range.end)
125 }
126}
127
128impl OrdLowerBound for ExtentKey {
129 fn cmp_lower_bound(&self, other: &ExtentKey) -> std::cmp::Ordering {
132 self.range.start.cmp(&other.range.start)
133 }
134}
135
136impl Ord for ExtentKey {
137 fn cmp(&self, other: &Self) -> std::cmp::Ordering {
138 self.range.start.cmp(&other.range.start).then(self.range.end.cmp(&other.range.end))
142 }
143}
144
145impl PartialOrd for ExtentKey {
146 fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
147 Some(self.cmp(other))
148 }
149}
150
151pub type ExtentMode = ExtentModeV38;
153
154#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, TypeFingerprint)]
155pub enum ExtentModeV38 {
156 Raw,
160 Cow(ChecksumsV38),
163 OverwritePartial(BitVec),
168 Overwrite,
172}
173
174#[cfg(fuzz)]
175impl<'a> arbitrary::Arbitrary<'a> for ExtentMode {
176 fn arbitrary(u: &mut arbitrary::Unstructured<'a>) -> arbitrary::Result<Self> {
177 Ok(match u.int_in_range(0..=3)? {
178 0 => ExtentMode::Raw,
179 1 => ExtentMode::Cow(u.arbitrary()?),
180 2 => ExtentMode::OverwritePartial(BitVec::from_bytes(u.arbitrary()?)),
181 3 => ExtentMode::Overwrite,
182 _ => unreachable!(),
183 })
184 }
185}
186
187pub type ExtentValue = ExtentValueV38;
190
191#[derive(Debug, Clone, Serialize, Deserialize, PartialEq, TypeFingerprint)]
192#[cfg_attr(fuzz, derive(arbitrary::Arbitrary))]
193pub enum ExtentValueV38 {
194 None,
197 Some { device_offset: u64, mode: ExtentModeV38, key_id: u64 },
201}
202
203impl ExtentValue {
204 pub fn new(device_offset: u64, mode: ExtentMode, key_id: u64) -> ExtentValue {
205 ExtentValue::Some { device_offset, mode, key_id }
206 }
207
208 pub fn new_raw(device_offset: u64, key_id: u64) -> ExtentValue {
209 Self::new(device_offset, ExtentMode::Raw, key_id)
210 }
211
212 pub fn with_checksum(device_offset: u64, checksums: Checksums, key_id: u64) -> ExtentValue {
214 Self::new(device_offset, ExtentMode::Cow(checksums), key_id)
215 }
216
217 pub fn blank_overwrite_extent(
219 device_offset: u64,
220 num_blocks: usize,
221 key_id: u64,
222 ) -> ExtentValue {
223 Self::new(
224 device_offset,
225 ExtentMode::OverwritePartial(BitVec::from_elem(num_blocks, false)),
226 key_id,
227 )
228 }
229
230 pub fn initialized_overwrite_extent(device_offset: u64, key_id: u64) -> ExtentValue {
232 Self::new(device_offset, ExtentMode::Overwrite, key_id)
233 }
234
235 pub fn deleted_extent() -> ExtentValue {
237 ExtentValue::None
238 }
239
240 pub fn is_deleted(&self) -> bool {
241 if let ExtentValue::None = self {
242 true
243 } else {
244 false
245 }
246 }
247
248 pub fn offset_by(&self, amount: u64, extent_len: u64) -> Self {
251 match self {
252 ExtentValue::None => Self::deleted_extent(),
253 ExtentValue::Some { device_offset, mode, key_id } => {
254 let mode = match mode {
255 ExtentMode::Raw => ExtentMode::Raw,
256 ExtentMode::Cow(checksums) => {
257 if checksums.len() > 0 {
258 let index = (amount / (extent_len / checksums.len() as u64)) as usize;
259 ExtentMode::Cow(checksums.offset_by(index))
260 } else {
261 ExtentMode::Cow(Checksums::fletcher(Vec::new()))
262 }
263 }
264 ExtentMode::Overwrite => ExtentMode::Overwrite,
265 ExtentMode::OverwritePartial(bitmap) => {
266 debug_assert!(bitmap.len() > 0);
267 let index = (amount / (extent_len / bitmap.len() as u64)) as usize;
268 ExtentMode::OverwritePartial(bitmap.clone().split_off(index))
269 }
270 };
271 ExtentValue::Some { device_offset: device_offset + amount, mode, key_id: *key_id }
272 }
273 }
274 }
275
276 pub fn shrunk(&self, original_len: u64, new_len: u64) -> Self {
278 match self {
279 ExtentValue::None => Self::deleted_extent(),
280 ExtentValue::Some { device_offset, mode, key_id } => {
281 let mode = match mode {
282 ExtentMode::Raw => ExtentMode::Raw,
283 ExtentMode::Cow(checksums) => {
284 if checksums.len() > 0 {
285 let len = (new_len / (original_len / checksums.len() as u64)) as usize;
286 ExtentMode::Cow(checksums.shrunk(len))
287 } else {
288 ExtentMode::Cow(Checksums::fletcher(Vec::new()))
289 }
290 }
291 ExtentMode::Overwrite => ExtentMode::Overwrite,
292 ExtentMode::OverwritePartial(bitmap) => {
293 debug_assert!(bitmap.len() > 0);
294 let len = (new_len / (original_len / bitmap.len() as u64)) as usize;
295 let mut new_bitmap = bitmap.clone();
296 new_bitmap.truncate(len);
297 ExtentMode::OverwritePartial(new_bitmap)
298 }
299 };
300 ExtentValue::Some { device_offset: *device_offset, mode, key_id: *key_id }
301 }
302 }
303 }
304}
305
306#[derive(Debug, Serialize, Deserialize, TypeFingerprint)]
307#[migrate_to_version(ExtentValueV38)]
308pub enum ExtentValueV37 {
309 None,
310 Some { device_offset: u64, checksums: ChecksumsV37, key_id: u64 },
311}
312
313#[derive(Debug, Serialize, Deserialize, Migrate, TypeFingerprint)]
314#[migrate_to_version(ExtentValueV37)]
315pub enum ExtentValueV32 {
316 None,
317 Some { device_offset: u64, checksums: ChecksumsV32, key_id: u64 },
318}
319
320impl From<ExtentValueV37> for ExtentValueV38 {
321 fn from(value: ExtentValueV37) -> Self {
322 match value {
323 ExtentValueV37::None => ExtentValue::None,
324 ExtentValueV37::Some { device_offset, checksums, key_id } => {
325 let mode = match checksums.migrate() {
326 None => ExtentMode::Raw,
327 Some(checksums) => ExtentMode::Cow(checksums),
328 };
329 ExtentValue::Some { device_offset, mode, key_id }
330 }
331 }
332 }
333}
334
335#[cfg(test)]
336mod tests {
337 use super::{ExtentKey, ExtentMode, ExtentValue};
338 use crate::checksum::Checksums;
339 use crate::lsm_tree::types::{OrdLowerBound, OrdUpperBound};
340 use crate::object_store::VOLUME_DATA_KEY_ID;
341 use bit_vec::BitVec;
342 use std::cmp::Ordering;
343
344 #[test]
345 fn test_extent_cmp() {
346 let extent = ExtentKey::new(100..150);
347 assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(0..100)), Ordering::Greater);
348 assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(0..110)), Ordering::Greater);
349 assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(0..150)), Ordering::Equal);
350 assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(99..150)), Ordering::Equal);
351 assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(100..150)), Ordering::Equal);
352 assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(0..151)), Ordering::Less);
353 assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(100..151)), Ordering::Less);
354 assert_eq!(extent.cmp_upper_bound(&ExtentKey::new(150..1000)), Ordering::Less);
355 }
356
357 #[test]
358 fn test_extent_cmp_lower_bound() {
359 let extent = ExtentKey::new(100..150);
360 assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(0..100)), Ordering::Greater);
361 assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(0..110)), Ordering::Greater);
362 assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(0..150)), Ordering::Greater);
363 assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(0..1000)), Ordering::Greater);
364 assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(99..1000)), Ordering::Greater);
365 assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(100..150)), Ordering::Equal);
366 assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(100..1000)), Ordering::Equal);
368 assert_eq!(extent.cmp_lower_bound(&ExtentKey::new(101..102)), Ordering::Less);
369 }
370
371 #[test]
372 fn test_extent_search_and_insertion_key() {
373 let extent = ExtentKey::new(100..150);
374 assert_eq!(extent.search_key(), ExtentKey::new(0..101));
375 assert_eq!(extent.cmp_lower_bound(&extent.search_key()), Ordering::Greater);
376 assert_eq!(extent.cmp_upper_bound(&extent.search_key()), Ordering::Greater);
377 assert_eq!(extent.key_for_merge_into(), ExtentKey::new(0..100));
378 assert_eq!(extent.cmp_lower_bound(&extent.key_for_merge_into()), Ordering::Greater);
379 }
380
381 #[test]
382 fn extent_value_offset_by() {
383 assert_eq!(ExtentValue::None.offset_by(1024, 2048), ExtentValue::None);
384 assert_eq!(
385 ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).offset_by(0, 2048),
386 ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
387 );
388 assert_eq!(
389 ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).offset_by(1024, 2048),
390 ExtentValue::new_raw(2048, VOLUME_DATA_KEY_ID)
391 );
392 assert_eq!(
393 ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).offset_by(2048, 2048),
394 ExtentValue::new_raw(3072, VOLUME_DATA_KEY_ID)
395 );
396
397 let make_checksums = |range: std::ops::Range<u64>| Checksums::fletcher(range.collect());
398
399 assert_eq!(
401 ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
402 .offset_by(0, 2048),
403 ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
404 );
405 assert_eq!(
406 ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
407 .offset_by(1024, 2048),
408 ExtentValue::with_checksum(2048, make_checksums(4..8), VOLUME_DATA_KEY_ID)
409 );
410 assert_eq!(
411 ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
412 .offset_by(2048, 2048),
413 ExtentValue::with_checksum(3072, Checksums::fletcher(Vec::new()), VOLUME_DATA_KEY_ID)
414 );
415
416 let make_bitmap = |cut, length| {
419 let mut begin_bitmap = BitVec::from_elem(cut, false);
420 let mut end_bitmap = BitVec::from_elem(length - cut, true);
421 begin_bitmap.append(&mut end_bitmap);
422 ExtentMode::OverwritePartial(begin_bitmap)
423 };
424 let make_extent =
425 |device_offset, mode| ExtentValue::Some { device_offset, mode, key_id: 0 };
426
427 assert_eq!(
428 make_extent(1024, make_bitmap(1, 8)).offset_by(0, 2048),
429 make_extent(1024, make_bitmap(1, 8))
430 );
431 assert_eq!(
432 make_extent(1024, make_bitmap(5, 8)).offset_by(1024, 2048),
433 make_extent(2048, make_bitmap(1, 4))
434 );
435 assert_eq!(
436 make_extent(1024, make_bitmap(0, 8)).offset_by(2048, 2048),
437 make_extent(3072, ExtentMode::OverwritePartial(BitVec::new()))
438 );
439
440 assert_eq!(
441 make_extent(1024, ExtentMode::Overwrite).offset_by(0, 2048),
442 make_extent(1024, ExtentMode::Overwrite)
443 );
444 assert_eq!(
445 make_extent(1024, ExtentMode::Overwrite).offset_by(1024, 2048),
446 make_extent(2048, ExtentMode::Overwrite)
447 );
448 assert_eq!(
449 make_extent(1024, ExtentMode::Overwrite).offset_by(2048, 2048),
450 make_extent(3072, ExtentMode::Overwrite)
451 );
452 }
453
454 #[test]
455 fn extent_value_shrunk() {
456 assert_eq!(ExtentValue::None.shrunk(2048, 1024), ExtentValue::None);
457 assert_eq!(
458 ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).shrunk(2048, 2048),
459 ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
460 );
461 assert_eq!(
462 ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).shrunk(2048, 1024),
463 ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
464 );
465 assert_eq!(
466 ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID).shrunk(2048, 0),
467 ExtentValue::new_raw(1024, VOLUME_DATA_KEY_ID)
468 );
469
470 let make_checksums = |range: std::ops::Range<u64>| Checksums::fletcher(range.collect());
471
472 assert_eq!(
474 ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
475 .shrunk(2048, 2048),
476 ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
477 );
478 assert_eq!(
479 ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
480 .shrunk(2048, 1024),
481 ExtentValue::with_checksum(1024, make_checksums(0..4), VOLUME_DATA_KEY_ID)
482 );
483 assert_eq!(
484 ExtentValue::with_checksum(1024, make_checksums(0..8), VOLUME_DATA_KEY_ID)
485 .shrunk(2048, 0),
486 ExtentValue::with_checksum(1024, Checksums::fletcher(Vec::new()), VOLUME_DATA_KEY_ID)
487 );
488
489 let make_bitmap = |cut, length| {
492 let mut begin_bitmap = BitVec::from_elem(cut, false);
493 let mut end_bitmap = BitVec::from_elem(length - cut, true);
494 begin_bitmap.append(&mut end_bitmap);
495 ExtentMode::OverwritePartial(begin_bitmap)
496 };
497 let make_extent =
498 |device_offset, mode| ExtentValue::Some { device_offset, mode, key_id: 0 };
499
500 assert_eq!(
501 make_extent(1024, make_bitmap(1, 8)).shrunk(2048, 2048),
502 make_extent(1024, make_bitmap(1, 8))
503 );
504 assert_eq!(
505 make_extent(1024, make_bitmap(3, 8)).shrunk(2048, 1024),
506 make_extent(1024, make_bitmap(3, 4))
507 );
508 assert_eq!(
509 make_extent(1024, make_bitmap(0, 8)).shrunk(2048, 0),
510 make_extent(1024, ExtentMode::OverwritePartial(BitVec::new()))
511 );
512
513 assert_eq!(
514 make_extent(1024, ExtentMode::Overwrite).shrunk(2048, 2048),
515 make_extent(1024, ExtentMode::Overwrite)
516 );
517 assert_eq!(
518 make_extent(1024, ExtentMode::Overwrite).shrunk(2048, 1024),
519 make_extent(1024, ExtentMode::Overwrite)
520 );
521 assert_eq!(
522 make_extent(1024, ExtentMode::Overwrite).shrunk(2048, 0),
523 make_extent(1024, ExtentMode::Overwrite)
524 );
525 }
526}