tp_state_machine/changes_trie/
prune.rs

1// This file is part of Tetcore.
2
3// Copyright (C) 2017-2021 Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! Changes trie pruning-related functions.
19
20use tetsy_hash_db::Hasher;
21use tp_trie::Recorder;
22use log::warn;
23use num_traits::One;
24use crate::proving_backend::ProvingBackendRecorder;
25use crate::trie_backend_essence::TrieBackendEssence;
26use crate::changes_trie::{AnchorBlockId, Storage, BlockNumber};
27use crate::changes_trie::storage::TrieBackendAdapter;
28use crate::changes_trie::input::{ChildIndex, InputKey};
29use codec::{Decode, Codec};
30
31/// Prune obsolete changes tries. Pruning happens at the same block, where highest
32/// level digest is created. Pruning guarantees to save changes tries for last
33/// `min_blocks_to_keep` blocks. We only prune changes tries at `max_digest_interval`
34/// ranges.
35pub fn prune<H: Hasher, Number: BlockNumber, F: FnMut(H::Out)>(
36	storage: &dyn Storage<H, Number>,
37	first: Number,
38	last: Number,
39	current_block: &AnchorBlockId<H::Out, Number>,
40	mut remove_trie_node: F,
41) where H::Out: Codec {
42	// delete changes trie for every block in range
43	let mut block = first;
44	loop {
45		if block >= last.clone() + One::one() {
46			break;
47		}
48
49		let prev_block = block.clone();
50		block += One::one();
51
52		let block = prev_block;
53		let root = match storage.root(current_block, block.clone()) {
54			Ok(Some(root)) => root,
55			Ok(None) => continue,
56			Err(error) => {
57				// try to delete other tries
58				warn!(target: "trie", "Failed to read changes trie root from DB: {}", error);
59				continue;
60			},
61		};
62		let children_roots = {
63			let trie_storage = TrieBackendEssence::<_, H>::new(
64				crate::changes_trie::TrieBackendStorageAdapter(storage),
65				root,
66			);
67			let child_prefix = ChildIndex::key_neutral_prefix(block.clone());
68			let mut children_roots = Vec::new();
69			trie_storage.for_key_values_with_prefix(&child_prefix, |key, value| {
70				if let Ok(InputKey::ChildIndex::<Number>(_trie_key)) = Decode::decode(&mut &key[..]) {
71					if let Ok(value) = <Vec<u8>>::decode(&mut &value[..]) {
72						let mut trie_root = <H as Hasher>::Out::default();
73						trie_root.as_mut().copy_from_slice(&value[..]);
74						children_roots.push(trie_root);
75					}
76				}
77			});
78
79			children_roots
80		};
81		for root in children_roots.into_iter() {
82			prune_trie(storage, root, &mut remove_trie_node);
83		}
84
85		prune_trie(storage, root, &mut remove_trie_node);
86	}
87}
88
89// Prune a trie.
90fn prune_trie<H: Hasher, Number: BlockNumber, F: FnMut(H::Out)>(
91	storage: &dyn Storage<H, Number>,
92	root: H::Out,
93	remove_trie_node: &mut F,
94) where H::Out: Codec {
95
96	// enumerate all changes trie' keys, recording all nodes that have been 'touched'
97	// (effectively - all changes trie nodes)
98	let mut proof_recorder: Recorder<H::Out> = Default::default();
99	{
100		let mut trie = ProvingBackendRecorder::<_, H> {
101			backend: &TrieBackendEssence::new(TrieBackendAdapter::new(storage), root),
102			proof_recorder: &mut proof_recorder,
103		};
104		trie.record_all_keys();
105	}
106
107	// all nodes of this changes trie should be pruned
108	remove_trie_node(root);
109	for node in proof_recorder.drain().into_iter().map(|n| n.hash) {
110		remove_trie_node(node);
111	}
112}
113
114#[cfg(test)]
115mod tests {
116	use std::collections::HashSet;
117	use tp_trie::MemoryDB;
118	use tet_core::H256;
119	use crate::backend::insert_into_memory_db;
120	use crate::changes_trie::storage::InMemoryStorage;
121	use codec::Encode;
122	use tp_runtime::traits::BlakeTwo256;
123	use super::*;
124
125	fn prune_by_collect(
126		storage: &dyn Storage<BlakeTwo256, u64>,
127		first: u64,
128		last: u64,
129		current_block: u64,
130	) -> HashSet<H256> {
131		let mut pruned_trie_nodes = HashSet::new();
132		let anchor = AnchorBlockId { hash: Default::default(), number: current_block };
133		prune(storage, first, last, &anchor,
134			|node| { pruned_trie_nodes.insert(node); });
135		pruned_trie_nodes
136	}
137
138	#[test]
139	fn prune_works() {
140		fn prepare_storage() -> InMemoryStorage<BlakeTwo256, u64> {
141			let child_info = tet_core::storage::ChildInfo::new_default(&b"1"[..]);
142			let child_key = ChildIndex { block: 67u64, storage_key: child_info.prefixed_storage_key() }.encode();
143			let mut mdb1 = MemoryDB::<BlakeTwo256>::default();
144			let root1 = insert_into_memory_db::<BlakeTwo256, _>(
145				&mut mdb1, vec![(vec![10], vec![20])]).unwrap();
146			let mut mdb2 = MemoryDB::<BlakeTwo256>::default();
147			let root2 = insert_into_memory_db::<BlakeTwo256, _>(
148				&mut mdb2,
149				vec![(vec![11], vec![21]), (vec![12], vec![22])],
150			).unwrap();
151			let mut mdb3 = MemoryDB::<BlakeTwo256>::default();
152			let ch_root3 = insert_into_memory_db::<BlakeTwo256, _>(
153				&mut mdb3, vec![(vec![110], vec![120])]).unwrap();
154			let root3 = insert_into_memory_db::<BlakeTwo256, _>(&mut mdb3, vec![
155				(vec![13], vec![23]),
156				(vec![14], vec![24]),
157				(child_key, ch_root3.as_ref().encode()),
158			]).unwrap();
159			let mut mdb4 = MemoryDB::<BlakeTwo256>::default();
160			let root4 = insert_into_memory_db::<BlakeTwo256, _>(
161				&mut mdb4,
162				vec![(vec![15], vec![25])],
163			).unwrap();
164			let storage = InMemoryStorage::new();
165			storage.insert(65, root1, mdb1);
166			storage.insert(66, root2, mdb2);
167			storage.insert(67, root3, mdb3);
168			storage.insert(68, root4, mdb4);
169
170			storage
171		}
172
173		let storage = prepare_storage();
174		assert!(prune_by_collect(&storage, 20, 30, 90).is_empty());
175		assert!(!storage.into_mdb().drain().is_empty());
176
177		let storage = prepare_storage();
178		let prune60_65 = prune_by_collect(&storage, 60, 65, 90);
179		assert!(!prune60_65.is_empty());
180		storage.remove_from_storage(&prune60_65);
181		assert!(!storage.into_mdb().drain().is_empty());
182
183		let storage = prepare_storage();
184		let prune60_70 = prune_by_collect(&storage, 60, 70, 90);
185		assert!(!prune60_70.is_empty());
186		storage.remove_from_storage(&prune60_70);
187		assert!(storage.into_mdb().drain().is_empty());
188	}
189}
tp_state_machine/changes_trie/prune.rs

tp_state_machine/changes_trie/
prune.rs
