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