Rework dependency cycle detection #10360
Conversation
1660260 to
cb80b1d
Compare
cb80b1d to
86ba250
Compare
|
Regarding the choice of using Boost.Signals2 for |
86ba250 to
83792af
Compare
c9cdc3c to
6f9628f
Compare
|
With the commit just pushed, everything from #10360 (review) should be addressed. I'm leaving this in draft state until I've redone and updated the tests in the PR description, but before that, I wan't the Actions to run at least so far that I've good confidence that they'll all succeed. Feel free to already have a look if you'd like. Regarding #10360 (comment) (printing only the cycle itself if the path that found is ρ-shaped): I'll probably leave it out of the PR for the moment in order to unblock #10290 faster and this is not making it worse than the status-quo. Conceptually, adding it is trivial: only show dependencies after an edge with |
6f9628f to
fce4775
Compare
Allows to hook into the config loading process just before OnAllConfigLoaded() is called on a bunch of individual config objects. Allows doing some operations more efficiently at once for all objects. Intended use: when adding a number of dependencies, it has to be checked whether this uses any cycles. This can be done more efficiently if all dependencies are checked at once. So far, this is with a case-distinction for initially loaded files in DaemonUtility::LoadConfigFiles() and for dependencies created by runtime updates in Dependency::OnAllConfigLoaded(). The mechanism added by this commit allows to unify the handling of both cases (done in a following commit).
Boost only implements it iself starting from version 1.74, but a specialization of std::hash<> can be added trivially to allow the use of std::unordered_set<boost::intrusive_ptr<T>> and std::unordered_map<boost::intrusive_ptr<K>, V>. Being unable to use such types already came up a few types in the past, often resulting in the use of raw pointer instead which always involves an additional "is this safe?"/"could the object go out of scope?" discussion. This commit simply solves this for the future by simply allowing the use of intrusive_ptr in unordered containers.
This commit groups a bunch of structs and static functions inside dependency.cpp into a new DependencyCycleChecker helper class. In the process, the implementation was changed a bit, the behavior should be unchanged except for a more user-friendly error message in the exception.
This commit removes a distinction in how dependency objects are checked for cycles in the resulting graph depending on whether they are part of the initially loaded configuration during process startup or as part of a runtime update. The DependencyCycleChecker helper class is extended with a mechanism that allows additional dependencies to be considered during the cycle search. This allows using it to check for cycles before actually registering the dependencies with the checkables. The aforementioned case-distinction for initial/runtime-update config is removed by making use of the newly added BeforeOnAllConfigLoaded signal to perform the cycle check at once for each batch of dependencies inside ConfigItem::CommitNewItems() for both cases now. During the initial config loading, there can be multiple batches of dependencies as objects from apply rules are created separately, so parts of the dependency graph might be visited multiple times now, however that is limited to a minimum as only parts of the graph that are reachable from the newly added dependencies are searched.
fce4775 to
8e7e687
Compare
|
@Al2Klimov As I requested a review a few days ago: did you already take a look at this or still want to? Otherwise, I'd 8000 merge this after the CI passed. |
| * @param func Functor accepting T::Ptr as an argument to be called for each object | ||
| */ | ||
| template<typename T, typename F> | ||
| void ForEachObject(F func) const |
There was a problem hiding this comment.
Glad to see that the compiler complains, and not dyncasts, if T doesn't match F.
|
|
||
| // Resolve parent/child names to Checkable::Ptr and temporarily add the edges to the checker. | ||
| // The dependencies are later registered to the checkables by Dependency::OnAllConfigLoaded(). | ||
| items.ForEachObject<Dependency>([&checker](Dependency::Ptr dependency) { |
There was a problem hiding this comment.
| items.ForEachObject<Dependency>([&checker](Dependency::Ptr dependency) { | |
| items.ForEachObject<Dependency>([&checker](Ptr dependency) { |
There was a problem hiding this comment.
Possible to do, but doesn't help with readability in my opinion.
| // It's sufficient to search for cycles starting from newly added dependencies only: if a newly added dependency is | ||
| // part of a cycle, that cycle is reachable from both the child and the parent of that dependency. The cycle search | ||
| // is started from the parent as a slight optimization as that will traverse fewer edges if there is no cycle. | ||
| items.ForEachObject<Dependency>([&checker](const Dependency::Ptr& dependency) { |
There was a problem hiding this comment.
| items.ForEachObject<Dependency>([&checker](const Dependency::Ptr& dependency) { | |
| items.ForEachObject<Dependency>([&checker](const Ptr& dependency) { |
With #10290, registering a dependency to a checkable will trigger further events inside Icinga DB, so fully registering it, then checking for cycles and unregistering it if there's actually a cycle isn't really the best idea. This PR provides changes that allow to check for cycles before actually fully registering the dependencies and gives the dependency cycle check code a general makeover. The changes include:
DependencyCycleCheckerhelper class for a bit more structure.DependencyCycleChecker::AddExtraDependency()).m_AssertNoCyclesForIndividualDeps):CommitNewItems()already adds config objects in batches. The cycle check is now performed for each batch in one go using a newly introducedBeforeOnAllConfigLoadedsignal.The commit messages and code comments contain more details, so please check there for all the details.
In general, expect for the different error messages, there should be no changes in user-facing behavior.
Tests
The following config has no cycles as-is, uncommenting either of the additional blocks introduces a cycle:
Additionally, the dependency creating the cycle can also be added as a runtime update:
Current master branch (5c651e4)
Without cycle
Config validates, daemon starts successfully.
Cycle with object
Cycle with apply
Note: I tested this by including the config in my test cluster, so this shows an unrelated host test-sat-a-231 that's also present there. It's part of the path that found the cycle but not actually part of the cycle itself (the path shown has a shape like the Greek letter ρ). The test below doesn't show that extra host, but that's only because the starting nodes for the search are picked differently, there was no change in the code that would prevent such a path from appearing.
Self-loop
Cycle with runtime update
{ "results": [ { "code": 500, "errors": [ "Error: Dependency cycle:\nHost 'cyclic-host-b'\n-> Dependency 'cyclic-host-b!dep-a'\n-> Service 'cyclic-host-a!example-service'\n-> Host 'cyclic-host-a' (implicit)\n-> Dependency 'cyclic-host-a!dep-b-runtime'\n-> Host 'cyclic-host-b'\n" ], "status": "Object could not be created." } ] }Pretty error message from the JSON:
This PR (fce4775)
Without cycle
Config validates, daemon starts successfully.
Cycle with object
Cycle with apply
Self-loop
As already noted in the old "cycle with apply" case, additional edges before the actual cycle may be shown both with and without this PR. The checkables are just picked in a different order, so the situations where this happens changed.
Cycle with runtime update
{ "results": [ { "code": 500, "errors": [ "Error: Dependency cycle:\n\t- Host \"cyclic-host-b\" depends on Service \"cyclic-host-a!example-service\" (Dependency \"dep-a\" in /etc/icinga2/zones.d/master/dependencies.conf: 14:1-14:25)\n\t- Service \"cyclic-host-a!example-service\" depends on Host \"cyclic-host-a\" (implicit)\n\t- Host \"cyclic-host-a\" depends on Host \"cyclic-host-b\" (Dependency \"dep-b-runtime\" in /var/lib/icinga2/api/packages/_api/77e78991-06d4-4589-aa0c-ee60e1d7724e/conf.d/dependencies/cyclic-host-a!dep-b-runtime.conf: 1:0-1:32)\n" ], "status": "Object could not be created." } ] }Pretty error message from the JSON: