apps/network-troubleshoot/core/src/main/java/org/onosproject/fnl/impl/DefaultCheckLoop.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.fnl.impl;

import org.onlab.packet.IpPrefix;
import org.onosproject.fnl.intf.NetworkAnomaly;
import org.onosproject.fnl.intf.NetworkDiagnostic;
import org.onosproject.fnl.base.TsLoopPacket;
import org.onosproject.fnl.base.TsReturn;
import org.onosproject.net.ConnectPoint;
import org.onosproject.net.Device;
import org.onosproject.net.DeviceId;
import org.onosproject.net.Link;
import org.onosproject.net.PortNumber;
import org.onosproject.net.device.DeviceService;
import org.onosproject.net.flow.FlowEntry;
import org.onosproject.net.flow.FlowRuleService;
import org.onosproject.net.flow.criteria.Criterion;
import org.onosproject.net.flow.criteria.EthTypeCriterion;
import org.onosproject.net.flow.criteria.IPCriterion;
import org.onosproject.net.flow.criteria.IPProtocolCriterion;
import org.onosproject.net.flow.criteria.PortCriterion;
import org.onosproject.net.flow.instructions.Instruction;
import org.onosproject.net.flow.instructions.Instructions.OutputInstruction;
import org.onosproject.net.host.HostService;
import org.onosproject.net.link.LinkService;
import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

import java.util.Iterator;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.stream.Collectors;

import static com.google.common.base.Preconditions.checkArgument;
import static com.google.common.base.Preconditions.checkNotNull;
import static org.onlab.packet.EthType.EtherType.IPV4;
import static org.onlab.packet.EthType.EtherType.VLAN;
import static org.onosproject.fnl.base.NetworkDiagnosticUtils.isDevice;
import static org.onosproject.fnl.base.NetworkDiagnosticUtils.sortCriteria;
import static org.onosproject.fnl.base.NetworkDiagnosticUtils.sortFlowTable;
import static org.onosproject.fnl.base.TsLoopPacket.matchBuilder;
import static org.onosproject.fnl.intf.NetworkDiagnostic.Type.LOOP;
import static org.onosproject.net.flow.FlowEntry.FlowEntryState.ADDED;
import static org.onosproject.net.flow.criteria.Criteria.matchInPort;
import static org.onosproject.net.flow.criteria.Criterion.Type.ETH_TYPE;
import static org.onosproject.net.flow.criteria.Criterion.Type.IN_PORT;
import static org.onosproject.net.flow.criteria.Criterion.Type.IP_PROTO;

/**
 * Loop Checking Diagnostic Implementation.
 *
 * Strategy Pattern.
 */
public class DefaultCheckLoop implements NetworkDiagnostic {

    private static final int IP_PROTO_TCP_TS = 6;
    private static final int IP_PROTO_UDP_TS = 17;

    private static final String E_CANNOT_HANDLE = "can not handle {} now.";

    private final Logger log = LoggerFactory.getLogger(getClass());

    private final DeviceService deviceService;
    private final HostService hostService;
    private final FlowRuleService flowRuleService;
    private final LinkService linkService;


    private Map<DeviceId, Device> deviceInfo;
    private Map<DeviceId, Iterable<FlowEntry>> flowEntryInfo;
    private Set<Device> accessDevices;

    //conventionally used by tsGetEgressLinks()
    private Map<DeviceId, Set<Link>> egressLinkInfo;

    //Two below are hot data in checking process.
    private Set<NetworkAnomaly> loops;
    private Set<DeviceId> excludeDeviceId;

    /**
     * Creates and returns an instance of Loop Checking algorithm module.
     *
     * @param ds reference of DeviceService
     * @param hs reference of HostService
     * @param frs reference of FlowRuleService
     * @param ls reference of LinkService
     */
    public DefaultCheckLoop(DeviceService ds,
                            HostService hs,
                            FlowRuleService frs,
                            LinkService ls) {
        checkNotNull(ds, "DeviceService cannot be null");
        checkNotNull(hs, "HostService cannot be null");
        checkNotNull(frs, "FlowRuleService cannot be null");
        checkNotNull(ls, "LinkService  cannot be null");

        deviceService = ds;
        hostService = hs;
        flowRuleService = frs;
        linkService = ls;
    }

    /**
     * Checks for loops and returns any that were found.
     * An empty set is returned if there are no loops.
     *
     * @return the set of loops; may be empty
     */
    @Override
    public Set<NetworkAnomaly> findAnomalies() {
        return findLoop();
    }

    @Override
    public Type type() {
        return LOOP;
    }

    /**
     * Enter of the loop checking algorithm.
     *
     * @return the set of loop results; empty, if there is no loop
     */
    private Set<NetworkAnomaly> findLoop() {

        getNetworkSnapshot();

        loops = new HashSet<>();
        excludeDeviceId = new HashSet<>();

        for (Device device : accessDevices) {
            if (excludeDeviceId.contains(device.id())) {
                continue;
            }


            List<FlowEntry> availableFlowEntries = new ArrayList<>();

            flowEntryInfo.get(device.id()).forEach(flowEntry -> {
                if (flowEntry.state() == ADDED) {
                    availableFlowEntries.add(flowEntry);
                }
            });

            List<FlowEntry> sortedFlowEntries = sortFlowTable(availableFlowEntries);


            for (FlowEntry flow : sortedFlowEntries) {

                TsLoopPacket pkt =
                        matchBuilder(flow.selector().criteria(), null);

                pkt.pushPathFlow(flow);

                List<Instruction> inst = flow.treatment().immediate();

                for (Instruction instOne : inst) {
                    // Attention !!!
                    // if you would like to modify the code here,
                    // please MAKE VERY SURE that you are clear with
                    // the relationship of any invoked methods, and
                    // the relationship of params which are passed in and out.
                    processOneInstruction(instOne, device.id(),
                            null, pkt, true, flow);
                }
            }
        }

        // TODO - avoid two-hop LOOP

        // TODO - another clean operations

        return loops;
    }

    /**
     * Iterate one by one at switch hops.
     * Return whether we discover a Loop now or not.
     *
     * When flows form a loop,
     * pkt is also a return value indicating the loop header.
     *
     * @param deviceId the device needed to be checked
     * @param pkt virtual packet forwarded by switches
     * @return true if a loop is discovered
     */
    private boolean matchDeviceFlows(DeviceId deviceId, TsLoopPacket pkt) {
        if (pkt.isPassedDevice(deviceId)) {
            return true; // Attention: pkt should be held outside
        }


        List<FlowEntry> availableFlowEntries = new ArrayList<>();

        flowEntryInfo.get(deviceId).forEach(flowEntry -> {
            if (flowEntry.state() == ADDED) {
                availableFlowEntries.add(flowEntry);
            }
        });

        List<FlowEntry> sortedFlowEntries = sortFlowTable(availableFlowEntries);


        for (FlowEntry flowEntry : sortedFlowEntries) {
            TsReturn<Boolean> isBigger = new TsReturn<>();
            TsLoopPacket newPkt = pkt.copyPacketMatch();

            if (!matchAndAddFlowEntry(flowEntry, newPkt, isBigger)) {
                continue;
            }

            newPkt.pushPathFlow(flowEntry);
            // no need to popPathFlow(),
            // because we will drop this newPkt, and copy pkt again

            for (Instruction instOne : flowEntry.treatment().immediate()) {
                // Attention !!!
                // if you would like to modify the code here,
                // please MAKE VERY SURE that you are clear with
                // the relationship of any invoked methods, and
                // the relationship of params which are passed in and out.
                if (processOneInstruction(instOne, deviceId,
                        pkt, newPkt, false, null)) {
                    return true;
                }
            }

            newPkt.popPathFlow();

            if (!isBigger.getValue()) {
                break;
            }
        }
        return false;
    }

    /**
     * Process one of every instructions.
     *
     * The isFindLoop should be true if it is invoked by findLoop method,
     * and be false if it is invoked by matchDeviceFlows method.
     *
     * @param instOne the instruction to be processed
     * @param currentDeviceId id of the device we are now in
     * @param initPkt the packet before being copied
     * @param matchedPkt the packet which matched the flow entry,
     *                   to which this instruction belongs
     * @param isFindLoop indicate if it is invoked by findLoop method
     * @param firstEntry the flow entry from which the packet is generated
     * @return true, if a loop is discovered;
     *         false, 1. invoked by matchDeviceFlows method, and detected no loop;
     *                2. invoked by findLoop method
     */
    private boolean processOneInstruction(Instruction instOne,
                                          DeviceId currentDeviceId,
                                          TsLoopPacket initPkt,
                                          TsLoopPacket matchedPkt,
                                          boolean isFindLoop,
                                          FlowEntry firstEntry) {
        if (isFindLoop) {
            checkArgument(initPkt == null,
                    "initPkt is not null, while isFindLoop is true.");
        } else {
            checkArgument(firstEntry == null,
                    "firstEntry is not null, while isFindLoop is false.");
        }


        Instruction.Type type = instOne.type();
        switch (type) {
            case L2MODIFICATION:
                //TODO - modify the L2 header of virtual packet
                log.warn(E_CANNOT_HANDLE, type);
                break;
            case L3MODIFICATION:
                //TODO - modify the L3 header of virtual packet
                log.warn(E_CANNOT_HANDLE, type);
                break;
            case L4MODIFICATION:
                //TODO - modify the L4 header of virtual packet
                log.warn(E_CANNOT_HANDLE, type);
                break;
            case OUTPUT:
                if (processOneOutputInstruction(instOne, currentDeviceId,
                        initPkt, matchedPkt, isFindLoop, firstEntry)) {
                    return true;
                }
                break;
            default:
                log.error("Can't process this type of instruction: {} now.",
                        instOne.type());
                break;
        }
        return false;
    }

    /**
     * Process one output instruction.
     *
     * Params are passed from processOneInstruction directly,
     * and obey the same rules.
     *
     * @param instOne the instruction to be processed
     * @param currentDeviceId id of the device we are now in
     * @param initPkt the packet before being copied
     * @param matchedPkt the packet which matched the flow entry,
     *                   to which this instruction belongs
     * @param isFindLoop indicate if it is invoked by findLoop method
     * @param firstEntry the flow entry from which the packet is generated
     * @return true, if a loop is discovered;
     *         false, 1. invoked by matchDeviceFlows method, and detected no loop;
     *                2. invoked by findLoop method
     */
    private boolean processOneOutputInstruction(Instruction instOne,
                                                DeviceId currentDeviceId,
                                                TsLoopPacket initPkt,
                                                TsLoopPacket matchedPkt,
                                                boolean isFindLoop,
                                                FlowEntry firstEntry) {
        OutputInstruction instOutput = (OutputInstruction) instOne;
        PortNumber instPort = instOutput.port();

        if (!instPort.isLogical()) {
            // single OUTPUT - NIC or normal port

            Set<Link> dstLink = tsGetEgressLinks(
                    new ConnectPoint(currentDeviceId, instPort));
            if (!dstLink.isEmpty()) {

                // TODO - now, just deal with the first destination.
                // will there be more destinations?

                Link dstThisLink = dstLink.iterator().next();
                ConnectPoint dstPoint = dstThisLink.dst();

                // check output to devices only (output to a host is normal)
                if (isDevice(dstPoint)) {
                    PortCriterion oldInPort =
                            updatePktInportPerHop(matchedPkt, dstPoint);
                    matchedPkt.pushPathLink(dstThisLink);
                    TsLoopPacket newNewPkt = matchedPkt.copyPacketMatch();

                    boolean loopFound =
                            matchDeviceFlows(dstPoint.deviceId(), newNewPkt);
                    if (isFindLoop) {
                        if (loopFound) {
                            loops.add(newNewPkt);
                            updateExcludeDeviceSet(newNewPkt);
                        }
                        matchedPkt.resetLinkFlow(firstEntry);
                    } else {
                        if (loopFound) {
                            initPkt.handInLoopMatch(newNewPkt);
                            return true;
                        }
                        matchedPkt.popPathLink();
                    }
                    restorePktInportPerHop(matchedPkt, oldInPort);
                }
            } else {
                if (!isFindLoop) {
                    //TODO - NEED
                    log.warn("no link connecting at device {}, port {}",
                            currentDeviceId, instPort);
                }
            }
        } else if (instPort.equals(PortNumber.IN_PORT)) {
            //TODO - in the future,
            // we may need to resolve this condition 1
            log.warn("can not handle {} port now.", PortNumber.IN_PORT);
        } else if (instPort.equals(PortNumber.NORMAL) ||
                instPort.equals(PortNumber.FLOOD) ||
                instPort.equals(PortNumber.ALL)) {
            //TODO - in the future,
            // we may need to resolve this condition 2
            log.warn("can not handle {}/{}/{} now.",
                    PortNumber.NORMAL, PortNumber.FLOOD, PortNumber.ALL);
        }
        return false;
    }

    private void updateExcludeDeviceSet(TsLoopPacket loopPkt) {
        Iterator<Link> iter = loopPkt.getPathLink();
        while (iter.hasNext()) {
            excludeDeviceId.add(iter.next().src().deviceId());
        }
    }

    private PortCriterion updatePktInportPerHop(TsLoopPacket oldPkt,
                                                ConnectPoint dstPoint) {

        PortCriterion inPort = oldPkt.getInport();
        PortCriterion oldInPort =
                null != inPort ? (PortCriterion) matchInPort(inPort.port()) : null;
        // TODO - check - if it really copies this object

        oldPkt.setHeader(matchInPort(dstPoint.port()));

        return oldInPort;
    }

    private void restorePktInportPerHop(TsLoopPacket pkt,
                                        PortCriterion oldInPort) {
        if (oldInPort == null) {
            pkt.delHeader(IN_PORT);
        } else {
            pkt.setHeader(oldInPort);
        }
    }

    private void getNetworkSnapshot() {
        deviceInfo = new HashMap<>();
        deviceService.getDevices().forEach(d -> deviceInfo.put(d.id(), d));

        flowEntryInfo = new HashMap<>();
        deviceInfo.keySet().forEach(id ->
                flowEntryInfo.put(id, flowRuleService.getFlowEntries(id)));

        egressLinkInfo = new HashMap<>();
        deviceInfo.keySet().forEach(id ->
                egressLinkInfo.put(id, linkService.getDeviceEgressLinks(id)));

        accessDevices = new HashSet<>();
        hostService.getHosts().forEach(h ->
                accessDevices.add(deviceInfo.get(h.location().deviceId())));
    }

    private Set<Link> tsGetEgressLinks(ConnectPoint point) {
        Set<Link> portEgressLink = new HashSet<>();
        DeviceId deviceId = point.deviceId();

        portEgressLink.addAll(
                //all egress links
                egressLinkInfo.get(deviceId)
                        .stream()
                        .filter(l -> l.src().equals(point))
                        .collect(Collectors.toList()));

        return portEgressLink;
    }

    private boolean matchAndAddFlowEntry(FlowEntry flowEntry,
                                         TsLoopPacket pkt,
                                         TsReturn<Boolean> isBigger) {
        isBigger.setValue(false);

        List<Criterion> criterionArray =
                sortCriteria(flowEntry.selector().criteria());

        for (Criterion criterion : criterionArray) {
            // TODO - advance
            switch (criterion.type()) {
                case IN_PORT:
                case ETH_SRC:
                    // At present, not support Ethernet mask (ONOS?)
                case ETH_DST:
                    // At present, not support Ethernet mask (ONOS?)
                case ETH_TYPE:
                    if (!matchAddExactly(pkt, criterion, isBigger)) {
                        return false;
                    }
                    break;
                case VLAN_VID:
                    // At present, not support VLAN mask (ONOS?)
                case VLAN_PCP:
                    if (!pkt.headerExists(ETH_TYPE) ||
                            !((EthTypeCriterion) pkt.getHeader(ETH_TYPE))
                                    .ethType().equals(VLAN.ethType())) {
                        return false;
                    }
                    if (!matchAddExactly(pkt, criterion, isBigger)) {
                        return false;
                    }
                    break;
                case IPV4_SRC:
                case IPV4_DST:
                    if (!pkt.headerExists(ETH_TYPE) ||
                            !((EthTypeCriterion) pkt.getHeader(ETH_TYPE))
                                    .ethType().equals(IPV4.ethType())) {
                        return false;
                    }
                    if (!matchAddIPV4(pkt, criterion, isBigger)) {
                        return false;
                    }
                    break;
                case IP_PROTO:
                    if (!pkt.headerExists(ETH_TYPE) ||
                            !((EthTypeCriterion) pkt.getHeader(ETH_TYPE))
                                    .ethType().equals(IPV4.ethType())) {
                        return false;
                    }
                    if (!matchAddExactly(pkt, criterion, isBigger)) {
                        return false;
                    }
                    break;
                case IP_DSCP:
                    // TODO: 10/28/16 support IP_DSCP match field
                    break;
                case IP_ECN:
                    // TODO: 10/28/16 support IP_DSCP match field
                    break;
                case TCP_SRC:
                case TCP_DST:
                    if (!pkt.headerExists(IP_PROTO) ||
                            IP_PROTO_TCP_TS !=
                                    ((IPProtocolCriterion)
                                            pkt.getHeader(IP_PROTO))
                                            .protocol()
                            ) {
                        // has TCP match requirement, but can't afford TCP
                        return false;
                    }
                    // in this "for" loop
                    // avoid IP_PROTO locates after TCP_*
                    if (!matchAddExactly(pkt, criterion, isBigger)) {
                        return false;
                    }
                    break;
                case UDP_SRC:
                case UDP_DST:
                    if (!pkt.headerExists(IP_PROTO) ||
                            IP_PROTO_UDP_TS !=
                                    ((IPProtocolCriterion)
                                            pkt.getHeader(IP_PROTO))
                                            .protocol()
                            ) {
                        // has UDP match requirement, but can't afford UDP
                        return false;
                    }
                    // in this "for" loop
                    // avoid IP_PROTO locates after UDP_*
                    if (!matchAddExactly(pkt, criterion, isBigger)) {
                        return false;
                    }
                    break;

                default:
                    log.debug("{} can't be supported by OF1.0",
                            criterion.type());
                    return false;
            }
        }
        return true;
    }

    private boolean matchAddExactly(TsLoopPacket pkt,
                                    Criterion criterion,
                                    TsReturn<Boolean> isBigger) {

        if (pkt.headerExists(criterion.type())) {
            if (!pkt.getHeader(criterion.type()).equals(criterion)) {
                return false;
            }

        } else {
            // TODO - check if it is IN_PORT or IN_PHY_PORT, should be strict
            pkt.setHeader(criterion);
            isBigger.setValue(true);
        }

        return true; // should put it here
    }

    // before invoking this, MUST insure EtherType is IPv4.
    private boolean matchAddIPV4(TsLoopPacket pkt,
                                 Criterion criterion,
                                 TsReturn<Boolean> isBigger) {

        if (pkt.headerExists(criterion.type())) {

            IpPrefix ipFlow = ((IPCriterion) criterion).ip();
            IpPrefix ipPkt =
                    ((IPCriterion) pkt.getHeader(criterion.type())).ip();

            // attention - the order below is important
            if (ipFlow.equals(ipPkt)) {
                // shoot

            } else if (ipFlow.contains(ipPkt)) {
                // shoot, pkt is more exact than flowEntry

            } else if (ipPkt.contains(ipFlow)) {
                // pkt should be changed to be more exact
                pkt.setHeader(criterion);
                isBigger.setValue(true);
            } else {
                // match fail
                return false;
            }

        } else {
            // attention the order of criteria in "for" loop
            pkt.setHeader(criterion);
            isBigger.setValue(true);
        }

        return true;
    }
}