cfx_storage/storage_db/
snapshot_mpt.rs

1// Copyright 2019 Conflux Foundation. All rights reserved.
2// Conflux is free software and distributed under GNU General Public License.
3// See http://www.gnu.org/licenses/
4
5use cfg_if::cfg_if;
6cfg_if! {
7    if #[cfg(test)] {
8        pub const CHECK_LOADED_SNAPSHOT_MPT_NODE: bool = true;
9    } else {
10        pub const CHECK_LOADED_SNAPSHOT_MPT_NODE: bool = false;
11    }
12}
13
14pub type SnapshotMptDbValue = Box<[u8]>;
15/// We use `VanillaTrieNode<(MerkleHash, i64)>` instead of
16/// `(VanillaTrieNode<MerkleHash>, i64)` to make seeking by rlp size position
17/// faster.
18#[derive(Clone, Default, Debug)]
19pub struct SnapshotMptNode(pub VanillaTrieNode<SubtreeMerkleWithSize>);
20
21#[derive(Copy, Clone, PartialEq, Debug, Default)]
22pub struct SubtreeMerkleWithSize {
23    pub merkle: MerkleHash,
24    pub subtree_size: u64,
25    // FIXME: delta_subtree_size should be cleared for skipped subtree during
26    // FIXME: merge. It's non trivial for in-place update mode, for which we
27    // FIXME: need a special subtree mark to be also taken into consideration
28    // FIXME: while seeking.
29    pub delta_subtree_size: u64,
30}
31
32// TODO: The key for SnapshotMpt should be changed to something else because
33// TODO: we'd like to use a multi-version snapshot db to manage multiple
34// TODO: snapshots.
35pub trait SnapshotMptTraitRead: AsSnapshotMptTraitRead {
36    fn get_merkle_root(&self) -> MerkleHash;
37    fn load_node(
38        &mut self, path: &dyn CompressedPathTrait,
39    ) -> Result<Option<SnapshotMptNode>>;
40}
41
42pub trait AsSnapshotMptTraitRead {
43    fn as_readonly(&mut self) -> &mut dyn SnapshotMptTraitRead;
44}
45
46impl<T: SnapshotMptTraitRead> AsSnapshotMptTraitRead for T {
47    fn as_readonly(&mut self) -> &mut dyn SnapshotMptTraitRead { self }
48}
49
50pub trait SnapshotMptTraitReadAndIterate: SnapshotMptTraitRead {
51    fn iterate_subtree_trie_nodes_without_root(
52        &mut self, path: &dyn CompressedPathTrait,
53    ) -> Result<Box<dyn SnapshotMptIteraterTrait + '_>>;
54}
55
56pub trait SnapshotMptTraitRw: SnapshotMptTraitReadAndIterate {
57    fn delete_node(&mut self, path: &dyn CompressedPathTrait) -> Result<()>;
58    fn write_node(
59        &mut self, path: &dyn CompressedPathTrait, trie_node: &SnapshotMptNode,
60    ) -> Result<()>;
61}
62
63// TODO: A snapshot mpt iterator is suitable to work as base_mpt in MptMerger's
64// TODO: save-as mode, because MptMerger always access nodes in snapshot mpt in
65// TODO: increasing order. we need to make special generalization for MptMerger
66// TODO: to take SnapshotMptIteraterTrait as input.
67pub trait SnapshotMptIteraterTrait:
68    FallibleIterator<Item = (CompressedPathRaw, SnapshotMptNode), Error = Error>
69{
70}
71
72impl<
73        T: FallibleIterator<
74            Item = (CompressedPathRaw, SnapshotMptNode),
75            Error = Error,
76        >,
77    > SnapshotMptIteraterTrait for T
78{
79}
80
81impl SnapshotMptNode {
82    pub const NO_CHILD: SubtreeMerkleWithSize = SubtreeMerkleWithSize {
83        merkle: MERKLE_NULL_NODE,
84        subtree_size: 0,
85        delta_subtree_size: 0,
86    };
87
88    pub fn is_valid(&self, path_to_node: &dyn CompressedPathTrait) -> bool {
89        let mut valid = true;
90
91        let children_merkles = self.get_children_merkles();
92        let merkle_hash = self.compute_merkle(
93            children_merkles.as_ref(),
94            CompressedPathRaw::second_nibble(
95                self.compressed_path_ref().path_mask(),
96            ) != CompressedPathRaw::NO_MISSING_NIBBLE,
97        );
98        if self.get_merkle().ne(&merkle_hash) {
99            error!(
100                "merkle hash mismatch, expected {:?}, got {:?}, path_to_node {:?}",
101                merkle_hash, self.get_merkle(), path_to_node,
102            );
103            valid = false;
104        }
105        let actual_children_count = children_merkles.as_ref().map_or(0, |v| {
106            v.iter().filter(|&x| x.ne(&MERKLE_NULL_NODE)).count()
107        });
108        if self.get_children_count() as usize != actual_children_count {
109            error!(
110                "children count is wrong: expected {} got {}",
111                actual_children_count,
112                self.get_children_count(),
113            );
114            valid = false;
115        }
116        if path_to_node.path_size() > 0
117            && !self.has_value()
118            && self.get_children_count() <= 1
119        {
120            error!(
121                "node should not exists due to path compressing rule, path_to_node {:?}, {:?}",
122                path_to_node, self
123            );
124            valid = false
125        }
126
127        valid
128    }
129
130    pub fn load_rlp_and_check(
131        rlp_bytes: &[u8], path_to_node: &dyn CompressedPathTrait,
132    ) -> Result<Self> {
133        let node = Self(Rlp::new(rlp_bytes).as_val()?);
134
135        if CHECK_LOADED_SNAPSHOT_MPT_NODE {
136            node.is_valid(path_to_node);
137        }
138        Ok(node)
139    }
140
141    pub fn subtree_size(&self, full_path: &dyn CompressedPathTrait) -> u64 {
142        Self::initial_subtree_size(&self.0, full_path)
143    }
144
145    fn initial_subtree_size(
146        node: &VanillaTrieNode<SubtreeMerkleWithSize>,
147        full_path: &dyn CompressedPathTrait,
148    ) -> u64 {
149        let mut size = match node.value_as_slice().into_option() {
150            None => 0,
151            Some(value) => {
152                rlp_key_value_len(full_path.path_size(), value.len())
153            }
154        };
155        for (
156            _child_index,
157            &SubtreeMerkleWithSize {
158                ref subtree_size, ..
159            },
160        ) in node.get_children_table_ref().iter()
161        {
162            size += subtree_size;
163        }
164
165        size
166    }
167
168    pub fn get_children_merkles(&self) -> MaybeMerkleTable {
169        if self.get_children_count() > 0 {
170            let mut merkle_table = Some(
171                [ChildrenTableItem::<MerkleHash>::no_child().clone();
172                    CHILDREN_COUNT],
173            );
174            for (child_index, &SubtreeMerkleWithSize { ref merkle, .. }) in
175                self.get_children_table_ref().iter()
176            {
177                merkle_table.as_mut().unwrap()[child_index as usize] = *merkle;
178            }
179            merkle_table
180        } else {
181            None
182        }
183    }
184
185    pub fn get_merkle_hash_wo_compressed_path(&self) -> MerkleHash {
186        compute_node_merkle(
187            self.get_children_merkles().as_ref(),
188            self.0.value_as_slice().into_option(),
189        )
190    }
191}
192
193impl Decodable for SnapshotMptNode {
194    fn decode(rlp: &Rlp) -> std::result::Result<Self, DecoderError> {
195        Ok(Self(rlp.as_val()?))
196    }
197}
198
199impl Deref for SnapshotMptNode {
200    type Target = VanillaTrieNode<SubtreeMerkleWithSize>;
201
202    fn deref(&self) -> &Self::Target { &self.0 }
203}
204
205impl DerefMut for SnapshotMptNode {
206    fn deref_mut(&mut self) -> &mut Self::Target { &mut self.0 }
207}
208
209impl Decodable for SubtreeMerkleWithSize {
210    fn decode(rlp: &Rlp) -> std::result::Result<Self, DecoderError> {
211        Ok(Self {
212            merkle: rlp.val_at(0)?,
213            subtree_size: rlp.val_at::<u64>(1)?,
214            delta_subtree_size: rlp.val_at::<u64>(2)?,
215        })
216    }
217}
218
219impl Encodable for SubtreeMerkleWithSize {
220    fn rlp_append(&self, s: &mut RlpStream) {
221        s.begin_list(3)
222            .append(&self.merkle)
223            .append(&self.subtree_size)
224            .append(&self.delta_subtree_size);
225    }
226}
227
228impl NodeRefTrait for SubtreeMerkleWithSize {}
229
230impl DefaultChildrenItem<SubtreeMerkleWithSize>
231    for ChildrenTableItem<SubtreeMerkleWithSize>
232{
233    fn no_child() -> &'static SubtreeMerkleWithSize {
234        &SnapshotMptNode::NO_CHILD
235    }
236}
237
238use super::super::impls::{
239    errors::*,
240    merkle_patricia_trie::{
241        merkle::{compute_node_merkle, MaybeMerkleTable},
242        mpt_cursor::rlp_key_value_len,
243        ChildrenTableItem, CompressedPathRaw, CompressedPathTrait,
244        DefaultChildrenItem, NodeRefTrait, TrieNodeTrait, VanillaTrieNode,
245        CHILDREN_COUNT,
246    },
247};
248use fallible_iterator::FallibleIterator;
249use primitives::{MerkleHash, MERKLE_NULL_NODE};
250use rlp::*;
251use std::ops::{Deref, DerefMut};
cfx_storage/storage_db/snapshot_mpt.rs

cfx_storage/storage_db/
snapshot_mpt.rs
