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