1use crate::{Blob, BufMut, Error, IoBuf, IoBufMut, ReadOptions};
52#[cfg(any(test, feature = "test-utils"))]
53use crate::{Storage, WriteOptions};
54use commonware_codec::{Buf, Copying, EncodeFixed, FixedSize, Read as CodecRead, ReadExt, Write};
55use commonware_cryptography::{Crc32, crc32};
56use std::num::NonZeroU16;
57
58mod cache;
59mod read;
60mod sealed;
61mod tip;
62mod view;
63mod writer;
64
65pub use cache::CacheRef;
66pub use read::Replay;
67pub use sealed::Sealed;
68use tracing::{debug, error};
69pub use writer::{Append, Recovering, Recovery, Writer};
70
71pub const CHECKSUM_SIZE: u64 = Checksum::SIZE as u64;
73
74const CHECKSUM_SLOT_LEN_SIZE: usize = u16::SIZE;
75const CHECKSUM_SLOT_SIZE: usize = CHECKSUM_SLOT_LEN_SIZE + crc32::Digest::SIZE;
76
77pub const fn page_size(physical_page_size: u32) -> NonZeroU16 {
91 assert!(
92 physical_page_size.is_power_of_two(),
93 "physical page size must be a power of two"
94 );
95 assert!(
96 physical_page_size as u64 > CHECKSUM_SIZE,
97 "physical page size must exceed the CRC record size"
98 );
99 let logical = physical_page_size as u64 - CHECKSUM_SIZE;
100 assert!(
101 logical <= u16::MAX as u64,
102 "logical page size must fit in a u16"
103 );
104 match NonZeroU16::new(logical as u16) {
105 Some(size) => size,
106 None => unreachable!(),
107 }
108}
109
110#[cfg(test)]
113pub(crate) fn validate_page_for_tests(page: &[u8]) -> bool {
114 Checksum::validate_page(page).is_some()
115}
116
117#[cfg(any(test, feature = "test-utils"))]
125pub fn page_len(page: &[u8], logical_page_size: usize) -> Option<usize> {
126 let footer = page.get(logical_page_size..)?;
127 if footer.len() != CHECKSUM_SIZE as usize {
128 return None;
129 }
130 let slots = [
131 (
132 u16::from_be_bytes(footer[0..2].try_into().unwrap()) as usize,
133 u32::from_be_bytes(footer[2..6].try_into().unwrap()),
134 ),
135 (
136 u16::from_be_bytes(footer[6..8].try_into().unwrap()) as usize,
137 u32::from_be_bytes(footer[8..12].try_into().unwrap()),
138 ),
139 ];
140 let authoritative = usize::from(slots[1].0 > slots[0].0);
141 for slot in [authoritative, authoritative ^ 1] {
142 let (len, checksum) = slots[slot];
143 if len > 0 && len <= logical_page_size && Crc32::checksum(&page[..len]) == checksum {
144 return Some(len);
145 }
146 }
147 None
148}
149
150#[cfg(any(test, feature = "test-utils"))]
154pub async fn corrupt_page(
155 storage: &impl Storage,
156 partition: &str,
157 name: &[u8],
158 page: u64,
159 logical_page_size: u64,
160) {
161 let physical_page_size = logical_page_size + CHECKSUM_SIZE;
163 let offset = page * physical_page_size;
164 let (blob, size) = storage.open(partition, name).await.unwrap();
165
166 assert!(
170 offset
171 .checked_add(physical_page_size * 2)
172 .is_some_and(|end| end <= size),
173 "corruption target must be an interior page"
174 );
175 let byte = blob
176 .read_at(offset, 1, ReadOptions::default())
177 .await
178 .unwrap()
179 .coalesce();
180 blob.write_at(
181 offset,
182 vec![byte.as_ref()[0] ^ 0xFF],
183 WriteOptions::default(),
184 )
185 .await
186 .unwrap();
187 blob.sync().await.unwrap();
188}
189
190fn validate_read_ranges(
197 buf_len: usize,
198 ranges: impl Iterator<Item = (u64, usize)>,
199 size: u64,
200) -> Result<(), Error> {
201 let mut expected_len = 0usize;
202 let mut previous_end = None;
203 for (offset, len) in ranges {
204 expected_len = expected_len
205 .checked_add(len)
206 .expect("buf must hold one slot per range totaling its length");
207 let end = offset
208 .checked_add(len as u64)
209 .ok_or(Error::OffsetOverflow)?;
210 if let Some(previous_end) = previous_end {
211 assert!(
212 offset >= previous_end,
213 "ranges must be sorted and non-overlapping"
214 );
215 }
216 if end > size {
217 return Err(Error::BlobInsufficientLength);
218 }
219 previous_end = Some(end);
220 }
221 assert_eq!(
222 buf_len, expected_len,
223 "buf must hold one slot per range totaling its length"
224 );
225 Ok(())
226}
227
228fn physical_page(page_num: u64, page_size: u64) -> Result<(u64, usize), Error> {
231 let physical_page_size = page_size
232 .checked_add(CHECKSUM_SIZE)
233 .ok_or(Error::OffsetOverflow)?;
234 let physical_page_start = page_num
235 .checked_mul(physical_page_size)
236 .ok_or(Error::OffsetOverflow)?;
237 let len = usize::try_from(physical_page_size).map_err(|_| Error::OffsetOverflow)?;
238 Ok((physical_page_start, len))
239}
240
241fn validate_physical_page(page: IoBufMut) -> Result<(IoBuf, ActiveChecksum), Error> {
243 let Some(checksum) = Checksum::validate_page(page.as_ref()) else {
244 return Err(Error::InvalidChecksum);
245 };
246 Ok((page.freeze().slice(..usize::from(checksum.len)), checksum))
247}
248
249async fn get_page_with_checksum_from_blob(
251 blob: &impl Blob,
252 page_num: u64,
253 page_size: u64,
254 read_options: ReadOptions,
255) -> Result<(IoBuf, ActiveChecksum), Error> {
256 let (start, len) = physical_page(page_num, page_size)?;
257 let page = blob.read_at(start, len, read_options).await?.coalesce();
258 validate_physical_page(page)
259}
260
261#[derive(Clone, Copy, Debug, Eq, PartialEq)]
263enum Slot {
264 First,
265 Second,
266}
267
268impl Slot {
269 const fn offset(self) -> usize {
271 match self {
272 Self::First => 0,
273 Self::Second => CHECKSUM_SLOT_SIZE,
274 }
275 }
276
277 const fn other(self) -> Self {
279 match self {
280 Self::First => Self::Second,
281 Self::Second => Self::First,
282 }
283 }
284}
285
286#[derive(Clone, Copy, Debug, Eq, PartialEq)]
288struct ActiveChecksum {
289 slot: Slot,
290 len: u16,
291 crc: u32,
292}
293
294impl ActiveChecksum {
295 const fn new(slot: Slot, len: u16, crc: u32) -> Self {
296 Self { slot, len, crc }
297 }
298}
299
300struct Checksum {
305 len1: u16,
306 crc1: u32,
307 len2: u16,
308 crc2: u32,
309}
310
311impl Checksum {
312 const fn new(len: u16, crc: u32) -> Self {
315 Self {
316 len1: len,
317 crc1: crc,
318 len2: 0,
319 crc2: 0,
320 }
321 }
322
323 const fn authoritative(&self) -> Slot {
325 if self.len1 >= self.len2 {
326 Slot::First
327 } else {
328 Slot::Second
329 }
330 }
331
332 fn validate_page(buf: &[u8]) -> Option<ActiveChecksum> {
335 let physical_page_size = buf.len() as u64;
336 if physical_page_size < CHECKSUM_SIZE {
337 error!(
338 physical_page_size,
339 required = CHECKSUM_SIZE,
340 "read page smaller than CRC record"
341 );
342 return None;
343 }
344
345 let crc_start_idx = (physical_page_size - CHECKSUM_SIZE) as usize;
348 let mut crc_bytes = Copying(&buf[crc_start_idx..]);
349 let crc_record = Self::read(&mut crc_bytes).expect("CRC record read should not fail");
350
351 let authoritative = crc_record.authoritative();
354 if let Some(checksum) = crc_record.validate_slot(authoritative, buf, crc_start_idx) {
355 return Some(checksum);
356 }
357
358 debug!("Invalid authoritative CRC, using fallback CRC");
361 let checksum = crc_record.validate_slot(authoritative.other(), buf, crc_start_idx);
362 if checksum.is_none() {
363 debug!("Invalid fallback CRC");
364 }
365 checksum
366 }
367
368 fn validate_slot(
370 &self,
371 slot: Slot,
372 buf: &[u8],
373 crc_start_idx: usize,
374 ) -> Option<ActiveChecksum> {
375 let (len, crc) = self.get_slot(slot);
376 let len_usize = len as usize;
377
378 if len_usize == 0 {
381 return None;
382 }
383
384 if len_usize > crc_start_idx {
386 return None;
387 }
388
389 if Crc32::checksum(&buf[..len_usize]) != crc {
391 return None;
392 }
393 Some(ActiveChecksum::new(slot, len, crc))
394 }
395
396 fn other_slot_is_inert(buf: &[u8], active: &ActiveChecksum) -> bool {
400 let crc_start_idx = buf.len() - Self::SIZE;
401 let mut crc_bytes = Copying(&buf[crc_start_idx..]);
402 let crc_record = Self::read(&mut crc_bytes).expect("CRC record must decode");
403 let slot = active.slot.other();
404 crc_record.get_slot(slot) == (0, 0)
405 || crc_record
406 .validate_slot(slot, buf, crc_start_idx)
407 .is_some_and(|checksum| checksum.len <= active.len)
408 }
409
410 const fn get_slot(&self, slot: Slot) -> (u16, u32) {
412 match slot {
413 Slot::First => (self.len1, self.crc1),
414 Slot::Second => (self.len2, self.crc2),
415 }
416 }
417
418 fn to_bytes(&self) -> [u8; CHECKSUM_SIZE as usize] {
420 self.encode_fixed()
421 }
422
423 fn slot_bytes(len: u16, crc: u32) -> [u8; CHECKSUM_SLOT_SIZE] {
428 let mut bytes = [0; CHECKSUM_SLOT_SIZE];
429 let mut buf = bytes.as_mut_slice();
430 len.write(&mut buf);
431 crc.write(&mut buf);
432 bytes
433 }
434
435 fn slot_len_bytes(len: u16) -> [u8; CHECKSUM_SLOT_LEN_SIZE] {
443 let mut bytes = [0; CHECKSUM_SLOT_LEN_SIZE];
444 let mut buf = bytes.as_mut_slice();
445 len.write(&mut buf);
446 bytes
447 }
448}
449
450impl Write for Checksum {
451 fn write(&self, buf: &mut impl BufMut) {
452 self.len1.write(buf);
453 self.crc1.write(buf);
454 self.len2.write(buf);
455 self.crc2.write(buf);
456 }
457}
458
459impl CodecRead for Checksum {
460 type Cfg = ();
461
462 fn read_cfg(buf: &mut impl Buf, _: &Self::Cfg) -> Result<Self, commonware_codec::Error> {
463 Ok(Self {
464 len1: u16::read(buf)?,
465 crc1: u32::read(buf)?,
466 len2: u16::read(buf)?,
467 crc2: u32::read(buf)?,
468 })
469 }
470}
471
472impl FixedSize for Checksum {
473 const SIZE: usize = 2 * u16::SIZE + 2 * crc32::Digest::SIZE;
474}
475
476#[cfg(feature = "arbitrary")]
477impl arbitrary::Arbitrary<'_> for Checksum {
478 fn arbitrary(u: &mut arbitrary::Unstructured<'_>) -> arbitrary::Result<Self> {
479 Ok(Self {
480 len1: u.arbitrary()?,
481 crc1: u.arbitrary()?,
482 len2: u.arbitrary()?,
483 crc2: u.arbitrary()?,
484 })
485 }
486}
487
488#[cfg(test)]
489mod tests {
490 use super::*;
491 use rstest::rstest;
492
493 #[test]
494 #[should_panic(expected = "corruption target must be an interior page")]
495 fn test_corrupt_page_rejects_short_blob() {
496 use crate::Runner as _;
497 crate::deterministic::Runner::default().start(|context| async move {
498 corrupt_page(&context, "short-blob", b"blob", 0, 64).await;
499 });
500 }
501
502 enum ValidationExpectation {
503 Ok,
504 OffsetOverflow,
505 BlobInsufficientLength,
506 }
507
508 #[rstest]
509 #[case::ok(12, vec![(0, 4), (4, 8)], 16, ValidationExpectation::Ok)]
510 #[case::empty_ranges_are_a_noop(0, vec![], 0, ValidationExpectation::Ok)]
511 #[case::zero_length_range(4, vec![(0, 0), (0, 4)], 16, ValidationExpectation::Ok)]
512 #[case::offset_overflow(4, vec![(u64::MAX, 4)], 16, ValidationExpectation::OffsetOverflow)]
513 #[case::insufficient_length(4, vec![(14, 4)], 16, ValidationExpectation::BlobInsufficientLength)]
514 #[case::range_may_end_exactly_at_logical_size(4, vec![(12, 4)], 16, ValidationExpectation::Ok)]
515 fn test_validate_read_ranges(
516 #[case] buf_len: usize,
517 #[case] ranges: Vec<(u64, usize)>,
518 #[case] size: u64,
519 #[case] expected: ValidationExpectation,
520 ) {
521 let result = validate_read_ranges(buf_len, ranges.iter().copied(), size);
522
523 match expected {
524 ValidationExpectation::Ok => assert!(result.is_ok()),
525 ValidationExpectation::OffsetOverflow => {
526 assert!(matches!(result, Err(Error::OffsetOverflow)))
527 }
528 ValidationExpectation::BlobInsufficientLength => {
529 assert!(matches!(result, Err(Error::BlobInsufficientLength)))
530 }
531 }
532 }
533
534 #[test]
535 #[should_panic(expected = "buf must hold one slot per range totaling its length")]
536 fn test_validate_read_ranges_rejects_buffer_len_mismatch() {
537 let _ = validate_read_ranges(7, [(0, 4), (4, 4)].into_iter(), 16);
538 }
539
540 #[test]
541 #[should_panic(expected = "ranges must be sorted and non-overlapping")]
542 fn test_validate_read_ranges_rejects_overlapping_ranges() {
543 let _ = validate_read_ranges(8, [(0, 4), (2, 4)].into_iter(), 16);
544 }
545
546 #[test]
547 #[should_panic(expected = "ranges must be sorted and non-overlapping")]
548 fn test_validate_read_ranges_rejects_unsorted_ranges() {
549 let _ = validate_read_ranges(8, [(8, 4), (4, 4)].into_iter(), 16);
550 }
551
552 #[test]
553 #[should_panic(expected = "buf must hold one slot per range totaling its length")]
554 fn test_validate_read_ranges_rejects_length_overflow() {
555 let _ = validate_read_ranges(
556 usize::MAX,
557 [(0, usize::MAX), (u64::MAX, 1)].into_iter(),
558 u64::MAX,
559 );
560 }
561
562 #[test]
563 fn test_crc_record_encode_read_roundtrip() {
564 let record = Checksum {
565 len1: 0x1234,
566 crc1: 0xAABBCCDD,
567 len2: 0x5678,
568 crc2: 0x11223344,
569 };
570
571 let bytes = record.to_bytes();
572 let restored = Checksum::read(&mut Copying(&bytes)).unwrap();
573
574 assert_eq!(restored.len1, 0x1234);
575 assert_eq!(restored.crc1, 0xAABBCCDD);
576 assert_eq!(restored.len2, 0x5678);
577 assert_eq!(restored.crc2, 0x11223344);
578 }
579
580 #[test]
581 fn test_crc_record_encoding() {
582 let record = Checksum {
583 len1: 0x0102,
584 crc1: 0x03040506,
585 len2: 0x0708,
586 crc2: 0x090A0B0C,
587 };
588
589 let bytes = record.to_bytes();
590 assert_eq!(
592 bytes,
593 [
594 0x01, 0x02, 0x03, 0x04, 0x05, 0x06, 0x07, 0x08, 0x09, 0x0A, 0x0B, 0x0C
595 ]
596 );
597 }
598
599 #[test]
600 fn test_crc_record_authoritative_len1_larger() {
601 let record = Checksum {
602 len1: 200,
603 crc1: 0xAAAAAAAA,
604 len2: 100,
605 crc2: 0xBBBBBBBB,
606 };
607
608 assert_eq!(record.authoritative(), Slot::First);
609 }
610
611 #[test]
612 fn test_crc_record_authoritative_len2_larger() {
613 let record = Checksum {
614 len1: 100,
615 crc1: 0xAAAAAAAA,
616 len2: 200,
617 crc2: 0xBBBBBBBB,
618 };
619
620 assert_eq!(record.authoritative(), Slot::Second);
621 }
622
623 #[test]
624 fn test_crc_record_authoritative_equal_lengths() {
625 let record = Checksum {
627 len1: 100,
628 crc1: 0xAAAAAAAA,
629 len2: 100,
630 crc2: 0xBBBBBBBB,
631 };
632
633 assert_eq!(record.authoritative(), Slot::First);
634 }
635
636 #[test]
637 fn test_validate_page_valid() {
638 let page_size = 64usize;
639 let physical_page_size = page_size + Checksum::SIZE;
640 let mut page = vec![0u8; physical_page_size];
641
642 let data = b"hello world";
644 page[..data.len()].copy_from_slice(data);
645
646 let crc = Crc32::checksum(&page[..data.len()]);
648 let record = Checksum::new(data.len() as u16, crc);
649
650 let crc_start = physical_page_size - Checksum::SIZE;
652 page[crc_start..].copy_from_slice(&record.to_bytes());
653
654 let validated = Checksum::validate_page(&page);
656 assert!(validated.is_some());
657 assert_eq!(validated.unwrap().len as usize, data.len());
658 }
659
660 #[test]
661 fn test_validate_page_invalid_crc() {
662 let page_size = 64usize;
663 let physical_page_size = page_size + Checksum::SIZE;
664 let mut page = vec![0u8; physical_page_size];
665
666 let data = b"hello world";
668 page[..data.len()].copy_from_slice(data);
669
670 let wrong_crc = 0xBADBADBA;
672 let record = Checksum::new(data.len() as u16, wrong_crc);
673
674 let crc_start = physical_page_size - Checksum::SIZE;
675 page[crc_start..].copy_from_slice(&record.to_bytes());
676
677 let validated = Checksum::validate_page(&page);
679 assert!(validated.is_none());
680 }
681
682 #[test]
683 fn test_validate_page_corrupted_data() {
684 let page_size = 64usize;
685 let physical_page_size = page_size + Checksum::SIZE;
686 let mut page = vec![0u8; physical_page_size];
687
688 let data = b"hello world";
690 page[..data.len()].copy_from_slice(data);
691 let crc = Crc32::checksum(&page[..data.len()]);
692 let record = Checksum::new(data.len() as u16, crc);
693
694 let crc_start = physical_page_size - Checksum::SIZE;
695 page[crc_start..].copy_from_slice(&record.to_bytes());
696
697 page[0] = 0xFF;
699
700 let validated = Checksum::validate_page(&page);
702 assert!(validated.is_none());
703 }
704
705 #[test]
706 fn test_validate_page_uses_larger_len() {
707 let page_size = 64usize;
708 let physical_page_size = page_size + Checksum::SIZE;
709 let mut page = vec![0u8; physical_page_size];
710
711 let data = b"hello world, this is longer";
713 page[..data.len()].copy_from_slice(data);
714 let crc = Crc32::checksum(&page[..data.len()]);
715
716 let record = Checksum {
718 len1: 5,
719 crc1: 0xDEADBEEF, len2: data.len() as u16,
721 crc2: crc,
722 };
723
724 let crc_start = physical_page_size - Checksum::SIZE;
725 page[crc_start..].copy_from_slice(&record.to_bytes());
726
727 let validated = Checksum::validate_page(&page);
729 assert!(validated.is_some());
730 assert_eq!(validated.unwrap().len as usize, data.len());
731 }
732
733 #[test]
734 fn test_validate_page_uses_fallback() {
735 let page_size = 64usize;
736 let physical_page_size = page_size + Checksum::SIZE;
737 let mut page = vec![0u8; physical_page_size];
738
739 let data = b"fallback data";
741 page[..data.len()].copy_from_slice(data);
742 let valid_crc = Crc32::checksum(&page[..data.len()]);
743 let valid_len = data.len() as u16;
744
745 let record = Checksum {
749 len1: valid_len + 10, crc1: 0xBAD1DEA, len2: valid_len, crc2: valid_crc, };
754
755 let crc_start = physical_page_size - Checksum::SIZE;
756 page[crc_start..].copy_from_slice(&record.to_bytes());
757
758 let validated = Checksum::validate_page(&page);
760
761 assert!(validated.is_some(), "Should have validated using fallback");
762 let validated = validated.unwrap();
763 assert_eq!(
764 validated,
765 ActiveChecksum::new(Slot::Second, valid_len, valid_crc)
766 );
767 }
768
769 #[test]
770 fn test_validate_page_no_fallback_available() {
771 let page_size = 64usize;
772 let physical_page_size = page_size + Checksum::SIZE;
773 let mut page = vec![0u8; physical_page_size];
774
775 let data = b"some data";
777 page[..data.len()].copy_from_slice(data);
778
779 let record = Checksum {
783 len1: data.len() as u16,
784 crc1: 0xBAD1DEA, len2: 0, crc2: 0,
787 };
788
789 let crc_start = physical_page_size - Checksum::SIZE;
790 page[crc_start..].copy_from_slice(&record.to_bytes());
791
792 let validated = Checksum::validate_page(&page);
794 assert!(
795 validated.is_none(),
796 "Should fail when primary is invalid and fallback has len=0"
797 );
798 }
799
800 #[cfg(feature = "arbitrary")]
801 mod conformance {
802 use super::*;
803 use commonware_codec::conformance::CodecConformance;
804
805 commonware_conformance::conformance_tests! {
806 CodecConformance<Checksum>,
807 }
808 }
809}