100 lines
3.2 KiB
Markdown
100 lines
3.2 KiB
Markdown
# UNDF: UNDF-2026-000000688
|
||
# Defect: moby-0002 — NetworkDB.networkNodes []string O(N²) node membership scan
|
||
|
||
**Project:** moby (Docker Engine)
|
||
**File:** `daemon/libnetwork/networkdb/networkdb.go`
|
||
**Function:** `addNetworkNode`, `deleteNetworkNode`, `findCommonNetworks`
|
||
**Complexity:** O(N) per call where N = nodes per network; O(N²) total across cluster join storm
|
||
**Severity:** MEDIUM
|
||
**Fix:** Change `networkNodes map[string][]string` → `map[string]map[string]struct{}`
|
||
|
||
## Pattern
|
||
|
||
```go
|
||
// DEFECT: O(N) membership check on every gossip event
|
||
func (nDB *NetworkDB) addNetworkNode(nid string, nodeName string) {
|
||
if slices.Contains(nDB.networkNodes[nid], nodeName) { // O(N) scan
|
||
return
|
||
}
|
||
nDB.networkNodes[nid] = append(nDB.networkNodes[nid], nodeName)
|
||
...
|
||
}
|
||
|
||
// DEFECT: O(N) delete — rebuilds entire slice
|
||
func (nDB *NetworkDB) deleteNetworkNode(nid string, nodeName string) {
|
||
nodes, ok := nDB.networkNodes[nid]
|
||
...
|
||
newNodes := make([]string, 0, len(nodes)-1)
|
||
for _, name := range nodes { // O(N) scan
|
||
if name == nodeName { continue }
|
||
newNodes = append(newNodes, name)
|
||
}
|
||
nDB.networkNodes[nid] = newNodes
|
||
}
|
||
|
||
// DEFECT: O(N) per-network scan in findCommonNetworks
|
||
for nid, nodes := range nDB.networkNodes {
|
||
for _, name := range nodes { // O(N) inner loop
|
||
if name == nodeName {
|
||
networks = append(networks, nid)
|
||
break
|
||
}
|
||
}
|
||
}
|
||
```
|
||
|
||
## Fix
|
||
|
||
```go
|
||
// Type change: map[string][]string → map[string]map[string]struct{}
|
||
networkNodes map[string]map[string]struct{}
|
||
|
||
// addNetworkNode: O(1)
|
||
func (nDB *NetworkDB) addNetworkNode(nid string, nodeName string) {
|
||
if nDB.networkNodes[nid] == nil {
|
||
nDB.networkNodes[nid] = make(map[string]struct{})
|
||
}
|
||
nDB.networkNodes[nid][nodeName] = struct{}{}
|
||
if n, ok := nDB.thisNodeNetworks[nid]; ok {
|
||
n.networkNodes.Store(int32(len(nDB.networkNodes[nid])))
|
||
}
|
||
}
|
||
|
||
// deleteNetworkNode: O(1)
|
||
func (nDB *NetworkDB) deleteNetworkNode(nid string, nodeName string) {
|
||
nodes, ok := nDB.networkNodes[nid]
|
||
if !ok || len(nodes) == 0 { return }
|
||
delete(nDB.networkNodes[nid], nodeName)
|
||
if n, ok := nDB.thisNodeNetworks[nid]; ok {
|
||
n.networkNodes.Store(int32(len(nDB.networkNodes[nid])))
|
||
}
|
||
}
|
||
|
||
// findCommonNetworks: O(M) instead of O(N×M)
|
||
for nid, nodes := range nDB.networkNodes {
|
||
if _, ok := nodes[nodeName]; ok {
|
||
networks = append(networks, nid)
|
||
}
|
||
}
|
||
|
||
// Peers() iteration: use maps.Keys() or range map
|
||
for nodeName := range nDB.networkNodes[nid] {
|
||
if node, ok := nDB.nodes[nodeName]; ok {
|
||
peers = append(peers, PeerInfo{...})
|
||
}
|
||
}
|
||
|
||
// bulkSync call sites: convert set to slice
|
||
nodeSlice := make([]string, 0, len(nDB.networkNodes[nid]))
|
||
for n := range nDB.networkNodes[nid] { nodeSlice = append(nodeSlice, n) }
|
||
if _, err := nDB.bulkSync(nodeSlice, true); err != nil { ... }
|
||
```
|
||
|
||
## Impact
|
||
|
||
In a Docker Swarm cluster with N nodes and M networks:
|
||
- Each node join/leave gossip event calls addNetworkNode/deleteNetworkNode
|
||
- Cluster join storm: N nodes × M networks × O(N) scan = O(N²×M)
|
||
- Fix: O(1) per event = O(N×M) total
|
||
|
||
At N=1000 nodes, M=10 networks: 10,000,000 comparisons → 10,000. **1000× overhead.**
|