Slotted dependencies are not resolved correctly

[tomchy]

Test scenario

Considering the following set of images in the Direct XIP mode:

Img0:        Img1
+----+      +----+
| v2 |      | v3 | <- s0
+----+      +----+
| v1 |      | v1 | <- s1
+----+      +----+

With the following set of dependencies:

• Img0, s0 depends on Img1, s0, v2
• Img1, s0 depends on img0, s0, v3
• Img0, s1 depends on Img1, s1, v1
• Img1, s1 depends on Img0, s1, v1

The current algorithm will invalidate all slots and refuse to boot, despite the fact that the pair (Img0, s1; Img1, s1) is valid.

The current algorithm

The algorithm iterates over images until all dependencies of active slots are met or all slots of an image are marked as unavailable.
The first slotted dependency is satisfied, so the logic will mark the Img1, s0 as active.

Img0:        Img1:
+----+      +----+
| v2 |-OK>  | v3 |
+----+      +----+
| v1 |      | v1 |
+----+      +----+

To make sure that no other dependency resolution will select a different slot of Img1 as active, the Img1, s1 is invalidated (marked as unavailable).

Img0:        Img1:
+----+      +----+
| v2 |-OK>  | v3 |
+----+      +----+
| v1 |      | xx |
+----+      +----+

Afterwards dependencies of the Img1, s0 are checked.

Img0:        Img1:
+----+      +----+
| v2 | <NOK-| v3 |
+----+      +----+
| v1 |      | xx |
+----+      +----+

Unfortunately - they are not met, so the Img1, s0 is invalidated (marked as unavailable).

Img0:        Img1:
+----+      +----+
| v2 | <NOK-| xx |
+----+      +----+
| v1 |      | xx |
+----+      +----+

At this stage the loop over images resets, but since all slots of Img1 are invalidated, the algorithm ends with a conclusion that there are no good candidates to boot the system.

Possible solutions

The main issue in the scenario above is the fact that if a slotted dependency is introduced, it is no longer true that a slot with the highest version number is checked first. This assumption allowed to optimize the dependency resolution algorithm from exponential to polynomial time complexity (if a slot with version x has the highest possible version and all of it's dependencies are met, then there is no other dependency in other slots that would be satisfied by an inactive slot and not satisfied with the active one, thus each image may be analyzed once).

Currently I see the following options:

• Drop the slotted dependencies (loader: Remove the possibility to specify dep slot #2486)
• Add a "practical" assumption on the slotted dependency usage. If we assume that slotted dependencies are used in Direct XIP only, than it is highly probable that they will describe all images from the same upgrade package, so the dependency may be interpreted as a request for equality not a weak request for a minimal version of the other image. Moreover, it is highly probable that if there is a dependency (Img_a, s_x -> Img_b, s_y) there is also a dependency (Img_b, s_y -> Img_a, s_x). Under those assumptions, the image with a lower index will resole all other incoming dependencies just by checking it's own dependencies, bringing back the correctness of the statement that if an image's dependencies are checked, there is nothing in the future checks that will be able to invalidate it (loader: Enforce version equality in slot deps #2488).
• Introduce a "brute force" solution for dependency resolution if slotted dependencies are enabled (loader: Brute force solution for dependencies #2487). Although the "brute force" sounds terribly, considering that the dependency checks are not involving cryptographic operations and that the number of available slots is typically <= 6, the solution will be found within <= 64 iterations which might be a good tradeoff between time and code complexity.
• Keep trying to find a polynomial time algorithm for the slotted dependency resolution. I was able to simply a problem into a non-versioned directed dependency graph, but still have not found a valid solution.

[tomchy]

Decided to fix the issue by removing the slotted dependency feature.