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 static com.google.common.base.Verify.verifyNotNull;
11 import static org.opendaylight.protocol.bgp.parser.spi.PathIdUtil.NON_PATH_ID;
12 import static org.opendaylight.protocol.bgp.parser.spi.PathIdUtil.NON_PATH_ID_VALUE;
14 import com.google.common.collect.ImmutableList;
15 import com.google.common.collect.Lists;
16 import java.util.ArrayList;
17 import java.util.Collections;
18 import java.util.List;
19 import java.util.Optional;
20 import java.util.stream.Collectors;
21 import org.opendaylight.protocol.bgp.mode.api.RouteEntry;
22 import org.opendaylight.protocol.bgp.mode.impl.BestPathStateImpl;
23 import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
24 import org.opendaylight.protocol.bgp.rib.spi.RouterId;
25 import org.opendaylight.protocol.bgp.rib.spi.entry.ActualBestPathRoutes;
26 import org.opendaylight.protocol.bgp.rib.spi.entry.AdvertizedRoute;
27 import org.opendaylight.protocol.bgp.rib.spi.entry.RouteEntryInfo;
28 import org.opendaylight.protocol.bgp.rib.spi.entry.StaleBestPathRoute;
29 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.message.rev180329.PathId;
30 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.Route;
31 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.Tables;
32 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.tables.Routes;
33 import org.opendaylight.yangtools.yang.binding.ChildOf;
34 import org.opendaylight.yangtools.yang.binding.ChoiceIn;
35 import org.opendaylight.yangtools.yang.binding.DataObject;
36 import org.opendaylight.yangtools.yang.binding.Identifiable;
37 import org.opendaylight.yangtools.yang.binding.Identifier;
38 import org.slf4j.Logger;
39 import org.slf4j.LoggerFactory;
42 * A single route entry inside a route table. Maintains the attributes from all contributing peers. The information is
43 * stored in arrays with a shared map of offsets for peers to allow lookups. This is needed to maintain low memory
44 * overhead in face of large number of routes and peers, where individual object overhead becomes the dominating factor.
47 * This class is NOT thread-safe.
49 public abstract class AddPathAbstractRouteEntry<C extends Routes & DataObject & ChoiceIn<Tables>,
50 S extends ChildOf<? super C>, R extends Route & ChildOf<? super S> & Identifiable<I>, I extends Identifier<R>>
51 implements RouteEntry<C, S, R, I> {
52 private static final class Stale<C extends Routes & DataObject & ChoiceIn<Tables>,
53 S extends ChildOf<? super C>, R extends Route & ChildOf<? super S> & Identifiable<I>,
54 I extends Identifier<R>> extends StaleBestPathRoute<C, S, R, I> {
55 private final List<I> addPathRouteKeyIdentifier;
56 private final List<I> staleRouteKeyIdentifier;
57 private final boolean isNonAddPathBestPathNew;
59 Stale(final RIBSupport<C, S, R, I> ribSupport, final String routeKey, final List<PathId> staleRoutesPathIds,
60 final List<PathId> withdrawalRoutePathIds, final boolean isNonAddPathBestPathNew) {
61 super(ribSupport.createRouteListKey(routeKey));
62 this.isNonAddPathBestPathNew = isNonAddPathBestPathNew;
64 this.staleRouteKeyIdentifier = staleRoutesPathIds.stream()
65 .map(pathId -> ribSupport.createRouteListKey(pathId, routeKey)).collect(Collectors.toList());
66 if (withdrawalRoutePathIds != null) {
67 this.addPathRouteKeyIdentifier = withdrawalRoutePathIds.stream()
68 .map(pathId -> ribSupport.createRouteListKey(pathId, routeKey)).collect(Collectors.toList());
70 this.addPathRouteKeyIdentifier = Collections.emptyList();
75 public List<I> getStaleRouteKeyIdentifiers() {
76 return this.staleRouteKeyIdentifier;
80 public List<I> getAddPathRouteKeyIdentifiers() {
81 return addPathRouteKeyIdentifier;
85 public boolean isNonAddPathBestPathNew() {
86 return isNonAddPathBestPathNew;
90 private static final Logger LOG = LoggerFactory.getLogger(AddPathAbstractRouteEntry.class);
91 private static final Long[] EMPTY_PATHS_ID = new Long[0];
92 private static final Route[] EMPTY_VALUES = new Route[0];
94 private RouteKeyOffsets offsets = RouteKeyOffsets.EMPTY;
95 private R[] values = (R[]) EMPTY_VALUES;
96 private Long[] pathsId = EMPTY_PATHS_ID;
97 private List<AddPathBestPath> bestPath;
98 private List<AddPathBestPath> bestPathRemoved;
99 private List<AddPathBestPath> newBestPathToBeAdvertised;
100 private List<Long> removedPathsId;
102 private long pathIdCounter = 0L;
103 private boolean isNonAddPathBestPathNew;
105 private R createRoute(final RIBSupport<C, S, R, I> ribSup, final String routeKey, final AddPathBestPath path) {
106 final RouteKeyOffsets map = this.offsets;
107 final R route = map.getValue(this.values, map.offsetOf(path.getRouteKey()));
108 return ribSup.createRoute(route, ribSup.createRouteListKey(pathIdObj(path.getPathIdLong()), routeKey),
109 path.getAttributes());
113 public final int addRoute(final RouterId routerId, final Long remotePathId, final R route) {
114 final RouteKey key = new RouteKey(routerId, remotePathId);
115 int offset = this.offsets.offsetOf(key);
117 final RouteKeyOffsets newOffsets = this.offsets.with(key);
118 offset = newOffsets.offsetOf(key);
119 final R[] newRoute = newOffsets.expand(this.offsets, this.values, offset);
120 final Long[] newPathsId = newOffsets.expand(this.offsets, this.pathsId, offset);
121 this.values = newRoute;
122 this.offsets = newOffsets;
123 this.pathsId = newPathsId;
124 this.offsets.setValue(this.pathsId, offset, ++this.pathIdCounter);
126 this.offsets.setValue(this.values, offset, route);
127 LOG.trace("Added route {} from {}", route, routerId);
132 public final boolean removeRoute(final RouterId routerId, final Long remotePathId) {
133 final RouteKey key = new RouteKey(routerId, remotePathId);
134 final int offset = this.offsets.offsetOf(key);
135 final Long pathId = this.offsets.getValue(this.pathsId, offset);
136 this.values = this.offsets.removeValue(this.values, offset, (R[]) EMPTY_VALUES);
137 this.pathsId = this.offsets.removeValue(this.pathsId, offset, EMPTY_PATHS_ID);
138 this.offsets = this.offsets.without(key);
139 if (this.removedPathsId == null) {
140 this.removedPathsId = new ArrayList<>();
142 this.removedPathsId.add(pathId);
143 return this.offsets.isEmpty();
147 public final Optional<StaleBestPathRoute<C, S, R, I>> removeStalePaths(final RIBSupport<C, S, R, I> ribSupport,
148 final String routeKey) {
149 final List<PathId> stalePaths;
150 if (bestPathRemoved != null && !bestPathRemoved.isEmpty()) {
151 stalePaths = bestPathRemoved.stream().map(AddPathBestPath::getPathId)
152 .map(AddPathAbstractRouteEntry::pathIdObj).collect(Collectors.toList());
153 bestPathRemoved = null;
155 stalePaths = Collections.emptyList();
158 List<PathId> removedPaths;
159 if (removedPathsId != null) {
160 removedPaths = Lists.transform(removedPathsId, AddPathAbstractRouteEntry::pathIdObj);
161 this.removedPathsId = null;
163 removedPaths = Collections.emptyList();
166 return stalePaths.isEmpty() && removedPaths.isEmpty() ? Optional.empty()
167 : Optional.of(new Stale<>(ribSupport, routeKey, stalePaths, removedPaths, isNonAddPathBestPathNew));
171 public final List<AdvertizedRoute<C, S, R, I>> newBestPaths(final RIBSupport<C, S, R, I> ribSupport,
172 final String routeKey) {
173 if (this.newBestPathToBeAdvertised == null || this.newBestPathToBeAdvertised.isEmpty()) {
174 return Collections.emptyList();
176 final List<AdvertizedRoute<C, S, R, I>> advertized = new ArrayList<>(newBestPathToBeAdvertised.size());
177 final AddPathBestPath firstBestPath = this.bestPath.isEmpty() ? null : this.bestPath.get(0);
178 for (final AddPathBestPath path : this.newBestPathToBeAdvertised) {
179 final R routeAddPath = createRoute(ribSupport, routeKey, path);
180 // FIXME: can we use identity check here?
181 final boolean isFirstBestPath = firstBestPath != null && firstBestPath.equals(path);
182 final AdvertizedRoute<C, S, R, I> adv = new AdvertizedRoute<>(ribSupport, isFirstBestPath,
183 routeAddPath, path.getAttributes(), path.getPeerId(), path.isDepreferenced());
186 this.newBestPathToBeAdvertised = null;
191 public final List<ActualBestPathRoutes<C, S, R, I>> actualBestPaths(final RIBSupport<C, S, R, I> ribSupport,
192 final RouteEntryInfo entryInfo) {
193 if (this.bestPath == null || this.bestPath.isEmpty()) {
194 return Collections.emptyList();
196 final List<ActualBestPathRoutes<C, S, R, I>> preexistentRoutes = new ArrayList<>();
197 for (final AddPathBestPath path : this.bestPath) {
198 final R route = createRoute(ribSupport, entryInfo.getRouteKey(), path);
199 final ActualBestPathRoutes<C, S, R, I> adv = new ActualBestPathRoutes<>(ribSupport, route, path.getPeerId(),
200 path.getAttributes(), path.isDepreferenced());
201 preexistentRoutes.add(adv);
203 return preexistentRoutes;
207 public final boolean selectBest(final long localAs) {
209 return isBestPathNew((size = offsets.size()) == 0 ? ImmutableList.of() : selectBest(localAs, size));
212 protected abstract ImmutableList<AddPathBestPath> selectBest(long localAs, int size);
215 * Process a specific route offset into specified selector.
217 * @param selector selector to update
218 * @param offset offset to process
220 protected final void processOffset(final AddPathSelector selector, final int offset) {
221 final RouteKey key = offsets.getKey(offset);
222 final R route = offsets.getValue(values, offset);
223 final Long pathId = offsets.getValue(pathsId, offset);
224 LOG.trace("Processing router key {} route {}", key, route);
225 selector.processPath(route.getAttributes(), key, offset, pathId);
228 protected final AddPathBestPath bestPathAt(final int offset) {
229 final Route route = verifyNotNull(offsets.getValue(values, offset));
230 return new AddPathBestPath(new BestPathStateImpl(route.getAttributes()), offsets.getKey(offset),
231 offsets.getValue(pathsId, offset), offset);
234 private boolean isBestPathNew(final ImmutableList<AddPathBestPath> newBestPathList) {
235 this.isNonAddPathBestPathNew = !isNonAddPathBestPathTheSame(newBestPathList);
236 filterRemovedPaths(newBestPathList);
237 if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()
238 || newBestPathList != null
239 && !newBestPathList.equals(this.bestPath)) {
240 if (this.bestPath != null) {
241 this.newBestPathToBeAdvertised = new ArrayList<>(newBestPathList);
242 this.newBestPathToBeAdvertised.removeAll(this.bestPath);
244 this.newBestPathToBeAdvertised = newBestPathList;
246 this.bestPath = newBestPathList;
247 LOG.trace("Actual Best {}, removed best {}", this.bestPath, this.bestPathRemoved);
253 private boolean isNonAddPathBestPathTheSame(final List<AddPathBestPath> newBestPathList) {
254 return !(isEmptyOrNull(this.bestPath) || isEmptyOrNull(newBestPathList))
255 && this.bestPath.get(0).equals(newBestPathList.get(0));
258 private static boolean isEmptyOrNull(final List<AddPathBestPath> pathList) {
259 return pathList == null || pathList.isEmpty();
262 private void filterRemovedPaths(final List<AddPathBestPath> newBestPathList) {
263 if (this.bestPath == null) {
266 this.bestPathRemoved = new ArrayList<>(this.bestPath);
267 this.bestPath.forEach(oldBest -> {
268 final Optional<AddPathBestPath> present = newBestPathList.stream()
269 .filter(newBest -> newBest.getPathId() == oldBest.getPathId()
270 && newBest.getRouteKey() == oldBest.getRouteKey()).findAny();
271 present.ifPresent(addPathBestPath -> this.bestPathRemoved.remove(oldBest));
275 private static PathId pathIdObj(final Long pathId) {
276 return pathId == NON_PATH_ID_VALUE ? NON_PATH_ID : new PathId(pathId);