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             final PeerRole destPeerRole = getRoutePeerIdRole(peerPT, destPeer);
 115             this.bestPath.stream().filter(path -> filterRoutes(path.getPeerId(), destPeer, peerPT, localTK, discPeers, destPeerRole) &&
 116                 peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath(this.bestPath.indexOf(path))))
 117                 .forEach(path -> writeRoutePath(destPeer, routeId, peerPT, peerGroup, destPeerSupAddPath, path, rootPath, localTK, ribSup, tx));
 118         }
 119     }
 120
 121     private void writeRoutePath(final PeerId destPeer, final PathArgument routeId, final ExportPolicyPeerTracker peerPT,
 122         final PeerExportGroup peerGroup, final boolean destPeerSupAddPath,
 123         final BestPath path, final YangInstanceIdentifier rootPath, final TablesKey localTK, final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 124         final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeId);
 125         final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(getRoutePeerIdRole(peerPT,path.getPeerId()), path.getAttributes());
 126         if (destPeerSupAddPath) {
 127             writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeIdAddPath, localTK), effectiveAttributes, createValue(routeIdAddPath, path), ribSup, tx);
 128         } else {
 129             writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK), effectiveAttributes, createValue(routeId, path), ribSup, tx);
 130         }
 131     }
 132
 133     private void addPathToDataStore(final BestPath path, final boolean isFirstBestPath, final PathArgument routeIdPA, final YangInstanceIdentifier locRibTarget,
 134         final RIBSupport ribSup, final ExportPolicyPeerTracker peerPT, final TablesKey localTK, final CacheDisconnectedPeers discPeers,
 135         final DOMDataWriteTransaction tx) {
 136         final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeIdPA);
 137         final YangInstanceIdentifier pathAddPathTarget = ribSup.routePath(locRibTarget.node(ROUTES_IDENTIFIER), routeIdAddPath);
 138         final MapEntryNode addPathValue = createValue(routeIdAddPath, path);
 139         final MapEntryNode value = createValue(routeIdPA, path);
 140         LOG.trace("Selected best value {}", addPathValue);
 141         fillLocRib(pathAddPathTarget, addPathValue, tx);
 142         fillAdjRibsOut(isFirstBestPath, path.getAttributes(), value, addPathValue, routeIdPA, routeIdAddPath, path.getPeerId(), peerPT, localTK,
 143             ribSup, discPeers, tx);
 144     }
 145
 146     private void removePathFromDataStore(final BestPath path, final boolean isFirstBestPath, final PathArgument routeIdPA,
 147         final YangInstanceIdentifier locRibTarget, final RIBSupport ribSup, final ExportPolicyPeerTracker peerPT, final TablesKey localTK,
 148         final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx) {
 149         LOG.trace("Best Path removed {}", path);
 150         final PathArgument routeIdAddPath = ribSup.getRouteIdAddPath(path.getPathId(), routeIdPA);
 151         final YangInstanceIdentifier pathAddPathTarget = ribSup.routePath(locRibTarget.node(ROUTES_IDENTIFIER), routeIdAddPath);
 152
 153         fillLocRib(pathAddPathTarget, null, tx);
 154         fillAdjRibsOut(isFirstBestPath, null, null, null, routeIdPA, routeIdAddPath, path.getPeerId(), peerPT, localTK, ribSup, discPeers, tx);
 155     }
 156
 157     private void fillAdjRibsOut(final boolean isFirstBestPath, final ContainerNode attributes, final NormalizedNode<?, ?> value, final MapEntryNode addPathValue,
 158         final PathArgument routeId, final PathArgument routeIdAddPath, final PeerId routePeerId, final ExportPolicyPeerTracker peerPT, final TablesKey
 159         localTK, final RIBSupport ribSup, final CacheDisconnectedPeers discPeers, final DOMDataWriteTransaction tx) {
 160         /*
 161          * We need to keep track of routers and populate adj-ribs-out, too. If we do not, we need to
 162          * expose from which client a particular route was learned from in the local RIB, and have
 163          * the listener perform filtering.
 164          *
 165          * We walk the policy set in order to minimize the amount of work we do for multiple peers:
 166          * if we have two eBGP peers, for example, there is no reason why we should perform the translation
 167          * multiple times.
 168          */
 169         for (final PeerRole role : PeerRole.values()) {
 170             final PeerExportGroup peerGroup = peerPT.getPeerGroup(role);
 171             if (peerGroup != null) {
 172                 final PeerRole destPeerRole = getRoutePeerIdRole(peerPT, routePeerId);
 173                 final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(destPeerRole, attributes);
 174                 for (final Map.Entry<PeerId, PeerExporTuple> pid : peerGroup.getPeers()) {
 175                     final PeerId destPeer = pid.getKey();
 176                     final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
 177                     if (filterRoutes(routePeerId, destPeer, peerPT, localTK, discPeers, destPeerRole) && peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath)) {
 178                         if (destPeerSupAddPath) {
 179                             update(destPeer, getAdjRibOutYII(ribSup, pid.getValue().getYii(), routeIdAddPath, localTK), effectiveAttributes,
 180                                 addPathValue,
 181                                 ribSup, tx);
 182                         } else {
 183                             update(destPeer, getAdjRibOutYII(ribSup, pid.getValue().getYii(), routeId, localTK), effectiveAttributes, value, ribSup, tx);
 184                         }
 185                     }
 186                 }
 187             }
 188         }
 189     }
 190
 191     private void update(final PeerId destPeer, final YangInstanceIdentifier routeTarget, final ContainerNode effAttr, final NormalizedNode<?, ?> value,
 192         final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
 193         if (!writeRoute(destPeer, routeTarget, effAttr, value, ribSup, tx)) {
 194             LOG.trace("Removing {} from transaction for peer {}", routeTarget, destPeer);
 195             tx.delete(LogicalDatastoreType.OPERATIONAL, routeTarget);
 196         }
 197     }
 198
 199     protected final OffsetMap getOffsets() {
 200         return this.offsets;
 201     }
 202
 203     public final boolean isEmpty() {
 204         return this.offsets.isEmpty();
 205     }
 206
 207     private void selectBest(final RouteKey key, final AddPathSelector selector) {
 208         final int offset = this.offsets.offsetOf(key);
 209         final ContainerNode attributes = this.offsets.getValue(this.values, offset);
 210         final Long pathId = this.offsets.getValue(this.pathsId, offset);
 211         LOG.trace("Processing router key {} attributes {}", key, attributes);
 212         selector.processPath(attributes, key, offset, pathId);
 213     }
 214
 215     /**
 216      * Process best path selection
 217      *
 218      * @param localAs The local autonomous system number
 219      * @param keyList List of RouteKey
 220      * @return the best path inside offset map passed
 221      */
 222     protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
 223         /*
 224          * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
 225          */
 226         final AddPathSelector selector = new AddPathSelector(localAs);
 227         Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
 228         LOG.trace("Best path selected {}", this.bestPath);
 229         return selector.result();
 230     }
 231
 232     private boolean isFirstBestPath(final int bestPathPosition) {
 233         return bestPathPosition == 0;
 234     }
 235
 236     private boolean peersSupportsAddPathOrIsFirstBestPath(final boolean peerSupportsAddPath, final boolean isFirstBestPath) {
 237         return !(!peerSupportsAddPath && !isFirstBestPath);
 238     }
 239
 240     protected boolean isBestPathNew(final List<AddPathBestPath> newBestPathList) {
 241         filterRemovedPaths(newBestPathList);
 242         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty() || newBestPathList != null && !newBestPathList.equals(this.bestPath)) {
 243             this.bestPath = newBestPathList;
 244             LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
 245             return true;
 246         }
 247         return false;
 248     }
 249
 250     private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
 251         if(this.bestPath == null) {
 252             return;
 253         }
 254         this.bestPathRemoved = new ArrayList<>(this.bestPath);
 255         this.bestPath.forEach(oldBest -> {
 256             final Optional<AddPathBestPath> present = newBestPathList.stream()
 257                 .filter(newBest -> newBest.getPathId() == oldBest.getPathId() && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
 258             if(present.isPresent()) {
 259                 this.bestPathRemoved.remove(oldBest);
 260             }
 261         });
 262     }
 263 }