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