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