ic-storage 0.5.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
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112

//! Read-only structural audit of the persisted tree and free-list ownership.
use super::{
    BTreeMap, Comparator, Error, Memory,
    page::{self, DEGREE, MAX_HEIGHT, PAYLOAD},
};
use std::{cmp::Ordering, collections::BTreeSet};

struct Audit<'a, M, C> {
    tree: &'a BTreeMap<M, C>,
    seen: BTreeSet<u64>,
    previous: Option<Vec<u8>>,
    count: u64,
    leaf_depth: Option<usize>,
}

pub(super) fn validate<M: Memory, C: Comparator>(tree: &BTreeMap<M, C>) -> Result<(), Error> {
    let mut audit = Audit {
        tree,
        seen: BTreeSet::new(),
        previous: None,
        count: 0,
        leaf_depth: None,
    };
    audit.audit_node(tree.header.root, 0)?;
    if audit.count != tree.header.len {
        return Err(Error::Corrupt);
    }
    let mut free = tree.header.free;
    while free != 0 {
        if !audit.seen.insert(free) {
            return Err(Error::Corrupt);
        }
        let page = page::read(&tree.memory, tree.header.next, free)?;
        if page[0] != page::FREE {
            return Err(Error::Corrupt);
        }
        free = page::number(&page, 8);
    }
    if audit.seen.len() as u64 != tree.header.next - 1 {
        return Err(Error::Corrupt);
    }
    Ok(())
}

impl<M: Memory, C: Comparator> Audit<'_, M, C> {
    fn audit_node(&mut self, id: u64, depth: usize) -> Result<(), Error> {
        if depth >= MAX_HEIGHT || !self.seen.insert(id) {
            return Err(Error::Corrupt);
        }
        let node = self.tree.node(id)?;
        if depth > 0 && node.entries.len() < DEGREE - 1 {
            return Err(Error::Corrupt);
        }
        if node.entries.is_empty() && !node.children.is_empty() {
            return Err(Error::Corrupt);
        }
        if node.children.is_empty() {
            if self.leaf_depth.is_some_and(|expected| expected != depth) {
                return Err(Error::Corrupt);
            }
            self.leaf_depth = Some(depth);
        }
        for (i, record) in node.entries.iter().enumerate() {
            if !node.children.is_empty() {
                self.audit_node(node.children[i], depth + 1)?;
            }
            let key = if record.key == 0 {
                self.tree.key(*record)?
            } else {
                page::read_blob_with(record.key, record.key_len, |id, output| {
                    if !self.seen.insert(id) {
                        return Err(Error::Corrupt);
                    }
                    page::read_into(&self.tree.memory, self.tree.header.next, id, output)
                })?
            };
            self.audit_blob(record.value, record.value_len)?;
            self.tree.check_key(&key)?;
            if let Some(previous) = self.previous.as_ref()
                && self.tree.order.compare(previous, &key)? != Ordering::Less
            {
                return Err(Error::Corrupt);
            }
            self.previous = Some(key);
            self.count = self.count.checked_add(1).ok_or(Error::Corrupt)?;
        }
        if let Some(last) = node.children.last() {
            self.audit_node(*last, depth + 1)?;
        }
        Ok(())
    }
    fn audit_blob(&mut self, mut id: u64, mut len: u64) -> Result<(), Error> {
        if id == 0 {
            return Ok(());
        }
        while len != 0 {
            if !self.seen.insert(id) {
                return Err(Error::Corrupt);
            }
            let page = page::read(&self.tree.memory, self.tree.header.next, id)?;
            if page[0] != page::BLOB {
                return Err(Error::Corrupt);
            }
            id = page::number(&page, 8);
            len = len.saturating_sub(PAYLOAD as u64);
        }
        if id != 0 {
            return Err(Error::Corrupt);
        }
        Ok(())
    }
}