Aaron Kruglikov | 4ce0b04 | 2015-10-07 14:04:17 -0700 | [diff] [blame] | 1 | /* |
Brian O'Connor | a09fe5b | 2017-08-03 21:12:30 -0700 | [diff] [blame] | 2 | * Copyright 2015-present Open Networking Foundation |
Aaron Kruglikov | 4ce0b04 | 2015-10-07 14:04:17 -0700 | [diff] [blame] | 3 | * |
| 4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
| 5 | * you may not use this file except in compliance with the License. |
| 6 | * You may obtain a copy of the License at |
| 7 | * |
| 8 | * http://www.apache.org/licenses/LICENSE-2.0 |
| 9 | * |
| 10 | * Unless required by applicable law or agreed to in writing, software |
| 11 | * distributed under the License is distributed on an "AS IS" BASIS, |
| 12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 13 | * See the License for the specific language governing permissions and |
| 14 | * limitations under the License. |
| 15 | */ |
| 16 | |
| 17 | package org.onlab.util; |
| 18 | |
| 19 | import com.google.common.collect.Lists; |
| 20 | import org.onlab.junit.TestUtils; |
| 21 | import org.slf4j.Logger; |
| 22 | |
| 23 | import java.util.Date; |
| 24 | import java.util.Iterator; |
| 25 | import java.util.LinkedList; |
| 26 | import java.util.TimerTask; |
| 27 | import java.util.concurrent.ExecutorService; |
| 28 | import java.util.concurrent.Executors; |
| 29 | |
| 30 | import static com.google.common.base.Preconditions.checkNotNull; |
| 31 | import static org.onlab.junit.TestTools.delay; |
| 32 | import static org.slf4j.LoggerFactory.getLogger; |
| 33 | |
| 34 | |
| 35 | /** |
| 36 | * Provides manually scheduled timer utility. All schedulable methods are subject to overflow (you can set a period of |
| 37 | * max long). Additionally if a skip skips a period of time greater than one period for a periodic task that task will |
| 38 | * only be executed once for that skip and scheduled it's period after the last execution. |
| 39 | */ |
| 40 | public class ManuallyAdvancingTimer extends java.util.Timer { |
| 41 | |
| 42 | /* States whether or not the static values from timer task have been set ensures population will only occur once.*/ |
| 43 | private boolean staticsPopulated = false; |
| 44 | |
| 45 | /* Virgin value from timer task */ |
| 46 | private int virginState; |
| 47 | |
| 48 | /* Scheduled value from timer task */ |
| 49 | private int scheduledState; |
| 50 | |
| 51 | /* Executed value from timer task */ |
| 52 | private int executedState; |
| 53 | |
| 54 | /* Cancelled value from timer task */ |
| 55 | private int cancelledState; |
| 56 | |
| 57 | private final Logger logger = getLogger(getClass()); |
| 58 | |
| 59 | /* Service for executing timer tasks */ |
| 60 | private final ExecutorService executorService = Executors.newSingleThreadExecutor(); |
| 61 | |
| 62 | /* Internal time representation independent of system time, manually advanced */ |
| 63 | private final TimerKeeper timerKeeper = new TimerKeeper(); |
| 64 | |
| 65 | /* Data structure for tracking tasks */ |
| 66 | private final TaskQueue queue = new TaskQueue(); |
| 67 | |
Aaron Kruglikov | f27dba6 | 2015-10-27 15:06:29 -0700 | [diff] [blame] | 68 | /* Whether execution should execute on the executor thread or the calling thread. */ |
| 69 | private final boolean runLocally; |
| 70 | |
| 71 | public ManuallyAdvancingTimer(boolean runLocally) { |
| 72 | this.runLocally = runLocally; |
| 73 | } |
| 74 | |
| 75 | |
Aaron Kruglikov | 4ce0b04 | 2015-10-07 14:04:17 -0700 | [diff] [blame] | 76 | @Override |
| 77 | public void schedule(TimerTask task, long delay) { |
| 78 | if (!staticsPopulated) { |
| 79 | populateStatics(task); |
| 80 | } |
| 81 | if (!submitTask(task, delay > 0 ? timerKeeper.currentTimeInMillis() + delay : |
| 82 | timerKeeper.currentTimeInMillis() - delay, 0)) { |
| 83 | logger.error("Failed to submit task"); |
| 84 | } |
| 85 | } |
| 86 | |
| 87 | @Override |
| 88 | public void schedule(TimerTask task, Date time) { |
| 89 | if (!staticsPopulated) { |
| 90 | populateStatics(task); |
| 91 | } |
| 92 | if (!submitTask(task, time.getTime(), 0)) { |
| 93 | logger.error("Failed to submit task"); |
| 94 | } |
| 95 | } |
| 96 | |
| 97 | @Override |
| 98 | public void schedule(TimerTask task, long delay, long period) { |
| 99 | if (!staticsPopulated) { |
| 100 | populateStatics(task); |
| 101 | } |
| 102 | if (!submitTask(task, delay > 0 ? timerKeeper.currentTimeInMillis() + delay : |
| 103 | timerKeeper.currentTimeInMillis() - delay, period)) { |
| 104 | logger.error("Failed to submit task"); |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | @Override |
| 109 | public void schedule(TimerTask task, Date firstTime, long period) { |
| 110 | if (!staticsPopulated) { |
| 111 | populateStatics(task); |
| 112 | } |
| 113 | if (!submitTask(task, firstTime.getTime(), period)) { |
| 114 | logger.error("Failed to submit task"); |
| 115 | } |
| 116 | } |
| 117 | |
| 118 | /*################################################WARNING################################################*/ |
| 119 | /* Schedule at fixed rate methods do not work exactly as in the java timer. They are clones of the periodic |
| 120 | *scheduling methods. */ |
| 121 | @Override |
| 122 | public void scheduleAtFixedRate(TimerTask task, long delay, long period) { |
| 123 | if (!staticsPopulated) { |
| 124 | populateStatics(task); |
| 125 | } |
| 126 | if (!submitTask(task, delay > 0 ? timerKeeper.currentTimeInMillis() + delay : |
| 127 | timerKeeper.currentTimeInMillis() - delay, period)) { |
| 128 | logger.error("Failed to submit task"); |
| 129 | } |
| 130 | } |
| 131 | |
| 132 | @Override |
| 133 | public void scheduleAtFixedRate(TimerTask task, Date firstTime, long period) { |
| 134 | if (!staticsPopulated) { |
| 135 | populateStatics(task); |
| 136 | } |
| 137 | if (!submitTask(task, firstTime.getTime(), period)) { |
| 138 | logger.error("Failed to submit task"); |
| 139 | } |
| 140 | } |
| 141 | |
| 142 | @Override |
| 143 | public void cancel() { |
| 144 | executorService.shutdown(); |
| 145 | queue.clear(); |
| 146 | } |
| 147 | |
| 148 | @Override |
| 149 | public int purge() { |
| 150 | return queue.removeCancelled(); |
| 151 | } |
| 152 | |
| 153 | /** |
| 154 | * Returns the virtual current time in millis. |
| 155 | * |
| 156 | * @return long representing simulated current time. |
| 157 | */ |
| 158 | public long currentTimeInMillis() { |
| 159 | return timerKeeper.currentTimeInMillis(); |
| 160 | } |
| 161 | |
| 162 | /** |
| 163 | * Returns the new simulated current time in millis after advancing the absolute value of millis to advance. |
| 164 | * Triggers event execution of all events scheduled for execution at times up to and including the returned time. |
| 165 | * Passing in the number zero has no effect. |
| 166 | * |
| 167 | * @param millisToAdvance the number of millis to advance. |
| 168 | * @return a long representing the current simulated time in millis |
| 169 | */ |
| 170 | public long advanceTimeMillis(long millisToAdvance) { |
| 171 | return timerKeeper.advanceTimeMillis(millisToAdvance); |
| 172 | } |
| 173 | |
| 174 | /** |
| 175 | * Advances the virtual time a certain number of millis triggers execution delays a certain amount to |
Aaron Kruglikov | f27dba6 | 2015-10-27 15:06:29 -0700 | [diff] [blame] | 176 | * allow time for execution. If runLocally is true then all real time delays are ignored. |
Aaron Kruglikov | 4ce0b04 | 2015-10-07 14:04:17 -0700 | [diff] [blame] | 177 | * |
| 178 | * @param virtualTimeAdvance the time to be advances in millis of simulated time. |
| 179 | * @param realTimeDelay the time to delay in real time to allow for processing. |
| 180 | */ |
| 181 | public void advanceTimeMillis(long virtualTimeAdvance, int realTimeDelay) { |
| 182 | timerKeeper.advanceTimeMillis(virtualTimeAdvance); |
Aaron Kruglikov | f27dba6 | 2015-10-27 15:06:29 -0700 | [diff] [blame] | 183 | if (!runLocally) { |
| 184 | delay(realTimeDelay); |
| 185 | } |
Aaron Kruglikov | 4ce0b04 | 2015-10-07 14:04:17 -0700 | [diff] [blame] | 186 | } |
| 187 | |
| 188 | /** |
| 189 | * Sets up the task and submits it to the queue. |
| 190 | * |
| 191 | * @param task the task to be added to the queue |
| 192 | * @param runtime the first runtime of the task |
| 193 | * @param period the period between runs thereafter |
| 194 | * @return returns true if the task was successfully submitted, false otherwise |
| 195 | */ |
| 196 | private boolean submitTask(TimerTask task, long runtime, long period) { |
| 197 | checkNotNull(task); |
| 198 | try { |
| 199 | TestUtils.setField(task, "state", scheduledState); |
| 200 | TestUtils.setField(task, "nextExecutionTime", runtime); |
| 201 | TestUtils.setField(task, "period", period); |
| 202 | } catch (TestUtils.TestUtilsException e) { |
| 203 | e.printStackTrace(); |
| 204 | return false; |
| 205 | } |
| 206 | queue.insertOrdered(task); |
| 207 | return true; |
| 208 | } |
| 209 | |
| 210 | /** |
| 211 | * Executes the given task (only if it is in the scheduled state) and proceeds to reschedule it or mark it as |
| 212 | * executed. Does not remove from the queue (this must be done outside). |
| 213 | * |
| 214 | * @param task the timer task to be executed |
| 215 | */ |
| 216 | private boolean executeTask(TimerTask task) { |
| 217 | checkNotNull(task); |
| 218 | int currentState; |
| 219 | try { |
| 220 | currentState = TestUtils.getField(task, "state"); |
| 221 | } catch (TestUtils.TestUtilsException e) { |
| 222 | logger.error("Could not get state of task."); |
| 223 | e.printStackTrace(); |
| 224 | return false; |
| 225 | } |
| 226 | //If cancelled or already executed stop here. |
| 227 | if (currentState == executedState || currentState == cancelledState) { |
| 228 | return false; |
| 229 | } else if (currentState == virginState) { |
| 230 | logger.error("Task was set for execution without being scheduled."); |
| 231 | return false; |
| 232 | } else if (currentState == scheduledState) { |
| 233 | long period; |
| 234 | |
| 235 | try { |
| 236 | period = TestUtils.getField(task, "period"); |
| 237 | } catch (TestUtils.TestUtilsException e) { |
| 238 | logger.error("Could not read period of task."); |
| 239 | e.printStackTrace(); |
| 240 | return false; |
| 241 | } |
| 242 | //Period of zero means one time execution. |
| 243 | if (period == 0) { |
| 244 | try { |
| 245 | TestUtils.setField(task, "state", executedState); |
| 246 | } catch (TestUtils.TestUtilsException e) { |
| 247 | logger.error("Could not set executed state."); |
| 248 | e.printStackTrace(); |
| 249 | return false; |
| 250 | } |
Aaron Kruglikov | f27dba6 | 2015-10-27 15:06:29 -0700 | [diff] [blame] | 251 | if (runLocally) { |
| 252 | task.run(); |
| 253 | } else { |
| 254 | executorService.execute(task); |
| 255 | } |
Aaron Kruglikov | 4ce0b04 | 2015-10-07 14:04:17 -0700 | [diff] [blame] | 256 | return true; |
| 257 | } else { |
| 258 | //Calculate next execution time, using absolute value of period |
| 259 | long nextTime = (period > 0) ? (timerKeeper.currentTimeInMillis() + period) : |
| 260 | (timerKeeper.currentTimeInMillis() - period); |
| 261 | try { |
| 262 | TestUtils.setField(task, "nextExecutionTime", nextTime); |
| 263 | } catch (TestUtils.TestUtilsException e) { |
| 264 | logger.error("Could not set next execution time."); |
| 265 | e.printStackTrace(); |
| 266 | return false; |
| 267 | } |
| 268 | //Schedule next execution |
| 269 | queue.insertOrdered(task); |
Aaron Kruglikov | f27dba6 | 2015-10-27 15:06:29 -0700 | [diff] [blame] | 270 | if (runLocally) { |
| 271 | task.run(); |
| 272 | } else { |
| 273 | executorService.execute(task); |
| 274 | } |
Aaron Kruglikov | 4ce0b04 | 2015-10-07 14:04:17 -0700 | [diff] [blame] | 275 | return true; |
| 276 | } |
| 277 | } |
| 278 | logger.error("State property of {} is in an illegal state and did not execute.", task); |
| 279 | return false; |
| 280 | } |
| 281 | |
| 282 | /** |
| 283 | * Executes all tasks in the queue scheduled for execution up to and including the current time. |
| 284 | * |
| 285 | * @return the total number of tasks run, -1 if failure |
| 286 | */ |
| 287 | private int executeEventsUpToPresent() { |
| 288 | int totalRun = 0; |
| 289 | if (queue.isEmpty()) { |
| 290 | return -1; |
| 291 | } |
| 292 | TimerTask currTask = queue.peek(); |
| 293 | long currExecTime; |
| 294 | try { |
| 295 | currExecTime = TestUtils.getField(currTask, "nextExecutionTime"); |
| 296 | } catch (TestUtils.TestUtilsException e) { |
| 297 | e.printStackTrace(); |
| 298 | throw new RuntimeException("Could not get nextExecutionTime"); |
| 299 | } |
| 300 | while (currExecTime <= timerKeeper.currentTimeInMillis()) { |
| 301 | if (executeTask(queue.pop())) { |
| 302 | totalRun++; |
| 303 | } |
| 304 | if (queue.isEmpty()) { |
| 305 | break; |
| 306 | } |
| 307 | currTask = queue.peek(); |
| 308 | try { |
| 309 | currExecTime = TestUtils.getField(currTask, "nextExecutionTime"); |
| 310 | } catch (TestUtils.TestUtilsException e) { |
| 311 | e.printStackTrace(); |
| 312 | throw new RuntimeException("Could not get nextExecutionTime"); |
| 313 | } |
| 314 | } |
| 315 | return totalRun; |
| 316 | } |
| 317 | |
| 318 | /** |
| 319 | * Populates the static fields from timer task. Should only be called once. |
| 320 | */ |
| 321 | private void populateStatics(TimerTask task) { |
| 322 | try { |
| 323 | virginState = TestUtils.getField(task, "VIRGIN"); |
| 324 | scheduledState = TestUtils.getField(task, "SCHEDULED"); |
| 325 | executedState = TestUtils.getField(task, "EXECUTED"); |
| 326 | cancelledState = TestUtils.getField(task, "CANCELLED"); |
| 327 | staticsPopulated = true; |
| 328 | } catch (TestUtils.TestUtilsException e) { |
| 329 | e.printStackTrace(); |
| 330 | } |
| 331 | } |
| 332 | |
| 333 | /** |
| 334 | * A class used to maintain the virtual time. |
| 335 | */ |
| 336 | private class TimerKeeper { |
| 337 | |
| 338 | private long currentTime = 0; |
| 339 | |
| 340 | /** |
| 341 | * Returns the virtual current time in millis. |
| 342 | * |
| 343 | * @return long representing simulated current time. |
| 344 | */ |
| 345 | long currentTimeInMillis() { |
| 346 | return currentTime; |
| 347 | } |
| 348 | |
| 349 | /** |
| 350 | * Returns the new simulated current time in millis after advancing the absolute value of millis to advance. |
| 351 | * Triggers event execution of all events scheduled for execution at times up to and including the returned |
| 352 | * time. Passing in the number zero has no effect. |
| 353 | * |
| 354 | * @param millisToAdvance the number of millis to advance. |
| 355 | * @return a long representing the current simulated time in millis |
| 356 | */ |
| 357 | long advanceTimeMillis(long millisToAdvance) { |
| 358 | currentTime = (millisToAdvance >= 0) ? (currentTime + millisToAdvance) : (currentTime - millisToAdvance); |
| 359 | if (millisToAdvance != 0) { |
| 360 | executeEventsUpToPresent(); |
| 361 | } |
| 362 | return currentTime; |
| 363 | } |
| 364 | } |
| 365 | |
| 366 | /** |
| 367 | * A queue backed by a linked list. Keeps elements sorted in ascending order of execution time. All calls are safe |
| 368 | * even on empty queue's. |
| 369 | */ |
| 370 | private class TaskQueue { |
| 371 | private final LinkedList<TimerTask> taskList = Lists.newLinkedList(); |
| 372 | |
| 373 | /** |
| 374 | * Adds the task to the queue in ascending order of scheduled execution. If execution time has already passed |
| 375 | * execute immediately. |
| 376 | * |
| 377 | * @param task the task to be added to the queue |
| 378 | */ |
| 379 | void insertOrdered(TimerTask task) { |
| 380 | //Using O(N) insertion because random access is expensive in linked lists worst case is 2N links followed |
| 381 | // for binary insertion vs N for simple insertion. |
| 382 | checkNotNull(task); |
| 383 | if (!staticsPopulated) { |
| 384 | populateStatics(task); |
| 385 | } |
| 386 | long insertTime; |
| 387 | try { |
| 388 | insertTime = TestUtils.getField(task, "nextExecutionTime"); |
| 389 | TestUtils.setField(task, "state", scheduledState); |
| 390 | } catch (TestUtils.TestUtilsException e) { |
| 391 | e.printStackTrace(); |
| 392 | return; |
| 393 | } |
| 394 | //If the task was scheduled in the past or for the current time run it immediately and do not add to the |
| 395 | // queue, subsequent executions will be scheduled as normal |
| 396 | if (insertTime <= timerKeeper.currentTimeInMillis()) { |
| 397 | executeTask(task); |
| 398 | return; |
| 399 | } |
| 400 | |
| 401 | Iterator<TimerTask> iter = taskList.iterator(); |
| 402 | int positionCounter = 0; |
| 403 | long nextTaskTime; |
| 404 | TimerTask currentTask; |
| 405 | while (iter.hasNext()) { |
| 406 | currentTask = iter.next(); |
| 407 | try { |
| 408 | nextTaskTime = TestUtils.getField(currentTask, "nextExecutionTime"); |
| 409 | } catch (TestUtils.TestUtilsException e) { |
| 410 | e.printStackTrace(); |
| 411 | return; |
| 412 | } |
| 413 | if (insertTime < nextTaskTime) { |
| 414 | taskList.add(positionCounter, task); |
| 415 | return; |
| 416 | } |
| 417 | positionCounter++; |
| 418 | } |
| 419 | taskList.addLast(task); |
| 420 | } |
| 421 | |
| 422 | /** |
| 423 | * Returns the first item in the queue (next scheduled for execution) without removing it, returns null if the |
| 424 | * queue is empty. |
| 425 | * |
| 426 | * @return the next TimerTask to run or null if the queue is empty |
| 427 | */ |
| 428 | TimerTask peek() { |
| 429 | if (taskList.isEmpty()) { |
| 430 | return null; |
| 431 | } |
| 432 | return taskList.getFirst(); |
| 433 | } |
| 434 | |
| 435 | /** |
| 436 | * Returns and removes the first item in the queue or null if it is empty. |
| 437 | * |
| 438 | * @return the first element of the queue or null if the queue is empty |
| 439 | */ |
| 440 | TimerTask pop() { |
| 441 | if (taskList.isEmpty()) { |
| 442 | return null; |
| 443 | } |
| 444 | return taskList.pop(); |
| 445 | } |
| 446 | |
| 447 | /** |
| 448 | * Performs a sort on the set of timer tasks, earliest task is first. Does nothing if queue is empty. |
| 449 | */ |
| 450 | void sort() { |
| 451 | if (taskList.isEmpty()) { |
| 452 | return; |
| 453 | } |
| 454 | taskList.sort((o1, o2) -> { |
| 455 | checkNotNull(o1); |
| 456 | checkNotNull(o2); |
| 457 | long executionTimeOne; |
| 458 | long executionTimeTwo; |
| 459 | try { |
| 460 | executionTimeOne = TestUtils.getField(o1, "nextExecutionTime"); |
| 461 | executionTimeTwo = TestUtils.getField(o2, "nextExecutionTime"); |
| 462 | } catch (TestUtils.TestUtilsException e) { |
| 463 | e.printStackTrace(); |
| 464 | throw new RuntimeException("Could not get next execution time."); |
| 465 | } |
| 466 | if (executionTimeOne == executionTimeTwo) { |
| 467 | return 0; |
| 468 | } else if (executionTimeOne < executionTimeTwo) { |
| 469 | return -1; |
| 470 | } else { |
| 471 | return 1; |
| 472 | } |
| 473 | }); |
| 474 | } |
| 475 | |
| 476 | /** |
| 477 | * Returns whether the queue is currently empty. |
| 478 | * |
| 479 | * @return true if the queue is empty, false otherwise |
| 480 | */ |
| 481 | boolean isEmpty() { |
| 482 | return taskList.isEmpty(); |
| 483 | } |
| 484 | |
| 485 | /** |
| 486 | * Clears the underlying list of the queue. |
| 487 | */ |
| 488 | void clear() { |
| 489 | taskList.clear(); |
| 490 | } |
| 491 | |
| 492 | /** |
| 493 | * Removes all cancelled tasks from the queue. Has no effect on behavior. |
| 494 | * |
| 495 | * @return returns the total number of items removed, -1 if list is empty or failure occurs. |
| 496 | */ |
| 497 | int removeCancelled() { |
| 498 | if (taskList.isEmpty()) { |
| 499 | return -1; |
| 500 | } |
| 501 | int removedCount = 0; |
| 502 | Iterator<TimerTask> taskIterator = taskList.iterator(); |
| 503 | TimerTask currTask; |
| 504 | int currState; |
| 505 | while (taskIterator.hasNext()) { |
| 506 | currTask = taskIterator.next(); |
| 507 | try { |
| 508 | currState = TestUtils.getField(currTask, "state"); |
| 509 | } catch (TestUtils.TestUtilsException e) { |
| 510 | logger.error("Could not get task state."); |
| 511 | e.printStackTrace(); |
| 512 | return -1; |
| 513 | } |
| 514 | if (currState == cancelledState) { |
| 515 | removedCount++; |
| 516 | taskIterator.remove(); |
| 517 | } |
| 518 | } |
| 519 | return removedCount; |
| 520 | } |
| 521 | } |
| 522 | } |