/*static char *SCCSID = "@(#)tom.h	6.4 91/06/01";*/
/*      static char *SCCSID = "@(#)tom.h	6.4 91/06/01" */

/***    TOM.H - Timeout Manager Header File
 *
 *      IBM/Microsoft Confidential
 *
 *      Copyright (c) IBM Corporation 1987, 1989, 1991
 *      Copyright (c) Microsoft Corporation 1987, 1989, 1991
 *
 *      All Rights Reserved
 */


/***ET  toe_s - Timeout Manager Element
 *
 *      A toe_s record is allocated by the caller of TOM, and is
 *      passed in to give TOM enough room to store a timeout and other
 *      required information.   The data must be considered hidden
 *      from the caller of TOM when the TOM event is set.
 *
 *      The TOM Element record contains the following:
 *      toe_ptoeNext    - Next toe in circular, doubly-linked list.
 *      toe_ptoePrev    - Previous toe in circular, doubly-linked list.
 *      toe_cmsec       - Destination Time (allowed to wrap)
 *      toe_worker      - Worker index
 *
 *      The toe_s record must be in resident memory.
 *
 *      ------------------------------------------
 *
 *      As the TCB must contain at least one toe_s structure, the
 *      structure was placed into tkexport.h.  However, the contents
 *      of the structure are not to be read or written by any component
 *      other than TOM.  This is a copy of the structure for reference.
 *
 *      typedef unsigned long toe_worker_t  // could be byte; see tkexport.h
 *
 *      struct  toe_s   {
 *              struct  toe_s  *toe_ptoeNext;
 *              struct  toe_s  *toe_ptoePrev;
 *              unsigned long   toe_cmsec;
 *              toe_worker_t    toe_worker;
 *      };
 *
 *      typedef struct  toe_s   toe_t;
 */


/***EC  TOM_W_ - TOM Workers
 *
 *      The TOM_W_ equates tell the timeout manager which function
 *      to call when the timeout event expires, during TOMTick.
 *
 *      When the timeout expires, the worker function will receive
 *      ptoe as it's sole parameter.  The worker's return value is
 *      ignored by TOM.  The timeout event will have already been
 *      cancelled by the time the worker is called, so the worker
 *      should not call TOMCancel.
 *
 *      The TOM worker will be called after EOI, at interrupt time,
 *      with interrupts enabled.  Interrupts will be automatically
 *      re-enabled again after the worker returns, in case it returns
 *      with interrupts disabled.  This rule keep interrupt dispatch
 *      latency high even if a lot of TOM events fire at once.
 *
 */

#define TOM_W_WAKE      0               // Wake a Thread
#define TOM_W_STARVE    1               // Give a Starvation Boost
#define TOM_W_TIMCLEAR  2               // Timer services - Sem Clear
#define TOM_W_BEEPDONE  3               // DosBeep complete
#define TOM_W_VDMMHOOK  4               // VDMM - Call A Hook
#define TOM_W_TIMESLICE 5               // Scheduler Timeslice
#define TOM_W_SWAPSHRINK 6              // Swap file shrinking
#define TOM_W_CODEUNLOCK 7              // Unlock file system code segment

#ifdef TOMTESTWORKER
#define TOM_W_TEST      8               // TOM Test Worker
#endif

#define TOM_W_MAX       9               // Max number of TOM workers


/***LD  TOMapfn - Array of TOM worker functions.
 *
 *      TOMapfn contains a list of the worker functions callable
 *      by TOM.  The function addresses for TOM workers is stored
 *      here.
 *
 *      To add a new TOM worker, define a constant in the above
 *      table, and store the address of the worker in TOMapfn.
 *      The values of TOM_WORKER_MASK and TOM_HIRES_FLAG will have
 *      to be adjusted as well.
 *
 */

extern  void    (*(TOMapfn[TOM_W_MAX])) (toe_t *ptoe);

extern  void    TKTomWake       (toe_t *ptoe);  // TOM_W_WAKE
extern  void    TKTomStarve     (toe_t *ptoe);  // TOM_W_STARVE
extern  void    TIMTomClear     (toe_t *ptoe);  // TOM_W_TIMCLEAR
extern  void    BeepTom         (toe_t *ptoe);  // TOM_W_BEEPDONE
extern  void    VDMMTomHook     (toe_t *ptoe);  // TOM_W_VDMMHOOK
extern  void    TKTomTimeslice  (toe_t *ptoe);  // TOM_W_TIMESLICE
extern  void    SMTomHook       (toe_t *ptoe);  // TOM_W_SWAPSHRINK
extern  void    FSTomCodeUnlock (toe_t *ptoe);  // TOM_W_CODEUNLOCK

#ifdef TOMTESTWORKER
extern  void    tomTestWorker   (toe_t *ptoe);  // TOM_W_TEST
#endif


/***LC  TOM Time Management Constants
 *
 *      Time is managed via Delta-Hashed Hierachical Timing Wheels.
 *
 *      Each timing wheel is a doubly-lined list, with toe_ptoeNext
 *      being elements that wake up later, and toe_ptoePrev being
 *      elements that wake up sooner, (if toe_cmcsec is the same).
 *      The head of the wheel is actually a (partial) list element,
 *      to simplify cancelling a particular timer.
 *
 *      To support 8ms resolution timers without the overhead of a
 *      high constant periodic clock rate, the clock is reprogrammed
 *      to interrupt at 128Hz only if a high-resolution timer is
 *      due to expire in less than 64ms.  Hi resolution timers must
 *      be identified up to 64ms before they fire, since the clock
 *      may only be reprogrammed to 128hz immediately after a full
 *      32hs tick.  This restriction is due to not knowing how much
 *      real-time has passed between clock ticks and the need to keep
 *      SIS_MsCount incrementing accurately regardless of the clock's
 *      frequency.  (See the clock device driver.)
 *
 *      toe_cmsec contains the time that the timer is expected to
 *      fire.  So, (cmsecTomTime - (ptoe-> toe_cmsec)) gives the
 *      number of miliseconds from now, until the event fires.
 *
 *      This "Delta-Time" is basis of the Hierachical Hash Calculation.
 *
 *      The bits of the delta time are divided into Hierachies:
 *      ------------------------------------------------------
 *      N Bits  Bit Range       Time Range (from now)
 *      --------------------------------------------------------
 *      (3)     00 to 02        Within the next 8ms
 *      (2)     03 to 04        Within the next 32ms
 *      (5)     05 to 09        Within the next 1 second
 *      (5)     10 to 14        Within the next 32 seconds
 *      (4)     15 to 18        Within the next 8 minutes
 *      (3)     19 to 21        Within the next 1 hour
 *      (5)     22 to 25        Within the next 1.5 days
 *      (5)     26 to 31        Within the next 49 days
 *
 *      The Hash Table Elements are divided as follows:
 *      ----------------------------------------------
 *      Hash Index       Hash From       Delta Time Limitations
 *      ---------------------------------------------------------
 *      Index 00 to 15   Bits 03 to 06   Bits 07 to 31 must be off
 *      Index 16 only    8ms pending timers bucket
 *      Index 17 only    32ms pending timers bucket
 *      Index 18 to 49   Bits 05 to 09   Bits 10 to 31 must be off
 *      Index 50 to 81   Bits 10 to 14   Bits 15 to 31 must be off
 *      Index 82 to 97   Bits 15 to 18   Bits 19 to 31 must be off
 *      Index 98 to 105  Bits 19 to 21   Bits 22 to 31 must be off
 *      Index 106 only   Bits 22 to 25   Bits 26 to 31 must be off
 *      Index 107 only   Bits 26 to 31   Don't care.
 *      Index 108 only   Migration bucket
 *
 *      The current time (masked appropriately) gives the current
 *      index for each hash order.
 *
 *      When setting a timer, the delta time is calculated, the hash
 *      is computed from that, and the timer is then linked onto the
 *      end of that timing wheel.  The destination time is stored.
 *
 *      When cancelling a timer, the timer is removed from the timing
 *      wheel list.
 *
 *      The overall effect is as follows:
 *      --------------------------------
 *    o Unlimited numbers of timers.
 *    o 8 and 32 msec (timer-tick) granularity.
 *    o Minimal overhead for 8ms resolution timers.
 *    o No granularity penalty for long-term timers.
 *    o Multiple Cancels are safe, after the initial TOMSet call is made.
 *    o Approximated FIFO ordering between timers that fire at the same time.
 *    o TOMSet becomes a small constant time.
 *    o TOMCancel becomes a small constant time.
 *    o TOMTick has a small constant-time overhead, plus the overhead for
 *      migration and fire.
 *    o The firing of any particular timer is a small constant time,
 *      roughly equivalent to TOMCancel.
 *    o A single migration is roughly equivalent to TOMCancel + TOMSet.
 *    o The number of migrations a particular timer experiences depends
 *      on how far in the future the timer is set to expire.  This is
 *      given as follows:
 *
 *      Time Range (from now)     Migrations (Add 1 for high resolution)
 *      -----------------------------------------------------
 *      Within the next 32ms          0
 *      Within the next 1 second      0
 *      Within the next 32 seconds    1
 *      Within the next 8 minutes     1 to 2
 *      Within the next 1 hour        1 to 3
 *      Within the next 1.5 days      1 per hour (up to 32), plus 1 to 4
 *      Within the next 49 days       1 per 1.5 days (up to 32), plus 1 to 35
 *      Forever (-1)                  0
 *
 *      The migrations occur as the orders are incremented.  That is,
 *      the 32-second timers are migrated every 32-seconds, when the
 *      32-second boundary is crossed.
 *
 *      It is also possible to construct Hashed Hierachical Timing
 *      Wheels without the delta-time subtraction, by using the
 *      destination time as the basis of the hash.  However, this
 *      causes performance spikes when migration occus, and increases
 *      the ammount of migration work.   Suppose the hash is constructed
 *      from the absolute time, using the partitioning defined above.
 *      If the current time is one tick earlier than the last time
 *      wrap (0 > cmsecTomTime >= -31), then ALL the timers in the hash
 *      table will collide on the order 5 hash.   This effect occurs on
 *      each order.  This greatly increases the work for TOMTick at the
 *      instant of each time rollover point.
 *
 *      Using a delta time avoids this complication, because when the
 *      timer is set or repositioned, the best possible position is
 *      chosen, given the current time-of-day.  So, a timer on the
 *      "within next hour" list must have been last set or migrated
 *      OVER ONE HOUR AGO, or it would be on one of the lower-order lists.
 *
 */

#define TOM_8MS_MASK            0x00000007      // Bits  0 to  2 (8ms gran.)
#define TOM_32MS_MASK           0x0000001F      // Bits  0 to  4 (32ms gran.)

#define TOM_WORKER_MASK         0x0000001F      // Bits  0 to  4 (worker)
#define TOM_HIRES_FLAG          0x00000020      // Bit   5 (hi res flag)

#define TOM_HIRES_MASK          0x00000078      // Bits 03 to 06
#define TOM_ORDER0_MASK         0x000003E0      // Bits 05 to 09
#define TOM_ORDER1_MASK         0x00007C00      // Bits 10 to 14
#define TOM_ORDER2_MASK         0x00078000      // Bits 15 to 18
#define TOM_ORDER3_MASK         0x00380000      // Bits 19 to 21
#define TOM_ORDER4_MASK         0x07C00000      // Bits 22 to 25
#define TOM_ORDER5_MASK         0xF8000000      // Bits 26 to 31

#define TOM_HIRES_SHIFT          3              // Bits 03 to 06
#define TOM_ORDER0_SHIFT         5              // Bits 05 to 09
#define TOM_ORDER1_SHIFT        10              // Bits 10 to 14
#define TOM_ORDER2_SHIFT        15              // Bits 15 to 18
#define TOM_ORDER3_SHIFT        19              // Bits 19 to 21
#define TOM_ORDER4_SHIFT        22              // Bits 22 to 25
#define TOM_ORDER5_SHIFT        26              // Bits 26 to 31

#define TOM_8MS_TICK            8               //  8 msec granularity
#define TOM_32MS_TICK           32              // 32 msec granularity

#define TOM_HIRES_INCR          (1 << TOM_HIRES_SHIFT)  // Bit  3
#define TOM_ORDER0_INCR         (1 << TOM_ORDER0_SHIFT) // Bit  5
#define TOM_ORDER1_INCR         (1 << TOM_ORDER1_SHIFT) // Bit 10
#define TOM_ORDER2_INCR         (1 << TOM_ORDER2_SHIFT) // Bit 15
#define TOM_ORDER3_INCR         (1 << TOM_ORDER3_SHIFT) // Bit 19
#define TOM_ORDER4_INCR         (1 << TOM_ORDER4_SHIFT) // Bit 22
#define TOM_ORDER5_INCR         (1 << TOM_ORDER5_SHIFT) // Bit 26

#define TOM_HIRES_LIMIT_MASK    0xFFFFFFC0      // Bits 06 to 31 must be off
#define TOM_ORDER0_LIMIT_MASK   0xFFFFFC00      // Bits 10 to 31 must be off
#define TOM_ORDER1_LIMIT_MASK   0xFFFF8000      // Bits 15 to 31 must be off
#define TOM_ORDER2_LIMIT_MASK   0xFFF80000      // Bits 19 to 31 must be off
#define TOM_ORDER3_LIMIT_MASK   0xFFC00000      // Bits 22 to 31 must be off
#define TOM_ORDER4_LIMIT_MASK   0xF8000000      // Bits 26 to 31 must be off
#define TOM_ORDER5_LIMIT_MASK   0               // Don't care.

#define TOM_HIRES_HASHSIZE      16              // Width of hi res hash
#define TOM_NEXT8_HASHSIZE       1              // Width of pending 8ms list
#define TOM_NEXT32_HASHSIZE      1              // Width of pending 32ms list
#define TOM_ORDER0_HASHSIZE     32              // Width of order 0 hash
#define TOM_ORDER1_HASHSIZE     32              // Width of order 1 hash
#define TOM_ORDER2_HASHSIZE     16              // Width of order 2 hash
#define TOM_ORDER3_HASHSIZE      8              // Width of order 3 hash
#define TOM_ORDER4_HASHSIZE      1              // Width of order 4 hash
#define TOM_ORDER5_HASHSIZE      1              // Width of order 5 hash
#define TOM_MIGRATE_HASHSIZE     1              // Width of migration list

// Total length of time contained in the hi resolution hash buckets.
#define TOM_HIRES_HASHTIME       TOM_HIRES_HASHSIZE * TOM_8MS_TICK

#define TOM_HASHBASE             0
#define TOM_HIRES_HASHBASE       TOM_HASHBASE   // Hi res buckets must be first
#define TOM_NEXT8_HASHBASE       (TOM_HIRES_HASHBASE + TOM_HIRES_HASHSIZE)
#define TOM_NEXT32_HASHBASE      (TOM_NEXT8_HASHBASE + TOM_NEXT8_HASHSIZE)
#define TOM_ORDER0_HASHBASE      (TOM_NEXT32_HASHBASE + TOM_NEXT32_HASHSIZE)
#define TOM_ORDER1_HASHBASE      (TOM_ORDER0_HASHBASE + TOM_ORDER0_HASHSIZE)
#define TOM_ORDER2_HASHBASE      (TOM_ORDER1_HASHBASE + TOM_ORDER1_HASHSIZE)
#define TOM_ORDER3_HASHBASE      (TOM_ORDER2_HASHBASE + TOM_ORDER2_HASHSIZE)
#define TOM_ORDER4_HASHBASE      (TOM_ORDER3_HASHBASE + TOM_ORDER3_HASHSIZE)
#define TOM_ORDER5_HASHBASE      (TOM_ORDER4_HASHBASE + TOM_ORDER4_HASHSIZE)
#define TOM_MIGRATE_HASHBASE     (TOM_ORDER5_HASHBASE + TOM_ORDER5_HASHSIZE)
#define TOM_HASHSIZE             (TOM_MIGRATE_HASHBASE + TOM_MIGRATE_HASHSIZE)
#define TOM_LAST_HASHBASE TOM_MIGRATE_HASHBASE

#define TOM_WAIT_FOREVER        0xFFFFFFFF      // cmsec = -1 => Wait forever


/***LD  tow_s - Timeout Manager Timing Wheel Head
 *
 *      tow_ptoeNext    - next timer
 *      tow_ptoePrev    - previous timer
 *
 */

struct  tow_s {
        toe_t   *tow_ptoeNext;
        toe_t   *tow_ptoePrev;
};

typedef struct  tow_s   tow_t;


/***LD  TOM - Local Timeout Manager Data
 *
 *      cmsecTomTime    - TOM's Time (<= System time) in msec (wraps)
 *      atowHash        - Timeout Wheel Hash Table
 *
 */

extern  ulong_t cmsecTomTime;                   // Current Time Of Day
extern  tow_t   atowHash[TOM_HASHSIZE];         // Timeout Wheel Hash Table

/*XLATOFF*/
/***EP  TOM - Exported Timeout Manager Functions
 *
 *      TOMSet          - Set a timed event to fire soon
 *      TOMCancel       - Cancel a timed event
 *      TOMTick         - Perform TOM Timer Tick processing
 */

extern  void    TOMSet      (toe_t *ptoe, ulong_t cmsec, ulong_t iapfnTom);
extern  void    TOMCancel   (toe_t *ptoe);
extern  void    TOMTick     (ulong_t cmsec, ulong_t fPostEOI);

#define TOMIsSet(ptoe)  ((ptoe) != (ptoe)->toe_ptoeNext)
