sc_transaction_pool/graph/
rotator.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//! Rotate extrinsic inside the pool.
20//!
21//! Keeps only recent extrinsic and discard the ones kept for a significant amount of time.
22//! Discarded extrinsics are banned so that they don't get re-imported again.
23
24use parking_lot::RwLock;
25use std::{
26	collections::HashMap,
27	hash, iter,
28	time::{Duration, Instant},
29};
30
31use super::base_pool::Transaction;
32
33/// Expected size of the banned extrinsics cache.
34const EXPECTED_SIZE: usize = 2048;
35
36/// Pool rotator is responsible to only keep fresh extrinsics in the pool.
37///
38/// Extrinsics that occupy the pool for too long are culled and temporarily banned from entering
39/// the pool again.
40pub struct PoolRotator<Hash> {
41	/// How long the extrinsic is banned for.
42	ban_time: Duration,
43	/// Currently banned extrinsics.
44	banned_until: RwLock<HashMap<Hash, Instant>>,
45}
46
47impl<Hash: hash::Hash + Eq> Default for PoolRotator<Hash> {
48	fn default() -> Self {
49		Self { ban_time: Duration::from_secs(60 * 30), banned_until: Default::default() }
50	}
51}
52
53impl<Hash: hash::Hash + Eq + Clone> PoolRotator<Hash> {
54	/// New rotator instance with specified ban time.
55	pub fn new(ban_time: Duration) -> Self {
56		Self { ban_time, banned_until: Default::default() }
57	}
58
59	/// Returns `true` if extrinsic hash is currently banned.
60	pub fn is_banned(&self, hash: &Hash) -> bool {
61		self.banned_until.read().contains_key(hash)
62	}
63
64	/// Bans given set of hashes.
65	pub fn ban(&self, now: &Instant, hashes: impl IntoIterator<Item = Hash>) {
66		let mut banned = self.banned_until.write();
67
68		for hash in hashes {
69			banned.insert(hash, *now + self.ban_time);
70		}
71
72		if banned.len() > 2 * EXPECTED_SIZE {
73			while banned.len() > EXPECTED_SIZE {
74				if let Some(key) = banned.keys().next().cloned() {
75					banned.remove(&key);
76				}
77			}
78		}
79	}
80
81	/// Bans extrinsic if it's stale.
82	///
83	/// Returns `true` if extrinsic is stale and got banned.
84	pub fn ban_if_stale<Ex>(
85		&self,
86		now: &Instant,
87		current_block: u64,
88		xt: &Transaction<Hash, Ex>,
89	) -> bool {
90		if xt.valid_till > current_block {
91			return false
92		}
93
94		self.ban(now, iter::once(xt.hash.clone()));
95		true
96	}
97
98	/// Removes timed bans.
99	pub fn clear_timeouts(&self, now: &Instant) {
100		let mut banned = self.banned_until.write();
101
102		banned.retain(|_, &mut v| v >= *now);
103	}
104}
105
106#[cfg(test)]
107mod tests {
108	use super::*;
109	use sp_runtime::transaction_validity::TransactionSource;
110
111	type Hash = u64;
112	type Ex = ();
113
114	fn rotator() -> PoolRotator<Hash> {
115		PoolRotator { ban_time: Duration::from_millis(10), ..Default::default() }
116	}
117
118	fn tx() -> (Hash, Transaction<Hash, Ex>) {
119		let hash = 5u64;
120		let tx = Transaction {
121			data: (),
122			bytes: 1,
123			hash,
124			priority: 5,
125			valid_till: 1,
126			requires: vec![],
127			provides: vec![],
128			propagate: true,
129			source: TransactionSource::External,
130		};
131
132		(hash, tx)
133	}
134
135	#[test]
136	fn should_not_ban_if_not_stale() {
137		// given
138		let (hash, tx) = tx();
139		let rotator = rotator();
140		assert!(!rotator.is_banned(&hash));
141		let now = Instant::now();
142		let past_block = 0;
143
144		// when
145		assert!(!rotator.ban_if_stale(&now, past_block, &tx));
146
147		// then
148		assert!(!rotator.is_banned(&hash));
149	}
150
151	#[test]
152	fn should_ban_stale_extrinsic() {
153		// given
154		let (hash, tx) = tx();
155		let rotator = rotator();
156		assert!(!rotator.is_banned(&hash));
157
158		// when
159		assert!(rotator.ban_if_stale(&Instant::now(), 1, &tx));
160
161		// then
162		assert!(rotator.is_banned(&hash));
163	}
164
165	#[test]
166	fn should_clear_banned() {
167		// given
168		let (hash, tx) = tx();
169		let rotator = rotator();
170		assert!(rotator.ban_if_stale(&Instant::now(), 1, &tx));
171		assert!(rotator.is_banned(&hash));
172
173		// when
174		let future = Instant::now() + rotator.ban_time + rotator.ban_time;
175		rotator.clear_timeouts(&future);
176
177		// then
178		assert!(!rotator.is_banned(&hash));
179	}
180
181	#[test]
182	fn should_garbage_collect() {
183		// given
184		fn tx_with(i: u64, valid_till: u64) -> Transaction<Hash, Ex> {
185			let hash = i;
186			Transaction {
187				data: (),
188				bytes: 2,
189				hash,
190				priority: 5,
191				valid_till,
192				requires: vec![],
193				provides: vec![],
194				propagate: true,
195				source: TransactionSource::External,
196			}
197		}
198
199		let rotator = rotator();
200
201		let now = Instant::now();
202		let past_block = 0;
203
204		// when
205		for i in 0..2 * EXPECTED_SIZE {
206			let tx = tx_with(i as u64, past_block);
207			assert!(rotator.ban_if_stale(&now, past_block, &tx));
208		}
209		assert_eq!(rotator.banned_until.read().len(), 2 * EXPECTED_SIZE);
210
211		// then
212		let tx = tx_with(2 * EXPECTED_SIZE as u64, past_block);
213		// trigger a garbage collection
214		assert!(rotator.ban_if_stale(&now, past_block, &tx));
215		assert_eq!(rotator.banned_until.read().len(), EXPECTED_SIZE);
216	}
217}
sc_transaction_pool/graph/rotator.rs

sc_transaction_pool/graph/
rotator.rs
