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

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

import com.google.common.base.MoreObjects;
import com.google.common.collect.ImmutableMap;
import com.google.common.collect.ImmutableMap.Builder;
import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Lists;
import com.google.common.collect.Maps;
import com.google.common.collect.Sets;
import org.onlab.packet.Ip4Address;
import org.onlab.packet.Ip6Address;
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.onosproject.segmentrouting.grouphandler.DefaultGroupHandler;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Objects;
import java.util.Set;
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.MoreObjects.toStringHelper;
import static com.google.common.base.Preconditions.checkNotNull;
import static java.util.concurrent.Executors.newScheduledThreadPool;
import static org.onlab.util.Tools.groupedThreads;

/**
 * Default routing handler that is responsible for route computing and
 * routing rule population.
 */
public class DefaultRoutingHandler {
    private static final int MAX_CONSTANT_RETRY_ATTEMPTS = 5;
    private static final int RETRY_INTERVAL_MS = 250;
    private static final int RETRY_INTERVAL_SCALE = 1;
    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
        = newScheduledThreadPool(1, groupedThreads("retryftr", "retry-%d", log));

    /**
     * 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();
    }

    /**
     * Returns an immutable copy of the current ECMP shortest-path graph as
     * computed by this controller instance.
     *
     * @return the current ECMP graph
     */
    public ImmutableMap<DeviceId, EcmpShortestPathGraph> getCurrentEmcpSpgMap() {
        Builder<DeviceId, EcmpShortestPathGraph> builder = ImmutableMap.builder();
        currentEcmpSpgMap.entrySet().forEach(entry -> {
            if (entry.getValue() != null) {
                builder.put(entry.getKey(), entry.getValue());
            }
        });
        return builder.build();
    }

    /**
     * Populates all routing rules to all connected routers, including default
     * routing rules, adjacency rules, and policy rules if any.
     */
    public void 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;
                }
                currentEcmpSpgMap.put(sw.id(), ecmpSpg);
                log.debug("Updating ECMPspg for sw:{}", sw.id());

                // 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;
        } finally {
            statusLock.unlock();
        }
    }

    /**
     * Populates the routing rules or makes hash group changes according to the
     * route-path changes due to link failure, switch failure or link up. This
     * method should only be called for one of these three possible event-types.
     * Note that when a switch goes away, all of its links fail as well,
     * but this is handled as a single switch removal event.
     *
     * @param linkDown the single failed link, or null for other conditions
     *                  such as link-up or a removed switch
     * @param linkUp the single link up, or null for other conditions such as
     *                  link-down or a removed switch
     * @param switchDown the removed switch, or null for other conditions such as
     *                  link-down or link-up
     */
    public void populateRoutingRulesForLinkStatusChange(Link linkDown,
                                                           Link linkUp,
                                                           DeviceId switchDown) {
        if ((linkDown != null && (linkUp != null || switchDown != null)) ||
                (linkUp != null && (linkDown != null || switchDown != null)) ||
                (switchDown != null && (linkUp != null || linkDown != null))) {
            log.warn("Only one event can be handled for link status change .. aborting");
            return;
        }

        statusLock.lock();
        try {

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

            // 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.debug("populateRoutingRulesForLinkStatusChange: "
                    + "populationStatus is STARTED");
            populationStatus = Status.STARTED;
            // try optimized re-routing
            if (linkDown == null) {
                // either a linkUp or a switchDown - compute all route changes by
                // comparing all routes of existing ECMP SPG to new ECMP SPG
                routeChanges = computeRouteChange();

                if (routeChanges != null) {
                    // deal with linkUp of a seen-before link
                    if (linkUp != null && srManager.isSeenLink(linkUp)) {
                        if (!isBidirectional(linkUp)) {
                            log.warn("Not a bidirectional link yet .. not "
                                    + "processing link {}", linkUp);
                            srManager.updateSeenLink(linkUp, true);
                            populationStatus = Status.ABORTED;
                            return;
                        }
                        // link previously seen before
                        // do hash-bucket changes instead of a re-route
                        processHashGroupChange(routeChanges, false, null);
                        // clear out routesChanges so a re-route is not attempted
                        routeChanges = ImmutableSet.of();
                    }

                    //deal with switchDown
                    if (switchDown != null) {
                        processHashGroupChange(routeChanges, true, switchDown);
                        // clear out routesChanges so a re-route is not attempted
                        routeChanges = ImmutableSet.of();
                    }

                    // for a linkUp of a never-seen-before link
                    // let it fall through to a reroute of the routeChanges

                }

                // now that we are past the check for a previously seen link
                // it is safe to update the store for the linkUp
                if (linkUp != null) {
                    srManager.updateSeenLink(linkUp, true);
                }

            } else {
                // link has gone down
                // Compare existing ECMP SPG only with the link that went down
                routeChanges = computeDamagedRoutes(linkDown);
                if (routeChanges != null) {
                    processHashGroupChange(routeChanges, true, null);
                    // clear out routesChanges so a re-route is not attempted
                    routeChanges = ImmutableSet.of();
                }
            }

            // do full re-routing if optimized routing returns null routeChanges
            if (routeChanges == null) {
                log.info("Optimized routing failed... doing full re-route");
                populateAllRoutingRules();
                return;
            }

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

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

    /**
     * Returns true if the link being queried is a bidirectional link. A bidi
     * link is defined as a link, whose reverse link - ie. the link in the reverse
     * direction - has been seen-before and is up.
     *
     * @param link the infrastructure link being queried
     * @return true if another unidirectional link exists in the reverse direction,
     *              has been seen-before and is up
     */
    private boolean isBidirectional(Link link) {
        Link reverseLink = srManager.linkService.getLink(link.dst(), link.src());
        if (reverseLink == null) {
            return false;
        }
        Boolean result = srManager.isSeenLinkUp(reverseLink);
        if (result == null) {
            return false;
        }
        return result.booleanValue();
    }

    /**
     * Processes a set a route-path changes by editing hash groups.
     *
     * @param routeChanges a set of route-path changes, where each route-path is
     *                     a list with its first element the src-switch of the path
     *                     and the second element the dst-switch of the path.
     * @param linkOrSwitchFailed true if the route changes are for a failed
     *                           switch or linkDown event
     * @param failedSwitch the switchId if the route changes are for a failed switch,
     *                     otherwise null
     */
    private void processHashGroupChange(Set<ArrayList<DeviceId>> routeChanges,
                                        boolean linkOrSwitchFailed,
                                        DeviceId failedSwitch) {
        for (ArrayList<DeviceId> route : routeChanges) {
            DeviceId targetSw = route.get(0);
            boolean success;
            DeviceId dstSw = null;
            if (route.size() > 1) {
                dstSw = route.get(1);
            }

            if (linkOrSwitchFailed) {
                success = fixHashGroupsForRoute(route, true);
                // it's possible that we cannot fix hash groups for a route
                // if the target switch has failed. Nevertheless the ecmp graph
                // for the impacted switch must still be updated.
                if (failedSwitch != null && targetSw.equals(failedSwitch)
                        && dstSw != null) {
                    currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw));
                    currentEcmpSpgMap.remove(targetSw);
                    log.debug("Updating ECMPspg for dst:{} removing failed "
                            + "target:{}", dstSw, targetSw);
                    return;
                }
                //linkfailed - update both sides
                currentEcmpSpgMap.put(targetSw, updatedEcmpSpgMap.get(targetSw));
                dstSw = route.get(1);
                currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw));
                log.debug("Updating ECMPspg for dst:{} and target:{}", dstSw, targetSw);
            } else {
                success = fixHashGroupsForRoute(route, false);
                if (success) {
                    currentEcmpSpgMap.put(targetSw, updatedEcmpSpgMap.get(targetSw));
                    if (dstSw != null) {
                        currentEcmpSpgMap.put(dstSw, updatedEcmpSpgMap.get(dstSw));
                    }
                    log.debug("Updating ECMPspg for target:{} and dst:{}",
                              targetSw, dstSw);
                }
            }
        }
    }

    /**
     * Edits hash groups in the src-switch (targetSw) of a route-path by
     * calling the groupHandler to either add or remove buckets in an existing
     * hash group.
     *
     * @param route a single list representing a route-path where the first element
     *                  is the src-switch (targetSw) of the route-path and the
     *                  second element is the dst-switch
     * @param revoke true if buckets in the hash-groups need to be removed;
     *              false if buckets in the hash-groups need to be added
     * @return true if the hash group editing is successful
     */
    private boolean fixHashGroupsForRoute(ArrayList<DeviceId> route,
                                          boolean revoke) {
        DeviceId targetSw = route.get(0);
        if (route.size() < 2) {
            log.warn("Cannot fixHashGroupsForRoute - no dstSw in route {}", route);
            return false;
        }
        DeviceId destSw = route.get(1);
        log.debug("Processing fixHashGroupsForRoute: Target {} -> Dest {}",
                  targetSw, destSw);
        boolean targetIsEdge = false;
        try {
            targetIsEdge = srManager.deviceConfiguration.isEdgeDevice(targetSw);
        } catch (DeviceConfigNotFoundException e) {
            log.warn(e.getMessage() + "Cannot determine if targetIsEdge {}.. "
                    + "continuing fixHash", targetSw);
        }

        // figure out the new next hops at the targetSw towards the destSw
        Set<DeviceId> nextHops = new HashSet<>();
        EcmpShortestPathGraph ecmpSpg = updatedEcmpSpgMap.get(destSw);
        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 target : swViaMap.keySet()) {
                if (target.equals(targetSw)) {
                    // found the iteration where targetSw is reached- get nextHops
                    if (!targetIsEdge && itrIdx > 1) {
                        // optimization for spines to not use other leaves to get
                        // to a leaf to avoid loops
                        log.debug("Avoiding {} hop path for non-edge targetSw:{}"
                                + " --> dstSw:{}", itrIdx, targetSw, destSw);
                        break;
                    }
                    for (ArrayList<DeviceId> via : swViaMap.get(target)) {
                        if (via.isEmpty()) {
                            nextHops.add(destSw);
                        } else {
                            // first elem is next-hop in each ECMP path
                            nextHops.add(via.get(0));
                        }
                    }
                    break;
                }
            }
        }

        // call group handler to change hash group at targetSw
        DefaultGroupHandler grpHandler = srManager.getGroupHandler(targetSw);
        if (grpHandler == null) {
            log.warn("Cannot find grouphandler for dev:{} .. aborting"
                    + " {} hash group buckets for route:{} ", targetSw,
                    (revoke) ? "revoke" : "repopulate", route);
            return false;
        }
        log.debug("{} hash-groups buckets For Route {} -> {} to next-hops {}",
                  (revoke) ? "revoke" : "repopulating",
                  targetSw, destSw, nextHops);
        return (revoke) ? grpHandler.fixHashGroups(targetSw, nextHops,
                                                       destSw, true)
                            : grpHandler.fixHashGroups(targetSw, nextHops,
                                                       destSw, false);
    }

    /**
     * Processes a set a route-path changes by reprogramming routing rules and
     * creating new hash-groups if necessary.
     *
     * @param routeChanges a set of route-path changes, where each route-path is
     *                     a list with its first element the src-switch of the path
     *                     and the second element the dst-switch of the path.
     * @return true if successful in repopulating routes
     */
    private boolean repopulateRoutingRulesForRoutes(Set<ArrayList<DeviceId>> routeChanges) {
        rulePopulator.resetCounter();
        HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> routesBydevice =
                new HashMap<>();
        for (ArrayList<DeviceId> link: routeChanges) {
            // When only the source device is defined, reinstall routes to all other devices
            if (link.size() == 1) {
                log.debug("-- 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 all to dest:{} is successful",
                              link.get(0));
                    currentEcmpSpgMap.put(link.get(0), ecmpSpg);
                    log.debug("Updating ECMPspg for dest:{}", link.get(0));
                } else {
                    log.warn("Failed to populate the flow rules from all to dest:{}", 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("-- repopulateRoutingRulesForRoutes {} -> {}",
                          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)) {
                            // in this ECMP path to the targetSw, get the next hop
                            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);
                    }
                }
            }
            //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.
            //In another case, the target switch has gone away, so
            //routes can't be installed. In that case, the current map
            //is updated here, without any flows being pushed.
            currentEcmpSpgMap.put(impactedDevice,
                                  updatedEcmpSpgMap.get(impactedDevice));
            log.debug("Updating ECMPspg for impacted dev:{}", impactedDevice);
        }

        processHashGroupChange(routeChanges, false, null);

        return true;
    }

    /**
     * Computes set of affected routes due to failed link. Assumes
     * previous ecmp shortest-path graph exists for a switch in order to compute
     * affected routes. If such a graph does not exist, the method returns null.
     *
     * @param linkFail the failed link
     * @return the set of affected routes which may be empty if no routes were
     *         affected, or null if no previous ecmp spg was found for comparison
     */
    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())) {
                log.debug("No mastership for {} .. skipping route optimization",
                          sw.id());
                continue;
            }
            EcmpShortestPathGraph ecmpSpg = currentEcmpSpgMap.get(sw.id());
            if (ecmpSpg == null) {
                log.warn("No existing ECMP graph for switch {}. Aborting optimized"
                        + " rerouting and opting for full-reroute", sw.id());
                return null;
            }
            if (log.isDebugEnabled()) {
                log.debug("Root switch: {}", sw.id());
                log.debug("  Current/Existing SPG: {}", ecmpSpg);
                log.debug("       New/Updated SPG: {}", updatedEcmpSpgMap.get(sw.id()));
            }
            HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> switchVia =
                    ecmpSpg.getAllLearnedSwitchesAndVia();
            for (Integer itrIdx : switchVia.keySet()) {
                log.trace("Current/Exiting SPG Iterindex# {}", itrIdx);
                HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> swViaMap =
                        switchVia.get(itrIdx);
                for (DeviceId targetSw : swViaMap.keySet()) {
                    DeviceId rootSw = sw.id();
                    if (log.isTraceEnabled()) {
                        log.trace("TargetSwitch {} --> RootSwitch {}", targetSw, rootSw);
                        for (ArrayList<DeviceId> via : swViaMap.get(targetSw)) {
                            log.trace(" Via:");
                            via.forEach(e -> log.trace("  {}", e));
                        }
                    }
                    Set<ArrayList<DeviceId>> subLinks =
                            computeLinks(targetSw, rootSw, 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, rootSw);
                            ArrayList<DeviceId> aRoute = new ArrayList<>();
                            aRoute.add(targetSw); // switch with rules to populate
                            aRoute.add(rootSw); // towards this destination
                            routes.add(aRoute);
                            break;
                        }
                    }
                }
            }

        }

        return routes;
    }

    /**
     * Computes set of affected routes due to new links or failed switches.
     *
     * @return the set of affected routes which may be empty if no routes were
     *         affected
     */
    private Set<ArrayList<DeviceId>> computeRouteChange() {

        ImmutableSet.Builder<ArrayList<DeviceId>> changedRoutesBuilder =
                ImmutableSet.builder();

        for (Device sw : srManager.deviceService.getDevices()) {
            DeviceId rootSw = sw.id();
            log.debug("Computing the impacted routes for device {}", rootSw);
            if (!srManager.mastershipService.isLocalMaster(rootSw)) {
                log.debug("No mastership for {} ... skipping route optimization",
                          rootSw);
                continue;
            }
            if (log.isTraceEnabled()) {
                log.trace("Device links for dev: {}", rootSw);
                for (Link link: srManager.linkService.getDeviceLinks(rootSw)) {
                    log.trace("{} -> {} ", link.src().deviceId(), link.dst().deviceId());
                }
            }
            EcmpShortestPathGraph currEcmpSpg = currentEcmpSpgMap.get(rootSw);
            if (currEcmpSpg == null) {
                log.debug("No existing ECMP graph for device {}.. adding self as "
                        + "changed route", rootSw);
                changedRoutesBuilder.add(Lists.newArrayList(rootSw));
                continue;
            }
            EcmpShortestPathGraph newEcmpSpg = updatedEcmpSpgMap.get(rootSw);
            if (log.isDebugEnabled()) {
                log.debug("Root switch: {}", rootSw);
                log.debug("  Current/Existing SPG: {}", currEcmpSpg);
                log.debug("       New/Updated SPG: {}", newEcmpSpg);
            }
            // first use the updated/new map to compare to current/existing map
            // as new links may have come up
            changedRoutesBuilder.addAll(compareGraphs(newEcmpSpg, currEcmpSpg, rootSw));
            // then use the current/existing map to compare to updated/new map
            // as switch may have been removed
            changedRoutesBuilder.addAll(compareGraphs(currEcmpSpg, newEcmpSpg, rootSw));
        }

        Set<ArrayList<DeviceId>> changedRoutes = changedRoutesBuilder.build();
        for (ArrayList<DeviceId> route: changedRoutes) {
            log.debug("Route changes Target -> Root");
            if (route.size() == 1) {
                log.debug(" : all -> {}", route.get(0));
            } else {
                log.debug(" : {} -> {}", route.get(0), route.get(1));
            }
        }
        return changedRoutes;
    }

    /**
     * For the root switch, searches all the target nodes reachable in the base
     * graph, and compares paths to the ones in the comp graph.
     *
     * @param base the graph that is indexed for all reachable target nodes
     *             from the root node
     * @param comp the graph that the base graph is compared to
     * @param rootSw  both ecmp graphs are calculated for the root node
     * @return all the routes that have changed in the base graph
     */
    private Set<ArrayList<DeviceId>> compareGraphs(EcmpShortestPathGraph base,
                                                   EcmpShortestPathGraph comp,
                                                   DeviceId rootSw) {
        ImmutableSet.Builder<ArrayList<DeviceId>> changedRoutesBuilder =
                ImmutableSet.builder();
        HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> baseMap =
                base.getAllLearnedSwitchesAndVia();
        HashMap<Integer, HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>>> compMap =
                comp.getAllLearnedSwitchesAndVia();
        for (Integer itrIdx : baseMap.keySet()) {
            HashMap<DeviceId, ArrayList<ArrayList<DeviceId>>> baseViaMap =
                    baseMap.get(itrIdx);
            for (DeviceId targetSw : baseViaMap.keySet()) {
                ArrayList<ArrayList<DeviceId>> basePath = baseViaMap.get(targetSw);
                ArrayList<ArrayList<DeviceId>> compPath = getVia(compMap, targetSw);
                if ((compPath == null) || !basePath.equals(compPath)) {
                    log.trace("Impacted route:{} -> {}", targetSw, rootSw);
                    ArrayList<DeviceId> route = new ArrayList<>();
                    route.add(targetSw);
                    route.add(rootSw);
                    changedRoutesBuilder.add(route);
                }
            }
        }
        return changedRoutesBuilder.build();
    }

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

        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 it succeeds in populating rules
     */
    private boolean populateEcmpRoutingRules(DeviceId destSw,
                                             EcmpShortestPathGraph ecmpSPG,
                                             Set<IpPrefix> 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 in which rules will be programmed
     * @param destSw Device ID of final destination switch to which the rules will forward
     * @param nextHops List of next hops via which destSw will be reached
     * @param subnets Subnets to be populated. If empty, populate all configured subnets.
     * @return true if it succees in populating rules
     */
    private boolean populateEcmpRoutingRulePartial(DeviceId targetSw,
                                                   DeviceId destSw,
                                                   Set<DeviceId> nextHops,
                                                   Set<IpPrefix> 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 destRouterIpv4;
        Ip6Address destRouterIpv6;

        try {
            targetIsEdge = config.isEdgeDevice(targetSw);
            destIsEdge = config.isEdgeDevice(destSw);
            destRouterIpv4 = config.getRouterIpv4(destSw);
            destRouterIpv6 = config.getRouterIpv6(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;
            }
            IpPrefix routerIpPrefix = destRouterIpv4.toIpPrefix();
            log.debug("* populateEcmpRoutingRulePartial in device {} towards {} "
                    + "for router IP {}", targetSw, destSw, routerIpPrefix);
            result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix,
                                                           destSw, nextHops);
            if (!result) {
                return false;
            }
            // If present we deal with IPv6 loopback.
            if (destRouterIpv6 != null) {
                routerIpPrefix = destRouterIpv6.toIpPrefix();
                log.debug("* populateEcmpRoutingRulePartial in device {} towards {}"
                        + " for v6 router IP {}", targetSw, destSw, routerIpPrefix);
                result = rulePopulator.populateIpRuleForRouter(targetSw, routerIpPrefix,
                                                               destSw, nextHops);
                if (!result) {
                    return false;
                }
            }
        }

        if (!targetIsEdge && destIsEdge) {
            // MPLS rules in all non-edge target devices
            log.debug("* populateEcmpRoutingRulePartial in device{} towards {} for "
                    + "all MPLS rules", targetSw, destSw);
            result = rulePopulator.populateMplsRule(targetSw, destSw, nextHops,
                                                    destRouterIpv4);
            if (!result) {
                return false;
            }
            if (destRouterIpv6 != null) {
                result = rulePopulator.populateMplsRule(targetSw, destSw, nextHops,
                                                        destRouterIpv6);
                if (!result) {
                    return false;
                }
            }
        }

        // To save on ECMP groups
        // avoid MPLS rules in non-edge-devices to non-edge-devices
        // avoid MPLS transit rules in edge-devices
        // avoid loopback IP rules in edge-devices to non-edge-devices
        return true;
    }

    /**
     * Populates filtering rules for port, and punting rules
     * for gateway IPs, loopback IPs and arp/ndp traffic.
     * Should only be called by the master instance for this device/port.
     *
     * @param deviceId Switch ID to set the rules
     */
    public void populatePortAddressingRules(DeviceId 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
        PortFilterInfo firstRun = rulePopulator.populateVlanMacFilters(deviceId);
        if (firstRun == null) {
            firstRun = new PortFilterInfo(0, 0, 0);
        }
        executorService.schedule(new RetryFilters(deviceId, firstRun),
                                 RETRY_INTERVAL_MS, 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<IpPrefix> 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<IpPrefix> 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);
        }
    }

    /**
     * Utility class used to temporarily store information about the ports on a
     * device processed for filtering objectives.
     */
    public final class PortFilterInfo {
        int disabledPorts = 0, errorPorts = 0, filteredPorts = 0;

        public PortFilterInfo(int disabledPorts, int errorPorts,
                           int filteredPorts) {
            this.disabledPorts = disabledPorts;
            this.filteredPorts = filteredPorts;
            this.errorPorts = errorPorts;
        }

        @Override
        public int hashCode() {
            return Objects.hash(disabledPorts, filteredPorts, errorPorts);
        }

        @Override
        public boolean equals(Object obj) {
            if (this == obj) {
                return true;
            }
            if ((obj == null) || (!(obj instanceof PortFilterInfo))) {
                return false;
            }
            PortFilterInfo other = (PortFilterInfo) obj;
            return ((disabledPorts == other.disabledPorts) &&
                    (filteredPorts == other.filteredPorts) &&
                    (errorPorts == other.errorPorts));
        }

        @Override
        public String toString() {
            MoreObjects.ToStringHelper helper = toStringHelper(this)
                    .add("disabledPorts", disabledPorts)
                    .add("errorPorts", errorPorts)
                    .add("filteredPorts", filteredPorts);
            return helper.toString();
        }
    }

    /**
     * RetryFilters populates filtering objectives for a device and keeps retrying
     * till the number of ports filtered are constant for a predefined number
     * of attempts.
     */
    protected final class RetryFilters implements Runnable {
        int constantAttempts = MAX_CONSTANT_RETRY_ATTEMPTS;
        DeviceId devId;
        int counter;
        PortFilterInfo prevRun;

        private RetryFilters(DeviceId deviceId, PortFilterInfo previousRun) {
            devId = deviceId;
            prevRun = previousRun;
            counter = 0;
        }

        @Override
        public void run() {
            log.debug("RETRY FILTER ATTEMPT {} ** dev:{}", ++counter, devId);
            PortFilterInfo thisRun = rulePopulator.populateVlanMacFilters(devId);
            boolean sameResult = prevRun.equals(thisRun);
            log.debug("dev:{} prevRun:{} thisRun:{} sameResult:{}", devId, prevRun,
                      thisRun, sameResult);
            if (thisRun == null || !sameResult || (sameResult && --constantAttempts > 0)) {
                // exponentially increasing intervals for retries
                executorService.schedule(this,
                    RETRY_INTERVAL_MS * (int) Math.pow(counter, RETRY_INTERVAL_SCALE),
                    TimeUnit.MILLISECONDS);
                if (!sameResult) {
                    constantAttempts = MAX_CONSTANT_RETRY_ATTEMPTS; //reset
                }
            }
            prevRun = (thisRun == null) ? prevRun : thisRun;
        }
    }

}