1 /*
   2  * Copyright (c) 1995, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.  Oracle designates this
   8  * particular file as subject to the "Classpath" exception as provided
   9  * by Oracle in the LICENSE file that accompanied this code.
  10  *
  11  * This code is distributed in the hope that it will be useful, but WITHOUT
  12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  14  * version 2 for more details (a copy is included in the LICENSE file that
  15  * accompanied this code).
  16  *
  17  * You should have received a copy of the GNU General Public License version
  18  * 2 along with this work; if not, write to the Free Software Foundation,
  19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  20  *
  21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  22  * or visit www.oracle.com if you need additional information or have any
  23  * questions.
  24  */
  25 
  26 package sun.misc;
  27 
  28 /**
  29     A Timer object is used by algorithms that require timed events.
  30     For example, in an animation loop, a timer would help in
  31     determining when to change frames.
  32 
  33     A timer has an interval which determines when it "ticks";
  34     that is, a timer delays for the specified interval and then
  35     it calls the owner's tick() method.
  36 
  37     Here's an example of creating a timer with a 5 sec interval:
  38 
  39     <pre>
  40     class Main implements Timeable {
  41         public void tick(Timer timer) {
  42             System.out.println("tick");
  43         }
  44         public static void main(String args[]) {
  45             (new Timer(this, 5000)).cont();
  46         }
  47     }
  48     </pre>
  49 
  50     A timer can be stopped, continued, or reset at any time.
  51     A timer's state is not stopped while it's calling the
  52     owner's tick() method.
  53 
  54     A timer can be regular or irregular.  If in regular mode,
  55     a timer ticks at the specified interval, regardless of
  56     how long the owner's tick() method takes.  While the timer
  57     is running, no ticks are ever discarded.  That means that if
  58     the owner's tick() method takes longer than the interval,
  59     the ticks that would have occurred are delivered immediately.
  60 
  61     In irregular mode, a timer starts delaying for exactly
  62     the specified interval only after the tick() method returns.
  63 
  64     Synchronization issues: do not hold the timer's monitor
  65     while calling any of the Timer operations below otherwise
  66     the Timer class will deadlock.
  67 
  68     @author     Patrick Chan
  69 */
  70 
  71 /*
  72     Synchronization issues:  there are two data structures that
  73     require locking.  A Timer object and the Timer queue
  74     (described in the TimerThread class).  To avoid deadlock,
  75     the timer queue monitor is always acquired before the timer
  76     object's monitor.  However, the timer queue monitor is acquired
  77     only if the timer operation will make use of the timer
  78     queue, e.g. stop().
  79 
  80     The class monitor on the class TimerThread severs as the monitor
  81     to the timer queue.
  82 
  83     Possible feature: perhaps a timer should have an associated
  84     thread priority.  The thread that makes the callback temporarily
  85     takes on that priority before calling the owner's tick() method.
  86 */
  87 
  88 public class Timer {
  89     /**
  90      * This is the owner of the timer.  Its tick method is
  91      * called when the timer ticks.
  92      */
  93     public Timeable owner;
  94 
  95     /*
  96      * This is the interval of time in ms.
  97      */
  98     long interval;
  99 
 100     /*
 101      * This variable is used for two different purposes.
 102      * This is done in order to save space.
 103      * If 'stopped' is true, this variable holds the time
 104      * that the timer was stopped; otherwise, this variable
 105      * is used by the TimerThread to determine when the timer
 106      * should tick.
 107      */
 108     long sleepUntil;
 109 
 110     /*
 111      * This is the time remaining before the timer ticks.  It
 112      * is only valid if 'stopped' is true.  If the timer is
 113      * continued, the next tick will happen remaingTime
 114      * milliseconds later.
 115      */
 116     long remainingTime;
 117 
 118     /*
 119      * True iff the timer is in regular mode.
 120      */
 121     boolean regular;
 122 
 123     /*
 124      * True iff the timer has been stopped.
 125      */
 126     boolean stopped;
 127 
 128     /* **************************************************************
 129      * Timer queue-related variables
 130      * ************************************************************** */
 131 
 132     /*
 133      * A link to another timer object.  This is used while the
 134      * timer object is enqueued in the timer queue.
 135      */
 136     Timer next;
 137 
 138     /* **************************************************************
 139      * Timer methods
 140      * ************************************************************** */
 141 
 142     /*
 143      * This variable holds a handle to the TimerThread class for
 144      * the purpose of getting at the class monitor.  The reason
 145      * why Class.forName("TimerThread") is not used is because it
 146      * doesn't appear to work when loaded via a net class loader.
 147      */
 148     static TimerThread timerThread = null;
 149 
 150     /**
 151      * Creates a timer object that is owned by 'owner' and
 152      * with the interval 'interval' milliseconds.  The new timer
 153      * object is stopped and is regular.  getRemainingTime()
 154      * return 'interval' at this point.  getStopTime() returns
 155      * the time this object was created.
 156      * @param owner    owner of the timer object
 157      * @param interval interval of the timer in milliseconds
 158      */
 159     public Timer(Timeable owner, long interval) {
 160         this.owner = owner;
 161         this.interval = interval;
 162         remainingTime = interval;
 163         regular = true;
 164         sleepUntil = System.currentTimeMillis();
 165         stopped = true;
 166         synchronized (getClass()) {
 167             if (timerThread == null) {
 168                 timerThread = new TimerThread();
 169             }
 170         }
 171     }
 172 
 173     /**
 174      * Returns true if this timer is stopped.
 175      */
 176     public synchronized boolean isStopped() {
 177         return stopped;
 178     }
 179 
 180     /**
 181      * Stops the timer.  The amount of time the timer has already
 182      * delayed is saved so if the timer is continued, it will only
 183      * delay for the amount of time remaining.
 184      * Note that even after stopping a timer, one more tick may
 185      * still occur.
 186      * This method is MT-safe; i.e. it is synchronized but for
 187      * implementation reasons, the synchronized modifier cannot
 188      * be included in the method declaration.
 189      */
 190     public void stop() {
 191         long now = System.currentTimeMillis();
 192 
 193         synchronized (timerThread) {
 194             synchronized (this) {
 195                 if (!stopped) {
 196                     TimerThread.dequeue(this);
 197                     remainingTime = Math.max(0, sleepUntil - now);
 198                     sleepUntil = now;        // stop time
 199                     stopped = true;
 200                 }
 201             }
 202         }
 203     }
 204 
 205     /**
 206      * Continue the timer.  The next tick will come at getRemainingTime()
 207      * milliseconds later.  If the timer is not stopped, this
 208      * call will be a no-op.
 209      * This method is MT-safe; i.e. it is synchronized but for
 210      * implementation reasons, the synchronized modifier cannot
 211      * be included in the method declaration.
 212      */
 213     public void cont() {
 214         synchronized (timerThread) {
 215             synchronized (this) {
 216                 if (stopped) {
 217                     // The TimerTickThread avoids requeuing the
 218                     // timer only if the sleepUntil value has changed.
 219                     // The following guarantees that the sleepUntil
 220                     // value will be different; without this guarantee,
 221                     // it's theoretically possible for the timer to be
 222                     // inserted twice.
 223                     sleepUntil = Math.max(sleepUntil + 1,
 224                         System.currentTimeMillis() + remainingTime);
 225                     TimerThread.enqueue(this);
 226                     stopped = false;
 227                 }
 228             }
 229         }
 230     }
 231 
 232     /**
 233      * Resets the timer's remaining time to the timer's interval.
 234      * If the timer's running state is not altered.
 235      */
 236     public void reset() {
 237         synchronized (timerThread) {
 238             synchronized (this) {
 239                 setRemainingTime(interval);
 240             }
 241         }
 242     }
 243 
 244     /**
 245      * Returns the time at which the timer was last stopped.  The
 246      * return value is valid only if the timer is stopped.
 247      */
 248     public synchronized long getStopTime() {
 249         return sleepUntil;
 250     }
 251 
 252     /**
 253      * Returns the timer's interval.
 254      */
 255     public synchronized long getInterval() {
 256         return interval;
 257     }
 258 
 259     /**
 260      * Changes the timer's interval.  The new interval setting
 261      * does not take effect until after the next tick.
 262      * This method does not alter the remaining time or the
 263      * running state of the timer.
 264      * @param interval new interval of the timer in milliseconds
 265      */
 266     public synchronized void setInterval(long interval) {
 267         this.interval = interval;
 268     }
 269 
 270     /**
 271      * Returns the remaining time before the timer's next tick.
 272      * The return value is valid only if timer is stopped.
 273      */
 274     public synchronized long getRemainingTime() {
 275         return remainingTime;
 276     }
 277 
 278     /**
 279      * Sets the remaining time before the timer's next tick.
 280      * This method does not alter the timer's running state.
 281      * This method is MT-safe; i.e. it is synchronized but for
 282      * implementation reasons, the synchronized modifier cannot
 283      * be included in the method declaration.
 284      * @param time new remaining time in milliseconds.
 285      */
 286     public void setRemainingTime(long time) {
 287         synchronized (timerThread) {
 288             synchronized (this) {
 289                 if (stopped) {
 290                     remainingTime = time;
 291                 } else {
 292                     stop();
 293                     remainingTime = time;
 294                     cont();
 295                 }
 296             }
 297         }
 298     }
 299 
 300     /**
 301      * In regular mode, a timer ticks at the specified interval,
 302      * regardless of how long the owner's tick() method takes.
 303      * While the timer is running, no ticks are ever discarded.
 304      * That means that if the owner's tick() method takes longer
 305      * than the interval, the ticks that would have occurred are
 306      * delivered immediately.
 307      *
 308      * In irregular mode, a timer starts delaying for exactly
 309      * the specified interval only after the tick() method returns.
 310      */
 311     public synchronized void setRegular(boolean regular) {
 312         this.regular = regular;
 313     }
 314 
 315     /*
 316      * This method is used only for testing purposes.
 317      */
 318     protected Thread getTimerThread() {
 319         return TimerThread.timerThread;
 320     }
 321 }
 322 
 323 
 324 /*
 325 
 326 This class implements the timer queue and is exclusively used by the
 327 Timer class.  There are only two methods exported to the Timer class -
 328 enqueue, for inserting a timer into queue and dequeue, for removing
 329 a timer from the queue.
 330 
 331 A timer in the timer queue is awaiting a tick.  When a timer is to be
 332 ticked, it is removed from the timer queue before the owner's tick()
 333 method is called.
 334 
 335 A single timer thread manages the timer queue.  This timer thread
 336 looks at the head of the timer queue and delays until it's time for
 337 the timer to tick.  When the time comes, the timer thread creates a
 338 callback thread to call the timer owner's tick() method.  The timer
 339 thread then processes the next timer in the queue.
 340 
 341 When a timer is inserted at the head of the queue, the timer thread is
 342 notified.  This causes the timer thread to prematurely wake up and
 343 process the new head of the queue.
 344 
 345 */
 346 
 347 class TimerThread extends Thread {
 348     /*
 349      * Set to true to get debugging output.
 350      */
 351     public static boolean debug = false;
 352 
 353     /*
 354      * This is a handle to the thread managing the thread queue.
 355      */
 356     static TimerThread timerThread;
 357 
 358     /*
 359      * This flag is set if the timer thread has been notified
 360      * while it was in the timed wait.  This flag allows the
 361      * timer thread to tell whether or not the wait completed.
 362      */
 363     static boolean notified = false;
 364 
 365     protected TimerThread() {
 366         super("TimerThread");
 367         timerThread = this;
 368         start();
 369     }
 370 
 371     public synchronized void run() {
 372         while (true) {
 373             long delay;
 374 
 375             while (timerQueue == null) {
 376                 try {
 377                     wait();
 378                 } catch (InterruptedException ex) {
 379                    // Just drop through and check timerQueue.
 380                 }
 381             }
 382             notified = false;
 383             delay = timerQueue.sleepUntil - System.currentTimeMillis();
 384             if (delay > 0) {
 385                 try {
 386                     wait(delay);
 387                 } catch (InterruptedException ex) {
 388                     // Just drop through.
 389                 }
 390             }
 391             // remove from timer queue.
 392             if (!notified) {
 393                 Timer timer = timerQueue;
 394                 timerQueue = timerQueue.next;
 395                 TimerTickThread thr = TimerTickThread.call(
 396                     timer, timer.sleepUntil);
 397                 if (debug) {
 398                     long delta = (System.currentTimeMillis() - timer.sleepUntil);
 399                     System.out.println("tick(" + thr.getName() + ","
 400                         + timer.interval + ","+delta+ ")");
 401                     if (delta > 250) {
 402                         System.out.println("*** BIG DELAY ***");
 403                     }
 404                 }
 405             }
 406         }
 407     }
 408 
 409     /* *******************************************************
 410        Timer Queue
 411        ******************************************************* */
 412 
 413     /*
 414      * The timer queue is a queue of timers waiting to tick.
 415      */
 416     static Timer timerQueue = null;
 417 
 418     /*
 419      * Uses timer.sleepUntil to determine where in the queue
 420      * to insert the timer object.
 421      * A new ticker thread is created only if the timer
 422      * is inserted at the beginning of the queue.
 423      * The timer must not already be in the queue.
 424      * Assumes the caller has the TimerThread monitor.
 425      */
 426     static protected void enqueue(Timer timer) {
 427         Timer prev = null;
 428         Timer cur = timerQueue;
 429 
 430         if (cur == null || timer.sleepUntil <= cur.sleepUntil) {
 431             // insert at front of queue
 432             timer.next = timerQueue;
 433             timerQueue = timer;
 434             notified = true;
 435             timerThread.notify();
 436         } else {
 437             do {
 438                 prev = cur;
 439                 cur = cur.next;
 440             } while (cur != null && timer.sleepUntil > cur.sleepUntil);
 441             // insert or append to the timer queue
 442             timer.next = cur;
 443             prev.next = timer;
 444         }
 445         if (debug) {
 446             long now = System.currentTimeMillis();
 447 
 448             System.out.print(Thread.currentThread().getName()
 449                 + ": enqueue " + timer.interval + ": ");
 450             cur = timerQueue;
 451             while(cur != null) {
 452                 long delta = cur.sleepUntil - now;
 453                 System.out.print(cur.interval + "(" + delta + ") ");
 454                 cur = cur.next;
 455             }
 456             System.out.println();
 457         }
 458     }
 459 
 460     /*
 461      * If the timer is not in the queue, returns false;
 462      * otherwise removes the timer from the timer queue and returns true.
 463      * Assumes the caller has the TimerThread monitor.
 464      */
 465     static protected boolean dequeue(Timer timer) {
 466         Timer prev = null;
 467         Timer cur = timerQueue;
 468 
 469         while (cur != null && cur != timer) {
 470             prev = cur;
 471             cur = cur.next;
 472         }
 473         if (cur == null) {
 474             if (debug) {
 475                 System.out.println(Thread.currentThread().getName()
 476                     + ": dequeue " + timer.interval + ": no-op");
 477             }
 478             return false;
 479         }       if (prev == null) {
 480             timerQueue = timer.next;
 481             notified = true;
 482             timerThread.notify();
 483         } else {
 484             prev.next = timer.next;
 485         }
 486         timer.next = null;
 487         if (debug) {
 488             long now = System.currentTimeMillis();
 489 
 490             System.out.print(Thread.currentThread().getName()
 491                 + ": dequeue " + timer.interval + ": ");
 492             cur = timerQueue;
 493             while(cur != null) {
 494                 long delta = cur.sleepUntil - now;
 495                 System.out.print(cur.interval + "(" + delta + ") ");
 496                 cur = cur.next;
 497             }
 498             System.out.println();
 499         }
 500         return true;
 501     }
 502 
 503     /*
 504      * Inserts the timer back into the queue.  This method
 505      * is used by a callback thread after it has called the
 506      * timer owner's tick() method.  This method recomputes
 507      * the sleepUntil field.
 508      * Assumes the caller has the TimerThread and Timer monitor.
 509      */
 510     protected static void requeue(Timer timer) {
 511         if (!timer.stopped) {
 512             long now = System.currentTimeMillis();
 513             if (timer.regular) {
 514                 timer.sleepUntil += timer.interval;
 515             } else {
 516                 timer.sleepUntil = now + timer.interval;
 517             }
 518             enqueue(timer);
 519         } else if (debug) {
 520             System.out.println(Thread.currentThread().getName()
 521                 + ": requeue " + timer.interval + ": no-op");
 522         }
 523     }
 524 }
 525 
 526 /*
 527 
 528 This class implements a simple thread whose only purpose is to call a
 529 timer owner's tick() method.  A small fixed-sized pool of threads is
 530 maintained and is protected by the class monitor.  If the pool is
 531 exhausted, a new thread is temporarily created and destroyed when
 532 done.
 533 
 534 A thread that's in the pool waits on it's own monitor.  When the
 535 thread is retrieved from the pool, the retriever notifies the thread's
 536 monitor.
 537 
 538 */
 539 
 540 class TimerTickThread extends Thread {
 541     /*
 542      * Maximum size of the thread pool.
 543      */
 544     static final int MAX_POOL_SIZE = 3;
 545 
 546     /*
 547      * Number of threads in the pool.
 548      */
 549     static int curPoolSize = 0;
 550 
 551     /*
 552      * The pool of timer threads.
 553      */
 554     static TimerTickThread pool = null;
 555 
 556     /*
 557      * Is used when linked into the thread pool.
 558      */
 559     TimerTickThread next = null;
 560 
 561     /*
 562      * This is the handle to the timer whose owner's
 563      * tick() method will be called.
 564      */
 565     Timer timer;
 566 
 567     /*
 568      * The value of a timer's sleepUntil value is captured here.
 569      * This is used to determine whether or not the timer should
 570      * be reinserted into the queue.  If the timer's sleepUntil
 571      * value has changed, the timer is not reinserted.
 572      */
 573     long lastSleepUntil;
 574 
 575     /*
 576      * Creates a new callback thread to call the timer owner's
 577      * tick() method.  A thread is taken from the pool if one
 578      * is available, otherwise, a new thread is created.
 579      * The thread handle is returned.
 580      */
 581     protected static synchronized TimerTickThread call(
 582             Timer timer, long sleepUntil) {
 583         TimerTickThread thread = pool;
 584 
 585         if (thread == null) {
 586             // create one.
 587             thread = new TimerTickThread();
 588             thread.timer = timer;
 589             thread.lastSleepUntil = sleepUntil;
 590             thread.start();
 591         } else {
 592             pool = pool.next;
 593             thread.timer = timer;
 594             thread.lastSleepUntil = sleepUntil;
 595             synchronized (thread) {
 596                 thread.notify();
 597             }
 598         }
 599         return thread;
 600     }
 601 
 602     /*
 603      * Returns false if the thread should simply exit;
 604      * otherwise the thread is returned the pool, where
 605      * it waits to be notified.  (I did try to use the
 606      * class monitor but the time between the notify
 607      * and breaking out of the wait seemed to take
 608      * significantly longer; need to look into this later.)
 609      */
 610     private boolean returnToPool() {
 611         synchronized (getClass()) {
 612             if (curPoolSize >= MAX_POOL_SIZE) {
 613                 return false;
 614             }
 615             next = pool;
 616             pool = this;
 617             curPoolSize++;
 618             timer = null;
 619         }
 620         while (timer == null) {
 621             synchronized (this) {
 622                 try {
 623                     wait();
 624                 } catch (InterruptedException ex) {
 625                    // Just drop through and retest timer.
 626                 }
 627             }
 628         }
 629         synchronized (getClass()) {
 630             curPoolSize--;
 631         }
 632         return true;
 633     }
 634 
 635     public void run() {
 636         do {
 637             timer.owner.tick(timer);
 638             synchronized (TimerThread.timerThread) {
 639                 synchronized (timer) {
 640                     if (lastSleepUntil == timer.sleepUntil) {
 641                         TimerThread.requeue(timer);
 642                     }
 643                 }
 644             }
 645         } while (returnToPool());
 646     }
 647 }