apps/segmentrouting/src/main/java/org/onosproject/segmentrouting/DefaultRoutingHandler.java

/*
 * Copyright 2015-present Open Networking Laboratory
 *
 * 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 org.onosproject.segmentrouting;

import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import org.onlab.packet.Ip4Address;
import org.onlab.packet.Ip4Prefix;
import org.onlab.packet.IpPrefix;
import org.onosproject.net.ConnectPoint;
import org.onosproject.net.Device;
import org.onosproject.net.DeviceId;
import org.onosproject.net.Link;
import org.onosproject.segmentrouting.config.DeviceConfigNotFoundException;
import org.onosproject.segmentrouting.config.DeviceConfiguration;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
import java.util.concurrent.Executors;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;

import static com.google.common.base.Preconditions.checkNotNull;

/**
 * Default routing handler that is responsible for route computing and
 * routing rule population.
 */
public class DefaultRoutingHandler {
    private static final int MAX_RETRY_ATTEMPTS = 5;
    private static final String ECMPSPG_MISSING = "ECMP shortest path graph not found";
    private static Logger log = LoggerFactory.getLogger(DefaultRoutingHandler.class);

    private SegmentRoutingManager srManager;
    private RoutingRulePopulator rulePopulator;
    private HashMap<DeviceId, EcmpShortestPathGraph> currentEcmpSpgMap;
    private HashMap<DeviceId, EcmpShortestPathGraph> updatedEcmpSpgMap;
    private DeviceConfiguration config;
    private final Lock statusLock = new ReentrantLock();
    private volatile Status populationStatus;
    private ScheduledExecutorService executorService = Executors.newScheduledThreadPool(1);

    /**
     * Represents the default routing population status.
     */
    public enum Status {
        // population process is not started yet.
        IDLE,

        // population process started.
        STARTED,

        // population process was aborted due to errors, mostly for groups not
        // found.
        ABORTED,

        // population process was finished successfully.
        SUCCEEDED
    }

    /**
     * Creates a DefaultRoutingHandler object.
     *
     * @param srManager SegmentRoutingManager object
     */
    public DefaultRoutingHandler(SegmentRoutingManager srManager) {
        this.srManager = srManager;
        this.rulePopulator = checkNotNull(srManager.routingRulePopulator);
        this.config = checkNotNull(srManager.deviceConfiguration);
        this.populationStatus = Status.IDLE;
        this.currentEcmpSpgMap = Maps.newHashMap();
    }

    /**
     * Populates all routing rules to all connected routers, including default
     * routing rules, adjacency rules, and policy rules if any.
     *
     * @return true if it succeeds in populating all rules, otherwise false
     */
    public boolean populateAllRoutingRules() {

        statusLock.lock();
        try {
            populationStatus = Status.STARTED;
            rulePopulator.resetCounter();
            log.info("Starting to populate segment-routing rules");
            log.debug("populateAllRoutingRules: populationStatus is STARTED");

            for (Device sw : srManager.deviceService.getDevices()) {
                if (!srManager.mastershipService.isLocalMaster(sw.id())) {
                    log.debug("populateAllRoutingRules: skipping device {}...we are not master",
                              sw.id());
                    continue;
                }

                EcmpShortestPathGraph ecmpSpg = new EcmpShortestPathGraph(sw.id(), srManager);
                if (!populateEcmpRoutingRules(sw.id(), ecmpSpg, ImmutableSet.of())) {
                    log.debug("populateAllRoutingRules: populationStatus is ABORTED");
                    populationStatus = Status.ABORTED;
                    log.debug("Abort routing rule population");
                    return false;
                }
                currentEcmpSpgMap.put(sw.id(), ecmpSpg);

                // TODO: Set adjacency routing rule for all switches
            }

            log.debug("populateAllRoutingRules: populationStatus is SUCCEEDED");
            populationStatus = Status.SUCCEEDED;
            log.info("Completed routing rule population. Total # of rules pushed : {}",
                    rulePopulator.getCounter());
            return true;
        } finally {
            statusLock.unlock();
        }
    }

    /**
     * Populates the routing rules according to the route changes due to the link
     * failure or link add. It computes the routes changed due to the link changes and
     * repopulates the rules only for the routes.
     *
     * @param linkFail link failed, null for link added
     * @return true if it succeeds to populate all rules, false otherwise
     */
    public boolean populateRoutingRulesForLinkStatusChange(Link linkFail) {

        statusLock.lock();
        try {

            if (populationStatus == Status.STARTED) {
                log.warn("Previous rule population is not finished.");
                return true;
            }

            // Take the snapshots of the links
            updatedEcmpSpgMap = new HashMap<>();
            for (Device sw : srManager.deviceService.getDevices()) {
                if (!srManager.mastershipService.isLocalMaster(sw.id())) {
                    continue;
                }
                EcmpShortestPathGraph ecmpSpgUpdated =
                        new EcmpShortestPathGraph(sw.id(), srManager);
                updatedEcmpSpgMap.put(sw.id(), ecmpSpgUpdated);
            }

            log.info("Starts rule population from link change");

            Set<ArrayList<DeviceId>> routeChanges;
            log.trace("populateRoutingRulesForLinkStatusChange: "
                    + "populationStatus is STARTED");
            populationStatus = Status.STARTED;
            if (linkFail == null) {
                // Compare all routes of existing ECMP SPG with the new ones
                routeChanges = computeRouteChange();
            } else {
                // Compare existing ECMP SPG only with the link removed
                routeChanges = computeDamagedRoutes(linkFail);
            }

            if (routeChanges.isEmpty()) {
                log.info("No route changes for the link status change");
                log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
                populationStatus = Status.SUCCEEDED;
                return true;
            }

            if (repopulateRoutingRulesForRoutes(routeChanges)) {
                log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is SUCCEEDED");
                populationStatus = Status.SUCCEEDED;
                log.info("Complete to repopulate the rules. # of rules populated : {}",
                        rulePopulator.getCounter());
                return true;
            } else {
                log.debug("populateRoutingRulesForLinkStatusChange: populationStatus is ABORTED");
                populationStatus = Status.ABORTED;
                log.warn("Failed to repopulate the rules.");
                return false;
            }
        } finally {
            statusLock.unlock();
        }
    }

    private boolean repopulateRoutingRulesForRoutes(Set<ArrayList<DeviceId>> routes) {
        rulePopulator.resetCounter();
        HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> routesBydevice =
                new HashMap<>();
        for (ArrayList<DeviceId> link: routes) {
            // When only the source device is defined, reinstall routes to all other devices
            if (link.size() == 1) {
                log.trace("repopulateRoutingRulesForRoutes: running ECMP graph for device {}", link.get(0));
                EcmpShortestPathGraph ecmpSpg = new EcmpShortestPathGraph(link.get(0), srManager);
                if (populateEcmpRoutingRules(link.get(0), ecmpSpg, ImmutableSet.of())) {
                    log.debug("Populating flow rules from {} to all is successful",
                              link.get(0));
                    currentEcmpSpgMap.put(link.get(0), ecmpSpg);
                } else {
                    log.warn("Failed to populate the flow rules from {} to all", link.get(0));
                    return false;
                }
            } else {
                ArrayList<ArrayList<DeviceId>> deviceRoutes =
                        routesBydevice.get(link.get(1));
                if (deviceRoutes == null) {
                    deviceRoutes = new ArrayList<>();
                    routesBydevice.put(link.get(1), deviceRoutes);
                }
                deviceRoutes.add(link);
            }
        }

        for (DeviceId impactedDevice : routesBydevice.keySet()) {
            ArrayList<ArrayList<DeviceId>> deviceRoutes =
                    routesBydevice.get(impactedDevice);
            for (ArrayList<DeviceId> link: deviceRoutes) {
                log.debug("repopulate RoutingRules For Routes {} -> {}",
                          link.get(0), link.get(1));
                DeviceId src = link.get(0);
                DeviceId dst = link.get(1);
                EcmpShortestPathGraph ecmpSpg = updatedEcmpSpgMap.get(dst);
                HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
                        ecmpSpg.getAllLearnedSwitchesAndVia();
                for (Integer itrIdx : switchVia.keySet()) {
                    HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
                            switchVia.get(itrIdx);
                    for (DeviceId targetSw : swViaMap.keySet()) {
                        if (!targetSw.equals(src)) {
                            continue;
                        }
                        Set<DeviceId> nextHops = new HashSet<>();
                        for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
                            if (via.isEmpty()) {
                                nextHops.add(dst);
                            } else {
                                nextHops.add(via.get(0));
                            }
                        }
                        if (!populateEcmpRoutingRulePartial(targetSw, dst,
                                nextHops, ImmutableSet.of())) {
                            return false;
                        }
                        log.debug("Populating flow rules from {} to {} is successful",
                                  targetSw, dst);
                    }
                }
                //currentEcmpSpgMap.put(dst, ecmpSpg);
            }
            //Only if all the flows for all impacted routes to a
            //specific target are pushed successfully, update the
            //ECMP graph for that target. (Or else the next event
            //would not see any changes in the ECMP graphs)
            currentEcmpSpgMap.put(impactedDevice,
                                  updatedEcmpSpgMap.get(impactedDevice));
        }
        return true;
    }

    private Set<ArrayList<DeviceId>> computeDamagedRoutes(Link linkFail) {

        Set<ArrayList<DeviceId>> routes = new HashSet<>();

        for (Device sw : srManager.deviceService.getDevices()) {
            log.debug("Computing the impacted routes for device {} due to link fail",
                      sw.id());
            if (!srManager.mastershipService.isLocalMaster(sw.id())) {
                continue;
            }
            EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
            if (ecmpSpg == null) {
                log.error("No existing ECMP graph for switch {}", sw.id());
                continue;
            }
            HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
                    ecmpSpg.getAllLearnedSwitchesAndVia();
            for (Integer itrIdx : switchVia.keySet()) {
                HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
                        switchVia.get(itrIdx);
                for (DeviceId targetSw : swViaMap.keySet()) {
                    DeviceId destSw = sw.id();
                    Set<ArrayList<DeviceId>> subLinks =
                            computeLinks(targetSw, destSw, swViaMap);
                    for (ArrayList<DeviceId> alink: subLinks) {
                        if ((alink.get(0).equals(linkFail.src().deviceId()) &&
                                alink.get(1).equals(linkFail.dst().deviceId()))
                                ||
                             (alink.get(0).equals(linkFail.dst().deviceId()) &&
                                     alink.get(1).equals(linkFail.src().deviceId()))) {
                            log.debug("Impacted route:{}->{}", targetSw, destSw);
                            ArrayList<DeviceId> aRoute = new ArrayList<>();
                            aRoute.add(targetSw);
                            aRoute.add(destSw);
                            routes.add(aRoute);
                            break;
                        }
                    }
                }
            }

        }

        return routes;
    }

    private Set<ArrayList<DeviceId>> computeRouteChange() {

        Set<ArrayList<DeviceId>> routes = new HashSet<>();

        for (Device sw : srManager.deviceService.getDevices()) {
            log.debug("Computing the impacted routes for device {}",
                      sw.id());
            if (!srManager.mastershipService.isLocalMaster(sw.id())) {
                log.debug("No mastership for {} and skip route optimization",
                          sw.id());
                continue;
            }

            log.trace("link of {} - ", sw.id());
            for (Link link: srManager.linkService.getDeviceLinks(sw.id())) {
                log.trace("{} -> {} ", link.src().deviceId(), link.dst().deviceId());
            }

            log.debug("Checking route change for switch {}", sw.id());
            EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
            if (ecmpSpg == null) {
                log.debug("No existing ECMP graph for device {}", sw.id());
                ArrayList<DeviceId> route = new ArrayList<>();
                route.add(sw.id());
                routes.add(route);
                continue;
            }
            EcmpShortestPathGraph newEcmpSpg = updatedEcmpSpgMap.get(sw.id());
            //currentEcmpSpgMap.put(sw.id(), newEcmpSpg);
            HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
                    ecmpSpg.getAllLearnedSwitchesAndVia();
            HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchViaUpdated =
                    newEcmpSpg.getAllLearnedSwitchesAndVia();

            for (Integer itrIdx : switchViaUpdated.keySet()) {
                HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMapUpdated =
                        switchViaUpdated.get(itrIdx);
                for (DeviceId srcSw : swViaMapUpdated.keySet()) {
                    ArrayList<ArrayList<DeviceId>> viaUpdated = swViaMapUpdated.get(srcSw);
                    ArrayList<ArrayList<DeviceId>> via = getVia(switchVia, srcSw);
                    if ((via == null) || !viaUpdated.equals(via)) {
                        log.debug("Impacted route:{}->{}", srcSw, sw.id());
                        ArrayList<DeviceId> route = new ArrayList<>();
                        route.add(srcSw);
                        route.add(sw.id());
                        routes.add(route);
                    }
                }
            }
        }

        for (ArrayList<DeviceId> link: routes) {
            log.trace("Route changes - ");
            if (link.size() == 1) {
                log.trace(" : {} - all", link.get(0));
            } else {
                log.trace(" : {} - {}", link.get(0), link.get(1));
            }
        }

        return routes;
    }

    private ArrayList<ArrayList<DeviceId>> getVia(HashMap<Integer, HashMap<DeviceId,
            ArrayList<ArrayList<DeviceId>>>> switchVia, DeviceId srcSw) {
        for (Integer itrIdx : switchVia.keySet()) {
            HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
                    switchVia.get(itrIdx);
            if (swViaMap.get(srcSw) == null) {
                continue;
            } else {
                return swViaMap.get(srcSw);
            }
        }

        return null;
    }

    private Set<ArrayList<DeviceId>> computeLinks(DeviceId src,
                                                  DeviceId dst,
                       HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> viaMap) {
        Set<ArrayList<DeviceId>> subLinks = Sets.newHashSet();
        for (ArrayList<DeviceId> via : viaMap.get(src)) {
            DeviceId linkSrc = src;
            DeviceId linkDst = dst;
            for (DeviceId viaDevice: via) {
                ArrayList<DeviceId> link = new ArrayList<>();
                linkDst = viaDevice;
                link.add(linkSrc);
                link.add(linkDst);
                subLinks.add(link);
                linkSrc = viaDevice;
            }
            ArrayList<DeviceId> link = new ArrayList<>();
            link.add(linkSrc);
            link.add(dst);
            subLinks.add(link);
        }

        return subLinks;
    }

    /**
     * Populate ECMP rules for subnets from all switches to destination.
     *
     * @param destSw Device ID of destination switch
     * @param ecmpSPG ECMP shortest path graph
     * @param subnets Subnets to be populated. If empty, populate all configured subnets.
     * @return true if succeed
     */
    private boolean populateEcmpRoutingRules(DeviceId destSw,
                                             EcmpShortestPathGraph ecmpSPG,
                                             Set<Ip4Prefix> subnets) {

        HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia = ecmpSPG
                .getAllLearnedSwitchesAndVia();
        for (Integer itrIdx : switchVia.keySet()) {
            HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap = switchVia
                    .get(itrIdx);
            for (DeviceId targetSw : swViaMap.keySet()) {
                Set<DeviceId> nextHops = new HashSet<>();
                log.debug("** Iter: {} root: {} target: {}", itrIdx, destSw, targetSw);
                for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
                    if (via.isEmpty()) {
                        nextHops.add(destSw);
                    } else {
                        nextHops.add(via.get(0));
                    }
                }
                if (!populateEcmpRoutingRulePartial(targetSw, destSw, nextHops, subnets)) {
                    return false;
                }
            }
        }

        return true;
    }

    /**
     * Populate ECMP rules for subnets from target to destination via nexthops.
     *
     * @param targetSw Device ID of target switch
     * @param destSw Device ID of destination switch
     * @param nextHops List of next hops
     * @param subnets Subnets to be populated. If empty, populate all configured subnets.
     * @return true if succeed
     */
    private boolean populateEcmpRoutingRulePartial(DeviceId targetSw,
                                                   DeviceId destSw,
                                                   Set<DeviceId> nextHops,
                                                   Set<Ip4Prefix> subnets) {
        boolean result;

        if (nextHops.isEmpty()) {
            nextHops.add(destSw);
        }
        // If both target switch and dest switch are edge routers, then set IP
        // rule for both subnet and router IP.
        boolean targetIsEdge;
        boolean destIsEdge;
        Ip4Address destRouterIp;

        try {
            targetIsEdge = config.isEdgeDevice(targetSw);
            destIsEdge = config.isEdgeDevice(destSw);
            destRouterIp = config.getRouterIp(destSw);
        } catch (DeviceConfigNotFoundException e) {
            log.warn(e.getMessage() + " Aborting populateEcmpRoutingRulePartial.");
            return false;
        }

        if (targetIsEdge && destIsEdge) {
            subnets = (subnets != null && !subnets.isEmpty()) ? subnets : config.getSubnets(destSw);
            log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for subnets {}",
                      targetSw, destSw, subnets);
            result = rulePopulator.populateIpRuleForSubnet(targetSw, subnets,
                                                           destSw, nextHops);
            if (!result) {
                return false;
            }

            Ip4Address routerIp = destRouterIp;
            IpPrefix routerIpPrefix = IpPrefix.valueOf(routerIp, IpPrefix.MAX_INET_MASK_LENGTH);
            log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for router IP {}",
                      targetSw, destSw, routerIpPrefix);
            result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, destSw, nextHops);
            if (!result) {
                return false;
            }

        } else if (targetIsEdge) {
            // If the target switch is an edge router, then set IP rules for the router IP.
            Ip4Address routerIp = destRouterIp;
            IpPrefix routerIpPrefix = IpPrefix.valueOf(routerIp, IpPrefix.MAX_INET_MASK_LENGTH);
            log.debug("* populateEcmpRoutingRulePartial in device {} towards {} for router IP {}",
                      targetSw, destSw, routerIpPrefix);
            result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix, destSw, nextHops);
            if (!result) {
                return false;
            }
        }
        // Populates MPLS rules to all routers
        log.debug("* populateEcmpRoutingRulePartial in device{} towards {} for all MPLS rules",
                targetSw, destSw);
        result = rulePopulator.populateMplsRule(targetSw, destSw, nextHops);
        if (!result) {
            return false;
        }
        return true;
    }

    /**
     * Populates filtering rules for permitting Router DstMac and VLAN.
     *
     * @param deviceId Switch ID to set the rules
     */
    public void populatePortAddressingRules(DeviceId deviceId) {
        rulePopulator.populateXConnectVlanFilters(deviceId);
        rulePopulator.populateRouterIpPunts(deviceId);

        // Although device is added, sometimes device store does not have the
        // ports for this device yet. It results in missing filtering rules in the
        // switch. We will attempt it a few times. If it still does not work,
        // user can manually repopulate using CLI command sr-reroute-network
        boolean success = rulePopulator.populateRouterMacVlanFilters(deviceId);
        if (!success) {
            executorService.schedule(new RetryFilters(deviceId), 200, TimeUnit.MILLISECONDS);
        }
    }

    /**
     * Start the flow rule population process if it was never started. The
     * process finishes successfully when all flow rules are set and stops with
     * ABORTED status when any groups required for flows is not set yet.
     */
    public void startPopulationProcess() {
        statusLock.lock();
        try {
            if (populationStatus == Status.IDLE
                    || populationStatus == Status.SUCCEEDED
                    || populationStatus == Status.ABORTED) {
                populationStatus = Status.STARTED;
                populateAllRoutingRules();
            } else {
                log.warn("Not initiating startPopulationProcess as populationStatus is {}",
                         populationStatus);
            }
        } finally {
            statusLock.unlock();
        }
    }

    /**
     * Resume the flow rule population process if it was aborted for any reason.
     * Mostly the process is aborted when the groups required are not set yet.
     *  XXX is this called?
     *
     */
    public void resumePopulationProcess() {
        statusLock.lock();
        try {
            if (populationStatus == Status.ABORTED) {
                populationStatus = Status.STARTED;
                // TODO: we need to restart from the point aborted instead of
                // restarting.
                populateAllRoutingRules();
            }
        } finally {
            statusLock.unlock();
        }
    }

    /**
     * Populate rules of given subnet at given location.
     *
     * @param cp connect point of the subnet being added
     * @param subnets subnet being added
     * @return true if succeed
     */
    protected boolean populateSubnet(ConnectPoint cp, Set<Ip4Prefix> subnets) {
        statusLock.lock();
        try {
            EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(cp.deviceId());
            if (ecmpSpg == null) {
                log.warn("Fail to populating subnet {}: {}", subnets, ECMPSPG_MISSING);
                return false;
            }
            return populateEcmpRoutingRules(cp.deviceId(), ecmpSpg, subnets);
        } finally {
            statusLock.unlock();
        }
    }

    /**
     * Revoke rules of given subnet at given location.
     *
     * @param subnets subnet being removed
     * @return true if succeed
     */
    protected boolean revokeSubnet(Set<Ip4Prefix> subnets) {
        statusLock.lock();
        try {
            return srManager.routingRulePopulator.revokeIpRuleForSubnet(subnets);
        } finally {
            statusLock.unlock();
        }
    }

    protected void purgeEcmpGraph(DeviceId deviceId) {
        currentEcmpSpgMap.remove(deviceId);
        if (updatedEcmpSpgMap != null) {
            updatedEcmpSpgMap.remove(deviceId);
        }
    }

    private final class RetryFilters implements Runnable {
        int attempts = MAX_RETRY_ATTEMPTS;
        DeviceId devId;

        private RetryFilters(DeviceId deviceId) {
            devId = deviceId;
        }

        @Override
        public void run() {
            boolean success = rulePopulator.populateRouterMacVlanFilters(devId);
            if (!success && --attempts > 0) {
                executorService.schedule(this, 200, TimeUnit.MILLISECONDS);
            } else if (attempts == 0) {
                log.error("Unable to populate MacVlan filters in dev:{}", devId);
            }
        }

    }

}