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 com.google.common.primitives.UnsignedInteger;
12 import java.util.ArrayList;
13 import java.util.Collections;
14 import java.util.List;
15 import java.util.Optional;
16 import java.util.stream.Collectors;
17 import javax.annotation.concurrent.NotThreadSafe;
18 import org.opendaylight.protocol.bgp.mode.api.RouteEntry;
19 import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
20 import org.opendaylight.protocol.bgp.rib.spi.entry.ActualBestPathRoutes;
21 import org.opendaylight.protocol.bgp.rib.spi.entry.AdvertizedRoute;
22 import org.opendaylight.protocol.bgp.rib.spi.entry.RouteEntryInfo;
23 import org.opendaylight.protocol.bgp.rib.spi.entry.StaleBestPathRoute;
24 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.Route;
25 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.Tables;
26 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.tables.Routes;
27 import org.opendaylight.yangtools.yang.binding.ChildOf;
28 import org.opendaylight.yangtools.yang.binding.ChoiceIn;
29 import org.opendaylight.yangtools.yang.binding.DataObject;
30 import org.opendaylight.yangtools.yang.binding.Identifiable;
31 import org.opendaylight.yangtools.yang.binding.Identifier;
32 import org.slf4j.Logger;
33 import org.slf4j.LoggerFactory;
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.
43 public abstract class AddPathAbstractRouteEntry<C extends Routes & DataObject & ChoiceIn<Tables>,
44 S extends ChildOf<? super C>,
45 R extends Route & ChildOf<? super S> & Identifiable<I>, I extends Identifier<R>>
46 implements RouteEntry<C, S, R, I> {
48 private static final Logger LOG = LoggerFactory.getLogger(AddPathAbstractRouteEntry.class);
49 private static final Long[] EMPTY_PATHS_ID = new Long[0];
50 private static final Route[] EMPTY_VALUES = new Route[0];
52 protected OffsetMap offsets = OffsetMap.EMPTY;
53 protected R[] values = (R[]) EMPTY_VALUES;
54 protected Long[] pathsId = EMPTY_PATHS_ID;
55 private List<AddPathBestPath> bestPath;
56 private List<AddPathBestPath> bestPathRemoved;
57 private long pathIdCounter = 0L;
58 private boolean isNonAddPathBestPathNew;
59 private List<AddPathBestPath> newBestPathToBeAdvertised;
60 private List<Long> removedPathsId;
62 private R createRoute(final RIBSupport<C, S, R, I> ribSup, final String routeKey,
63 final long pathId, final AddPathBestPath path) {
64 final OffsetMap map = getOffsets();
65 final R route = map.getValue(this.values, map.offsetOf(path.getRouteKey()));
66 return ribSup.createRoute(route, routeKey, pathId, path.getAttributes());
70 public final int addRoute(final UnsignedInteger routerId, final long remotePathId, final R route) {
71 final RouteKey key = new RouteKey(routerId, remotePathId);
72 int offset = this.offsets.offsetOf(key);
74 final OffsetMap newOffsets = this.offsets.with(key);
75 offset = newOffsets.offsetOf(key);
76 final R[] newRoute = newOffsets.expand(this.offsets, this.values, offset);
77 final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset);
78 this.values = newRoute;
79 this.offsets = newOffsets;
80 this.pathsId = newPathsId;
81 this.offsets.setValue(this.pathsId, offset, ++this.pathIdCounter);
83 this.offsets.setValue(this.values, offset, route);
84 LOG.trace("Added route {} from {}", route, key.getRouteId());
89 public final boolean removeRoute(final UnsignedInteger routerId, final long remotePathId) {
90 final RouteKey key = new RouteKey(routerId, remotePathId);
91 final int offset = getOffsets().offsetOf(key);
92 final long pathId = this.offsets.getValue(this.pathsId, offset);
93 this.values = this.offsets.removeValue(this.values, offset, (R[]) EMPTY_VALUES);
94 this.pathsId = this.offsets.removeValue(this.pathsId, offset, EMPTY_PATHS_ID);
95 this.offsets = this.offsets.without(key);
96 if (this.removedPathsId == null) {
97 this.removedPathsId = new ArrayList<>();
99 this.removedPathsId.add(pathId);
104 public final Optional<StaleBestPathRoute<C, S, R, I>> removeStalePaths(final RIBSupport<C, S, R, I> ribSupport,
105 final String routeKey) {
106 if ((this.bestPathRemoved == null || this.bestPathRemoved.isEmpty()) && this.removedPathsId == null) {
107 return Optional.empty();
109 List<Long> stalePaths = Collections.emptyList();
110 if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()) {
111 stalePaths = this.bestPathRemoved.stream().map(AddPathBestPath::getPathId).collect(Collectors.toList());
112 this.bestPathRemoved = null;
114 final StaleBestPathRoute<C, S, R, I> stale = new StaleBestPathRoute<>(ribSupport, routeKey, stalePaths,
115 this.removedPathsId, this.isNonAddPathBestPathNew);
116 this.removedPathsId = null;
117 return Optional.of(stale);
121 public final List<AdvertizedRoute<C, S, R, I>> newBestPaths(final RIBSupport<C, S, R, I> ribSupport,
122 final String routeKey) {
123 if (this.newBestPathToBeAdvertised == null || this.newBestPathToBeAdvertised.isEmpty()) {
124 return Collections.emptyList();
126 final List<AdvertizedRoute<C, S, R, I>> advertized = new ArrayList<>();
127 for (final AddPathBestPath path : this.newBestPathToBeAdvertised) {
128 final boolean isFirstBestPath = isFirstBestPath(this.bestPath.indexOf(path));
129 final R routeAddPath = createRoute(ribSupport, routeKey, path.getPathId(), path);
130 final AdvertizedRoute<C, S, R, I> adv = new AdvertizedRoute<>(ribSupport, isFirstBestPath,
131 routeAddPath, path.getAttributes(), path.getPeerId());
134 this.newBestPathToBeAdvertised = null;
139 public final List<ActualBestPathRoutes<C, S, R, I>> actualBestPaths(final RIBSupport<C, S, R, I> ribSupport,
140 final RouteEntryInfo entryInfo) {
141 if (this.bestPath == null || this.bestPath.isEmpty()) {
142 return Collections.emptyList();
144 final List<ActualBestPathRoutes<C, S, R, I>> preexistentRoutes = new ArrayList<>();
145 for (final AddPathBestPath path : this.bestPath) {
146 final R route = createRoute(ribSupport, entryInfo.getRouteKey(), path.getPathId(), path);
147 final ActualBestPathRoutes<C, S, R, I> adv = new ActualBestPathRoutes<>(ribSupport, route, path.getPeerId(),
148 path.getAttributes());
149 preexistentRoutes.add(adv);
151 return preexistentRoutes;
154 private OffsetMap getOffsets() {
158 public final boolean isEmpty() {
159 return this.offsets.isEmpty();
162 private void selectBest(final RouteKey key, final AddPathSelector selector) {
163 final int offset = this.offsets.offsetOf(key);
164 final R route = this.offsets.getValue(this.values, offset);
165 final long pathId = this.offsets.getValue(this.pathsId, offset);
166 LOG.trace("Processing router key {} route {}", key, route);
167 selector.processPath(route.getAttributes(), key, offset, pathId);
171 * Process best path selection.
173 * @param localAs The local autonomous system number
174 * @param keyList List of RouteKey
175 * @return the best path inside offset map passed
177 protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
179 * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
181 final AddPathSelector selector = new AddPathSelector(localAs);
182 Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
183 LOG.trace("Best path selected {}", this.bestPath);
184 return selector.result();
187 private static boolean isFirstBestPath(final int bestPathPosition) {
188 return bestPathPosition == 0;
191 protected boolean isBestPathNew(final List<AddPathBestPath> newBestPathList) {
192 this.isNonAddPathBestPathNew = !isNonAddPathBestPathTheSame(newBestPathList);
193 filterRemovedPaths(newBestPathList);
194 if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()
195 || newBestPathList != null
196 && !newBestPathList.equals(this.bestPath)) {
197 this.newBestPathToBeAdvertised = new ArrayList<>(newBestPathList);
198 if (this.bestPath != null) {
199 this.newBestPathToBeAdvertised.removeAll(this.bestPath);
201 this.bestPath = newBestPathList;
202 LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
208 private boolean isNonAddPathBestPathTheSame(final List<AddPathBestPath> newBestPathList) {
209 return !(isEmptyOrNull(this.bestPath) || isEmptyOrNull(newBestPathList))
210 && this.bestPath.get(0).equals(newBestPathList.get(0));
213 private static boolean isEmptyOrNull(final List<AddPathBestPath> pathList) {
214 return pathList == null || pathList.isEmpty();
217 private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
218 if (this.bestPath == null) {
221 this.bestPathRemoved = new ArrayList<>(this.bestPath);
222 this.bestPath.forEach(oldBest -> {
223 final Optional<AddPathBestPath> present = newBestPathList.stream()
224 .filter(newBest -> newBest.getPathId() == oldBest.getPathId()
225 && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
226 present.ifPresent(addPathBestPath -> this.bestPathRemoved.remove(oldBest));