referrerpolicy=no-referrer-when-downgrade

sp_storage/
lib.rs

1// This file is part of Substrate.
2
3// Copyright (C) Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! Primitive types for storage related stuff.
19
20#![cfg_attr(not(feature = "std"), no_std)]
21
22extern crate alloc;
23
24#[cfg(feature = "serde")]
25use serde::{Deserialize, Serialize};
26use sp_debug_derive::RuntimeDebug;
27
28use alloc::vec::Vec;
29use codec::{Decode, Encode};
30use core::{
31	fmt::Display,
32	ops::{Deref, DerefMut},
33};
34use ref_cast::RefCast;
35
36/// Storage key.
37#[derive(PartialEq, Eq, RuntimeDebug, Hash, PartialOrd, Ord, Clone, Encode, Decode)]
38#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
39pub struct StorageKey(
40	#[cfg_attr(feature = "serde", serde(with = "impl_serde::serialize"))] pub Vec<u8>,
41);
42
43impl AsRef<[u8]> for StorageKey {
44	fn as_ref(&self) -> &[u8] {
45		self.0.as_ref()
46	}
47}
48
49/// Storage key with read/write tracking information.
50#[derive(PartialEq, Eq, Ord, PartialOrd, core::hash::Hash, RuntimeDebug, Clone, Encode, Decode)]
51pub struct TrackedStorageKey {
52	pub key: Vec<u8>,
53	pub reads: u32,
54	pub writes: u32,
55	pub whitelisted: bool,
56}
57
58impl TrackedStorageKey {
59	/// Create a default `TrackedStorageKey`
60	pub fn new(key: Vec<u8>) -> Self {
61		Self { key, reads: 0, writes: 0, whitelisted: false }
62	}
63	/// Check if this key has been "read", i.e. it exists in the memory overlay.
64	///
65	/// Can be true if the key has been read, has been written to, or has been
66	/// whitelisted.
67	pub fn has_been_read(&self) -> bool {
68		self.whitelisted || self.reads > 0u32 || self.has_been_written()
69	}
70	/// Check if this key has been "written", i.e. a new value will be committed to the database.
71	///
72	/// Can be true if the key has been written to, or has been whitelisted.
73	pub fn has_been_written(&self) -> bool {
74		self.whitelisted || self.writes > 0u32
75	}
76	/// Add a storage read to this key.
77	pub fn add_read(&mut self) {
78		self.reads += 1;
79	}
80	/// Add a storage write to this key.
81	pub fn add_write(&mut self) {
82		self.writes += 1;
83	}
84	/// Whitelist this key.
85	pub fn whitelist(&mut self) {
86		self.whitelisted = true;
87	}
88}
89
90// Easily convert a key to a `TrackedStorageKey` that has been whitelisted.
91impl From<Vec<u8>> for TrackedStorageKey {
92	fn from(key: Vec<u8>) -> Self {
93		Self { key, reads: 0, writes: 0, whitelisted: true }
94	}
95}
96
97/// Storage key of a child trie, it contains the prefix to the key.
98#[derive(PartialEq, Eq, RuntimeDebug, Hash, PartialOrd, Ord, Clone)]
99#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
100#[repr(transparent)]
101#[derive(RefCast)]
102pub struct PrefixedStorageKey(
103	#[cfg_attr(feature = "serde", serde(with = "impl_serde::serialize"))] Vec<u8>,
104);
105
106impl Deref for PrefixedStorageKey {
107	type Target = Vec<u8>;
108
109	fn deref(&self) -> &Vec<u8> {
110		&self.0
111	}
112}
113
114impl DerefMut for PrefixedStorageKey {
115	fn deref_mut(&mut self) -> &mut Vec<u8> {
116		&mut self.0
117	}
118}
119
120impl PrefixedStorageKey {
121	/// Create a prefixed storage key from its byte array representation.
122	pub fn new(inner: Vec<u8>) -> Self {
123		PrefixedStorageKey(inner)
124	}
125
126	/// Create a prefixed storage key reference.
127	pub fn new_ref(inner: &Vec<u8>) -> &Self {
128		PrefixedStorageKey::ref_cast(inner)
129	}
130
131	/// Get inner key, this should only be needed when writing into parent trie to avoid an
132	/// allocation.
133	pub fn into_inner(self) -> Vec<u8> {
134		self.0
135	}
136}
137
138/// Storage data associated to a [`StorageKey`].
139#[derive(PartialEq, Eq, RuntimeDebug, Hash, PartialOrd, Ord, Clone, Encode, Decode, Default)]
140#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
141pub struct StorageData(
142	#[cfg_attr(feature = "serde", serde(with = "impl_serde::serialize"))] pub Vec<u8>,
143);
144
145/// Map of data to use in a storage, it is a collection of
146/// byte key and values.
147pub type StorageMap = alloc::collections::BTreeMap<Vec<u8>, Vec<u8>>;
148
149/// Map of storage children.
150#[cfg(feature = "std")]
151pub type ChildrenMap = std::collections::HashMap<Vec<u8>, StorageChild>;
152
153#[cfg(not(feature = "std"))]
154pub type ChildrenMap = alloc::collections::BTreeMap<Vec<u8>, StorageChild>;
155
156/// Child trie storage data.
157#[derive(Debug, PartialEq, Eq, Clone)]
158pub struct StorageChild {
159	/// Child data for storage.
160	pub data: StorageMap,
161	/// Associated child info for a child
162	/// trie.
163	pub child_info: ChildInfo,
164}
165
166/// Struct containing data needed for a storage.
167#[derive(Default, Debug, Clone)]
168pub struct Storage {
169	/// Top trie storage data.
170	pub top: StorageMap,
171	/// Children trie storage data. Key does not include prefix, only for the `default` trie kind,
172	/// of `ChildType::ParentKeyId` type.
173	pub children_default: ChildrenMap,
174}
175
176/// Storage change set
177#[derive(RuntimeDebug, PartialEq, Eq, Clone)]
178#[cfg_attr(feature = "serde", derive(Serialize, Deserialize))]
179#[cfg_attr(feature = "serde", serde(rename_all = "camelCase"))]
180pub struct StorageChangeSet<Hash> {
181	/// Block hash
182	pub block: Hash,
183	/// A list of changes
184	pub changes: Vec<(StorageKey, Option<StorageData>)>,
185}
186
187/// List of all well known keys and prefixes in storage.
188pub mod well_known_keys {
189	/// Wasm code of the runtime.
190	///
191	/// Stored as a raw byte vector. Required by substrate.
192	///
193	/// Encodes to `0x3A636F6465`.
194	pub const CODE: &[u8] = b":code";
195
196	/// Number of wasm linear memory pages required for execution of the runtime.
197	///
198	/// The type of this value is encoded `u64`.
199	///
200	/// Encodes to `0x307833413633364636343635`
201	pub const HEAP_PAGES: &[u8] = b":heappages";
202
203	/// Current extrinsic index (u32) is stored under this key.
204	///
205	/// Encodes to `0x3a65787472696e7369635f696e646578`.
206	pub const EXTRINSIC_INDEX: &[u8] = b":extrinsic_index";
207
208	/// Current intra-block entropy (a universally unique `[u8; 32]` value) is stored here.
209	///
210	/// Encodes to `0x3a696e747261626c6f636b5f656e74726f7079`.
211	pub const INTRABLOCK_ENTROPY: &[u8] = b":intrablock_entropy";
212
213	/// Prefix of child storage keys.
214	pub const CHILD_STORAGE_KEY_PREFIX: &[u8] = b":child_storage:";
215
216	/// Prefix of the default child storage keys in the top trie.
217	pub const DEFAULT_CHILD_STORAGE_KEY_PREFIX: &[u8] = b":child_storage:default:";
218
219	/// Whether a key is a default child storage key.
220	///
221	/// This is convenience function which basically checks if the given `key` starts
222	/// with `DEFAULT_CHILD_STORAGE_KEY_PREFIX` and doesn't do anything apart from that.
223	pub fn is_default_child_storage_key(key: &[u8]) -> bool {
224		key.starts_with(DEFAULT_CHILD_STORAGE_KEY_PREFIX)
225	}
226
227	/// Whether a key is a child storage key.
228	///
229	/// This is convenience function which basically checks if the given `key` starts
230	/// with `CHILD_STORAGE_KEY_PREFIX` and doesn't do anything apart from that.
231	pub fn is_child_storage_key(key: &[u8]) -> bool {
232		// Other code might depend on this, so be careful changing this.
233		key.starts_with(CHILD_STORAGE_KEY_PREFIX)
234	}
235
236	/// Returns if the given `key` starts with [`CHILD_STORAGE_KEY_PREFIX`] or collides with it.
237	pub fn starts_with_child_storage_key(key: &[u8]) -> bool {
238		if key.len() > CHILD_STORAGE_KEY_PREFIX.len() {
239			key.starts_with(CHILD_STORAGE_KEY_PREFIX)
240		} else {
241			CHILD_STORAGE_KEY_PREFIX.starts_with(key)
242		}
243	}
244}
245
246/// Threshold size to start using trie value nodes in state.
247pub const TRIE_VALUE_NODE_THRESHOLD: u32 = 33;
248
249/// Information related to a child state.
250#[derive(PartialEq, Eq, Hash, PartialOrd, Ord, Encode, Decode, Debug, Clone)]
251pub enum ChildInfo {
252	/// This is the one used by default.
253	ParentKeyId(ChildTrieParentKeyId),
254}
255
256impl ChildInfo {
257	/// Instantiates child information for a default child trie
258	/// of kind `ChildType::ParentKeyId`, using an unprefixed parent
259	/// storage key.
260	pub fn new_default(storage_key: &[u8]) -> Self {
261		let data = storage_key.to_vec();
262		ChildInfo::ParentKeyId(ChildTrieParentKeyId { data })
263	}
264
265	/// Same as `new_default` but with `Vec<u8>` as input.
266	pub fn new_default_from_vec(storage_key: Vec<u8>) -> Self {
267		ChildInfo::ParentKeyId(ChildTrieParentKeyId { data: storage_key })
268	}
269
270	/// Try to update with another instance, return false if both instance
271	/// are not compatible.
272	pub fn try_update(&mut self, other: &ChildInfo) -> bool {
273		match self {
274			ChildInfo::ParentKeyId(child_trie) => child_trie.try_update(other),
275		}
276	}
277
278	/// Returns byte sequence (keyspace) that can be use by underlying db to isolate keys.
279	/// This is a unique id of the child trie. The collision resistance of this value
280	/// depends on the type of child info use. For `ChildInfo::Default` it is and need to be.
281	#[inline]
282	pub fn keyspace(&self) -> &[u8] {
283		match self {
284			ChildInfo::ParentKeyId(..) => self.storage_key(),
285		}
286	}
287
288	/// Returns a reference to the location in the direct parent of
289	/// this trie but without the common prefix for this kind of
290	/// child trie.
291	pub fn storage_key(&self) -> &[u8] {
292		match self {
293			ChildInfo::ParentKeyId(ChildTrieParentKeyId { data }) => &data[..],
294		}
295	}
296
297	/// Return the full location in the direct parent of
298	/// this trie.
299	pub fn prefixed_storage_key(&self) -> PrefixedStorageKey {
300		match self {
301			ChildInfo::ParentKeyId(ChildTrieParentKeyId { data }) =>
302				ChildType::ParentKeyId.new_prefixed_key(data.as_slice()),
303		}
304	}
305
306	/// Returns the full location in the direct parent of
307	/// this trie.
308	pub fn into_prefixed_storage_key(self) -> PrefixedStorageKey {
309		match self {
310			ChildInfo::ParentKeyId(ChildTrieParentKeyId { mut data }) => {
311				ChildType::ParentKeyId.do_prefix_key(&mut data);
312				PrefixedStorageKey(data)
313			},
314		}
315	}
316
317	/// Returns the type for this child info.
318	pub fn child_type(&self) -> ChildType {
319		match self {
320			ChildInfo::ParentKeyId(..) => ChildType::ParentKeyId,
321		}
322	}
323}
324
325/// Type of child.
326/// It does not strictly define different child type, it can also
327/// be related to technical consideration or api variant.
328#[repr(u32)]
329#[derive(Clone, Copy, PartialEq)]
330#[cfg_attr(feature = "std", derive(Debug))]
331pub enum ChildType {
332	/// If runtime module ensures that the child key is a unique id that will
333	/// only be used once, its parent key is used as a child trie unique id.
334	ParentKeyId = 1,
335}
336
337impl ChildType {
338	/// Try to get a child type from its `u32` representation.
339	pub fn new(repr: u32) -> Option<ChildType> {
340		Some(match repr {
341			r if r == ChildType::ParentKeyId as u32 => ChildType::ParentKeyId,
342			_ => return None,
343		})
344	}
345
346	/// Transform a prefixed key into a tuple of the child type
347	/// and the unprefixed representation of the key.
348	pub fn from_prefixed_key<'a>(storage_key: &'a PrefixedStorageKey) -> Option<(Self, &'a [u8])> {
349		let match_type = |storage_key: &'a [u8], child_type: ChildType| {
350			let prefix = child_type.parent_prefix();
351			if storage_key.starts_with(prefix) {
352				Some((child_type, &storage_key[prefix.len()..]))
353			} else {
354				None
355			}
356		};
357		match_type(storage_key, ChildType::ParentKeyId)
358	}
359
360	/// Produce a prefixed key for a given child type.
361	fn new_prefixed_key(&self, key: &[u8]) -> PrefixedStorageKey {
362		let parent_prefix = self.parent_prefix();
363		let mut result = Vec::with_capacity(parent_prefix.len() + key.len());
364		result.extend_from_slice(parent_prefix);
365		result.extend_from_slice(key);
366		PrefixedStorageKey(result)
367	}
368
369	/// Prefixes a vec with the prefix for this child type.
370	fn do_prefix_key(&self, key: &mut Vec<u8>) {
371		let parent_prefix = self.parent_prefix();
372		let key_len = key.len();
373		if !parent_prefix.is_empty() {
374			key.resize(key_len + parent_prefix.len(), 0);
375			key.copy_within(..key_len, parent_prefix.len());
376			key[..parent_prefix.len()].copy_from_slice(parent_prefix);
377		}
378	}
379
380	/// Returns the location reserved for this child trie in their parent trie if there
381	/// is one.
382	pub fn parent_prefix(&self) -> &'static [u8] {
383		match self {
384			&ChildType::ParentKeyId => well_known_keys::DEFAULT_CHILD_STORAGE_KEY_PREFIX,
385		}
386	}
387}
388
389/// A child trie of default type.
390///
391/// It uses the same default implementation as the top trie, top trie being a child trie with no
392/// keyspace and no storage key. Its keyspace is the variable (unprefixed) part of its storage key.
393/// It shares its trie nodes backend storage with every other child trie, so its storage key needs
394/// to be a unique id that will be use only once. Those unique id also required to be long enough to
395/// avoid any unique id to be prefixed by an other unique id.
396#[derive(PartialEq, Eq, Hash, PartialOrd, Ord, Encode, Decode, Debug, Clone)]
397pub struct ChildTrieParentKeyId {
398	/// Data is the storage key without prefix.
399	data: Vec<u8>,
400}
401
402impl ChildTrieParentKeyId {
403	/// Try to update with another instance, return false if both instance
404	/// are not compatible.
405	fn try_update(&mut self, other: &ChildInfo) -> bool {
406		match other {
407			ChildInfo::ParentKeyId(other) => self.data[..] == other.data[..],
408		}
409	}
410}
411
412/// Different possible state version.
413///
414/// V0 and V1 uses a same trie implementation, but V1 will write external value node in the trie for
415/// value with size at least `TRIE_VALUE_NODE_THRESHOLD`.
416#[derive(Debug, Default, Clone, Copy, Eq, PartialEq)]
417#[cfg_attr(feature = "std", derive(Encode, Decode))]
418pub enum StateVersion {
419	/// Old state version, no value nodes.
420	V0 = 0,
421	/// New state version can use value nodes.
422	#[default]
423	V1 = 1,
424}
425
426impl Display for StateVersion {
427	fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
428		match self {
429			StateVersion::V0 => f.write_str("0"),
430			StateVersion::V1 => f.write_str("1"),
431		}
432	}
433}
434
435impl From<StateVersion> for u8 {
436	fn from(version: StateVersion) -> u8 {
437		version as u8
438	}
439}
440
441impl TryFrom<u8> for StateVersion {
442	type Error = ();
443	fn try_from(val: u8) -> core::result::Result<StateVersion, ()> {
444		match val {
445			0 => Ok(StateVersion::V0),
446			1 => Ok(StateVersion::V1),
447			2 => Ok(StateVersion::V1),
448			_ => Err(()),
449		}
450	}
451}
452
453impl StateVersion {
454	/// If defined, values in state of size bigger or equal
455	/// to this threshold will use a separate trie node.
456	/// Otherwise, value will be inlined in branch or leaf
457	/// node.
458	pub fn state_value_threshold(&self) -> Option<u32> {
459		match self {
460			StateVersion::V0 => None,
461			StateVersion::V1 => Some(TRIE_VALUE_NODE_THRESHOLD),
462		}
463	}
464}
465
466#[cfg(test)]
467mod tests {
468	use super::*;
469
470	#[test]
471	fn test_prefix_default_child_info() {
472		let child_info = ChildInfo::new_default(b"any key");
473		let prefix = child_info.child_type().parent_prefix();
474		assert!(prefix.starts_with(well_known_keys::CHILD_STORAGE_KEY_PREFIX));
475		assert!(prefix.starts_with(well_known_keys::DEFAULT_CHILD_STORAGE_KEY_PREFIX));
476	}
477}