| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | package chartengine |
| 4 | |
| 5 | import ( |
| 6 | "sort" |
| 7 | |
| 8 | "github.com/netdata/netdata/go/plugins/plugin/framework/chartengine/internal/program" |
| 9 | ) |
| 10 | |
| 11 | func orderedMaterializedDimensionNames(dimensions map[string]*materializedDimensionState) []string { |
| 12 | type staticEntry struct { |
| 13 | name string |
| 14 | order int |
| 15 | } |
| 16 | staticEntries := make([]staticEntry, 0, len(dimensions)) |
| 17 | dynamicNames := make([]string, 0, len(dimensions)) |
| 18 | for name, dim := range dimensions { |
| 19 | if dim.static { |
| 20 | staticEntries = append(staticEntries, staticEntry{ |
| 21 | name: name, |
| 22 | order: dim.order, |
| 23 | }) |
| 24 | continue |
| 25 | } |
| 26 | dynamicNames = append(dynamicNames, name) |
| 27 | } |
| 28 | sort.Slice(staticEntries, func(i, j int) bool { |
| 29 | if staticEntries[i].order != staticEntries[j].order { |
| 30 | return staticEntries[i].order < staticEntries[j].order |
| 31 | } |
| 32 | return staticEntries[i].name < staticEntries[j].name |
| 33 | }) |
| 34 | sort.Strings(dynamicNames) |
| 35 | out := make([]string, 0, len(staticEntries)+len(dynamicNames)) |
| 36 | for _, item := range staticEntries { |
| 37 | out = append(out, item.name) |
| 38 | } |
| 39 | out = append(out, dynamicNames...) |
| 40 | return out |
| 41 | } |
| 42 | |
| 43 | func enforceLifecycleCaps( |
| 44 | currentSuccessSeq uint64, |
| 45 | chartsByID map[string]*chartState, |
| 46 | state *materializedState, |
| 47 | ) ([]RemoveDimensionAction, []RemoveChartAction) { |
| 48 | if len(chartsByID) == 0 || state == nil { |
| 49 | return nil, nil |
| 50 | } |
| 51 | removeCharts := enforceChartInstanceCaps(currentSuccessSeq, chartsByID, state) |
| 52 | removeDims := enforceDimensionCaps(currentSuccessSeq, chartsByID, state) |
| 53 | return removeDims, removeCharts |
| 54 | } |
| 55 | |
| 56 | func enforceChartInstanceCaps( |
| 57 | currentSuccessSeq uint64, |
| 58 | chartsByID map[string]*chartState, |
| 59 | state *materializedState, |
| 60 | ) []RemoveChartAction { |
| 61 | observedByTemplate := make(map[string][]string) |
| 62 | for chartID, cs := range chartsByID { |
| 63 | observedByTemplate[cs.templateID] = append(observedByTemplate[cs.templateID], chartID) |
| 64 | } |
| 65 | for templateID := range observedByTemplate { |
| 66 | sort.Strings(observedByTemplate[templateID]) |
| 67 | } |
| 68 | |
| 69 | existingByTemplate := make(map[string][]string) |
| 70 | for chartID, matChart := range state.charts { |
| 71 | existingByTemplate[matChart.templateID] = append(existingByTemplate[matChart.templateID], chartID) |
| 72 | } |
| 73 | for templateID := range existingByTemplate { |
| 74 | sort.Strings(existingByTemplate[templateID]) |
| 75 | } |
| 76 | |
| 77 | removeCharts := make([]RemoveChartAction, 0) |
| 78 | |
| 79 | templateIDs := make([]string, 0, len(observedByTemplate)) |
| 80 | for templateID := range observedByTemplate { |
| 81 | templateIDs = append(templateIDs, templateID) |
| 82 | } |
| 83 | sort.Strings(templateIDs) |
| 84 | |
| 85 | for _, templateID := range templateIDs { |
| 86 | observedIDs := observedByTemplate[templateID] |
| 87 | var lifecycle program.LifecyclePolicy |
| 88 | if len(observedIDs) > 0 { |
| 89 | lifecycle = chartsByID[observedIDs[0]].lifecycle |
| 90 | } |
| 91 | // max_instances is a soft cap: |
| 92 | // currently active chart instances are never evicted in the same successful cycle. |
| 93 | maxInstances := lifecycle.MaxInstances |
| 94 | if maxInstances <= 0 { |
| 95 | continue |
| 96 | } |
| 97 | |
| 98 | existingIDs := existingByTemplate[templateID] |
| 99 | existingSet := make(map[string]struct{}, len(existingIDs)) |
| 100 | for _, id := range existingIDs { |
| 101 | existingSet[id] = struct{}{} |
| 102 | } |
| 103 | newObserved := make([]string, 0, len(observedIDs)) |
| 104 | for _, id := range observedIDs { |
| 105 | if _, ok := existingSet[id]; !ok { |
| 106 | newObserved = append(newObserved, id) |
| 107 | } |
| 108 | } |
| 109 | |
| 110 | total := len(existingIDs) + len(newObserved) |
| 111 | if total <= maxInstances { |
| 112 | continue |
| 113 | } |
| 114 | overflow := total - maxInstances |
| 115 | |
| 116 | type chartCandidate struct { |
| 117 | chartID string |
| 118 | lastSeen uint64 |
| 119 | } |
| 120 | candidates := make([]chartCandidate, 0, len(existingIDs)) |
| 121 | for _, chartID := range existingIDs { |
| 122 | matChart := state.charts[chartID] |
| 123 | if matChart == nil { |
| 124 | continue |
| 125 | } |
| 126 | // Never evict chart instances seen in the current successful cycle. |
| 127 | if matChart.lastSeenSuccessSeq == currentSuccessSeq { |
| 128 | continue |
| 129 | } |
| 130 | if _, seen := chartsByID[chartID]; seen { |
| 131 | continue |
| 132 | } |
| 133 | candidates = append(candidates, chartCandidate{ |
| 134 | chartID: chartID, |
| 135 | lastSeen: matChart.lastSeenSuccessSeq, |
| 136 | }) |
| 137 | } |
| 138 | sort.Slice(candidates, func(i, j int) bool { |
| 139 | if candidates[i].lastSeen != candidates[j].lastSeen { |
| 140 | return candidates[i].lastSeen < candidates[j].lastSeen |
| 141 | } |
| 142 | return candidates[i].chartID < candidates[j].chartID |
| 143 | }) |
| 144 | |
| 145 | for i := 0; i < len(candidates) && overflow > 0; i++ { |
| 146 | chartID := candidates[i].chartID |
| 147 | matChart := state.charts[chartID] |
| 148 | if matChart == nil { |
| 149 | continue |
| 150 | } |
| 151 | removeCharts = append(removeCharts, RemoveChartAction{ |
| 152 | ChartID: chartID, |
| 153 | Meta: matChart.meta, |
| 154 | }) |
| 155 | delete(state.charts, chartID) |
| 156 | overflow-- |
| 157 | } |
| 158 | |
| 159 | if overflow > 0 { |
| 160 | // Drop new chart instances deterministically when no eviction candidates remain. |
| 161 | // If all existing instances are active and no new ones were observed, overflow remains |
| 162 | // and the soft cap may be temporarily exceeded. |
| 163 | for i := len(newObserved) - 1; i >= 0 && overflow > 0; i-- { |
| 164 | delete(chartsByID, newObserved[i]) |
| 165 | overflow-- |
| 166 | } |
| 167 | } |
| 168 | } |
| 169 | return removeCharts |
| 170 | } |
| 171 | |
| 172 | func enforceDimensionCaps( |
| 173 | currentSuccessSeq uint64, |
| 174 | chartsByID map[string]*chartState, |
| 175 | state *materializedState, |
| 176 | ) []RemoveDimensionAction { |
| 177 | // Per-chart dimension caps: evict least-recently-seen inactive dims first, then drop new dims. |
| 178 | removeDims := make([]RemoveDimensionAction, 0) |
| 179 | chartIDs := make([]string, 0, len(chartsByID)) |
| 180 | for chartID := range chartsByID { |
| 181 | chartIDs = append(chartIDs, chartID) |
| 182 | } |
| 183 | sort.Strings(chartIDs) |
| 184 | for _, chartID := range chartIDs { |
| 185 | cs := chartsByID[chartID] |
| 186 | maxDims := cs.lifecycle.Dimensions.MaxDims |
| 187 | if maxDims <= 0 { |
| 188 | continue |
| 189 | } |
| 190 | matChart := state.charts[chartID] |
| 191 | existingCount := 0 |
| 192 | if matChart != nil { |
| 193 | existingCount = len(matChart.dimensions) |
| 194 | } |
| 195 | |
| 196 | newNames := make([]string, 0, cs.observedCount) |
| 197 | for name, entry := range cs.entries { |
| 198 | if entry == nil || entry.seenSeq != cs.currentBuildSeq { |
| 199 | continue |
| 200 | } |
| 201 | if matChart == nil || matChart.dimensions[name] == nil { |
| 202 | newNames = append(newNames, name) |
| 203 | } |
| 204 | } |
| 205 | sort.Strings(newNames) |
| 206 | |
| 207 | total := existingCount + len(newNames) |
| 208 | if total <= maxDims { |
| 209 | continue |
| 210 | } |
| 211 | overflow := total - maxDims |
| 212 | |
| 213 | if matChart != nil && overflow > 0 { |
| 214 | type dimCandidate struct { |
| 215 | name string |
| 216 | lastSeen uint64 |
| 217 | } |
| 218 | candidates := make([]dimCandidate, 0, len(matChart.dimensions)) |
| 219 | for name, dim := range matChart.dimensions { |
| 220 | if dim.lastSeenSuccessSeq == currentSuccessSeq { |
| 221 | continue |
| 222 | } |
| 223 | if entry, seen := cs.entries[name]; seen && entry != nil && entry.seenSeq == cs.currentBuildSeq { |
| 224 | continue |
| 225 | } |
| 226 | candidates = append(candidates, dimCandidate{ |
| 227 | name: name, |
| 228 | lastSeen: dim.lastSeenSuccessSeq, |
| 229 | }) |
| 230 | } |
| 231 | sort.Slice(candidates, func(i, j int) bool { |
| 232 | if candidates[i].lastSeen != candidates[j].lastSeen { |
| 233 | return candidates[i].lastSeen < candidates[j].lastSeen |
| 234 | } |
| 235 | return candidates[i].name < candidates[j].name |
| 236 | }) |
| 237 | for i := 0; i < len(candidates) && overflow > 0; i++ { |
| 238 | name := candidates[i].name |
| 239 | dim := matChart.dimensions[name] |
| 240 | if dim == nil { |
| 241 | continue |
| 242 | } |
| 243 | removeDims = append(removeDims, RemoveDimensionAction{ |
| 244 | ChartID: chartID, |
| 245 | ChartMeta: matChart.meta, |
| 246 | Name: name, |
| 247 | Hidden: dim.hidden, |
| 248 | Float: dim.float, |
| 249 | Algorithm: dim.algorithm, |
| 250 | Multiplier: dim.multiplier, |
| 251 | Divisor: dim.divisor, |
| 252 | }) |
| 253 | matChart.removeDimension(name) |
| 254 | overflow-- |
| 255 | } |
| 256 | } |
| 257 | |
| 258 | if overflow > 0 { |
| 259 | orderedObserved := orderedObservedDimensionNames(cs.entries, cs.currentBuildSeq) |
| 260 | // Drop newest/least-priority candidates first (end of deterministic order). |
| 261 | for i := len(orderedObserved) - 1; i >= 0 && overflow > 0; i-- { |
| 262 | name := orderedObserved[i] |
| 263 | if matChart != nil && matChart.dimensions[name] != nil { |
| 264 | continue |
| 265 | } |
| 266 | delete(cs.entries, name) |
| 267 | cs.observedCount-- |
| 268 | overflow-- |
| 269 | } |
| 270 | } |
| 271 | } |
| 272 | return removeDims |
| 273 | } |
| 274 | |
| 275 | func collectExpiryRemovals( |
| 276 | currentSuccessSeq uint64, |
| 277 | state *materializedState, |
| 278 | ) ([]RemoveDimensionAction, []RemoveChartAction) { |
| 279 | if state == nil || len(state.charts) == 0 { |
| 280 | return nil, nil |
| 281 | } |
| 282 | |
| 283 | chartIDs := make([]string, 0, len(state.charts)) |
| 284 | for chartID := range state.charts { |
| 285 | chartIDs = append(chartIDs, chartID) |
| 286 | } |
| 287 | sort.Strings(chartIDs) |
| 288 | |
| 289 | toRemoveChart := make(map[string]struct{}) |
| 290 | for _, chartID := range chartIDs { |
| 291 | matChart := state.charts[chartID] |
| 292 | if shouldExpire(matChart.lastSeenSuccessSeq, currentSuccessSeq, matChart.lifecycle.ExpireAfterCycles) { |
| 293 | toRemoveChart[chartID] = struct{}{} |
| 294 | } |
| 295 | } |
| 296 | |
| 297 | removeDims := make([]RemoveDimensionAction, 0) |
| 298 | for _, chartID := range chartIDs { |
| 299 | if _, removed := toRemoveChart[chartID]; removed { |
| 300 | continue |
| 301 | } |
| 302 | matChart := state.charts[chartID] |
| 303 | expireAfter := matChart.lifecycle.Dimensions.ExpireAfterCycles |
| 304 | if expireAfter <= 0 || len(matChart.dimensions) == 0 { |
| 305 | continue |
| 306 | } |
| 307 | |
| 308 | dimNames := make([]string, 0, len(matChart.dimensions)) |
| 309 | for name := range matChart.dimensions { |
| 310 | dimNames = append(dimNames, name) |
| 311 | } |
| 312 | sort.Strings(dimNames) |
| 313 | for _, name := range dimNames { |
| 314 | dim := matChart.dimensions[name] |
| 315 | if !shouldExpire(dim.lastSeenSuccessSeq, currentSuccessSeq, expireAfter) { |
| 316 | continue |
| 317 | } |
| 318 | removeDims = append(removeDims, RemoveDimensionAction{ |
| 319 | ChartID: chartID, |
| 320 | ChartMeta: matChart.meta, |
| 321 | Name: name, |
| 322 | Hidden: dim.hidden, |
| 323 | Float: dim.float, |
| 324 | Algorithm: dim.algorithm, |
| 325 | Multiplier: dim.multiplier, |
| 326 | Divisor: dim.divisor, |
| 327 | }) |
| 328 | matChart.removeDimension(name) |
| 329 | } |
| 330 | } |
| 331 | |
| 332 | removeCharts := make([]RemoveChartAction, 0, len(toRemoveChart)) |
| 333 | for _, chartID := range chartIDs { |
| 334 | if _, removed := toRemoveChart[chartID]; !removed { |
| 335 | continue |
| 336 | } |
| 337 | matChart := state.charts[chartID] |
| 338 | if matChart == nil { |
| 339 | continue |
| 340 | } |
| 341 | removeCharts = append(removeCharts, RemoveChartAction{ |
| 342 | ChartID: chartID, |
| 343 | Meta: matChart.meta, |
| 344 | }) |
| 345 | delete(state.charts, chartID) |
| 346 | } |
| 347 | return removeDims, removeCharts |
| 348 | } |
| 349 | |
| 350 | func orderedObservedDimensionNames(entries map[string]*dimBuildEntry, seenSeq uint64) []string { |
| 351 | type staticEntry struct { |
| 352 | name string |
| 353 | order int |
| 354 | } |
| 355 | staticEntries := make([]staticEntry, 0, len(entries)) |
| 356 | dynamicNames := make([]string, 0, len(entries)) |
| 357 | for name, entry := range entries { |
| 358 | if entry == nil || entry.seenSeq != seenSeq { |
| 359 | continue |
| 360 | } |
| 361 | if entry.static { |
| 362 | staticEntries = append(staticEntries, staticEntry{ |
| 363 | name: name, |
| 364 | order: entry.order, |
| 365 | }) |
| 366 | continue |
| 367 | } |
| 368 | dynamicNames = append(dynamicNames, name) |
| 369 | } |
| 370 | sort.Slice(staticEntries, func(i, j int) bool { |
| 371 | if staticEntries[i].order != staticEntries[j].order { |
| 372 | return staticEntries[i].order < staticEntries[j].order |
| 373 | } |
| 374 | return staticEntries[i].name < staticEntries[j].name |
| 375 | }) |
| 376 | sort.Strings(dynamicNames) |
| 377 | out := make([]string, 0, len(staticEntries)+len(dynamicNames)) |
| 378 | for _, entry := range staticEntries { |
| 379 | out = append(out, entry.name) |
| 380 | } |
| 381 | out = append(out, dynamicNames...) |
| 382 | return out |
| 383 | } |