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