tyler.durden/icinga2
1
0
Fork 0
mirror of https://github.com/Icinga/icinga2.git synced 2025-08-20 09:08:16 +02:00
Code Issues Packages Projects Releases Wiki Activity
icinga2/lib/icinga
History
Julian Brost 63e9ef58ba Prevent worst-case exponential complexity in dependency evaluation 
So far, calling Checkable::IsReachable() traversed all possible paths to it's
parents. In case a parent is reachable via multiple paths, all it's parents
were evaluated multiple times, result in a worst-case exponential complexity.

With this commit, the implementation keeps track of which checkables were
already visited and uses the already-computed reachability instead of repeating
the computation, ensuring a worst-case linear runtime within the graph size.
2025-08-04 10:42:20 +02:00
..
apiactions.cpp
Merge pull request #9924 from ymartin-ovh/pr-9916
2025-06-06 15:15:51 +02:00
apiactions.hpp
Refactor GetSingleObjectByNameUsingPermissions
2020-07-07 15:45:58 +02:00
apievents.cpp
ApiEvents: Implement new API event streams response
2021-01-11 14:59:48 +01:00
apievents.hpp
ApiEvents: Implement new API event streams response
2021-01-11 14:59:48 +01:00
checkable-check.cpp
Address comments from review
2025-05-29 09:16:46 +02:00
checkable-comment.cpp
Checkable#RemoveAckComments(): add optional comment entry time filter
2023-03-03 15:48:11 +01:00
checkable-dependency.cpp
Move code involved in recursive dependency evaluation to helper class
2025-08-04 10:42:20 +02:00
checkable-downtime.cpp
Remove unused Checkable#RemoveAllDowntimes()
2024-05-21 14:28:39 +02:00
checkable-event.cpp
CONTEXT: use << everywhere to unify usages
2022-11-30 11:06:51 +01:00
checkable-flapping.cpp
Flapping: Allow to ignore states in flapping calculation
2021-01-20 11:09:03 +01:00
checkable-notification.cpp
Use GetParents() in FireSppressedNotifications()
2025-03-19 16:28:00 +01:00
checkable.cpp
Merge pull request #10457 from Icinga/remove-superfluous-dsl-functions
2025-06-10 16:33:37 +02:00
checkable.hpp
Move code involved in recursive dependency evaluation to helper class
2025-08-04 10:42:20 +02:00
checkable.ti
Checkable: improve state notifications after suppression ends
2022-03-03 14:25:23 +01:00
checkcommand.cpp
Require to pass WaitGroup::Ptr to several methods
2025-05-23 14:53:58 +02:00
checkcommand.hpp
Require to pass WaitGroup::Ptr to several methods
2025-05-23 14:53:58 +02:00
checkcommand.ti
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
checkresult.cpp
Initialize namespaces without using overrideFrozen
2023-01-19 09:53:36 +01:00
checkresult.hpp
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
checkresult.ti
Make ProcessResult#ExitStatus and CheckResult#exit_status 64-bit ints
2024-04-23 17:45:31 +02:00
cib.cpp
Simplify NamespaceValue class hierarchy to one struct without member functions
2023-01-19 17:55:11 +01:00
cib.hpp
Use std::mutex, not boost::mutex
2021-02-03 09:54:57 +01:00
clusterevents-check.cpp
Require to pass WaitGroup::Ptr to several methods
2025-05-23 14:53:58 +02:00
clusterevents.cpp
Merge pull request #10397 from Icinga/activation-priority-10179
2025-05-28 12:30:40 +02:00
clusterevents.hpp
Notification#BeginExecuteNotification(): on recovery clear last_notified_state_per_user
2023-12-13 13:21:22 +01:00
CMakeLists.txt
Move code involved in recursive dependency evaluation to helper class
2025-08-04 10:42:20 +02:00
command.cpp
Remove redundant "Validation failed" prefix from ValidationError exceptions
2024-10-23 13:06:12 +02:00
command.hpp
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
command.ti
Introduce Command#arguments[].sep
2022-05-11 17:50:12 +02:00
comment.cpp
Merge pull request #9924 from ymartin-ovh/pr-9916
2025-06-06 15:15:51 +02:00
comment.hpp
AddComment: return Comment::Ptr instead of String containing the name
2025-06-03 17:00:07 +02:00
comment.ti
Mark MakeName and ParseName virtual methods as override
2025-05-19 11:33:22 +02:00
compatutility.cpp
Fix compiler warnings by (copy-)constructing loop variables explicitly
2025-04-22 13:55:49 +02:00
compatutility.hpp
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
customvarobject.cpp
Fix file endings
2023-05-17 18:05:13 +02:00
customvarobject.hpp
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
customvarobject.ti
Icinga DB: Make sure object relationships are handled correctly
2021-11-12 13:34:57 +01:00
dependency-apply.cpp
CONTEXT: use << everywhere to unify usages
2022-11-30 11:06:51 +01:00
dependency-group.cpp
Move code involved in recursive dependency evaluation to helper class
2025-08-04 10:42:20 +02:00
dependency-state.cpp
Prevent worst-case exponential complexity in dependency evaluation
2025-08-04 10:42:20 +02:00
dependency.cpp
DependencyGroup: don't change the keys of m_Members after construction
2025-03-19 16:28:00 +01:00
dependency.hpp
Prevent worst-case exponential complexity in dependency evaluation
2025-08-04 10:42:20 +02:00
dependency.ti
Mark MakeName and ParseName virtual methods as override
2025-05-19 11:33:22 +02:00
downtime.cpp
Fix compiler warnings by (copy-)constructing loop variables explicitly
2025-04-22 13:55:49 +02:00
downtime.hpp
Introduce & use enum DowntimeRemovalReason
2024-05-23 09:34:15 +02:00
downtime.ti
Mark MakeName and ParseName virtual methods as override
2025-05-19 11:33:22 +02:00
envresolver.cpp
Introduce EnvResolver
2023-02-06 11:25:25 +01:00
envresolver.hpp
Introduce EnvResolver
2023-02-06 11:25:25 +01:00
eventcommand.cpp
Use ExecuteOverride to override the command
2020-07-31 17:28:33 +02:00
eventcommand.hpp
Don't mark a method as virtual in a final class
2023-01-26 09:10:38 +01:00
eventcommand.ti
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
externalcommandprocessor.cpp
Correct a problem with expiry times not being passed through to AcknowledgeProblem
2025-06-23 11:57:29 +02:00
externalcommandprocessor.hpp
Require to pass WaitGroup::Ptr to several methods
2025-05-23 14:53:58 +02:00
host.cpp
Merge {host,service}::StateTypeToString() & drop unused StateTypeFromString()
2025-06-06 13:31:44 +02:00
host.hpp
Merge {host,service}::StateTypeToString() & drop unused StateTypeFromString()
2025-06-06 13:31:44 +02:00
host.ti
Replace EventuallyAtomic with AtomicOrLocked which falls back to a mutex
2022-05-03 12:02:46 +02:00
hostgroup.cpp
Fix compiler warnings by (copy-)constructing loop variables explicitly
2025-04-22 13:55:49 +02:00
hostgroup.hpp
Use std::mutex, not boost::mutex
2021-02-03 09:54:57 +01:00
hostgroup.ti
Replace EventuallyAtomic with AtomicOrLocked which falls back to a mutex
2022-05-03 12:02:46 +02:00
i2-icinga.hpp
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
icinga-itl.conf
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
icingaapplication.cpp
MacroProcessor::ResolveMacro(): treat quasi-CV-object IcingaApplication as real CV-object
2023-05-31 16:35:09 +02:00
icingaapplication.hpp
Fix that MaxConcurrentChecks constant is overridden from 'checker' feature
2019-04-16 15:04:57 +02:00
icingaapplication.ti
Merge pull request #6970 from Icinga/bugfix/perfdata-gaps
2019-02-26 15:38:15 +01:00
legacytimeperiod.cpp
Merge pull request #9731 from Icinga/fix-compiler-warnings-by-copy-constructing-loop-variables-explicitly
2025-05-21 14:26:47 +02:00
legacytimeperiod.hpp
LegacyTimePeriod: Prevent modification of input parameters
2021-07-22 15:17:06 +02:00
macroprocessor.cpp
MacroProcessor::ResolveMacro(): treat quasi-CV-object IcingaApplication as real CV-object
2023-05-31 16:35:09 +02:00
macroprocessor.hpp
ResolverSpec: add option not to resolve "$name$"
2023-02-06 16:39:17 +01:00
macroresolver.hpp
Refactor MacroResolver::OverrideMacros
2020-07-03 15:53:51 +02:00
notification-apply.cpp
CONTEXT: use << everywhere to unify usages
2022-11-30 11:06:51 +01:00
notification.cpp
Refresh the states & types bitsets whenever states & types attrs change
2025-06-06 13:31:44 +02:00
notification.hpp
Refresh the states & types bitsets whenever states & types attrs change
2025-06-06 13:31:44 +02:00
notification.ti
Refresh the states & types bitsets whenever states & types attrs change
2025-06-06 13:31:44 +02:00
notificationcommand.cpp
Use ExecuteOverride to override the command
2020-07-31 17:28:33 +02:00
notificationcommand.hpp
Use ExecuteOverride to override the command
2020-07-31 17:28:33 +02:00
notificationcommand.ti
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
objectutils.cpp
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
objectutils.hpp
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
pluginutility.cpp
PluginUtility: Fix PerfData don't get parsed correctly
2023-04-05 15:37:54 +02:00
pluginutility.hpp
PluginUtility::FormatPerfdata(): normalize UoMs if desired
2021-07-05 19:05:32 +02:00
scheduleddowntime-apply.cpp
CONTEXT: use << everywhere to unify usages
2022-11-30 11:06:51 +01:00
scheduleddowntime.cpp
Introduce & use enum DowntimeRemovalReason
2024-05-23 09:34:15 +02:00
scheduleddowntime.hpp
Targeted apply rules: don't unnecessarily eval filter
2022-10-28 14:27:53 +02:00
scheduleddowntime.ti
Mark MakeName and ParseName virtual methods as override
2025-05-19 11:33:22 +02:00
service-apply.cpp
CONTEXT: use << everywhere to unify usages
2022-11-30 11:06:51 +01:00
service.cpp
Merge {host,service}::StateTypeToString() & drop unused StateTypeFromString()
2025-06-06 13:31:44 +02:00
service.hpp
Merge {host,service}::StateTypeToString() & drop unused StateTypeFromString()
2025-06-06 13:31:44 +02:00
service.ti
Mark MakeName and ParseName virtual methods as override
2025-05-19 11:33:22 +02:00
servicegroup.cpp
Fix compiler warnings by (copy-)constructing loop variables explicitly
2025-04-22 13:55:49 +02:00
servicegroup.hpp
Use std::mutex, not boost::mutex
2021-02-03 09:54:57 +01:00
servicegroup.ti
Replace EventuallyAtomic with AtomicOrLocked which falls back to a mutex
2022-05-03 12:02:46 +02:00
timeperiod.cpp
Fix compiler warnings by (copy-)constructing loop variables explicitly
2025-04-22 13:55:49 +02:00
timeperiod.hpp
Replace Copyright header with a short version, part I
2019-02-25 14:48:22 +01:00
timeperiod.ti
Replace EventuallyAtomic with AtomicOrLocked which falls back to a mutex
2022-05-03 12:02:46 +02:00
user.cpp
Refresh the states & types bitsets whenever states & types attrs change
2025-06-06 13:31:44 +02:00
user.hpp
Refresh the states & types bitsets whenever states & types attrs change
2025-06-06 13:31:44 +02:00
user.ti
Refresh the states & types bitsets whenever states & types attrs change
2025-06-06 13:31:44 +02:00
usergroup.cpp
Fix compiler warnings by (copy-)constructing loop variables explicitly
2025-04-22 13:55:49 +02:00
usergroup.hpp
Fix build on Mac with -DICINGA2_UNITY_BUILD=OFF -DICINGA2_WITH_LIVESTATUS=ON
2024-09-27 12:41:11 +02:00
usergroup.ti
Replace EventuallyAtomic with AtomicOrLocked which falls back to a mutex
2022-05-03 12:02:46 +02:00