mod.rs 18.3 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
// Copyright 2020 Parity Technologies (UK) Ltd.
// This file is part of Polkadot.

// Polkadot is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.

// Polkadot is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with Polkadot.  If not, see <http://www.gnu.org/licenses/>.

17
//! Version 1 of the DB schema.
18

19
use kvdb::{DBTransaction, KeyValueDB};
20
use polkadot_node_primitives::approval::{DelayTranche, AssignmentCert};
21
22
use polkadot_primitives::v1::{
	ValidatorIndex, GroupIndex, CandidateReceipt, SessionIndex, CoreIndex,
23
	BlockNumber, Hash, CandidateHash, ValidatorSignature,
24
};
Bastian Köcher's avatar
Bastian Köcher committed
25
use sp_consensus_slots::Slot;
26
27
28
29
30
31
32
use parity_scale_codec::{Encode, Decode};

use std::collections::{BTreeMap, HashMap};
use std::collections::hash_map::Entry;
use bitvec::{vec::BitVec, order::Lsb0 as BitOrderLsb0};

#[cfg(test)]
33
pub mod tests;
34

35
36
37
38
39
40
41
// slot_duration * 2 + DelayTranche gives the number of delay tranches since the
// unix epoch.
#[derive(Encode, Decode, Clone, Copy, Debug, PartialEq)]
pub struct Tick(u64);

pub type Bitfield = BitVec<BitOrderLsb0, u8>;

42
43
const STORED_BLOCKS_KEY: &[u8] = b"Approvals_StoredBlocks";

44
45
46
47
48
49
50
/// The database config.
#[derive(Debug, Clone, Copy)]
pub struct Config {
	/// The column family in the database where data is stored.
	pub col_data: u32,
}

51
52
53
54
55
56
57
58
59
60
/// Details pertaining to our assignment on a block.
#[derive(Encode, Decode, Debug, Clone, PartialEq)]
pub struct OurAssignment {
	pub cert: AssignmentCert,
	pub tranche: DelayTranche,
	pub validator_index: ValidatorIndex,
	// Whether the assignment has been triggered already.
	pub triggered: bool,
}

61
/// Metadata regarding a specific tranche of assignments for a specific candidate.
62
63
64
#[derive(Encode, Decode, Debug, Clone, PartialEq)]
pub struct TrancheEntry {
	pub tranche: DelayTranche,
65
66
	// Assigned validators, and the instant we received their assignment, rounded
	// to the nearest tick.
67
	pub assignments: Vec<(ValidatorIndex, Tick)>,
68
69
70
71
}

/// Metadata regarding approval of a particular candidate within the context of some
/// particular block.
72
73
74
75
76
#[derive(Encode, Decode, Debug, Clone, PartialEq)]
pub struct ApprovalEntry {
	pub tranches: Vec<TrancheEntry>,
	pub backing_group: GroupIndex,
	pub our_assignment: Option<OurAssignment>,
77
	pub our_approval_sig: Option<ValidatorSignature>,
78
	// `n_validators` bits.
79
80
	pub assignments: Bitfield,
	pub approved: bool,
81
82
83
}

/// Metadata regarding approval of a particular candidate.
84
85
86
87
#[derive(Encode, Decode, Debug, Clone, PartialEq)]
pub struct CandidateEntry {
	pub candidate: CandidateReceipt,
	pub session: SessionIndex,
88
89
	// Assignments are based on blocks, so we need to track assignments separately
	// based on the block we are looking at.
90
91
	pub block_assignments: BTreeMap<Hash, ApprovalEntry>,
	pub approvals: Bitfield,
92
93
94
95
}

/// Metadata regarding approval of a particular block, by way of approval of the
/// candidates contained within it.
96
97
98
#[derive(Encode, Decode, Debug, Clone, PartialEq)]
pub struct BlockEntry {
	pub block_hash: Hash,
99
100
	pub block_number: BlockNumber,
	pub parent_hash: Hash,
101
102
103
104
105
	pub session: SessionIndex,
	pub slot: Slot,
	/// Random bytes derived from the VRF submitted within the block by the block
	/// author as a credential and used as input to approval assignment criteria.
	pub relay_vrf_story: [u8; 32],
106
107
	// The candidates included as-of this block and the index of the core they are
	// leaving. Sorted ascending by core index.
108
	pub candidates: Vec<(CoreIndex, CandidateHash)>,
109
110
111
	// A bitfield where the i'th bit corresponds to the i'th candidate in `candidates`.
	// The i'th bit is `true` iff the candidate has been approved in the context of this
	// block. The block can be considered approved if the bitfield has all bits set to `true`.
112
113
	pub approved_bitfield: Bitfield,
	pub children: Vec<Hash>,
114
115
116
}

/// A range from earliest..last block number stored within the DB.
117
118
119
120
121
122
123
124
#[derive(Encode, Decode, Debug, Clone, PartialEq)]
pub struct StoredBlockRange(BlockNumber, BlockNumber);

impl From<crate::Tick> for Tick {
	fn from(tick: crate::Tick) -> Tick {
		Tick(tick)
	}
}
125

126
127
128
129
130
impl From<Tick> for crate::Tick {
	fn from(tick: Tick) -> crate::Tick {
		tick.0
	}
}
131

132
133
134
135
136
137
138
139
140
141
142
143
/// Errors while accessing things from the DB.
#[derive(Debug, derive_more::From, derive_more::Display)]
pub enum Error {
	Io(std::io::Error),
	InvalidDecoding(parity_scale_codec::Error),
}

impl std::error::Error for Error {}

/// Result alias for DB errors.
pub type Result<T> = std::result::Result<T, Error>;

144
145
146
/// Canonicalize some particular block, pruning everything before it and
/// pruning any competing branches at the same height.
pub(crate) fn canonicalize(
147
	store: &dyn KeyValueDB,
148
	config: &Config,
149
150
151
	canon_number: BlockNumber,
	canon_hash: Hash,
)
152
	-> Result<()>
153
{
154
	let range = match load_stored_blocks(store, config)? {
155
156
157
158
159
160
161
162
		None => return Ok(()),
		Some(range) => if range.0 >= canon_number {
			return Ok(())
		} else {
			range
		},
	};

163
	let mut transaction = DBTransaction::new();
164
165
166
167
168
169
170
171
172
173
174

	// Storing all candidates in memory is potentially heavy, but should be fine
	// as long as finality doesn't stall for a long while. We could optimize this
	// by keeping only the metadata about which blocks reference each candidate.
	let mut visited_candidates = HashMap::new();

	// All the block heights we visited but didn't necessarily delete everything from.
	let mut visited_heights = HashMap::new();

	let visit_and_remove_block_entry = |
		block_hash: Hash,
175
		transaction: &mut DBTransaction,
176
		visited_candidates: &mut HashMap<CandidateHash, CandidateEntry>,
177
	| -> Result<Vec<Hash>> {
178
		let block_entry = match load_block_entry(store, config,  &block_hash)? {
179
180
181
182
			None => return Ok(Vec::new()),
			Some(b) => b,
		};

183
		transaction.delete(config.col_data, &block_entry_key(&block_hash)[..]);
184
185
186
187
		for &(_, ref candidate_hash) in &block_entry.candidates {
			let candidate = match visited_candidates.entry(*candidate_hash) {
				Entry::Occupied(e) => e.into_mut(),
				Entry::Vacant(e) => {
188
					e.insert(match load_candidate_entry(store, config, candidate_hash)? {
189
190
191
192
193
194
195
196
197
198
199
200
201
202
						None => continue, // Should not happen except for corrupt DB
						Some(c) => c,
					})
				}
			};

			candidate.block_assignments.remove(&block_hash);
		}

		Ok(block_entry.children)
	};

	// First visit everything before the height.
	for i in range.0..canon_number {
203
204
		let at_height = load_blocks_at_height(store, config, i)?;
		transaction.delete(config.col_data, &blocks_at_height_key(i)[..]);
205
206
207
208

		for b in at_height {
			let _ = visit_and_remove_block_entry(
				b,
209
				&mut transaction,
210
211
212
213
214
215
216
				&mut visited_candidates,
			)?;
		}
	}

	// Then visit everything at the height.
	let pruned_branches = {
217
218
		let at_height = load_blocks_at_height(store, config, canon_number)?;
		transaction.delete(config.col_data, &blocks_at_height_key(canon_number));
219
220
221
222
223
224
225
226

		// Note that while there may be branches descending from blocks at earlier heights,
		// we have already covered them by removing everything at earlier heights.
		let mut pruned_branches = Vec::new();

		for b in at_height {
			let children = visit_and_remove_block_entry(
				b,
227
				&mut transaction,
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
				&mut visited_candidates,
			)?;

			if b != canon_hash {
				pruned_branches.extend(children);
			}
		}

		pruned_branches
	};

	// Follow all children of non-canonicalized blocks.
	{
		let mut frontier: Vec<_> = pruned_branches.into_iter().map(|h| (canon_number + 1, h)).collect();
		while let Some((height, next_child)) = frontier.pop() {
			let children = visit_and_remove_block_entry(
				next_child,
245
				&mut transaction,
246
247
248
249
250
251
252
253
254
				&mut visited_candidates,
			)?;

			// extend the frontier of branches to include the given height.
			frontier.extend(children.into_iter().map(|h| (height + 1, h)));

			// visit the at-height key for this deleted block's height.
			let at_height = match visited_heights.entry(height) {
				Entry::Occupied(e) => e.into_mut(),
255
				Entry::Vacant(e) => e.insert(load_blocks_at_height(store, config, height)?),
256
257
258
259
260
261
262
263
264
			};

			if let Some(i) = at_height.iter().position(|x| x == &next_child) {
				at_height.remove(i);
			}
		}
	}

	// Update all `CandidateEntry`s, deleting all those which now have empty `block_assignments`.
265
266
	for (candidate_hash, candidate) in visited_candidates {
		if candidate.block_assignments.is_empty() {
267
			transaction.delete(config.col_data, &candidate_entry_key(&candidate_hash)[..]);
268
269
		} else {
			transaction.put_vec(
270
				config.col_data,
271
272
273
				&candidate_entry_key(&candidate_hash)[..],
				candidate.encode(),
			);
274
		}
275
	}
276
277

	// Update all blocks-at-height keys, deleting all those which now have empty `block_assignments`.
278
279
	for (h, at) in visited_heights {
		if at.is_empty() {
280
			transaction.delete(config.col_data, &blocks_at_height_key(h)[..]);
281
		} else {
282
			transaction.put_vec(config.col_data, &blocks_at_height_key(h), at.encode());
283
284
		}
	}
285
286
287
288
289
290
291
292

	// due to the fork pruning, this range actually might go too far above where our actual highest block is,
	// if a relatively short fork is canonicalized.
	let new_range = StoredBlockRange(
		canon_number + 1,
		std::cmp::max(range.1, canon_number + 2),
	).encode();

293
	transaction.put_vec(config.col_data, &STORED_BLOCKS_KEY[..], new_range);
294
295

	// Update the values on-disk.
296
	store.write(transaction).map_err(Into::into)
297
298
}

299
fn load_decode<D: Decode>(store: &dyn KeyValueDB, col_data: u32, key: &[u8])
300
	-> Result<Option<D>>
301
{
302
	match store.get(col_data, key)? {
303
304
305
		None => Ok(None),
		Some(raw) => D::decode(&mut &raw[..])
			.map(Some)
306
			.map_err(Into::into),
307
308
309
310
311
312
313
	}
}

/// Information about a new candidate necessary to instantiate the requisite
/// candidate and approval entries.
#[derive(Clone)]
pub(crate) struct NewCandidateInfo {
314
315
316
	pub candidate: CandidateReceipt,
	pub backing_group: GroupIndex,
	pub our_assignment: Option<OurAssignment>,
317
318
319
320
321
322
323
324
325
326
}

/// Record a new block entry.
///
/// This will update the blocks-at-height mapping, the stored block range, if necessary,
/// and add block and candidate entries. It will also add approval entries to existing
/// candidate entries and add this as a child of any block entry corresponding to the
/// parent hash.
///
/// Has no effect if there is already an entry for the block or `candidate_info` returns
327
328
/// `None` for any of the candidates referenced by the block entry. In these cases,
/// no information about new candidates will be referred to by this function.
329
pub(crate) fn add_block_entry(
330
	store: &dyn KeyValueDB,
331
	config: &Config,
332
333
334
	entry: BlockEntry,
	n_validators: usize,
	candidate_info: impl Fn(&CandidateHash) -> Option<NewCandidateInfo>,
335
336
) -> Result<Vec<(CandidateHash, CandidateEntry)>> {
	let mut transaction = DBTransaction::new();
337
	let session = entry.session;
338
339
	let parent_hash = entry.parent_hash;
	let number = entry.block_number;
340

341
342
	// Update the stored block range.
	{
343
		let new_range = match load_stored_blocks(store, config)? {
344
345
346
347
348
349
350
351
			None => Some(StoredBlockRange(number, number + 1)),
			Some(range) => if range.1 <= number {
				Some(StoredBlockRange(range.0, number + 1))
			} else {
				None
			}
		};

352
		new_range.map(|n| transaction.put_vec(config.col_data, &STORED_BLOCKS_KEY[..], n.encode()))
353
354
	};

355
356
	// Update the blocks at height meta key.
	{
357
		let mut blocks_at_height = load_blocks_at_height(store, config, number)?;
358
359
		if blocks_at_height.contains(&entry.block_hash) {
			// seems we already have a block entry for this block. nothing to do here.
360
			return Ok(Vec::new())
361
362
363
		}

		blocks_at_height.push(entry.block_hash);
364
		transaction.put_vec(config.col_data, &blocks_at_height_key(number)[..], blocks_at_height.encode())
365
366
	};

367
368
	let mut candidate_entries = Vec::with_capacity(entry.candidates.len());

369
370
	// read and write all updated entries.
	{
371
372
373
374
375
376
		for &(_, ref candidate_hash) in &entry.candidates {
			let NewCandidateInfo {
				candidate,
				backing_group,
				our_assignment,
			} = match candidate_info(candidate_hash) {
377
				None => return Ok(Vec::new()),
378
379
380
				Some(info) => info,
			};

381
			let mut candidate_entry = load_candidate_entry(store, config, &candidate_hash)?
382
383
384
385
386
387
388
389
390
391
392
393
394
				.unwrap_or_else(move || CandidateEntry {
					candidate,
					session,
					block_assignments: BTreeMap::new(),
					approvals: bitvec::bitvec![BitOrderLsb0, u8; 0; n_validators],
				});

			candidate_entry.block_assignments.insert(
				entry.block_hash,
				ApprovalEntry {
					tranches: Vec::new(),
					backing_group,
					our_assignment,
395
					our_approval_sig: None,
396
397
398
399
400
					assignments: bitvec::bitvec![BitOrderLsb0, u8; 0; n_validators],
					approved: false,
				}
			);

401
			transaction.put_vec(
402
				config.col_data,
403
404
				&candidate_entry_key(&candidate_hash)[..],
				candidate_entry.encode(),
405
			);
406
407

			candidate_entries.push((*candidate_hash, candidate_entry));
408
409
410
		}
	};

411
	// Update the child index for the parent.
412
	load_block_entry(store, config, &parent_hash)?.map(|mut e| {
413
		e.children.push(entry.block_hash);
414
		transaction.put_vec(config.col_data, &block_entry_key(&parent_hash)[..], e.encode())
415
	});
416

417
	// Put the new block entry in.
418
	transaction.put_vec(config.col_data, &block_entry_key(&entry.block_hash)[..], entry.encode());
419

420
	store.write(transaction)?;
421
422
423
	Ok(candidate_entries)
}

424
425
/// Forcibly approve all candidates included at up to the given relay-chain height in the indicated
/// chain.
426
427
///
/// Returns a list of block hashes that were not approved and are now.
428
429
pub fn force_approve(
	store: &dyn KeyValueDB,
430
	db_config: Config,
431
432
	chain_head: Hash,
	up_to: BlockNumber,
433
) -> Result<Vec<Hash>> {
434
435
436
437
438
	enum State {
		WalkTo,
		Approving,
	}

439
440
	let mut approved_hashes = Vec::new();

441
442
443
	let mut cur_hash = chain_head;
	let mut state = State::WalkTo;

444
	let mut tx = Transaction::new(db_config);
445
446
447

	// iterate back to the `up_to` block, and then iterate backwards until all blocks
	// are updated.
448
	while let Some(mut entry) = load_block_entry(store, &db_config, &cur_hash)? {
449
450
451
452
453
454
455
456
457
458

		if entry.block_number <= up_to {
			state = State::Approving;
		}

		cur_hash = entry.parent_hash;

		match state {
			State::WalkTo => {},
			State::Approving => {
459
460
461
462
463
464
465
466
				let is_approved = entry.approved_bitfield.count_ones()
					== entry.approved_bitfield.len();

				if !is_approved {
					entry.approved_bitfield.iter_mut().for_each(|mut b| *b = true);
					approved_hashes.push(entry.block_hash);
					tx.put_block_entry(entry);
				}
467
468
469
470
			}
		}
	}

471
472
	tx.write(store)?;
	Ok(approved_hashes)
473
474
}

475
476
477
478
479
480
481
482
483
484
485
486
/// Return all blocks which have entries in the DB, ascending, by height.
pub(crate) fn load_all_blocks(store: &dyn KeyValueDB, config: &Config) -> Result<Vec<Hash>> {
	let stored_blocks = load_stored_blocks(store, config)?;

	let mut hashes = Vec::new();
	for height in stored_blocks.into_iter().flat_map(|s| s.0..s.1) {
		hashes.extend(load_blocks_at_height(store, config, height)?);
	}

	Ok(hashes)
}

487
488
489
490
491
// An atomic transaction of multiple candidate or block entries.
#[must_use = "Transactions do nothing unless written to a DB"]
pub struct Transaction {
	block_entries: HashMap<Hash, BlockEntry>,
	candidate_entries: HashMap<CandidateHash, CandidateEntry>,
492
	config: Config,
493
494
495
}

impl Transaction {
496
497
498
499
500
501
502
503
	pub(crate) fn new(config: Config) -> Self {
		Transaction {
			block_entries: HashMap::default(),
			candidate_entries: HashMap::default(),
			config,
		}
	}

504
505
506
507
508
509
510
511
512
513
514
515
516
	/// Put a block entry in the transaction, overwriting any other with the
	/// same hash.
	pub(crate) fn put_block_entry(&mut self, entry: BlockEntry) {
		let hash = entry.block_hash;
		let _ = self.block_entries.insert(hash, entry);
	}

	/// Put a candidate entry in the transaction, overwriting any other with the
	/// same hash.
	pub(crate) fn put_candidate_entry(&mut self, hash: CandidateHash, entry: CandidateEntry) {
		let _ = self.candidate_entries.insert(hash, entry);
	}

517
518
519
520
521
	/// Returns true if the transaction contains no actions
	pub(crate) fn is_empty(&self) -> bool {
		self.block_entries.is_empty() && self.candidate_entries.is_empty()
	}

522
	/// Write the contents of the transaction, atomically, to the DB.
523
	pub(crate) fn write(self, db: &dyn KeyValueDB) -> Result<()> {
524
		if self.is_empty() {
525
526
527
			return Ok(())
		}

528
529
530
		let mut db_transaction = DBTransaction::new();

		for (hash, entry) in self.block_entries {
531
532
533
			let k = block_entry_key(&hash);
			let v = entry.encode();

534
			db_transaction.put_vec(self.config.col_data, &k, v);
535
		}
536

537
		for (hash, entry) in self.candidate_entries {
538
539
540
			let k = candidate_entry_key(&hash);
			let v = entry.encode();

541
			db_transaction.put_vec(self.config.col_data, &k, v);
542
		}
543

544
		db.write(db_transaction).map_err(Into::into)
545
	}
546
547
548
}

/// Load the stored-blocks key from the state.
549
fn load_stored_blocks(store: &dyn KeyValueDB, config: &Config)
550
	-> Result<Option<StoredBlockRange>>
551
{
552
	load_decode(store, config.col_data, STORED_BLOCKS_KEY)
553
554
555
}

/// Load a blocks-at-height entry for a given block number.
556
557
558
559
560
pub(crate) fn load_blocks_at_height(
	store: &dyn KeyValueDB,
	config: &Config,
	block_number: BlockNumber,
)
561
	-> Result<Vec<Hash>> {
562
	load_decode(store, config.col_data, &blocks_at_height_key(block_number))
563
564
565
566
		.map(|x| x.unwrap_or_default())
}

/// Load a block entry from the aux store.
567
pub(crate) fn load_block_entry(store: &dyn KeyValueDB, config: &Config, block_hash: &Hash)
568
	-> Result<Option<BlockEntry>>
569
{
570
	load_decode(store, config.col_data, &block_entry_key(block_hash))
571
572
573
}

/// Load a candidate entry from the aux store.
574
575
576
577
578
pub(crate) fn load_candidate_entry(
	store: &dyn KeyValueDB,
	config: &Config,
	candidate_hash: &CandidateHash,
)
579
	-> Result<Option<CandidateEntry>>
580
{
581
	load_decode(store, config.col_data, &candidate_entry_key(candidate_hash))
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
}

/// The key a given block entry is stored under.
fn block_entry_key(block_hash: &Hash) -> [u8; 46] {
	const BLOCK_ENTRY_PREFIX: [u8; 14] = *b"Approvals_blck";

	let mut key = [0u8; 14 + 32];
	key[0..14].copy_from_slice(&BLOCK_ENTRY_PREFIX);
	key[14..][..32].copy_from_slice(block_hash.as_ref());

	key
}

/// The key a given candidate entry is stored under.
fn candidate_entry_key(candidate_hash: &CandidateHash) -> [u8; 46] {
	const CANDIDATE_ENTRY_PREFIX: [u8; 14] = *b"Approvals_cand";

	let mut key = [0u8; 14 + 32];
	key[0..14].copy_from_slice(&CANDIDATE_ENTRY_PREFIX);
	key[14..][..32].copy_from_slice(candidate_hash.0.as_ref());

	key
}

/// The key a set of block hashes corresponding to a block number is stored under.
fn blocks_at_height_key(block_number: BlockNumber) -> [u8; 16] {
	const BLOCKS_AT_HEIGHT_PREFIX: [u8; 12] = *b"Approvals_at";

	let mut key = [0u8; 12 + 4];
	key[0..12].copy_from_slice(&BLOCKS_AT_HEIGHT_PREFIX);
	block_number.using_encoded(|s| key[12..16].copy_from_slice(s));

	key
}