| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | package l2topology |
| 4 | |
| 5 | import ( |
| 6 | "sort" |
| 7 | "strings" |
| 8 | ) |
| 9 | |
| 10 | func collapseActorsByIP(actors []Actor) []Actor { |
| 11 | if len(actors) <= 1 { |
| 12 | return actors |
| 13 | } |
| 14 | |
| 15 | parent := make([]int, len(actors)) |
| 16 | for i := range parent { |
| 17 | parent[i] = i |
| 18 | } |
| 19 | find := func(x int) int { |
| 20 | for parent[x] != x { |
| 21 | parent[x] = parent[parent[x]] |
| 22 | x = parent[x] |
| 23 | } |
| 24 | return x |
| 25 | } |
| 26 | union := func(a, b int) { |
| 27 | ra := find(a) |
| 28 | rb := find(b) |
| 29 | if ra == rb { |
| 30 | return |
| 31 | } |
| 32 | if ra < rb { |
| 33 | parent[rb] = ra |
| 34 | return |
| 35 | } |
| 36 | parent[ra] = rb |
| 37 | } |
| 38 | |
| 39 | ipOwner := make(map[string]int) |
| 40 | for idx, actor := range actors { |
| 41 | if strings.EqualFold(strings.TrimSpace(actor.ActorType), "segment") { |
| 42 | continue |
| 43 | } |
| 44 | ips := normalizedTopologyActorIPs(actor) |
| 45 | if len(ips) == 0 { |
| 46 | continue |
| 47 | } |
| 48 | for _, ip := range ips { |
| 49 | if owner, ok := ipOwner[ip]; ok { |
| 50 | union(idx, owner) |
| 51 | continue |
| 52 | } |
| 53 | ipOwner[ip] = idx |
| 54 | } |
| 55 | } |
| 56 | |
| 57 | groups := make(map[int][]int) |
| 58 | for idx := range actors { |
| 59 | root := find(idx) |
| 60 | groups[root] = append(groups[root], idx) |
| 61 | } |
| 62 | |
| 63 | keep := make([]bool, len(actors)) |
| 64 | for i := range keep { |
| 65 | keep[i] = true |
| 66 | } |
| 67 | for _, members := range groups { |
| 68 | if len(members) <= 1 { |
| 69 | continue |
| 70 | } |
| 71 | rep := members[0] |
| 72 | for _, idx := range members[1:] { |
| 73 | if compareTopologyActorCollapsePriority(actors[idx], actors[rep]) < 0 { |
| 74 | rep = idx |
| 75 | } |
| 76 | } |
| 77 | merged := actors[rep] |
| 78 | collapsedCount := 1 |
| 79 | for _, idx := range members { |
| 80 | if idx == rep { |
| 81 | continue |
| 82 | } |
| 83 | collapsedCount++ |
| 84 | merged.Match = mergeTopologyActorMatch(merged.Match, actors[idx].Match) |
| 85 | merged.Labels = mergeTopologyActorLabels(merged.Labels, actors[idx].Labels) |
| 86 | merged.Attributes = mergeTopologyActorAttributes(merged.Attributes, actors[idx].Attributes) |
| 87 | keep[idx] = false |
| 88 | } |
| 89 | if collapsedCount > 1 { |
| 90 | if merged.Attributes == nil { |
| 91 | merged.Attributes = make(map[string]any) |
| 92 | } |
| 93 | merged.Attributes["collapsed_by_ip"] = true |
| 94 | merged.Attributes["collapsed_count"] = collapsedCount |
| 95 | } |
| 96 | actors[rep] = merged |
| 97 | } |
| 98 | |
| 99 | out := make([]Actor, 0, len(actors)) |
| 100 | for idx, actor := range actors { |
| 101 | if !keep[idx] { |
| 102 | continue |
| 103 | } |
| 104 | out = append(out, actor) |
| 105 | } |
| 106 | return out |
| 107 | } |
| 108 | |
| 109 | func eliminateNonIPInferredActors(actors []Actor, links []Link) ([]Actor, []Link) { |
| 110 | if len(actors) == 0 { |
| 111 | return actors, links |
| 112 | } |
| 113 | removedIdentityKeys := make(map[string]struct{}) |
| 114 | filteredActors := make([]Actor, 0, len(actors)) |
| 115 | for _, actor := range actors { |
| 116 | if topologyActorIsInferred(actor) && len(normalizedTopologyActorIPs(actor)) == 0 { |
| 117 | for _, key := range topologyMatchIdentityKeys(actor.Match) { |
| 118 | removedIdentityKeys[key] = struct{}{} |
| 119 | } |
| 120 | continue |
| 121 | } |
| 122 | filteredActors = append(filteredActors, actor) |
| 123 | } |
| 124 | if len(removedIdentityKeys) == 0 { |
| 125 | return actors, links |
| 126 | } |
| 127 | |
| 128 | filteredLinks := make([]Link, 0, len(links)) |
| 129 | for _, link := range links { |
| 130 | srcKeys := topologyMatchIdentityKeys(link.Src.Match) |
| 131 | dstKeys := topologyMatchIdentityKeys(link.Dst.Match) |
| 132 | if topologyIdentityKeysOverlap(srcKeys, removedIdentityKeys) { |
| 133 | continue |
| 134 | } |
| 135 | if topologyIdentityKeysOverlap(dstKeys, removedIdentityKeys) { |
| 136 | continue |
| 137 | } |
| 138 | filteredLinks = append(filteredLinks, link) |
| 139 | } |
| 140 | return filteredActors, filteredLinks |
| 141 | } |
| 142 | |
| 143 | func topologyIdentityKeysOverlap(keys []string, set map[string]struct{}) bool { |
| 144 | if len(keys) == 0 || len(set) == 0 { |
| 145 | return false |
| 146 | } |
| 147 | for _, key := range keys { |
| 148 | if _, ok := set[key]; ok { |
| 149 | return true |
| 150 | } |
| 151 | } |
| 152 | return false |
| 153 | } |
| 154 | |
| 155 | func normalizedTopologyActorIPs(actor Actor) []string { |
| 156 | if len(actor.Match.IPAddresses) == 0 { |
| 157 | return nil |
| 158 | } |
| 159 | seen := make(map[string]struct{}, len(actor.Match.IPAddresses)) |
| 160 | out := make([]string, 0, len(actor.Match.IPAddresses)) |
| 161 | for _, value := range actor.Match.IPAddresses { |
| 162 | ip := normalizeTopologyIP(value) |
| 163 | if ip == "" { |
| 164 | continue |
| 165 | } |
| 166 | if _, ok := seen[ip]; ok { |
| 167 | continue |
| 168 | } |
| 169 | seen[ip] = struct{}{} |
| 170 | out = append(out, ip) |
| 171 | } |
| 172 | sort.Strings(out) |
| 173 | return out |
| 174 | } |
| 175 | |
| 176 | func compareTopologyActorCollapsePriority(left, right Actor) int { |
| 177 | leftDevice := IsDeviceActorType(left.ActorType) |
| 178 | rightDevice := IsDeviceActorType(right.ActorType) |
| 179 | if leftDevice != rightDevice { |
| 180 | if leftDevice { |
| 181 | return -1 |
| 182 | } |
| 183 | return 1 |
| 184 | } |
| 185 | leftInferred := topologyActorIsInferred(left) |
| 186 | rightInferred := topologyActorIsInferred(right) |
| 187 | if leftInferred != rightInferred { |
| 188 | if !leftInferred { |
| 189 | return -1 |
| 190 | } |
| 191 | return 1 |
| 192 | } |
| 193 | leftKey := canonicalTopologyMatchKey(left.Match) |
| 194 | rightKey := canonicalTopologyMatchKey(right.Match) |
| 195 | return strings.Compare(leftKey, rightKey) |
| 196 | } |
| 197 | |
| 198 | func mergeTopologyActorMatch(base, other Match) Match { |
| 199 | base.ChassisIDs = mergeTopologyStringLists(base.ChassisIDs, other.ChassisIDs) |
| 200 | base.MacAddresses = mergeTopologyStringLists(base.MacAddresses, other.MacAddresses) |
| 201 | base.IPAddresses = mergeTopologyStringLists(base.IPAddresses, other.IPAddresses) |
| 202 | base.Hostnames = mergeTopologyStringLists(base.Hostnames, other.Hostnames) |
| 203 | base.DNSNames = mergeTopologyStringLists(base.DNSNames, other.DNSNames) |
| 204 | if strings.TrimSpace(base.SysName) == "" { |
| 205 | base.SysName = strings.TrimSpace(other.SysName) |
| 206 | } |
| 207 | if strings.TrimSpace(base.SysObjectID) == "" { |
| 208 | base.SysObjectID = strings.TrimSpace(other.SysObjectID) |
| 209 | } |
| 210 | return base |
| 211 | } |
| 212 | |
| 213 | func mergeTopologyStringLists(base []string, extra []string) []string { |
| 214 | seen := make(map[string]struct{}, len(base)+len(extra)) |
| 215 | out := make([]string, 0, len(base)+len(extra)) |
| 216 | for _, value := range append(base, extra...) { |
| 217 | value = strings.TrimSpace(value) |
| 218 | if value == "" { |
| 219 | continue |
| 220 | } |
| 221 | if _, ok := seen[value]; ok { |
| 222 | continue |
| 223 | } |
| 224 | seen[value] = struct{}{} |
| 225 | out = append(out, value) |
| 226 | } |
| 227 | sort.Strings(out) |
| 228 | if len(out) == 0 { |
| 229 | return nil |
| 230 | } |
| 231 | return out |
| 232 | } |
| 233 | |
| 234 | func mergeTopologyActorLabels(base, extra map[string]string) map[string]string { |
| 235 | if len(extra) == 0 { |
| 236 | return base |
| 237 | } |
| 238 | if base == nil { |
| 239 | base = make(map[string]string, len(extra)) |
| 240 | } |
| 241 | for key, value := range extra { |
| 242 | key = strings.TrimSpace(key) |
| 243 | value = strings.TrimSpace(value) |
| 244 | if key == "" || value == "" { |
| 245 | continue |
| 246 | } |
| 247 | if _, exists := base[key]; exists { |
| 248 | continue |
| 249 | } |
| 250 | base[key] = value |
| 251 | } |
| 252 | return base |
| 253 | } |
| 254 | |
| 255 | func mergeTopologyActorAttributes(base, extra map[string]any) map[string]any { |
| 256 | if len(extra) == 0 { |
| 257 | return base |
| 258 | } |
| 259 | if base == nil { |
| 260 | base = make(map[string]any, len(extra)) |
| 261 | } |
| 262 | for key, value := range extra { |
| 263 | key = strings.TrimSpace(key) |
| 264 | if key == "" { |
| 265 | continue |
| 266 | } |
| 267 | if _, exists := base[key]; exists { |
| 268 | continue |
| 269 | } |
| 270 | base[key] = value |
| 271 | } |
| 272 | return base |
| 273 | } |
| 274 | |
| 275 | func topologyActorIsInferred(actor Actor) bool { |
| 276 | if strings.EqualFold(strings.TrimSpace(actor.ActorType), "endpoint") { |
| 277 | return true |
| 278 | } |
| 279 | if topologyAnyBoolValue(actor.Attributes["inferred"]) { |
| 280 | return true |
| 281 | } |
| 282 | if len(actor.Labels) > 0 { |
| 283 | if topologyAnyBoolValue(actor.Labels["inferred"]) { |
| 284 | return true |
| 285 | } |
| 286 | } |
| 287 | return false |
| 288 | } |
| 289 | |
| 290 | func topologyAnyBoolValue(value any) bool { |
| 291 | switch typed := value.(type) { |
| 292 | case bool: |
| 293 | return typed |
| 294 | case string: |
| 295 | switch strings.ToLower(strings.TrimSpace(typed)) { |
| 296 | case "1", "true", "yes", "on": |
| 297 | return true |
| 298 | } |
| 299 | } |
| 300 | return false |
| 301 | } |