bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java

   1 /*
   2  * Copyright (c) 2015 Cisco Systems, Inc. and others.  All rights reserved.
   3  *
   4  * This program and the accompanying materials are made available under the
   5  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
   6  * and is available at http://www.eclipse.org/legal/epl-v10.html
   7  */
   8 package org.opendaylight.protocol.bgp.mode.impl.add;
   9
  10 import java.util.ArrayList;
  11 import java.util.Collections;
  12 import java.util.List;
  13 import java.util.Map;
  14 import javax.annotation.concurrent.NotThreadSafe;
  15 import org.opendaylight.controller.md.sal.common.api.data.LogicalDatastoreType;
  16 import org.opendaylight.controller.md.sal.dom.api.DOMDataWriteTransaction;
  17 import org.opendaylight.protocol.bgp.mode.api.BestPath;
  18 import org.opendaylight.protocol.bgp.mode.impl.OffsetMap;
  19 import org.opendaylight.protocol.bgp.mode.spi.AbstractRouteEntry;
  20 import org.opendaylight.protocol.bgp.rib.spi.CacheDisconnectedPeers;
  21 import org.opendaylight.protocol.bgp.rib.spi.ExportPolicyPeerTracker;
  22 import org.opendaylight.protocol.bgp.rib.spi.PeerExportGroup;
  23 import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
  24 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.PeerId;
  25 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.PeerRole;
  26 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev130925.rib.TablesKey;
  27 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier;
  28 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.NodeIdentifier;
  29 import org.opendaylight.yangtools.yang.data.api.YangInstanceIdentifier.PathArgument;
  30 import org.opendaylight.yangtools.yang.data.api.schema.ContainerNode;
  31 import org.opendaylight.yangtools.yang.data.api.schema.MapEntryNode;
  32 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNode;
  33 import org.opendaylight.yangtools.yang.data.api.schema.NormalizedNodes;
  34 import org.slf4j.Logger;
  35 import org.slf4j.LoggerFactory;
  36
  37 /**
  38  * A single route entry inside a route table. Maintains the attributes of
  39  * from all contributing peers. The information is stored in arrays with a
  40  * shared map of offsets for peers to allow lookups. This is needed to
  41  * maintain low memory overhead in face of large number of routes and peers,
  42  * where individual object overhead becomes the dominating factor.
  43  */
  44 @NotThreadSafe
  45 public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry {
  46
  47     private static final Logger LOG = LoggerFactory.getLogger(AddPathAbstractRouteEntry.class);
  48     protected List<AddPathBestPath> bestPath = new ArrayList<>();
  49     protected List<AddPathBestPath> bestPathRemoved = new ArrayList<>();
  50     protected OffsetMap<RouteKey> offsets = new OffsetMap<>(RouteKey.class);
  51     protected ContainerNode[] values = new ContainerNode[0];
  52     protected Long[] pathsId = new Long[0];
  53     private long pathIdCounter = 0L;
  54
  55     private int addRoute(final RouteKey key, final ContainerNode attributes) {
  56         this.pathIdCounter++;
  57         int offset = this.offsets.offsetOf(key);
  58         if (offset < 0) {
  59             final OffsetMap<RouteKey> newOffsets = this.offsets.with(key);
  60             offset = newOffsets.offsetOf(key);
  61             final ContainerNode[] newAttributes = newOffsets.expand(this.offsets, this.values, offset);
  62             final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset);
  63             this.values = newAttributes;
  64             this.offsets = newOffsets;
  65             this.pathsId = newPathsId;
  66         }
  67
  68         this.offsets.setValue(this.values, offset, attributes);
  69         this.offsets.setValue(this.pathsId, offset, this.pathIdCounter);
  70         LOG.trace("Added route from {} attributes {}", key.getRouteId(), attributes);
  71         return offset;
  72     }
  73
  74     protected int addRoute(final RouteKey key, final NodeIdentifier attributesIdentifier, final NormalizedNode<?, ?> data) {
  75         LOG.trace("Find {} in {}", attributesIdentifier, data);
  76         final ContainerNode advertisedAttrs = (ContainerNode) NormalizedNodes.findNode(data, attributesIdentifier).orNull();
  77         return addRoute(key, advertisedAttrs);
  78     }
  79
  80     /**
  81      * Remove route
  82      *
  83      * @param key RouteKey of removed route
  84      * @param offset Offset of removed route
  85      * @return true if it was the last route
  86      */
  87     protected final boolean removeRoute(final RouteKey key, final int offset) {
  88         this.values = this.offsets.removeValue(this.values, offset);
  89         this.pathsId = this.offsets.removeValue(this.pathsId, offset);
  90         this.offsets = this.offsets.without(key);
  91         return this.offsets.size() == 0;
  92     }
  93
  94     @Override
  95     public void updateRoute(final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final YangInstanceIdentifier locRibTarget, final RIBSupport ribSup,
  96         final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx, final PathArgument routeIdPA) {
  97         this.bestPathRemoved.forEach(path -> removePathFromDataStore(path, isFirstBestPath(bestPathRemoved.indexOf(path)), routeIdPA, locRibTarget, ribSup,
  98             peerPT, localTK, discPeers,tx));
  99         this.bestPathRemoved = Collections.emptyList();
 100
 101         this.bestPath.forEach(path -> addPathToDataStore(path, isFirstBestPath(this.bestPath.indexOf(path)), routeIdPA, locRibTarget, ribSup,
 102             peerPT, localTK, discPeers,tx));
 103     }
 104
 105     @Override
 106     public void writeRoute(final PeerId destPeer, final PathArgument routeId, final YangInstanceIdentifier rootPath, final PeerExportGroup peerGroup,
 107         final TablesKey localTK, final ExportPolicyPeerTracker peerPT, final RIBSupport ribSup, final CacheDisconnectedPeers discPeers,
 108         final DOMDataWriteTransaction tx) {
 109         final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
 110         this.bestPath.stream().filter(path -> filterRoutes(path.getPeerId(), destPeer, peerPT, localTK, discPeers) &&
 111             peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath(this.bestPath.indexOf(path))))
 112             .forEach(path -> writeRoutePath(destPeer, routeId, peerGroup, destPeerSupAddPath, path, rootPath, localTK, ribSup, tx));
 113     }
 114
 115     private void writeRoutePath(final PeerId destPeer, final PathArgument routeId, final PeerExportGroup peerGroup, final boolean destPeerSupAddPath,
 116         final BestPath path, final YangInstanceIdentifier rootPath, final TablesKey localTK, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 117         final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeId);
 118         final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(path.getPeerId(), path.getAttributes());
 119         if (destPeerSupAddPath) {
 120             writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPath, localTK), effectiveAttributes, createValue(routeIdAddPath, path), ribSup, tx);
 121         } else {
 122             writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK), effectiveAttributes, createValue(routeId, path), ribSup, tx);
 123         }
 124     }
 125
 126     private void addPathToDataStore(final BestPath path, final boolean isFirstBestPath, final PathArgument routeIdPA, final YangInstanceIdentifier locRibTarget,
 127         final RIBSupport ribSup, final ExportPolicyPeerTracker peerPT, final TablesKey localTK, final CacheDisconnectedPeers discPeers,
 128         final DOMDataWriteTransaction tx) {
 129         final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeIdPA);
 130         final YangInstanceIdentifier pathAddPathTarget = ribSup.routePath(locRibTarget.node(ROUTES_IDENTIFIER), routeIdAddPath);
 131         final MapEntryNode addPathValue = createValue(routeIdAddPath, path);
 132         final MapEntryNode value = createValue(routeIdPA, path);
 133         LOG.trace("Selected best value {}", addPathValue);
 134         fillLocRib(pathAddPathTarget, addPathValue, tx);
 135         fillAdjRibsOut(isFirstBestPath, path.getAttributes(), value, addPathValue, routeIdPA, routeIdAddPath, path.getPeerId(), peerPT, localTK,
 136             ribSup, discPeers, tx);
 137     }
 138
 139     private void removePathFromDataStore(final BestPath path, final boolean isFirstBestPath, final PathArgument routeIdPA,
 140         final YangInstanceIdentifier locRibTarget, final RIBSupport ribSup, final ExportPolicyPeerTracker peerPT, final TablesKey localTK,
 141         final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx) {
 142         LOG.trace("Best Path removed {}", path);
 143         final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeIdPA);
 144         final YangInstanceIdentifier pathAddPathTarget = ribSup.routePath(locRibTarget.node(ROUTES_IDENTIFIER), routeIdAddPath);
 145
 146         fillLocRib(pathAddPathTarget, null, tx);
 147         fillAdjRibsOut(isFirstBestPath, null, null, null, routeIdPA, routeIdAddPath, path.getPeerId(), peerPT, localTK, ribSup, discPeers, tx);
 148     }
 149
 150     private void fillAdjRibsOut(final boolean isFirstBestPath, final ContainerNode attributes, final NormalizedNode<?, ?> value, final MapEntryNode addPathValue,
 151         final PathArgument routeId, final PathArgument routeIdAddPath, final PeerId routePeerId, final ExportPolicyPeerTracker peerPT, final TablesKey
 152         localTK, final RIBSupport ribSup, final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx) {
 153         /*
 154          * We need to keep track of routers and populate adj-ribs-out, too. If we do not, we need to
 155          * expose from which client a particular route was learned from in the local RIB, and have
 156          * the listener perform filtering.
 157          *
 158          * We walk the policy set in order to minimize the amount of work we do for multiple peers:
 159          * if we have two eBGP peers, for example, there is no reason why we should perform the translation
 160          * multiple times.
 161          */
 162         for (final PeerRole role : PeerRole.values()) {
 163             if (PeerRole.Internal.equals(role)) {
 164                 continue;
 165             }
 166             final PeerExportGroup peerGroup = peerPT.getPeerGroup(role);
 167             if (peerGroup != null) {
 168                 final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(routePeerId, attributes);
 169                 for (final Map.Entry<PeerId, YangInstanceIdentifier> pid : peerGroup.getPeers()) {
 170                     final PeerId destPeer = pid.getKey();
 171                     final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
 172                     if (filterRoutes(routePeerId, destPeer, peerPT, localTK, discPeers) && peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath)) {
 173                         if (destPeerSupAddPath) {
 174                             update(destPeer, getAdjRibOutYII(ribSup, pid.getValue(), routeIdAddPath, localTK), effectiveAttributes, addPathValue,
 175                                 ribSup, tx);
 176                         } else {
 177                             update(destPeer, getAdjRibOutYII(ribSup, pid.getValue(), routeId, localTK), effectiveAttributes, value, ribSup, tx);
 178                         }
 179                     }
 180                 }
 181             }
 182         }
 183     }
 184
 185     private void update(final PeerId destPeer, final YangInstanceIdentifier routeTarget, final ContainerNode effAttr, final NormalizedNode<?, ?> value,
 186         final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 187         if (!writeRoute(destPeer, routeTarget, effAttr, value, ribSup, tx)) {
 188             LOG.trace("Removing {} from transaction for peer {}", routeTarget, destPeer);
 189             tx.delete(LogicalDatastoreType.OPERATIONAL, routeTarget);
 190         }
 191     }
 192
 193     protected final OffsetMap<RouteKey> getOffsets() {
 194         return this.offsets;
 195     }
 196
 197     protected void selectBest(final RouteKey key, final AddPathSelector selector) {
 198         final int offset = this.offsets.offsetOf(key);
 199         final ContainerNode attributes = this.offsets.getValue(this.values, offset);
 200         final Long pathId = this.offsets.getValue(this.pathsId, offset);
 201         LOG.trace("Processing router key {} attributes {}", key, attributes);
 202         selector.processPath(attributes, key, offset, pathId);
 203     }
 204
 205     /**
 206      * Process best path selection
 207      *
 208      * @param localAs The local autonomous system number
 209      * @param keyList List of RouteKey
 210      * @return the best path inside offset map passed
 211      */
 212     protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
 213         /*
 214          * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
 215          */
 216         final AddPathSelector selector = new AddPathSelector(localAs);
 217         keyList.forEach(key -> selectBest(key, selector));
 218         LOG.trace("Best path selected {}", this.bestPath);
 219         return selector.result();
 220     }
 221
 222     protected boolean isFirstBestPath(final int bestPathPosition) {
 223         return bestPathPosition == 0;
 224     }
 225
 226     private boolean peersSupportsAddPathOrIsFirstBestPath(final boolean peerSupportsAddPath, final boolean isFirstBestPath) {
 227         return !(!peerSupportsAddPath && !isFirstBestPath);
 228     }
 229 }