referrerpolicy=no-referrer-when-downgrade

sc_client_db/
lib.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0
5
6// This program is free software: you can redistribute it and/or modify
7// it under the terms of the GNU General Public License as published by
8// the Free Software Foundation, either version 3 of the License, or
9// (at your option) any later version.
10
11// This program is distributed in the hope that it will be useful,
12// but WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14// GNU General Public License for more details.
15
16// You should have received a copy of the GNU General Public License
17// along with this program. If not, see <https://www.gnu.org/licenses/>.
18
19//! Client backend that is backed by a database.
20//!
21//! # Canonicality vs. Finality
22//!
23//! Finality indicates that a block will not be reverted, according to the consensus algorithm,
24//! while canonicality indicates that the block may be reverted, but we will be unable to do so,
25//! having discarded heavy state that will allow a chain reorganization.
26//!
27//! Finality implies canonicality but not vice-versa.
28
29#![warn(missing_docs)]
30
31pub mod offchain;
32
33pub mod bench;
34
35mod children;
36mod parity_db;
37mod pinned_blocks_cache;
38mod record_stats_state;
39mod stats;
40#[cfg(any(feature = "rocksdb", test))]
41mod upgrade;
42mod utils;
43
44use linked_hash_map::LinkedHashMap;
45use log::{debug, trace, warn};
46use parking_lot::{Mutex, RwLock};
47use prometheus_endpoint::Registry;
48use std::{
49	collections::{HashMap, HashSet},
50	io,
51	path::{Path, PathBuf},
52	sync::Arc,
53};
54
55use crate::{
56	pinned_blocks_cache::PinnedBlocksCache,
57	record_stats_state::RecordStatsState,
58	stats::StateUsageStats,
59	utils::{meta_keys, read_db, read_meta, DatabaseType, Meta},
60};
61use codec::{Decode, Encode};
62use hash_db::Prefix;
63use sc_client_api::{
64	backend::NewBlockState,
65	blockchain::{BlockGap, BlockGapType},
66	leaves::{FinalizationOutcome, LeafSet},
67	utils::is_descendent_of,
68	IoInfo, MemoryInfo, MemorySize, TrieCacheContext, UsageInfo,
69};
70use sc_state_db::{IsPruned, LastCanonicalized, StateDb};
71use sp_arithmetic::traits::Saturating;
72use sp_blockchain::{
73	Backend as _, CachedHeaderMetadata, DisplacedLeavesAfterFinalization, Error as ClientError,
74	HeaderBackend, HeaderMetadata, HeaderMetadataCache, Result as ClientResult,
75};
76use sp_core::{
77	offchain::OffchainOverlayedChange,
78	storage::{well_known_keys, ChildInfo},
79};
80use sp_database::Transaction;
81use sp_runtime::{
82	generic::BlockId,
83	traits::{
84		Block as BlockT, Hash, HashingFor, Header as HeaderT, NumberFor, One, SaturatedConversion,
85		Zero,
86	},
87	Justification, Justifications, StateVersion, Storage,
88};
89use sp_state_machine::{
90	backend::{AsTrieBackend, Backend as StateBackend},
91	BackendTransaction, ChildStorageCollection, DBValue, IndexOperation, IterArgs,
92	OffchainChangesCollection, StateMachineStats, StorageCollection, StorageIterator, StorageKey,
93	StorageValue, UsageInfo as StateUsageInfo,
94};
95use sp_trie::{cache::SharedTrieCache, prefixed_key, MemoryDB, MerkleValue, PrefixedMemoryDB};
96use utils::BLOCK_GAP_CURRENT_VERSION;
97
98// Re-export the Database trait so that one can pass an implementation of it.
99pub use sc_state_db::PruningMode;
100pub use sp_database::Database;
101
102pub use bench::BenchmarkingState;
103
104const CACHE_HEADERS: usize = 8;
105
106/// DB-backed patricia trie state, transaction type is an overlay of changes to commit.
107pub type DbState<H> = sp_state_machine::TrieBackend<Arc<dyn sp_state_machine::Storage<H>>, H>;
108
109/// Builder for [`DbState`].
110pub type DbStateBuilder<Hasher> =
111	sp_state_machine::TrieBackendBuilder<Arc<dyn sp_state_machine::Storage<Hasher>>, Hasher>;
112
113/// Length of a [`DbHash`].
114const DB_HASH_LEN: usize = 32;
115
116/// Hash type that this backend uses for the database.
117pub type DbHash = sp_core::H256;
118
119/// An extrinsic entry in the database.
120#[derive(Debug, Encode, Decode)]
121enum DbExtrinsic<B: BlockT> {
122	/// Extrinsic that contains indexed data.
123	Indexed {
124		/// Hash of the indexed part.
125		hash: DbHash,
126		/// Extrinsic header.
127		header: Vec<u8>,
128	},
129	/// Complete extrinsic data.
130	Full(B::Extrinsic),
131}
132
133/// A reference tracking state.
134///
135/// It makes sure that the hash we are using stays pinned in storage
136/// until this structure is dropped.
137pub struct RefTrackingState<Block: BlockT> {
138	state: DbState<HashingFor<Block>>,
139	storage: Arc<StorageDb<Block>>,
140	parent_hash: Option<Block::Hash>,
141}
142
143impl<B: BlockT> RefTrackingState<B> {
144	fn new(
145		state: DbState<HashingFor<B>>,
146		storage: Arc<StorageDb<B>>,
147		parent_hash: Option<B::Hash>,
148	) -> Self {
149		RefTrackingState { state, parent_hash, storage }
150	}
151}
152
153impl<B: BlockT> Drop for RefTrackingState<B> {
154	fn drop(&mut self) {
155		if let Some(hash) = &self.parent_hash {
156			self.storage.state_db.unpin(hash);
157		}
158	}
159}
160
161impl<Block: BlockT> std::fmt::Debug for RefTrackingState<Block> {
162	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
163		write!(f, "Block {:?}", self.parent_hash)
164	}
165}
166
167/// A raw iterator over the `RefTrackingState`.
168pub struct RawIter<B: BlockT> {
169	inner: <DbState<HashingFor<B>> as StateBackend<HashingFor<B>>>::RawIter,
170}
171
172impl<B: BlockT> StorageIterator<HashingFor<B>> for RawIter<B> {
173	type Backend = RefTrackingState<B>;
174	type Error = <DbState<HashingFor<B>> as StateBackend<HashingFor<B>>>::Error;
175
176	fn next_key(&mut self, backend: &Self::Backend) -> Option<Result<StorageKey, Self::Error>> {
177		self.inner.next_key(&backend.state)
178	}
179
180	fn next_pair(
181		&mut self,
182		backend: &Self::Backend,
183	) -> Option<Result<(StorageKey, StorageValue), Self::Error>> {
184		self.inner.next_pair(&backend.state)
185	}
186
187	fn was_complete(&self) -> bool {
188		self.inner.was_complete()
189	}
190}
191
192impl<B: BlockT> StateBackend<HashingFor<B>> for RefTrackingState<B> {
193	type Error = <DbState<HashingFor<B>> as StateBackend<HashingFor<B>>>::Error;
194	type TrieBackendStorage =
195		<DbState<HashingFor<B>> as StateBackend<HashingFor<B>>>::TrieBackendStorage;
196	type RawIter = RawIter<B>;
197
198	fn storage(&self, key: &[u8]) -> Result<Option<Vec<u8>>, Self::Error> {
199		self.state.storage(key)
200	}
201
202	fn storage_hash(&self, key: &[u8]) -> Result<Option<B::Hash>, Self::Error> {
203		self.state.storage_hash(key)
204	}
205
206	fn child_storage(
207		&self,
208		child_info: &ChildInfo,
209		key: &[u8],
210	) -> Result<Option<Vec<u8>>, Self::Error> {
211		self.state.child_storage(child_info, key)
212	}
213
214	fn child_storage_hash(
215		&self,
216		child_info: &ChildInfo,
217		key: &[u8],
218	) -> Result<Option<B::Hash>, Self::Error> {
219		self.state.child_storage_hash(child_info, key)
220	}
221
222	fn closest_merkle_value(
223		&self,
224		key: &[u8],
225	) -> Result<Option<MerkleValue<B::Hash>>, Self::Error> {
226		self.state.closest_merkle_value(key)
227	}
228
229	fn child_closest_merkle_value(
230		&self,
231		child_info: &ChildInfo,
232		key: &[u8],
233	) -> Result<Option<MerkleValue<B::Hash>>, Self::Error> {
234		self.state.child_closest_merkle_value(child_info, key)
235	}
236
237	fn exists_storage(&self, key: &[u8]) -> Result<bool, Self::Error> {
238		self.state.exists_storage(key)
239	}
240
241	fn exists_child_storage(
242		&self,
243		child_info: &ChildInfo,
244		key: &[u8],
245	) -> Result<bool, Self::Error> {
246		self.state.exists_child_storage(child_info, key)
247	}
248
249	fn next_storage_key(&self, key: &[u8]) -> Result<Option<Vec<u8>>, Self::Error> {
250		self.state.next_storage_key(key)
251	}
252
253	fn next_child_storage_key(
254		&self,
255		child_info: &ChildInfo,
256		key: &[u8],
257	) -> Result<Option<Vec<u8>>, Self::Error> {
258		self.state.next_child_storage_key(child_info, key)
259	}
260
261	fn storage_root<'a>(
262		&self,
263		delta: impl Iterator<Item = (&'a [u8], Option<&'a [u8]>)>,
264		state_version: StateVersion,
265	) -> (B::Hash, BackendTransaction<HashingFor<B>>) {
266		self.state.storage_root(delta, state_version)
267	}
268
269	fn child_storage_root<'a>(
270		&self,
271		child_info: &ChildInfo,
272		delta: impl Iterator<Item = (&'a [u8], Option<&'a [u8]>)>,
273		state_version: StateVersion,
274	) -> (B::Hash, bool, BackendTransaction<HashingFor<B>>) {
275		self.state.child_storage_root(child_info, delta, state_version)
276	}
277
278	fn raw_iter(&self, args: IterArgs) -> Result<Self::RawIter, Self::Error> {
279		self.state.raw_iter(args).map(|inner| RawIter { inner })
280	}
281
282	fn register_overlay_stats(&self, stats: &StateMachineStats) {
283		self.state.register_overlay_stats(stats);
284	}
285
286	fn usage_info(&self) -> StateUsageInfo {
287		self.state.usage_info()
288	}
289}
290
291impl<B: BlockT> AsTrieBackend<HashingFor<B>> for RefTrackingState<B> {
292	type TrieBackendStorage =
293		<DbState<HashingFor<B>> as StateBackend<HashingFor<B>>>::TrieBackendStorage;
294
295	fn as_trie_backend(
296		&self,
297	) -> &sp_state_machine::TrieBackend<Self::TrieBackendStorage, HashingFor<B>> {
298		&self.state.as_trie_backend()
299	}
300}
301
302/// Database settings.
303pub struct DatabaseSettings {
304	/// The maximum trie cache size in bytes.
305	///
306	/// If `None` is given, the cache is disabled.
307	pub trie_cache_maximum_size: Option<usize>,
308	/// Requested state pruning mode.
309	pub state_pruning: Option<PruningMode>,
310	/// Where to find the database.
311	pub source: DatabaseSource,
312	/// Block pruning mode.
313	///
314	/// NOTE: only finalized blocks are subject for removal!
315	pub blocks_pruning: BlocksPruning,
316
317	/// Prometheus metrics registry.
318	pub metrics_registry: Option<Registry>,
319}
320
321/// Block pruning settings.
322#[derive(Debug, Clone, Copy, PartialEq)]
323pub enum BlocksPruning {
324	/// Keep full block history, of every block that was ever imported.
325	KeepAll,
326	/// Keep full finalized block history.
327	KeepFinalized,
328	/// Keep N recent finalized blocks.
329	Some(u32),
330}
331
332impl BlocksPruning {
333	/// True if this is an archive pruning mode (either KeepAll or KeepFinalized).
334	pub fn is_archive(&self) -> bool {
335		match *self {
336			BlocksPruning::KeepAll | BlocksPruning::KeepFinalized => true,
337			BlocksPruning::Some(_) => false,
338		}
339	}
340}
341
342/// Where to find the database..
343#[derive(Debug, Clone)]
344pub enum DatabaseSource {
345	/// Check given path, and see if there is an existing database there. If it's either `RocksDb`
346	/// or `ParityDb`, use it. If there is none, create a new instance of `ParityDb`.
347	Auto {
348		/// Path to the paritydb database.
349		paritydb_path: PathBuf,
350		/// Path to the rocksdb database.
351		rocksdb_path: PathBuf,
352		/// Cache size in MiB. Used only by `RocksDb` variant of `DatabaseSource`.
353		cache_size: usize,
354	},
355	/// Load a RocksDB database from a given path. Recommended for most uses.
356	#[cfg(feature = "rocksdb")]
357	RocksDb {
358		/// Path to the database.
359		path: PathBuf,
360		/// Cache size in MiB.
361		cache_size: usize,
362	},
363
364	/// Load a ParityDb database from a given path.
365	ParityDb {
366		/// Path to the database.
367		path: PathBuf,
368	},
369
370	/// Use a custom already-open database.
371	Custom {
372		/// the handle to the custom storage
373		db: Arc<dyn Database<DbHash>>,
374
375		/// if set, the `create` flag will be required to open such datasource
376		require_create_flag: bool,
377	},
378}
379
380impl DatabaseSource {
381	/// Return path for databases that are stored on disk.
382	pub fn path(&self) -> Option<&Path> {
383		match self {
384			// as per https://github.com/paritytech/substrate/pull/9500#discussion_r684312550
385			//
386			// IIUC this is needed for polkadot to create its own dbs, so until it can use parity db
387			// I would think rocksdb, but later parity-db.
388			DatabaseSource::Auto { paritydb_path, .. } => Some(paritydb_path),
389			#[cfg(feature = "rocksdb")]
390			DatabaseSource::RocksDb { path, .. } => Some(path),
391			DatabaseSource::ParityDb { path } => Some(path),
392			DatabaseSource::Custom { .. } => None,
393		}
394	}
395
396	/// Set path for databases that are stored on disk.
397	pub fn set_path(&mut self, p: &Path) -> bool {
398		match self {
399			DatabaseSource::Auto { ref mut paritydb_path, .. } => {
400				*paritydb_path = p.into();
401				true
402			},
403			#[cfg(feature = "rocksdb")]
404			DatabaseSource::RocksDb { ref mut path, .. } => {
405				*path = p.into();
406				true
407			},
408			DatabaseSource::ParityDb { ref mut path } => {
409				*path = p.into();
410				true
411			},
412			DatabaseSource::Custom { .. } => false,
413		}
414	}
415}
416
417impl std::fmt::Display for DatabaseSource {
418	fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
419		let name = match self {
420			DatabaseSource::Auto { .. } => "Auto",
421			#[cfg(feature = "rocksdb")]
422			DatabaseSource::RocksDb { .. } => "RocksDb",
423			DatabaseSource::ParityDb { .. } => "ParityDb",
424			DatabaseSource::Custom { .. } => "Custom",
425		};
426		write!(f, "{}", name)
427	}
428}
429
430pub(crate) mod columns {
431	pub const META: u32 = crate::utils::COLUMN_META;
432	pub const STATE: u32 = 1;
433	pub const STATE_META: u32 = 2;
434	/// maps hashes to lookup keys and numbers to canon hashes.
435	pub const KEY_LOOKUP: u32 = 3;
436	pub const HEADER: u32 = 4;
437	pub const BODY: u32 = 5;
438	pub const JUSTIFICATIONS: u32 = 6;
439	pub const AUX: u32 = 8;
440	/// Offchain workers local storage
441	pub const OFFCHAIN: u32 = 9;
442	/// Transactions
443	pub const TRANSACTION: u32 = 11;
444	pub const BODY_INDEX: u32 = 12;
445}
446
447struct PendingBlock<Block: BlockT> {
448	header: Block::Header,
449	justifications: Option<Justifications>,
450	body: Option<Vec<Block::Extrinsic>>,
451	indexed_body: Option<Vec<Vec<u8>>>,
452	leaf_state: NewBlockState,
453}
454
455// wrapper that implements trait required for state_db
456#[derive(Clone)]
457struct StateMetaDb(Arc<dyn Database<DbHash>>);
458
459impl sc_state_db::MetaDb for StateMetaDb {
460	type Error = sp_database::error::DatabaseError;
461
462	fn get_meta(&self, key: &[u8]) -> Result<Option<Vec<u8>>, Self::Error> {
463		Ok(self.0.get(columns::STATE_META, key))
464	}
465}
466
467struct MetaUpdate<Block: BlockT> {
468	pub hash: Block::Hash,
469	pub number: NumberFor<Block>,
470	pub is_best: bool,
471	pub is_finalized: bool,
472	pub with_state: bool,
473}
474
475fn cache_header<Hash: std::cmp::Eq + std::hash::Hash, Header>(
476	cache: &mut LinkedHashMap<Hash, Option<Header>>,
477	hash: Hash,
478	header: Option<Header>,
479) {
480	cache.insert(hash, header);
481	while cache.len() > CACHE_HEADERS {
482		cache.pop_front();
483	}
484}
485
486/// Block database
487pub struct BlockchainDb<Block: BlockT> {
488	db: Arc<dyn Database<DbHash>>,
489	meta: Arc<RwLock<Meta<NumberFor<Block>, Block::Hash>>>,
490	leaves: RwLock<LeafSet<Block::Hash, NumberFor<Block>>>,
491	header_metadata_cache: Arc<HeaderMetadataCache<Block>>,
492	header_cache: Mutex<LinkedHashMap<Block::Hash, Option<Block::Header>>>,
493	pinned_blocks_cache: Arc<RwLock<PinnedBlocksCache<Block>>>,
494}
495
496impl<Block: BlockT> BlockchainDb<Block> {
497	fn new(db: Arc<dyn Database<DbHash>>) -> ClientResult<Self> {
498		let meta = read_meta::<Block>(&*db, columns::HEADER)?;
499		let leaves = LeafSet::read_from_db(&*db, columns::META, meta_keys::LEAF_PREFIX)?;
500		Ok(BlockchainDb {
501			db,
502			leaves: RwLock::new(leaves),
503			meta: Arc::new(RwLock::new(meta)),
504			header_metadata_cache: Arc::new(HeaderMetadataCache::default()),
505			header_cache: Default::default(),
506			pinned_blocks_cache: Arc::new(RwLock::new(PinnedBlocksCache::new())),
507		})
508	}
509
510	fn update_meta(&self, update: MetaUpdate<Block>) {
511		let MetaUpdate { hash, number, is_best, is_finalized, with_state } = update;
512		let mut meta = self.meta.write();
513		if number.is_zero() {
514			meta.genesis_hash = hash;
515		}
516
517		if is_best {
518			meta.best_number = number;
519			meta.best_hash = hash;
520		}
521
522		if is_finalized {
523			if with_state {
524				meta.finalized_state = Some((hash, number));
525			}
526			meta.finalized_number = number;
527			meta.finalized_hash = hash;
528		}
529	}
530
531	fn update_block_gap(&self, gap: Option<BlockGap<NumberFor<Block>>>) {
532		let mut meta = self.meta.write();
533		meta.block_gap = gap;
534	}
535
536	/// Empty the cache of pinned items.
537	fn clear_pinning_cache(&self) {
538		self.pinned_blocks_cache.write().clear();
539	}
540
541	/// Load a justification into the cache of pinned items.
542	/// Reference count of the item will not be increased. Use this
543	/// to load values for items into the cache which have already been pinned.
544	fn insert_justifications_if_pinned(&self, hash: Block::Hash, justification: Justification) {
545		let mut cache = self.pinned_blocks_cache.write();
546		if !cache.contains(hash) {
547			return;
548		}
549
550		let justifications = Justifications::from(justification);
551		cache.insert_justifications(hash, Some(justifications));
552	}
553
554	/// Load a justification from the db into the cache of pinned items.
555	/// Reference count of the item will not be increased. Use this
556	/// to load values for items into the cache which have already been pinned.
557	fn insert_persisted_justifications_if_pinned(&self, hash: Block::Hash) -> ClientResult<()> {
558		let mut cache = self.pinned_blocks_cache.write();
559		if !cache.contains(hash) {
560			return Ok(());
561		}
562
563		let justifications = self.justifications_uncached(hash)?;
564		cache.insert_justifications(hash, justifications);
565		Ok(())
566	}
567
568	/// Load a block body from the db into the cache of pinned items.
569	/// Reference count of the item will not be increased. Use this
570	/// to load values for items items into the cache which have already been pinned.
571	fn insert_persisted_body_if_pinned(&self, hash: Block::Hash) -> ClientResult<()> {
572		let mut cache = self.pinned_blocks_cache.write();
573		if !cache.contains(hash) {
574			return Ok(());
575		}
576
577		let body = self.body_uncached(hash)?;
578		cache.insert_body(hash, body);
579		Ok(())
580	}
581
582	/// Bump reference count for pinned item.
583	fn bump_ref(&self, hash: Block::Hash) {
584		self.pinned_blocks_cache.write().pin(hash);
585	}
586
587	/// Decrease reference count for pinned item and remove if reference count is 0.
588	fn unpin(&self, hash: Block::Hash) {
589		self.pinned_blocks_cache.write().unpin(hash);
590	}
591
592	fn justifications_uncached(&self, hash: Block::Hash) -> ClientResult<Option<Justifications>> {
593		match read_db(
594			&*self.db,
595			columns::KEY_LOOKUP,
596			columns::JUSTIFICATIONS,
597			BlockId::<Block>::Hash(hash),
598		)? {
599			Some(justifications) => match Decode::decode(&mut &justifications[..]) {
600				Ok(justifications) => Ok(Some(justifications)),
601				Err(err) =>
602					return Err(sp_blockchain::Error::Backend(format!(
603						"Error decoding justifications: {err}"
604					))),
605			},
606			None => Ok(None),
607		}
608	}
609
610	fn body_uncached(&self, hash: Block::Hash) -> ClientResult<Option<Vec<Block::Extrinsic>>> {
611		if let Some(body) =
612			read_db(&*self.db, columns::KEY_LOOKUP, columns::BODY, BlockId::Hash::<Block>(hash))?
613		{
614			// Plain body
615			match Decode::decode(&mut &body[..]) {
616				Ok(body) => return Ok(Some(body)),
617				Err(err) =>
618					return Err(sp_blockchain::Error::Backend(format!("Error decoding body: {err}"))),
619			}
620		}
621
622		if let Some(index) = read_db(
623			&*self.db,
624			columns::KEY_LOOKUP,
625			columns::BODY_INDEX,
626			BlockId::Hash::<Block>(hash),
627		)? {
628			match Vec::<DbExtrinsic<Block>>::decode(&mut &index[..]) {
629				Ok(index) => {
630					let mut body = Vec::new();
631					for ex in index {
632						match ex {
633							DbExtrinsic::Indexed { hash, header } => {
634								match self.db.get(columns::TRANSACTION, hash.as_ref()) {
635									Some(t) => {
636										let mut input =
637											utils::join_input(header.as_ref(), t.as_ref());
638										let ex = Block::Extrinsic::decode(&mut input).map_err(
639											|err| {
640												sp_blockchain::Error::Backend(format!(
641													"Error decoding indexed extrinsic: {err}"
642												))
643											},
644										)?;
645										body.push(ex);
646									},
647									None =>
648										return Err(sp_blockchain::Error::Backend(format!(
649											"Missing indexed transaction {hash:?}"
650										))),
651								};
652							},
653							DbExtrinsic::Full(ex) => {
654								body.push(ex);
655							},
656						}
657					}
658					return Ok(Some(body));
659				},
660				Err(err) =>
661					return Err(sp_blockchain::Error::Backend(format!(
662						"Error decoding body list: {err}",
663					))),
664			}
665		}
666		Ok(None)
667	}
668}
669
670impl<Block: BlockT> sc_client_api::blockchain::HeaderBackend<Block> for BlockchainDb<Block> {
671	fn header(&self, hash: Block::Hash) -> ClientResult<Option<Block::Header>> {
672		let mut cache = self.header_cache.lock();
673		if let Some(result) = cache.get_refresh(&hash) {
674			return Ok(result.clone());
675		}
676		let header = utils::read_header(
677			&*self.db,
678			columns::KEY_LOOKUP,
679			columns::HEADER,
680			BlockId::<Block>::Hash(hash),
681		)?;
682		cache_header(&mut cache, hash, header.clone());
683		Ok(header)
684	}
685
686	fn info(&self) -> sc_client_api::blockchain::Info<Block> {
687		let meta = self.meta.read();
688		sc_client_api::blockchain::Info {
689			best_hash: meta.best_hash,
690			best_number: meta.best_number,
691			genesis_hash: meta.genesis_hash,
692			finalized_hash: meta.finalized_hash,
693			finalized_number: meta.finalized_number,
694			finalized_state: meta.finalized_state,
695			number_leaves: self.leaves.read().count(),
696			block_gap: meta.block_gap,
697		}
698	}
699
700	fn status(&self, hash: Block::Hash) -> ClientResult<sc_client_api::blockchain::BlockStatus> {
701		match self.header(hash)?.is_some() {
702			true => Ok(sc_client_api::blockchain::BlockStatus::InChain),
703			false => Ok(sc_client_api::blockchain::BlockStatus::Unknown),
704		}
705	}
706
707	fn number(&self, hash: Block::Hash) -> ClientResult<Option<NumberFor<Block>>> {
708		Ok(self.header_metadata(hash).ok().map(|header_metadata| header_metadata.number))
709	}
710
711	fn hash(&self, number: NumberFor<Block>) -> ClientResult<Option<Block::Hash>> {
712		Ok(utils::read_header::<Block>(
713			&*self.db,
714			columns::KEY_LOOKUP,
715			columns::HEADER,
716			BlockId::Number(number),
717		)?
718		.map(|header| header.hash()))
719	}
720}
721
722impl<Block: BlockT> sc_client_api::blockchain::Backend<Block> for BlockchainDb<Block> {
723	fn body(&self, hash: Block::Hash) -> ClientResult<Option<Vec<Block::Extrinsic>>> {
724		let cache = self.pinned_blocks_cache.read();
725		if let Some(result) = cache.body(&hash) {
726			return Ok(result.clone());
727		}
728
729		self.body_uncached(hash)
730	}
731
732	fn justifications(&self, hash: Block::Hash) -> ClientResult<Option<Justifications>> {
733		let cache = self.pinned_blocks_cache.read();
734		if let Some(result) = cache.justifications(&hash) {
735			return Ok(result.clone());
736		}
737
738		self.justifications_uncached(hash)
739	}
740
741	fn last_finalized(&self) -> ClientResult<Block::Hash> {
742		Ok(self.meta.read().finalized_hash)
743	}
744
745	fn leaves(&self) -> ClientResult<Vec<Block::Hash>> {
746		Ok(self.leaves.read().hashes())
747	}
748
749	fn children(&self, parent_hash: Block::Hash) -> ClientResult<Vec<Block::Hash>> {
750		children::read_children(&*self.db, columns::META, meta_keys::CHILDREN_PREFIX, parent_hash)
751	}
752
753	fn indexed_transaction(&self, hash: Block::Hash) -> ClientResult<Option<Vec<u8>>> {
754		Ok(self.db.get(columns::TRANSACTION, hash.as_ref()))
755	}
756
757	fn has_indexed_transaction(&self, hash: Block::Hash) -> ClientResult<bool> {
758		Ok(self.db.contains(columns::TRANSACTION, hash.as_ref()))
759	}
760
761	fn block_indexed_body(&self, hash: Block::Hash) -> ClientResult<Option<Vec<Vec<u8>>>> {
762		let body = match read_db(
763			&*self.db,
764			columns::KEY_LOOKUP,
765			columns::BODY_INDEX,
766			BlockId::<Block>::Hash(hash),
767		)? {
768			Some(body) => body,
769			None => return Ok(None),
770		};
771		match Vec::<DbExtrinsic<Block>>::decode(&mut &body[..]) {
772			Ok(index) => {
773				let mut transactions = Vec::new();
774				for ex in index.into_iter() {
775					if let DbExtrinsic::Indexed { hash, .. } = ex {
776						match self.db.get(columns::TRANSACTION, hash.as_ref()) {
777							Some(t) => transactions.push(t),
778							None =>
779								return Err(sp_blockchain::Error::Backend(format!(
780									"Missing indexed transaction {hash:?}",
781								))),
782						}
783					}
784				}
785				Ok(Some(transactions))
786			},
787			Err(err) =>
788				Err(sp_blockchain::Error::Backend(format!("Error decoding body list: {err}"))),
789		}
790	}
791}
792
793impl<Block: BlockT> HeaderMetadata<Block> for BlockchainDb<Block> {
794	type Error = sp_blockchain::Error;
795
796	fn header_metadata(
797		&self,
798		hash: Block::Hash,
799	) -> Result<CachedHeaderMetadata<Block>, Self::Error> {
800		self.header_metadata_cache.header_metadata(hash).map_or_else(
801			|| {
802				self.header(hash)?
803					.map(|header| {
804						let header_metadata = CachedHeaderMetadata::from(&header);
805						self.header_metadata_cache
806							.insert_header_metadata(header_metadata.hash, header_metadata.clone());
807						header_metadata
808					})
809					.ok_or_else(|| {
810						ClientError::UnknownBlock(format!(
811							"Header was not found in the database: {hash:?}",
812						))
813					})
814			},
815			Ok,
816		)
817	}
818
819	fn insert_header_metadata(&self, hash: Block::Hash, metadata: CachedHeaderMetadata<Block>) {
820		self.header_metadata_cache.insert_header_metadata(hash, metadata)
821	}
822
823	fn remove_header_metadata(&self, hash: Block::Hash) {
824		self.header_cache.lock().remove(&hash);
825		self.header_metadata_cache.remove_header_metadata(hash);
826	}
827}
828
829/// Database transaction
830pub struct BlockImportOperation<Block: BlockT> {
831	old_state: RecordStatsState<RefTrackingState<Block>, Block>,
832	db_updates: PrefixedMemoryDB<HashingFor<Block>>,
833	storage_updates: StorageCollection,
834	child_storage_updates: ChildStorageCollection,
835	offchain_storage_updates: OffchainChangesCollection,
836	pending_block: Option<PendingBlock<Block>>,
837	aux_ops: Vec<(Vec<u8>, Option<Vec<u8>>)>,
838	finalized_blocks: Vec<(Block::Hash, Option<Justification>)>,
839	set_head: Option<Block::Hash>,
840	commit_state: bool,
841	create_gap: bool,
842	index_ops: Vec<IndexOperation>,
843}
844
845impl<Block: BlockT> BlockImportOperation<Block> {
846	fn apply_offchain(&mut self, transaction: &mut Transaction<DbHash>) {
847		let mut count = 0;
848		for ((prefix, key), value_operation) in self.offchain_storage_updates.drain(..) {
849			count += 1;
850			let key = crate::offchain::concatenate_prefix_and_key(&prefix, &key);
851			match value_operation {
852				OffchainOverlayedChange::SetValue(val) =>
853					transaction.set_from_vec(columns::OFFCHAIN, &key, val),
854				OffchainOverlayedChange::Remove => transaction.remove(columns::OFFCHAIN, &key),
855			}
856		}
857
858		if count > 0 {
859			log::debug!(target: "sc_offchain", "Applied {count} offchain indexing changes.");
860		}
861	}
862
863	fn apply_aux(&mut self, transaction: &mut Transaction<DbHash>) {
864		for (key, maybe_val) in self.aux_ops.drain(..) {
865			match maybe_val {
866				Some(val) => transaction.set_from_vec(columns::AUX, &key, val),
867				None => transaction.remove(columns::AUX, &key),
868			}
869		}
870	}
871
872	fn apply_new_state(
873		&mut self,
874		storage: Storage,
875		state_version: StateVersion,
876	) -> ClientResult<Block::Hash> {
877		if storage.top.keys().any(|k| well_known_keys::is_child_storage_key(k)) {
878			return Err(sp_blockchain::Error::InvalidState);
879		}
880
881		let child_delta = storage.children_default.values().map(|child_content| {
882			(
883				&child_content.child_info,
884				child_content.data.iter().map(|(k, v)| (&k[..], Some(&v[..]))),
885			)
886		});
887
888		let (root, transaction) = self.old_state.full_storage_root(
889			storage.top.iter().map(|(k, v)| (&k[..], Some(&v[..]))),
890			child_delta,
891			state_version,
892		);
893
894		self.db_updates = transaction;
895		Ok(root)
896	}
897}
898
899impl<Block: BlockT> sc_client_api::backend::BlockImportOperation<Block>
900	for BlockImportOperation<Block>
901{
902	type State = RecordStatsState<RefTrackingState<Block>, Block>;
903
904	fn state(&self) -> ClientResult<Option<&Self::State>> {
905		Ok(Some(&self.old_state))
906	}
907
908	fn set_block_data(
909		&mut self,
910		header: Block::Header,
911		body: Option<Vec<Block::Extrinsic>>,
912		indexed_body: Option<Vec<Vec<u8>>>,
913		justifications: Option<Justifications>,
914		leaf_state: NewBlockState,
915	) -> ClientResult<()> {
916		assert!(self.pending_block.is_none(), "Only one block per operation is allowed");
917		self.pending_block =
918			Some(PendingBlock { header, body, indexed_body, justifications, leaf_state });
919		Ok(())
920	}
921
922	fn update_db_storage(
923		&mut self,
924		update: PrefixedMemoryDB<HashingFor<Block>>,
925	) -> ClientResult<()> {
926		self.db_updates = update;
927		Ok(())
928	}
929
930	fn reset_storage(
931		&mut self,
932		storage: Storage,
933		state_version: StateVersion,
934	) -> ClientResult<Block::Hash> {
935		let root = self.apply_new_state(storage, state_version)?;
936		self.commit_state = true;
937		Ok(root)
938	}
939
940	fn set_genesis_state(
941		&mut self,
942		storage: Storage,
943		commit: bool,
944		state_version: StateVersion,
945	) -> ClientResult<Block::Hash> {
946		let root = self.apply_new_state(storage, state_version)?;
947		self.commit_state = commit;
948		Ok(root)
949	}
950
951	fn insert_aux<I>(&mut self, ops: I) -> ClientResult<()>
952	where
953		I: IntoIterator<Item = (Vec<u8>, Option<Vec<u8>>)>,
954	{
955		self.aux_ops.append(&mut ops.into_iter().collect());
956		Ok(())
957	}
958
959	fn update_storage(
960		&mut self,
961		update: StorageCollection,
962		child_update: ChildStorageCollection,
963	) -> ClientResult<()> {
964		self.storage_updates = update;
965		self.child_storage_updates = child_update;
966		Ok(())
967	}
968
969	fn update_offchain_storage(
970		&mut self,
971		offchain_update: OffchainChangesCollection,
972	) -> ClientResult<()> {
973		self.offchain_storage_updates = offchain_update;
974		Ok(())
975	}
976
977	fn mark_finalized(
978		&mut self,
979		block: Block::Hash,
980		justification: Option<Justification>,
981	) -> ClientResult<()> {
982		self.finalized_blocks.push((block, justification));
983		Ok(())
984	}
985
986	fn mark_head(&mut self, hash: Block::Hash) -> ClientResult<()> {
987		assert!(self.set_head.is_none(), "Only one set head per operation is allowed");
988		self.set_head = Some(hash);
989		Ok(())
990	}
991
992	fn update_transaction_index(&mut self, index_ops: Vec<IndexOperation>) -> ClientResult<()> {
993		self.index_ops = index_ops;
994		Ok(())
995	}
996
997	fn set_create_gap(&mut self, create_gap: bool) {
998		self.create_gap = create_gap;
999	}
1000}
1001
1002struct StorageDb<Block: BlockT> {
1003	pub db: Arc<dyn Database<DbHash>>,
1004	pub state_db: StateDb<Block::Hash, Vec<u8>, StateMetaDb>,
1005	prefix_keys: bool,
1006}
1007
1008impl<Block: BlockT> sp_state_machine::Storage<HashingFor<Block>> for StorageDb<Block> {
1009	fn get(&self, key: &Block::Hash, prefix: Prefix) -> Result<Option<DBValue>, String> {
1010		if self.prefix_keys {
1011			let key = prefixed_key::<HashingFor<Block>>(key, prefix);
1012			self.state_db.get(&key, self)
1013		} else {
1014			self.state_db.get(key.as_ref(), self)
1015		}
1016		.map_err(|e| format!("Database backend error: {e:?}"))
1017	}
1018}
1019
1020impl<Block: BlockT> sc_state_db::NodeDb for StorageDb<Block> {
1021	type Error = io::Error;
1022	type Key = [u8];
1023
1024	fn get(&self, key: &[u8]) -> Result<Option<Vec<u8>>, Self::Error> {
1025		Ok(self.db.get(columns::STATE, key))
1026	}
1027}
1028
1029struct DbGenesisStorage<Block: BlockT> {
1030	root: Block::Hash,
1031	storage: PrefixedMemoryDB<HashingFor<Block>>,
1032}
1033
1034impl<Block: BlockT> DbGenesisStorage<Block> {
1035	pub fn new(root: Block::Hash, storage: PrefixedMemoryDB<HashingFor<Block>>) -> Self {
1036		DbGenesisStorage { root, storage }
1037	}
1038}
1039
1040impl<Block: BlockT> sp_state_machine::Storage<HashingFor<Block>> for DbGenesisStorage<Block> {
1041	fn get(&self, key: &Block::Hash, prefix: Prefix) -> Result<Option<DBValue>, String> {
1042		use hash_db::HashDB;
1043		Ok(self.storage.get(key, prefix))
1044	}
1045}
1046
1047struct EmptyStorage<Block: BlockT>(pub Block::Hash);
1048
1049impl<Block: BlockT> EmptyStorage<Block> {
1050	pub fn new() -> Self {
1051		let mut root = Block::Hash::default();
1052		let mut mdb = MemoryDB::<HashingFor<Block>>::default();
1053		// both triedbmut are the same on empty storage.
1054		sp_trie::trie_types::TrieDBMutBuilderV1::<HashingFor<Block>>::new(&mut mdb, &mut root)
1055			.build();
1056		EmptyStorage(root)
1057	}
1058}
1059
1060impl<Block: BlockT> sp_state_machine::Storage<HashingFor<Block>> for EmptyStorage<Block> {
1061	fn get(&self, _key: &Block::Hash, _prefix: Prefix) -> Result<Option<DBValue>, String> {
1062		Ok(None)
1063	}
1064}
1065
1066/// Frozen `value` at time `at`.
1067///
1068/// Used as inner structure under lock in `FrozenForDuration`.
1069struct Frozen<T: Clone> {
1070	at: std::time::Instant,
1071	value: Option<T>,
1072}
1073
1074/// Some value frozen for period of time.
1075///
1076/// If time `duration` not passed since the value was instantiated,
1077/// current frozen value is returned. Otherwise, you have to provide
1078/// a new value which will be again frozen for `duration`.
1079pub(crate) struct FrozenForDuration<T: Clone> {
1080	duration: std::time::Duration,
1081	value: parking_lot::Mutex<Frozen<T>>,
1082}
1083
1084impl<T: Clone> FrozenForDuration<T> {
1085	fn new(duration: std::time::Duration) -> Self {
1086		Self { duration, value: Frozen { at: std::time::Instant::now(), value: None }.into() }
1087	}
1088
1089	fn take_or_else<F>(&self, f: F) -> T
1090	where
1091		F: FnOnce() -> T,
1092	{
1093		let mut lock = self.value.lock();
1094		let now = std::time::Instant::now();
1095		if now.saturating_duration_since(lock.at) > self.duration || lock.value.is_none() {
1096			let new_value = f();
1097			lock.at = now;
1098			lock.value = Some(new_value.clone());
1099			new_value
1100		} else {
1101			lock.value.as_ref().expect("Checked with in branch above; qed").clone()
1102		}
1103	}
1104}
1105
1106/// Disk backend.
1107///
1108/// Disk backend keeps data in a key-value store. In archive mode, trie nodes are kept from all
1109/// blocks. Otherwise, trie nodes are kept only from some recent blocks.
1110pub struct Backend<Block: BlockT> {
1111	storage: Arc<StorageDb<Block>>,
1112	offchain_storage: offchain::LocalStorage,
1113	blockchain: BlockchainDb<Block>,
1114	canonicalization_delay: u64,
1115	import_lock: Arc<RwLock<()>>,
1116	is_archive: bool,
1117	blocks_pruning: BlocksPruning,
1118	io_stats: FrozenForDuration<(kvdb::IoStats, StateUsageInfo)>,
1119	state_usage: Arc<StateUsageStats>,
1120	genesis_state: RwLock<Option<Arc<DbGenesisStorage<Block>>>>,
1121	shared_trie_cache: Option<sp_trie::cache::SharedTrieCache<HashingFor<Block>>>,
1122}
1123
1124impl<Block: BlockT> Backend<Block> {
1125	/// Create a new instance of database backend.
1126	///
1127	/// The pruning window is how old a block must be before the state is pruned.
1128	pub fn new(db_config: DatabaseSettings, canonicalization_delay: u64) -> ClientResult<Self> {
1129		use utils::OpenDbError;
1130
1131		let db_source = &db_config.source;
1132
1133		let (needs_init, db) =
1134			match crate::utils::open_database::<Block>(db_source, DatabaseType::Full, false) {
1135				Ok(db) => (false, db),
1136				Err(OpenDbError::DoesNotExist) => {
1137					let db =
1138						crate::utils::open_database::<Block>(db_source, DatabaseType::Full, true)?;
1139					(true, db)
1140				},
1141				Err(as_is) => return Err(as_is.into()),
1142			};
1143
1144		Self::from_database(db as Arc<_>, canonicalization_delay, &db_config, needs_init)
1145	}
1146
1147	/// Reset the shared trie cache.
1148	pub fn reset_trie_cache(&self) {
1149		if let Some(cache) = &self.shared_trie_cache {
1150			cache.reset();
1151		}
1152	}
1153
1154	/// Create new memory-backed client backend for tests.
1155	#[cfg(any(test, feature = "test-helpers"))]
1156	pub fn new_test(blocks_pruning: u32, canonicalization_delay: u64) -> Self {
1157		Self::new_test_with_tx_storage(BlocksPruning::Some(blocks_pruning), canonicalization_delay)
1158	}
1159
1160	/// Create new memory-backed client backend for tests.
1161	#[cfg(any(test, feature = "test-helpers"))]
1162	pub fn new_test_with_tx_storage(
1163		blocks_pruning: BlocksPruning,
1164		canonicalization_delay: u64,
1165	) -> Self {
1166		let db = kvdb_memorydb::create(crate::utils::NUM_COLUMNS);
1167		let db = sp_database::as_database(db);
1168		let state_pruning = match blocks_pruning {
1169			BlocksPruning::KeepAll => PruningMode::ArchiveAll,
1170			BlocksPruning::KeepFinalized => PruningMode::ArchiveCanonical,
1171			BlocksPruning::Some(n) => PruningMode::blocks_pruning(n),
1172		};
1173		let db_setting = DatabaseSettings {
1174			trie_cache_maximum_size: Some(16 * 1024 * 1024),
1175			state_pruning: Some(state_pruning),
1176			source: DatabaseSource::Custom { db, require_create_flag: true },
1177			blocks_pruning,
1178			metrics_registry: None,
1179		};
1180
1181		Self::new(db_setting, canonicalization_delay).expect("failed to create test-db")
1182	}
1183
1184	/// Expose the Database that is used by this backend.
1185	/// The second argument is the Column that stores the State.
1186	///
1187	/// Should only be needed for benchmarking.
1188	#[cfg(feature = "runtime-benchmarks")]
1189	pub fn expose_db(&self) -> (Arc<dyn sp_database::Database<DbHash>>, sp_database::ColumnId) {
1190		(self.storage.db.clone(), columns::STATE)
1191	}
1192
1193	/// Expose the Storage that is used by this backend.
1194	///
1195	/// Should only be needed for benchmarking.
1196	#[cfg(feature = "runtime-benchmarks")]
1197	pub fn expose_storage(&self) -> Arc<dyn sp_state_machine::Storage<HashingFor<Block>>> {
1198		self.storage.clone()
1199	}
1200
1201	/// Expose the shared trie cache that is used by this backend.
1202	///
1203	/// Should only be needed for benchmarking.
1204	#[cfg(feature = "runtime-benchmarks")]
1205	pub fn expose_shared_trie_cache(
1206		&self,
1207	) -> Option<sp_trie::cache::SharedTrieCache<HashingFor<Block>>> {
1208		self.shared_trie_cache.clone()
1209	}
1210
1211	fn from_database(
1212		db: Arc<dyn Database<DbHash>>,
1213		canonicalization_delay: u64,
1214		config: &DatabaseSettings,
1215		should_init: bool,
1216	) -> ClientResult<Self> {
1217		let mut db_init_transaction = Transaction::new();
1218
1219		let requested_state_pruning = config.state_pruning.clone();
1220		let state_meta_db = StateMetaDb(db.clone());
1221		let map_e = sp_blockchain::Error::from_state_db;
1222
1223		let (state_db_init_commit_set, state_db) = StateDb::open(
1224			state_meta_db,
1225			requested_state_pruning,
1226			!db.supports_ref_counting(),
1227			should_init,
1228		)
1229		.map_err(map_e)?;
1230
1231		apply_state_commit(&mut db_init_transaction, state_db_init_commit_set);
1232
1233		let state_pruning_used = state_db.pruning_mode();
1234		let is_archive_pruning = state_pruning_used.is_archive();
1235		let blockchain = BlockchainDb::new(db.clone())?;
1236
1237		let storage_db =
1238			StorageDb { db: db.clone(), state_db, prefix_keys: !db.supports_ref_counting() };
1239
1240		let offchain_storage = offchain::LocalStorage::new(db.clone());
1241
1242		let shared_trie_cache = config.trie_cache_maximum_size.map(|maximum_size| {
1243			let system_memory = sysinfo::System::new_all();
1244			let used_memory = system_memory.used_memory();
1245			let total_memory = system_memory.total_memory();
1246
1247			debug!("Initializing shared trie cache with size {} bytes, {}% of total memory", maximum_size, (maximum_size as f64 / total_memory as f64 * 100.0));
1248			if maximum_size as u64 > total_memory - used_memory {
1249				warn!(
1250					"Not enough memory to initialize shared trie cache. Cache size: {} bytes. System memory: used {} bytes, total {} bytes",
1251					maximum_size, used_memory, total_memory,
1252				);
1253			}
1254
1255			SharedTrieCache::new(sp_trie::cache::CacheSize::new(maximum_size), config.metrics_registry.as_ref())
1256		});
1257
1258		let backend = Backend {
1259			storage: Arc::new(storage_db),
1260			offchain_storage,
1261			blockchain,
1262			canonicalization_delay,
1263			import_lock: Default::default(),
1264			is_archive: is_archive_pruning,
1265			io_stats: FrozenForDuration::new(std::time::Duration::from_secs(1)),
1266			state_usage: Arc::new(StateUsageStats::new()),
1267			blocks_pruning: config.blocks_pruning,
1268			genesis_state: RwLock::new(None),
1269			shared_trie_cache,
1270		};
1271
1272		// Older DB versions have no last state key. Check if the state is available and set it.
1273		let info = backend.blockchain.info();
1274		if info.finalized_state.is_none() &&
1275			info.finalized_hash != Default::default() &&
1276			sc_client_api::Backend::have_state_at(
1277				&backend,
1278				info.finalized_hash,
1279				info.finalized_number,
1280			) {
1281			backend.blockchain.update_meta(MetaUpdate {
1282				hash: info.finalized_hash,
1283				number: info.finalized_number,
1284				is_best: info.finalized_hash == info.best_hash,
1285				is_finalized: true,
1286				with_state: true,
1287			});
1288		}
1289
1290		db.commit(db_init_transaction)?;
1291
1292		Ok(backend)
1293	}
1294
1295	/// Handle setting head within a transaction. `route_to` should be the last
1296	/// block that existed in the database. `best_to` should be the best block
1297	/// to be set.
1298	///
1299	/// In the case where the new best block is a block to be imported, `route_to`
1300	/// should be the parent of `best_to`. In the case where we set an existing block
1301	/// to be best, `route_to` should equal to `best_to`.
1302	fn set_head_with_transaction(
1303		&self,
1304		transaction: &mut Transaction<DbHash>,
1305		route_to: Block::Hash,
1306		best_to: (NumberFor<Block>, Block::Hash),
1307	) -> ClientResult<(Vec<Block::Hash>, Vec<Block::Hash>)> {
1308		let mut enacted = Vec::default();
1309		let mut retracted = Vec::default();
1310
1311		let (best_number, best_hash) = best_to;
1312
1313		let meta = self.blockchain.meta.read();
1314
1315		if meta.best_number.saturating_sub(best_number).saturated_into::<u64>() >
1316			self.canonicalization_delay
1317		{
1318			return Err(sp_blockchain::Error::SetHeadTooOld);
1319		}
1320
1321		let parent_exists =
1322			self.blockchain.status(route_to)? == sp_blockchain::BlockStatus::InChain;
1323
1324		// Cannot find tree route with empty DB or when imported a detached block.
1325		if meta.best_hash != Default::default() && parent_exists {
1326			let tree_route = sp_blockchain::tree_route(&self.blockchain, meta.best_hash, route_to)?;
1327
1328			// uncanonicalize: check safety violations and ensure the numbers no longer
1329			// point to these block hashes in the key mapping.
1330			for r in tree_route.retracted() {
1331				if r.hash == meta.finalized_hash {
1332					warn!(
1333						"Potential safety failure: reverting finalized block {:?}",
1334						(&r.number, &r.hash)
1335					);
1336
1337					return Err(sp_blockchain::Error::NotInFinalizedChain);
1338				}
1339
1340				retracted.push(r.hash);
1341				utils::remove_number_to_key_mapping(transaction, columns::KEY_LOOKUP, r.number)?;
1342			}
1343
1344			// canonicalize: set the number lookup to map to this block's hash.
1345			for e in tree_route.enacted() {
1346				enacted.push(e.hash);
1347				utils::insert_number_to_key_mapping(
1348					transaction,
1349					columns::KEY_LOOKUP,
1350					e.number,
1351					e.hash,
1352				)?;
1353			}
1354		}
1355
1356		let lookup_key = utils::number_and_hash_to_lookup_key(best_number, &best_hash)?;
1357		transaction.set_from_vec(columns::META, meta_keys::BEST_BLOCK, lookup_key);
1358		utils::insert_number_to_key_mapping(
1359			transaction,
1360			columns::KEY_LOOKUP,
1361			best_number,
1362			best_hash,
1363		)?;
1364
1365		Ok((enacted, retracted))
1366	}
1367
1368	fn ensure_sequential_finalization(
1369		&self,
1370		header: &Block::Header,
1371		last_finalized: Option<Block::Hash>,
1372	) -> ClientResult<()> {
1373		let last_finalized =
1374			last_finalized.unwrap_or_else(|| self.blockchain.meta.read().finalized_hash);
1375		if last_finalized != self.blockchain.meta.read().genesis_hash &&
1376			*header.parent_hash() != last_finalized
1377		{
1378			return Err(sp_blockchain::Error::NonSequentialFinalization(format!(
1379				"Last finalized {last_finalized:?} not parent of {:?}",
1380				header.hash()
1381			)));
1382		}
1383		Ok(())
1384	}
1385
1386	/// `remove_displaced` can be set to `false` if this is not the last of many subsequent calls
1387	/// for performance reasons.
1388	fn finalize_block_with_transaction(
1389		&self,
1390		transaction: &mut Transaction<DbHash>,
1391		hash: Block::Hash,
1392		header: &Block::Header,
1393		last_finalized: Option<Block::Hash>,
1394		justification: Option<Justification>,
1395		current_transaction_justifications: &mut HashMap<Block::Hash, Justification>,
1396		remove_displaced: bool,
1397	) -> ClientResult<MetaUpdate<Block>> {
1398		// TODO: ensure best chain contains this block.
1399		let number = *header.number();
1400		self.ensure_sequential_finalization(header, last_finalized)?;
1401		let with_state = sc_client_api::Backend::have_state_at(self, hash, number);
1402
1403		self.note_finalized(
1404			transaction,
1405			header,
1406			hash,
1407			with_state,
1408			current_transaction_justifications,
1409			remove_displaced,
1410		)?;
1411
1412		if let Some(justification) = justification {
1413			transaction.set_from_vec(
1414				columns::JUSTIFICATIONS,
1415				&utils::number_and_hash_to_lookup_key(number, hash)?,
1416				Justifications::from(justification.clone()).encode(),
1417			);
1418			current_transaction_justifications.insert(hash, justification);
1419		}
1420		Ok(MetaUpdate { hash, number, is_best: false, is_finalized: true, with_state })
1421	}
1422
1423	// performs forced canonicalization with a delay after importing a non-finalized block.
1424	fn force_delayed_canonicalize(
1425		&self,
1426		transaction: &mut Transaction<DbHash>,
1427	) -> ClientResult<()> {
1428		let best_canonical = match self.storage.state_db.last_canonicalized() {
1429			LastCanonicalized::None => 0,
1430			LastCanonicalized::Block(b) => b,
1431			// Nothing needs to be done when canonicalization is not happening.
1432			LastCanonicalized::NotCanonicalizing => return Ok(()),
1433		};
1434
1435		let info = self.blockchain.info();
1436		let best_number: u64 = self.blockchain.info().best_number.saturated_into();
1437
1438		for to_canonicalize in
1439			best_canonical + 1..=best_number.saturating_sub(self.canonicalization_delay)
1440		{
1441			let hash_to_canonicalize = sc_client_api::blockchain::HeaderBackend::hash(
1442				&self.blockchain,
1443				to_canonicalize.saturated_into(),
1444			)?
1445			.ok_or_else(|| {
1446				let best_hash = info.best_hash;
1447
1448				sp_blockchain::Error::Backend(format!(
1449					"Can't canonicalize missing block number #{to_canonicalize} when for best block {best_hash:?} (#{best_number})",
1450				))
1451			})?;
1452
1453			if !sc_client_api::Backend::have_state_at(
1454				self,
1455				hash_to_canonicalize,
1456				to_canonicalize.saturated_into(),
1457			) {
1458				return Ok(());
1459			}
1460
1461			trace!(target: "db", "Canonicalize block #{to_canonicalize} ({hash_to_canonicalize:?})");
1462			let commit = self.storage.state_db.canonicalize_block(&hash_to_canonicalize).map_err(
1463				sp_blockchain::Error::from_state_db::<
1464					sc_state_db::Error<sp_database::error::DatabaseError>,
1465				>,
1466			)?;
1467			apply_state_commit(transaction, commit);
1468		}
1469
1470		Ok(())
1471	}
1472
1473	fn try_commit_operation(&self, mut operation: BlockImportOperation<Block>) -> ClientResult<()> {
1474		let mut transaction = Transaction::new();
1475
1476		operation.apply_aux(&mut transaction);
1477		operation.apply_offchain(&mut transaction);
1478
1479		let mut meta_updates = Vec::with_capacity(operation.finalized_blocks.len());
1480		let (best_num, mut last_finalized_hash, mut last_finalized_num, mut block_gap) = {
1481			let meta = self.blockchain.meta.read();
1482			(meta.best_number, meta.finalized_hash, meta.finalized_number, meta.block_gap)
1483		};
1484
1485		let mut block_gap_updated = false;
1486
1487		let mut current_transaction_justifications: HashMap<Block::Hash, Justification> =
1488			HashMap::new();
1489		let mut finalized_blocks = operation.finalized_blocks.into_iter().peekable();
1490		while let Some((block_hash, justification)) = finalized_blocks.next() {
1491			let block_header = self.blockchain.expect_header(block_hash)?;
1492			meta_updates.push(self.finalize_block_with_transaction(
1493				&mut transaction,
1494				block_hash,
1495				&block_header,
1496				Some(last_finalized_hash),
1497				justification,
1498				&mut current_transaction_justifications,
1499				finalized_blocks.peek().is_none(),
1500			)?);
1501			last_finalized_hash = block_hash;
1502			last_finalized_num = *block_header.number();
1503		}
1504
1505		let imported = if let Some(pending_block) = operation.pending_block {
1506			let hash = pending_block.header.hash();
1507
1508			let parent_hash = *pending_block.header.parent_hash();
1509			let number = *pending_block.header.number();
1510			let highest_leaf = self
1511				.blockchain
1512				.leaves
1513				.read()
1514				.highest_leaf()
1515				.map(|(n, _)| n)
1516				.unwrap_or(Zero::zero());
1517			let existing_header = number <= highest_leaf && self.blockchain.header(hash)?.is_some();
1518			let existing_body = pending_block.body.is_some();
1519
1520			// blocks are keyed by number + hash.
1521			let lookup_key = utils::number_and_hash_to_lookup_key(number, hash)?;
1522
1523			if pending_block.leaf_state.is_best() {
1524				self.set_head_with_transaction(&mut transaction, parent_hash, (number, hash))?;
1525			};
1526
1527			utils::insert_hash_to_key_mapping(&mut transaction, columns::KEY_LOOKUP, number, hash)?;
1528
1529			transaction.set_from_vec(columns::HEADER, &lookup_key, pending_block.header.encode());
1530			if let Some(body) = pending_block.body {
1531				// If we have any index operations we save block in the new format with indexed
1532				// extrinsic headers Otherwise we save the body as a single blob.
1533				if operation.index_ops.is_empty() {
1534					transaction.set_from_vec(columns::BODY, &lookup_key, body.encode());
1535				} else {
1536					let body =
1537						apply_index_ops::<Block>(&mut transaction, body, operation.index_ops);
1538					transaction.set_from_vec(columns::BODY_INDEX, &lookup_key, body);
1539				}
1540			}
1541			if let Some(body) = pending_block.indexed_body {
1542				apply_indexed_body::<Block>(&mut transaction, body);
1543			}
1544			if let Some(justifications) = pending_block.justifications {
1545				transaction.set_from_vec(
1546					columns::JUSTIFICATIONS,
1547					&lookup_key,
1548					justifications.encode(),
1549				);
1550			}
1551
1552			if number.is_zero() {
1553				transaction.set(columns::META, meta_keys::GENESIS_HASH, hash.as_ref());
1554
1555				if operation.commit_state {
1556					transaction.set_from_vec(columns::META, meta_keys::FINALIZED_STATE, lookup_key);
1557				} else {
1558					// When we don't want to commit the genesis state, we still preserve it in
1559					// memory to bootstrap consensus. It is queried for an initial list of
1560					// authorities, etc.
1561					*self.genesis_state.write() = Some(Arc::new(DbGenesisStorage::new(
1562						*pending_block.header.state_root(),
1563						operation.db_updates.clone(),
1564					)));
1565				}
1566			}
1567
1568			let finalized = if operation.commit_state {
1569				let mut changeset: sc_state_db::ChangeSet<Vec<u8>> =
1570					sc_state_db::ChangeSet::default();
1571				let mut ops: u64 = 0;
1572				let mut bytes: u64 = 0;
1573				let mut removal: u64 = 0;
1574				let mut bytes_removal: u64 = 0;
1575				for (mut key, (val, rc)) in operation.db_updates.drain() {
1576					self.storage.db.sanitize_key(&mut key);
1577					if rc > 0 {
1578						ops += 1;
1579						bytes += key.len() as u64 + val.len() as u64;
1580						if rc == 1 {
1581							changeset.inserted.push((key, val.to_vec()));
1582						} else {
1583							changeset.inserted.push((key.clone(), val.to_vec()));
1584							for _ in 0..rc - 1 {
1585								changeset.inserted.push((key.clone(), Default::default()));
1586							}
1587						}
1588					} else if rc < 0 {
1589						removal += 1;
1590						bytes_removal += key.len() as u64;
1591						if rc == -1 {
1592							changeset.deleted.push(key);
1593						} else {
1594							for _ in 0..-rc {
1595								changeset.deleted.push(key.clone());
1596							}
1597						}
1598					}
1599				}
1600				self.state_usage.tally_writes_nodes(ops, bytes);
1601				self.state_usage.tally_removed_nodes(removal, bytes_removal);
1602
1603				let mut ops: u64 = 0;
1604				let mut bytes: u64 = 0;
1605				for (key, value) in operation
1606					.storage_updates
1607					.iter()
1608					.chain(operation.child_storage_updates.iter().flat_map(|(_, s)| s.iter()))
1609				{
1610					ops += 1;
1611					bytes += key.len() as u64;
1612					if let Some(v) = value.as_ref() {
1613						bytes += v.len() as u64;
1614					}
1615				}
1616				self.state_usage.tally_writes(ops, bytes);
1617				let number_u64 = number.saturated_into::<u64>();
1618				let commit = self
1619					.storage
1620					.state_db
1621					.insert_block(&hash, number_u64, pending_block.header.parent_hash(), changeset)
1622					.map_err(|e: sc_state_db::Error<sp_database::error::DatabaseError>| {
1623						sp_blockchain::Error::from_state_db(e)
1624					})?;
1625				apply_state_commit(&mut transaction, commit);
1626				if number <= last_finalized_num {
1627					// Canonicalize in the db when re-importing existing blocks with state.
1628					let commit = self.storage.state_db.canonicalize_block(&hash).map_err(
1629						sp_blockchain::Error::from_state_db::<
1630							sc_state_db::Error<sp_database::error::DatabaseError>,
1631						>,
1632					)?;
1633					apply_state_commit(&mut transaction, commit);
1634					meta_updates.push(MetaUpdate {
1635						hash,
1636						number,
1637						is_best: false,
1638						is_finalized: true,
1639						with_state: true,
1640					});
1641				}
1642
1643				// Check if need to finalize. Genesis is always finalized instantly.
1644				let finalized = number_u64 == 0 || pending_block.leaf_state.is_final();
1645				finalized
1646			} else {
1647				(number.is_zero() && last_finalized_num.is_zero()) ||
1648					pending_block.leaf_state.is_final()
1649			};
1650
1651			let header = &pending_block.header;
1652			let is_best = pending_block.leaf_state.is_best();
1653			debug!(
1654				target: "db",
1655				"DB Commit {hash:?} ({number}), best={is_best}, state={}, existing={existing_header}, finalized={finalized}",
1656				operation.commit_state,
1657			);
1658
1659			self.state_usage.merge_sm(operation.old_state.usage_info());
1660
1661			// release state reference so that it can be finalized
1662			// VERY IMPORTANT
1663			drop(operation.old_state);
1664
1665			if finalized {
1666				// TODO: ensure best chain contains this block.
1667				self.ensure_sequential_finalization(header, Some(last_finalized_hash))?;
1668				let mut current_transaction_justifications = HashMap::new();
1669				self.note_finalized(
1670					&mut transaction,
1671					header,
1672					hash,
1673					operation.commit_state,
1674					&mut current_transaction_justifications,
1675					true,
1676				)?;
1677			} else {
1678				// canonicalize blocks which are old enough, regardless of finality.
1679				self.force_delayed_canonicalize(&mut transaction)?
1680			}
1681
1682			if !existing_header {
1683				// Add a new leaf if the block has the potential to be finalized.
1684				if number > last_finalized_num || last_finalized_num.is_zero() {
1685					let mut leaves = self.blockchain.leaves.write();
1686					leaves.import(hash, number, parent_hash);
1687					leaves.prepare_transaction(
1688						&mut transaction,
1689						columns::META,
1690						meta_keys::LEAF_PREFIX,
1691					);
1692				}
1693
1694				let mut children = children::read_children(
1695					&*self.storage.db,
1696					columns::META,
1697					meta_keys::CHILDREN_PREFIX,
1698					parent_hash,
1699				)?;
1700				if !children.contains(&hash) {
1701					children.push(hash);
1702					children::write_children(
1703						&mut transaction,
1704						columns::META,
1705						meta_keys::CHILDREN_PREFIX,
1706						parent_hash,
1707						children,
1708					);
1709				}
1710			}
1711
1712			let should_check_block_gap = !existing_header || !existing_body;
1713
1714			if should_check_block_gap {
1715				let insert_new_gap =
1716					|transaction: &mut Transaction<DbHash>,
1717					 new_gap: BlockGap<NumberFor<Block>>,
1718					 block_gap: &mut Option<BlockGap<NumberFor<Block>>>| {
1719						transaction.set(columns::META, meta_keys::BLOCK_GAP, &new_gap.encode());
1720						transaction.set(
1721							columns::META,
1722							meta_keys::BLOCK_GAP_VERSION,
1723							&BLOCK_GAP_CURRENT_VERSION.encode(),
1724						);
1725						block_gap.replace(new_gap);
1726					};
1727
1728				if let Some(mut gap) = block_gap {
1729					match gap.gap_type {
1730						BlockGapType::MissingHeaderAndBody =>
1731							if number == gap.start {
1732								gap.start += One::one();
1733								utils::insert_number_to_key_mapping(
1734									&mut transaction,
1735									columns::KEY_LOOKUP,
1736									number,
1737									hash,
1738								)?;
1739								if gap.start > gap.end {
1740									transaction.remove(columns::META, meta_keys::BLOCK_GAP);
1741									transaction.remove(columns::META, meta_keys::BLOCK_GAP_VERSION);
1742									block_gap = None;
1743									debug!(target: "db", "Removed block gap.");
1744								} else {
1745									insert_new_gap(&mut transaction, gap, &mut block_gap);
1746									debug!(target: "db", "Update block gap. {block_gap:?}");
1747								}
1748								block_gap_updated = true;
1749							},
1750						BlockGapType::MissingBody => {
1751							// Gap increased when syncing the header chain during fast sync.
1752							if number == gap.end + One::one() && !existing_body {
1753								gap.end += One::one();
1754								utils::insert_number_to_key_mapping(
1755									&mut transaction,
1756									columns::KEY_LOOKUP,
1757									number,
1758									hash,
1759								)?;
1760								insert_new_gap(&mut transaction, gap, &mut block_gap);
1761								debug!(target: "db", "Update block gap. {block_gap:?}");
1762								block_gap_updated = true;
1763							// Gap decreased when downloading the full blocks.
1764							} else if number == gap.start && existing_body {
1765								gap.start += One::one();
1766								if gap.start > gap.end {
1767									transaction.remove(columns::META, meta_keys::BLOCK_GAP);
1768									transaction.remove(columns::META, meta_keys::BLOCK_GAP_VERSION);
1769									block_gap = None;
1770									debug!(target: "db", "Removed block gap.");
1771								} else {
1772									insert_new_gap(&mut transaction, gap, &mut block_gap);
1773									debug!(target: "db", "Update block gap. {block_gap:?}");
1774								}
1775								block_gap_updated = true;
1776							}
1777						},
1778					}
1779				} else if operation.create_gap {
1780					if number > best_num + One::one() &&
1781						self.blockchain.header(parent_hash)?.is_none()
1782					{
1783						let gap = BlockGap {
1784							start: best_num + One::one(),
1785							end: number - One::one(),
1786							gap_type: BlockGapType::MissingHeaderAndBody,
1787						};
1788						insert_new_gap(&mut transaction, gap, &mut block_gap);
1789						block_gap_updated = true;
1790						debug!(target: "db", "Detected block gap (warp sync) {block_gap:?}");
1791					} else if number == best_num + One::one() &&
1792						self.blockchain.header(parent_hash)?.is_some() &&
1793						!existing_body
1794					{
1795						let gap = BlockGap {
1796							start: number,
1797							end: number,
1798							gap_type: BlockGapType::MissingBody,
1799						};
1800						insert_new_gap(&mut transaction, gap, &mut block_gap);
1801						block_gap_updated = true;
1802						debug!(target: "db", "Detected block gap (fast sync) {block_gap:?}");
1803					}
1804				}
1805			}
1806
1807			meta_updates.push(MetaUpdate {
1808				hash,
1809				number,
1810				is_best: pending_block.leaf_state.is_best(),
1811				is_finalized: finalized,
1812				with_state: operation.commit_state,
1813			});
1814			Some((pending_block.header, hash))
1815		} else {
1816			None
1817		};
1818
1819		if let Some(set_head) = operation.set_head {
1820			if let Some(header) =
1821				sc_client_api::blockchain::HeaderBackend::header(&self.blockchain, set_head)?
1822			{
1823				let number = header.number();
1824				let hash = header.hash();
1825
1826				self.set_head_with_transaction(&mut transaction, hash, (*number, hash))?;
1827
1828				meta_updates.push(MetaUpdate {
1829					hash,
1830					number: *number,
1831					is_best: true,
1832					is_finalized: false,
1833					with_state: false,
1834				});
1835			} else {
1836				return Err(sp_blockchain::Error::UnknownBlock(format!(
1837					"Cannot set head {set_head:?}",
1838				)));
1839			}
1840		}
1841
1842		self.storage.db.commit(transaction)?;
1843
1844		// Apply all in-memory state changes.
1845		// Code beyond this point can't fail.
1846
1847		if let Some((header, hash)) = imported {
1848			trace!(target: "db", "DB Commit done {hash:?}");
1849			let header_metadata = CachedHeaderMetadata::from(&header);
1850			self.blockchain.insert_header_metadata(header_metadata.hash, header_metadata);
1851			cache_header(&mut self.blockchain.header_cache.lock(), hash, Some(header));
1852		}
1853
1854		for m in meta_updates {
1855			self.blockchain.update_meta(m);
1856		}
1857		if block_gap_updated {
1858			self.blockchain.update_block_gap(block_gap);
1859		}
1860
1861		Ok(())
1862	}
1863
1864	// Write stuff to a transaction after a new block is finalized. This canonicalizes finalized
1865	// blocks. Fails if called with a block which was not a child of the last finalized block.
1866	/// `remove_displaced` can be set to `false` if this is not the last of many subsequent calls
1867	/// for performance reasons.
1868	fn note_finalized(
1869		&self,
1870		transaction: &mut Transaction<DbHash>,
1871		f_header: &Block::Header,
1872		f_hash: Block::Hash,
1873		with_state: bool,
1874		current_transaction_justifications: &mut HashMap<Block::Hash, Justification>,
1875		remove_displaced: bool,
1876	) -> ClientResult<()> {
1877		let f_num = *f_header.number();
1878
1879		let lookup_key = utils::number_and_hash_to_lookup_key(f_num, f_hash)?;
1880		if with_state {
1881			transaction.set_from_vec(columns::META, meta_keys::FINALIZED_STATE, lookup_key.clone());
1882		}
1883		transaction.set_from_vec(columns::META, meta_keys::FINALIZED_BLOCK, lookup_key);
1884
1885		let requires_canonicalization = match self.storage.state_db.last_canonicalized() {
1886			LastCanonicalized::None => true,
1887			LastCanonicalized::Block(b) => f_num.saturated_into::<u64>() > b,
1888			LastCanonicalized::NotCanonicalizing => false,
1889		};
1890
1891		if requires_canonicalization && sc_client_api::Backend::have_state_at(self, f_hash, f_num) {
1892			let commit = self.storage.state_db.canonicalize_block(&f_hash).map_err(
1893				sp_blockchain::Error::from_state_db::<
1894					sc_state_db::Error<sp_database::error::DatabaseError>,
1895				>,
1896			)?;
1897			apply_state_commit(transaction, commit);
1898		}
1899
1900		if remove_displaced {
1901			let new_displaced = self.blockchain.displaced_leaves_after_finalizing(f_hash, f_num)?;
1902
1903			self.blockchain.leaves.write().remove_displaced_leaves(FinalizationOutcome::new(
1904				new_displaced.displaced_leaves.iter().copied(),
1905			));
1906
1907			if !matches!(self.blocks_pruning, BlocksPruning::KeepAll) {
1908				self.prune_displaced_branches(transaction, &new_displaced)?;
1909			}
1910		}
1911
1912		self.prune_blocks(transaction, f_num, current_transaction_justifications)?;
1913
1914		Ok(())
1915	}
1916
1917	fn prune_blocks(
1918		&self,
1919		transaction: &mut Transaction<DbHash>,
1920		finalized_number: NumberFor<Block>,
1921		current_transaction_justifications: &mut HashMap<Block::Hash, Justification>,
1922	) -> ClientResult<()> {
1923		if let BlocksPruning::Some(blocks_pruning) = self.blocks_pruning {
1924			// Always keep the last finalized block
1925			let keep = std::cmp::max(blocks_pruning, 1);
1926			if finalized_number >= keep.into() {
1927				let number = finalized_number.saturating_sub(keep.into());
1928
1929				// Before we prune a block, check if it is pinned
1930				if let Some(hash) = self.blockchain.hash(number)? {
1931					self.blockchain.insert_persisted_body_if_pinned(hash)?;
1932
1933					// If the block was finalized in this transaction, it will not be in the db
1934					// yet.
1935					if let Some(justification) = current_transaction_justifications.remove(&hash) {
1936						self.blockchain.insert_justifications_if_pinned(hash, justification);
1937					} else {
1938						self.blockchain.insert_persisted_justifications_if_pinned(hash)?;
1939					}
1940				};
1941
1942				self.prune_block(transaction, BlockId::<Block>::number(number))?;
1943			}
1944		}
1945		Ok(())
1946	}
1947
1948	fn prune_displaced_branches(
1949		&self,
1950		transaction: &mut Transaction<DbHash>,
1951		displaced: &DisplacedLeavesAfterFinalization<Block>,
1952	) -> ClientResult<()> {
1953		// Discard all blocks from displaced branches
1954		for &hash in displaced.displaced_blocks.iter() {
1955			self.blockchain.insert_persisted_body_if_pinned(hash)?;
1956			self.prune_block(transaction, BlockId::<Block>::hash(hash))?;
1957		}
1958		Ok(())
1959	}
1960
1961	fn prune_block(
1962		&self,
1963		transaction: &mut Transaction<DbHash>,
1964		id: BlockId<Block>,
1965	) -> ClientResult<()> {
1966		debug!(target: "db", "Removing block #{id}");
1967		utils::remove_from_db(
1968			transaction,
1969			&*self.storage.db,
1970			columns::KEY_LOOKUP,
1971			columns::BODY,
1972			id,
1973		)?;
1974		utils::remove_from_db(
1975			transaction,
1976			&*self.storage.db,
1977			columns::KEY_LOOKUP,
1978			columns::JUSTIFICATIONS,
1979			id,
1980		)?;
1981		if let Some(index) =
1982			read_db(&*self.storage.db, columns::KEY_LOOKUP, columns::BODY_INDEX, id)?
1983		{
1984			utils::remove_from_db(
1985				transaction,
1986				&*self.storage.db,
1987				columns::KEY_LOOKUP,
1988				columns::BODY_INDEX,
1989				id,
1990			)?;
1991			match Vec::<DbExtrinsic<Block>>::decode(&mut &index[..]) {
1992				Ok(index) =>
1993					for ex in index {
1994						if let DbExtrinsic::Indexed { hash, .. } = ex {
1995							transaction.release(columns::TRANSACTION, hash);
1996						}
1997					},
1998				Err(err) =>
1999					return Err(sp_blockchain::Error::Backend(format!(
2000						"Error decoding body list: {err}",
2001					))),
2002			}
2003		}
2004		Ok(())
2005	}
2006
2007	fn empty_state(&self) -> RecordStatsState<RefTrackingState<Block>, Block> {
2008		let root = EmptyStorage::<Block>::new().0; // Empty trie
2009		let db_state = DbStateBuilder::<HashingFor<Block>>::new(self.storage.clone(), root)
2010			.with_optional_cache(self.shared_trie_cache.as_ref().map(|c| c.local_cache_untrusted()))
2011			.build();
2012		let state = RefTrackingState::new(db_state, self.storage.clone(), None);
2013		RecordStatsState::new(state, None, self.state_usage.clone())
2014	}
2015}
2016
2017fn apply_state_commit(
2018	transaction: &mut Transaction<DbHash>,
2019	commit: sc_state_db::CommitSet<Vec<u8>>,
2020) {
2021	for (key, val) in commit.data.inserted.into_iter() {
2022		transaction.set_from_vec(columns::STATE, &key[..], val);
2023	}
2024	for key in commit.data.deleted.into_iter() {
2025		transaction.remove(columns::STATE, &key[..]);
2026	}
2027	for (key, val) in commit.meta.inserted.into_iter() {
2028		transaction.set_from_vec(columns::STATE_META, &key[..], val);
2029	}
2030	for key in commit.meta.deleted.into_iter() {
2031		transaction.remove(columns::STATE_META, &key[..]);
2032	}
2033}
2034
2035fn apply_index_ops<Block: BlockT>(
2036	transaction: &mut Transaction<DbHash>,
2037	body: Vec<Block::Extrinsic>,
2038	ops: Vec<IndexOperation>,
2039) -> Vec<u8> {
2040	let mut extrinsic_index: Vec<DbExtrinsic<Block>> = Vec::with_capacity(body.len());
2041	let mut index_map = HashMap::new();
2042	let mut renewed_map = HashMap::new();
2043	for op in ops {
2044		match op {
2045			IndexOperation::Insert { extrinsic, hash, size } => {
2046				index_map.insert(extrinsic, (hash, size));
2047			},
2048			IndexOperation::Renew { extrinsic, hash } => {
2049				renewed_map.insert(extrinsic, DbHash::from_slice(hash.as_ref()));
2050			},
2051		}
2052	}
2053	for (index, extrinsic) in body.into_iter().enumerate() {
2054		let db_extrinsic = if let Some(hash) = renewed_map.get(&(index as u32)) {
2055			// Bump ref counter
2056			let extrinsic = extrinsic.encode();
2057			transaction.reference(columns::TRANSACTION, DbHash::from_slice(hash.as_ref()));
2058			DbExtrinsic::Indexed { hash: *hash, header: extrinsic }
2059		} else {
2060			match index_map.get(&(index as u32)) {
2061				Some((hash, size)) => {
2062					let encoded = extrinsic.encode();
2063					if *size as usize <= encoded.len() {
2064						let offset = encoded.len() - *size as usize;
2065						transaction.store(
2066							columns::TRANSACTION,
2067							DbHash::from_slice(hash.as_ref()),
2068							encoded[offset..].to_vec(),
2069						);
2070						DbExtrinsic::Indexed {
2071							hash: DbHash::from_slice(hash.as_ref()),
2072							header: encoded[..offset].to_vec(),
2073						}
2074					} else {
2075						// Invalid indexed slice. Just store full data and don't index anything.
2076						DbExtrinsic::Full(extrinsic)
2077					}
2078				},
2079				_ => DbExtrinsic::Full(extrinsic),
2080			}
2081		};
2082		extrinsic_index.push(db_extrinsic);
2083	}
2084	debug!(
2085		target: "db",
2086		"DB transaction index: {} inserted, {} renewed, {} full",
2087		index_map.len(),
2088		renewed_map.len(),
2089		extrinsic_index.len() - index_map.len() - renewed_map.len(),
2090	);
2091	extrinsic_index.encode()
2092}
2093
2094fn apply_indexed_body<Block: BlockT>(transaction: &mut Transaction<DbHash>, body: Vec<Vec<u8>>) {
2095	for extrinsic in body {
2096		let hash = sp_runtime::traits::BlakeTwo256::hash(&extrinsic);
2097		transaction.store(columns::TRANSACTION, DbHash::from_slice(hash.as_ref()), extrinsic);
2098	}
2099}
2100
2101impl<Block> sc_client_api::backend::AuxStore for Backend<Block>
2102where
2103	Block: BlockT,
2104{
2105	fn insert_aux<
2106		'a,
2107		'b: 'a,
2108		'c: 'a,
2109		I: IntoIterator<Item = &'a (&'c [u8], &'c [u8])>,
2110		D: IntoIterator<Item = &'a &'b [u8]>,
2111	>(
2112		&self,
2113		insert: I,
2114		delete: D,
2115	) -> ClientResult<()> {
2116		let mut transaction = Transaction::new();
2117		for (k, v) in insert {
2118			transaction.set(columns::AUX, k, v);
2119		}
2120		for k in delete {
2121			transaction.remove(columns::AUX, k);
2122		}
2123		self.storage.db.commit(transaction)?;
2124		Ok(())
2125	}
2126
2127	fn get_aux(&self, key: &[u8]) -> ClientResult<Option<Vec<u8>>> {
2128		Ok(self.storage.db.get(columns::AUX, key))
2129	}
2130}
2131
2132impl<Block: BlockT> sc_client_api::backend::Backend<Block> for Backend<Block> {
2133	type BlockImportOperation = BlockImportOperation<Block>;
2134	type Blockchain = BlockchainDb<Block>;
2135	type State = RecordStatsState<RefTrackingState<Block>, Block>;
2136	type OffchainStorage = offchain::LocalStorage;
2137
2138	fn begin_operation(&self) -> ClientResult<Self::BlockImportOperation> {
2139		Ok(BlockImportOperation {
2140			pending_block: None,
2141			old_state: self.empty_state(),
2142			db_updates: PrefixedMemoryDB::default(),
2143			storage_updates: Default::default(),
2144			child_storage_updates: Default::default(),
2145			offchain_storage_updates: Default::default(),
2146			aux_ops: Vec::new(),
2147			finalized_blocks: Vec::new(),
2148			set_head: None,
2149			commit_state: false,
2150			create_gap: true,
2151			index_ops: Default::default(),
2152		})
2153	}
2154
2155	fn begin_state_operation(
2156		&self,
2157		operation: &mut Self::BlockImportOperation,
2158		block: Block::Hash,
2159	) -> ClientResult<()> {
2160		if block == Default::default() {
2161			operation.old_state = self.empty_state();
2162		} else {
2163			operation.old_state = self.state_at(block, TrieCacheContext::Untrusted)?;
2164		}
2165
2166		operation.commit_state = true;
2167		Ok(())
2168	}
2169
2170	fn commit_operation(&self, operation: Self::BlockImportOperation) -> ClientResult<()> {
2171		let usage = operation.old_state.usage_info();
2172		self.state_usage.merge_sm(usage);
2173
2174		if let Err(e) = self.try_commit_operation(operation) {
2175			let state_meta_db = StateMetaDb(self.storage.db.clone());
2176			self.storage
2177				.state_db
2178				.reset(state_meta_db)
2179				.map_err(sp_blockchain::Error::from_state_db)?;
2180			self.blockchain.clear_pinning_cache();
2181			Err(e)
2182		} else {
2183			self.storage.state_db.sync();
2184			Ok(())
2185		}
2186	}
2187
2188	fn finalize_block(
2189		&self,
2190		hash: Block::Hash,
2191		justification: Option<Justification>,
2192	) -> ClientResult<()> {
2193		let mut transaction = Transaction::new();
2194		let header = self.blockchain.expect_header(hash)?;
2195
2196		let mut current_transaction_justifications = HashMap::new();
2197		let m = self.finalize_block_with_transaction(
2198			&mut transaction,
2199			hash,
2200			&header,
2201			None,
2202			justification,
2203			&mut current_transaction_justifications,
2204			true,
2205		)?;
2206
2207		self.storage.db.commit(transaction)?;
2208		self.blockchain.update_meta(m);
2209		Ok(())
2210	}
2211
2212	fn append_justification(
2213		&self,
2214		hash: Block::Hash,
2215		justification: Justification,
2216	) -> ClientResult<()> {
2217		let mut transaction: Transaction<DbHash> = Transaction::new();
2218		let header = self.blockchain.expect_header(hash)?;
2219		let number = *header.number();
2220
2221		// Check if the block is finalized first.
2222		let is_descendent_of = is_descendent_of(&self.blockchain, None);
2223		let last_finalized = self.blockchain.last_finalized()?;
2224
2225		// We can do a quick check first, before doing a proper but more expensive check
2226		if number > self.blockchain.info().finalized_number ||
2227			(hash != last_finalized && !is_descendent_of(&hash, &last_finalized)?)
2228		{
2229			return Err(ClientError::NotInFinalizedChain);
2230		}
2231
2232		let justifications = if let Some(mut stored_justifications) =
2233			self.blockchain.justifications(hash)?
2234		{
2235			if !stored_justifications.append(justification) {
2236				return Err(ClientError::BadJustification("Duplicate consensus engine ID".into()));
2237			}
2238			stored_justifications
2239		} else {
2240			Justifications::from(justification)
2241		};
2242
2243		transaction.set_from_vec(
2244			columns::JUSTIFICATIONS,
2245			&utils::number_and_hash_to_lookup_key(number, hash)?,
2246			justifications.encode(),
2247		);
2248
2249		self.storage.db.commit(transaction)?;
2250
2251		Ok(())
2252	}
2253
2254	fn offchain_storage(&self) -> Option<Self::OffchainStorage> {
2255		Some(self.offchain_storage.clone())
2256	}
2257
2258	fn usage_info(&self) -> Option<UsageInfo> {
2259		let (io_stats, state_stats) = self.io_stats.take_or_else(|| {
2260			(
2261				// TODO: implement DB stats and cache size retrieval
2262				kvdb::IoStats::empty(),
2263				self.state_usage.take(),
2264			)
2265		});
2266		let database_cache = MemorySize::from_bytes(0);
2267		let state_cache = MemorySize::from_bytes(
2268			self.shared_trie_cache.as_ref().map_or(0, |c| c.used_memory_size()),
2269		);
2270
2271		Some(UsageInfo {
2272			memory: MemoryInfo { state_cache, database_cache },
2273			io: IoInfo {
2274				transactions: io_stats.transactions,
2275				bytes_read: io_stats.bytes_read,
2276				bytes_written: io_stats.bytes_written,
2277				writes: io_stats.writes,
2278				reads: io_stats.reads,
2279				average_transaction_size: io_stats.avg_transaction_size() as u64,
2280				state_reads: state_stats.reads.ops,
2281				state_writes: state_stats.writes.ops,
2282				state_writes_cache: state_stats.overlay_writes.ops,
2283				state_reads_cache: state_stats.cache_reads.ops,
2284				state_writes_nodes: state_stats.nodes_writes.ops,
2285			},
2286		})
2287	}
2288
2289	fn revert(
2290		&self,
2291		n: NumberFor<Block>,
2292		revert_finalized: bool,
2293	) -> ClientResult<(NumberFor<Block>, HashSet<Block::Hash>)> {
2294		let mut reverted_finalized = HashSet::new();
2295
2296		let info = self.blockchain.info();
2297
2298		let highest_leaf = self
2299			.blockchain
2300			.leaves
2301			.read()
2302			.highest_leaf()
2303			.and_then(|(n, h)| h.last().map(|h| (n, *h)));
2304
2305		let best_number = info.best_number;
2306		let best_hash = info.best_hash;
2307
2308		let finalized = info.finalized_number;
2309
2310		let revertible = best_number - finalized;
2311		let n = if !revert_finalized && revertible < n { revertible } else { n };
2312
2313		let (n, mut number_to_revert, mut hash_to_revert) = match highest_leaf {
2314			Some((l_n, l_h)) => (n + (l_n - best_number), l_n, l_h),
2315			None => (n, best_number, best_hash),
2316		};
2317
2318		let mut revert_blocks = || -> ClientResult<NumberFor<Block>> {
2319			for c in 0..n.saturated_into::<u64>() {
2320				if number_to_revert.is_zero() {
2321					return Ok(c.saturated_into::<NumberFor<Block>>());
2322				}
2323				let mut transaction = Transaction::new();
2324				let removed = self.blockchain.header(hash_to_revert)?.ok_or_else(|| {
2325					sp_blockchain::Error::UnknownBlock(format!(
2326						"Error reverting to {hash_to_revert}. Block header not found.",
2327					))
2328				})?;
2329				let removed_hash = removed.hash();
2330
2331				let prev_number = number_to_revert.saturating_sub(One::one());
2332				let prev_hash =
2333					if prev_number == best_number { best_hash } else { *removed.parent_hash() };
2334
2335				if !self.have_state_at(prev_hash, prev_number) {
2336					return Ok(c.saturated_into::<NumberFor<Block>>());
2337				}
2338
2339				match self.storage.state_db.revert_one() {
2340					Some(commit) => {
2341						apply_state_commit(&mut transaction, commit);
2342
2343						number_to_revert = prev_number;
2344						hash_to_revert = prev_hash;
2345
2346						let update_finalized = number_to_revert < finalized;
2347
2348						let key = utils::number_and_hash_to_lookup_key(
2349							number_to_revert,
2350							&hash_to_revert,
2351						)?;
2352						if update_finalized {
2353							transaction.set_from_vec(
2354								columns::META,
2355								meta_keys::FINALIZED_BLOCK,
2356								key.clone(),
2357							);
2358
2359							reverted_finalized.insert(removed_hash);
2360							if let Some((hash, _)) = self.blockchain.info().finalized_state {
2361								if hash == hash_to_revert {
2362									if !number_to_revert.is_zero() &&
2363										self.have_state_at(
2364											prev_hash,
2365											number_to_revert - One::one(),
2366										) {
2367										let lookup_key = utils::number_and_hash_to_lookup_key(
2368											number_to_revert - One::one(),
2369											prev_hash,
2370										)?;
2371										transaction.set_from_vec(
2372											columns::META,
2373											meta_keys::FINALIZED_STATE,
2374											lookup_key,
2375										);
2376									} else {
2377										transaction
2378											.remove(columns::META, meta_keys::FINALIZED_STATE);
2379									}
2380								}
2381							}
2382						}
2383						transaction.set_from_vec(columns::META, meta_keys::BEST_BLOCK, key);
2384						transaction.remove(columns::KEY_LOOKUP, removed.hash().as_ref());
2385						children::remove_children(
2386							&mut transaction,
2387							columns::META,
2388							meta_keys::CHILDREN_PREFIX,
2389							hash_to_revert,
2390						);
2391						self.storage.db.commit(transaction)?;
2392
2393						let is_best = number_to_revert < best_number;
2394
2395						self.blockchain.update_meta(MetaUpdate {
2396							hash: hash_to_revert,
2397							number: number_to_revert,
2398							is_best,
2399							is_finalized: update_finalized,
2400							with_state: false,
2401						});
2402					},
2403					None => return Ok(c.saturated_into::<NumberFor<Block>>()),
2404				}
2405			}
2406
2407			Ok(n)
2408		};
2409
2410		let reverted = revert_blocks()?;
2411
2412		let revert_leaves = || -> ClientResult<()> {
2413			let mut transaction = Transaction::new();
2414			let mut leaves = self.blockchain.leaves.write();
2415
2416			leaves.revert(hash_to_revert, number_to_revert);
2417			leaves.prepare_transaction(&mut transaction, columns::META, meta_keys::LEAF_PREFIX);
2418			self.storage.db.commit(transaction)?;
2419
2420			Ok(())
2421		};
2422
2423		revert_leaves()?;
2424
2425		Ok((reverted, reverted_finalized))
2426	}
2427
2428	fn remove_leaf_block(&self, hash: Block::Hash) -> ClientResult<()> {
2429		let best_hash = self.blockchain.info().best_hash;
2430
2431		if best_hash == hash {
2432			return Err(sp_blockchain::Error::Backend(format!("Can't remove best block {hash:?}")));
2433		}
2434
2435		let hdr = self.blockchain.header_metadata(hash)?;
2436		if !self.have_state_at(hash, hdr.number) {
2437			return Err(sp_blockchain::Error::UnknownBlock(format!(
2438				"State already discarded for {hash:?}",
2439			)));
2440		}
2441
2442		let mut leaves = self.blockchain.leaves.write();
2443		if !leaves.contains(hdr.number, hash) {
2444			return Err(sp_blockchain::Error::Backend(format!(
2445				"Can't remove non-leaf block {hash:?}",
2446			)));
2447		}
2448
2449		let mut transaction = Transaction::new();
2450		if let Some(commit) = self.storage.state_db.remove(&hash) {
2451			apply_state_commit(&mut transaction, commit);
2452		}
2453		transaction.remove(columns::KEY_LOOKUP, hash.as_ref());
2454
2455		let children: Vec<_> = self
2456			.blockchain()
2457			.children(hdr.parent)?
2458			.into_iter()
2459			.filter(|child_hash| *child_hash != hash)
2460			.collect();
2461		let parent_leaf = if children.is_empty() {
2462			children::remove_children(
2463				&mut transaction,
2464				columns::META,
2465				meta_keys::CHILDREN_PREFIX,
2466				hdr.parent,
2467			);
2468			Some(hdr.parent)
2469		} else {
2470			children::write_children(
2471				&mut transaction,
2472				columns::META,
2473				meta_keys::CHILDREN_PREFIX,
2474				hdr.parent,
2475				children,
2476			);
2477			None
2478		};
2479
2480		let remove_outcome = leaves.remove(hash, hdr.number, parent_leaf);
2481		leaves.prepare_transaction(&mut transaction, columns::META, meta_keys::LEAF_PREFIX);
2482		if let Err(e) = self.storage.db.commit(transaction) {
2483			if let Some(outcome) = remove_outcome {
2484				leaves.undo().undo_remove(outcome);
2485			}
2486			return Err(e.into());
2487		}
2488		self.blockchain().remove_header_metadata(hash);
2489		Ok(())
2490	}
2491
2492	fn blockchain(&self) -> &BlockchainDb<Block> {
2493		&self.blockchain
2494	}
2495
2496	fn state_at(
2497		&self,
2498		hash: Block::Hash,
2499		trie_cache_context: TrieCacheContext,
2500	) -> ClientResult<Self::State> {
2501		if hash == self.blockchain.meta.read().genesis_hash {
2502			if let Some(genesis_state) = &*self.genesis_state.read() {
2503				let root = genesis_state.root;
2504				let db_state =
2505					DbStateBuilder::<HashingFor<Block>>::new(genesis_state.clone(), root)
2506						.with_optional_cache(self.shared_trie_cache.as_ref().map(|c| {
2507							if matches!(trie_cache_context, TrieCacheContext::Trusted) {
2508								c.local_cache_trusted()
2509							} else {
2510								c.local_cache_untrusted()
2511							}
2512						}))
2513						.build();
2514
2515				let state = RefTrackingState::new(db_state, self.storage.clone(), None);
2516				return Ok(RecordStatsState::new(state, None, self.state_usage.clone()));
2517			}
2518		}
2519
2520		match self.blockchain.header_metadata(hash) {
2521			Ok(ref hdr) => {
2522				let hint = || {
2523					sc_state_db::NodeDb::get(self.storage.as_ref(), hdr.state_root.as_ref())
2524						.unwrap_or(None)
2525						.is_some()
2526				};
2527
2528				if let Ok(()) =
2529					self.storage.state_db.pin(&hash, hdr.number.saturated_into::<u64>(), hint)
2530				{
2531					let root = hdr.state_root;
2532					let db_state =
2533						DbStateBuilder::<HashingFor<Block>>::new(self.storage.clone(), root)
2534							.with_optional_cache(self.shared_trie_cache.as_ref().map(|c| {
2535								if matches!(trie_cache_context, TrieCacheContext::Trusted) {
2536									c.local_cache_trusted()
2537								} else {
2538									c.local_cache_untrusted()
2539								}
2540							}))
2541							.build();
2542					let state = RefTrackingState::new(db_state, self.storage.clone(), Some(hash));
2543					Ok(RecordStatsState::new(state, Some(hash), self.state_usage.clone()))
2544				} else {
2545					Err(sp_blockchain::Error::UnknownBlock(format!(
2546						"State already discarded for {hash:?}",
2547					)))
2548				}
2549			},
2550			Err(e) => Err(e),
2551		}
2552	}
2553
2554	fn have_state_at(&self, hash: Block::Hash, number: NumberFor<Block>) -> bool {
2555		if self.is_archive {
2556			match self.blockchain.header_metadata(hash) {
2557				Ok(header) => sp_state_machine::Storage::get(
2558					self.storage.as_ref(),
2559					&header.state_root,
2560					(&[], None),
2561				)
2562				.unwrap_or(None)
2563				.is_some(),
2564				_ => false,
2565			}
2566		} else {
2567			match self.storage.state_db.is_pruned(&hash, number.saturated_into::<u64>()) {
2568				IsPruned::Pruned => false,
2569				IsPruned::NotPruned => true,
2570				IsPruned::MaybePruned => match self.blockchain.header_metadata(hash) {
2571					Ok(header) => sp_state_machine::Storage::get(
2572						self.storage.as_ref(),
2573						&header.state_root,
2574						(&[], None),
2575					)
2576					.unwrap_or(None)
2577					.is_some(),
2578					_ => false,
2579				},
2580			}
2581		}
2582	}
2583
2584	fn get_import_lock(&self) -> &RwLock<()> {
2585		&self.import_lock
2586	}
2587
2588	fn requires_full_sync(&self) -> bool {
2589		matches!(
2590			self.storage.state_db.pruning_mode(),
2591			PruningMode::ArchiveAll | PruningMode::ArchiveCanonical
2592		)
2593	}
2594
2595	fn pin_block(&self, hash: <Block as BlockT>::Hash) -> sp_blockchain::Result<()> {
2596		let hint = || {
2597			let header_metadata = self.blockchain.header_metadata(hash);
2598			header_metadata
2599				.map(|hdr| {
2600					sc_state_db::NodeDb::get(self.storage.as_ref(), hdr.state_root.as_ref())
2601						.unwrap_or(None)
2602						.is_some()
2603				})
2604				.unwrap_or(false)
2605		};
2606
2607		if let Some(number) = self.blockchain.number(hash)? {
2608			self.storage.state_db.pin(&hash, number.saturated_into::<u64>(), hint).map_err(
2609				|_| {
2610					sp_blockchain::Error::UnknownBlock(format!(
2611						"Unable to pin: state already discarded for `{hash:?}`",
2612					))
2613				},
2614			)?;
2615		} else {
2616			return Err(ClientError::UnknownBlock(format!(
2617				"Can not pin block with hash `{hash:?}`. Block not found.",
2618			)));
2619		}
2620
2621		if self.blocks_pruning != BlocksPruning::KeepAll {
2622			// Only increase reference count for this hash. Value is loaded once we prune.
2623			self.blockchain.bump_ref(hash);
2624		}
2625		Ok(())
2626	}
2627
2628	fn unpin_block(&self, hash: <Block as BlockT>::Hash) {
2629		self.storage.state_db.unpin(&hash);
2630
2631		if self.blocks_pruning != BlocksPruning::KeepAll {
2632			self.blockchain.unpin(hash);
2633		}
2634	}
2635}
2636
2637impl<Block: BlockT> sc_client_api::backend::LocalBackend<Block> for Backend<Block> {}
2638
2639#[cfg(test)]
2640pub(crate) mod tests {
2641	use super::*;
2642	use crate::columns;
2643	use hash_db::{HashDB, EMPTY_PREFIX};
2644	use sc_client_api::{
2645		backend::{Backend as BTrait, BlockImportOperation as Op},
2646		blockchain::Backend as BLBTrait,
2647	};
2648	use sp_blockchain::{lowest_common_ancestor, tree_route};
2649	use sp_core::H256;
2650	use sp_runtime::{
2651		testing::{Block as RawBlock, Header, MockCallU64, TestXt},
2652		traits::{BlakeTwo256, Hash},
2653		ConsensusEngineId, StateVersion,
2654	};
2655
2656	const CONS0_ENGINE_ID: ConsensusEngineId = *b"CON0";
2657	const CONS1_ENGINE_ID: ConsensusEngineId = *b"CON1";
2658
2659	type UncheckedXt = TestXt<MockCallU64, ()>;
2660	pub(crate) type Block = RawBlock<UncheckedXt>;
2661
2662	pub fn insert_header(
2663		backend: &Backend<Block>,
2664		number: u64,
2665		parent_hash: H256,
2666		changes: Option<Vec<(Vec<u8>, Vec<u8>)>>,
2667		extrinsics_root: H256,
2668	) -> H256 {
2669		insert_block(backend, number, parent_hash, changes, extrinsics_root, Vec::new(), None)
2670			.unwrap()
2671	}
2672
2673	pub fn insert_block(
2674		backend: &Backend<Block>,
2675		number: u64,
2676		parent_hash: H256,
2677		_changes: Option<Vec<(Vec<u8>, Vec<u8>)>>,
2678		extrinsics_root: H256,
2679		body: Vec<UncheckedXt>,
2680		transaction_index: Option<Vec<IndexOperation>>,
2681	) -> Result<H256, sp_blockchain::Error> {
2682		use sp_runtime::testing::Digest;
2683
2684		let digest = Digest::default();
2685		let mut header =
2686			Header { number, parent_hash, state_root: Default::default(), digest, extrinsics_root };
2687
2688		let block_hash = if number == 0 { Default::default() } else { parent_hash };
2689		let mut op = backend.begin_operation().unwrap();
2690		backend.begin_state_operation(&mut op, block_hash).unwrap();
2691		if let Some(index) = transaction_index {
2692			op.update_transaction_index(index).unwrap();
2693		}
2694
2695		// Insert some fake data to ensure that the block can be found in the state column.
2696		let (root, overlay) = op.old_state.storage_root(
2697			vec![(block_hash.as_ref(), Some(block_hash.as_ref()))].into_iter(),
2698			StateVersion::V1,
2699		);
2700		op.update_db_storage(overlay).unwrap();
2701		header.state_root = root.into();
2702
2703		op.set_block_data(header.clone(), Some(body), None, None, NewBlockState::Best)
2704			.unwrap();
2705
2706		backend.commit_operation(op)?;
2707
2708		Ok(header.hash())
2709	}
2710
2711	pub fn insert_disconnected_header(
2712		backend: &Backend<Block>,
2713		number: u64,
2714		parent_hash: H256,
2715		extrinsics_root: H256,
2716		best: bool,
2717	) -> H256 {
2718		use sp_runtime::testing::Digest;
2719
2720		let digest = Digest::default();
2721		let header =
2722			Header { number, parent_hash, state_root: Default::default(), digest, extrinsics_root };
2723
2724		let mut op = backend.begin_operation().unwrap();
2725
2726		op.set_block_data(
2727			header.clone(),
2728			Some(vec![]),
2729			None,
2730			None,
2731			if best { NewBlockState::Best } else { NewBlockState::Normal },
2732		)
2733		.unwrap();
2734
2735		backend.commit_operation(op).unwrap();
2736
2737		header.hash()
2738	}
2739
2740	pub fn insert_header_no_head(
2741		backend: &Backend<Block>,
2742		number: u64,
2743		parent_hash: H256,
2744		extrinsics_root: H256,
2745	) -> H256 {
2746		use sp_runtime::testing::Digest;
2747
2748		let digest = Digest::default();
2749		let mut header =
2750			Header { number, parent_hash, state_root: Default::default(), digest, extrinsics_root };
2751		let mut op = backend.begin_operation().unwrap();
2752
2753		let root = backend
2754			.state_at(parent_hash, TrieCacheContext::Untrusted)
2755			.unwrap_or_else(|_| {
2756				if parent_hash == Default::default() {
2757					backend.empty_state()
2758				} else {
2759					panic!("Unknown block: {parent_hash:?}")
2760				}
2761			})
2762			.storage_root(
2763				vec![(parent_hash.as_ref(), Some(parent_hash.as_ref()))].into_iter(),
2764				StateVersion::V1,
2765			)
2766			.0;
2767		header.state_root = root.into();
2768
2769		op.set_block_data(header.clone(), None, None, None, NewBlockState::Normal)
2770			.unwrap();
2771		backend.commit_operation(op).unwrap();
2772
2773		header.hash()
2774	}
2775
2776	#[test]
2777	fn block_hash_inserted_correctly() {
2778		let backing = {
2779			let db = Backend::<Block>::new_test(1, 0);
2780			for i in 0..10 {
2781				assert!(db.blockchain().hash(i).unwrap().is_none());
2782
2783				{
2784					let hash = if i == 0 {
2785						Default::default()
2786					} else {
2787						db.blockchain.hash(i - 1).unwrap().unwrap()
2788					};
2789
2790					let mut op = db.begin_operation().unwrap();
2791					db.begin_state_operation(&mut op, hash).unwrap();
2792					let header = Header {
2793						number: i,
2794						parent_hash: hash,
2795						state_root: Default::default(),
2796						digest: Default::default(),
2797						extrinsics_root: Default::default(),
2798					};
2799
2800					op.set_block_data(header, Some(vec![]), None, None, NewBlockState::Best)
2801						.unwrap();
2802					db.commit_operation(op).unwrap();
2803				}
2804
2805				assert!(db.blockchain().hash(i).unwrap().is_some())
2806			}
2807			db.storage.db.clone()
2808		};
2809
2810		let backend = Backend::<Block>::new(
2811			DatabaseSettings {
2812				trie_cache_maximum_size: Some(16 * 1024 * 1024),
2813				state_pruning: Some(PruningMode::blocks_pruning(1)),
2814				source: DatabaseSource::Custom { db: backing, require_create_flag: false },
2815				blocks_pruning: BlocksPruning::KeepFinalized,
2816				metrics_registry: None,
2817			},
2818			0,
2819		)
2820		.unwrap();
2821		assert_eq!(backend.blockchain().info().best_number, 9);
2822		for i in 0..10 {
2823			assert!(backend.blockchain().hash(i).unwrap().is_some())
2824		}
2825	}
2826
2827	#[test]
2828	fn set_state_data() {
2829		set_state_data_inner(StateVersion::V0);
2830		set_state_data_inner(StateVersion::V1);
2831	}
2832	fn set_state_data_inner(state_version: StateVersion) {
2833		let db = Backend::<Block>::new_test(2, 0);
2834		let hash = {
2835			let mut op = db.begin_operation().unwrap();
2836			let mut header = Header {
2837				number: 0,
2838				parent_hash: Default::default(),
2839				state_root: Default::default(),
2840				digest: Default::default(),
2841				extrinsics_root: Default::default(),
2842			};
2843
2844			let storage = vec![(vec![1, 3, 5], vec![2, 4, 6]), (vec![1, 2, 3], vec![9, 9, 9])];
2845
2846			header.state_root = op
2847				.old_state
2848				.storage_root(storage.iter().map(|(x, y)| (&x[..], Some(&y[..]))), state_version)
2849				.0
2850				.into();
2851			let hash = header.hash();
2852
2853			op.reset_storage(
2854				Storage {
2855					top: storage.into_iter().collect(),
2856					children_default: Default::default(),
2857				},
2858				state_version,
2859			)
2860			.unwrap();
2861			op.set_block_data(header.clone(), Some(vec![]), None, None, NewBlockState::Best)
2862				.unwrap();
2863
2864			db.commit_operation(op).unwrap();
2865
2866			let state = db.state_at(hash, TrieCacheContext::Untrusted).unwrap();
2867
2868			assert_eq!(state.storage(&[1, 3, 5]).unwrap(), Some(vec![2, 4, 6]));
2869			assert_eq!(state.storage(&[1, 2, 3]).unwrap(), Some(vec![9, 9, 9]));
2870			assert_eq!(state.storage(&[5, 5, 5]).unwrap(), None);
2871
2872			hash
2873		};
2874
2875		{
2876			let mut op = db.begin_operation().unwrap();
2877			db.begin_state_operation(&mut op, hash).unwrap();
2878			let mut header = Header {
2879				number: 1,
2880				parent_hash: hash,
2881				state_root: Default::default(),
2882				digest: Default::default(),
2883				extrinsics_root: Default::default(),
2884			};
2885
2886			let storage = vec![(vec![1, 3, 5], None), (vec![5, 5, 5], Some(vec![4, 5, 6]))];
2887
2888			let (root, overlay) = op.old_state.storage_root(
2889				storage.iter().map(|(k, v)| (k.as_slice(), v.as_ref().map(|v| &v[..]))),
2890				state_version,
2891			);
2892			op.update_db_storage(overlay).unwrap();
2893			header.state_root = root.into();
2894
2895			op.update_storage(storage, Vec::new()).unwrap();
2896			op.set_block_data(header.clone(), Some(vec![]), None, None, NewBlockState::Best)
2897				.unwrap();
2898
2899			db.commit_operation(op).unwrap();
2900
2901			let state = db.state_at(header.hash(), TrieCacheContext::Untrusted).unwrap();
2902
2903			assert_eq!(state.storage(&[1, 3, 5]).unwrap(), None);
2904			assert_eq!(state.storage(&[1, 2, 3]).unwrap(), Some(vec![9, 9, 9]));
2905			assert_eq!(state.storage(&[5, 5, 5]).unwrap(), Some(vec![4, 5, 6]));
2906		}
2907	}
2908
2909	#[test]
2910	fn delete_only_when_negative_rc() {
2911		sp_tracing::try_init_simple();
2912		let state_version = StateVersion::default();
2913		let key;
2914		let backend = Backend::<Block>::new_test(1, 0);
2915
2916		let hash = {
2917			let mut op = backend.begin_operation().unwrap();
2918			backend.begin_state_operation(&mut op, Default::default()).unwrap();
2919			let mut header = Header {
2920				number: 0,
2921				parent_hash: Default::default(),
2922				state_root: Default::default(),
2923				digest: Default::default(),
2924				extrinsics_root: Default::default(),
2925			};
2926
2927			header.state_root =
2928				op.old_state.storage_root(std::iter::empty(), state_version).0.into();
2929			let hash = header.hash();
2930
2931			op.reset_storage(
2932				Storage { top: Default::default(), children_default: Default::default() },
2933				state_version,
2934			)
2935			.unwrap();
2936
2937			key = op.db_updates.insert(EMPTY_PREFIX, b"hello");
2938			op.set_block_data(header, Some(vec![]), None, None, NewBlockState::Best)
2939				.unwrap();
2940
2941			backend.commit_operation(op).unwrap();
2942			assert_eq!(
2943				backend
2944					.storage
2945					.db
2946					.get(columns::STATE, &sp_trie::prefixed_key::<BlakeTwo256>(&key, EMPTY_PREFIX))
2947					.unwrap(),
2948				&b"hello"[..]
2949			);
2950			hash
2951		};
2952
2953		let hashof1 = {
2954			let mut op = backend.begin_operation().unwrap();
2955			backend.begin_state_operation(&mut op, hash).unwrap();
2956			let mut header = Header {
2957				number: 1,
2958				parent_hash: hash,
2959				state_root: Default::default(),
2960				digest: Default::default(),
2961				extrinsics_root: Default::default(),
2962			};
2963
2964			let storage: Vec<(_, _)> = vec![];
2965
2966			header.state_root = op
2967				.old_state
2968				.storage_root(storage.iter().cloned().map(|(x, y)| (x, Some(y))), state_version)
2969				.0
2970				.into();
2971			let hash = header.hash();
2972
2973			op.db_updates.insert(EMPTY_PREFIX, b"hello");
2974			op.db_updates.remove(&key, EMPTY_PREFIX);
2975			op.set_block_data(header, Some(vec![]), None, None, NewBlockState::Best)
2976				.unwrap();
2977
2978			backend.commit_operation(op).unwrap();
2979			assert_eq!(
2980				backend
2981					.storage
2982					.db
2983					.get(columns::STATE, &sp_trie::prefixed_key::<BlakeTwo256>(&key, EMPTY_PREFIX))
2984					.unwrap(),
2985				&b"hello"[..]
2986			);
2987			hash
2988		};
2989
2990		let hashof2 = {
2991			let mut op = backend.begin_operation().unwrap();
2992			backend.begin_state_operation(&mut op, hashof1).unwrap();
2993			let mut header = Header {
2994				number: 2,
2995				parent_hash: hashof1,
2996				state_root: Default::default(),
2997				digest: Default::default(),
2998				extrinsics_root: Default::default(),
2999			};
3000
3001			let storage: Vec<(_, _)> = vec![];
3002
3003			header.state_root = op
3004				.old_state
3005				.storage_root(storage.iter().cloned().map(|(x, y)| (x, Some(y))), state_version)
3006				.0
3007				.into();
3008			let hash = header.hash();
3009
3010			op.db_updates.remove(&key, EMPTY_PREFIX);
3011			op.set_block_data(header, Some(vec![]), None, None, NewBlockState::Best)
3012				.unwrap();
3013
3014			backend.commit_operation(op).unwrap();
3015
3016			assert!(backend
3017				.storage
3018				.db
3019				.get(columns::STATE, &sp_trie::prefixed_key::<BlakeTwo256>(&key, EMPTY_PREFIX))
3020				.is_some());
3021			hash
3022		};
3023
3024		let hashof3 = {
3025			let mut op = backend.begin_operation().unwrap();
3026			backend.begin_state_operation(&mut op, hashof2).unwrap();
3027			let mut header = Header {
3028				number: 3,
3029				parent_hash: hashof2,
3030				state_root: Default::default(),
3031				digest: Default::default(),
3032				extrinsics_root: Default::default(),
3033			};
3034
3035			let storage: Vec<(_, _)> = vec![];
3036
3037			header.state_root = op
3038				.old_state
3039				.storage_root(storage.iter().cloned().map(|(x, y)| (x, Some(y))), state_version)
3040				.0
3041				.into();
3042			let hash = header.hash();
3043
3044			op.set_block_data(header, Some(vec![]), None, None, NewBlockState::Best)
3045				.unwrap();
3046
3047			backend.commit_operation(op).unwrap();
3048			hash
3049		};
3050
3051		let hashof4 = {
3052			let mut op = backend.begin_operation().unwrap();
3053			backend.begin_state_operation(&mut op, hashof3).unwrap();
3054			let mut header = Header {
3055				number: 4,
3056				parent_hash: hashof3,
3057				state_root: Default::default(),
3058				digest: Default::default(),
3059				extrinsics_root: Default::default(),
3060			};
3061
3062			let storage: Vec<(_, _)> = vec![];
3063
3064			header.state_root = op
3065				.old_state
3066				.storage_root(storage.iter().cloned().map(|(x, y)| (x, Some(y))), state_version)
3067				.0
3068				.into();
3069			let hash = header.hash();
3070
3071			op.set_block_data(header, Some(vec![]), None, None, NewBlockState::Best)
3072				.unwrap();
3073
3074			backend.commit_operation(op).unwrap();
3075			assert!(backend
3076				.storage
3077				.db
3078				.get(columns::STATE, &sp_trie::prefixed_key::<BlakeTwo256>(&key, EMPTY_PREFIX))
3079				.is_none());
3080			hash
3081		};
3082
3083		backend.finalize_block(hashof1, None).unwrap();
3084		backend.finalize_block(hashof2, None).unwrap();
3085		backend.finalize_block(hashof3, None).unwrap();
3086		backend.finalize_block(hashof4, None).unwrap();
3087		assert!(backend
3088			.storage
3089			.db
3090			.get(columns::STATE, &sp_trie::prefixed_key::<BlakeTwo256>(&key, EMPTY_PREFIX))
3091			.is_none());
3092	}
3093
3094	#[test]
3095	fn tree_route_works() {
3096		let backend = Backend::<Block>::new_test(1000, 100);
3097		let blockchain = backend.blockchain();
3098		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
3099
3100		// fork from genesis: 3 prong.
3101		let a1 = insert_header(&backend, 1, block0, None, Default::default());
3102		let a2 = insert_header(&backend, 2, a1, None, Default::default());
3103		let a3 = insert_header(&backend, 3, a2, None, Default::default());
3104
3105		// fork from genesis: 2 prong.
3106		let b1 = insert_header(&backend, 1, block0, None, H256::from([1; 32]));
3107		let b2 = insert_header(&backend, 2, b1, None, Default::default());
3108
3109		{
3110			let tree_route = tree_route(blockchain, a1, a1).unwrap();
3111
3112			assert_eq!(tree_route.common_block().hash, a1);
3113			assert!(tree_route.retracted().is_empty());
3114			assert!(tree_route.enacted().is_empty());
3115		}
3116
3117		{
3118			let tree_route = tree_route(blockchain, a3, b2).unwrap();
3119
3120			assert_eq!(tree_route.common_block().hash, block0);
3121			assert_eq!(
3122				tree_route.retracted().iter().map(|r| r.hash).collect::<Vec<_>>(),
3123				vec![a3, a2, a1]
3124			);
3125			assert_eq!(
3126				tree_route.enacted().iter().map(|r| r.hash).collect::<Vec<_>>(),
3127				vec![b1, b2]
3128			);
3129		}
3130
3131		{
3132			let tree_route = tree_route(blockchain, a1, a3).unwrap();
3133
3134			assert_eq!(tree_route.common_block().hash, a1);
3135			assert!(tree_route.retracted().is_empty());
3136			assert_eq!(
3137				tree_route.enacted().iter().map(|r| r.hash).collect::<Vec<_>>(),
3138				vec![a2, a3]
3139			);
3140		}
3141
3142		{
3143			let tree_route = tree_route(blockchain, a3, a1).unwrap();
3144
3145			assert_eq!(tree_route.common_block().hash, a1);
3146			assert_eq!(
3147				tree_route.retracted().iter().map(|r| r.hash).collect::<Vec<_>>(),
3148				vec![a3, a2]
3149			);
3150			assert!(tree_route.enacted().is_empty());
3151		}
3152
3153		{
3154			let tree_route = tree_route(blockchain, a2, a2).unwrap();
3155
3156			assert_eq!(tree_route.common_block().hash, a2);
3157			assert!(tree_route.retracted().is_empty());
3158			assert!(tree_route.enacted().is_empty());
3159		}
3160	}
3161
3162	#[test]
3163	fn tree_route_child() {
3164		let backend = Backend::<Block>::new_test(1000, 100);
3165		let blockchain = backend.blockchain();
3166
3167		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
3168		let block1 = insert_header(&backend, 1, block0, None, Default::default());
3169
3170		{
3171			let tree_route = tree_route(blockchain, block0, block1).unwrap();
3172
3173			assert_eq!(tree_route.common_block().hash, block0);
3174			assert!(tree_route.retracted().is_empty());
3175			assert_eq!(
3176				tree_route.enacted().iter().map(|r| r.hash).collect::<Vec<_>>(),
3177				vec![block1]
3178			);
3179		}
3180	}
3181
3182	#[test]
3183	fn lowest_common_ancestor_works() {
3184		let backend = Backend::<Block>::new_test(1000, 100);
3185		let blockchain = backend.blockchain();
3186		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
3187
3188		// fork from genesis: 3 prong.
3189		let a1 = insert_header(&backend, 1, block0, None, Default::default());
3190		let a2 = insert_header(&backend, 2, a1, None, Default::default());
3191		let a3 = insert_header(&backend, 3, a2, None, Default::default());
3192
3193		// fork from genesis: 2 prong.
3194		let b1 = insert_header(&backend, 1, block0, None, H256::from([1; 32]));
3195		let b2 = insert_header(&backend, 2, b1, None, Default::default());
3196
3197		{
3198			let lca = lowest_common_ancestor(blockchain, a3, b2).unwrap();
3199
3200			assert_eq!(lca.hash, block0);
3201			assert_eq!(lca.number, 0);
3202		}
3203
3204		{
3205			let lca = lowest_common_ancestor(blockchain, a1, a3).unwrap();
3206
3207			assert_eq!(lca.hash, a1);
3208			assert_eq!(lca.number, 1);
3209		}
3210
3211		{
3212			let lca = lowest_common_ancestor(blockchain, a3, a1).unwrap();
3213
3214			assert_eq!(lca.hash, a1);
3215			assert_eq!(lca.number, 1);
3216		}
3217
3218		{
3219			let lca = lowest_common_ancestor(blockchain, a2, a3).unwrap();
3220
3221			assert_eq!(lca.hash, a2);
3222			assert_eq!(lca.number, 2);
3223		}
3224
3225		{
3226			let lca = lowest_common_ancestor(blockchain, a2, a1).unwrap();
3227
3228			assert_eq!(lca.hash, a1);
3229			assert_eq!(lca.number, 1);
3230		}
3231
3232		{
3233			let lca = lowest_common_ancestor(blockchain, a2, a2).unwrap();
3234
3235			assert_eq!(lca.hash, a2);
3236			assert_eq!(lca.number, 2);
3237		}
3238	}
3239
3240	#[test]
3241	fn displaced_leaves_after_finalizing_works_with_disconnect() {
3242		// In this test we will create a situation that can typically happen after warp sync.
3243		// The situation looks like this:
3244		// g -> <unimported> -> a3 -> a4
3245		// Basically there is a gap of unimported blocks at some point in the chain.
3246		let backend = Backend::<Block>::new_test(1000, 100);
3247		let blockchain = backend.blockchain();
3248		let genesis_number = 0;
3249		let genesis_hash =
3250			insert_header(&backend, genesis_number, Default::default(), None, Default::default());
3251
3252		let a3_number = 3;
3253		let a3_hash = insert_disconnected_header(
3254			&backend,
3255			a3_number,
3256			H256::from([200; 32]),
3257			H256::from([1; 32]),
3258			true,
3259		);
3260
3261		let a4_number = 4;
3262		let a4_hash =
3263			insert_disconnected_header(&backend, a4_number, a3_hash, H256::from([2; 32]), true);
3264		{
3265			let displaced =
3266				blockchain.displaced_leaves_after_finalizing(a3_hash, a3_number).unwrap();
3267			assert_eq!(blockchain.leaves().unwrap(), vec![a4_hash, genesis_hash]);
3268			assert_eq!(displaced.displaced_leaves, vec![(genesis_number, genesis_hash)]);
3269			assert_eq!(displaced.displaced_blocks, vec![]);
3270		}
3271
3272		{
3273			let displaced =
3274				blockchain.displaced_leaves_after_finalizing(a4_hash, a4_number).unwrap();
3275			assert_eq!(blockchain.leaves().unwrap(), vec![a4_hash, genesis_hash]);
3276			assert_eq!(displaced.displaced_leaves, vec![(genesis_number, genesis_hash)]);
3277			assert_eq!(displaced.displaced_blocks, vec![]);
3278		}
3279
3280		// Import block a1 which has the genesis block as parent.
3281		// g -> a1 -> <unimported> -> a3(f) -> a4
3282		let a1_number = 1;
3283		let a1_hash = insert_disconnected_header(
3284			&backend,
3285			a1_number,
3286			genesis_hash,
3287			H256::from([123; 32]),
3288			false,
3289		);
3290		{
3291			let displaced =
3292				blockchain.displaced_leaves_after_finalizing(a3_hash, a3_number).unwrap();
3293			assert_eq!(blockchain.leaves().unwrap(), vec![a4_hash, a1_hash]);
3294			assert_eq!(displaced.displaced_leaves, vec![]);
3295			assert_eq!(displaced.displaced_blocks, vec![]);
3296		}
3297
3298		// Import block b1 which has the genesis block as parent.
3299		// g -> a1 -> <unimported> -> a3(f) -> a4
3300		//  \-> b1
3301		let b1_number = 1;
3302		let b1_hash = insert_disconnected_header(
3303			&backend,
3304			b1_number,
3305			genesis_hash,
3306			H256::from([124; 32]),
3307			false,
3308		);
3309		{
3310			let displaced =
3311				blockchain.displaced_leaves_after_finalizing(a3_hash, a3_number).unwrap();
3312			assert_eq!(blockchain.leaves().unwrap(), vec![a4_hash, a1_hash, b1_hash]);
3313			assert_eq!(displaced.displaced_leaves, vec![]);
3314			assert_eq!(displaced.displaced_blocks, vec![]);
3315		}
3316
3317		// If branch of b blocks is higher in number than a branch, we
3318		// should still not prune disconnected leafs.
3319		// g -> a1 -> <unimported> -> a3(f) -> a4
3320		//  \-> b1 -> b2 ----------> b3 ----> b4 -> b5
3321		let b2_number = 2;
3322		let b2_hash =
3323			insert_disconnected_header(&backend, b2_number, b1_hash, H256::from([40; 32]), false);
3324		let b3_number = 3;
3325		let b3_hash =
3326			insert_disconnected_header(&backend, b3_number, b2_hash, H256::from([41; 32]), false);
3327		let b4_number = 4;
3328		let b4_hash =
3329			insert_disconnected_header(&backend, b4_number, b3_hash, H256::from([42; 32]), false);
3330		let b5_number = 5;
3331		let b5_hash =
3332			insert_disconnected_header(&backend, b5_number, b4_hash, H256::from([43; 32]), false);
3333		{
3334			let displaced =
3335				blockchain.displaced_leaves_after_finalizing(a3_hash, a3_number).unwrap();
3336			assert_eq!(blockchain.leaves().unwrap(), vec![b5_hash, a4_hash, a1_hash]);
3337			assert_eq!(displaced.displaced_leaves, vec![]);
3338			assert_eq!(displaced.displaced_blocks, vec![]);
3339		}
3340
3341		// Even though there is a disconnect, diplace should still detect
3342		// branches above the block gap.
3343		//                              /-> c4
3344		// g -> a1 -> <unimported> -> a3 -> a4(f)
3345		//  \-> b1 -> b2 ----------> b3 -> b4 -> b5
3346		let c4_number = 4;
3347		let c4_hash =
3348			insert_disconnected_header(&backend, c4_number, a3_hash, H256::from([44; 32]), false);
3349		{
3350			let displaced =
3351				blockchain.displaced_leaves_after_finalizing(a4_hash, a4_number).unwrap();
3352			assert_eq!(blockchain.leaves().unwrap(), vec![b5_hash, a4_hash, c4_hash, a1_hash]);
3353			assert_eq!(displaced.displaced_leaves, vec![(c4_number, c4_hash)]);
3354			assert_eq!(displaced.displaced_blocks, vec![c4_hash]);
3355		}
3356	}
3357	#[test]
3358	fn displaced_leaves_after_finalizing_works() {
3359		let backend = Backend::<Block>::new_test(1000, 100);
3360		let blockchain = backend.blockchain();
3361		let genesis_number = 0;
3362		let genesis_hash =
3363			insert_header(&backend, genesis_number, Default::default(), None, Default::default());
3364
3365		// fork from genesis: 3 prong.
3366		// block 0 -> a1 -> a2 -> a3
3367		//        \
3368		//         -> b1 -> b2 -> c1 -> c2
3369		//              \
3370		//               -> d1 -> d2
3371		let a1_number = 1;
3372		let a1_hash = insert_header(&backend, a1_number, genesis_hash, None, Default::default());
3373		let a2_number = 2;
3374		let a2_hash = insert_header(&backend, a2_number, a1_hash, None, Default::default());
3375		let a3_number = 3;
3376		let a3_hash = insert_header(&backend, a3_number, a2_hash, None, Default::default());
3377
3378		{
3379			let displaced = blockchain
3380				.displaced_leaves_after_finalizing(genesis_hash, genesis_number)
3381				.unwrap();
3382			assert_eq!(displaced.displaced_leaves, vec![]);
3383			assert_eq!(displaced.displaced_blocks, vec![]);
3384		}
3385		{
3386			let displaced_a1 =
3387				blockchain.displaced_leaves_after_finalizing(a1_hash, a1_number).unwrap();
3388			assert_eq!(displaced_a1.displaced_leaves, vec![]);
3389			assert_eq!(displaced_a1.displaced_blocks, vec![]);
3390
3391			let displaced_a2 =
3392				blockchain.displaced_leaves_after_finalizing(a2_hash, a3_number).unwrap();
3393			assert_eq!(displaced_a2.displaced_leaves, vec![]);
3394			assert_eq!(displaced_a2.displaced_blocks, vec![]);
3395
3396			let displaced_a3 =
3397				blockchain.displaced_leaves_after_finalizing(a3_hash, a3_number).unwrap();
3398			assert_eq!(displaced_a3.displaced_leaves, vec![]);
3399			assert_eq!(displaced_a3.displaced_blocks, vec![]);
3400		}
3401		{
3402			// Finalized block is above leaves and not imported yet.
3403			// We will not be able to make a connection,
3404			// nothing can be marked as displaced.
3405			let displaced =
3406				blockchain.displaced_leaves_after_finalizing(H256::from([57; 32]), 10).unwrap();
3407			assert_eq!(displaced.displaced_leaves, vec![]);
3408			assert_eq!(displaced.displaced_blocks, vec![]);
3409		}
3410
3411		// fork from genesis: 2 prong.
3412		let b1_number = 1;
3413		let b1_hash = insert_header(&backend, b1_number, genesis_hash, None, H256::from([1; 32]));
3414		let b2_number = 2;
3415		let b2_hash = insert_header(&backend, b2_number, b1_hash, None, Default::default());
3416
3417		// fork from b2.
3418		let c1_number = 3;
3419		let c1_hash = insert_header(&backend, c1_number, b2_hash, None, H256::from([2; 32]));
3420		let c2_number = 4;
3421		let c2_hash = insert_header(&backend, c2_number, c1_hash, None, Default::default());
3422
3423		// fork from b1.
3424		let d1_number = 2;
3425		let d1_hash = insert_header(&backend, d1_number, b1_hash, None, H256::from([3; 32]));
3426		let d2_number = 3;
3427		let d2_hash = insert_header(&backend, d2_number, d1_hash, None, Default::default());
3428
3429		{
3430			let displaced_a1 =
3431				blockchain.displaced_leaves_after_finalizing(a1_hash, a1_number).unwrap();
3432			assert_eq!(
3433				displaced_a1.displaced_leaves,
3434				vec![(c2_number, c2_hash), (d2_number, d2_hash)]
3435			);
3436			let mut displaced_blocks = vec![b1_hash, b2_hash, c1_hash, c2_hash, d1_hash, d2_hash];
3437			displaced_blocks.sort();
3438			assert_eq!(displaced_a1.displaced_blocks, displaced_blocks);
3439
3440			let displaced_a2 =
3441				blockchain.displaced_leaves_after_finalizing(a2_hash, a2_number).unwrap();
3442			assert_eq!(displaced_a1.displaced_leaves, displaced_a2.displaced_leaves);
3443			assert_eq!(displaced_a1.displaced_blocks, displaced_a2.displaced_blocks);
3444
3445			let displaced_a3 =
3446				blockchain.displaced_leaves_after_finalizing(a3_hash, a3_number).unwrap();
3447			assert_eq!(displaced_a1.displaced_leaves, displaced_a3.displaced_leaves);
3448			assert_eq!(displaced_a1.displaced_blocks, displaced_a3.displaced_blocks);
3449		}
3450		{
3451			let displaced =
3452				blockchain.displaced_leaves_after_finalizing(b1_hash, b1_number).unwrap();
3453			assert_eq!(displaced.displaced_leaves, vec![(a3_number, a3_hash)]);
3454			let mut displaced_blocks = vec![a1_hash, a2_hash, a3_hash];
3455			displaced_blocks.sort();
3456			assert_eq!(displaced.displaced_blocks, displaced_blocks);
3457		}
3458		{
3459			let displaced =
3460				blockchain.displaced_leaves_after_finalizing(b2_hash, b2_number).unwrap();
3461			assert_eq!(
3462				displaced.displaced_leaves,
3463				vec![(a3_number, a3_hash), (d2_number, d2_hash)]
3464			);
3465			let mut displaced_blocks = vec![a1_hash, a2_hash, a3_hash, d1_hash, d2_hash];
3466			displaced_blocks.sort();
3467			assert_eq!(displaced.displaced_blocks, displaced_blocks);
3468		}
3469		{
3470			let displaced =
3471				blockchain.displaced_leaves_after_finalizing(c2_hash, c2_number).unwrap();
3472			assert_eq!(
3473				displaced.displaced_leaves,
3474				vec![(a3_number, a3_hash), (d2_number, d2_hash)]
3475			);
3476			let mut displaced_blocks = vec![a1_hash, a2_hash, a3_hash, d1_hash, d2_hash];
3477			displaced_blocks.sort();
3478			assert_eq!(displaced.displaced_blocks, displaced_blocks);
3479		}
3480	}
3481
3482	#[test]
3483	fn test_tree_route_regression() {
3484		// NOTE: this is a test for a regression introduced in #3665, the result
3485		// of tree_route would be erroneously computed, since it was taking into
3486		// account the `ancestor` in `CachedHeaderMetadata` for the comparison.
3487		// in this test we simulate the same behavior with the side-effect
3488		// triggering the issue being eviction of a previously fetched record
3489		// from the cache, therefore this test is dependent on the LRU cache
3490		// size for header metadata, which is currently set to 5000 elements.
3491		let backend = Backend::<Block>::new_test(10000, 10000);
3492		let blockchain = backend.blockchain();
3493
3494		let genesis = insert_header(&backend, 0, Default::default(), None, Default::default());
3495
3496		let block100 = (1..=100).fold(genesis, |parent, n| {
3497			insert_header(&backend, n, parent, None, Default::default())
3498		});
3499
3500		let block7000 = (101..=7000).fold(block100, |parent, n| {
3501			insert_header(&backend, n, parent, None, Default::default())
3502		});
3503
3504		// This will cause the ancestor of `block100` to be set to `genesis` as a side-effect.
3505		lowest_common_ancestor(blockchain, genesis, block100).unwrap();
3506
3507		// While traversing the tree we will have to do 6900 calls to
3508		// `header_metadata`, which will make sure we will exhaust our cache
3509		// which only takes 5000 elements. In particular, the `CachedHeaderMetadata` struct for
3510		// block #100 will be evicted and will get a new value (with ancestor set to its parent).
3511		let tree_route = tree_route(blockchain, block100, block7000).unwrap();
3512
3513		assert!(tree_route.retracted().is_empty());
3514	}
3515
3516	#[test]
3517	fn test_leaves_with_complex_block_tree() {
3518		let backend: Arc<Backend<substrate_test_runtime_client::runtime::Block>> =
3519			Arc::new(Backend::new_test(20, 20));
3520		substrate_test_runtime_client::trait_tests::test_leaves_for_backend(backend);
3521	}
3522
3523	#[test]
3524	fn test_children_with_complex_block_tree() {
3525		let backend: Arc<Backend<substrate_test_runtime_client::runtime::Block>> =
3526			Arc::new(Backend::new_test(20, 20));
3527		substrate_test_runtime_client::trait_tests::test_children_for_backend(backend);
3528	}
3529
3530	#[test]
3531	fn test_blockchain_query_by_number_gets_canonical() {
3532		let backend: Arc<Backend<substrate_test_runtime_client::runtime::Block>> =
3533			Arc::new(Backend::new_test(20, 20));
3534		substrate_test_runtime_client::trait_tests::test_blockchain_query_by_number_gets_canonical(
3535			backend,
3536		);
3537	}
3538
3539	#[test]
3540	fn test_leaves_pruned_on_finality() {
3541		//   / 1b - 2b - 3b
3542		// 0 - 1a - 2a
3543		//   \ 1c
3544		let backend: Backend<Block> = Backend::new_test(10, 10);
3545		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
3546
3547		let block1_a = insert_header(&backend, 1, block0, None, Default::default());
3548		let block1_b = insert_header(&backend, 1, block0, None, [1; 32].into());
3549		let block1_c = insert_header(&backend, 1, block0, None, [2; 32].into());
3550
3551		assert_eq!(backend.blockchain().leaves().unwrap(), vec![block1_a, block1_b, block1_c]);
3552
3553		let block2_a = insert_header(&backend, 2, block1_a, None, Default::default());
3554		let block2_b = insert_header(&backend, 2, block1_b, None, Default::default());
3555
3556		let block3_b = insert_header(&backend, 3, block2_b, None, [3; 32].into());
3557
3558		assert_eq!(backend.blockchain().leaves().unwrap(), vec![block3_b, block2_a, block1_c]);
3559
3560		backend.finalize_block(block1_a, None).unwrap();
3561		backend.finalize_block(block2_a, None).unwrap();
3562
3563		// All leaves are pruned that are known to not belong to canonical branch
3564		assert_eq!(backend.blockchain().leaves().unwrap(), vec![block2_a]);
3565	}
3566
3567	#[test]
3568	fn test_aux() {
3569		let backend: Backend<substrate_test_runtime_client::runtime::Block> =
3570			Backend::new_test(0, 0);
3571		assert!(backend.get_aux(b"test").unwrap().is_none());
3572		backend.insert_aux(&[(&b"test"[..], &b"hello"[..])], &[]).unwrap();
3573		assert_eq!(b"hello", &backend.get_aux(b"test").unwrap().unwrap()[..]);
3574		backend.insert_aux(&[], &[&b"test"[..]]).unwrap();
3575		assert!(backend.get_aux(b"test").unwrap().is_none());
3576	}
3577
3578	#[test]
3579	fn test_finalize_block_with_justification() {
3580		use sc_client_api::blockchain::Backend as BlockChainBackend;
3581
3582		let backend = Backend::<Block>::new_test(10, 10);
3583
3584		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
3585		let block1 = insert_header(&backend, 1, block0, None, Default::default());
3586
3587		let justification = Some((CONS0_ENGINE_ID, vec![1, 2, 3]));
3588		backend.finalize_block(block1, justification.clone()).unwrap();
3589
3590		assert_eq!(
3591			backend.blockchain().justifications(block1).unwrap(),
3592			justification.map(Justifications::from),
3593		);
3594	}
3595
3596	#[test]
3597	fn test_append_justification_to_finalized_block() {
3598		use sc_client_api::blockchain::Backend as BlockChainBackend;
3599
3600		let backend = Backend::<Block>::new_test(10, 10);
3601
3602		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
3603		let block1 = insert_header(&backend, 1, block0, None, Default::default());
3604
3605		let just0 = (CONS0_ENGINE_ID, vec![1, 2, 3]);
3606		backend.finalize_block(block1, Some(just0.clone().into())).unwrap();
3607
3608		let just1 = (CONS1_ENGINE_ID, vec![4, 5]);
3609		backend.append_justification(block1, just1.clone()).unwrap();
3610
3611		let just2 = (CONS1_ENGINE_ID, vec![6, 7]);
3612		assert!(matches!(
3613			backend.append_justification(block1, just2),
3614			Err(ClientError::BadJustification(_))
3615		));
3616
3617		let justifications = {
3618			let mut just = Justifications::from(just0);
3619			just.append(just1);
3620			just
3621		};
3622		assert_eq!(backend.blockchain().justifications(block1).unwrap(), Some(justifications),);
3623	}
3624
3625	#[test]
3626	fn test_finalize_multiple_blocks_in_single_op() {
3627		let backend = Backend::<Block>::new_test(10, 10);
3628
3629		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
3630		let block1 = insert_header(&backend, 1, block0, None, Default::default());
3631		let block2 = insert_header(&backend, 2, block1, None, Default::default());
3632		let block3 = insert_header(&backend, 3, block2, None, Default::default());
3633		let block4 = insert_header(&backend, 4, block3, None, Default::default());
3634		{
3635			let mut op = backend.begin_operation().unwrap();
3636			backend.begin_state_operation(&mut op, block0).unwrap();
3637			op.mark_finalized(block1, None).unwrap();
3638			op.mark_finalized(block2, None).unwrap();
3639			backend.commit_operation(op).unwrap();
3640		}
3641		{
3642			let mut op = backend.begin_operation().unwrap();
3643			backend.begin_state_operation(&mut op, block2).unwrap();
3644			op.mark_finalized(block3, None).unwrap();
3645			op.mark_finalized(block4, None).unwrap();
3646			backend.commit_operation(op).unwrap();
3647		}
3648	}
3649
3650	#[test]
3651	fn storage_hash_is_cached_correctly() {
3652		let state_version = StateVersion::default();
3653		let backend = Backend::<Block>::new_test(10, 10);
3654
3655		let hash0 = {
3656			let mut op = backend.begin_operation().unwrap();
3657			backend.begin_state_operation(&mut op, Default::default()).unwrap();
3658			let mut header = Header {
3659				number: 0,
3660				parent_hash: Default::default(),
3661				state_root: Default::default(),
3662				digest: Default::default(),
3663				extrinsics_root: Default::default(),
3664			};
3665
3666			let storage = vec![(b"test".to_vec(), b"test".to_vec())];
3667
3668			header.state_root = op
3669				.old_state
3670				.storage_root(storage.iter().map(|(x, y)| (&x[..], Some(&y[..]))), state_version)
3671				.0
3672				.into();
3673			let hash = header.hash();
3674
3675			op.reset_storage(
3676				Storage {
3677					top: storage.into_iter().collect(),
3678					children_default: Default::default(),
3679				},
3680				state_version,
3681			)
3682			.unwrap();
3683			op.set_block_data(header.clone(), Some(vec![]), None, None, NewBlockState::Best)
3684				.unwrap();
3685
3686			backend.commit_operation(op).unwrap();
3687
3688			hash
3689		};
3690
3691		let block0_hash = backend
3692			.state_at(hash0, TrieCacheContext::Untrusted)
3693			.unwrap()
3694			.storage_hash(&b"test"[..])
3695			.unwrap();
3696
3697		let hash1 = {
3698			let mut op = backend.begin_operation().unwrap();
3699			backend.begin_state_operation(&mut op, hash0).unwrap();
3700			let mut header = Header {
3701				number: 1,
3702				parent_hash: hash0,
3703				state_root: Default::default(),
3704				digest: Default::default(),
3705				extrinsics_root: Default::default(),
3706			};
3707
3708			let storage = vec![(b"test".to_vec(), Some(b"test2".to_vec()))];
3709
3710			let (root, overlay) = op.old_state.storage_root(
3711				storage.iter().map(|(k, v)| (k.as_slice(), v.as_ref().map(|v| &v[..]))),
3712				state_version,
3713			);
3714			op.update_db_storage(overlay).unwrap();
3715			header.state_root = root.into();
3716			let hash = header.hash();
3717
3718			op.update_storage(storage, Vec::new()).unwrap();
3719			op.set_block_data(header, Some(vec![]), None, None, NewBlockState::Normal)
3720				.unwrap();
3721
3722			backend.commit_operation(op).unwrap();
3723
3724			hash
3725		};
3726
3727		{
3728			let header = backend.blockchain().header(hash1).unwrap().unwrap();
3729			let mut op = backend.begin_operation().unwrap();
3730			op.set_block_data(header, None, None, None, NewBlockState::Best).unwrap();
3731			backend.commit_operation(op).unwrap();
3732		}
3733
3734		let block1_hash = backend
3735			.state_at(hash1, TrieCacheContext::Untrusted)
3736			.unwrap()
3737			.storage_hash(&b"test"[..])
3738			.unwrap();
3739
3740		assert_ne!(block0_hash, block1_hash);
3741	}
3742
3743	#[test]
3744	fn test_finalize_non_sequential() {
3745		let backend = Backend::<Block>::new_test(10, 10);
3746
3747		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
3748		let block1 = insert_header(&backend, 1, block0, None, Default::default());
3749		let block2 = insert_header(&backend, 2, block1, None, Default::default());
3750		{
3751			let mut op = backend.begin_operation().unwrap();
3752			backend.begin_state_operation(&mut op, block0).unwrap();
3753			op.mark_finalized(block2, None).unwrap();
3754			backend.commit_operation(op).unwrap_err();
3755		}
3756	}
3757
3758	#[test]
3759	fn prune_blocks_on_finalize() {
3760		let pruning_modes =
3761			vec![BlocksPruning::Some(2), BlocksPruning::KeepFinalized, BlocksPruning::KeepAll];
3762
3763		for pruning_mode in pruning_modes {
3764			let backend = Backend::<Block>::new_test_with_tx_storage(pruning_mode, 0);
3765			let mut blocks = Vec::new();
3766			let mut prev_hash = Default::default();
3767			for i in 0..5 {
3768				let hash = insert_block(
3769					&backend,
3770					i,
3771					prev_hash,
3772					None,
3773					Default::default(),
3774					vec![UncheckedXt::new_transaction(i.into(), ())],
3775					None,
3776				)
3777				.unwrap();
3778				blocks.push(hash);
3779				prev_hash = hash;
3780			}
3781
3782			{
3783				let mut op = backend.begin_operation().unwrap();
3784				backend.begin_state_operation(&mut op, blocks[4]).unwrap();
3785				for i in 1..5 {
3786					op.mark_finalized(blocks[i], None).unwrap();
3787				}
3788				backend.commit_operation(op).unwrap();
3789			}
3790			let bc = backend.blockchain();
3791
3792			if matches!(pruning_mode, BlocksPruning::Some(_)) {
3793				assert_eq!(None, bc.body(blocks[0]).unwrap());
3794				assert_eq!(None, bc.body(blocks[1]).unwrap());
3795				assert_eq!(None, bc.body(blocks[2]).unwrap());
3796				assert_eq!(
3797					Some(vec![UncheckedXt::new_transaction(3.into(), ())]),
3798					bc.body(blocks[3]).unwrap()
3799				);
3800				assert_eq!(
3801					Some(vec![UncheckedXt::new_transaction(4.into(), ())]),
3802					bc.body(blocks[4]).unwrap()
3803				);
3804			} else {
3805				for i in 0..5 {
3806					assert_eq!(
3807						Some(vec![UncheckedXt::new_transaction((i as u64).into(), ())]),
3808						bc.body(blocks[i]).unwrap()
3809					);
3810				}
3811			}
3812		}
3813	}
3814
3815	#[test]
3816	fn prune_blocks_on_finalize_with_fork() {
3817		sp_tracing::try_init_simple();
3818
3819		let pruning_modes =
3820			vec![BlocksPruning::Some(2), BlocksPruning::KeepFinalized, BlocksPruning::KeepAll];
3821
3822		for pruning in pruning_modes {
3823			let backend = Backend::<Block>::new_test_with_tx_storage(pruning, 10);
3824			let mut blocks = Vec::new();
3825			let mut prev_hash = Default::default();
3826			for i in 0..5 {
3827				let hash = insert_block(
3828					&backend,
3829					i,
3830					prev_hash,
3831					None,
3832					Default::default(),
3833					vec![UncheckedXt::new_transaction(i.into(), ())],
3834					None,
3835				)
3836				.unwrap();
3837				blocks.push(hash);
3838				prev_hash = hash;
3839			}
3840
3841			// insert a fork at block 2
3842			let fork_hash_root = insert_block(
3843				&backend,
3844				2,
3845				blocks[1],
3846				None,
3847				H256::random(),
3848				vec![UncheckedXt::new_transaction(2.into(), ())],
3849				None,
3850			)
3851			.unwrap();
3852			insert_block(
3853				&backend,
3854				3,
3855				fork_hash_root,
3856				None,
3857				H256::random(),
3858				vec![
3859					UncheckedXt::new_transaction(3.into(), ()),
3860					UncheckedXt::new_transaction(11.into(), ()),
3861				],
3862				None,
3863			)
3864			.unwrap();
3865			let mut op = backend.begin_operation().unwrap();
3866			backend.begin_state_operation(&mut op, blocks[4]).unwrap();
3867			op.mark_head(blocks[4]).unwrap();
3868			backend.commit_operation(op).unwrap();
3869
3870			let bc = backend.blockchain();
3871			assert_eq!(
3872				Some(vec![UncheckedXt::new_transaction(2.into(), ())]),
3873				bc.body(fork_hash_root).unwrap()
3874			);
3875
3876			for i in 1..5 {
3877				let mut op = backend.begin_operation().unwrap();
3878				backend.begin_state_operation(&mut op, blocks[4]).unwrap();
3879				op.mark_finalized(blocks[i], None).unwrap();
3880				backend.commit_operation(op).unwrap();
3881			}
3882
3883			if matches!(pruning, BlocksPruning::Some(_)) {
3884				assert_eq!(None, bc.body(blocks[0]).unwrap());
3885				assert_eq!(None, bc.body(blocks[1]).unwrap());
3886				assert_eq!(None, bc.body(blocks[2]).unwrap());
3887
3888				assert_eq!(
3889					Some(vec![UncheckedXt::new_transaction(3.into(), ())]),
3890					bc.body(blocks[3]).unwrap()
3891				);
3892				assert_eq!(
3893					Some(vec![UncheckedXt::new_transaction(4.into(), ())]),
3894					bc.body(blocks[4]).unwrap()
3895				);
3896			} else {
3897				for i in 0..5 {
3898					assert_eq!(
3899						Some(vec![UncheckedXt::new_transaction((i as u64).into(), ())]),
3900						bc.body(blocks[i]).unwrap()
3901					);
3902				}
3903			}
3904
3905			if matches!(pruning, BlocksPruning::KeepAll) {
3906				assert_eq!(
3907					Some(vec![UncheckedXt::new_transaction(2.into(), ())]),
3908					bc.body(fork_hash_root).unwrap()
3909				);
3910			} else {
3911				assert_eq!(None, bc.body(fork_hash_root).unwrap());
3912			}
3913
3914			assert_eq!(bc.info().best_number, 4);
3915			for i in 0..5 {
3916				assert!(bc.hash(i).unwrap().is_some());
3917			}
3918		}
3919	}
3920
3921	#[test]
3922	fn prune_blocks_on_finalize_and_reorg() {
3923		//	0 - 1b
3924		//	\ - 1a - 2a - 3a
3925		//	     \ - 2b
3926
3927		let backend = Backend::<Block>::new_test_with_tx_storage(BlocksPruning::Some(10), 10);
3928
3929		let make_block = |index, parent, val: u64| {
3930			insert_block(
3931				&backend,
3932				index,
3933				parent,
3934				None,
3935				H256::random(),
3936				vec![UncheckedXt::new_transaction(val.into(), ())],
3937				None,
3938			)
3939			.unwrap()
3940		};
3941
3942		let block_0 = make_block(0, Default::default(), 0x00);
3943		let block_1a = make_block(1, block_0, 0x1a);
3944		let block_1b = make_block(1, block_0, 0x1b);
3945		let block_2a = make_block(2, block_1a, 0x2a);
3946		let block_2b = make_block(2, block_1a, 0x2b);
3947		let block_3a = make_block(3, block_2a, 0x3a);
3948
3949		// Make sure 1b is head
3950		let mut op = backend.begin_operation().unwrap();
3951		backend.begin_state_operation(&mut op, block_0).unwrap();
3952		op.mark_head(block_1b).unwrap();
3953		backend.commit_operation(op).unwrap();
3954
3955		// Finalize 3a
3956		let mut op = backend.begin_operation().unwrap();
3957		backend.begin_state_operation(&mut op, block_0).unwrap();
3958		op.mark_head(block_3a).unwrap();
3959		op.mark_finalized(block_1a, None).unwrap();
3960		op.mark_finalized(block_2a, None).unwrap();
3961		op.mark_finalized(block_3a, None).unwrap();
3962		backend.commit_operation(op).unwrap();
3963
3964		let bc = backend.blockchain();
3965		assert_eq!(None, bc.body(block_1b).unwrap());
3966		assert_eq!(None, bc.body(block_2b).unwrap());
3967		assert_eq!(
3968			Some(vec![UncheckedXt::new_transaction(0x00.into(), ())]),
3969			bc.body(block_0).unwrap()
3970		);
3971		assert_eq!(
3972			Some(vec![UncheckedXt::new_transaction(0x1a.into(), ())]),
3973			bc.body(block_1a).unwrap()
3974		);
3975		assert_eq!(
3976			Some(vec![UncheckedXt::new_transaction(0x2a.into(), ())]),
3977			bc.body(block_2a).unwrap()
3978		);
3979		assert_eq!(
3980			Some(vec![UncheckedXt::new_transaction(0x3a.into(), ())]),
3981			bc.body(block_3a).unwrap()
3982		);
3983	}
3984
3985	#[test]
3986	fn indexed_data_block_body() {
3987		let backend = Backend::<Block>::new_test_with_tx_storage(BlocksPruning::Some(1), 10);
3988
3989		let x0 = UncheckedXt::new_transaction(0.into(), ()).encode();
3990		let x1 = UncheckedXt::new_transaction(1.into(), ()).encode();
3991		let x0_hash = <HashingFor<Block> as sp_core::Hasher>::hash(&x0[1..]);
3992		let x1_hash = <HashingFor<Block> as sp_core::Hasher>::hash(&x1[1..]);
3993		let index = vec![
3994			IndexOperation::Insert {
3995				extrinsic: 0,
3996				hash: x0_hash.as_ref().to_vec(),
3997				size: (x0.len() - 1) as u32,
3998			},
3999			IndexOperation::Insert {
4000				extrinsic: 1,
4001				hash: x1_hash.as_ref().to_vec(),
4002				size: (x1.len() - 1) as u32,
4003			},
4004		];
4005		let hash = insert_block(
4006			&backend,
4007			0,
4008			Default::default(),
4009			None,
4010			Default::default(),
4011			vec![
4012				UncheckedXt::new_transaction(0.into(), ()),
4013				UncheckedXt::new_transaction(1.into(), ()),
4014			],
4015			Some(index),
4016		)
4017		.unwrap();
4018		let bc = backend.blockchain();
4019		assert_eq!(bc.indexed_transaction(x0_hash).unwrap().unwrap(), &x0[1..]);
4020		assert_eq!(bc.indexed_transaction(x1_hash).unwrap().unwrap(), &x1[1..]);
4021
4022		let hashof0 = bc.info().genesis_hash;
4023		// Push one more blocks and make sure block is pruned and transaction index is cleared.
4024		let block1 =
4025			insert_block(&backend, 1, hash, None, Default::default(), vec![], None).unwrap();
4026		backend.finalize_block(block1, None).unwrap();
4027		assert_eq!(bc.body(hashof0).unwrap(), None);
4028		assert_eq!(bc.indexed_transaction(x0_hash).unwrap(), None);
4029		assert_eq!(bc.indexed_transaction(x1_hash).unwrap(), None);
4030	}
4031
4032	#[test]
4033	fn index_invalid_size() {
4034		let backend = Backend::<Block>::new_test_with_tx_storage(BlocksPruning::Some(1), 10);
4035
4036		let x0 = UncheckedXt::new_transaction(0.into(), ()).encode();
4037		let x1 = UncheckedXt::new_transaction(1.into(), ()).encode();
4038
4039		let x0_hash = <HashingFor<Block> as sp_core::Hasher>::hash(&x0[..]);
4040		let x1_hash = <HashingFor<Block> as sp_core::Hasher>::hash(&x1[..]);
4041		let index = vec![
4042			IndexOperation::Insert {
4043				extrinsic: 0,
4044				hash: x0_hash.as_ref().to_vec(),
4045				size: (x0.len()) as u32,
4046			},
4047			IndexOperation::Insert {
4048				extrinsic: 1,
4049				hash: x1_hash.as_ref().to_vec(),
4050				size: (x1.len() + 1) as u32,
4051			},
4052		];
4053		insert_block(
4054			&backend,
4055			0,
4056			Default::default(),
4057			None,
4058			Default::default(),
4059			vec![
4060				UncheckedXt::new_transaction(0.into(), ()),
4061				UncheckedXt::new_transaction(1.into(), ()),
4062			],
4063			Some(index),
4064		)
4065		.unwrap();
4066		let bc = backend.blockchain();
4067		assert_eq!(bc.indexed_transaction(x0_hash).unwrap().unwrap(), &x0[..]);
4068		assert_eq!(bc.indexed_transaction(x1_hash).unwrap(), None);
4069	}
4070
4071	#[test]
4072	fn renew_transaction_storage() {
4073		let backend = Backend::<Block>::new_test_with_tx_storage(BlocksPruning::Some(2), 10);
4074		let mut blocks = Vec::new();
4075		let mut prev_hash = Default::default();
4076		let x1 = UncheckedXt::new_transaction(0.into(), ()).encode();
4077		let x1_hash = <HashingFor<Block> as sp_core::Hasher>::hash(&x1[1..]);
4078		for i in 0..10 {
4079			let mut index = Vec::new();
4080			if i == 0 {
4081				index.push(IndexOperation::Insert {
4082					extrinsic: 0,
4083					hash: x1_hash.as_ref().to_vec(),
4084					size: (x1.len() - 1) as u32,
4085				});
4086			} else if i < 5 {
4087				// keep renewing 1st
4088				index.push(IndexOperation::Renew { extrinsic: 0, hash: x1_hash.as_ref().to_vec() });
4089			} // else stop renewing
4090			let hash = insert_block(
4091				&backend,
4092				i,
4093				prev_hash,
4094				None,
4095				Default::default(),
4096				vec![UncheckedXt::new_transaction(i.into(), ())],
4097				Some(index),
4098			)
4099			.unwrap();
4100			blocks.push(hash);
4101			prev_hash = hash;
4102		}
4103
4104		for i in 1..10 {
4105			let mut op = backend.begin_operation().unwrap();
4106			backend.begin_state_operation(&mut op, blocks[4]).unwrap();
4107			op.mark_finalized(blocks[i], None).unwrap();
4108			backend.commit_operation(op).unwrap();
4109			let bc = backend.blockchain();
4110			if i < 6 {
4111				assert!(bc.indexed_transaction(x1_hash).unwrap().is_some());
4112			} else {
4113				assert!(bc.indexed_transaction(x1_hash).unwrap().is_none());
4114			}
4115		}
4116	}
4117
4118	#[test]
4119	fn remove_leaf_block_works() {
4120		let backend = Backend::<Block>::new_test_with_tx_storage(BlocksPruning::Some(2), 10);
4121		let mut blocks = Vec::new();
4122		let mut prev_hash = Default::default();
4123		for i in 0..2 {
4124			let hash = insert_block(
4125				&backend,
4126				i,
4127				prev_hash,
4128				None,
4129				Default::default(),
4130				vec![UncheckedXt::new_transaction(i.into(), ())],
4131				None,
4132			)
4133			.unwrap();
4134			blocks.push(hash);
4135			prev_hash = hash;
4136		}
4137
4138		for i in 0..2 {
4139			let hash = insert_block(
4140				&backend,
4141				2,
4142				blocks[1],
4143				None,
4144				sp_core::H256::random(),
4145				vec![UncheckedXt::new_transaction(i.into(), ())],
4146				None,
4147			)
4148			.unwrap();
4149			blocks.push(hash);
4150		}
4151
4152		// insert a fork at block 1, which becomes best block
4153		let best_hash = insert_block(
4154			&backend,
4155			1,
4156			blocks[0],
4157			None,
4158			sp_core::H256::random(),
4159			vec![UncheckedXt::new_transaction(42.into(), ())],
4160			None,
4161		)
4162		.unwrap();
4163
4164		assert_eq!(backend.blockchain().info().best_hash, best_hash);
4165		assert!(backend.remove_leaf_block(best_hash).is_err());
4166
4167		assert_eq!(backend.blockchain().leaves().unwrap(), vec![blocks[2], blocks[3], best_hash]);
4168		assert_eq!(backend.blockchain().children(blocks[1]).unwrap(), vec![blocks[2], blocks[3]]);
4169
4170		assert!(backend.have_state_at(blocks[3], 2));
4171		assert!(backend.blockchain().header(blocks[3]).unwrap().is_some());
4172		backend.remove_leaf_block(blocks[3]).unwrap();
4173		assert!(!backend.have_state_at(blocks[3], 2));
4174		assert!(backend.blockchain().header(blocks[3]).unwrap().is_none());
4175		assert_eq!(backend.blockchain().leaves().unwrap(), vec![blocks[2], best_hash]);
4176		assert_eq!(backend.blockchain().children(blocks[1]).unwrap(), vec![blocks[2]]);
4177
4178		assert!(backend.have_state_at(blocks[2], 2));
4179		assert!(backend.blockchain().header(blocks[2]).unwrap().is_some());
4180		backend.remove_leaf_block(blocks[2]).unwrap();
4181		assert!(!backend.have_state_at(blocks[2], 2));
4182		assert!(backend.blockchain().header(blocks[2]).unwrap().is_none());
4183		assert_eq!(backend.blockchain().leaves().unwrap(), vec![best_hash, blocks[1]]);
4184		assert_eq!(backend.blockchain().children(blocks[1]).unwrap(), vec![]);
4185
4186		assert!(backend.have_state_at(blocks[1], 1));
4187		assert!(backend.blockchain().header(blocks[1]).unwrap().is_some());
4188		backend.remove_leaf_block(blocks[1]).unwrap();
4189		assert!(!backend.have_state_at(blocks[1], 1));
4190		assert!(backend.blockchain().header(blocks[1]).unwrap().is_none());
4191		assert_eq!(backend.blockchain().leaves().unwrap(), vec![best_hash]);
4192		assert_eq!(backend.blockchain().children(blocks[0]).unwrap(), vec![best_hash]);
4193	}
4194
4195	#[test]
4196	fn test_import_existing_block_as_new_head() {
4197		let backend: Backend<Block> = Backend::new_test(10, 3);
4198		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
4199		let block1 = insert_header(&backend, 1, block0, None, Default::default());
4200		let block2 = insert_header(&backend, 2, block1, None, Default::default());
4201		let block3 = insert_header(&backend, 3, block2, None, Default::default());
4202		let block4 = insert_header(&backend, 4, block3, None, Default::default());
4203		let block5 = insert_header(&backend, 5, block4, None, Default::default());
4204		assert_eq!(backend.blockchain().info().best_hash, block5);
4205
4206		// Insert 1 as best again. This should fail because canonicalization_delay == 3 and best ==
4207		// 5
4208		let header = Header {
4209			number: 1,
4210			parent_hash: block0,
4211			state_root: BlakeTwo256::trie_root(Vec::new(), StateVersion::V1),
4212			digest: Default::default(),
4213			extrinsics_root: Default::default(),
4214		};
4215		let mut op = backend.begin_operation().unwrap();
4216		op.set_block_data(header, None, None, None, NewBlockState::Best).unwrap();
4217		assert!(matches!(backend.commit_operation(op), Err(sp_blockchain::Error::SetHeadTooOld)));
4218
4219		// Insert 2 as best again.
4220		let header = backend.blockchain().header(block2).unwrap().unwrap();
4221		let mut op = backend.begin_operation().unwrap();
4222		op.set_block_data(header, None, None, None, NewBlockState::Best).unwrap();
4223		backend.commit_operation(op).unwrap();
4224		assert_eq!(backend.blockchain().info().best_hash, block2);
4225	}
4226
4227	#[test]
4228	fn test_import_existing_block_as_final() {
4229		let backend: Backend<Block> = Backend::new_test(10, 10);
4230		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
4231		let block1 = insert_header(&backend, 1, block0, None, Default::default());
4232		let _block2 = insert_header(&backend, 2, block1, None, Default::default());
4233		// Genesis is auto finalized, the rest are not.
4234		assert_eq!(backend.blockchain().info().finalized_hash, block0);
4235
4236		// Insert 1 as final again.
4237		let header = backend.blockchain().header(block1).unwrap().unwrap();
4238
4239		let mut op = backend.begin_operation().unwrap();
4240		op.set_block_data(header, None, None, None, NewBlockState::Final).unwrap();
4241		backend.commit_operation(op).unwrap();
4242
4243		assert_eq!(backend.blockchain().info().finalized_hash, block1);
4244	}
4245
4246	#[test]
4247	fn test_import_existing_state_fails() {
4248		let backend: Backend<Block> = Backend::new_test(10, 10);
4249		let genesis =
4250			insert_block(&backend, 0, Default::default(), None, Default::default(), vec![], None)
4251				.unwrap();
4252
4253		insert_block(&backend, 1, genesis, None, Default::default(), vec![], None).unwrap();
4254		let err = insert_block(&backend, 1, genesis, None, Default::default(), vec![], None)
4255			.err()
4256			.unwrap();
4257		match err {
4258			sp_blockchain::Error::StateDatabase(m) if m == "Block already exists" => (),
4259			e @ _ => panic!("Unexpected error {:?}", e),
4260		}
4261	}
4262
4263	#[test]
4264	fn test_leaves_not_created_for_ancient_blocks() {
4265		let backend: Backend<Block> = Backend::new_test(10, 10);
4266		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
4267
4268		let block1_a = insert_header(&backend, 1, block0, None, Default::default());
4269		let block2_a = insert_header(&backend, 2, block1_a, None, Default::default());
4270		backend.finalize_block(block1_a, None).unwrap();
4271		assert_eq!(backend.blockchain().leaves().unwrap(), vec![block2_a]);
4272
4273		// Insert a fork prior to finalization point. Leave should not be created.
4274		insert_header_no_head(&backend, 1, block0, [1; 32].into());
4275		assert_eq!(backend.blockchain().leaves().unwrap(), vec![block2_a]);
4276	}
4277
4278	#[test]
4279	fn revert_non_best_blocks() {
4280		let backend = Backend::<Block>::new_test(10, 10);
4281
4282		let genesis =
4283			insert_block(&backend, 0, Default::default(), None, Default::default(), vec![], None)
4284				.unwrap();
4285
4286		let block1 =
4287			insert_block(&backend, 1, genesis, None, Default::default(), vec![], None).unwrap();
4288
4289		let block2 =
4290			insert_block(&backend, 2, block1, None, Default::default(), vec![], None).unwrap();
4291
4292		let block3 = {
4293			let mut op = backend.begin_operation().unwrap();
4294			backend.begin_state_operation(&mut op, block1).unwrap();
4295			let header = Header {
4296				number: 3,
4297				parent_hash: block2,
4298				state_root: BlakeTwo256::trie_root(Vec::new(), StateVersion::V1),
4299				digest: Default::default(),
4300				extrinsics_root: Default::default(),
4301			};
4302
4303			op.set_block_data(header.clone(), Some(Vec::new()), None, None, NewBlockState::Normal)
4304				.unwrap();
4305
4306			backend.commit_operation(op).unwrap();
4307
4308			header.hash()
4309		};
4310
4311		let block4 = {
4312			let mut op = backend.begin_operation().unwrap();
4313			backend.begin_state_operation(&mut op, block2).unwrap();
4314			let header = Header {
4315				number: 4,
4316				parent_hash: block3,
4317				state_root: BlakeTwo256::trie_root(Vec::new(), StateVersion::V1),
4318				digest: Default::default(),
4319				extrinsics_root: Default::default(),
4320			};
4321
4322			op.set_block_data(header.clone(), Some(Vec::new()), None, None, NewBlockState::Normal)
4323				.unwrap();
4324
4325			backend.commit_operation(op).unwrap();
4326
4327			header.hash()
4328		};
4329
4330		let block3_fork = {
4331			let mut op = backend.begin_operation().unwrap();
4332			backend.begin_state_operation(&mut op, block2).unwrap();
4333			let header = Header {
4334				number: 3,
4335				parent_hash: block2,
4336				state_root: BlakeTwo256::trie_root(Vec::new(), StateVersion::V1),
4337				digest: Default::default(),
4338				extrinsics_root: H256::from_low_u64_le(42),
4339			};
4340
4341			op.set_block_data(header.clone(), Some(Vec::new()), None, None, NewBlockState::Normal)
4342				.unwrap();
4343
4344			backend.commit_operation(op).unwrap();
4345
4346			header.hash()
4347		};
4348
4349		assert!(backend.have_state_at(block1, 1));
4350		assert!(backend.have_state_at(block2, 2));
4351		assert!(backend.have_state_at(block3, 3));
4352		assert!(backend.have_state_at(block4, 4));
4353		assert!(backend.have_state_at(block3_fork, 3));
4354
4355		assert_eq!(backend.blockchain.leaves().unwrap(), vec![block4, block3_fork]);
4356		assert_eq!(4, backend.blockchain.leaves.read().highest_leaf().unwrap().0);
4357
4358		assert_eq!(3, backend.revert(1, false).unwrap().0);
4359
4360		assert!(backend.have_state_at(block1, 1));
4361		assert!(!backend.have_state_at(block2, 2));
4362		assert!(!backend.have_state_at(block3, 3));
4363		assert!(!backend.have_state_at(block4, 4));
4364		assert!(!backend.have_state_at(block3_fork, 3));
4365
4366		assert_eq!(backend.blockchain.leaves().unwrap(), vec![block1]);
4367		assert_eq!(1, backend.blockchain.leaves.read().highest_leaf().unwrap().0);
4368	}
4369
4370	#[test]
4371	fn revert_finalized_blocks() {
4372		let pruning_modes = [BlocksPruning::Some(10), BlocksPruning::KeepAll];
4373
4374		// we will create a chain with 11 blocks, finalize block #8 and then
4375		// attempt to revert 5 blocks.
4376		for pruning_mode in pruning_modes {
4377			let backend = Backend::<Block>::new_test_with_tx_storage(pruning_mode, 1);
4378
4379			let mut parent = Default::default();
4380			for i in 0..=10 {
4381				parent = insert_block(&backend, i, parent, None, Default::default(), vec![], None)
4382					.unwrap();
4383			}
4384
4385			assert_eq!(backend.blockchain().info().best_number, 10);
4386
4387			let block8 = backend.blockchain().hash(8).unwrap().unwrap();
4388			backend.finalize_block(block8, None).unwrap();
4389			backend.revert(5, true).unwrap();
4390
4391			match pruning_mode {
4392				// we can only revert to blocks for which we have state, if pruning is enabled
4393				// then the last state available will be that of the latest finalized block
4394				BlocksPruning::Some(_) => {
4395					assert_eq!(backend.blockchain().info().finalized_number, 8)
4396				},
4397				// otherwise if we're not doing state pruning we can revert past finalized blocks
4398				_ => assert_eq!(backend.blockchain().info().finalized_number, 5),
4399			}
4400		}
4401	}
4402
4403	#[test]
4404	fn test_no_duplicated_leaves_allowed() {
4405		let backend: Backend<Block> = Backend::new_test(10, 10);
4406		let block0 = insert_header(&backend, 0, Default::default(), None, Default::default());
4407		let block1 = insert_header(&backend, 1, block0, None, Default::default());
4408		// Add block 2 not as the best block
4409		let block2 = insert_header_no_head(&backend, 2, block1, Default::default());
4410		assert_eq!(backend.blockchain().leaves().unwrap(), vec![block2]);
4411		assert_eq!(backend.blockchain().info().best_hash, block1);
4412
4413		// Add block 2 as the best block
4414		let block2 = insert_header(&backend, 2, block1, None, Default::default());
4415		assert_eq!(backend.blockchain().leaves().unwrap(), vec![block2]);
4416		assert_eq!(backend.blockchain().info().best_hash, block2);
4417	}
4418
4419	#[test]
4420	fn force_delayed_canonicalize_waiting_for_blocks_to_be_finalized() {
4421		let pruning_modes =
4422			[BlocksPruning::Some(10), BlocksPruning::KeepAll, BlocksPruning::KeepFinalized];
4423
4424		for pruning_mode in pruning_modes {
4425			eprintln!("Running with pruning mode: {:?}", pruning_mode);
4426
4427			let backend = Backend::<Block>::new_test_with_tx_storage(pruning_mode, 1);
4428
4429			let genesis = insert_block(
4430				&backend,
4431				0,
4432				Default::default(),
4433				None,
4434				Default::default(),
4435				vec![],
4436				None,
4437			)
4438			.unwrap();
4439
4440			let block1 = {
4441				let mut op = backend.begin_operation().unwrap();
4442				backend.begin_state_operation(&mut op, genesis).unwrap();
4443				let mut header = Header {
4444					number: 1,
4445					parent_hash: genesis,
4446					state_root: Default::default(),
4447					digest: Default::default(),
4448					extrinsics_root: Default::default(),
4449				};
4450
4451				let storage = vec![(vec![1, 3, 5], None), (vec![5, 5, 5], Some(vec![4, 5, 6]))];
4452
4453				let (root, overlay) = op.old_state.storage_root(
4454					storage.iter().map(|(k, v)| (k.as_slice(), v.as_ref().map(|v| &v[..]))),
4455					StateVersion::V1,
4456				);
4457				op.update_db_storage(overlay).unwrap();
4458				header.state_root = root.into();
4459
4460				op.update_storage(storage, Vec::new()).unwrap();
4461
4462				op.set_block_data(
4463					header.clone(),
4464					Some(Vec::new()),
4465					None,
4466					None,
4467					NewBlockState::Normal,
4468				)
4469				.unwrap();
4470
4471				backend.commit_operation(op).unwrap();
4472
4473				header.hash()
4474			};
4475
4476			if matches!(pruning_mode, BlocksPruning::Some(_)) {
4477				assert_eq!(
4478					LastCanonicalized::Block(0),
4479					backend.storage.state_db.last_canonicalized()
4480				);
4481			}
4482
4483			// This should not trigger any forced canonicalization as we didn't have imported any
4484			// best block by now.
4485			let block2 = {
4486				let mut op = backend.begin_operation().unwrap();
4487				backend.begin_state_operation(&mut op, block1).unwrap();
4488				let mut header = Header {
4489					number: 2,
4490					parent_hash: block1,
4491					state_root: Default::default(),
4492					digest: Default::default(),
4493					extrinsics_root: Default::default(),
4494				};
4495
4496				let storage = vec![(vec![5, 5, 5], Some(vec![4, 5, 6, 2]))];
4497
4498				let (root, overlay) = op.old_state.storage_root(
4499					storage.iter().map(|(k, v)| (k.as_slice(), v.as_ref().map(|v| &v[..]))),
4500					StateVersion::V1,
4501				);
4502				op.update_db_storage(overlay).unwrap();
4503				header.state_root = root.into();
4504
4505				op.update_storage(storage, Vec::new()).unwrap();
4506
4507				op.set_block_data(
4508					header.clone(),
4509					Some(Vec::new()),
4510					None,
4511					None,
4512					NewBlockState::Normal,
4513				)
4514				.unwrap();
4515
4516				backend.commit_operation(op).unwrap();
4517
4518				header.hash()
4519			};
4520
4521			if matches!(pruning_mode, BlocksPruning::Some(_)) {
4522				assert_eq!(
4523					LastCanonicalized::Block(0),
4524					backend.storage.state_db.last_canonicalized()
4525				);
4526			}
4527
4528			// This should also not trigger it yet, because we import a best block, but the best
4529			// block from the POV of the db is still at `0`.
4530			let block3 = {
4531				let mut op = backend.begin_operation().unwrap();
4532				backend.begin_state_operation(&mut op, block2).unwrap();
4533				let mut header = Header {
4534					number: 3,
4535					parent_hash: block2,
4536					state_root: Default::default(),
4537					digest: Default::default(),
4538					extrinsics_root: Default::default(),
4539				};
4540
4541				let storage = vec![(vec![5, 5, 5], Some(vec![4, 5, 6, 3]))];
4542
4543				let (root, overlay) = op.old_state.storage_root(
4544					storage.iter().map(|(k, v)| (k.as_slice(), v.as_ref().map(|v| &v[..]))),
4545					StateVersion::V1,
4546				);
4547				op.update_db_storage(overlay).unwrap();
4548				header.state_root = root.into();
4549
4550				op.update_storage(storage, Vec::new()).unwrap();
4551
4552				op.set_block_data(
4553					header.clone(),
4554					Some(Vec::new()),
4555					None,
4556					None,
4557					NewBlockState::Best,
4558				)
4559				.unwrap();
4560
4561				backend.commit_operation(op).unwrap();
4562
4563				header.hash()
4564			};
4565
4566			// Now it should kick in.
4567			let block4 = {
4568				let mut op = backend.begin_operation().unwrap();
4569				backend.begin_state_operation(&mut op, block3).unwrap();
4570				let mut header = Header {
4571					number: 4,
4572					parent_hash: block3,
4573					state_root: Default::default(),
4574					digest: Default::default(),
4575					extrinsics_root: Default::default(),
4576				};
4577
4578				let storage = vec![(vec![5, 5, 5], Some(vec![4, 5, 6, 4]))];
4579
4580				let (root, overlay) = op.old_state.storage_root(
4581					storage.iter().map(|(k, v)| (k.as_slice(), v.as_ref().map(|v| &v[..]))),
4582					StateVersion::V1,
4583				);
4584				op.update_db_storage(overlay).unwrap();
4585				header.state_root = root.into();
4586
4587				op.update_storage(storage, Vec::new()).unwrap();
4588
4589				op.set_block_data(
4590					header.clone(),
4591					Some(Vec::new()),
4592					None,
4593					None,
4594					NewBlockState::Best,
4595				)
4596				.unwrap();
4597
4598				backend.commit_operation(op).unwrap();
4599
4600				header.hash()
4601			};
4602
4603			if matches!(pruning_mode, BlocksPruning::Some(_)) {
4604				assert_eq!(
4605					LastCanonicalized::Block(2),
4606					backend.storage.state_db.last_canonicalized()
4607				);
4608			}
4609
4610			assert_eq!(block1, backend.blockchain().hash(1).unwrap().unwrap());
4611			assert_eq!(block2, backend.blockchain().hash(2).unwrap().unwrap());
4612			assert_eq!(block3, backend.blockchain().hash(3).unwrap().unwrap());
4613			assert_eq!(block4, backend.blockchain().hash(4).unwrap().unwrap());
4614		}
4615	}
4616
4617	#[test]
4618	fn test_pinned_blocks_on_finalize() {
4619		let backend = Backend::<Block>::new_test_with_tx_storage(BlocksPruning::Some(1), 10);
4620		let mut blocks = Vec::new();
4621		let mut prev_hash = Default::default();
4622
4623		let build_justification = |i: u64| ([0, 0, 0, 0], vec![i.try_into().unwrap()]);
4624		// Block tree:
4625		//   0 -> 1 -> 2 -> 3 -> 4
4626		for i in 0..5 {
4627			let hash = insert_block(
4628				&backend,
4629				i,
4630				prev_hash,
4631				None,
4632				Default::default(),
4633				vec![UncheckedXt::new_transaction(i.into(), ())],
4634				None,
4635			)
4636			.unwrap();
4637			blocks.push(hash);
4638			// Avoid block pruning.
4639			backend.pin_block(blocks[i as usize]).unwrap();
4640
4641			prev_hash = hash;
4642		}
4643
4644		let bc = backend.blockchain();
4645
4646		// Check that we can properly access values when there is reference count
4647		// but no value.
4648		assert_eq!(
4649			Some(vec![UncheckedXt::new_transaction(1.into(), ())]),
4650			bc.body(blocks[1]).unwrap()
4651		);
4652
4653		// Block 1 gets pinned three times
4654		backend.pin_block(blocks[1]).unwrap();
4655		backend.pin_block(blocks[1]).unwrap();
4656
4657		// Finalize all blocks. This will trigger pruning.
4658		let mut op = backend.begin_operation().unwrap();
4659		backend.begin_state_operation(&mut op, blocks[4]).unwrap();
4660		for i in 1..5 {
4661			op.mark_finalized(blocks[i], Some(build_justification(i.try_into().unwrap())))
4662				.unwrap();
4663		}
4664		backend.commit_operation(op).unwrap();
4665
4666		// Block 0, 1, 2, 3 are pinned, so all values should be cached.
4667		// Block 4 is inside the pruning window, its value is in db.
4668		assert_eq!(
4669			Some(vec![UncheckedXt::new_transaction(0.into(), ())]),
4670			bc.body(blocks[0]).unwrap()
4671		);
4672
4673		assert_eq!(
4674			Some(vec![UncheckedXt::new_transaction(1.into(), ())]),
4675			bc.body(blocks[1]).unwrap()
4676		);
4677		assert_eq!(
4678			Some(Justifications::from(build_justification(1))),
4679			bc.justifications(blocks[1]).unwrap()
4680		);
4681
4682		assert_eq!(
4683			Some(vec![UncheckedXt::new_transaction(2.into(), ())]),
4684			bc.body(blocks[2]).unwrap()
4685		);
4686		assert_eq!(
4687			Some(Justifications::from(build_justification(2))),
4688			bc.justifications(blocks[2]).unwrap()
4689		);
4690
4691		assert_eq!(
4692			Some(vec![UncheckedXt::new_transaction(3.into(), ())]),
4693			bc.body(blocks[3]).unwrap()
4694		);
4695		assert_eq!(
4696			Some(Justifications::from(build_justification(3))),
4697			bc.justifications(blocks[3]).unwrap()
4698		);
4699
4700		assert_eq!(
4701			Some(vec![UncheckedXt::new_transaction(4.into(), ())]),
4702			bc.body(blocks[4]).unwrap()
4703		);
4704		assert_eq!(
4705			Some(Justifications::from(build_justification(4))),
4706			bc.justifications(blocks[4]).unwrap()
4707		);
4708
4709		// Unpin all blocks. Values should be removed from cache.
4710		for block in &blocks {
4711			backend.unpin_block(*block);
4712		}
4713
4714		assert!(bc.body(blocks[0]).unwrap().is_none());
4715		// Block 1 was pinned twice, we expect it to be still cached
4716		assert!(bc.body(blocks[1]).unwrap().is_some());
4717		assert!(bc.justifications(blocks[1]).unwrap().is_some());
4718		// Headers should also be available while pinned
4719		assert!(bc.header(blocks[1]).ok().flatten().is_some());
4720		assert!(bc.body(blocks[2]).unwrap().is_none());
4721		assert!(bc.justifications(blocks[2]).unwrap().is_none());
4722		assert!(bc.body(blocks[3]).unwrap().is_none());
4723		assert!(bc.justifications(blocks[3]).unwrap().is_none());
4724
4725		// After these unpins, block 1 should also be removed
4726		backend.unpin_block(blocks[1]);
4727		assert!(bc.body(blocks[1]).unwrap().is_some());
4728		assert!(bc.justifications(blocks[1]).unwrap().is_some());
4729		backend.unpin_block(blocks[1]);
4730		assert!(bc.body(blocks[1]).unwrap().is_none());
4731		assert!(bc.justifications(blocks[1]).unwrap().is_none());
4732
4733		// Block 4 is inside the pruning window and still kept
4734		assert_eq!(
4735			Some(vec![UncheckedXt::new_transaction(4.into(), ())]),
4736			bc.body(blocks[4]).unwrap()
4737		);
4738		assert_eq!(
4739			Some(Justifications::from(build_justification(4))),
4740			bc.justifications(blocks[4]).unwrap()
4741		);
4742
4743		// Block tree:
4744		//   0 -> 1 -> 2 -> 3 -> 4 -> 5
4745		let hash = insert_block(
4746			&backend,
4747			5,
4748			prev_hash,
4749			None,
4750			Default::default(),
4751			vec![UncheckedXt::new_transaction(5.into(), ())],
4752			None,
4753		)
4754		.unwrap();
4755		blocks.push(hash);
4756
4757		backend.pin_block(blocks[4]).unwrap();
4758		// Mark block 5 as finalized.
4759		let mut op = backend.begin_operation().unwrap();
4760		backend.begin_state_operation(&mut op, blocks[5]).unwrap();
4761		op.mark_finalized(blocks[5], Some(build_justification(5))).unwrap();
4762		backend.commit_operation(op).unwrap();
4763
4764		assert!(bc.body(blocks[0]).unwrap().is_none());
4765		assert!(bc.body(blocks[1]).unwrap().is_none());
4766		assert!(bc.body(blocks[2]).unwrap().is_none());
4767		assert!(bc.body(blocks[3]).unwrap().is_none());
4768
4769		assert_eq!(
4770			Some(vec![UncheckedXt::new_transaction(4.into(), ())]),
4771			bc.body(blocks[4]).unwrap()
4772		);
4773		assert_eq!(
4774			Some(Justifications::from(build_justification(4))),
4775			bc.justifications(blocks[4]).unwrap()
4776		);
4777		assert_eq!(
4778			Some(vec![UncheckedXt::new_transaction(5.into(), ())]),
4779			bc.body(blocks[5]).unwrap()
4780		);
4781		assert!(bc.header(blocks[5]).ok().flatten().is_some());
4782
4783		backend.unpin_block(blocks[4]);
4784		assert!(bc.body(blocks[4]).unwrap().is_none());
4785		assert!(bc.justifications(blocks[4]).unwrap().is_none());
4786
4787		// Append a justification to block 5.
4788		backend.append_justification(blocks[5], ([0, 0, 0, 1], vec![42])).unwrap();
4789
4790		let hash = insert_block(
4791			&backend,
4792			6,
4793			blocks[5],
4794			None,
4795			Default::default(),
4796			vec![UncheckedXt::new_transaction(6.into(), ())],
4797			None,
4798		)
4799		.unwrap();
4800		blocks.push(hash);
4801
4802		// Pin block 5 so it gets loaded into the cache on prune
4803		backend.pin_block(blocks[5]).unwrap();
4804
4805		// Finalize block 6 so block 5 gets pruned. Since it is pinned both justifications should be
4806		// in memory.
4807		let mut op = backend.begin_operation().unwrap();
4808		backend.begin_state_operation(&mut op, blocks[6]).unwrap();
4809		op.mark_finalized(blocks[6], None).unwrap();
4810		backend.commit_operation(op).unwrap();
4811
4812		assert_eq!(
4813			Some(vec![UncheckedXt::new_transaction(5.into(), ())]),
4814			bc.body(blocks[5]).unwrap()
4815		);
4816		assert!(bc.header(blocks[5]).ok().flatten().is_some());
4817		let mut expected = Justifications::from(build_justification(5));
4818		expected.append(([0, 0, 0, 1], vec![42]));
4819		assert_eq!(Some(expected), bc.justifications(blocks[5]).unwrap());
4820	}
4821
4822	#[test]
4823	fn test_pinned_blocks_on_finalize_with_fork() {
4824		let backend = Backend::<Block>::new_test_with_tx_storage(BlocksPruning::Some(1), 10);
4825		let mut blocks = Vec::new();
4826		let mut prev_hash = Default::default();
4827
4828		// Block tree:
4829		//   0 -> 1 -> 2 -> 3 -> 4
4830		for i in 0..5 {
4831			let hash = insert_block(
4832				&backend,
4833				i,
4834				prev_hash,
4835				None,
4836				Default::default(),
4837				vec![UncheckedXt::new_transaction(i.into(), ())],
4838				None,
4839			)
4840			.unwrap();
4841			blocks.push(hash);
4842
4843			// Avoid block pruning.
4844			backend.pin_block(blocks[i as usize]).unwrap();
4845
4846			prev_hash = hash;
4847		}
4848
4849		// Insert a fork at the second block.
4850		// Block tree:
4851		//   0 -> 1 -> 2 -> 3 -> 4
4852		//        \ -> 2 -> 3
4853		let fork_hash_root = insert_block(
4854			&backend,
4855			2,
4856			blocks[1],
4857			None,
4858			H256::random(),
4859			vec![UncheckedXt::new_transaction(2.into(), ())],
4860			None,
4861		)
4862		.unwrap();
4863		let fork_hash_3 = insert_block(
4864			&backend,
4865			3,
4866			fork_hash_root,
4867			None,
4868			H256::random(),
4869			vec![
4870				UncheckedXt::new_transaction(3.into(), ()),
4871				UncheckedXt::new_transaction(11.into(), ()),
4872			],
4873			None,
4874		)
4875		.unwrap();
4876
4877		// Do not prune the fork hash.
4878		backend.pin_block(fork_hash_3).unwrap();
4879
4880		let mut op = backend.begin_operation().unwrap();
4881		backend.begin_state_operation(&mut op, blocks[4]).unwrap();
4882		op.mark_head(blocks[4]).unwrap();
4883		backend.commit_operation(op).unwrap();
4884
4885		for i in 1..5 {
4886			let mut op = backend.begin_operation().unwrap();
4887			backend.begin_state_operation(&mut op, blocks[4]).unwrap();
4888			op.mark_finalized(blocks[i], None).unwrap();
4889			backend.commit_operation(op).unwrap();
4890		}
4891
4892		let bc = backend.blockchain();
4893		assert_eq!(
4894			Some(vec![UncheckedXt::new_transaction(0.into(), ())]),
4895			bc.body(blocks[0]).unwrap()
4896		);
4897		assert_eq!(
4898			Some(vec![UncheckedXt::new_transaction(1.into(), ())]),
4899			bc.body(blocks[1]).unwrap()
4900		);
4901		assert_eq!(
4902			Some(vec![UncheckedXt::new_transaction(2.into(), ())]),
4903			bc.body(blocks[2]).unwrap()
4904		);
4905		assert_eq!(
4906			Some(vec![UncheckedXt::new_transaction(3.into(), ())]),
4907			bc.body(blocks[3]).unwrap()
4908		);
4909		assert_eq!(
4910			Some(vec![UncheckedXt::new_transaction(4.into(), ())]),
4911			bc.body(blocks[4]).unwrap()
4912		);
4913		// Check the fork hashes.
4914		assert_eq!(None, bc.body(fork_hash_root).unwrap());
4915		assert_eq!(
4916			Some(vec![
4917				UncheckedXt::new_transaction(3.into(), ()),
4918				UncheckedXt::new_transaction(11.into(), ())
4919			]),
4920			bc.body(fork_hash_3).unwrap()
4921		);
4922
4923		// Unpin all blocks, except the forked one.
4924		for block in &blocks {
4925			backend.unpin_block(*block);
4926		}
4927		assert!(bc.body(blocks[0]).unwrap().is_none());
4928		assert!(bc.body(blocks[1]).unwrap().is_none());
4929		assert!(bc.body(blocks[2]).unwrap().is_none());
4930		assert!(bc.body(blocks[3]).unwrap().is_none());
4931
4932		assert!(bc.body(fork_hash_3).unwrap().is_some());
4933		backend.unpin_block(fork_hash_3);
4934		assert!(bc.body(fork_hash_3).unwrap().is_none());
4935	}
4936}