ic-storage 0.3.0

Page-based stable-memory B-tree storage for Internet Computer applications
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95

use super::{Error, SIZE, checksum, number, seal, verify};

#[test]
fn checksum_preserves_persisted_fnv1a_bytes() {
    let mut state = 0x6a09_e667_f3bc_c909u64;
    for pattern in 0..66 {
        let mut page = [0; SIZE];
        for byte in &mut page {
            state ^= state << 13;
            state ^= state >> 7;
            state ^= state << 17;
            *byte = match pattern {
                0 => 0,
                1 => 255,
                _ => state.to_le_bytes()[0],
            };
        }
        // The original persisted algorithm, independently of chunk boundaries.
        let expected = page[..SIZE - 8]
            .iter()
            .fold(0xcbf2_9ce4_8422_2325u64, |hash, byte| {
                (hash ^ u64::from(*byte)).wrapping_mul(0x100_0000_01b3)
            });
        assert_eq!(checksum(&page), expected);
        seal(&mut page);
        assert_eq!(number(&page, SIZE - 8), expected);
        assert_eq!(verify(&page), Ok(()));
    }
}

#[test]
fn checksum_detects_corruption_at_every_page_byte() {
    let mut page = [0x5a; SIZE];
    seal(&mut page);
    for at in 0..SIZE {
        page[at] ^= 1;
        assert_eq!(verify(&page), Err(Error::Corrupt), "byte {at}");
        page[at] ^= 1;
    }
    assert_eq!(verify(&page), Ok(()));
}

#[test]
fn free_pages_preserve_bytes_and_validate_padding() {
    for next in (0..64)
        .flat_map(|bit| [1u64 << bit, !(1u64 << bit)])
        .chain([0, u64::MAX])
    {
        let mut expected = [0; SIZE];
        expected[0] = super::FREE;
        super::put(&mut expected, 8, next);
        seal(&mut expected);
        let actual = super::free(next);
        assert_eq!(*actual, expected, "free-list successor {next}");
        assert_eq!(verify(&actual), Ok(()));
    }
    let mut page = super::free(42);
    for at in 0..SIZE {
        page[at] ^= 1;
        assert_eq!(verify(&page), Err(Error::Corrupt), "free-page byte {at}");
        page[at] ^= 1;
    }
}

#[test]
fn zero_suffix_checksum_matches_original_at_every_boundary() {
    let mut page = [0; SIZE];
    for at in 0..SIZE - 8 {
        page[at] = 0xa5;
        let expected = page[..SIZE - 8]
            .iter()
            .fold(0xcbf2_9ce4_8422_2325u64, |hash, byte| {
                (hash ^ u64::from(*byte)).wrapping_mul(0x100_0000_01b3)
            });
        assert_eq!(checksum(&page), expected, "last nonzero byte {at}");
        page[at] = 0;
    }
}

#[test]
fn heap_blob_encoding_preserves_every_page_byte() {
    for len in 0..=super::PAYLOAD {
        for next in [0, 1, u64::MAX] {
            let payload = (0..len).map(|at| at.to_le_bytes()[0]).collect::<Vec<_>>();
            let mut expected = [0; SIZE];
            expected[0] = super::BLOB;
            super::put(&mut expected, 8, next);
            expected[16..16 + len].copy_from_slice(&payload);
            seal(&mut expected);
            let actual = super::encode_blob(next, &payload);
            assert_eq!(*actual, expected);
            assert_eq!(verify(&actual), Ok(()));
        }
    }
}