blob: 5bfaf96636f516cac33e78eae2eda4985c7112f6 [file] [log] [blame]
khenaidoo89b0e942018-10-21 21:11:33 -04001/*
2 * Copyright 2018-present Open Networking Foundation
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17package graph
18
19import (
20 "errors"
21 "fmt"
22 "github.com/gyuho/goraph"
Scott Bakercb7c88a2019-10-16 18:32:48 -070023 "github.com/opencord/voltha-lib-go/pkg/log"
William Kurkiandaa6bb22019-03-07 12:26:28 -050024 "github.com/opencord/voltha-protos/go/voltha"
khenaidoo89b0e942018-10-21 21:11:33 -040025 "strconv"
26 "strings"
Stephane Barbariec53a2752019-03-08 17:50:10 -050027 "sync"
khenaidoo89b0e942018-10-21 21:11:33 -040028)
29
30func init() {
khenaidoo910204f2019-04-08 17:56:40 -040031 log.AddPackage(log.JSON, log.WarnLevel, nil)
khenaidoo89b0e942018-10-21 21:11:33 -040032}
33
34type RouteHop struct {
35 DeviceID string
36 Ingress uint32
37 Egress uint32
38}
39
40type OFPortLink struct {
41 Ingress uint32
42 Egress uint32
43}
44
khenaidoo910204f2019-04-08 17:56:40 -040045type ofPortLinkToPath struct {
46 link OFPortLink
47 path []RouteHop
48}
49
khenaidoo89b0e942018-10-21 21:11:33 -040050type GetDeviceFunc func(id string) (*voltha.Device, error)
51
khenaidoo89b0e942018-10-21 21:11:33 -040052type DeviceGraph struct {
khenaidoo910204f2019-04-08 17:56:40 -040053 logicalDeviceId string
54 GGraph goraph.Graph
55 getDeviceFromModel GetDeviceFunc
56 logicalPorts []*voltha.LogicalPort
57 rootPortsString map[string]uint32
58 nonRootPortsString map[string]uint32
59 RootPorts map[uint32]uint32
60 rootPortsLock sync.RWMutex
61 Routes map[OFPortLink][]RouteHop
62 graphBuildLock sync.RWMutex
63 boundaryPorts map[string]uint32
64 boundaryPortsLock sync.RWMutex
65 cachedDevices map[string]*voltha.Device
66 cachedDevicesLock sync.RWMutex
67 devicesAdded map[string]string
68 portsAdded map[string]string
khenaidoo89b0e942018-10-21 21:11:33 -040069}
70
khenaidoo910204f2019-04-08 17:56:40 -040071func NewDeviceGraph(logicalDeviceId string, getDevice GetDeviceFunc) *DeviceGraph {
khenaidoo89b0e942018-10-21 21:11:33 -040072 var dg DeviceGraph
khenaidoo910204f2019-04-08 17:56:40 -040073 dg.logicalDeviceId = logicalDeviceId
khenaidoo89b0e942018-10-21 21:11:33 -040074 dg.GGraph = goraph.NewGraph()
khenaidoo910204f2019-04-08 17:56:40 -040075 dg.getDeviceFromModel = getDevice
khenaidoo1ce37ad2019-03-24 22:07:24 -040076 dg.graphBuildLock = sync.RWMutex{}
khenaidoo910204f2019-04-08 17:56:40 -040077 dg.cachedDevicesLock = sync.RWMutex{}
78 dg.rootPortsLock = sync.RWMutex{}
79 dg.devicesAdded = make(map[string]string)
80 dg.portsAdded = make(map[string]string)
81 dg.rootPortsString = make(map[string]uint32)
82 dg.nonRootPortsString = make(map[string]uint32)
83 dg.RootPorts = make(map[uint32]uint32)
84 dg.boundaryPorts = make(map[string]uint32)
85 dg.Routes = make(map[OFPortLink][]RouteHop)
86 dg.cachedDevices = make(map[string]*voltha.Device)
87 log.Debug("new device graph created ...")
khenaidoo89b0e942018-10-21 21:11:33 -040088 return &dg
89}
90
khenaidoo910204f2019-04-08 17:56:40 -040091//IsRootPort returns true if the port is a root port on a logical device
92func (dg *DeviceGraph) IsRootPort(port uint32) bool {
93 dg.rootPortsLock.RLock()
94 defer dg.rootPortsLock.RUnlock()
95 _, exist := dg.RootPorts[port]
96 return exist
97}
98
99//GetDeviceNodeIds retrieves all the nodes in the device graph
100func (dg *DeviceGraph) GetDeviceNodeIds() map[string]string {
101 dg.graphBuildLock.RLock()
102 defer dg.graphBuildLock.RUnlock()
103 nodeIds := make(map[string]string)
104 nodesMap := dg.GGraph.GetNodes()
105 for id, node := range nodesMap {
106 if len(strings.Split(node.String(), ":")) != 2 { // not port node
107 nodeIds[id.String()] = id.String()
108 }
109 }
110 return nodeIds
111}
112
113//ComputeRoutes creates a device graph from the logical ports and then calculates all the routes
114//between the logical ports. This will clear up the graph and routes if there were any.
khenaidoo89b0e942018-10-21 21:11:33 -0400115func (dg *DeviceGraph) ComputeRoutes(lps []*voltha.LogicalPort) {
Stephane Barbariec53a2752019-03-08 17:50:10 -0500116 if dg == nil {
117 return
118 }
khenaidoo1ce37ad2019-03-24 22:07:24 -0400119 dg.graphBuildLock.Lock()
120 defer dg.graphBuildLock.Unlock()
Stephane Barbariec53a2752019-03-08 17:50:10 -0500121
khenaidoo910204f2019-04-08 17:56:40 -0400122 // Clear the graph
123 dg.reset()
124
125 dg.logicalPorts = lps
126
127 // Set the root, non-root ports and boundary ports
khenaidoo89b0e942018-10-21 21:11:33 -0400128 for _, lp := range lps {
khenaidoo910204f2019-04-08 17:56:40 -0400129 portId := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
130 if lp.RootPort {
131 dg.rootPortsString[portId] = lp.OfpPort.PortNo
132 dg.RootPorts[lp.OfpPort.PortNo] = lp.OfpPort.PortNo
133 } else {
134 dg.nonRootPortsString[portId] = lp.OfpPort.PortNo
135 }
136 dg.boundaryPorts[portId] = lp.OfpPort.PortNo
khenaidoo89b0e942018-10-21 21:11:33 -0400137 }
khenaidoo89b0e942018-10-21 21:11:33 -0400138
139 // Build the graph
140 var device *voltha.Device
khenaidoo89b0e942018-10-21 21:11:33 -0400141 for _, logicalPort := range dg.logicalPorts {
khenaidoo2c6a0992019-04-29 13:46:56 -0400142 device, _ = dg.getDevice(logicalPort.DeviceId, false)
khenaidoo910204f2019-04-08 17:56:40 -0400143 dg.GGraph = dg.addDevice(device, dg.GGraph, &dg.devicesAdded, &dg.portsAdded, dg.boundaryPorts)
khenaidoo89b0e942018-10-21 21:11:33 -0400144 }
khenaidoo910204f2019-04-08 17:56:40 -0400145
khenaidoo89b0e942018-10-21 21:11:33 -0400146 dg.Routes = dg.buildRoutes()
147}
148
khenaidoo910204f2019-04-08 17:56:40 -0400149// AddPort adds a port to the graph. If the graph is empty it will just invoke ComputeRoutes function
150func (dg *DeviceGraph) AddPort(lp *voltha.LogicalPort) {
khenaidoo2c6a0992019-04-29 13:46:56 -0400151 log.Debugw("Addport", log.Fields{"logicalPort": lp})
khenaidoo910204f2019-04-08 17:56:40 -0400152 // If the graph does not exist invoke ComputeRoutes.
153 if len(dg.boundaryPorts) == 0 {
154 dg.ComputeRoutes([]*voltha.LogicalPort{lp})
155 return
156 }
157
158 dg.graphBuildLock.Lock()
159 defer dg.graphBuildLock.Unlock()
160
161 portId := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
162
163 // If the port is already part of the boundary ports, do nothing
164 if dg.portExist(portId) {
khenaidoo910204f2019-04-08 17:56:40 -0400165 return
166 }
khenaidoo2c6a0992019-04-29 13:46:56 -0400167 // Add the port to the set of boundary ports
168 dg.boundaryPorts[portId] = lp.OfpPort.PortNo
169
khenaidoo910204f2019-04-08 17:56:40 -0400170 // Add the device where this port is located to the device graph. If the device is already added then
171 // only the missing port will be added
khenaidoo2c6a0992019-04-29 13:46:56 -0400172 device, _ := dg.getDevice(lp.DeviceId, false)
khenaidoo910204f2019-04-08 17:56:40 -0400173 dg.GGraph = dg.addDevice(device, dg.GGraph, &dg.devicesAdded, &dg.portsAdded, dg.boundaryPorts)
174
175 if lp.RootPort {
176 // Compute the route from this root port to all non-root ports
177 dg.rootPortsString[portId] = lp.OfpPort.PortNo
178 dg.RootPorts[lp.OfpPort.PortNo] = lp.OfpPort.PortNo
179 dg.Routes = dg.buildPathsToAllNonRootPorts(lp)
180 } else {
181 // Compute the route from this port to all root ports
182 dg.nonRootPortsString[portId] = lp.OfpPort.PortNo
183 dg.Routes = dg.buildPathsToAllRootPorts(lp)
184 }
185
186 dg.Print()
187}
188
189func (dg *DeviceGraph) Print() error {
khenaidoo2c6a0992019-04-29 13:46:56 -0400190 log.Debugw("Print", log.Fields{"graph": dg.logicalDeviceId, "boundaryPorts": dg.boundaryPorts})
khenaidoo910204f2019-04-08 17:56:40 -0400191 if level, err := log.GetPackageLogLevel(); err == nil && level == log.DebugLevel {
192 output := ""
193 routeNumber := 1
194 for k, v := range dg.Routes {
195 key := fmt.Sprintf("LP:%d->LP:%d", k.Ingress, k.Egress)
196 val := ""
197 for _, i := range v {
198 val += fmt.Sprintf("{%d->%s->%d},", i.Ingress, i.DeviceID, i.Egress)
199 }
200 val = val[:len(val)-1]
201 output += fmt.Sprintf("%d:{%s=>%s} ", routeNumber, key, fmt.Sprintf("[%s]", val))
202 routeNumber += 1
203 }
khenaidoo2c6a0992019-04-29 13:46:56 -0400204 if len(dg.Routes) == 0 {
205 log.Debugw("no-routes-found", log.Fields{"lDeviceId": dg.logicalDeviceId, "Graph": dg.GGraph.String()})
206 } else {
207 log.Debugw("graph_routes", log.Fields{"lDeviceId": dg.logicalDeviceId, "Routes": output})
208 }
khenaidoo910204f2019-04-08 17:56:40 -0400209 }
210 return nil
211}
212
khenaidoo4c9e5592019-09-09 16:20:41 -0400213func (dg *DeviceGraph) IsUpToDate(ld *voltha.LogicalDevice) bool {
214 if ld != nil {
215 if len(dg.boundaryPorts) != len(ld.Ports) {
216 return false
217 }
218 var portId string
219 var val uint32
220 var exist bool
221 for _, lp := range ld.Ports {
222 portId = concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
223 if val, exist = dg.boundaryPorts[portId]; !exist || val != lp.OfpPort.PortNo {
224 return false
225 }
226 }
227 return true
228 }
229 return len(dg.boundaryPorts) == 0
230}
231
khenaidoo910204f2019-04-08 17:56:40 -0400232//getDevice returns the device either from the local cache (default) or from the model.
233//TODO: Set a cache timeout such that we do not use invalid data. The full device lifecycle should also
234//be taken in consideration
khenaidoo2c6a0992019-04-29 13:46:56 -0400235func (dg *DeviceGraph) getDevice(id string, useCache bool) (*voltha.Device, error) {
236 if useCache {
237 dg.cachedDevicesLock.RLock()
238 if d, exist := dg.cachedDevices[id]; exist {
239 dg.cachedDevicesLock.RUnlock()
240 //log.Debugw("getDevice - returned from cache", log.Fields{"deviceId": id})
241 return d, nil
242 }
khenaidoo910204f2019-04-08 17:56:40 -0400243 dg.cachedDevicesLock.RUnlock()
khenaidoo910204f2019-04-08 17:56:40 -0400244 }
khenaidoo910204f2019-04-08 17:56:40 -0400245 // Not cached
246 if d, err := dg.getDeviceFromModel(id); err != nil {
247 log.Errorw("device-not-found", log.Fields{"deviceId": id, "error": err})
248 return nil, err
249 } else { // cache it
250 dg.cachedDevicesLock.Lock()
251 dg.cachedDevices[id] = d
252 dg.cachedDevicesLock.Unlock()
253 //log.Debugw("getDevice - returned from model", log.Fields{"deviceId": id})
254 return d, nil
255 }
256}
257
258// addDevice adds a device to a device graph and setup edges that represent the device connections to its peers
khenaidoo89b0e942018-10-21 21:11:33 -0400259func (dg *DeviceGraph) addDevice(device *voltha.Device, g goraph.Graph, devicesAdded *map[string]string, portsAdded *map[string]string,
khenaidoo910204f2019-04-08 17:56:40 -0400260 boundaryPorts map[string]uint32) goraph.Graph {
khenaidoo89b0e942018-10-21 21:11:33 -0400261
262 if device == nil {
263 return g
264 }
265
khenaidoo3d3b8c22019-05-22 18:10:39 -0400266 log.Debugw("Adding-device", log.Fields{"deviceId": device.Id, "ports": device.Ports})
267
khenaidoo910204f2019-04-08 17:56:40 -0400268 if _, exist := (*devicesAdded)[device.Id]; !exist {
269 g.AddNode(goraph.NewNode(device.Id))
270 (*devicesAdded)[device.Id] = device.Id
khenaidoo89b0e942018-10-21 21:11:33 -0400271 }
khenaidoo89b0e942018-10-21 21:11:33 -0400272
273 var portId string
274 var peerPortId string
275 for _, port := range device.Ports {
276 portId = concatDeviceIdPortId(device.Id, port.PortNo)
277 if _, exist := (*portsAdded)[portId]; !exist {
278 (*portsAdded)[portId] = portId
279 g.AddNode(goraph.NewNode(portId))
280 g.AddEdge(goraph.StringID(device.Id), goraph.StringID(portId), 1)
281 g.AddEdge(goraph.StringID(portId), goraph.StringID(device.Id), 1)
282 }
283 for _, peer := range port.Peers {
284 if _, exist := (*devicesAdded)[peer.DeviceId]; !exist {
khenaidoo2c6a0992019-04-29 13:46:56 -0400285 d, _ := dg.getDevice(peer.DeviceId, true)
khenaidoo89b0e942018-10-21 21:11:33 -0400286 g = dg.addDevice(d, g, devicesAdded, portsAdded, boundaryPorts)
khenaidoo89b0e942018-10-21 21:11:33 -0400287 }
khenaidoo2c6a0992019-04-29 13:46:56 -0400288 peerPortId = concatDeviceIdPortId(peer.DeviceId, peer.PortNo)
289 g.AddEdge(goraph.StringID(portId), goraph.StringID(peerPortId), 1)
290 g.AddEdge(goraph.StringID(peerPortId), goraph.StringID(portId), 1)
291
khenaidoo89b0e942018-10-21 21:11:33 -0400292 }
293 }
294 return g
295}
296
khenaidoo910204f2019-04-08 17:56:40 -0400297//portExist returns true if the port ID is already part of the boundary ports map.
298func (dg *DeviceGraph) portExist(id string) bool {
299 dg.boundaryPortsLock.RLock()
300 defer dg.boundaryPortsLock.RUnlock()
301 _, exist := dg.boundaryPorts[id]
khenaidoo89b0e942018-10-21 21:11:33 -0400302 return exist
303}
304
khenaidoo910204f2019-04-08 17:56:40 -0400305// buildPathsToAllRootPorts builds all the paths from the non-root logical port to all root ports
306// on the logical device
307func (dg *DeviceGraph) buildPathsToAllRootPorts(lp *voltha.LogicalPort) map[OFPortLink][]RouteHop {
308 paths := dg.Routes
309 source := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
310 sourcePort := lp.OfpPort.PortNo
311 ch := make(chan *ofPortLinkToPath)
312 numBuildRequest := 0
313 for target, targetPort := range dg.rootPortsString {
314 go dg.buildRoute(source, target, sourcePort, targetPort, ch)
315 numBuildRequest += 1
316 }
317 responseReceived := 0
318forloop:
319 for {
320 if responseReceived == numBuildRequest {
321 break
322 }
323 select {
324 case res, ok := <-ch:
325 if !ok {
326 log.Debug("channel closed")
327 break forloop
khenaidoo89b0e942018-10-21 21:11:33 -0400328 }
khenaidoo910204f2019-04-08 17:56:40 -0400329 if res != nil && len(res.path) > 0 {
330 paths[res.link] = res.path
331 paths[OFPortLink{Ingress: res.link.Egress, Egress: res.link.Ingress}] = getReverseRoute(res.path)
khenaidoo89b0e942018-10-21 21:11:33 -0400332 }
khenaidoo910204f2019-04-08 17:56:40 -0400333 }
334 responseReceived += 1
335 }
khenaidoo89b0e942018-10-21 21:11:33 -0400336 return paths
337}
338
khenaidoo910204f2019-04-08 17:56:40 -0400339// buildPathsToAllNonRootPorts builds all the paths from the root logical port to all non-root ports
340// on the logical device
341func (dg *DeviceGraph) buildPathsToAllNonRootPorts(lp *voltha.LogicalPort) map[OFPortLink][]RouteHop {
342 paths := dg.Routes
343 source := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
344 sourcePort := lp.OfpPort.PortNo
345 ch := make(chan *ofPortLinkToPath)
346 numBuildRequest := 0
347 for target, targetPort := range dg.nonRootPortsString {
348 go dg.buildRoute(source, target, sourcePort, targetPort, ch)
349 numBuildRequest += 1
350 }
351 responseReceived := 0
352forloop:
353 for {
354 if responseReceived == numBuildRequest {
355 break
356 }
357 select {
358 case res, ok := <-ch:
359 if !ok {
360 log.Debug("channel closed")
361 break forloop
362 }
363 if res != nil && len(res.path) > 0 {
364 paths[res.link] = res.path
365 paths[OFPortLink{Ingress: res.link.Egress, Egress: res.link.Ingress}] = getReverseRoute(res.path)
366 }
367 }
368 responseReceived += 1
369 }
370 return paths
371}
372
373//buildRoute builds a route between a source and a target logical port
374func (dg *DeviceGraph) buildRoute(sourceId, targetId string, sourcePort, targetPort uint32, ch chan *ofPortLinkToPath) {
375 var pathIds []goraph.ID
376 path := make([]RouteHop, 0)
377 var err error
378 var hop RouteHop
379 var result *ofPortLinkToPath
380
381 if sourceId == targetId {
382 ch <- result
383 return
384 }
385 //Ignore Root - Root Routes
386 if dg.IsRootPort(sourcePort) && dg.IsRootPort(targetPort) {
387 ch <- result
388 return
389 }
390
391 //Ignore non-Root - non-Root Routes
392 if !dg.IsRootPort(sourcePort) && !dg.IsRootPort(targetPort) {
393 ch <- result
394 return
395 }
396
397 if pathIds, _, err = goraph.Dijkstra(dg.GGraph, goraph.StringID(sourceId), goraph.StringID(targetId)); err != nil {
398 log.Errorw("no-path", log.Fields{"sourceId": sourceId, "targetId": targetId, "error": err})
399 ch <- result
400 return
401 }
402 if len(pathIds)%3 != 0 {
403 ch <- result
404 return
405 }
406 var deviceId string
407 var ingressPort uint32
408 var egressPort uint32
409 for i := 0; i < len(pathIds); i = i + 3 {
410 if deviceId, ingressPort, err = splitIntoDeviceIdPortId(pathIds[i].String()); err != nil {
411 log.Errorw("id-error", log.Fields{"sourceId": sourceId, "targetId": targetId, "error": err})
412 break
413 }
414 if _, egressPort, err = splitIntoDeviceIdPortId(pathIds[i+2].String()); err != nil {
415 log.Errorw("id-error", log.Fields{"sourceId": sourceId, "targetId": targetId, "error": err})
416 break
417 }
418 hop = RouteHop{Ingress: ingressPort, DeviceID: deviceId, Egress: egressPort}
419 path = append(path, hop)
420 }
421 result = &ofPortLinkToPath{link: OFPortLink{Ingress: sourcePort, Egress: targetPort}, path: path}
422 ch <- result
423}
424
425//buildRoutes build all routes between all the ports on the logical device
426func (dg *DeviceGraph) buildRoutes() map[OFPortLink][]RouteHop {
427 paths := make(map[OFPortLink][]RouteHop)
428 ch := make(chan *ofPortLinkToPath)
429 numBuildRequest := 0
430 for source, sourcePort := range dg.boundaryPorts {
431 for target, targetPort := range dg.boundaryPorts {
432 go dg.buildRoute(source, target, sourcePort, targetPort, ch)
433 numBuildRequest += 1
khenaidoo89b0e942018-10-21 21:11:33 -0400434 }
435 }
khenaidoo910204f2019-04-08 17:56:40 -0400436 responseReceived := 0
437forloop:
438 for {
439 if responseReceived == numBuildRequest {
440 break
441 }
442 select {
443 case res, ok := <-ch:
444 if !ok {
445 log.Debug("channel closed")
446 break forloop
447 }
448 if res != nil && len(res.path) > 0 {
449 paths[res.link] = res.path
450 }
451 }
452 responseReceived += 1
453 }
454 return paths
455}
456
457// reset cleans up the device graph
458func (dg *DeviceGraph) reset() {
459 dg.devicesAdded = make(map[string]string)
460 dg.portsAdded = make(map[string]string)
461 dg.rootPortsString = make(map[string]uint32)
462 dg.nonRootPortsString = make(map[string]uint32)
463 dg.RootPorts = make(map[uint32]uint32)
464 dg.boundaryPorts = make(map[string]uint32)
465 dg.Routes = make(map[OFPortLink][]RouteHop)
466 dg.cachedDevices = make(map[string]*voltha.Device)
467}
468
469//concatDeviceIdPortId formats a portid using the device id and the port number
470func concatDeviceIdPortId(deviceId string, portNo uint32) string {
471 return fmt.Sprintf("%s:%d", deviceId, portNo)
472}
473
474// splitIntoDeviceIdPortId extracts the device id and port number from the portId
475func splitIntoDeviceIdPortId(id string) (string, uint32, error) {
476 result := strings.Split(id, ":")
477 if len(result) != 2 {
478 return "", 0, errors.New(fmt.Sprintf("invalid-id-%s", id))
479 }
480 if temp, err := strconv.ParseInt(result[1], 10, 32); err != nil {
481 return "", 0, errors.New(fmt.Sprintf("invalid-id-%s-%s", id, err.Error()))
482 } else {
483 return result[0], uint32(temp), nil
484 }
485}
486
khenaidoocfe03b92019-06-03 20:06:31 -0400487//getReverseRoute returns the reverse of the route
khenaidoo910204f2019-04-08 17:56:40 -0400488func getReverseRoute(route []RouteHop) []RouteHop {
489 reverse := make([]RouteHop, len(route))
khenaidoocfe03b92019-06-03 20:06:31 -0400490 for i, j := 0, len(route)-1; j >= 0; i, j = i+1, j-1 {
491 reverse[i].DeviceID, reverse[i].Ingress, reverse[i].Egress = route[j].DeviceID, route[j].Egress, route[j].Ingress
khenaidoo910204f2019-04-08 17:56:40 -0400492 }
493 return reverse
khenaidoo89b0e942018-10-21 21:11:33 -0400494}