2 * Copyright (c) 2015 Cisco Systems, Inc. and others. All rights reserved.
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
8 package org.opendaylight.protocol.bgp.mode.impl.add;
10 import com.google.common.collect.Lists;
11 import java.util.ArrayList;
12 import java.util.List;
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;
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.
46 public abstract class AddPathAbstractRouteEntry extends AbstractRouteEntry {
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;
56 private int addRoute(final RouteKey key, final ContainerNode attributes) {
57 int offset = this.offsets.offsetOf(key);
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);
68 this.offsets.setValue(this.values, offset, attributes);
69 LOG.trace("Added route from {} attributes {}", key.getRouteId(), attributes);
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);
82 * @param key RouteKey of removed route
83 * @param offset Offset of removed route
84 * @return true if it was the last route
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);
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;
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));
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));
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);
129 writeRoute(destPeer, getAdjRibOutYII(ribSup, rootPath, routeId, localTK), effectiveAttributes, createValue(routeId, path), ribSup, tx);
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);
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);
153 fillLocRib(pathAddPathTarget, null, tx);
154 fillAdjRibsOut(isFirstBestPath, null, null, null, routeIdPA, routeIdAddPath, path.getPeerId(), peerPT, localTK, ribSup, discPeers, tx);
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) {
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.
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
169 for (final PeerRole role : PeerRole.values()) {
170 final PeerExportGroup peerGroup = peerPT.getPeerGroup(role);
171 if (peerGroup != null) {
172 final ContainerNode effectiveAttributes = peerGroup.effectiveAttributes(getRoutePeerIdRole(peerPT, routePeerId), attributes);
173 for (final Map.Entry<PeerId, PeerExporTuple> pid : peerGroup.getPeers()) {
174 final PeerId destPeer = pid.getKey();
175 final boolean destPeerSupAddPath = peerPT.isAddPathSupportedByPeer(destPeer);
176 if (filterRoutes(routePeerId, destPeer, peerPT, localTK, discPeers, getRoutePeerIdRole(peerPT, destPeer))
177 && peersSupportsAddPathOrIsFirstBestPath(destPeerSupAddPath, isFirstBestPath)) {
178 if (destPeerSupAddPath) {
179 update(destPeer, getAdjRibOutYII(ribSup, pid.getValue().getYii(), routeIdAddPath, localTK), effectiveAttributes,
180 addPathValue, ribSup, tx);
182 update(destPeer, getAdjRibOutYII(ribSup, pid.getValue().getYii(), routeId, localTK), effectiveAttributes, value, ribSup, tx);
190 private void update(final PeerId destPeer, final YangInstanceIdentifier routeTarget, final ContainerNode effAttr, final NormalizedNode<?, ?> value,
191 final RIBSupport ribSup, final DOMDataWriteTransaction tx) {
192 if (!writeRoute(destPeer, routeTarget, effAttr, value, ribSup, tx)) {
193 LOG.trace("Removing {} from transaction for peer {}", routeTarget, destPeer);
194 tx.delete(LogicalDatastoreType.OPERATIONAL, routeTarget);
198 protected final OffsetMap getOffsets() {
202 public final boolean isEmpty() {
203 return this.offsets.isEmpty();
206 private void selectBest(final RouteKey key, final AddPathSelector selector) {
207 final int offset = this.offsets.offsetOf(key);
208 final ContainerNode attributes = this.offsets.getValue(this.values, offset);
209 final Long pathId = this.offsets.getValue(this.pathsId, offset);
210 LOG.trace("Processing router key {} attributes {}", key, attributes);
211 selector.processPath(attributes, key, offset, pathId);
215 * Process best path selection
217 * @param localAs The local autonomous system number
218 * @param keyList List of RouteKey
219 * @return the best path inside offset map passed
221 protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
223 * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
225 final AddPathSelector selector = new AddPathSelector(localAs);
226 Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
227 LOG.trace("Best path selected {}", this.bestPath);
228 return selector.result();
231 private boolean isFirstBestPath(final int bestPathPosition) {
232 return bestPathPosition == 0;
235 private boolean peersSupportsAddPathOrIsFirstBestPath(final boolean peerSupportsAddPath, final boolean isFirstBestPath) {
236 return !(!peerSupportsAddPath && !isFirstBestPath);
239 protected boolean isBestPathNew(final List<AddPathBestPath> newBestPathList) {
240 filterRemovedPaths(newBestPathList);
241 if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty() || newBestPathList != null && !newBestPathList.equals(this.bestPath)) {
242 this.bestPath = newBestPathList;
243 LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
249 private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
250 if(this.bestPath == null) {
253 this.bestPathRemoved = new ArrayList<>(this.bestPath);
254 this.bestPath.forEach(oldBest -> {
255 final Optional<AddPathBestPath> present = newBestPathList.stream()
256 .filter(newBest -> newBest.getPathId() == oldBest.getPathId() && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
257 if(present.isPresent()) {
258 this.bestPathRemoved.remove(oldBest);