* Commit my changes

* some backing fixes

* indentation

* fix backing tests

* tweak includability rules

* comment

* Update node/core/backing/src/lib.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update node/core/backing/src/lib.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update node/core/backing/src/lib.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Update node/core/backing/src/lib.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

Co-authored-by: Bastian Köcher <git@kchr.de>
Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* DMP: data structures and plumbing

* DMP: Implement DMP logic in the router module

DMP: Integrate DMP parts into the inclusion module

* DMP: Introduce the max size limit for the size of a downward message

* DMP: Runtime API for accessing inbound messages

* OCD

Small clean ups

* DMP: fix the naming of the error

* DMP: add caution about a non-existent recipient

* annoying whitespaces

* update guide

Add `CheckValidationOutputs` runtime api and also change the
candidate-validation stuff

* promote ValidationOutputs to global primitives

i.e. move it from node specific primitives to global v1 primitives. This
will be needed when we share it later in the runtime inclusion module

* refactor acceptance checks in the inclusion module

factor out the common code to share it during the block inclusion and
for the forthcoming CheckValidationOutputs runtime api.

Also note that the acceptance criteria was updated to incorporate checks
that exist now in candidate-validation

* plumb the runtime api outside

* extract validation_data from ValidationOutputs

* use runtime-api to check validation outputs

apart from that refactor, update docs and tidy a bit

* Update the maxium code size

This is to fix a test that performs an upgrade.

* Fix keystore types

* Use SyncCryptoStorePtr

* Borrow keystore

* Fix unused imports

* Fix polkadot service

* Fix bitfield-distribution tests

* Fix indentation

* Fix backing tests

* Fix tests

* Fix provisioner tests

* Removed SyncCryptoStorePtr

* Fix services

* Address PR feedback

* Address PR feedback - 2

* Update CryptoStorePtr imports to be from sp_keystore

* Typo

* Fix CryptoStore import

* Document the reason behind using filesystem keystore

* Remove VALIDATORS

* Fix duplicate dependency

* Mark sp-keystore as optional

* Fix availability distribution

* Fix call to sign_with

* Fix keystore usage

* Remove tokio and fix parachains Cargo config

* Typos

* Fix keystore dereferencing

* Fix CryptoStore import

* Fix provisioner

* Fix node backing

* Update services

* Cleanup dependencies

* Use sync_keystore

* Fix node service

* Fix node service - 2

* Fix node service - 3

* Rename CryptoStorePtr to SyncCryptoStorePtr

* "Update Substrate"

* Apply suggestions from code review

* Update node/core/backing/Cargo.toml

* Update primitives/src/v0.rs

Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* Fix wasm build

* Update Cargo.lock

Co-authored-by: parity-processbot <>
Co-authored-by: Bastian Köcher <bkchr@users.noreply.github.com>

* extract collator assignment from cores

* check required collator

* test and fix checks

* update primitives

* correct parent_head field

* make hrmp field pub

* refactor validation data: runtime

* refactor validation data: messages

* add arguments to full_validation_data runtime API

* port runtime API

* mostly port over candidate validation

* remove some parameters from ValidationParams

* guide: update candidate validation

* update candidate outputs

* update ValidationOutputs in primitives

* port over candidate validation

* add a new test for no-transient behavior

* update util runtime API wrappers

* candidate backing

* fix missing imports

* change some fields of validation data around

* runtime API impl

* update candidate validation

* fix backing tests

* grumbles from review

* fix av-store tests

* fix some more crates

* fix provisioner tests

* fix availability distribution tests

* port collation-generation to new validation data

* fix overseer tests

* Update roadmap/implementers-guide/src/node/utility/candidate-validation.md

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

Co-authored-by: Peter Goodspeed-Niklaus <coriolinus@users.noreply.github.com>

* service-new: cosmetic changes

* overseer: draft of prometheus metrics

* metrics: update active_leaves metrics

* metrics: extract into functions

* metrics: resolve XXX

* metrics: it's ugly, but it works

* Bump Substrate

* metrics: move a bunch of code around

* Bumb substrate again

* metrics: fix a warning

* fix a warning in runtime

* metrics: statements signed

* metrics: statements impl RegisterMetrics

* metrics: refactor Metrics trait

* metrics: add Metrics assoc type to JobTrait

* metrics: move Metrics trait to util

* metrics: fix overseer

* metrics: fix backing

* metrics: fix candidate validation

* metrics: derive Default

* metrics: docs

* metrics: add stubs for other subsystems

* metrics: add more stubs and fix compilation

* metrics: fix doctest

* metrics: move to subsystem

* metrics: fix candidate validation

* metrics: bitfield signing

* metrics: av store

* metrics: chain API

* metrics: runtime API

* metrics: stub for avad

* metrics: candidates seconded

* metrics: ok I gave up

* metrics: provisioner

* metrics: remove a clone by requiring Metrics: Sync

* metrics: YAGNI

* metrics: remove another TODO

* metrics: for later

* metrics: add parachain_ prefix

* metrics: s/signed_statement/signed_statements

* utils: add a comment for job metrics

* metrics: address review comments

* metrics: oops

* metrics: make sure to save files before commit 😅



* use _total suffix for requests metrics

Co-authored-by: Max Inden <mail@max-inden.de>

* metrics: add tests for overseer

* update Cargo.lock

* overseer: add a test for CollationGeneration

* collation-generation: impl metrics

* collation-generation: use kebab-case for name

* collation-generation: add a constructor

Co-authored-by: Gav Wood <gavin@parity.io>
Co-authored-by: Ashley Ruglys <ashley.ruglys@gmail.com>
Co-authored-by: Max Inden <mail@max-inden.de>

* break out subsystem-util and subsystem-test-helpers into individual crates

* cause all packages to check successfully

* sketch out provisioner basics

* handle provisionable data

* stub out select_inherent_data

* split runtime APIs into sub-chapters to improve linkability

* explain SignedAvailabilityBitfield semantics

* add internal link to further documentation

* some more work figuring out how the provisioner can do its thing

* fix broken link

* don't import enum variants where it's one layer deep

* make request_availability_cores a free fn in util

* document more precisely what should happen on block production

* finish first-draft implementation of provisioner

* start working on the full and proper backed candidate selection rule

* Pass number of block under construction via RequestInherentData

* Revert "Pass number of block under construction via RequestInherentData"

This reverts commit 850fe62c.

That initially looked like the better approach--it spent the time
budget for fetching the block number in the proposer, instead of
the provisioner, and that felt more appropriate--but it turns out
not to be obvious how to get the block number of the block under
construction from within the proposer. The Chain API may be less
ideal, but it should be easier to implement.

* wip: get the block under production from the Chain API

* add ChainApiMessage to AllMessages

* don't break the run loop if a provisionable data channel closes

* clone only those backed candidates which are coherent

* propagate chain_api subsystem through various locations

* add delegated_subsystem! macro to ease delegating subsystems

Unfortunately, it doesn't work right:

```
error[E0446]: private type `CandidateBackingJob` in public interface
   --> node/core/backing/src/lib.rs:775:1
    |
86  | struct CandidateBackingJob {
    | - `CandidateBackingJob` declared as private
...
775 | delegated_subsystem!(CandidateBackingJob as CandidateBackingSubsystem);
    | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ can't leak private type
```

I'm not sure precisely what's going wrong, here; I suspect the problem is
the use of `$job as JobTrait>::RunArgs` and `::ToJob`; the failure would be
that it's not reifying the types to verify that the actual types are public,
but instead referring to them via `CandidateBackingJob`, which is in fact private;
that privacy is the point.

Going to see if I can generic my way out of this, but we may be headed for a
quick revert here.

* fix delegated_subsystem

The invocation is a bit more verbose than I'd prefer, but it's also
more explicit about what types need to be public. I'll take it as a win.

* add provisioning subsystem; reduce public interface of provisioner

* deny missing docs in provisioner

* refactor core selection per code review suggestion

This is twice as much code when measured by line, but IMO it is
in fact somewhat clearer to read, so overall a win.

Also adds an improved rule for selecting availability bitfields,
which (unlike the previous implementation) guarantees that the
appropriate postconditions hold there.

* fix bad merge double-declaration

* update guide with (hopefully) complete provisioner candidate selection procedure

* clarify candidate selection algorithm

* Revert "clarify candidate selection algorithm"

This reverts commit c68a02ac.

* clarify candidate selection algorithm

* update provisioner to implement candidate selection per the guide

* add test that no more than one bitfield is selected per validator

* add test that each selected bitfield corresponds to an occupied core

* add test that more set bits win conflicts

* add macro for specializing runtime requests; specailize all runtime requests

* add tests harness for select_candidates tests

* add first real select_candidates test, fix test_harness

* add mock overseer and test that success is possible

* add test that the candidate selection algorithm picks the right ones

* make candidate selection test somewhat more stringent

* Sort out validation errors

* Typo

* Fixed wasm/android build

* Fixed bad merge

* polkadot-subsystem: update runtime API message types

* update all networking subsystems to use fallible runtime APIs

* fix bitfield-signing and make it use new runtime APIs

* port candidate-backing to handle runtime API errors and new types

* remove old runtime API messages

* remove unused imports

* fix grumbles

* fix backing tests

* Initial commit

* WIP

* Make atomic transactions

* Remove pruning code

* Fix build and add a Nop to bridge

* Fixes from review

* Move config struct around for clarity

* Rename constructor and warn on missing docs

* Fix a test and rename a message

* Fix some more reviews

* Obviously failed to rebase cleanly

* add ActiveLeavesUpdate, remove StartWork, StopWork

* replace StartWork, StopWork in subsystem crate tests

* mechanically update OverseerSignal in other modules

* convert overseer to take advantage of new multi-hash update abilities

Note: this does not yet convert the tests; some of the tests now freeze:

test tests::overseer_start_stop_works ... test tests::overseer_start_stop_works has been running for over 60 seconds
test tests::overseer_finalize_works ... test tests::overseer_finalize_works has been running for over 60 seconds

* fix broken overseer tests

* manually impl PartialEq for ActiveLeavesUpdate, rm trait Equivalent

This cleans up the code a bit and makes it easier in the future to
do the right thing when comparing ALUs.

* use target in all network bridge logging

* reduce spamming of  and

* Companion for #6726

* Spaces

* 'Update substrate'

Co-authored-by: parity-processbot <>

* rename GlobalValidationSchedule to GlobalValidationData

* guide: update candidate descriptor to contain validation data hash

* guide: add note in inclusion module about checking validation data hash

* primitives: update CandidateDescriptor to contain new hash

* fix payload computation

* add helpers for computing validation data to runtime modules

* guide: note routines

* inclusion: check validation data hash and fix local_validation_data bug

* add a case to candidate_checks and improve that test substantially

* bump versions

* address review comments

* add a test for including code upgrade

* bump kusama version

* bump westend & polkadot versions

* get conclude signal working properly; don't allocate a vector

* wip: add test suite / example / explanation for using utility subsystem

Unfortunately, the test fails right now for reasons which seem
very odd. Just have to keep poking at it.

* explicitly import everything

* fix subsystem-util test

The root problem here was two-fold:

- there was a circular dependency from subsystem -> test-helpers/subsystem ->
  subsystem
- cfg(test) doesn't propagate between crates

The solution: move the subsystem test helpers into a sub-module
within subsystem. Publicly export them from the previous location
so no other code breaks.

Doing this has an additional benefit: it ensures that no production
code can ever accidentally use the subsystem helpers, as they are compile-
gated on cfg(test).

* fully commit to moving test helpers into a subsystem module

* add some more tests

* get rid of log tests in favor of real error forwarding

It's not obvious whether we'll ever really want to chase down
these errors outside a testing context, but having the capability
won't hurt.

* fix issue which caused test to hang on osx

* only require that job errors are PartialEq when testing

also fix polkadot-node-core-backing tests

* get rid of any notion of partialeq

* rethink testing

Combine tests of starting and stopping job: leaving a test executor
with a job running was pretty clearly the cause of the sometimes-hang.

Also, add a timeout so tests _can't_ hang anymore; they just fail
after a while.

* rename fwd_errors -> forward_errors

* warn on error propagation failure

* fix unused import leftover from merge

* derive eq for subsystemerror

* Use SpawnNamed instead of Spawn in Overseer

* reexport SpawnNamed and fix doc tests

* Fix deps

* Add subsystem-util crate.

Start by moving the JobCanceler here.

* copy utility functions for requesting runtime data; generalize

* convert subsystem-util from crate to module in subsystem

The point of making a sub-crate is to ensure that only the necessary
parts of a program get compiled; if a dependent package needed only
subsystem-util, and not subsystem, then subsystem wouldn't need to
be compiled.

However, that will never happen: subsystem-util depends on
subsystem::messages, so subsystem will always be compiled.

Therefore, it makes more sense to add it as a module in the existing
crate than as a new and distinct crate.

* make runtime request sender type generic

* candidate backing subsystem uses util for api requests

* add struct Validator representing the local validator

This struct can be constructed when the local node is a validator;
the constructor fails otherwise. It stores a bit of local data, and
provides some utility methods.

* add alternate constructor for better efficiency

* refactor candidate backing to use utility methods

* fix test breakage caused by reordering tests

* restore test which accidentally got deleted during merge

* start extracting jobs management into helper traits + structs

* use util::{JobHandle, Jobs} in CandidateBackingSubsystem

* implement generic job-manager subsystem impl

This means that the work of implementing a subsystem boils down
to implementing the job, and then writing an appropriate
type definition, i.e.

pub type CandidateBackingSubsystem<Spawner, Context> =
	util::JobManager<Spawner, Context, CandidateBackingJob>;

* add hash-extraction helper to messages

* fix errors caused by improper rebase

* doc improvement

* simplify conversion from overseer communication to job message

* document fn hash for all messages

* rename fn hash() -> fn relay_parent

* gracefully shut down running futures on Conclude

* ensure we're validating with the proper validator index

* rename: handle_unhashed_msg -> handle_orphan_msg

* impl Stream for Jobs<Spawner, Job>

This turns out to be relatively complicated and requires some
unsafe code, so we'll want either detailed review, or to choose
to revert this commit.

* add missing documentation for public items

* use pin-project to eliminate unsafe code from this codebase

* rename SenderMessage -> FromJob

* reenvision the subsystem requests as an extension trait

This works within `util.rs`, but fails in `core/backing/src/lib.rs`,
because we don't actually create the struct soon enough. Continuing
down this path would imply substantial rewriting.

* Revert "reenvision the subsystem requests as an extension trait"

This reverts commit a5639e36.

The fact is, the new API is more complicated to no real benefit.

* apply suggested futuresunordered join_all impl

* CandidateValidationMessage variants have no top-level relay parents

* rename handle_orphan_msg -> handle_unanchored_msg

* make most node-core-backing types private

Now the only public types exposed in that module are
CandidateBackingSubsystem and ToJob. While ideally we could reduce
the public interface to only the former type, that doesn't work
because ToJob appears in the public interface of CandidateBackingSubsystem.

This also involves changing the definition of CandidateBackingSubsystem;
it is no longer a typedef, but a struct wrapping the job manager.

* create a v1 primitives module

* Improve guide on availability types

* punctuate

* new parachains runtime uses new primitives

* tests of new runtime now use new primitives

* add ErasureChunk to guide

* export erasure chunk from v1 primitives

* subsystem crate uses v1 primitives

* node-primitives uses new v1 primitives

* port overseer to new primitives

* new-proposer uses v1 primitives (no ParachainHost anymore)

* fix no-std compilation for primitives

* service-new uses v1 primitives

* network-bridge uses new primitives

* statement distribution uses v1 primitives

* PoV distribution uses v1 primitives; add PoV::hash fn

* move parachain to v0

* remove inclusion_inherent module and place into v1

* remove everything from primitives crate root

* remove some unused old types from v0 primitives

* point everything else at primitives::v0

* squanch some warns up

* add RuntimeDebug import to no-std as well

* port over statement-table and validation

* fix final errors in validation and node-primitives

* add dummy Ord impl to committed candidate receipt

* guide: update CandidateValidationMessage

* add primitive for validationoutputs

* expand CandidateValidationMessage further

* bikeshed

* add some impls to omitted-validation-data and available-data

* expand CandidateValidationMessage

* make erasure-coding generic over v1/v0

* update usages of erasure-coding

* implement commitments.hash()

* use Arc<Pov> for CandidateValidation

* improve new erasure-coding method names

* fix up candidate backing

* update docs a bit

* fix most tests and add short-circuiting to make_pov_available

* fix remainder of candidate backing tests

* squanching warns

* squanch it up

* some fallout

* overseer fallout

* free from polkadot-test-service hell

* Updates guide for CandidateBacking

* Move assignment types to primitives

* Initial implementation.

* More functionality

* use assert_matches

* Changes to report misbehaviors

* Some fixes after a review

* Remove a blank line

* Update guide and some types

* Adds run_job function

* Some comments and refactorings

* Fix review

* Remove warnings

* Use summary in kicking off validation

* Parallelize requests

* Validation provides local and global validation params

* Test issued validity tracking

* Nits from review