diff options
Diffstat (limited to 'framework/src/onos/utils/misc')
10 files changed, 924 insertions, 106 deletions
diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java index b62d3b24..206a34c8 100644 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java +++ b/framework/src/onos/utils/misc/src/main/java/org/onlab/graph/DisjointPathPair.java @@ -19,52 +19,67 @@ package org.onlab.graph; import java.util.List; import java.util.Objects; -import java.util.Set; -import static com.google.common.collect.ImmutableSet.of; import static com.google.common.base.MoreObjects.toStringHelper; - +/** + * Pair of disjoint paths. + * + * @param <V> type of vertex + * @param <E> type of edge + */ public class DisjointPathPair<V extends Vertex, E extends Edge<V>> implements Path<V, E> { - public Path<V, E> path1, path2; - boolean usingPath1 = true; + + private Path<V, E> primary, secondary; + boolean primaryActive = true; /** - * Creates a Disjoint Path Pair from two paths. + * Creates a disjoint path pair from two paths. * - * @param p1 first path - * @param p2 second path + * @param primary primary path + * @param secondary secondary path */ - public DisjointPathPair(Path<V, E> p1, Path<V, E> p2) { - path1 = p1; - path2 = p2; + public DisjointPathPair(Path<V, E> primary, Path<V, E> secondary) { + this.primary = primary; + this.secondary = secondary; } @Override public V src() { - return path1.src(); + return primary.src(); } @Override public V dst() { - return path1.dst(); + return primary.dst(); + } + + /** + * Returns the primary path. + * + * @return primary path + */ + public Path<V, E> primary() { + return primary; + } + + /** + * Returns the secondary path. + * + * @return primary path + */ + public Path<V, E> secondary() { + return secondary; } @Override public double cost() { - if (!hasBackup()) { - return path1.cost(); - } - return path1.cost() + path2.cost(); + return hasBackup() ? primary.cost() + secondary.cost() : primary.cost(); } @Override public List<E> edges() { - if (usingPath1 || !hasBackup()) { - return path1.edges(); - } else { - return path2.edges(); - } + return primaryActive || !hasBackup() ? primary.edges() : secondary.edges(); } /** @@ -73,7 +88,7 @@ public class DisjointPathPair<V extends Vertex, E extends Edge<V>> implements Pa * @return boolean representing whether it has backup */ public boolean hasBackup() { - return path2 != null && path2.edges() != null; + return secondary != null && secondary.edges() != null; } @Override @@ -88,13 +103,8 @@ public class DisjointPathPair<V extends Vertex, E extends Edge<V>> implements Pa @Override public int hashCode() { - Set<Path<V, E>> paths; - if (!hasBackup()) { - paths = of(path1); - } else { - paths = of(path1, path2); - } - return Objects.hash(paths); + return hasBackup() ? Objects.hash(primary) + Objects.hash(secondary) : + Objects.hash(primary); } @Override @@ -106,10 +116,10 @@ public class DisjointPathPair<V extends Vertex, E extends Edge<V>> implements Pa final DisjointPathPair other = (DisjointPathPair) obj; return Objects.equals(this.src(), other.src()) && Objects.equals(this.dst(), other.dst()) && - (Objects.equals(this.path1, other.path1) && - Objects.equals(this.path2, other.path2)) || - (Objects.equals(this.path1, other.path2) && - Objects.equals(this.path2, other.path1)); + (Objects.equals(this.primary, other.primary) && + Objects.equals(this.secondary, other.secondary)) || + (Objects.equals(this.primary, other.secondary) && + Objects.equals(this.secondary, other.primary)); } return false; } @@ -120,9 +130,6 @@ public class DisjointPathPair<V extends Vertex, E extends Edge<V>> implements Pa * @return number of paths */ public int size() { - if (hasBackup()) { - return 2; - } - return 1; + return hasBackup() ? 2 : 1; } } diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrGroup.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrGroup.java index 891a0193..be4ab19a 100644 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrGroup.java +++ b/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrGroup.java @@ -241,7 +241,7 @@ public class PIMAddrGroup { return false; } final PIMAddrGroup other = (PIMAddrGroup) obj; - if (this.family != this.family) { + if (this.family != other.family) { return false; } diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrSource.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrSource.java index 2d4a7816..21526408 100644 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrSource.java +++ b/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrSource.java @@ -265,7 +265,7 @@ public class PIMAddrSource { return false; } final PIMAddrSource other = (PIMAddrSource) obj; - if (this.family != this.family) { + if (this.family != other.family) { return false; } diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrUnicast.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrUnicast.java index 0c2d676b..a6ba3895 100644 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrUnicast.java +++ b/framework/src/onos/utils/misc/src/main/java/org/onlab/packet/pim/PIMAddrUnicast.java @@ -166,7 +166,7 @@ public class PIMAddrUnicast { return false; } final PIMAddrUnicast other = (PIMAddrUnicast) obj; - if (this.family != this.family) { + if (this.family != other.family) { return false; } diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/util/HexDump.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/util/HexDump.java new file mode 100755 index 00000000..cfb79390 --- /dev/null +++ b/framework/src/onos/utils/misc/src/main/java/org/onlab/util/HexDump.java @@ -0,0 +1,57 @@ +/*
+ * Copyright 2015 Open Networking Laboratory
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+package org.onlab.util;
+
+import org.jboss.netty.buffer.ChannelBuffer;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+/**
+ * HexDump class an utility to dump buffer in hex format.
+ */
+public final class HexDump {
+ protected static final Logger log = LoggerFactory.getLogger(HexDump.class);
+
+ private HexDump() {
+ }
+
+ /**
+ * Dump the buffer content in hex format.
+ *
+ * @param buff buffer content to dump in hex format
+ */
+ public static void dump(ChannelBuffer buff) {
+ try {
+ byte[] yTemp;
+ yTemp = buff.array();
+
+ int iStartIndex = buff.readerIndex();
+ int iEndIndex = buff.writerIndex();
+ do {
+ StringBuilder sb = new StringBuilder();
+ for (int k = 0; (k < 16) && (iStartIndex < iEndIndex); ++k) {
+ if (0 == k % 4) {
+ sb.append(String.format(" ")); // blank after 4 bytes
+ }
+ sb.append(String.format("%02X ", yTemp[iStartIndex++]));
+ }
+ log.debug(sb.toString());
+ } while (iStartIndex < iEndIndex);
+ } catch (Exception e) {
+ log.error("[HexDump] Invalid buffer: " + e.toString());
+ }
+ }
+}
diff --git a/framework/src/onos/utils/misc/src/main/java/org/onlab/util/Tools.java b/framework/src/onos/utils/misc/src/main/java/org/onlab/util/Tools.java index abc48ccf..1b788145 100644 --- a/framework/src/onos/utils/misc/src/main/java/org/onlab/util/Tools.java +++ b/framework/src/onos/utils/misc/src/main/java/org/onlab/util/Tools.java @@ -299,12 +299,14 @@ public abstract class Tools { * * @param path file path * @return file contents + * @deprecated in Emu release */ + @Deprecated public static List<String> slurp(File path) { - try { + try ( BufferedReader br = new BufferedReader( new InputStreamReader(new FileInputStream(path), StandardCharsets.UTF_8)); - + ) { List<String> lines = new ArrayList<>(); String line; while ((line = br.readLine()) != null) { diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java index 885fbe5c..8bfd270c 100644 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java +++ b/framework/src/onos/utils/misc/src/test/java/org/onlab/graph/SRLGGraphSearchTest.java @@ -17,44 +17,37 @@ package org.onlab.graph; import org.junit.Test; -import java.util.Set; + +import java.util.HashMap; import java.util.HashSet; import java.util.Map; -import java.util.HashMap; +import java.util.Set; import static com.google.common.collect.ImmutableSet.of; +import static org.junit.Assert.assertEquals; import static org.junit.Assert.assertTrue; - - +import static org.onlab.graph.GraphPathSearch.ALL_PATHS; /** * Test of the Suurballe backup path algorithm. */ public class SRLGGraphSearchTest extends BreadthFirstSearchTest { + @Override protected AbstractGraphPathSearch<TestVertex, TestEdge> graphSearch() { - return new SRLGGraphSearch<TestVertex, TestEdge>(null); + return new SRLGGraphSearch<>(null); } - public void setWeights() { - weight = new EdgeWeight<TestVertex, TestEdge>() { - @Override - public double weight(TestEdge edge) { - return edge.weight(); - } - }; - } public void setDefaultWeights() { weight = null; } + @Override public void defaultGraphTest() { - } @Override public void defaultHopCountWeight() { - } @Test @@ -66,34 +59,34 @@ public class SRLGGraphSearchTest extends BreadthFirstSearchTest { TestEdge dC = new TestEdge(D, C, 1); Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D), of(aB, bC, aD, dC)); - Map<TestEdge, Integer> riskProfile = new HashMap<TestEdge, Integer>(); + Map<TestEdge, Integer> riskProfile = new HashMap<>(); riskProfile.put(aB, 0); riskProfile.put(bC, 0); riskProfile.put(aD, 1); riskProfile.put(dC, 1); - SRLGGraphSearch<TestVertex, TestEdge> search = - new SRLGGraphSearch<TestVertex, TestEdge>(2, riskProfile); - Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, GraphPathSearch.ALL_PATHS).paths(); + SRLGGraphSearch<TestVertex, TestEdge> search = new SRLGGraphSearch<>(2, riskProfile); + Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, ALL_PATHS).paths(); System.out.println("\n\n\n" + paths + "\n\n\n"); - assertTrue("one disjoint path pair found", paths.size() == 1); + assertEquals("one disjoint path pair found", 1, paths.size()); checkIsDisjoint(paths.iterator().next(), riskProfile); } + public void checkIsDisjoint(Path<TestVertex, TestEdge> p, Map<TestEdge, Integer> risks) { assertTrue("The path is not a DisjointPathPair", (p instanceof DisjointPathPair)); DisjointPathPair<TestVertex, TestEdge> q = (DisjointPathPair) p; - Set<Integer> p1Risks = new HashSet<Integer>(); - Set<Integer> p2Risks = new HashSet<Integer>(); - for (TestEdge e: q.edges()) { + Set<Integer> p1Risks = new HashSet<>(); + for (TestEdge e : q.edges()) { p1Risks.add(risks.get(e)); } if (!q.hasBackup()) { return; } - Path<TestVertex, TestEdge> pq = q.path2; + Path<TestVertex, TestEdge> pq = q.secondary(); for (TestEdge e: pq.edges()) { assertTrue("The paths are not disjoint", !p1Risks.contains(risks.get(e))); } } + @Test public void complexGraphTest() { setDefaultWeights(); @@ -105,16 +98,15 @@ public class SRLGGraphSearchTest extends BreadthFirstSearchTest { TestEdge bE = new TestEdge(B, E, 1); Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E), of(aB, bC, aD, dC, cE, bE)); - Map<TestEdge, Integer> riskProfile = new HashMap<TestEdge, Integer>(); + Map<TestEdge, Integer> riskProfile = new HashMap<>(); riskProfile.put(aB, 0); riskProfile.put(bC, 0); riskProfile.put(aD, 1); riskProfile.put(dC, 1); riskProfile.put(cE, 2); riskProfile.put(bE, 3); - SRLGGraphSearch<TestVertex, TestEdge> search = - new SRLGGraphSearch<TestVertex, TestEdge>(4, riskProfile); - Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, GraphPathSearch.ALL_PATHS).paths(); + SRLGGraphSearch<TestVertex, TestEdge> search = new SRLGGraphSearch<>(4, riskProfile); + search.search(graph, A, E, weight, ALL_PATHS).paths(); } @Test @@ -128,19 +120,19 @@ public class SRLGGraphSearchTest extends BreadthFirstSearchTest { TestEdge cE = new TestEdge(C, E, 1); Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D, E), of(aB, bE, aD, dE, aC, cE)); - Map<TestEdge, Integer> riskProfile = new HashMap<TestEdge, Integer>(); + Map<TestEdge, Integer> riskProfile = new HashMap<>(); riskProfile.put(aB, 0); riskProfile.put(bE, 1); riskProfile.put(aD, 2); riskProfile.put(dE, 3); riskProfile.put(aC, 4); riskProfile.put(cE, 5); - SRLGGraphSearch<TestVertex, TestEdge> search = - new SRLGGraphSearch<TestVertex, TestEdge>(6, riskProfile); - Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, GraphPathSearch.ALL_PATHS).paths(); + SRLGGraphSearch<TestVertex, TestEdge> search = new SRLGGraphSearch<>(6, riskProfile); + Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, ALL_PATHS).paths(); assertTrue("> one disjoint path pair found", paths.size() >= 1); checkIsDisjoint(paths.iterator().next(), riskProfile); } + @Test public void onePath() { setDefaultWeights(); @@ -150,17 +142,17 @@ public class SRLGGraphSearchTest extends BreadthFirstSearchTest { TestEdge dC = new TestEdge(D, C, 1); Graph<TestVertex, TestEdge> graph = new AdjacencyListsGraph<>(of(A, B, C, D), of(aB, bC, aD, dC)); - Map<TestEdge, Integer> riskProfile = new HashMap<TestEdge, Integer>(); + Map<TestEdge, Integer> riskProfile = new HashMap<>(); riskProfile.put(aB, 0); riskProfile.put(bC, 0); riskProfile.put(aD, 1); riskProfile.put(dC, 0); - SRLGGraphSearch<TestVertex, TestEdge> search = - new SRLGGraphSearch<TestVertex, TestEdge>(2, riskProfile); - Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, GraphPathSearch.ALL_PATHS).paths(); + SRLGGraphSearch<TestVertex, TestEdge> search = new SRLGGraphSearch<>(2, riskProfile); + Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, C, weight, ALL_PATHS).paths(); System.out.println(paths); assertTrue("no disjoint path pairs found", paths.size() == 0); } + @Test public void noPath() { setDefaultWeights(); @@ -175,9 +167,8 @@ public class SRLGGraphSearchTest extends BreadthFirstSearchTest { riskProfile.put(bC, 0); riskProfile.put(aD, 1); riskProfile.put(dC, 0); - SRLGGraphSearch<TestVertex, TestEdge> search = - new SRLGGraphSearch<>(2, riskProfile); - Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, GraphPathSearch.ALL_PATHS).paths(); + SRLGGraphSearch<TestVertex, TestEdge> search = new SRLGGraphSearch<>(2, riskProfile); + Set<Path<TestVertex, TestEdge>> paths = search.search(graph, A, E, weight, ALL_PATHS).paths(); assertTrue("no disjoint path pairs found", paths.size() == 0); } } diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/util/AbstractAccumulatorTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/util/AbstractAccumulatorTest.java index 02f0deb1..db7224ad 100644 --- a/framework/src/onos/utils/misc/src/test/java/org/onlab/util/AbstractAccumulatorTest.java +++ b/framework/src/onos/utils/misc/src/test/java/org/onlab/util/AbstractAccumulatorTest.java @@ -15,23 +15,24 @@ */ package org.onlab.util; -import org.junit.Ignore; import org.junit.Test; import java.util.List; -import java.util.Timer; import java.util.stream.IntStream; -import static org.junit.Assert.*; +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; import static org.onlab.junit.TestTools.assertAfter; -import static org.onlab.junit.TestTools.delay; /** * Tests the operation of the accumulator. */ public class AbstractAccumulatorTest { - private final Timer timer = new Timer(); + + private final ManuallyAdvancingTimer timer = new ManuallyAdvancingTimer(); + @Test public void basics() throws Exception { @@ -42,7 +43,6 @@ public class AbstractAccumulatorTest { assertEquals("incorrect idle ms", 70, accumulator.maxIdleMillis()); } - @Ignore("FIXME: timing sensitive test failing randomly.") @Test public void eventTrigger() { TestAccumulator accumulator = new TestAccumulator(); @@ -52,43 +52,40 @@ public class AbstractAccumulatorTest { accumulator.add(new TestItem("d")); assertTrue("should not have fired yet", accumulator.batch.isEmpty()); accumulator.add(new TestItem("e")); - delay(20); + timer.advanceTimeMillis(20, 10); assertFalse("should have fired", accumulator.batch.isEmpty()); assertEquals("incorrect batch", "abcde", accumulator.batch); } - @Ignore("FIXME: timing sensitive test failing randomly.") @Test public void timeTrigger() { TestAccumulator accumulator = new TestAccumulator(); accumulator.add(new TestItem("a")); - delay(30); + timer.advanceTimeMillis(30, 1); assertTrue("should not have fired yet", accumulator.batch.isEmpty()); accumulator.add(new TestItem("b")); - delay(30); + timer.advanceTimeMillis(30, 1); assertTrue("should not have fired yet", accumulator.batch.isEmpty()); accumulator.add(new TestItem("c")); - delay(30); + timer.advanceTimeMillis(30, 1); assertTrue("should not have fired yet", accumulator.batch.isEmpty()); accumulator.add(new TestItem("d")); - delay(60); + timer.advanceTimeMillis(10, 10); assertFalse("should have fired", accumulator.batch.isEmpty()); assertEquals("incorrect batch", "abcd", accumulator.batch); } - @Ignore("FIXME: timing sensitive test failing randomly.") @Test public void idleTrigger() { TestAccumulator accumulator = new TestAccumulator(); accumulator.add(new TestItem("a")); assertTrue("should not have fired yet", accumulator.batch.isEmpty()); accumulator.add(new TestItem("b")); - delay(80); + timer.advanceTimeMillis(70, 10); assertFalse("should have fired", accumulator.batch.isEmpty()); assertEquals("incorrect batch", "ab", accumulator.batch); } - @Ignore("FIXME: timing sensitive test failing randomly.") @Test public void readyIdleTrigger() { TestAccumulator accumulator = new TestAccumulator(); @@ -96,30 +93,28 @@ public class AbstractAccumulatorTest { accumulator.add(new TestItem("a")); assertTrue("should not have fired yet", accumulator.batch.isEmpty()); accumulator.add(new TestItem("b")); - delay(80); + timer.advanceTimeMillis(80, 1); assertTrue("should not have fired yet", accumulator.batch.isEmpty()); accumulator.ready = true; - delay(80); + timer.advanceTimeMillis(80, 10); assertFalse("should have fired", accumulator.batch.isEmpty()); assertEquals("incorrect batch", "ab", accumulator.batch); } - @Ignore("FIXME: timing sensitive test failing randomly.") @Test public void readyLongTrigger() { TestAccumulator accumulator = new TestAccumulator(); accumulator.ready = false; - delay(120); + timer.advanceTimeMillis(120, 1); assertTrue("should not have fired yet", accumulator.batch.isEmpty()); accumulator.add(new TestItem("a")); assertTrue("should not have fired yet", accumulator.batch.isEmpty()); accumulator.ready = true; - delay(80); + timer.advanceTimeMillis(120, 10); assertFalse("should have fired", accumulator.batch.isEmpty()); assertEquals("incorrect batch", "a", accumulator.batch); } - @Ignore("FIXME: timing sensitive test failing randomly.") @Test public void readyMaxTrigger() { TestAccumulator accumulator = new TestAccumulator(); @@ -133,16 +128,16 @@ public class AbstractAccumulatorTest { assertTrue("should not have fired yet", accumulator.batch.isEmpty()); accumulator.ready = true; accumulator.add(new TestItem("g")); - delay(5); + timer.advanceTimeMillis(10, 10); assertFalse("should have fired", accumulator.batch.isEmpty()); assertEquals("incorrect batch", "abcdefg", accumulator.batch); } - @Ignore("FIXME: timing sensitive test failing randomly.") @Test public void stormTest() { TestAccumulator accumulator = new TestAccumulator(); IntStream.range(0, 1000).forEach(i -> accumulator.add(new TestItem("#" + i))); + timer.advanceTimeMillis(1); assertAfter(100, () -> assertEquals("wrong item count", 1000, accumulator.itemCount)); assertEquals("wrong batch count", 200, accumulator.batchCount); } @@ -180,5 +175,4 @@ public class AbstractAccumulatorTest { return ready; } } - } diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/util/ManuallyAdvancingTimer.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/util/ManuallyAdvancingTimer.java new file mode 100644 index 00000000..4116cbef --- /dev/null +++ b/framework/src/onos/utils/misc/src/test/java/org/onlab/util/ManuallyAdvancingTimer.java @@ -0,0 +1,504 @@ +/* + * Copyright 2015 Open Networking Laboratory + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.onlab.util; + +import com.google.common.collect.Lists; +import org.onlab.junit.TestUtils; +import org.slf4j.Logger; + +import java.util.Date; +import java.util.Iterator; +import java.util.LinkedList; +import java.util.TimerTask; +import java.util.concurrent.ExecutorService; +import java.util.concurrent.Executors; + +import static com.google.common.base.Preconditions.checkNotNull; +import static org.onlab.junit.TestTools.delay; +import static org.slf4j.LoggerFactory.getLogger; + + +/** + * Provides manually scheduled timer utility. All schedulable methods are subject to overflow (you can set a period of + * max long). Additionally if a skip skips a period of time greater than one period for a periodic task that task will + * only be executed once for that skip and scheduled it's period after the last execution. + */ +public class ManuallyAdvancingTimer extends java.util.Timer { + + /* States whether or not the static values from timer task have been set ensures population will only occur once.*/ + private boolean staticsPopulated = false; + + /* Virgin value from timer task */ + private int virginState; + + /* Scheduled value from timer task */ + private int scheduledState; + + /* Executed value from timer task */ + private int executedState; + + /* Cancelled value from timer task */ + private int cancelledState; + + private final Logger logger = getLogger(getClass()); + + /* Service for executing timer tasks */ + private final ExecutorService executorService = Executors.newSingleThreadExecutor(); + + /* Internal time representation independent of system time, manually advanced */ + private final TimerKeeper timerKeeper = new TimerKeeper(); + + /* Data structure for tracking tasks */ + private final TaskQueue queue = new TaskQueue(); + + @Override + public void schedule(TimerTask task, long delay) { + if (!staticsPopulated) { + populateStatics(task); + } + if (!submitTask(task, delay > 0 ? timerKeeper.currentTimeInMillis() + delay : + timerKeeper.currentTimeInMillis() - delay, 0)) { + logger.error("Failed to submit task"); + } + } + + @Override + public void schedule(TimerTask task, Date time) { + if (!staticsPopulated) { + populateStatics(task); + } + if (!submitTask(task, time.getTime(), 0)) { + logger.error("Failed to submit task"); + } + } + + @Override + public void schedule(TimerTask task, long delay, long period) { + if (!staticsPopulated) { + populateStatics(task); + } + if (!submitTask(task, delay > 0 ? timerKeeper.currentTimeInMillis() + delay : + timerKeeper.currentTimeInMillis() - delay, period)) { + logger.error("Failed to submit task"); + } + } + + @Override + public void schedule(TimerTask task, Date firstTime, long period) { + if (!staticsPopulated) { + populateStatics(task); + } + if (!submitTask(task, firstTime.getTime(), period)) { + logger.error("Failed to submit task"); + } + } + + /*################################################WARNING################################################*/ + /* Schedule at fixed rate methods do not work exactly as in the java timer. They are clones of the periodic + *scheduling methods. */ + @Override + public void scheduleAtFixedRate(TimerTask task, long delay, long period) { + if (!staticsPopulated) { + populateStatics(task); + } + if (!submitTask(task, delay > 0 ? timerKeeper.currentTimeInMillis() + delay : + timerKeeper.currentTimeInMillis() - delay, period)) { + logger.error("Failed to submit task"); + } + } + + @Override + public void scheduleAtFixedRate(TimerTask task, Date firstTime, long period) { + if (!staticsPopulated) { + populateStatics(task); + } + if (!submitTask(task, firstTime.getTime(), period)) { + logger.error("Failed to submit task"); + } + } + + @Override + public void cancel() { + executorService.shutdown(); + queue.clear(); + } + + @Override + public int purge() { + return queue.removeCancelled(); + } + + /** + * Returns the virtual current time in millis. + * + * @return long representing simulated current time. + */ + public long currentTimeInMillis() { + return timerKeeper.currentTimeInMillis(); + } + + /** + * Returns the new simulated current time in millis after advancing the absolute value of millis to advance. + * Triggers event execution of all events scheduled for execution at times up to and including the returned time. + * Passing in the number zero has no effect. + * + * @param millisToAdvance the number of millis to advance. + * @return a long representing the current simulated time in millis + */ + public long advanceTimeMillis(long millisToAdvance) { + return timerKeeper.advanceTimeMillis(millisToAdvance); + } + + /** + * Advances the virtual time a certain number of millis triggers execution delays a certain amount to + * allow time for execution. + * + * @param virtualTimeAdvance the time to be advances in millis of simulated time. + * @param realTimeDelay the time to delay in real time to allow for processing. + */ + public void advanceTimeMillis(long virtualTimeAdvance, int realTimeDelay) { + timerKeeper.advanceTimeMillis(virtualTimeAdvance); + delay(realTimeDelay); + } + + /** + * Sets up the task and submits it to the queue. + * + * @param task the task to be added to the queue + * @param runtime the first runtime of the task + * @param period the period between runs thereafter + * @return returns true if the task was successfully submitted, false otherwise + */ + private boolean submitTask(TimerTask task, long runtime, long period) { + checkNotNull(task); + try { + TestUtils.setField(task, "state", scheduledState); + TestUtils.setField(task, "nextExecutionTime", runtime); + TestUtils.setField(task, "period", period); + } catch (TestUtils.TestUtilsException e) { + e.printStackTrace(); + return false; + } + queue.insertOrdered(task); + return true; + } + + /** + * Executes the given task (only if it is in the scheduled state) and proceeds to reschedule it or mark it as + * executed. Does not remove from the queue (this must be done outside). + * + * @param task the timer task to be executed + */ + private boolean executeTask(TimerTask task) { + checkNotNull(task); + int currentState; + try { + currentState = TestUtils.getField(task, "state"); + } catch (TestUtils.TestUtilsException e) { + logger.error("Could not get state of task."); + e.printStackTrace(); + return false; + } + //If cancelled or already executed stop here. + if (currentState == executedState || currentState == cancelledState) { + return false; + } else if (currentState == virginState) { + logger.error("Task was set for execution without being scheduled."); + return false; + } else if (currentState == scheduledState) { + long period; + + try { + period = TestUtils.getField(task, "period"); + } catch (TestUtils.TestUtilsException e) { + logger.error("Could not read period of task."); + e.printStackTrace(); + return false; + } + //Period of zero means one time execution. + if (period == 0) { + try { + TestUtils.setField(task, "state", executedState); + } catch (TestUtils.TestUtilsException e) { + logger.error("Could not set executed state."); + e.printStackTrace(); + return false; + } + executorService.execute(task); + return true; + } else { + //Calculate next execution time, using absolute value of period + long nextTime = (period > 0) ? (timerKeeper.currentTimeInMillis() + period) : + (timerKeeper.currentTimeInMillis() - period); + try { + TestUtils.setField(task, "nextExecutionTime", nextTime); + } catch (TestUtils.TestUtilsException e) { + logger.error("Could not set next execution time."); + e.printStackTrace(); + return false; + } + //Schedule next execution + queue.insertOrdered(task); + executorService.execute(task); + return true; + } + } + logger.error("State property of {} is in an illegal state and did not execute.", task); + return false; + } + + /** + * Executes all tasks in the queue scheduled for execution up to and including the current time. + * + * @return the total number of tasks run, -1 if failure + */ + private int executeEventsUpToPresent() { + int totalRun = 0; + if (queue.isEmpty()) { + return -1; + } + TimerTask currTask = queue.peek(); + long currExecTime; + try { + currExecTime = TestUtils.getField(currTask, "nextExecutionTime"); + } catch (TestUtils.TestUtilsException e) { + e.printStackTrace(); + throw new RuntimeException("Could not get nextExecutionTime"); + } + while (currExecTime <= timerKeeper.currentTimeInMillis()) { + if (executeTask(queue.pop())) { + totalRun++; + } + if (queue.isEmpty()) { + break; + } + currTask = queue.peek(); + try { + currExecTime = TestUtils.getField(currTask, "nextExecutionTime"); + } catch (TestUtils.TestUtilsException e) { + e.printStackTrace(); + throw new RuntimeException("Could not get nextExecutionTime"); + } + } + return totalRun; + } + + /** + * Populates the static fields from timer task. Should only be called once. + */ + private void populateStatics(TimerTask task) { + try { + virginState = TestUtils.getField(task, "VIRGIN"); + scheduledState = TestUtils.getField(task, "SCHEDULED"); + executedState = TestUtils.getField(task, "EXECUTED"); + cancelledState = TestUtils.getField(task, "CANCELLED"); + staticsPopulated = true; + } catch (TestUtils.TestUtilsException e) { + e.printStackTrace(); + } + } + + /** + * A class used to maintain the virtual time. + */ + private class TimerKeeper { + + private long currentTime = 0; + + /** + * Returns the virtual current time in millis. + * + * @return long representing simulated current time. + */ + long currentTimeInMillis() { + return currentTime; + } + + /** + * Returns the new simulated current time in millis after advancing the absolute value of millis to advance. + * Triggers event execution of all events scheduled for execution at times up to and including the returned + * time. Passing in the number zero has no effect. + * + * @param millisToAdvance the number of millis to advance. + * @return a long representing the current simulated time in millis + */ + long advanceTimeMillis(long millisToAdvance) { + currentTime = (millisToAdvance >= 0) ? (currentTime + millisToAdvance) : (currentTime - millisToAdvance); + if (millisToAdvance != 0) { + executeEventsUpToPresent(); + } + return currentTime; + } + } + + /** + * A queue backed by a linked list. Keeps elements sorted in ascending order of execution time. All calls are safe + * even on empty queue's. + */ + private class TaskQueue { + private final LinkedList<TimerTask> taskList = Lists.newLinkedList(); + + /** + * Adds the task to the queue in ascending order of scheduled execution. If execution time has already passed + * execute immediately. + * + * @param task the task to be added to the queue + */ + void insertOrdered(TimerTask task) { + //Using O(N) insertion because random access is expensive in linked lists worst case is 2N links followed + // for binary insertion vs N for simple insertion. + checkNotNull(task); + if (!staticsPopulated) { + populateStatics(task); + } + long insertTime; + try { + insertTime = TestUtils.getField(task, "nextExecutionTime"); + TestUtils.setField(task, "state", scheduledState); + } catch (TestUtils.TestUtilsException e) { + e.printStackTrace(); + return; + } + //If the task was scheduled in the past or for the current time run it immediately and do not add to the + // queue, subsequent executions will be scheduled as normal + if (insertTime <= timerKeeper.currentTimeInMillis()) { + executeTask(task); + return; + } + + Iterator<TimerTask> iter = taskList.iterator(); + int positionCounter = 0; + long nextTaskTime; + TimerTask currentTask; + while (iter.hasNext()) { + currentTask = iter.next(); + try { + nextTaskTime = TestUtils.getField(currentTask, "nextExecutionTime"); + } catch (TestUtils.TestUtilsException e) { + e.printStackTrace(); + return; + } + if (insertTime < nextTaskTime) { + taskList.add(positionCounter, task); + return; + } + positionCounter++; + } + taskList.addLast(task); + } + + /** + * Returns the first item in the queue (next scheduled for execution) without removing it, returns null if the + * queue is empty. + * + * @return the next TimerTask to run or null if the queue is empty + */ + TimerTask peek() { + if (taskList.isEmpty()) { + return null; + } + return taskList.getFirst(); + } + + /** + * Returns and removes the first item in the queue or null if it is empty. + * + * @return the first element of the queue or null if the queue is empty + */ + TimerTask pop() { + if (taskList.isEmpty()) { + return null; + } + return taskList.pop(); + } + + /** + * Performs a sort on the set of timer tasks, earliest task is first. Does nothing if queue is empty. + */ + void sort() { + if (taskList.isEmpty()) { + return; + } + taskList.sort((o1, o2) -> { + checkNotNull(o1); + checkNotNull(o2); + long executionTimeOne; + long executionTimeTwo; + try { + executionTimeOne = TestUtils.getField(o1, "nextExecutionTime"); + executionTimeTwo = TestUtils.getField(o2, "nextExecutionTime"); + } catch (TestUtils.TestUtilsException e) { + e.printStackTrace(); + throw new RuntimeException("Could not get next execution time."); + } + if (executionTimeOne == executionTimeTwo) { + return 0; + } else if (executionTimeOne < executionTimeTwo) { + return -1; + } else { + return 1; + } + }); + } + + /** + * Returns whether the queue is currently empty. + * + * @return true if the queue is empty, false otherwise + */ + boolean isEmpty() { + return taskList.isEmpty(); + } + + /** + * Clears the underlying list of the queue. + */ + void clear() { + taskList.clear(); + } + + /** + * Removes all cancelled tasks from the queue. Has no effect on behavior. + * + * @return returns the total number of items removed, -1 if list is empty or failure occurs. + */ + int removeCancelled() { + if (taskList.isEmpty()) { + return -1; + } + int removedCount = 0; + Iterator<TimerTask> taskIterator = taskList.iterator(); + TimerTask currTask; + int currState; + while (taskIterator.hasNext()) { + currTask = taskIterator.next(); + try { + currState = TestUtils.getField(currTask, "state"); + } catch (TestUtils.TestUtilsException e) { + logger.error("Could not get task state."); + e.printStackTrace(); + return -1; + } + if (currState == cancelledState) { + removedCount++; + taskIterator.remove(); + } + } + return removedCount; + } + } +} diff --git a/framework/src/onos/utils/misc/src/test/java/org/onlab/util/ManuallyAdvancingTimerTest.java b/framework/src/onos/utils/misc/src/test/java/org/onlab/util/ManuallyAdvancingTimerTest.java new file mode 100644 index 00000000..b8e1e85e --- /dev/null +++ b/framework/src/onos/utils/misc/src/test/java/org/onlab/util/ManuallyAdvancingTimerTest.java @@ -0,0 +1,263 @@ +/* + * Copyright 2015 Open Networking Laboratory + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ + +package org.onlab.util; + +import com.google.common.collect.Lists; +import org.junit.Before; +import org.junit.Test; + +import java.util.ArrayList; +import java.util.Date; +import java.util.TimerTask; +import java.util.concurrent.atomic.AtomicInteger; + +import static org.junit.Assert.assertEquals; +import static org.junit.Assert.assertFalse; +import static org.junit.Assert.assertTrue; +import static org.onlab.junit.TestTools.delay; + +/** + * Testing class for manually advancing timer. + */ +public class ManuallyAdvancingTimerTest { + + private ManuallyAdvancingTimer timer; + + /* Generates unique id's for TestTasks */ + private AtomicInteger idGenerator; + + /* Tracks TestTasks in order of creation, tasks are automatically added at creation. */ + private ArrayList<TestTask> taskList; + + /* Total number of tasks run */ + private AtomicInteger tasksRunCount; + + // FIXME if this class fails first try increasing the real time delay to account for heavy system load. + private static final int REAL_TIME_DELAY = 1; + + /** + * Sets up the testing environment. + */ + @Before + public void setup() { + timer = new ManuallyAdvancingTimer(); + idGenerator = new AtomicInteger(1); + tasksRunCount = new AtomicInteger(0); + taskList = Lists.newArrayList(); + } + + /** + * Tests the one time schedule with delay. + * + * @throws Exception throws an exception if the test fails + */ + @Test + public void testScheduleByDelay() throws Exception { + /* Test scheduling in the future as normal. */ + timer.schedule(new TestTask(), 10); + timer.advanceTimeMillis(5); + assertFalse(taskList.get(0).hasRun()); + timer.advanceTimeMillis(10, REAL_TIME_DELAY); + assertTrue(taskList.get(0).hasRun()); + + /* Test scheduling with negative numbers */ + timer.schedule(new TestTask(), -10); + timer.advanceTimeMillis(5); + assertFalse(taskList.get(1).hasRun()); + timer.advanceTimeMillis(10, REAL_TIME_DELAY); + assertTrue(taskList.get(1).hasRun()); + + /* Reset list, counter and timer for next test */ + taskList.clear(); + idGenerator.set(1); + tasksRunCount.set(0); + + for (int i = 0; i < 50; i++) { + timer.schedule(new TestTask(), i); + } + /* Test that a task scheduled for present is run and not placed in the queue */ + assertEquals("Only the first task should have run.", 1, tasksRunCount.get()); + + for (int i = 2; i <= 50; i++) { + timer.advanceTimeMillis(1, REAL_TIME_DELAY); + assertEquals("One task should be executed per loop", i, tasksRunCount.get()); + } + /* Below tests ordered insertion, this will only be done once, it is the same for all schedule methods. */ + + tasksRunCount.set(0); + + for (int i = 0; i < 10; i++) { + timer.schedule(new TestTask(), 500); + } + + assertEquals("No new tasks should have been run since run count reset.", 0, tasksRunCount.get()); + timer.schedule(new TestTask(), 10); + assertEquals("No new tasks should have been run since run count reset.", 0, tasksRunCount.get()); + timer.advanceTimeMillis(10, REAL_TIME_DELAY); + assertEquals("One new tasks should have been run since run count reset.", 1, tasksRunCount.get()); + timer.advanceTimeMillis(510, REAL_TIME_DELAY); + assertEquals("Eleven new tasks should have been run since run count reset.", 11, tasksRunCount.get()); + } + + /** + * Tests scheduling for a particular date or time which may be in the past. + * + * @throws Exception throws an exception if the test fails + */ + @Test + public void testScheduleByDate() throws Exception { + /* Tests basic scheduling for future times. */ + timer.schedule(new TestTask(), new Date(10)); + timer.advanceTimeMillis(5); + assertFalse(taskList.get(0).hasRun()); + timer.advanceTimeMillis(10, REAL_TIME_DELAY); + assertTrue(taskList.get(0).hasRun()); + + /* Test scheduling with past times numbers */ + timer.schedule(new TestTask(), new Date(0)); + delay(REAL_TIME_DELAY); + assertTrue(taskList.get(1).hasRun()); + + /* Tests cancellation on non-periodic events */ + TestTask task = new TestTask(); + timer.schedule(task, new Date(timer.currentTimeInMillis() + 10)); + task.cancel(); + timer.advanceTimeMillis(12, REAL_TIME_DELAY); + assertFalse(task.hasRun()); + + } + + /** + * Test scheduling beginning after a delay and recurring periodically. + * + * @throws Exception throws an exception if the test fails + */ + @Test + public void testScheduleByDelayPeriodic() throws Exception { + /* Test straightforward periodic execution */ + timer.schedule(new TestTask(), 0, 10); + delay(REAL_TIME_DELAY); + assertEquals("Task should have run once when added.", 1, taskList.get(0).timesRun()); + + /* Tests whether things that are not added to the queue are scheduled for future executions (ones which execute + immediately on add). */ + timer.advanceTimeMillis(10, REAL_TIME_DELAY); + assertEquals("Task should have run once when added.", 2, taskList.get(0).timesRun()); + + /* Tests whether cancellation works on periodic events. */ + taskList.get(0).cancel(); + + timer.advanceTimeMillis(10, REAL_TIME_DELAY); + assertEquals("The task should not have run another time.", 2, taskList.get(0).timesRun()); + + TestTask task = new TestTask(); + timer.schedule(task, 0, 10); + timer.advanceTimeMillis(100, REAL_TIME_DELAY); + assertEquals("Should have run immeditaley and subsequently once during the larger skip", task.timesRun(), 2); + + } + + /** + * Test scheduling beginning at a specified date and recurring periodically. + * + * @throws Exception throws an exception if the test fails + */ + @Test + public void testScheduleByDatePeriodic() throws Exception { + /* Test straightforward periodic execution */ + timer.schedule(new TestTask(), new Date(timer.currentTimeInMillis()), 10); + delay(REAL_TIME_DELAY); + assertEquals("Task should have run once when added.", 1, taskList.get(0).timesRun()); + + /* Tests whether things that are not added to the queue are scheduled for future executions (ones which execute + immediately on add). */ + timer.advanceTimeMillis(10, REAL_TIME_DELAY); + assertEquals("Task should have run once when added.", 2, taskList.get(0).timesRun()); + + /* Tests whether cancellation works on periodic events. */ + taskList.get(0).cancel(); + + timer.advanceTimeMillis(10, REAL_TIME_DELAY); + assertEquals("The task should not have run another time.", 2, taskList.get(0).timesRun()); + + TestTask task = new TestTask(); + timer.schedule(task, new Date(timer.currentTimeInMillis()), 10); + timer.advanceTimeMillis(100, REAL_TIME_DELAY); + assertEquals("Should have run immediately and subsequently once during the larger skip", task.timesRun(), 2); + } + + /* Schedule at fixed rate runs exactly like the two scheduling methods just tested so tests are not included */ + + /** + * Timer task with added functions to make it better for testing. + */ + private class TestTask extends TimerTask { + + /* Remains true once the task has been run at least once */ + private boolean hasRun; + + /* Unique id per event. */ + private int id; + + /* Specifies the number of times an event has run */ + private int timesRun; + + /** + * Constructor initializes id, timesRun, and id fields. + */ + public TestTask() { + id = idGenerator.getAndIncrement(); + timesRun = 0; + hasRun = false; + taskList.add(this); + } + + @Override + public void run() { + this.hasRun = true; + tasksRunCount.incrementAndGet(); + timesRun++; + } + + /** + * Returns whether this event has run. + * + * @return true if the event has run, false otherwise. + */ + public boolean hasRun() { + return hasRun; + } + + /** + * Returns the number of times this task has run. + * + * @return an int representing the number of times this task has been run + */ + public int timesRun() { + return timesRun; + } + + /** + * Returns the unique identifier of this task. + * + * @return a unique integer identifier + */ + public int getId() { + return id; + } + } +}
\ No newline at end of file |