Fix addpath selection performance

As it turns out, the two selection modes operate under completely
different assuptions, rendering
AddPathAbstractRouteEntry.selectBest() utterly useless.

Specialize N-path and All-path selectors to operate in the offset
order, which makes it clear OffsetMap.getRouteKeys() is unneeded
and that a simple offset-based helper,
AddPathAbstractRouteEntry.processOffset() is all that we need to
efficiently select paths.

Also switch N-path to use int, which is more than enough to cover
the uint8 range we really need.

The end result is that we make minimal memory allocations to
fulfill the needed functionality while also improving access
locality, while side-stepping offsetOf() searches.

For bonus points, we get to completely hide RouteKey, OffsetMap,
the AddPathBestPath constructor and all AddPathAbstractRouteEntry
fields.

Change-Id: Ia68cd3f88aef04a04506f3a2cc96d04485c19ad9
Signed-off-by: Robert Varga <robert.varga@pantheon.tech>

diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java
index 02aef5337285c33b48313cbe80bc4f431762677d..2854630872e593dcc47164f89fd5741f92529355 100644 (file)
--- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java
+++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathAbstractRouteEntry.java
@@ -7,11 +7,11 @@
  */
 package org.opendaylight.protocol.bgp.mode.impl.add;
 
+import static com.google.common.base.Verify.verifyNotNull;
 import static org.opendaylight.protocol.bgp.parser.spi.PathIdUtil.NON_PATH_ID;
 import static org.opendaylight.protocol.bgp.parser.spi.PathIdUtil.NON_PATH_ID_VALUE;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.collect.Lists;
 import com.google.common.primitives.UnsignedInteger;
 import java.util.ArrayList;
 import java.util.Collections;
@@ -20,6 +20,7 @@ import java.util.Optional;
 import java.util.stream.Collectors;
 import javax.annotation.concurrent.NotThreadSafe;
 import org.opendaylight.protocol.bgp.mode.api.RouteEntry;
+import org.opendaylight.protocol.bgp.mode.impl.BestPathStateImpl;
 import org.opendaylight.protocol.bgp.rib.spi.RIBSupport;
 import org.opendaylight.protocol.bgp.rib.spi.entry.ActualBestPathRoutes;
 import org.opendaylight.protocol.bgp.rib.spi.entry.AdvertizedRoute;
@@ -54,18 +55,19 @@ public abstract class AddPathAbstractRouteEntry<C extends Routes & DataObject &
     private static final Long[] EMPTY_PATHS_ID = new Long[0];
     private static final Route[] EMPTY_VALUES = new Route[0];
 
-    protected OffsetMap offsets = OffsetMap.EMPTY;
-    protected R[] values = (R[]) EMPTY_VALUES;
-    protected Long[] pathsId = EMPTY_PATHS_ID;
+    private OffsetMap offsets = OffsetMap.EMPTY;
+    private R[] values = (R[]) EMPTY_VALUES;
+    private Long[] pathsId = EMPTY_PATHS_ID;
     private List<AddPathBestPath> bestPath;
     private List<AddPathBestPath> bestPathRemoved;
-    private long pathIdCounter = 0L;
-    private boolean isNonAddPathBestPathNew;
     private List<AddPathBestPath> newBestPathToBeAdvertised;
     private List<Long> removedPathsId;
 
+    private long pathIdCounter = 0L;
+    private boolean isNonAddPathBestPathNew;
+
     private R createRoute(final RIBSupport<C, S, R, I> ribSup, final String routeKey, final AddPathBestPath path) {
-        final OffsetMap map = getOffsets();
+        final OffsetMap map = this.offsets;
         final R route = map.getValue(this.values, map.offsetOf(path.getRouteKey()));
         return ribSup.createRoute(route, ribSup.createRouteListKey(pathIdObj(path.getPathIdLong()), routeKey),
             path.getAttributes());
@@ -93,7 +95,7 @@ public abstract class AddPathAbstractRouteEntry<C extends Routes & DataObject &
     @Override
     public final boolean removeRoute(final UnsignedInteger routerId, final Long remotePathId) {
         final RouteKey key = new RouteKey(routerId, remotePathId);
-        final int offset = getOffsets().offsetOf(key);
+        final int offset = this.offsets.offsetOf(key);
         final Long pathId = this.offsets.getValue(this.pathsId, offset);
         this.values = this.offsets.removeValue(this.values, offset, (R[]) EMPTY_VALUES);
         this.pathsId = this.offsets.removeValue(this.pathsId, offset, EMPTY_PATHS_ID);
@@ -102,7 +104,7 @@ public abstract class AddPathAbstractRouteEntry<C extends Routes & DataObject &
             this.removedPathsId = new ArrayList<>();
         }
         this.removedPathsId.add(pathId);
-        return isEmpty();
+        return this.offsets.isEmpty();
     }
 
     @Override
@@ -158,40 +160,35 @@ public abstract class AddPathAbstractRouteEntry<C extends Routes & DataObject &
         return preexistentRoutes;
     }
 
-    private OffsetMap getOffsets() {
-        return this.offsets;
+    @Override
+    public final boolean selectBest(final long localAs) {
+        final int size;
+        return isBestPathNew((size = offsets.size()) == 0 ? ImmutableList.of() : selectBest(localAs, size));
     }
 
-    public final boolean isEmpty() {
-        return this.offsets.isEmpty();
-    }
+    protected abstract ImmutableList<AddPathBestPath> selectBest(long localAs, int size);
 
-    private void selectBest(final RouteKey key, final AddPathSelector selector) {
-        final int offset = this.offsets.offsetOf(key);
-        final R route = this.offsets.getValue(this.values, offset);
-        final Long pathId = this.offsets.getValue(this.pathsId, offset);
+    /**
+     * Process a specific route offset into specified selector.
+     *
+     * @param selector selector to update
+     * @param offset offset to process
+     */
+    protected final void processOffset(final AddPathSelector selector, final int offset) {
+        final RouteKey key = offsets.getKey(offset);
+        final R route = offsets.getValue(values, offset);
+        final Long pathId = offsets.getValue(pathsId, offset);
         LOG.trace("Processing router key {} route {}", key, route);
         selector.processPath(route.getAttributes(), key, offset, pathId);
     }
 
-    /**
-     * Process best path selection.
-     *
-     * @param localAs The local autonomous system number
-     * @param keyList List of RouteKey
-     * @return the best path inside offset map passed
-     */
-    protected AddPathBestPath selectBest(final long localAs, final List<RouteKey> keyList) {
-        /*
-         * FIXME: optimize flaps by making sure we consider stability of currently-selected route.
-         */
-        final AddPathSelector selector = new AddPathSelector(localAs);
-        Lists.reverse(keyList).forEach(key -> selectBest(key, selector));
-        LOG.trace("Best path selected {}", this.bestPath);
-        return selector.result();
+    protected final AddPathBestPath bestPathAt(final int offset) {
+        final Route route = verifyNotNull(offsets.getValue(values, offset));
+        return new AddPathBestPath(new BestPathStateImpl(route.getAttributes()), offsets.getKey(offset),
+            offsets.getValue(pathsId, offset), offset);
     }
 
-    protected boolean isBestPathNew(final ImmutableList<AddPathBestPath> newBestPathList) {
+    private boolean isBestPathNew(final ImmutableList<AddPathBestPath> newBestPathList) {
         this.isNonAddPathBestPathNew = !isNonAddPathBestPathTheSame(newBestPathList);
         filterRemovedPaths(newBestPathList);
         if (this.bestPathRemoved != null && !this.bestPathRemoved.isEmpty()

diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathBestPath.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathBestPath.java
index 330fab90f6adada71847afb3313f6c953c90a88c..2053138ca0d71b7bde2dbadee900083523879eb7 100644 (file)
--- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathBestPath.java
+++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/AddPathBestPath.java
@@ -22,7 +22,7 @@ public final class AddPathBestPath extends AbstractBestPath {
     private final Long pathId;
     private final int offset;
 
-    public AddPathBestPath(@Nonnull final BestPathState state, @Nonnull final RouteKey key, final @Nonnull Long pathId,
+    AddPathBestPath(@Nonnull final BestPathState state, @Nonnull final RouteKey key, final @Nonnull Long pathId,
             final int offset) {
         super(state);
         this.routeKey = requireNonNull(key);
@@ -30,7 +30,7 @@ public final class AddPathBestPath extends AbstractBestPath {
         this.offset = offset;
     }
 
-    public RouteKey getRouteKey() {
+    RouteKey getRouteKey() {
         return this.routeKey;
     }
 
@@ -98,7 +98,7 @@ public final class AddPathBestPath extends AbstractBestPath {
      *
      * @return Path Id as a {@link Long}
      */
-    public @Nonnull Long getPathIdLong() {
+    @Nonnull Long getPathIdLong() {
         return this.pathId;
     }
 }

diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/OffsetMap.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/OffsetMap.java
index e42328069ee8d938f51b4f265eee77149bbc3c4c..0bb0af00574e1aab260c8421adb9855f860a85db 100644 (file)
--- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/OffsetMap.java
+++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/OffsetMap.java
@@ -17,9 +17,7 @@ import java.lang.reflect.Array;
 import java.util.Arrays;
 import java.util.Collections;
 import java.util.Comparator;
-import java.util.List;
 import java.util.Set;
-import java.util.stream.Collectors;
 import javax.annotation.Nonnull;
 import org.slf4j.Logger;
 import org.slf4j.LoggerFactory;
@@ -31,7 +29,7 @@ import org.slf4j.LoggerFactory;
  * We also provide utility reformat methods, which provide access to
  * array members and array management features.
  */
-public final class OffsetMap {
+final class OffsetMap {
     private static final Logger LOG = LoggerFactory.getLogger(OffsetMap.class);
     private static final String NEGATIVEOFFSET = "Invalid negative offset %s";
     private static final String INVALIDOFFSET = "Invalid offset %s for %s router IDs";
@@ -54,15 +52,15 @@ public final class OffsetMap {
         this.routeKeys = array;
     }
 
-    public int offsetOf(final RouteKey key) {
+    int offsetOf(final RouteKey key) {
         return Arrays.binarySearch(this.routeKeys, key, COMPARATOR);
     }
 
-    public int size() {
+    int size() {
         return this.routeKeys.length;
     }
 
-    public OffsetMap with(final RouteKey key) {
+    OffsetMap with(final RouteKey key) {
         // TODO: we could make this faster if we had an array-backed Set and requiring
         //       the caller to give us the result of offsetOf() -- as that indicates
         //       where to insert the new routerId while maintaining the sorted nature
@@ -74,7 +72,7 @@ public final class OffsetMap {
         return OFFSETMAPS.getUnchecked(builder.build());
     }
 
-    public OffsetMap without(final RouteKey key) {
+    OffsetMap without(final RouteKey key) {
         final Builder<RouteKey> builder = ImmutableSet.builder();
         final int index = indexOfRouterId(key);
         if (index < 0) {
@@ -94,19 +92,23 @@ public final class OffsetMap {
         return -1;
     }
 
-    public <T> T getValue(final T[] array, final int offset) {
+    RouteKey getKey(final int offset) {
+        return routeKeys[offset];
+    }
+
+    <T> T getValue(final T[] array, final int offset) {
         Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
         Preconditions.checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, this.routeKeys.length);
         return array[offset];
     }
 
-    public <T> void setValue(final T[] array, final int offset, final T value) {
+    <T> void setValue(final T[] array, final int offset, final T value) {
         Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
         Preconditions.checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, this.routeKeys.length);
         array[offset] = value;
     }
 
-    public <T> T[] expand(final OffsetMap oldOffsets, final T[] oldArray, final int offset) {
+    <T> T[] expand(final OffsetMap oldOffsets, final T[] oldArray, final int offset) {
         @SuppressWarnings("unchecked")
         final T[] ret = (T[]) Array.newInstance(oldArray.getClass().getComponentType(), this.routeKeys.length);
         final int oldSize = oldOffsets.routeKeys.length;
@@ -117,7 +119,7 @@ public final class OffsetMap {
         return ret;
     }
 
-    public <T> T[] removeValue(final T[] oldArray, final int offset, final T[] emptyArray) {
+    <T> T[] removeValue(final T[] oldArray, final int offset, final T[] emptyArray) {
         final int length = oldArray.length;
         Preconditions.checkArgument(offset >= 0, NEGATIVEOFFSET, offset);
         Preconditions.checkArgument(offset < this.routeKeys.length, INVALIDOFFSET, offset, length);
@@ -140,8 +142,4 @@ public final class OffsetMap {
     boolean isEmpty() {
         return this.size() == 0;
     }
-
-    public List<RouteKey> getRouteKeysList() {
-        return Arrays.stream(this.routeKeys).collect(Collectors.toList());
-    }
 }
\ No newline at end of file

diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/RouteKey.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/RouteKey.java
index 24bc8e793b04610072566c324d95e541082a02bd..1528a0331268b34a0fca5bdb25e34649d73b3a4f 100644 (file)
--- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/RouteKey.java
+++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/RouteKey.java
@@ -16,7 +16,7 @@ import org.eclipse.jdt.annotation.Nullable;
 import org.opendaylight.yangtools.concepts.Immutable;
 
 @NonNullByDefault
-public final class RouteKey implements Comparable<RouteKey>, Immutable {
+final class RouteKey implements Comparable<RouteKey>, Immutable {
     private final UnsignedInteger routerId;
     private final long remotePathId;
 

diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/AllPathsRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/AllPathsRouteEntry.java
index 3259c03551adb0a823da513b60dbb3b04773deb9..8b8c8edaae8b1209ee04b0b5d7054e8c4c40b339 100644 (file)
--- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/AllPathsRouteEntry.java
+++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/all/paths/AllPathsRouteEntry.java
@@ -9,13 +9,10 @@
 package org.opendaylight.protocol.bgp.mode.impl.add.all.paths;
 
 import com.google.common.collect.ImmutableList;
-import java.util.ArrayList;
-import java.util.List;
-import org.opendaylight.protocol.bgp.mode.api.BestPathState;
-import org.opendaylight.protocol.bgp.mode.impl.BestPathStateImpl;
+import com.google.common.collect.ImmutableList.Builder;
 import org.opendaylight.protocol.bgp.mode.impl.add.AddPathAbstractRouteEntry;
 import org.opendaylight.protocol.bgp.mode.impl.add.AddPathBestPath;
-import org.opendaylight.protocol.bgp.mode.impl.add.RouteKey;
+import org.opendaylight.protocol.bgp.mode.impl.add.AddPathSelector;
 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.Route;
 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.Tables;
 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.tables.Routes;
@@ -24,35 +21,37 @@ import org.opendaylight.yangtools.yang.binding.ChoiceIn;
 import org.opendaylight.yangtools.yang.binding.DataObject;
 import org.opendaylight.yangtools.yang.binding.Identifiable;
 import org.opendaylight.yangtools.yang.binding.Identifier;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
 
 final class AllPathsRouteEntry<C extends Routes & DataObject & ChoiceIn<Tables>, S extends ChildOf<? super C>,
         R extends Route & ChildOf<? super S> & Identifiable<I>, I extends Identifier<R>>
         extends AddPathAbstractRouteEntry<C, S, R, I> {
-    AllPathsRouteEntry() {
-    }
+    private static final Logger LOG = LoggerFactory.getLogger(AllPathsRouteEntry.class);
 
     @Override
-    public boolean selectBest(final long localAs) {
-        final List<AddPathBestPath> newBestPathList = new ArrayList<>();
-        final List<RouteKey> keyList = this.offsets.getRouteKeysList();
-
-        if (!keyList.isEmpty()) {
-            /* we set the best path first on List for not supported Add path cases*/
-            final AddPathBestPath newBest = selectBest(localAs, keyList);
-            newBestPathList.add(newBest);
-            keyList.remove(newBest.getRouteKey());
-            /*we add the rest of path, regardless in what order they are, since this is all path case */
-            for (final RouteKey key : keyList) {
-                final int offset = this.offsets.offsetOf(key);
-                final Route route = this.offsets.getValue(this.values, offset);
-                if (route != null) {
-                    final BestPathState state = new BestPathStateImpl(route.getAttributes());
-                    final AddPathBestPath bestPath = new AddPathBestPath(state, key,
-                            this.offsets.getValue(this.pathsId, offset), offset);
-                    newBestPathList.add(bestPath);
-                }
-            }
+    protected ImmutableList<AddPathBestPath> selectBest(final long localAs, final int size) {
+        // Select the best path for the case when AddPath is not supported
+        final AddPathSelector selector = new AddPathSelector(localAs);
+        for (int offset = 0; offset < size; ++offset) {
+            processOffset(selector, offset);
         }
-        return isBestPathNew(ImmutableList.copyOf(newBestPathList));
+
+        final AddPathBestPath newBest = selector.result();
+        LOG.trace("Best path selected {}", newBest);
+
+        final Builder<AddPathBestPath> builder = ImmutableList.builderWithExpectedSize(size);
+        builder.add(newBest);
+
+        // Since we are selecting all paths, add all the other paths, do that in two steps, skipping the selected
+        // route.
+        for (int offset = 0; offset < newBest.getOffset(); ++offset) {
+            builder.add(bestPathAt(offset));
+        }
+        for (int offset = newBest.getOffset() + 1; offset < size; ++offset) {
+            builder.add(bestPathAt(offset));
+        }
+
+        return builder.build();
     }
 }

diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/AddPathBestNPathSelection.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/AddPathBestNPathSelection.java
index 6f2245a8f98fa943a5c12bad0f85e1017ae1cadf..fa3658f8582dfb0f0e11377e97103ad943e9034f 100644 (file)
--- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/AddPathBestNPathSelection.java
+++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/AddPathBestNPathSelection.java
@@ -5,9 +5,10 @@
  * terms of the Eclipse Public License v1.0 which accompanies this distribution,
  * and is available at http://www.eclipse.org/legal/epl-v10.html
  */
-
 package org.opendaylight.protocol.bgp.mode.impl.add.n.paths;
 
+import static com.google.common.base.Preconditions.checkArgument;
+
 import org.opendaylight.protocol.bgp.mode.api.PathSelectionMode;
 import org.opendaylight.protocol.bgp.mode.api.RouteEntry;
 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.Route;
@@ -20,9 +21,10 @@ import org.opendaylight.yangtools.yang.binding.Identifiable;
 import org.opendaylight.yangtools.yang.binding.Identifier;
 
 public final class AddPathBestNPathSelection implements PathSelectionMode {
-    private final long npaths;
+    private final int npaths;
 
-    public AddPathBestNPathSelection(final long npaths) {
+    public AddPathBestNPathSelection(final int npaths) {
+        checkArgument(npaths > 1);
         this.npaths = npaths;
     }
 

diff --git a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/NPathsRouteEntry.java b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/NPathsRouteEntry.java
index ce8ab52e58ad13f1b85a518a8153be03e09e16a6..faba19d103c4fcdb3e93d814f724b96b6849448c 100644 (file)
--- a/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/NPathsRouteEntry.java
+++ b/bgp/path-selection-mode/src/main/java/org/opendaylight/protocol/bgp/mode/impl/add/n/paths/NPathsRouteEntry.java
@@ -9,11 +9,10 @@
 package org.opendaylight.protocol.bgp.mode.impl.add.n.paths;
 
 import com.google.common.collect.ImmutableList;
-import java.util.ArrayList;
-import java.util.List;
+import com.google.common.collect.ImmutableList.Builder;
 import org.opendaylight.protocol.bgp.mode.impl.add.AddPathAbstractRouteEntry;
 import org.opendaylight.protocol.bgp.mode.impl.add.AddPathBestPath;
-import org.opendaylight.protocol.bgp.mode.impl.add.RouteKey;
+import org.opendaylight.protocol.bgp.mode.impl.add.AddPathSelector;
 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.Route;
 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.Tables;
 import org.opendaylight.yang.gen.v1.urn.opendaylight.params.xml.ns.yang.bgp.rib.rev180329.rib.tables.Routes;
@@ -22,27 +21,56 @@ import org.opendaylight.yangtools.yang.binding.ChoiceIn;
 import org.opendaylight.yangtools.yang.binding.DataObject;
 import org.opendaylight.yangtools.yang.binding.Identifiable;
 import org.opendaylight.yangtools.yang.binding.Identifier;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
 
 final class NPathsRouteEntry<C extends Routes & DataObject & ChoiceIn<Tables>, S extends ChildOf<? super C>,
         R extends Route & ChildOf<? super S> & Identifiable<I>, I extends Identifier<R>>
         extends AddPathAbstractRouteEntry<C, S, R, I> {
-    private final long npaths;
+    private static final Logger LOG = LoggerFactory.getLogger(NPathsRouteEntry.class);
 
-    NPathsRouteEntry(final long npaths) {
+    private final int npaths;
+
+    NPathsRouteEntry(final int npaths) {
         this.npaths = npaths;
     }
 
     @Override
-    public boolean selectBest(final long localAs) {
-        final List<AddPathBestPath> newBestPathList = new ArrayList<>();
-        final List<RouteKey> keyList = this.offsets.getRouteKeysList();
-        final long maxSearch = this.npaths < this.offsets.size()
-                && this.npaths != 0 ? this.npaths : this.offsets.size();
-        for (long i = 0; i < maxSearch; ++i) {
-            final AddPathBestPath newBest = selectBest(localAs, keyList);
-            newBestPathList.add(newBest);
-            keyList.remove(newBest.getRouteKey());
+    protected ImmutableList<AddPathBestPath> selectBest(final long localAs, final int size) {
+        final int limit = Math.min(npaths, size);
+        switch (limit) {
+            case 0:
+                return ImmutableList.of();
+            case 1:
+                return ImmutableList.of(bestPathAt(0));
+            default:
+                return selectBest(localAs, size, limit);
         }
-        return isBestPathNew(ImmutableList.copyOf(newBestPathList));
+    }
+
+    private ImmutableList<AddPathBestPath> selectBest(final long localAs, final int size, final int limit) {
+        // Scratch pool of offsets, we set them to true as we use them up.
+        final boolean[] offsets = new boolean[size];
+        final Builder<AddPathBestPath> builder = ImmutableList.builderWithExpectedSize(limit);
+
+        // This ends up being (limit * size) traversals of offsets[], but that should be fine, as it is a dense array.
+        // If this ever becomes a problem, we can optimize by having a AddPathSelector which remembers previous state,
+        // so that we can rewind it. That will allow us to not only skip offset searches, but also recomputing the
+        // (relatively) costly per-path state from scratch.
+        for (int search = 0; search < limit; ++search) {
+            final AddPathSelector selector = new AddPathSelector(localAs);
+            for (int offset = 0; offset < size; ++offset) {
+                if (!offsets[offset]) {
+                    processOffset(selector, offset);
+                }
+            }
+            final AddPathBestPath result = selector.result();
+            LOG.trace("Path {} selected {}", search, result);
+            builder.add(result);
+
+            offsets[result.getOffset()] = true;
+        }
+
+        return builder.build();
     }
 }

diff --git a/bgp/rib-impl/src/main/java/org/opendaylight/protocol/bgp/rib/impl/config/OpenConfigMappingUtil.java b/bgp/rib-impl/src/main/java/org/opendaylight/protocol/bgp/rib/impl/config/OpenConfigMappingUtil.java
index d2b0340350b411900cd78e66c51bc7cd18c8c688..418b383cb43571155b05688b99f0a620987aca42 100644 (file)
--- a/bgp/rib-impl/src/main/java/org/opendaylight/protocol/bgp/rib/impl/config/OpenConfigMappingUtil.java
+++ b/bgp/rib-impl/src/main/java/org/opendaylight/protocol/bgp/rib/impl/config/OpenConfigMappingUtil.java
@@ -228,10 +228,10 @@ final class OpenConfigMappingUtil {
             if (afiSafi2 != null) {
                 final Optional<BgpTableType> bgpTableType = tableTypeRegistry.getTableType(afiSafi.getAfiSafiName());
                 if (bgpTableType.isPresent()) {
-                    final Short sendMax = afiSafi2.getSendMax();
+                    final int sendMax = afiSafi2.getSendMax();
                     final PathSelectionMode selectionMode;
                     if (sendMax > 1) {
-                        selectionMode = new AddPathBestNPathSelection(sendMax.longValue());
+                        selectionMode = new AddPathBestNPathSelection(sendMax);
                     } else {
                         selectionMode = new AllPathSelection();
                     }

diff --git a/bgp/rib-impl/src/test/java/org/opendaylight/protocol/bgp/rib/impl/AddPathNPathsTest.java b/bgp/rib-impl/src/test/java/org/opendaylight/protocol/bgp/rib/impl/AddPathNPathsTest.java
index a8794259ce016f13835cc6d86eacd20eadbc6217..2c2f42f89bd79e2792fb0b0cb2d6d1f5696f0b74 100644 (file)
--- a/bgp/rib-impl/src/test/java/org/opendaylight/protocol/bgp/rib/impl/AddPathNPathsTest.java
+++ b/bgp/rib-impl/src/test/java/org/opendaylight/protocol/bgp/rib/impl/AddPathNPathsTest.java
@@ -35,11 +35,12 @@ public class AddPathNPathsTest extends AbstractAddPathTest {
     private RIBImpl ribImpl;
     private Channel serverChannel;
 
+    @Override
     @Before
     public void setUp() throws Exception {
         super.setUp();
         final TablesKey tk = new TablesKey(Ipv4AddressFamily.class, UnicastSubsequentAddressFamily.class);
-        final Map<TablesKey, PathSelectionMode> pathTables = ImmutableMap.of(tk, new AddPathBestNPathSelection(2L));
+        final Map<TablesKey, PathSelectionMode> pathTables = ImmutableMap.of(tk, new AddPathBestNPathSelection(2));
 
         this.ribImpl = new RIBImpl(this.tableRegistry, new RibId("test-rib"), AS_NUMBER, new BgpId(RIB_ID),
                 this.ribExtension,
@@ -53,6 +54,7 @@ public class AddPathNPathsTest extends AbstractAddPathTest {
         this.serverChannel = channelFuture.channel();
     }
 
+    @Override
     @After
     public void tearDown() throws ExecutionException, InterruptedException {
         waitFutureSuccess(this.serverChannel.close());

diff --git a/bgp/rib-impl/src/test/java/org/opendaylight/protocol/bgp/rib/impl/config/OpenConfigMappingUtilTest.java b/bgp/rib-impl/src/test/java/org/opendaylight/protocol/bgp/rib/impl/config/OpenConfigMappingUtilTest.java
index cb5312229a6be382690e96699e757298ca638093..8515650a4511d0c0526c00080ceae000cc39ab7f 100644 (file)
--- a/bgp/rib-impl/src/test/java/org/opendaylight/protocol/bgp/rib/impl/config/OpenConfigMappingUtilTest.java
+++ b/bgp/rib-impl/src/test/java/org/opendaylight/protocol/bgp/rib/impl/config/OpenConfigMappingUtilTest.java
@@ -27,7 +27,6 @@ import static org.opendaylight.protocol.bgp.rib.impl.config.OpenConfigMappingUti
 import static org.opendaylight.yang.gen.v1.urn.ietf.params.xml.ns.yang.ietf.inet.types.rev130715.IetfInetUtil.INSTANCE;
 
 import com.google.common.collect.ImmutableList;
-import com.google.common.primitives.Shorts;
 import java.math.BigDecimal;
 import java.nio.charset.StandardCharsets;
 import java.util.ArrayList;
@@ -115,8 +114,8 @@ public class OpenConfigMappingUtilTest {
     private static final Ipv4Address CLUSTER_ID = new Ipv4Address("4.3.2.1");
     private static final Ipv4Address LOCAL_HOST = new Ipv4Address("127.0.0.1");
 
-    private static final Long ALL_PATHS = 0L;
-    private static final Long N_PATHS = 2L;
+    private static final Short ALL_PATHS = 0;
+    private static final Short N_PATHS = 2;
     private static final PathSelectionMode ADD_PATH_BEST_N_PATH_SELECTION = new AddPathBestNPathSelection(N_PATHS);
     private static final PathSelectionMode ADD_PATH_BEST_ALL_PATH_SELECTION = new AllPathSelection();
     private static final BgpTableType BGP_TABLE_TYPE_IPV4 = new BgpTableTypeImpl(Ipv4AddressFamily.class,
@@ -146,11 +145,11 @@ public class OpenConfigMappingUtilTest {
         TABLE_TYPES.add(new BgpTableTypeImpl(Ipv4AddressFamily.class, UnicastSubsequentAddressFamily.class));
         TABLE_TYPES.add(new BgpTableTypeImpl(Ipv6AddressFamily.class, UnicastSubsequentAddressFamily.class));
         AFISAFIS.add(new AfiSafiBuilder().setAfiSafiName(IPV4UNICAST.class)
-                .addAugmentation(GlobalAddPathsConfig.class, new GlobalAddPathsConfigBuilder().setReceive(true)
-                        .setSendMax(Shorts.checkedCast(N_PATHS)).build()).build());
+                .addAugmentation(GlobalAddPathsConfig.class, new GlobalAddPathsConfigBuilder().setReceive(Boolean.TRUE)
+                        .setSendMax(N_PATHS).build()).build());
         AFISAFIS.add(new AfiSafiBuilder().setAfiSafiName(IPV6UNICAST.class)
-                .addAugmentation(GlobalAddPathsConfig.class, new GlobalAddPathsConfigBuilder().setReceive(true)
-                        .setSendMax(Shorts.checkedCast(ALL_PATHS)).build()).build());
+                .addAugmentation(GlobalAddPathsConfig.class, new GlobalAddPathsConfigBuilder().setReceive(Boolean.TRUE)
+                        .setSendMax(ALL_PATHS).build()).build());
     }
 
     @Mock
@@ -400,10 +399,10 @@ public class OpenConfigMappingUtilTest {
         final List<AfiSafi> families = new ArrayList<>();
         families.add(new AfiSafiBuilder().setAfiSafiName(IPV4UNICAST.class)
             .addAugmentation(GlobalAddPathsConfig.class, new GlobalAddPathsConfigBuilder()
-                    .setSendMax(Shorts.checkedCast(N_PATHS)).build()).build());
+                    .setSendMax(N_PATHS).build()).build());
         families.add(new AfiSafiBuilder().setAfiSafiName(IPV6UNICAST.class)
             .addAugmentation(GlobalAddPathsConfig.class, new GlobalAddPathsConfigBuilder()
-                    .setSendMax(Shorts.checkedCast(ALL_PATHS)).build()).build());
+                    .setSendMax(ALL_PATHS).build()).build());
         final Map<BgpTableType, PathSelectionMode> result = OpenConfigMappingUtil
                 .toPathSelectionMode(families, this.tableTypeRegistry);
         final Map<BgpTableType, PathSelectionMode> expected = new HashMap<>();
@@ -440,15 +439,14 @@ public class OpenConfigMappingUtilTest {
         families.add(new AfiSafiBuilder().setAfiSafiName(IPV4UNICAST.class)
             .addAugmentation(NeighborAddPathsConfig.class,
                 new NeighborAddPathsConfigBuilder()
-                    .setReceive(true).setSendMax(Shorts.checkedCast(ALL_PATHS)).build()).build());
+                    .setReceive(Boolean.TRUE).setSendMax(ALL_PATHS).build()).build());
         families.add(new AfiSafiBuilder().setAfiSafiName(IPV6UNICAST.class)
             .addAugmentation(NeighborAddPathsConfig.class,
                 new NeighborAddPathsConfigBuilder()
-                    .setReceive(false).setSendMax(Shorts.checkedCast(N_PATHS)).build()).build());
+                    .setReceive(Boolean.FALSE).setSendMax(N_PATHS).build()).build());
         families.add(new AfiSafiBuilder().setAfiSafiName(IPV6LABELLEDUNICAST.class)
             .addAugmentation(NeighborAddPathsConfig.class,
-                new NeighborAddPathsConfigBuilder()
-                    .setReceive(false).build()).build());
+                new NeighborAddPathsConfigBuilder().setReceive(Boolean.FALSE).build()).build());
         final List<AddressFamilies> result = OpenConfigMappingUtil
                 .toAddPathCapability(families, this.tableTypeRegistry);
         assertEquals(FAMILIES, result);