| 1 | // SPDX-License-Identifier: GPL-3.0-or-later |
| 2 | |
| 3 | package l2topology |
| 4 | |
| 5 | import ( |
| 6 | "sort" |
| 7 | "strconv" |
| 8 | "strings" |
| 9 | ) |
| 10 | |
| 11 | // bridgeDomainModel is the persisted bridge-domain assembly equivalent that |
| 12 | // topology projection can consume directly. |
| 13 | type bridgeDomainModel struct { |
| 14 | domains []*bridgeBroadcastDomain |
| 15 | } |
| 16 | |
| 17 | type bridgeBroadcastDomain struct { |
| 18 | bridges map[string]*bridgeDomainBridge |
| 19 | segments []*bridgeDomainSegment |
| 20 | } |
| 21 | |
| 22 | type bridgeDomainBridge struct { |
| 23 | nodeID string |
| 24 | root bool |
| 25 | } |
| 26 | |
| 27 | type bridgeDomainSegment struct { |
| 28 | designatedPort bridgePortRef |
| 29 | ports map[string]bridgePortRef |
| 30 | endpointIDs map[string]struct{} |
| 31 | methods map[string]struct{} |
| 32 | } |
| 33 | |
| 34 | type bridgeBridgeLinkRecord struct { |
| 35 | port bridgePortRef |
| 36 | designatedPort bridgePortRef |
| 37 | method string |
| 38 | } |
| 39 | |
| 40 | type bridgeMacLinkRecord struct { |
| 41 | port bridgePortRef |
| 42 | endpointID string |
| 43 | method string |
| 44 | } |
| 45 | |
| 46 | type bridgeNodeSet map[string]struct{} |
| 47 | |
| 48 | func (s bridgeNodeSet) add(v string) { |
| 49 | v = strings.TrimSpace(v) |
| 50 | if v == "" { |
| 51 | return |
| 52 | } |
| 53 | s[v] = struct{}{} |
| 54 | } |
| 55 | |
| 56 | func buildBridgeDomainModel( |
| 57 | bridgeLinks []bridgeBridgeLinkRecord, |
| 58 | macLinks []bridgeMacLinkRecord, |
| 59 | ) bridgeDomainModel { |
| 60 | model := bridgeDomainModel{domains: make([]*bridgeBroadcastDomain, 0)} |
| 61 | if len(bridgeLinks) == 0 && len(macLinks) == 0 { |
| 62 | return model |
| 63 | } |
| 64 | |
| 65 | bblSegments := make([]*bridgeDomainSegment, 0) |
| 66 | rootToNodes := make(map[string]bridgeNodeSet) |
| 67 | |
| 68 | for _, link := range bridgeLinks { |
| 69 | designatedNodeID := strings.TrimSpace(link.designatedPort.deviceID) |
| 70 | nodeID := strings.TrimSpace(link.port.deviceID) |
| 71 | if designatedNodeID == "" || nodeID == "" { |
| 72 | continue |
| 73 | } |
| 74 | |
| 75 | added := false |
| 76 | for _, segment := range bblSegments { |
| 77 | if segment.containsPort(link.designatedPort) { |
| 78 | segment.addPort(link.port) |
| 79 | added = true |
| 80 | break |
| 81 | } |
| 82 | } |
| 83 | if !added { |
| 84 | segment := newBridgeDomainSegment(link.designatedPort) |
| 85 | segment.addPort(link.port) |
| 86 | bblSegments = append(bblSegments, segment) |
| 87 | } |
| 88 | |
| 89 | mergeRootDomainSets(rootToNodes, designatedNodeID, nodeID) |
| 90 | } |
| 91 | |
| 92 | bmlSegments := make([]*bridgeDomainSegment, 0) |
| 93 | for _, link := range macLinks { |
| 94 | if strings.TrimSpace(link.port.deviceID) == "" || strings.TrimSpace(link.endpointID) == "" { |
| 95 | continue |
| 96 | } |
| 97 | |
| 98 | added := false |
| 99 | for _, segment := range bblSegments { |
| 100 | if segment.containsPort(link.port) { |
| 101 | segment.addEndpoint(link.endpointID, link.method) |
| 102 | added = true |
| 103 | break |
| 104 | } |
| 105 | } |
| 106 | if added { |
| 107 | continue |
| 108 | } |
| 109 | for _, segment := range bmlSegments { |
| 110 | if segment.containsPort(link.port) { |
| 111 | segment.addEndpoint(link.endpointID, link.method) |
| 112 | added = true |
| 113 | break |
| 114 | } |
| 115 | } |
| 116 | if added { |
| 117 | continue |
| 118 | } |
| 119 | |
| 120 | segment := newBridgeDomainSegment(link.port) |
| 121 | segment.addEndpoint(link.endpointID, link.method) |
| 122 | bmlSegments = append(bmlSegments, segment) |
| 123 | } |
| 124 | |
| 125 | rootIDs := sortedStringKeys(rootToNodes) |
| 126 | for _, rootID := range rootIDs { |
| 127 | domain := &bridgeBroadcastDomain{ |
| 128 | bridges: make(map[string]*bridgeDomainBridge), |
| 129 | segments: make([]*bridgeDomainSegment, 0), |
| 130 | } |
| 131 | domain.bridges[rootID] = &bridgeDomainBridge{nodeID: rootID, root: true} |
| 132 | for nodeID := range rootToNodes[rootID] { |
| 133 | domain.bridges[nodeID] = &bridgeDomainBridge{nodeID: nodeID, root: false} |
| 134 | } |
| 135 | model.domains = append(model.domains, domain) |
| 136 | } |
| 137 | |
| 138 | for _, segment := range bblSegments { |
| 139 | for _, domain := range model.domains { |
| 140 | if domain.loadSegment(segment) { |
| 141 | break |
| 142 | } |
| 143 | } |
| 144 | } |
| 145 | |
| 146 | for _, segment := range bmlSegments { |
| 147 | inserted := false |
| 148 | for _, domain := range model.domains { |
| 149 | if domain.loadSegment(segment) { |
| 150 | inserted = true |
| 151 | break |
| 152 | } |
| 153 | } |
| 154 | if inserted { |
| 155 | continue |
| 156 | } |
| 157 | |
| 158 | rootID := strings.TrimSpace(segment.designatedPort.deviceID) |
| 159 | if rootID == "" { |
| 160 | continue |
| 161 | } |
| 162 | domain := &bridgeBroadcastDomain{ |
| 163 | bridges: map[string]*bridgeDomainBridge{ |
| 164 | rootID: {nodeID: rootID, root: true}, |
| 165 | }, |
| 166 | segments: make([]*bridgeDomainSegment, 0, 1), |
| 167 | } |
| 168 | domain.loadSegment(segment) |
| 169 | model.domains = append(model.domains, domain) |
| 170 | } |
| 171 | |
| 172 | sort.SliceStable(model.domains, func(i, j int) bool { |
| 173 | return model.domains[i].sortKey() < model.domains[j].sortKey() |
| 174 | }) |
| 175 | for _, domain := range model.domains { |
| 176 | domain.sortSegments() |
| 177 | } |
| 178 | |
| 179 | return model |
| 180 | } |
| 181 | |
| 182 | func mergeRootDomainSets(rootToNodes map[string]bridgeNodeSet, designatedNodeID, nodeID string) { |
| 183 | designatedNodeID = strings.TrimSpace(designatedNodeID) |
| 184 | nodeID = strings.TrimSpace(nodeID) |
| 185 | if designatedNodeID == "" || nodeID == "" { |
| 186 | return |
| 187 | } |
| 188 | |
| 189 | targetRoot := findRootForNode(rootToNodes, designatedNodeID) |
| 190 | if targetRoot == "" { |
| 191 | targetRoot = designatedNodeID |
| 192 | } |
| 193 | targetSet := rootToNodes[targetRoot] |
| 194 | if targetSet == nil { |
| 195 | targetSet = make(bridgeNodeSet) |
| 196 | } |
| 197 | if designatedNodeID != targetRoot { |
| 198 | targetSet.add(designatedNodeID) |
| 199 | } |
| 200 | |
| 201 | sourceRoot := findRootForNode(rootToNodes, nodeID) |
| 202 | if sourceRoot != "" && sourceRoot != targetRoot { |
| 203 | if sourceSet, ok := rootToNodes[sourceRoot]; ok { |
| 204 | for id := range sourceSet { |
| 205 | targetSet.add(id) |
| 206 | } |
| 207 | delete(rootToNodes, sourceRoot) |
| 208 | } |
| 209 | targetSet.add(sourceRoot) |
| 210 | } |
| 211 | if nodeID != targetRoot { |
| 212 | targetSet.add(nodeID) |
| 213 | } |
| 214 | |
| 215 | rootToNodes[targetRoot] = targetSet |
| 216 | } |
| 217 | |
| 218 | func findRootForNode(rootToNodes map[string]bridgeNodeSet, nodeID string) string { |
| 219 | nodeID = strings.TrimSpace(nodeID) |
| 220 | if nodeID == "" { |
| 221 | return "" |
| 222 | } |
| 223 | if _, ok := rootToNodes[nodeID]; ok { |
| 224 | return nodeID |
| 225 | } |
| 226 | if rootID := findRootContaining(rootToNodes, nodeID); rootID != "" { |
| 227 | return rootID |
| 228 | } |
| 229 | return "" |
| 230 | } |
| 231 | |
| 232 | func findRootContaining(rootToNodes map[string]bridgeNodeSet, nodeID string) string { |
| 233 | for rootID, set := range rootToNodes { |
| 234 | if _, ok := set[nodeID]; ok { |
| 235 | return rootID |
| 236 | } |
| 237 | } |
| 238 | return "" |
| 239 | } |
| 240 | |
| 241 | func newBridgeDomainSegment(designatedPort bridgePortRef) *bridgeDomainSegment { |
| 242 | seg := &bridgeDomainSegment{ |
| 243 | designatedPort: designatedPort, |
| 244 | ports: make(map[string]bridgePortRef), |
| 245 | endpointIDs: make(map[string]struct{}), |
| 246 | methods: make(map[string]struct{}), |
| 247 | } |
| 248 | seg.addPort(designatedPort) |
| 249 | return seg |
| 250 | } |
| 251 | |
| 252 | func (s *bridgeDomainSegment) containsPort(port bridgePortRef) bool { |
| 253 | if s == nil { |
| 254 | return false |
| 255 | } |
| 256 | _, ok := s.ports[s.portIdentityKey(port)] |
| 257 | return ok |
| 258 | } |
| 259 | |
| 260 | func (s *bridgeDomainSegment) addPort(port bridgePortRef) { |
| 261 | if s == nil { |
| 262 | return |
| 263 | } |
| 264 | key := s.portIdentityKey(port) |
| 265 | if key == "" { |
| 266 | return |
| 267 | } |
| 268 | if existing, ok := s.ports[key]; ok { |
| 269 | if existing.ifName == "" { |
| 270 | existing.ifName = port.ifName |
| 271 | } |
| 272 | if existing.ifIndex == 0 && port.ifIndex > 0 { |
| 273 | existing.ifIndex = port.ifIndex |
| 274 | } |
| 275 | if existing.bridgePort == "" { |
| 276 | existing.bridgePort = port.bridgePort |
| 277 | } |
| 278 | if existing.vlanID == "" { |
| 279 | existing.vlanID = port.vlanID |
| 280 | } |
| 281 | port = existing |
| 282 | } |
| 283 | s.ports[key] = port |
| 284 | } |
| 285 | |
| 286 | func (s *bridgeDomainSegment) addEndpoint(endpointID, method string) { |
| 287 | if s == nil { |
| 288 | return |
| 289 | } |
| 290 | endpointID = strings.TrimSpace(endpointID) |
| 291 | if endpointID == "" { |
| 292 | return |
| 293 | } |
| 294 | s.endpointIDs[endpointID] = struct{}{} |
| 295 | method = strings.ToLower(strings.TrimSpace(method)) |
| 296 | if method == "" { |
| 297 | method = "fdb" |
| 298 | } |
| 299 | s.methods[method] = struct{}{} |
| 300 | } |
| 301 | |
| 302 | func (s *bridgeDomainSegment) portIdentityKey(port bridgePortRef) string { |
| 303 | nodeID := strings.TrimSpace(port.deviceID) |
| 304 | bridgePort := strings.TrimSpace(port.bridgePort) |
| 305 | if bridgePort == "" { |
| 306 | if port.ifIndex > 0 { |
| 307 | bridgePort = strconvItoa(port.ifIndex) |
| 308 | } else { |
| 309 | bridgePort = strings.TrimSpace(port.ifName) |
| 310 | } |
| 311 | } |
| 312 | if nodeID == "" || bridgePort == "" { |
| 313 | return "" |
| 314 | } |
| 315 | return nodeID + keySep + strings.ToLower(bridgePort) |
| 316 | } |
| 317 | |
| 318 | func (s *bridgeDomainSegment) sortKey() string { |
| 319 | return portSortKey(s.designatedPort) + keySep + strings.Join(sortedBridgePortSet(s.ports), ",") |
| 320 | } |
| 321 | |
| 322 | func (d *bridgeBroadcastDomain) loadSegment(segment *bridgeDomainSegment) bool { |
| 323 | if d == nil || segment == nil { |
| 324 | return false |
| 325 | } |
| 326 | for _, port := range segment.ports { |
| 327 | if _, ok := d.bridges[strings.TrimSpace(port.deviceID)]; ok { |
| 328 | d.segments = append(d.segments, segment) |
| 329 | return true |
| 330 | } |
| 331 | } |
| 332 | return false |
| 333 | } |
| 334 | |
| 335 | func (d *bridgeBroadcastDomain) sortKey() string { |
| 336 | if d == nil { |
| 337 | return "" |
| 338 | } |
| 339 | ids := make([]string, 0, len(d.bridges)) |
| 340 | for id := range d.bridges { |
| 341 | ids = append(ids, id) |
| 342 | } |
| 343 | sort.Strings(ids) |
| 344 | return strings.Join(ids, ",") |
| 345 | } |
| 346 | |
| 347 | func (d *bridgeBroadcastDomain) sortSegments() { |
| 348 | if d == nil { |
| 349 | return |
| 350 | } |
| 351 | sort.SliceStable(d.segments, func(i, j int) bool { |
| 352 | return d.segments[i].sortKey() < d.segments[j].sortKey() |
| 353 | }) |
| 354 | } |
| 355 | |
| 356 | func sortedBridgePortSet(m map[string]bridgePortRef) []string { |
| 357 | out := make([]string, 0, len(m)) |
| 358 | for _, port := range m { |
| 359 | out = append(out, portSortKey(port)) |
| 360 | } |
| 361 | sort.Strings(out) |
| 362 | return out |
| 363 | } |
| 364 | |
| 365 | func portSortKey(port bridgePortRef) string { |
| 366 | return strings.Join([]string{ |
| 367 | strings.TrimSpace(port.deviceID), |
| 368 | strings.ToLower(strings.TrimSpace(port.bridgePort)), |
| 369 | strings.TrimSpace(port.ifName), |
| 370 | strconvItoa(port.ifIndex), |
| 371 | strings.TrimSpace(port.vlanID), |
| 372 | }, keySep) |
| 373 | } |
| 374 | |
| 375 | func strconvItoa(v int) string { |
| 376 | if v <= 0 { |
| 377 | return "" |
| 378 | } |
| 379 | return strconv.Itoa(v) |
| 380 | } |
| 381 | |
| 382 | func sortedStringKeys[T any](m map[string]T) []string { |
| 383 | keys := make([]string, 0, len(m)) |
| 384 | for k := range m { |
| 385 | keys = append(keys, k) |
| 386 | } |
| 387 | sort.Strings(keys) |
| 388 | return keys |
| 389 | } |