rw_core/graph/device_graph.go

/*
 * Copyright 2018-present Open Networking Foundation
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 * http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */

package graph

import (
	"errors"
	"fmt"
	"github.com/gyuho/goraph"
	"github.com/opencord/voltha-go/common/log"
	"github.com/opencord/voltha-protos/go/voltha"
	"strconv"
	"strings"
	"sync"
)

func init() {
	log.AddPackage(log.JSON, log.WarnLevel, nil)
}

type RouteHop struct {
	DeviceID string
	Ingress  uint32
	Egress   uint32
}

type OFPortLink struct {
	Ingress uint32
	Egress  uint32
}

type ofPortLinkToPath struct {
	link OFPortLink
	path []RouteHop
}

type GetDeviceFunc func(id string) (*voltha.Device, error)

type DeviceGraph struct {
	logicalDeviceId    string
	GGraph             goraph.Graph
	getDeviceFromModel GetDeviceFunc
	logicalPorts       []*voltha.LogicalPort
	rootPortsString    map[string]uint32
	nonRootPortsString map[string]uint32
	RootPorts          map[uint32]uint32
	rootPortsLock      sync.RWMutex
	Routes             map[OFPortLink][]RouteHop
	graphBuildLock     sync.RWMutex
	boundaryPorts      map[string]uint32
	boundaryPortsLock  sync.RWMutex
	cachedDevices      map[string]*voltha.Device
	cachedDevicesLock  sync.RWMutex
	devicesAdded       map[string]string
	portsAdded         map[string]string
}

func NewDeviceGraph(logicalDeviceId string, getDevice GetDeviceFunc) *DeviceGraph {
	var dg DeviceGraph
	dg.logicalDeviceId = logicalDeviceId
	dg.GGraph = goraph.NewGraph()
	dg.getDeviceFromModel = getDevice
	dg.graphBuildLock = sync.RWMutex{}
	dg.cachedDevicesLock = sync.RWMutex{}
	dg.rootPortsLock = sync.RWMutex{}
	dg.devicesAdded = make(map[string]string)
	dg.portsAdded = make(map[string]string)
	dg.rootPortsString = make(map[string]uint32)
	dg.nonRootPortsString = make(map[string]uint32)
	dg.RootPorts = make(map[uint32]uint32)
	dg.boundaryPorts = make(map[string]uint32)
	dg.Routes = make(map[OFPortLink][]RouteHop)
	dg.cachedDevices = make(map[string]*voltha.Device)
	log.Debug("new device graph created ...")
	return &dg
}

//IsRootPort returns true if the port is a root port on a logical device
func (dg *DeviceGraph) IsRootPort(port uint32) bool {
	dg.rootPortsLock.RLock()
	defer dg.rootPortsLock.RUnlock()
	_, exist := dg.RootPorts[port]
	return exist
}

//GetDeviceNodeIds retrieves all the nodes in the device graph
func (dg *DeviceGraph) GetDeviceNodeIds() map[string]string {
	dg.graphBuildLock.RLock()
	defer dg.graphBuildLock.RUnlock()
	nodeIds := make(map[string]string)
	nodesMap := dg.GGraph.GetNodes()
	for id, node := range nodesMap {
		if len(strings.Split(node.String(), ":")) != 2 { // not port node
			nodeIds[id.String()] = id.String()
		}
	}
	return nodeIds
}

//ComputeRoutes creates a device graph from the logical ports and then calculates all the routes
//between the logical ports.  This will clear up the graph and routes if there were any.
func (dg *DeviceGraph) ComputeRoutes(lps []*voltha.LogicalPort) {
	if dg == nil {
		return
	}
	dg.graphBuildLock.Lock()
	defer dg.graphBuildLock.Unlock()

	// Clear the graph
	dg.reset()

	dg.logicalPorts = lps

	// Set the root, non-root ports and boundary ports
	for _, lp := range lps {
		portId := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
		if lp.RootPort {
			dg.rootPortsString[portId] = lp.OfpPort.PortNo
			dg.RootPorts[lp.OfpPort.PortNo] = lp.OfpPort.PortNo
		} else {
			dg.nonRootPortsString[portId] = lp.OfpPort.PortNo
		}
		dg.boundaryPorts[portId] = lp.OfpPort.PortNo
	}

	// Build the graph
	var device *voltha.Device
	for _, logicalPort := range dg.logicalPorts {
		device, _ = dg.getDevice(logicalPort.DeviceId, false)
		dg.GGraph = dg.addDevice(device, dg.GGraph, &dg.devicesAdded, &dg.portsAdded, dg.boundaryPorts)
	}

	dg.Routes = dg.buildRoutes()
}

// AddPort adds a port to the graph.  If the graph is empty it will just invoke ComputeRoutes function
func (dg *DeviceGraph) AddPort(lp *voltha.LogicalPort) {
	log.Debugw("Addport", log.Fields{"logicalPort": lp})
	//  If the graph does not exist invoke ComputeRoutes.
	if len(dg.boundaryPorts) == 0 {
		dg.ComputeRoutes([]*voltha.LogicalPort{lp})
		return
	}

	dg.graphBuildLock.Lock()
	defer dg.graphBuildLock.Unlock()

	portId := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)

	//	If the port is already part of the boundary ports, do nothing
	if dg.portExist(portId) {
		return
	}
	// Add the port to the set of boundary ports
	dg.boundaryPorts[portId] = lp.OfpPort.PortNo

	// Add the device where this port is located to the device graph. If the device is already added then
	// only the missing port will be added
	device, _ := dg.getDevice(lp.DeviceId, false)
	dg.GGraph = dg.addDevice(device, dg.GGraph, &dg.devicesAdded, &dg.portsAdded, dg.boundaryPorts)

	if lp.RootPort {
		// Compute the route from this root port to all non-root ports
		dg.rootPortsString[portId] = lp.OfpPort.PortNo
		dg.RootPorts[lp.OfpPort.PortNo] = lp.OfpPort.PortNo
		dg.Routes = dg.buildPathsToAllNonRootPorts(lp)
	} else {
		// Compute the route from this port to all root ports
		dg.nonRootPortsString[portId] = lp.OfpPort.PortNo
		dg.Routes = dg.buildPathsToAllRootPorts(lp)
	}

	dg.Print()
}

func (dg *DeviceGraph) Print() error {
	log.Debugw("Print", log.Fields{"graph": dg.logicalDeviceId, "boundaryPorts": dg.boundaryPorts})
	if level, err := log.GetPackageLogLevel(); err == nil && level == log.DebugLevel {
		output := ""
		routeNumber := 1
		for k, v := range dg.Routes {
			key := fmt.Sprintf("LP:%d->LP:%d", k.Ingress, k.Egress)
			val := ""
			for _, i := range v {
				val += fmt.Sprintf("{%d->%s->%d},", i.Ingress, i.DeviceID, i.Egress)
			}
			val = val[:len(val)-1]
			output += fmt.Sprintf("%d:{%s=>%s}   ", routeNumber, key, fmt.Sprintf("[%s]", val))
			routeNumber += 1
		}
		if len(dg.Routes) == 0 {
			log.Debugw("no-routes-found", log.Fields{"lDeviceId": dg.logicalDeviceId, "Graph": dg.GGraph.String()})
		} else {
			log.Debugw("graph_routes", log.Fields{"lDeviceId": dg.logicalDeviceId, "Routes": output})
		}
	}
	return nil
}

//getDevice returns the device either from the local cache (default) or from the model.
//TODO: Set a cache timeout such that we do not use invalid data.  The full device lifecycle should also
//be taken in consideration
func (dg *DeviceGraph) getDevice(id string, useCache bool) (*voltha.Device, error) {
	if useCache {
		dg.cachedDevicesLock.RLock()
		if d, exist := dg.cachedDevices[id]; exist {
			dg.cachedDevicesLock.RUnlock()
			//log.Debugw("getDevice - returned from cache", log.Fields{"deviceId": id})
			return d, nil
		}
		dg.cachedDevicesLock.RUnlock()
	}
	//	Not cached
	if d, err := dg.getDeviceFromModel(id); err != nil {
		log.Errorw("device-not-found", log.Fields{"deviceId": id, "error": err})
		return nil, err
	} else { // cache it
		dg.cachedDevicesLock.Lock()
		dg.cachedDevices[id] = d
		dg.cachedDevicesLock.Unlock()
		//log.Debugw("getDevice - returned from model", log.Fields{"deviceId": id})
		return d, nil
	}
}

// addDevice adds a device to a device graph and setup edges that represent the device connections to its peers
func (dg *DeviceGraph) addDevice(device *voltha.Device, g goraph.Graph, devicesAdded *map[string]string, portsAdded *map[string]string,
	boundaryPorts map[string]uint32) goraph.Graph {

	if device == nil {
		return g
	}

	if _, exist := (*devicesAdded)[device.Id]; !exist {
		g.AddNode(goraph.NewNode(device.Id))
		(*devicesAdded)[device.Id] = device.Id
	}

	var portId string
	var peerPortId string
	for _, port := range device.Ports {
		portId = concatDeviceIdPortId(device.Id, port.PortNo)
		if _, exist := (*portsAdded)[portId]; !exist {
			(*portsAdded)[portId] = portId
			g.AddNode(goraph.NewNode(portId))
			g.AddEdge(goraph.StringID(device.Id), goraph.StringID(portId), 1)
			g.AddEdge(goraph.StringID(portId), goraph.StringID(device.Id), 1)
		}
		for _, peer := range port.Peers {
			if _, exist := (*devicesAdded)[peer.DeviceId]; !exist {
				d, _ := dg.getDevice(peer.DeviceId, true)
				g = dg.addDevice(d, g, devicesAdded, portsAdded, boundaryPorts)
			}
			peerPortId = concatDeviceIdPortId(peer.DeviceId, peer.PortNo)
			g.AddEdge(goraph.StringID(portId), goraph.StringID(peerPortId), 1)
			g.AddEdge(goraph.StringID(peerPortId), goraph.StringID(portId), 1)

		}
	}
	return g
}

//portExist returns true if the port ID is already part of the boundary ports map.
func (dg *DeviceGraph) portExist(id string) bool {
	dg.boundaryPortsLock.RLock()
	defer dg.boundaryPortsLock.RUnlock()
	_, exist := dg.boundaryPorts[id]
	return exist
}

// buildPathsToAllRootPorts builds all the paths from the non-root logical port to all root ports
// on the logical device
func (dg *DeviceGraph) buildPathsToAllRootPorts(lp *voltha.LogicalPort) map[OFPortLink][]RouteHop {
	paths := dg.Routes
	source := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
	sourcePort := lp.OfpPort.PortNo
	ch := make(chan *ofPortLinkToPath)
	numBuildRequest := 0
	for target, targetPort := range dg.rootPortsString {
		go dg.buildRoute(source, target, sourcePort, targetPort, ch)
		numBuildRequest += 1
	}
	responseReceived := 0
forloop:
	for {
		if responseReceived == numBuildRequest {
			break
		}
		select {
		case res, ok := <-ch:
			if !ok {
				log.Debug("channel closed")
				break forloop
			}
			if res != nil && len(res.path) > 0 {
				paths[res.link] = res.path
				paths[OFPortLink{Ingress: res.link.Egress, Egress: res.link.Ingress}] = getReverseRoute(res.path)
			}
		}
		responseReceived += 1
	}
	return paths
}

// buildPathsToAllNonRootPorts builds all the paths from the root logical port to all non-root ports
// on the logical device
func (dg *DeviceGraph) buildPathsToAllNonRootPorts(lp *voltha.LogicalPort) map[OFPortLink][]RouteHop {
	paths := dg.Routes
	source := concatDeviceIdPortId(lp.DeviceId, lp.DevicePortNo)
	sourcePort := lp.OfpPort.PortNo
	ch := make(chan *ofPortLinkToPath)
	numBuildRequest := 0
	for target, targetPort := range dg.nonRootPortsString {
		go dg.buildRoute(source, target, sourcePort, targetPort, ch)
		numBuildRequest += 1
	}
	responseReceived := 0
forloop:
	for {
		if responseReceived == numBuildRequest {
			break
		}
		select {
		case res, ok := <-ch:
			if !ok {
				log.Debug("channel closed")
				break forloop
			}
			if res != nil && len(res.path) > 0 {
				paths[res.link] = res.path
				paths[OFPortLink{Ingress: res.link.Egress, Egress: res.link.Ingress}] = getReverseRoute(res.path)
			}
		}
		responseReceived += 1
	}
	return paths
}

//buildRoute builds a route between a source and a target logical port
func (dg *DeviceGraph) buildRoute(sourceId, targetId string, sourcePort, targetPort uint32, ch chan *ofPortLinkToPath) {
	var pathIds []goraph.ID
	path := make([]RouteHop, 0)
	var err error
	var hop RouteHop
	var result *ofPortLinkToPath

	if sourceId == targetId {
		ch <- result
		return
	}
	//Ignore Root - Root Routes
	if dg.IsRootPort(sourcePort) && dg.IsRootPort(targetPort) {
		ch <- result
		return
	}

	//Ignore non-Root - non-Root Routes
	if !dg.IsRootPort(sourcePort) && !dg.IsRootPort(targetPort) {
		ch <- result
		return
	}

	if pathIds, _, err = goraph.Dijkstra(dg.GGraph, goraph.StringID(sourceId), goraph.StringID(targetId)); err != nil {
		log.Errorw("no-path", log.Fields{"sourceId": sourceId, "targetId": targetId, "error": err})
		ch <- result
		return
	}
	if len(pathIds)%3 != 0 {
		ch <- result
		return
	}
	var deviceId string
	var ingressPort uint32
	var egressPort uint32
	for i := 0; i < len(pathIds); i = i + 3 {
		if deviceId, ingressPort, err = splitIntoDeviceIdPortId(pathIds[i].String()); err != nil {
			log.Errorw("id-error", log.Fields{"sourceId": sourceId, "targetId": targetId, "error": err})
			break
		}
		if _, egressPort, err = splitIntoDeviceIdPortId(pathIds[i+2].String()); err != nil {
			log.Errorw("id-error", log.Fields{"sourceId": sourceId, "targetId": targetId, "error": err})
			break
		}
		hop = RouteHop{Ingress: ingressPort, DeviceID: deviceId, Egress: egressPort}
		path = append(path, hop)
	}
	result = &ofPortLinkToPath{link: OFPortLink{Ingress: sourcePort, Egress: targetPort}, path: path}
	ch <- result
}

//buildRoutes build all routes between all the ports on the logical device
func (dg *DeviceGraph) buildRoutes() map[OFPortLink][]RouteHop {
	paths := make(map[OFPortLink][]RouteHop)
	ch := make(chan *ofPortLinkToPath)
	numBuildRequest := 0
	for source, sourcePort := range dg.boundaryPorts {
		for target, targetPort := range dg.boundaryPorts {
			go dg.buildRoute(source, target, sourcePort, targetPort, ch)
			numBuildRequest += 1
		}
	}
	responseReceived := 0
forloop:
	for {
		if responseReceived == numBuildRequest {
			break
		}
		select {
		case res, ok := <-ch:
			if !ok {
				log.Debug("channel closed")
				break forloop
			}
			if res != nil && len(res.path) > 0 {
				paths[res.link] = res.path
			}
		}
		responseReceived += 1
	}
	return paths
}

// reset cleans up the device graph
func (dg *DeviceGraph) reset() {
	dg.devicesAdded = make(map[string]string)
	dg.portsAdded = make(map[string]string)
	dg.rootPortsString = make(map[string]uint32)
	dg.nonRootPortsString = make(map[string]uint32)
	dg.RootPorts = make(map[uint32]uint32)
	dg.boundaryPorts = make(map[string]uint32)
	dg.Routes = make(map[OFPortLink][]RouteHop)
	dg.cachedDevices = make(map[string]*voltha.Device)
}

//concatDeviceIdPortId formats a portid using the device id and the port number
func concatDeviceIdPortId(deviceId string, portNo uint32) string {
	return fmt.Sprintf("%s:%d", deviceId, portNo)
}

// splitIntoDeviceIdPortId extracts the device id and port number from the portId
func splitIntoDeviceIdPortId(id string) (string, uint32, error) {
	result := strings.Split(id, ":")
	if len(result) != 2 {
		return "", 0, errors.New(fmt.Sprintf("invalid-id-%s", id))
	}
	if temp, err := strconv.ParseInt(result[1], 10, 32); err != nil {
		return "", 0, errors.New(fmt.Sprintf("invalid-id-%s-%s", id, err.Error()))
	} else {
		return result[0], uint32(temp), nil
	}
}

//getReverseRoute returns the reverse of the route in param
func getReverseRoute(route []RouteHop) []RouteHop {
	reverse := make([]RouteHop, len(route))
	for i, j := 0, len(route)-1; i < j; i, j = i+1, j-1 {
		reverse[i], reverse[j] = route[j], route[i]
	}
	return reverse
}