Many of the functions in the solver that operated on the edges were very
large which obscured their usage and the overall flow of the scheduler.
This change refactors those functions into separate smaller functions to
make it easier to follow the overall flow of the scheduler.
Signed-off-by: Jonathan A. Sternberg <jonathan.sternberg@docker.com>
Move scheduler debug statements to their own functions and in their own
file so that scheduler debug statements don't make the scheduler logic
more complex to follow. Some of the scheduler logs can be quite long and
can make it difficult to follow the code logic. This changes these log
statements to `debugSchedulerXXX` where `XXX` is the message that would
be printed.
Signed-off-by: Jonathan A. Sternberg <jonathan.sternberg@docker.com>
This updates the pipe library to use generics for the request payload
and the status value. This allows the solver to put in explicit types
rather than rely on type casting from interfaces which helps with type
safety and understandability.
The status value used by the solver uses the `any` type instead of an
explicit type because the `unpark` method takes a generic list of pipes
and the different pipes have different result types. We can likely
change this in the future or create a discriminated union for the
types that can be used in this package. That is left for future work
because at least the request payload is typed now.
Signed-off-by: Jonathan A. Sternberg <jonathan.sternberg@docker.com>
This adds new environment variables for allowing
debugging scheduler for only specific steps. This
is useful because the scheduler debugging is quite
verbose so if you run it on production builds it can
generate lots of data that is hard to analyze. Old
behavior is unchanged.
Signed-off-by: Tonis Tiigi <tonistiigi@gmail.com>
"Merged edges" is an optimization in the solve graph where two different active LLB edges can be combined into one after cache key computation finds that they generated equivalent cache chain.
In that case, one edge is released and is set to point to another. The reference count for the second one is increased.
An issue was discovered where an edge that was already pointing to another edge became a target to the third one. The current implementation did not handle the case where an edge that already had a different target itself became a target edge as well. This resulted in an inconsistent graph state where edges that were thought to be released could get scheduled again.
Instead of setting the same edge value to two different maps, the new logic is to chain the edges into a linked list that should handle multiple levels of targets. This slightly increases the number of lookups, but "merged edges" case is very rare anyway, and a couple of extra pointer dereferences do not affect build speed.
Signed-off-by: Tonis Tiigi <tonistiigi@gmail.com>
In some cases edges that depend on each other
can have identical cache keys. This happens for
example when empty layers are optimized out by
the differ between identical commands. We need to
detect this case and avoid merge.
Signed-off-by: Tonis Tiigi <tonistiigi@gmail.com>
Preprocess should not be taken into account when calculating
cache-slow state. But it should be used to detect if dep is complete
so preprocess runs before parent's exec function.
Signed-off-by: Tonis Tiigi <tonistiigi@gmail.com>
Detect the cases where open input keys are not possible even
when computed keys are calculated to skip to cache lookup early.
Signed-off-by: Tonis Tiigi <tonistiigi@gmail.com>
