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.DebugLevel, nil)
}

type RouteHop struct {
	DeviceID string
	Ingress  uint32
	Egress   uint32
}

type OFPortLink struct {
	Ingress uint32
	Egress  uint32
}

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

func concatDeviceIdPortId(deviceId string, portId uint32) string {
	return fmt.Sprintf("%s:%d", deviceId, 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
	}
}

type DeviceGraph struct {
	GGraph        goraph.Graph
	getDevice     GetDeviceFunc
	logicalPorts  []*voltha.LogicalPort
	RootPorts     map[uint32]uint32
	Routes        map[OFPortLink][]RouteHop
	graphBuildLock sync.RWMutex
	boundaryPorts sync.Map
}

func NewDeviceGraph(getDevice GetDeviceFunc) *DeviceGraph {
	var dg DeviceGraph
	dg.GGraph = goraph.NewGraph()
	dg.getDevice = getDevice
	dg.graphBuildLock = sync.RWMutex{}
	return &dg
}

func (dg *DeviceGraph) ComputeRoutes(lps []*voltha.LogicalPort) {
	if dg == nil {
		return
	}
	dg.graphBuildLock.Lock()
	defer dg.graphBuildLock.Unlock()
	dg.logicalPorts = lps
	// Set the root ports
	dg.RootPorts = make(map[uint32]uint32)
	for _, lp := range lps {
		if lp.RootPort {
			dg.RootPorts[lp.OfpPort.PortNo] = lp.OfpPort.PortNo
		}
	}
	// set the boundary ports
	dg.boundaryPorts.Range(func(key interface{}, value interface{}) bool {
		dg.boundaryPorts.Delete(key)
		return true
	})
	//dg.boundaryPorts = sync.Map{}

	for _, lp := range lps {
		dg.boundaryPorts.Store(fmt.Sprintf("%s:%d", lp.DeviceId, lp.DevicePortNo), lp.OfpPort.PortNo)
	}
	dg.Routes = make(map[OFPortLink][]RouteHop)

	// Build the graph
	var device *voltha.Device
	devicesAdded := make(map[string]string)
	portsAdded := make(map[string]string)
	for _, logicalPort := range dg.logicalPorts {
		device, _ = dg.getDevice(logicalPort.DeviceId)
		dg.GGraph = dg.addDevice(device, dg.GGraph, &devicesAdded, &portsAdded, dg.boundaryPorts)
	}
	dg.Routes = dg.buildRoutes()
}

func (dg *DeviceGraph) addDevice(device *voltha.Device, g goraph.Graph, devicesAdded *map[string]string, portsAdded *map[string]string,
	boundaryPorts sync.Map) goraph.Graph {

	if device == nil {
		return g
	}

	if _, exist := (*devicesAdded)[device.Id]; exist {
		return g
	}
	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)
				g = dg.addDevice(d, g, devicesAdded, portsAdded, boundaryPorts)
			} else {
				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
}

func (dg *DeviceGraph) IsRootPort(port uint32) bool {
	_, exist := dg.RootPorts[port]
	return exist
}

func (dg *DeviceGraph) buildRoutes() map[OFPortLink][]RouteHop {
	var pathIds []goraph.ID
	path := make([]RouteHop, 0)
	paths := make(map[OFPortLink][]RouteHop)
	var err error
	var hop RouteHop

	dg.boundaryPorts.Range(func(src, srcPort interface{}) bool {
		source := src.(string)
		sourcePort := srcPort.(uint32)

		dg.boundaryPorts.Range(func(dst, dstPort interface{}) bool {
			target := dst.(string)
			targetPort := dstPort.(uint32)

			if source == target {
				return true
			}
			//Ignore NNI - NNI Routes
			if dg.IsRootPort(sourcePort) && dg.IsRootPort(targetPort) {
				return true
			}

			//Ignore UNI - UNI Routes
			if !dg.IsRootPort(sourcePort) && !dg.IsRootPort(targetPort) {
				return true
			}

			if pathIds, _, err = goraph.Dijkstra(dg.GGraph, goraph.StringID(source), goraph.StringID(target)); err != nil {
				log.Errorw("no-path", log.Fields{"source": source, "target": target, "error": err})
				return true
			}
			if len(pathIds)%3 != 0 {
				return true
			}
			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{"source": source, "target": target, "error": err})
					break
				}
				if _, egressPort, err = splitIntoDeviceIdPortId(pathIds[i+2].String()); err != nil {
					log.Errorw("id-error", log.Fields{"source": source, "target": target, "error": err})
					break
				}
				hop = RouteHop{Ingress: ingressPort, DeviceID: deviceId, Egress: egressPort}
				path = append(path, hop)
			}
			tmp := make([]RouteHop, len(path))
			copy(tmp, path)
			path = nil
			paths[OFPortLink{Ingress: sourcePort, Egress: targetPort}] = tmp
			return true
		})
		return true
	})
	return paths
}

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
}