polkadot_collator_protocol/validator_side/
claim_queue_state.rs

1// Copyright (C) Parity Technologies (UK) Ltd.
2// This file is part of Polkadot.
3
4// Polkadot is free software: you can redistribute it and/or modify
5// it under the terms of the GNU General Public License as published by
6// the Free Software Foundation, either version 3 of the License, or
7// (at your option) any later version.
8
9// Polkadot is distributed in the hope that it will be useful,
10// but WITHOUT ANY WARRANTY; without even the implied warranty of
11// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12// GNU General Public License for more details.
13
14// You should have received a copy of the GNU General Public License
15// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.
16
17//! `ClaimQueueState` tracks the state of the claim queue over a set of relay blocks. Refer to
18//! [`ClaimQueueState`] for more details.
19
20use std::collections::VecDeque;
21
22use crate::LOG_TARGET;
23use polkadot_primitives::{Hash, Id as ParaId};
24
25/// Represents a single claim from the claim queue, mapped to the relay chain block where it could
26/// be backed on-chain.
27#[derive(Debug, PartialEq)]
28struct ClaimInfo {
29	// Hash of the relay chain block. Can be `None` if it is still not known (a future block).
30	hash: Option<Hash>,
31	/// Represents the `ParaId` scheduled for the block. Can be `None` if nothing is scheduled.
32	claim: Option<ParaId>,
33	/// The length of the claim queue at the block. It is used to determine the 'block window'
34	/// where a claim can be made.
35	claim_queue_len: usize,
36	/// A flag that indicates if the slot is claimed or not.
37	claimed: bool,
38}
39
40/// Tracks the state of the claim queue over a set of relay blocks.
41///
42/// Generally the claim queue represents the `ParaId` that should be scheduled at the current block
43/// (the first element of the claim queue) and N other `ParaId`s which are supposed to be scheduled
44/// on the next relay blocks. In other words the claim queue is a rolling window giving a hint what
45/// should be built/fetched/accepted (depending on the context) at each block.
46///
47/// Since the claim queue peeks into the future blocks there is a relation between the claim queue
48/// state between the current block and the future blocks.
49/// Let's see an example with 2 co-scheduled parachains:
50/// - relay parent 1; Claim queue: [A, B, A]
51/// - relay parent 2; Claim queue: [B, A, B]
52/// - relay parent 3; Claim queue: [A, B, A]
53/// - and so on
54///
55/// Note that at rp1 the second element in the claim queue is equal to the first one in rp2. Also
56/// the third element of the claim queue at rp1 is equal to the second one in rp2 and the first one
57/// in rp3.
58///
59/// So if we want to claim the third slot at rp 1 we are also claiming the second at rp2 and first
60/// at rp3. To track this in a simple way we can project the claim queue onto the relay blocks like
61/// this:
62///               [A]   [B]   [A] -> this is the claim queue at rp3
63///         [B]   [A]   [B]       -> this is the claim queue at rp2
64///   [A]   [B]   [A]	          -> this is the claim queue at rp1
65/// [RP 1][RP 2][RP 3][RP X][RP Y] -> relay blocks, RP x and RP Y are future blocks
66///
67/// Note that the claims at each column are the same so we can simplify this by just projecting a
68/// single claim over a block:
69///   [A]   [B]   [A]   [B]   [A]  -> claims effectively are the same
70/// [RP 1][RP 2][RP 3][RP X][RP Y] -> relay blocks, RP x and RP Y are future blocks
71///
72/// Basically this is how `ClaimQueueState` works. It keeps track of claims at each block by mapping
73/// claims to relay blocks.
74///
75/// How making a claim works?
76/// At each relay block we keep track how long is the claim queue. This is a 'window' where we can
77/// make a claim. So adding a claim just looks for a free spot at this window and claims it.
78///
79/// Note on adding a new leaf.
80/// When a new leaf is added we check if the first element in its claim queue matches with the
81/// projection on the first element in 'future blocks'. If yes - the new relay block inherits this
82/// claim. If not - this means that the claim queue changed for some reason so the claim can't be
83/// inherited. This should not happen under normal circumstances. But if it happens it means that we
84/// have got one claim which won't be satisfied in the worst case scenario.
85pub(crate) struct ClaimQueueState {
86	block_state: VecDeque<ClaimInfo>,
87	future_blocks: VecDeque<ClaimInfo>,
88}
89
90impl ClaimQueueState {
91	pub(crate) fn new() -> Self {
92		Self { block_state: VecDeque::new(), future_blocks: VecDeque::new() }
93	}
94
95	// Appends a new leaf
96	pub(crate) fn add_leaf(&mut self, hash: &Hash, claim_queue: &Vec<ParaId>) {
97		if self.block_state.iter().any(|s| s.hash == Some(*hash)) {
98			return
99		}
100
101		// First check if our view for the future blocks is consistent with the one in the claim
102		// queue of the new block. If not - the claim queue has changed for some reason and we need
103		// to readjust our view.
104		for (idx, expected_claim) in claim_queue.iter().enumerate() {
105			match self.future_blocks.get_mut(idx) {
106				Some(future_block) =>
107					if future_block.claim.as_ref() != Some(expected_claim) {
108						// There is an inconsistency. Update our view with the one from the claim
109						// queue. `claimed` can't be true anymore since the `ParaId` has changed.
110						future_block.claimed = false;
111						future_block.claim = Some(*expected_claim);
112					},
113				None => {
114					self.future_blocks.push_back(ClaimInfo {
115						hash: None,
116						claim: Some(*expected_claim),
117						// For future blocks we don't know the size of the claim queue.
118						// `claim_queue_len` could be an option but there is not much benefit from
119						// the extra boilerplate code to handle it. We set it to one since we
120						// usually know about one claim at each future block but this value is not
121						// used anywhere in the code.
122						claim_queue_len: 1,
123						claimed: false,
124					});
125				},
126			}
127		}
128
129		// Now pop the first future block and add it as a leaf
130		let claim_info = if let Some(new_leaf) = self.future_blocks.pop_front() {
131			ClaimInfo {
132				hash: Some(*hash),
133				claim: claim_queue.first().copied(),
134				claim_queue_len: claim_queue.len(),
135				claimed: new_leaf.claimed,
136			}
137		} else {
138			// maybe the claim queue was empty but we still need to add a leaf
139			ClaimInfo {
140				hash: Some(*hash),
141				claim: claim_queue.first().copied(),
142				claim_queue_len: claim_queue.len(),
143				claimed: false,
144			}
145		};
146
147		// `future_blocks` can't be longer than the length of the claim queue at the last block - 1.
148		// For example this can happen if at relay block N we have got a claim queue of a length 4
149		// and it's shrunk to 2.
150		self.future_blocks.truncate(claim_queue.len().saturating_sub(1));
151
152		self.block_state.push_back(claim_info);
153	}
154
155	fn get_window<'a>(
156		&'a mut self,
157		relay_parent: &'a Hash,
158	) -> impl Iterator<Item = &'a mut ClaimInfo> + 'a {
159		let mut window = self
160			.block_state
161			.iter_mut()
162			.skip_while(|b| b.hash != Some(*relay_parent))
163			.peekable();
164		let cq_len = window.peek().map_or(0, |b| b.claim_queue_len);
165		window.chain(self.future_blocks.iter_mut()).take(cq_len)
166	}
167
168	pub(crate) fn claim_at(&mut self, relay_parent: &Hash, para_id: &ParaId) -> bool {
169		gum::trace!(
170			target: LOG_TARGET,
171			?para_id,
172			?relay_parent,
173			"claim_at"
174		);
175		self.find_a_claim(relay_parent, para_id, true)
176	}
177
178	pub(crate) fn can_claim_at(&mut self, relay_parent: &Hash, para_id: &ParaId) -> bool {
179		gum::trace!(
180			target: LOG_TARGET,
181			?para_id,
182			?relay_parent,
183			"can_claim_at"
184		);
185
186		self.find_a_claim(relay_parent, para_id, false)
187	}
188
189	// Returns `true` if there is a claim within `relay_parent`'s view of the claim queue for
190	// `para_id`. If `claim_it` is set to `true` the slot is claimed. Otherwise the function just
191	// reports the availability of the slot.
192	fn find_a_claim(&mut self, relay_parent: &Hash, para_id: &ParaId, claim_it: bool) -> bool {
193		let window = self.get_window(relay_parent);
194
195		for w in window {
196			gum::trace!(
197				target: LOG_TARGET,
198				?para_id,
199				?relay_parent,
200				claim_info=?w,
201				?claim_it,
202				"Checking claim"
203			);
204
205			if !w.claimed && w.claim == Some(*para_id) {
206				w.claimed = claim_it;
207				return true
208			}
209		}
210
211		false
212	}
213
214	pub(crate) fn unclaimed_at(&mut self, relay_parent: &Hash) -> Vec<ParaId> {
215		let window = self.get_window(relay_parent);
216
217		window.filter(|b| !b.claimed).filter_map(|b| b.claim).collect()
218	}
219}
220
221#[cfg(test)]
222mod test {
223	use super::*;
224
225	#[test]
226	fn sane_initial_state() {
227		let mut state = ClaimQueueState::new();
228		let relay_parent = Hash::from_low_u64_be(1);
229		let para_id = ParaId::new(1);
230
231		assert!(!state.can_claim_at(&relay_parent, &para_id));
232		assert!(!state.claim_at(&relay_parent, &para_id));
233		assert_eq!(state.unclaimed_at(&relay_parent), vec![]);
234	}
235
236	#[test]
237	fn add_leaf_works() {
238		let mut state = ClaimQueueState::new();
239		let relay_parent_a = Hash::from_low_u64_be(1);
240		let para_id = ParaId::new(1);
241		let claim_queue = vec![para_id, para_id, para_id];
242
243		state.add_leaf(&relay_parent_a, &claim_queue);
244		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id, para_id, para_id]);
245
246		assert_eq!(
247			state.block_state,
248			VecDeque::from(vec![ClaimInfo {
249				hash: Some(relay_parent_a),
250				claim: Some(para_id),
251				claim_queue_len: 3,
252				claimed: false,
253			},])
254		);
255		assert_eq!(
256			state.future_blocks,
257			VecDeque::from(vec![
258				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: false },
259				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: false }
260			])
261		);
262
263		// should be no op
264		state.add_leaf(&relay_parent_a, &claim_queue);
265		assert_eq!(state.block_state.len(), 1);
266		assert_eq!(state.future_blocks.len(), 2);
267
268		// add another leaf
269		let relay_parent_b = Hash::from_low_u64_be(2);
270		state.add_leaf(&relay_parent_b, &claim_queue);
271
272		assert_eq!(
273			state.block_state,
274			VecDeque::from(vec![
275				ClaimInfo {
276					hash: Some(relay_parent_a),
277					claim: Some(para_id),
278					claim_queue_len: 3,
279					claimed: false,
280				},
281				ClaimInfo {
282					hash: Some(relay_parent_b),
283					claim: Some(para_id),
284					claim_queue_len: 3,
285					claimed: false,
286				}
287			])
288		);
289		assert_eq!(
290			state.future_blocks,
291			VecDeque::from(vec![
292				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: false },
293				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: false }
294			])
295		);
296
297		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id, para_id, para_id]);
298		assert_eq!(state.unclaimed_at(&relay_parent_b), vec![para_id, para_id, para_id]);
299	}
300
301	#[test]
302	fn claims_at_separate_relay_parents_work() {
303		let mut state = ClaimQueueState::new();
304		let relay_parent_a = Hash::from_low_u64_be(1);
305		let relay_parent_b = Hash::from_low_u64_be(2);
306		let para_id = ParaId::new(1);
307		let claim_queue = vec![para_id, para_id, para_id];
308
309		state.add_leaf(&relay_parent_a, &claim_queue);
310		state.add_leaf(&relay_parent_b, &claim_queue);
311
312		// add one claim for a
313		assert!(state.can_claim_at(&relay_parent_a, &para_id));
314		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id, para_id, para_id]);
315		assert!(state.claim_at(&relay_parent_a, &para_id));
316
317		// and one for b
318		assert!(state.can_claim_at(&relay_parent_b, &para_id));
319		assert_eq!(state.unclaimed_at(&relay_parent_b), vec![para_id, para_id, para_id]);
320		assert!(state.claim_at(&relay_parent_b, &para_id));
321
322		// a should have one claim since the one for b was claimed
323		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id]);
324		// and two more for b
325		assert_eq!(state.unclaimed_at(&relay_parent_b), vec![para_id, para_id]);
326
327		assert_eq!(
328			state.block_state,
329			VecDeque::from(vec![
330				ClaimInfo {
331					hash: Some(relay_parent_a),
332					claim: Some(para_id),
333					claim_queue_len: 3,
334					claimed: true,
335				},
336				ClaimInfo {
337					hash: Some(relay_parent_b),
338					claim: Some(para_id),
339					claim_queue_len: 3,
340					claimed: true,
341				}
342			])
343		);
344		assert_eq!(
345			state.future_blocks,
346			VecDeque::from(vec![
347				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: false },
348				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: false }
349			])
350		);
351	}
352
353	#[test]
354	fn claims_are_transferred_to_next_slot() {
355		let mut state = ClaimQueueState::new();
356		let relay_parent_a = Hash::from_low_u64_be(1);
357		let para_id = ParaId::new(1);
358		let claim_queue = vec![para_id, para_id, para_id];
359
360		state.add_leaf(&relay_parent_a, &claim_queue);
361
362		// add two claims, 2nd should be transferred to a new leaf
363		assert!(state.can_claim_at(&relay_parent_a, &para_id));
364		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id, para_id, para_id]);
365		assert!(state.claim_at(&relay_parent_a, &para_id));
366
367		assert!(state.can_claim_at(&relay_parent_a, &para_id));
368		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id, para_id]);
369		assert!(state.claim_at(&relay_parent_a, &para_id));
370
371		assert_eq!(
372			state.block_state,
373			VecDeque::from(vec![ClaimInfo {
374				hash: Some(relay_parent_a),
375				claim: Some(para_id),
376				claim_queue_len: 3,
377				claimed: true,
378			},])
379		);
380		assert_eq!(
381			state.future_blocks,
382			VecDeque::from(vec![
383				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: true },
384				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: false }
385			])
386		);
387
388		// one more
389		assert!(state.can_claim_at(&relay_parent_a, &para_id));
390		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id]);
391		assert!(state.claim_at(&relay_parent_a, &para_id));
392
393		assert_eq!(
394			state.block_state,
395			VecDeque::from(vec![ClaimInfo {
396				hash: Some(relay_parent_a),
397				claim: Some(para_id),
398				claim_queue_len: 3,
399				claimed: true,
400			},])
401		);
402		assert_eq!(
403			state.future_blocks,
404			VecDeque::from(vec![
405				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: true },
406				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: true }
407			])
408		);
409
410		// no more claims
411		assert!(!state.can_claim_at(&relay_parent_a, &para_id));
412		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![]);
413	}
414
415	#[test]
416	fn claims_are_transferred_to_new_leaves() {
417		let mut state = ClaimQueueState::new();
418		let relay_parent_a = Hash::from_low_u64_be(1);
419		let para_id = ParaId::new(1);
420		let claim_queue = vec![para_id, para_id, para_id];
421
422		state.add_leaf(&relay_parent_a, &claim_queue);
423
424		for _ in 0..3 {
425			assert!(state.can_claim_at(&relay_parent_a, &para_id));
426			assert!(state.claim_at(&relay_parent_a, &para_id));
427		}
428
429		assert_eq!(
430			state.block_state,
431			VecDeque::from(vec![ClaimInfo {
432				hash: Some(relay_parent_a),
433				claim: Some(para_id),
434				claim_queue_len: 3,
435				claimed: true,
436			},])
437		);
438		assert_eq!(
439			state.future_blocks,
440			VecDeque::from(vec![
441				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: true },
442				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: true }
443			])
444		);
445
446		// no more claims
447		assert!(!state.can_claim_at(&relay_parent_a, &para_id));
448
449		// new leaf
450		let relay_parent_b = Hash::from_low_u64_be(2);
451		state.add_leaf(&relay_parent_b, &claim_queue);
452
453		assert_eq!(
454			state.block_state,
455			VecDeque::from(vec![
456				ClaimInfo {
457					hash: Some(relay_parent_a),
458					claim: Some(para_id),
459					claim_queue_len: 3,
460					claimed: true,
461				},
462				ClaimInfo {
463					hash: Some(relay_parent_b),
464					claim: Some(para_id),
465					claim_queue_len: 3,
466					claimed: true,
467				}
468			])
469		);
470		assert_eq!(
471			state.future_blocks,
472			VecDeque::from(vec![
473				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: true },
474				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: false }
475			])
476		);
477
478		// still no claims for a
479		assert!(!state.can_claim_at(&relay_parent_a, &para_id));
480
481		// but can accept for b
482		assert!(state.can_claim_at(&relay_parent_b, &para_id));
483		assert!(state.claim_at(&relay_parent_b, &para_id));
484
485		assert_eq!(
486			state.block_state,
487			VecDeque::from(vec![
488				ClaimInfo {
489					hash: Some(relay_parent_a),
490					claim: Some(para_id),
491					claim_queue_len: 3,
492					claimed: true,
493				},
494				ClaimInfo {
495					hash: Some(relay_parent_b),
496					claim: Some(para_id),
497					claim_queue_len: 3,
498					claimed: true,
499				}
500			])
501		);
502		assert_eq!(
503			state.future_blocks,
504			VecDeque::from(vec![
505				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: true },
506				ClaimInfo { hash: None, claim: Some(para_id), claim_queue_len: 1, claimed: true }
507			])
508		);
509	}
510
511	#[test]
512	fn two_paras() {
513		let mut state = ClaimQueueState::new();
514		let relay_parent_a = Hash::from_low_u64_be(1);
515		let para_id_a = ParaId::new(1);
516		let para_id_b = ParaId::new(2);
517		let claim_queue = vec![para_id_a, para_id_b, para_id_a];
518
519		state.add_leaf(&relay_parent_a, &claim_queue);
520		assert!(state.can_claim_at(&relay_parent_a, &para_id_a));
521		assert!(state.can_claim_at(&relay_parent_a, &para_id_b));
522		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id_a, para_id_b, para_id_a]);
523
524		assert_eq!(
525			state.block_state,
526			VecDeque::from(vec![ClaimInfo {
527				hash: Some(relay_parent_a),
528				claim: Some(para_id_a),
529				claim_queue_len: 3,
530				claimed: false,
531			},])
532		);
533		assert_eq!(
534			state.future_blocks,
535			VecDeque::from(vec![
536				ClaimInfo {
537					hash: None,
538					claim: Some(para_id_b),
539					claim_queue_len: 1,
540					claimed: false
541				},
542				ClaimInfo {
543					hash: None,
544					claim: Some(para_id_a),
545					claim_queue_len: 1,
546					claimed: false
547				}
548			])
549		);
550
551		assert!(state.claim_at(&relay_parent_a, &para_id_a));
552		assert!(state.can_claim_at(&relay_parent_a, &para_id_a));
553		assert!(state.can_claim_at(&relay_parent_a, &para_id_b));
554		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id_b, para_id_a]);
555
556		assert_eq!(
557			state.block_state,
558			VecDeque::from(vec![ClaimInfo {
559				hash: Some(relay_parent_a),
560				claim: Some(para_id_a),
561				claim_queue_len: 3,
562				claimed: true,
563			},])
564		);
565		assert_eq!(
566			state.future_blocks,
567			VecDeque::from(vec![
568				ClaimInfo {
569					hash: None,
570					claim: Some(para_id_b),
571					claim_queue_len: 1,
572					claimed: false
573				},
574				ClaimInfo {
575					hash: None,
576					claim: Some(para_id_a),
577					claim_queue_len: 1,
578					claimed: false
579				}
580			])
581		);
582
583		assert!(state.claim_at(&relay_parent_a, &para_id_a));
584		assert!(!state.can_claim_at(&relay_parent_a, &para_id_a));
585		assert!(state.can_claim_at(&relay_parent_a, &para_id_b));
586		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id_b]);
587
588		assert_eq!(
589			state.block_state,
590			VecDeque::from(vec![ClaimInfo {
591				hash: Some(relay_parent_a),
592				claim: Some(para_id_a),
593				claim_queue_len: 3,
594				claimed: true,
595			},])
596		);
597		assert_eq!(
598			state.future_blocks,
599			VecDeque::from(vec![
600				ClaimInfo {
601					hash: None,
602					claim: Some(para_id_b),
603					claim_queue_len: 1,
604					claimed: false
605				},
606				ClaimInfo { hash: None, claim: Some(para_id_a), claim_queue_len: 1, claimed: true }
607			])
608		);
609
610		assert!(state.claim_at(&relay_parent_a, &para_id_b));
611		assert!(!state.can_claim_at(&relay_parent_a, &para_id_a));
612		assert!(!state.can_claim_at(&relay_parent_a, &para_id_b));
613		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![]);
614
615		assert_eq!(
616			state.block_state,
617			VecDeque::from(vec![ClaimInfo {
618				hash: Some(relay_parent_a),
619				claim: Some(para_id_a),
620				claim_queue_len: 3,
621				claimed: true,
622			},])
623		);
624		assert_eq!(
625			state.future_blocks,
626			VecDeque::from(vec![
627				ClaimInfo { hash: None, claim: Some(para_id_b), claim_queue_len: 1, claimed: true },
628				ClaimInfo { hash: None, claim: Some(para_id_a), claim_queue_len: 1, claimed: true }
629			])
630		);
631	}
632
633	#[test]
634	fn claim_queue_changes_unexpectedly() {
635		let mut state = ClaimQueueState::new();
636		let relay_parent_a = Hash::from_low_u64_be(1);
637		let para_id_a = ParaId::new(1);
638		let para_id_b = ParaId::new(2);
639		let claim_queue_a = vec![para_id_a, para_id_b, para_id_a];
640
641		state.add_leaf(&relay_parent_a, &claim_queue_a);
642		assert!(state.can_claim_at(&relay_parent_a, &para_id_a));
643		assert!(state.can_claim_at(&relay_parent_a, &para_id_b));
644		assert!(state.claim_at(&relay_parent_a, &para_id_a));
645		assert!(state.claim_at(&relay_parent_a, &para_id_a));
646		assert!(state.claim_at(&relay_parent_a, &para_id_b));
647		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![]);
648
649		assert_eq!(
650			state.block_state,
651			VecDeque::from(vec![ClaimInfo {
652				hash: Some(relay_parent_a),
653				claim: Some(para_id_a),
654				claim_queue_len: 3,
655				claimed: true,
656			},])
657		);
658		assert_eq!(
659			state.future_blocks,
660			VecDeque::from(vec![
661				ClaimInfo { hash: None, claim: Some(para_id_b), claim_queue_len: 1, claimed: true },
662				ClaimInfo { hash: None, claim: Some(para_id_a), claim_queue_len: 1, claimed: true }
663			])
664		);
665
666		let relay_parent_b = Hash::from_low_u64_be(2);
667		let claim_queue_b = vec![para_id_a, para_id_a, para_id_a]; // should be [b, a, ...]
668		state.add_leaf(&relay_parent_b, &claim_queue_b);
669
670		// because of the unexpected change in claim queue we lost the claim for paraB and have one
671		// unclaimed for paraA
672		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id_a]);
673
674		assert_eq!(
675			state.block_state,
676			VecDeque::from(vec![
677				ClaimInfo {
678					hash: Some(relay_parent_a),
679					claim: Some(para_id_a),
680					claim_queue_len: 3,
681					claimed: true,
682				},
683				ClaimInfo {
684					hash: Some(relay_parent_b),
685					claim: Some(para_id_a),
686					claim_queue_len: 3,
687					claimed: false,
688				}
689			])
690		);
691		assert_eq!(
692			state.future_blocks,
693			// since the 3rd slot of the claim queue at rp1 is equal to the second one in rp2, this
694			// claim still exists
695			VecDeque::from(vec![
696				ClaimInfo { hash: None, claim: Some(para_id_a), claim_queue_len: 1, claimed: true },
697				ClaimInfo {
698					hash: None,
699					claim: Some(para_id_a),
700					claim_queue_len: 1,
701					claimed: false
702				}
703			])
704		);
705	}
706
707	#[test]
708	fn claim_queue_changes_unexpectedly_with_two_blocks() {
709		let mut state = ClaimQueueState::new();
710		let relay_parent_a = Hash::from_low_u64_be(1);
711		let para_id_a = ParaId::new(1);
712		let para_id_b = ParaId::new(2);
713		let claim_queue_a = vec![para_id_a, para_id_b, para_id_b];
714
715		state.add_leaf(&relay_parent_a, &claim_queue_a);
716		assert!(state.can_claim_at(&relay_parent_a, &para_id_a));
717		assert!(state.can_claim_at(&relay_parent_a, &para_id_b));
718		assert!(state.claim_at(&relay_parent_a, &para_id_a));
719		assert!(state.claim_at(&relay_parent_a, &para_id_b));
720		assert!(state.claim_at(&relay_parent_a, &para_id_b));
721		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![]);
722
723		assert_eq!(
724			state.block_state,
725			VecDeque::from(vec![ClaimInfo {
726				hash: Some(relay_parent_a),
727				claim: Some(para_id_a),
728				claim_queue_len: 3,
729				claimed: true,
730			},])
731		);
732		assert_eq!(
733			state.future_blocks,
734			VecDeque::from(vec![
735				ClaimInfo { hash: None, claim: Some(para_id_b), claim_queue_len: 1, claimed: true },
736				ClaimInfo { hash: None, claim: Some(para_id_b), claim_queue_len: 1, claimed: true }
737			])
738		);
739
740		let relay_parent_b = Hash::from_low_u64_be(2);
741		let claim_queue_b = vec![para_id_a, para_id_a, para_id_a]; // should be [b, b, ...]
742		state.add_leaf(&relay_parent_b, &claim_queue_b);
743
744		// because of the unexpected change in claim queue we lost both claims for paraB and have
745		// two unclaimed for paraA
746		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id_a, para_id_a]);
747
748		assert_eq!(
749			state.block_state,
750			VecDeque::from(vec![
751				ClaimInfo {
752					hash: Some(relay_parent_a),
753					claim: Some(para_id_a),
754					claim_queue_len: 3,
755					claimed: true,
756				},
757				ClaimInfo {
758					hash: Some(relay_parent_b),
759					claim: Some(para_id_a),
760					claim_queue_len: 3,
761					claimed: false,
762				}
763			])
764		);
765		assert_eq!(
766			state.future_blocks,
767			VecDeque::from(vec![
768				ClaimInfo {
769					hash: None,
770					claim: Some(para_id_a),
771					claim_queue_len: 1,
772					claimed: false
773				},
774				ClaimInfo {
775					hash: None,
776					claim: Some(para_id_a),
777					claim_queue_len: 1,
778					claimed: false
779				}
780			])
781		);
782	}
783
784	#[test]
785	fn empty_claim_queue() {
786		let mut state = ClaimQueueState::new();
787		let relay_parent_a = Hash::from_low_u64_be(1);
788		let para_id_a = ParaId::new(1);
789		let claim_queue_a = vec![];
790
791		state.add_leaf(&relay_parent_a, &claim_queue_a);
792		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![]);
793
794		assert_eq!(
795			state.block_state,
796			VecDeque::from(vec![ClaimInfo {
797				hash: Some(relay_parent_a),
798				claim: None,
799				claim_queue_len: 0,
800				claimed: false,
801			},])
802		);
803		// no claim queue so we know nothing about future blocks
804		assert!(state.future_blocks.is_empty());
805
806		assert!(!state.can_claim_at(&relay_parent_a, &para_id_a));
807		assert!(!state.claim_at(&relay_parent_a, &para_id_a));
808		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![]);
809
810		let relay_parent_b = Hash::from_low_u64_be(2);
811		let claim_queue_b = vec![para_id_a];
812		state.add_leaf(&relay_parent_b, &claim_queue_b);
813
814		assert_eq!(
815			state.block_state,
816			VecDeque::from(vec![
817				ClaimInfo {
818					hash: Some(relay_parent_a),
819					claim: None,
820					claim_queue_len: 0,
821					claimed: false,
822				},
823				ClaimInfo {
824					hash: Some(relay_parent_b),
825					claim: Some(para_id_a),
826					claim_queue_len: 1,
827					claimed: false,
828				},
829			])
830		);
831		// claim queue with length 1 doesn't say anything about future blocks
832		assert!(state.future_blocks.is_empty());
833
834		assert!(!state.can_claim_at(&relay_parent_a, &para_id_a));
835		assert!(!state.claim_at(&relay_parent_a, &para_id_a));
836		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![]);
837
838		assert!(state.can_claim_at(&relay_parent_b, &para_id_a));
839		assert_eq!(state.unclaimed_at(&relay_parent_b), vec![para_id_a]);
840		assert!(state.claim_at(&relay_parent_b, &para_id_a));
841
842		let relay_parent_c = Hash::from_low_u64_be(3);
843		let claim_queue_c = vec![para_id_a, para_id_a];
844		state.add_leaf(&relay_parent_c, &claim_queue_c);
845
846		assert_eq!(
847			state.block_state,
848			VecDeque::from(vec![
849				ClaimInfo {
850					hash: Some(relay_parent_a),
851					claim: None,
852					claim_queue_len: 0,
853					claimed: false,
854				},
855				ClaimInfo {
856					hash: Some(relay_parent_b),
857					claim: Some(para_id_a),
858					claim_queue_len: 1,
859					claimed: true,
860				},
861				ClaimInfo {
862					hash: Some(relay_parent_c),
863					claim: Some(para_id_a),
864					claim_queue_len: 2,
865					claimed: false,
866				},
867			])
868		);
869		// claim queue with length 2 fills only one future block
870		assert_eq!(
871			state.future_blocks,
872			VecDeque::from(vec![ClaimInfo {
873				hash: None,
874				claim: Some(para_id_a),
875				claim_queue_len: 1,
876				claimed: false,
877			},])
878		);
879
880		assert!(!state.can_claim_at(&relay_parent_a, &para_id_a));
881		assert!(!state.claim_at(&relay_parent_a, &para_id_a));
882		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![]);
883
884		// already claimed
885		assert!(!state.can_claim_at(&relay_parent_b, &para_id_a));
886		assert_eq!(state.unclaimed_at(&relay_parent_b), vec![]);
887		assert!(!state.claim_at(&relay_parent_b, &para_id_a));
888
889		assert!(state.can_claim_at(&relay_parent_c, &para_id_a));
890		assert_eq!(state.unclaimed_at(&relay_parent_c), vec![para_id_a, para_id_a]);
891	}
892
893	#[test]
894	fn claim_queue_becomes_shorter() {
895		let mut state = ClaimQueueState::new();
896		let relay_parent_a = Hash::from_low_u64_be(1);
897		let para_id_a = ParaId::new(1);
898		let para_id_b = ParaId::new(2);
899		let claim_queue_a = vec![para_id_a, para_id_b, para_id_a];
900
901		state.add_leaf(&relay_parent_a, &claim_queue_a);
902		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id_a, para_id_b, para_id_a]);
903
904		assert_eq!(
905			state.block_state,
906			VecDeque::from(vec![ClaimInfo {
907				hash: Some(relay_parent_a),
908				claim: Some(para_id_a),
909				claim_queue_len: 3,
910				claimed: false,
911			},])
912		);
913		assert_eq!(
914			state.future_blocks,
915			VecDeque::from(vec![
916				ClaimInfo {
917					hash: None,
918					claim: Some(para_id_b),
919					claim_queue_len: 1,
920					claimed: false
921				},
922				ClaimInfo {
923					hash: None,
924					claim: Some(para_id_a),
925					claim_queue_len: 1,
926					claimed: false
927				}
928			])
929		);
930
931		let relay_parent_b = Hash::from_low_u64_be(2);
932		let claim_queue_b = vec![para_id_a, para_id_b]; // should be [b, a]
933		state.add_leaf(&relay_parent_b, &claim_queue_b);
934
935		assert_eq!(state.unclaimed_at(&relay_parent_b), vec![para_id_a, para_id_b]);
936		// claims for `relay_parent_a` has changed.
937		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id_a, para_id_a, para_id_b]);
938
939		assert_eq!(
940			state.block_state,
941			VecDeque::from(vec![
942				ClaimInfo {
943					hash: Some(relay_parent_a),
944					claim: Some(para_id_a),
945					claim_queue_len: 3,
946					claimed: false,
947				},
948				ClaimInfo {
949					hash: Some(relay_parent_b),
950					claim: Some(para_id_a),
951					claim_queue_len: 2,
952					claimed: false,
953				}
954			])
955		);
956		assert_eq!(
957			state.future_blocks,
958			VecDeque::from(vec![ClaimInfo {
959				hash: None,
960				claim: Some(para_id_b),
961				claim_queue_len: 1,
962				claimed: false
963			},])
964		);
965	}
966
967	#[test]
968	fn claim_queue_becomes_shorter_and_drops_future_claims() {
969		let mut state = ClaimQueueState::new();
970		let relay_parent_a = Hash::from_low_u64_be(1);
971		let para_id_a = ParaId::new(1);
972		let para_id_b = ParaId::new(2);
973		let claim_queue_a = vec![para_id_a, para_id_b, para_id_a, para_id_b];
974
975		state.add_leaf(&relay_parent_a, &claim_queue_a);
976
977		assert_eq!(
978			state.unclaimed_at(&relay_parent_a),
979			vec![para_id_a, para_id_b, para_id_a, para_id_b]
980		);
981
982		// We start with claim queue len 4.
983		assert_eq!(
984			state.block_state,
985			VecDeque::from(vec![ClaimInfo {
986				hash: Some(relay_parent_a),
987				claim: Some(para_id_a),
988				claim_queue_len: 4,
989				claimed: false,
990			},])
991		);
992		// we have got three future blocks
993		assert_eq!(
994			state.future_blocks,
995			VecDeque::from(vec![
996				ClaimInfo {
997					hash: None,
998					claim: Some(para_id_b),
999					claim_queue_len: 1,
1000					claimed: false
1001				},
1002				ClaimInfo {
1003					hash: None,
1004					claim: Some(para_id_a),
1005					claim_queue_len: 1,
1006					claimed: false
1007				},
1008				ClaimInfo {
1009					hash: None,
1010					claim: Some(para_id_b),
1011					claim_queue_len: 1,
1012					claimed: false
1013				}
1014			])
1015		);
1016
1017		// The next claim len is 2, so we loose one future block
1018		let relay_parent_b = Hash::from_low_u64_be(2);
1019		let para_id_a = ParaId::new(1);
1020		let para_id_b = ParaId::new(2);
1021		let claim_queue_b = vec![para_id_b, para_id_a];
1022		state.add_leaf(&relay_parent_b, &claim_queue_b);
1023
1024		assert_eq!(state.unclaimed_at(&relay_parent_a), vec![para_id_a, para_id_b, para_id_a]);
1025		assert_eq!(state.unclaimed_at(&relay_parent_b), vec![para_id_b, para_id_a]);
1026
1027		assert_eq!(
1028			state.block_state,
1029			VecDeque::from(vec![
1030				ClaimInfo {
1031					hash: Some(relay_parent_a),
1032					claim: Some(para_id_a),
1033					claim_queue_len: 4,
1034					claimed: false,
1035				},
1036				ClaimInfo {
1037					hash: Some(relay_parent_b),
1038					claim: Some(para_id_b),
1039					claim_queue_len: 2,
1040					claimed: false,
1041				}
1042			])
1043		);
1044
1045		assert_eq!(
1046			state.future_blocks,
1047			VecDeque::from(vec![ClaimInfo {
1048				hash: None,
1049				claim: Some(para_id_a),
1050				claim_queue_len: 1,
1051				claimed: false
1052			},])
1053		);
1054	}
1055}
polkadot_collator_protocol/validator_side/claim_queue_state.rs

polkadot_collator_protocol/validator_side/
claim_queue_state.rs
