Implement component dependency sorting
Open, NormalPublic

Description

Right now VyOS uses hardcoded priorities specified in command definitions to execute config scripts in the correct order (e.g. to avoid trying to configure firewall before interfaces it will be assigned to are configured).
This model is problematic on multiple levels. First, it makes parallel commit theoretically impossible to implement. Second, it means every contributor must be aware of the complete list of priorities and must find a place in the priority list for their component. Also, unless we leave pretty huge gaps between priorities, the possibility that we run out of numbers and have to do a lot of renumbering to put a new component in the right place. Last but definitely not list, in this model it's very hard to find out what really depends on what, you need to read the source, and the source may not make it very explicit either.

Explicit dependencies will solve all these issues. I think initially we should not worry about parallelizing the commit, and even if/when we introduce it, there still should be an option to execute everything sequentially, e.g. to debug race conditions and other bugs related to concurrency and parallelism (if running it sequentially makes the problem go away, you know where to look).

For sequential commit, we need to sort the components by their dependencies, thus creating a flat list of component names in order of execution. E.g. [(firewall, [interfaces]), (bgp, [interfaces, route-filters]), (interfaces, []), (route-filters, [])] should turn into [interfaces, route-filters, firewall, bgp] (or equivalent).

An idea how it may work:

  1. Make an empty list XS
  2. Take the list of all components with their dependencies (YS), identify components that have no dependencies and move them to XS
  3. Repeatedly remove components from the list YS and append them to XS if and only if they depend only on components already in XS
  4. If list YS is empty after an iteration, we are done. If it's not empty, but XS is the same as before the iteration, it means either a component depends on something that doesn't exist, or there's a dependency cycle, either way we cannot proceed.

Details

Difficulty level
Easy (less than an hour)