oasis_core_runtime/storage/mkvs/tree/
node.rs

1use std::{cell::RefCell, rc::Rc};
2
3use crate::{
4    common::{crypto::hash::Hash, namespace::Namespace},
5    storage::mkvs::{
6        cache::{CacheExtra, CacheItem},
7        marshal::Marshal,
8    },
9};
10
11/// Common interface for node-like objects in the tree.
12pub trait Node {
13    /// Check whether the node is clean or not.
14    fn is_clean(&self) -> bool;
15    /// Get the node's hash.
16    fn get_hash(&self) -> Hash;
17    /// Recompute the node's hash.
18    fn update_hash(&mut self);
19    /// Duplicate the node but include only hash references.
20    #[allow(dead_code)]
21    fn extract(&self) -> NodeRef;
22}
23
24/// Storage root type.
25#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash, cbor::Encode, cbor::Decode)]
26#[repr(u8)]
27pub enum RootType {
28    /// Invalid or uninitialized storage root type.
29    #[default]
30    Invalid = 0,
31    /// Storage root for runtime state.
32    State = 1,
33    /// Storage root for transaction IO.
34    IO = 2,
35}
36
37/// Storage root.
38#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, cbor::Encode, cbor::Decode)]
39pub struct Root {
40    /// Namespace under which the root is stored.
41    #[cbor(rename = "ns")]
42    pub namespace: Namespace,
43    /// Monotonically increasing version number in which the root is stored.
44    pub version: u64,
45    /// The storage type that this root has data for.
46    pub root_type: RootType,
47    /// Merkle root hash.
48    pub hash: Hash,
49}
50
51/// A box type that can contain either internal or leaf nodes.
52#[derive(Debug, Eq, PartialEq)]
53pub enum NodeBox {
54    Internal(InternalNode),
55    Leaf(LeafNode),
56}
57
58impl Default for NodeBox {
59    fn default() -> Self {
60        NodeBox::Internal(Default::default())
61    }
62}
63
64impl Node for NodeBox {
65    fn is_clean(&self) -> bool {
66        match self {
67            NodeBox::Internal(ref n) => n.is_clean(),
68            NodeBox::Leaf(ref n) => n.is_clean(),
69        }
70    }
71
72    fn get_hash(&self) -> Hash {
73        match self {
74            NodeBox::Internal(ref n) => n.get_hash(),
75            NodeBox::Leaf(ref n) => n.get_hash(),
76        }
77    }
78
79    fn update_hash(&mut self) {
80        match self {
81            NodeBox::Internal(ref mut n) => n.update_hash(),
82            NodeBox::Leaf(ref mut n) => n.update_hash(),
83        }
84    }
85
86    fn extract(&self) -> NodeRef {
87        match self {
88            NodeBox::Internal(ref n) => n.extract(),
89            NodeBox::Leaf(ref n) => n.extract(),
90        }
91    }
92}
93
94/// Node types in the tree.
95///
96/// Integer values of the variants here are also used in subtree
97/// serialization and as prefixes in node hash computations.
98#[derive(Copy, Clone, Debug)]
99#[repr(u8)]
100pub enum NodeKind {
101    None = 0x02,
102    Internal = 0x01,
103    Leaf = 0x00,
104}
105
106/// `NodeRef` is a reference-counted pointer to a node box.
107pub type NodeRef = Rc<RefCell<NodeBox>>;
108
109/// A pointer to a node in the tree.
110#[derive(Debug, Default)]
111pub struct NodePointer {
112    pub clean: bool,
113    pub hash: Hash,
114    pub node: Option<NodeRef>,
115
116    pub cache_extra: CacheExtra<NodePointer>,
117}
118
119/// A reference-counted pointer to a pointer.
120pub type NodePtrRef = Rc<RefCell<NodePointer>>;
121
122impl NodePointer {
123    /// Construct a null pointer.
124    pub fn null_ptr() -> NodePtrRef {
125        Rc::new(RefCell::new(NodePointer {
126            node: None,
127            clean: true,
128            hash: Hash::empty_hash(),
129            ..Default::default()
130        }))
131    }
132
133    /// Construct a hash-only pointer.
134    pub fn hash_ptr(hash: Hash) -> NodePtrRef {
135        Rc::new(RefCell::new(NodePointer {
136            node: None,
137            clean: true,
138            hash,
139            ..Default::default()
140        }))
141    }
142
143    /// Construct a node pointer from a full node.
144    pub fn from_node(node: NodeBox) -> NodePtrRef {
145        Rc::new(RefCell::new(NodePointer {
146            hash: node.get_hash(),
147            node: Some(Rc::new(RefCell::new(node))),
148            clean: true,
149            ..Default::default()
150        }))
151    }
152
153    /// Check if the pointer is a null pointer.
154    pub fn is_null(&self) -> bool {
155        self.hash.is_empty()
156    }
157
158    /// Check if the pointer has a resolved reference to a concrete node.
159    pub fn has_node(&self) -> bool {
160        !self.is_null() && self.node.is_some()
161    }
162
163    /// Get a reference to the node the pointer is pointing to.
164    pub fn get_node(&self) -> NodeRef {
165        match &self.node {
166            None => panic!("mkvs: get_node called on pointer without a node"),
167            Some(node) => node.clone(),
168        }
169    }
170
171    /// Return a copy of this pointer containing only hash references.
172    pub fn extract(&self) -> NodePtrRef {
173        assert!(self.clean, "mkvs: extract called on dirty pointer");
174
175        Rc::new(RefCell::new(NodePointer {
176            clean: true,
177            hash: self.hash,
178            ..Default::default()
179        }))
180    }
181
182    // Make deep copy of the Pointer to LeafNode excluding LRU and DBInternal.
183    //
184    // Panics, if it's called on non-leaf node pointer.
185    #[allow(dead_code)]
186    fn copy_leaf_ptr(&self) -> NodePtrRef {
187        if !self.has_node() {
188            return NodePointer::null_ptr();
189        }
190
191        assert!(self.clean, "mkvs: copy_leaf_ptr called on dirty pointer");
192
193        if let Some(ref some_node) = self.node {
194            let nyoo = noderef_as!(some_node, Leaf).copy();
195            Rc::new(RefCell::new(NodePointer {
196                clean: true,
197                hash: self.hash,
198                node: Some(Rc::new(RefCell::new(NodeBox::Leaf(nyoo)))),
199                ..Default::default()
200            }))
201        } else {
202            panic!("mkvs: copy_leaf_ptr called on a non-leaf pointer");
203        }
204    }
205}
206
207impl CacheItem for NodePointer {
208    fn get_cache_extra(&self) -> CacheExtra<NodePointer> {
209        self.cache_extra
210    }
211
212    fn set_cache_extra(&mut self, new_val: CacheExtra<NodePointer>) {
213        self.cache_extra = new_val;
214    }
215
216    fn get_cached_size(&self) -> usize {
217        1
218    }
219}
220
221impl PartialEq for NodePointer {
222    fn eq(&self, other: &NodePointer) -> bool {
223        if self.clean && other.clean {
224            self.hash == other.hash
225        } else {
226            self.node.is_some() && self.node == other.node
227        }
228    }
229}
230
231impl Eq for NodePointer {}
232
233/// An internal tree node with two children and possibly a leaf.
234#[derive(Debug, Default)]
235pub struct InternalNode {
236    pub clean: bool,
237    pub hash: Hash,
238    pub label: Key,              // label on the incoming edge
239    pub label_bit_length: Depth, // length of the label in bits
240    pub leaf_node: NodePtrRef,   // for the key ending at this depth
241    pub left: NodePtrRef,
242    pub right: NodePtrRef,
243}
244
245impl Node for InternalNode {
246    fn is_clean(&self) -> bool {
247        self.clean
248    }
249
250    fn get_hash(&self) -> Hash {
251        self.hash
252    }
253
254    fn update_hash(&mut self) {
255        let leaf_node_hash = self.leaf_node.borrow().hash;
256        let left_hash = self.left.borrow().hash;
257        let right_hash = self.right.borrow().hash;
258
259        self.hash = Hash::digest_bytes_list(&[
260            &[NodeKind::Internal as u8],
261            &self.label_bit_length.marshal_binary().unwrap(),
262            self.label.as_ref(),
263            leaf_node_hash.as_ref(),
264            left_hash.as_ref(),
265            right_hash.as_ref(),
266        ]);
267    }
268
269    fn extract(&self) -> NodeRef {
270        assert!(self.clean, "mkvs: extract called on dirty node");
271
272        Rc::new(RefCell::new(NodeBox::Internal(InternalNode {
273            clean: true,
274            hash: self.hash,
275            label: self.label.clone(),
276            label_bit_length: self.label_bit_length,
277            leaf_node: self.leaf_node.borrow().copy_leaf_ptr(),
278            left: self.left.borrow().extract(),
279            right: self.right.borrow().extract(),
280        })))
281    }
282}
283
284impl PartialEq for InternalNode {
285    fn eq(&self, other: &InternalNode) -> bool {
286        if self.clean && other.clean {
287            self.hash == other.hash
288        } else {
289            self.leaf_node == other.leaf_node
290                && self.left == other.left
291                && self.right == other.right
292        }
293    }
294}
295
296impl Eq for InternalNode {}
297
298/// A leaf node containing a key/value pair.
299#[derive(Debug, Default)]
300pub struct LeafNode {
301    pub clean: bool,
302    pub hash: Hash,
303    pub key: Key,
304    pub value: Value,
305}
306
307impl LeafNode {
308    pub fn copy(&self) -> LeafNode {
309        LeafNode {
310            clean: self.clean,
311            hash: self.hash,
312            key: self.key.to_owned(),
313            value: self.value.clone(),
314        }
315    }
316}
317
318impl Node for LeafNode {
319    fn is_clean(&self) -> bool {
320        self.clean
321    }
322
323    fn get_hash(&self) -> Hash {
324        self.hash
325    }
326
327    fn update_hash(&mut self) {
328        self.hash = Hash::digest_bytes_list(&[
329            &[NodeKind::Leaf as u8],
330            &(self.key.len() as u32).marshal_binary().unwrap(),
331            self.key.as_ref(),
332            &(self.value.len() as u32).marshal_binary().unwrap(),
333            self.value.as_ref(),
334        ]);
335    }
336
337    fn extract(&self) -> NodeRef {
338        assert!(self.clean, "mkvs: extract called on dirty node");
339        Rc::new(RefCell::new(NodeBox::Leaf(LeafNode {
340            clean: true,
341            hash: self.hash,
342            key: self.key.clone(),
343            value: self.value.clone(),
344        })))
345    }
346}
347
348impl PartialEq for LeafNode {
349    fn eq(&self, other: &LeafNode) -> bool {
350        if self.clean && other.clean {
351            self.hash == other.hash
352        } else {
353            self.key == other.key && self.value == other.value
354        }
355    }
356}
357
358impl Eq for LeafNode {}
359
360// Depth determines the maximum length of the key in bits.
361//
362// max length = 2^size_of(Depth)*8
363pub type Depth = u16;
364
365pub trait DepthTrait {
366    // Returns the number of bytes needed to fit given bits.
367    fn to_bytes(&self) -> usize;
368}
369
370impl DepthTrait for Depth {
371    fn to_bytes(&self) -> usize {
372        let size = self / 8;
373        if !self.is_multiple_of(8) {
374            (size + 1) as usize
375        } else {
376            size as usize
377        }
378    }
379}
380
381// Key holds variable-length key.
382pub type Key = Vec<u8>;
383
384pub trait KeyTrait {
385    /// Get a single bit from the given hash.
386    fn get_bit(&self, bit: Depth) -> bool;
387    /// Returns the length of the key in bits.
388    fn bit_length(&self) -> Depth;
389    /// Bit-wise splits of the key.
390    fn split(&self, split_point: Depth, key_len: Depth) -> (Key, Key);
391    /// Bit-wise merges key of given length with another key of given length.
392    fn merge(&self, key_len: Depth, k2: &Key, k2_len: Depth) -> Key;
393    /// Appends the given bit to the key.
394    fn append_bit(&self, key_len: Depth, bit: bool) -> Key;
395    /// Computes length of common prefix of k and k2 with given bit lengths.
396    fn common_prefix_len(&self, key_len: Depth, k2: &Key, k2_len: Depth) -> Depth;
397}
398
399impl KeyTrait for Key {
400    fn get_bit(&self, bit: Depth) -> bool {
401        (self[(bit / 8) as usize] & (1 << (7 - (bit % 8)))) != 0
402    }
403
404    fn bit_length(&self) -> Depth {
405        (self.len() * 8) as Depth
406    }
407
408    fn split(&self, split_point: Depth, key_len: Depth) -> (Key, Key) {
409        assert!(
410            split_point <= key_len,
411            "mkvs: split_point {} greater than key_len {}",
412            split_point,
413            key_len
414        );
415
416        let prefix_len = split_point.to_bytes();
417        let suffix_len = (key_len - split_point).to_bytes();
418        let mut prefix: Key = vec![0; prefix_len];
419        let mut suffix: Key = vec![0; suffix_len];
420
421        prefix.clone_from_slice(&self[0..split_point.to_bytes()]);
422
423        // Clean the remainder of the byte.
424        if !split_point.is_multiple_of(8) {
425            prefix[prefix_len - 1] &= 0xff << (8 - split_point % 8)
426        }
427
428        for i in 0..suffix_len {
429            // First set the left chunk of the byte
430            suffix[i] = self[i + split_point as usize / 8] << (split_point % 8);
431            // ...and the right chunk, if we haven't reached the end of k yet.
432            if !split_point.is_multiple_of(8) && i + split_point as usize / 8 + 1 != self.len() {
433                suffix[i] |=
434                    self[i + split_point as usize / 8 + 1] >> (8 - split_point as usize % 8);
435            }
436        }
437
438        (prefix, suffix)
439    }
440
441    fn merge(&self, key_len: Depth, k2: &Key, k2_len: Depth) -> Key {
442        let mut key_len_bytes = (key_len as usize) / 8;
443        if !key_len.is_multiple_of(8) {
444            key_len_bytes += 1;
445        }
446
447        let mut new_key: Key = vec![0; (key_len + k2_len).to_bytes()];
448        new_key[..key_len_bytes].clone_from_slice(&self[..key_len_bytes]);
449
450        for i in 0..k2.len() {
451            // First set the right chunk of the previous byte
452            if !key_len.is_multiple_of(8) && key_len_bytes > 0 {
453                new_key[key_len_bytes + i - 1] |= k2[i] >> (key_len % 8);
454            }
455            // ...and the next left chunk, if we haven't reached the end of newKey
456            // yet.
457            if key_len_bytes + i < new_key.len() {
458                // another mod 8 to prevent bit shifting for 8 bits
459                new_key[key_len_bytes + i] |= k2[i] << ((8 - key_len % 8) % 8);
460            }
461        }
462
463        new_key
464    }
465
466    fn append_bit(&self, key_len: Depth, val: bool) -> Key {
467        let mut new_key: Key = vec![0; (key_len + 1).to_bytes()];
468        new_key[..self.len()].clone_from_slice(self);
469
470        if val {
471            new_key[key_len as usize / 8] |= 0x80 >> (key_len % 8)
472        } else {
473            new_key[key_len as usize / 8] &= !(0x80 >> (key_len % 8))
474        }
475
476        new_key
477    }
478
479    fn common_prefix_len(&self, key_bit_len: Depth, k2: &Key, k2_bit_len: Depth) -> Depth {
480        let min_key_len = if k2.len() < self.len() {
481            k2.len()
482        } else {
483            self.len()
484        };
485
486        // Compute the common prefix byte-wise.
487        let mut i: usize = 0;
488        while i < min_key_len {
489            if self[i] != k2[i] {
490                break;
491            }
492            i += 1;
493        }
494
495        // Prefixes match i bytes and maybe some more bits below.
496        let mut bit_length = (i * 8) as Depth;
497
498        if i != self.len() && i != k2.len() {
499            // We got a mismatch somewhere along the way. We need to compute how
500            // many additional bits in i-th byte match.
501            bit_length += (self[i] ^ k2[i]).leading_zeros() as Depth;
502        }
503
504        // In any case, bit_length should never exceed length of the shorter key.
505        if bit_length > key_bit_len {
506            bit_length = key_bit_len;
507        }
508        if bit_length > k2_bit_len {
509            bit_length = k2_bit_len;
510        };
511        bit_length
512    }
513}
514
515// Value holds the leaf node value.
516pub type Value = Vec<u8>;
oasis_core_runtime/storage/mkvs/tree/node.rs

oasis_core_runtime/storage/mkvs/tree/
node.rs
