4.2.1 Timer servers

The timer server includes a timer allocator to allocate timers and delivers virtual clock interrupts as timers expire.

<Off timer server. >= (U->)
// A timer server.
// 
class off_TmrSrv : public off_HWCompResource {
public:
  // Returns a pointer to the timer allocator.
  virtual off_TmrAllocator *get_allocator(void);

  <Other public methods of off_TmrSrv. >

protected:
  <Other protected methods of off_TmrSrv. >
private:
  off_TmrAllocator t_alloc;
  <Other private members of off_TmrSrv. >

};

Defines off_TmrSrv (links are to index).

<off_TmrSrv::get_allocator implementation. >= (U->)
inline off_TmrAllocator *off_TmrSrv::get_allocator(void) {
  assert(valid()); return &t_alloc;
}

Being a subclass of CompResource we must implement make_available. This method does not have sense for timers thus it simply returns an error code^4.7.

<Other public methods of off_TmrSrv. >= (<-U) [D->]
// Is this identifier a local one?
inline boolean_t is_local(const off_tmr_id_t &tmr);

<Implementation of off_CompResource::make_available. >

Such routine uses is_local.

<off_TmrSrv::is_local implementation. >= (U->)
// Is this identifier a local one?
inline boolean_t off_TmrSrv::is_local(const off_tmr_id_t &tmr) 
{
    return ( tmr.i_slot <= t_alloc.get_length() &&
             (t_alloc+(natural_t)tmr.i_slot)->l_tmr.get_id() == tmr );

}

<Off timer server dependencies. >= (U->) [D->]
#include <flux/types.h>         // for boolean_t natural_t et al.
#include <klib/ids.h>           // for natural_t et al.
#include <klib/HWCompResource.h> // for off_HWCompResource
#include <klib/err.h>            // for err_t 
#include <klib/prot.h>          // for off_Protection
#include <klib/Magic.h>          // for magic numbers
#include <hw/Tmr.h>     // for off_Tmr
#include <hw/TmrAllocator.h>   // for off_TmrAllocator

This implementation uses is_local.

Each timer server is created by its processor. Initially, it is statically allocated with default parameters for its members. Besides, the desired hz is set.

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
// Creates a Timer server.
off_TmrSrv(void); 

<off_TmrSrv::off_TmrSrv implementation. >= (U->)
// Creates a Timer server.
off_TmrSrv::off_TmrSrv(void) :
  off_HWCompResource(off_Protection(),OFF_PRTL_NULL,
                     OFF_ID_NULL,OFF_MAGIC_TMRSRV),
  <Initialize t_alloc. >,
  t_hz(OFF_TMR_HZ),
  <Initialize other aggregate members of off_TmrSrv. >
{

  do_debug(putchar('t'));
}

The hertz the timer is running at is a system limit.

<Off limits. >=
const int OFF_TMR_HZ = 1000; // Hertz each timer is running at.

Defines OFF_TMR_HZ (links are to index).

<Off timer server implementation dependencies. >= (U->) [D->]
#include <klib/limits.h>        // for OFF_TMR_HZ

<Other private members of off_TmrSrv. >= (<-U) [D->]
natural_t t_hz;                 // HZs for this timer server. 

When the node is started, the timer server is started too.

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
// Starts normal operation for this timer server.
err_t start(const off_mdepTmrSrv &mdep, const off_id_t &id);

<off_TmrSrv::start implementation. >= (U->)
// Starts normal operation for this timer server.
err_t off_TmrSrv::start( const off_mdepTmrSrv &mdep, const off_id_t &id)
{
  assert(valid());
  set_id(id); 

  <Start other members of off_TmrSrv according to mdep. >
  <Start the timer hardware at t_hz. >

  kcout<< "Tmr   #"<<id<< fmt(" (%d timers) ",get_ntmrs());
  kcout<< "started."<< nl;

  return EOK;

}

Here, get_ntmrs returns the number of existing timers.

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
natural_t get_ntmrs(void) const { return off_mdepTmrSrv::get_ntmrs(); }

<Off timer server implementation dependencies. >+= (U->) [<-D->]
#include <assert.h>             // for assert
#include <klib/str.h>           // for kcout.

<Off timer server dependencies. >+= (U->) [<-D->]
#include <hw/mdep/mTmrSrv.h> // for off_mdepTmrSrv

A new member, m_mdep will store the boot time information, which is needed because it provides common information useful to timer server users.

<Other private members of off_TmrSrv. >+= (<-U) [<-D->]
off_mdepTmrSrv   t_mdep;         // Mach. dep. information

<Start other members of off_TmrSrv according to mdep. >= (<-U) [D->]
t_mdep=mdep;

We must define the new magic number used before.

<Off magic numbers. >= [D->]
OFF_MAGIC_TMRSRV, // TmrSrv magic nb.

We can now add another case to the implementation of Magic::nameof.

<off_Magic::nameof case for m_numbers. >= [D->]
case OFF_MAGIC_TMRSRV:
  return "off_TmrSrv";

Timer server users can check their references to processors using this method.

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
// Does this look like a TmrSrv?
boolean_t valid(void) const { return get_magic() == OFF_MAGIC_TMRSRV; }

The interesting part of start is setting the hardware timer. We simply start the machine dependent server and then allocate the clock interrupt (which is initially disabled).

<Start the timer hardware at t_hz. >= (<-U)
mdep.start(t_hz);
t_clkirq=new(nd.get_proc(0).get_irqs(),
             nd.get_proc(0).get_irqs()->get_clk())  off_Irq(get_protection(),
                                                            get_domain(),NULL);

Note how we set a \emph{null} handler. The event table knows that the clock interrupt is part of the system inner cycle and delivers it directly to clock_handler.

<Other private members of off_TmrSrv. >+= (<-U) [<-D->]
off_Irq *t_clkirq;                      // HW clock interrupt. 

<Initialize other aggregate members of off_TmrSrv. >= (<-U) [D->]
t_clkirq(NULL),

<Off timer server dependencies. >+= (U->) [<-D->]
#include <hw/Event.h>           // for off_Irq

\subsection{Timers}

A timer is simply a hardware resource unit which has an associated period of time, might repeat (i.e. reinstall itself when expired), and has an associated virtual clock interrupt (which is raised when the timer expires).

<Off timer. >= (U->)
// A timer.
//
class off_Tmr : public off_HWResUnit {
public:
  // Is this timer periodic?
  inline boolean_t is_periodic(void) const;

  // Which interrupt line is used by this timer?
  inline const off_ev_id_t &get_irqline(void) const;

  <Other public methods of off_Tmr. >
protected:
  <Other protected members of off_Tmr. >
  <Other protected methods of off_Tmr. >
  inline natural_t get_ticks(void);
private:
  natural_t   t_ticks;          // # of ticks left for this timer.
  off_ev_id_t t_irq;            // Interrupt line. 
  <Other private members of off_Tmr. >
};

Defines off_Tmr (links are to index).

<Off timer dependencies. >= (U->) [D->]
#include <klib/HWResUnit.h>     // for off_HWResUnit

<off_Tmr::get_ticks implementation. >= (U->)
inline natural_t off_Tmr::get_ticks(void)
{
  return t_ticks;
}

<off_Tmr::get_irqline implementation. >= (U->)
// Which interrupt line is used by this timer?
inline const off_ev_id_t &off_Tmr::get_irqline(void) const  { return t_irq; }

To know if a timer is periodic we use a resource flag.

<off_Tmr::is_periodic implementation. >= (U->)
// Is this timer periodic?
inline boolean_t off_Tmr::is_periodic(void) const 
{
 return r_flags & OFF_TF_PRD; 
}

<Set timer periodic flag. >= (U->)
if (periodic)
  r_flags |= OFF_TF_PRD;
else
  r_flags &= ~OFF_TF_PRD;

Where we have to define the flag used.

<Off timer flags. >= (U->)
// flag bits for off_Tmrs.
// They are compatible with resource flag bits. 
const unsigned8_t OFF_TF_PRD    = 0x10; // Is it a periodic timer?

Defines OFF_TF_PRD (links are to index).

A timer is created with a prespecified protection and domain identifier. The interrupt line, number of ticks, and the periodic flag must be specified too.

<Other public methods of off_Tmr. >= (<-U) [D->]
// Creates a timer. 
off_Tmr(const off_Protection &p, 
        const off_prtl_id_t &domain,
        const off_tmr_id_t &id,
        off_TmrSrv   *srv,
        natural_t    nticks,
        const off_ev_id_t &irqline,
        boolean_t periodic );

Users use a constructor receiving only the protection, domain, number of ticks, and the periodic flag.

<Other public methods of off_Tmr. >+= (<-U) [<-D->]
// Creates a timer.
off_Tmr(const off_Protection &p, 
        const off_prtl_id_t &domain,
        natural_t    nticks,
        boolean_t periodic );

<off_Tmr::off_Tmr implementation. >= (U->) [D->]
// Creates a timer.
off_Tmr::off_Tmr(const off_Protection &p, 
                 const off_prtl_id_t &domain,
                 natural_t    nticks,
                 boolean_t periodic ) :
  off_HWResUnit(p,domain),
  t_ticks(nticks),
  t_irq(OFF_EU_ID_NULL)
{
  <Set timer periodic flag. >
  <Initialize other private members of off_Tmr. >
}

As you may suspect, each timer delivers a fixed virtual clock interrupt. Users may not choose which clock interrupt is delivered by each timer.

Remaining timer data is pre-initialized. A zero-argument (trap and interrupt) constructor permits declaration of uninitialized events.

<Other public methods of off_Tmr. >+= (<-U) [<-D->]
// Allows uninitialized timers.
off_Tmr(void) : 
  off_HWResUnit(off_Protection(), OFF_PRTL_NULL, OFF_EU_ID_NULL, 
                OFF_MAGIC_TMR, NULL)
{;}

When the timer server is created, another constructor is used to preinitialize fields which will remain fixed.

<Other public methods of off_Tmr. >+= (<-U) [<-D->]
// Preinitializes a timer.
off_Tmr(const off_tmr_id_t &id, const off_ev_id_t &irq, off_TmrSrv *c);

<off_Tmr::off_Tmr implementation. >+= (U->) [<-D]
// Preinitializes a timer.
off_Tmr::off_Tmr(const off_tmr_id_t &id, 
                 const off_ev_id_t &irq, off_TmrSrv *c) :
  off_HWResUnit(id,OFF_MAGIC_TMR,(off_HWCompResource*)c),
  t_ticks(0),
  t_irq(irq)
{;}  

<Off timer dependencies. >+= (U->) [<-D->]
#include <sys/types.h>
#include <klib/ids.h>
#include <klib/err.h>            // for err_t 
#include <klib/prot.h>          // for off_Protection
#include <klib/Magic.h>          // for magic numbers
class off_TmrSrv;

We have to define the new magic number as well as add another case to the implementation of Magic::nameof.

<Off magic numbers. >+= [<-D]
OFF_MAGIC_TMR, // Tmr magic nb.

<off_Magic::nameof case for m_numbers. >+= [<-D]
case OFF_MAGIC_TMR:
  return "off_Tmr";

Timer users can check their references to processors using this method.

<Other public methods of off_Tmr. >+= (<-U) [<-D->]
// Does this look like a Tmr?
boolean_t valid(void) const { return get_magic() == OFF_MAGIC_TMR; }

The new container can also implement its get_umagic method.

<Other protected methods of off_TmrSrv. >= (<-U) [D->]
virtual off_magic_t get_umagic(void) { return OFF_MAGIC_TMR; }

\subsection{Timer allocation}

A timer allocator is a FixedAllocator instantiated at timer server creation time to allocate Tmrs.

<Off timer allocator. >= (U->)
// A timer allocator.
//
class off_TmrAllocator : public off_TFixedAllocator<off_LTmr> {
public: 

  // Creates a timer allocator. 
  off_TmrAllocator(off_Exhausted *r);

  <Other public methods of off_TmrAllocator. >

  const off_TmrAllocator &operator=(const off_TmrAllocator &other) { 
    return (*this=other);
  }
  
private:
  <Other private members of off_TmrAllocator. >
};

Defines off_TmrAllocator (links are to index).

The timer server only needs to supply the appropriate revocation trigger (i.e. himself) to create the timer allocator.

<Initialize t_alloc. >= (<-U)
t_alloc((off_Exhausted*)this)

<Off timer allocator dependencies. >= (U->) [D->]
#include <klib/FixedAllocator.h> // for off_TFixedAllocator et al.

To support the linked lists used in the timer allocator, nodes allocated are actually of type LTmr.

<Off linkable timer. >= (U->)
// A linkable timer. 
//
class off_LTmr : public DLinkedNode {
public:
  off_Tmr l_tmr;
  
  // To allow uninitialized timers. 
  off_LTmr(void) : l_tmr() {;}

  <Other public methods of off_LTmr. >
};

<Off timer allocator dependencies. >+= (U->) [<-D->]
#include <hw/Tmr.h>        // for off_Tmr

The fixed allocator uses a fixed array of LTmrs. There are as many timers as virtual clock interrupts.

<Other private members of off_TmrAllocator. >= (<-U) [D->]
off_LTmr t_tmr[OFF_MDEP_NVINT_MAX]; // Timer slots.  

<Off timer allocator dependencies. >+= (U->) [<-D->]
#include <klib/limits.h>      // for OFF_MDEP_NVINT_MAX

An indexer is also needed.

<Other private members of off_TmrAllocator. >+= (<-U) [<-D]
static off_Indexer<off_LTmr> t_idx; // Linked timer indexer.

<Off timer allocator static members. >= (U->)
off_Indexer<off_LTmr> off_TmrAllocator::t_idx; // Linked timer indexer.

<Off timer allocator dependencies. >+= (U->) [<-D]
#include <klib/Indexer.h>       // for off_Indexer

Timer allocator creation is pretty simple.

<off_TmrAllocator::off_TmrAllocator implementation. >= (U->)
// Creates a timer allocator. 
off_TmrAllocator::off_TmrAllocator(off_Exhausted *r) 
  {;}

Using the allocator, the timer server can allocate and deallocate timers.

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
// Allocates a timer.
off_Tmr *alloc(boolean_t use_revocation=FALSE);
off_Tmr *alloc(const off_tmr_id_t &at, boolean_t use_revocation=FALSE);

// Deallocates a timer.. 
void free(const off_Tmr *rq);

<off_TmrSrv::alloc and free implementation. >= (U->)
// Allocates a timer
off_Tmr *off_TmrSrv::alloc(boolean_t use_revocation)
{
  off_LTmr *lt;
  assert(valid());
  w_lock();
  lt=t_alloc.allocate(use_revocation);
  w_unlock();
  return (lt)?(&lt->l_tmr):(off_Tmr*)NULL;
}

off_Tmr *off_TmrSrv::alloc(const off_tmr_id_t &at, 
                           boolean_t use_revocation)
{
  off_LTmr *lt;
  assert(valid());
  w_lock();
  lt=t_alloc.allocate(at,use_revocation);
  w_unlock();
  return (lt)?(&lt->l_tmr):(off_Tmr*)NULL;

}

// Deallocates a timer
void off_TmrSrv::free(const off_Tmr *t)
{
  off_LTmr *lt=(off_LTmr*)(((char*)t)-(int)&off_LTmr::l_tmr);
  assert(valid() && t);
  w_lock(); 
  t_alloc.deallocate(lt); 
  <Deactivate HW clock interrupt if necessary. >
  w_unlock(); 
}

Timers have their own new and delete operators. The operator new receives the where the slot should be allocated. Operator new uses the timer server alloc method to find an available timer.

<Other public methods of off_Tmr. >+= (<-U) [<-D->]
// Allocate a timer.
void *operator new(size_t s, boolean_t use_revocation=FALSE);
void *operator new(size_t s, const off_tmr_id_t &at,
                   boolean_t use_revocation=FALSE);

// Deallocates this timer.
void operator delete(void *p);

<off_Tmr::operator new implementation. >= (U->)
// Allocate a timer.
void *off_Tmr::operator new(size_t s, boolean_t use_revocation)
{
  off_Tmr *t=nd.get_proc(0).get_tmr().alloc(use_revocation);
  (void)s;
  assert(s && nd.get_proc(0).get_tmr().valid());
  assert(!t || t->valid());
  return (void*)t;
}

void *off_Tmr::operator new(size_t s, const off_tmr_id_t &at,
                            boolean_t use_revocation)
{
  off_Tmr *t=nd.get_proc(0).get_tmr().alloc(at,use_revocation);
  (void)s;
  assert(s && nd.get_proc(0).get_tmr().valid());
  assert(!t || t->valid());
  return (void*)t;
}

<Off timer implementation dependencies. >= (U->) [D->]
#include <node/Node.h>          // for off_Node, nd, etc.

The operator delete does what could be expected.

<off_Tmr::operator delete implementation. >= (U->)
// Deallocates this run queue slot.
void off_Tmr::operator delete(void *p)
{
   off_Tmr *t=(off_Tmr*)p;
  assert(t && t->valid());
  ((off_TmrSrv*)(t->get_container()))->free(t);
}

Timers are pre-initialized when the timer server is started.

<Start other members of off_TmrSrv according to mdep. >+= (<-U) [<-D]
for (natural_t t=0; t< get_ntmrs(); t++){
  off_tmr_id_t tid(get_id(),t);
  off_ev_id_t  irq(nd.get_proc(0).get_irqs()->get_vint0(),
                   t + nd.get_proc(0).get_irqs()->get_vint0());
  (void) new(t_alloc+t) off_LTmr(tid,irq,this);
}

<Off timer server implementation dependencies. >+= (U->) [<-D->]
#include <flux/types.h>         // for boolean_t natural_t et al.

Again, we use a tricky new operator.

<Other public methods of off_LTmr. >= (<-U) [D->]
void *operator new(size_t s, off_LTmr *t) { (void)s; return (void*)t; }

The LTmr constructor pre-initializes each timer in turn using the pre-initialization constructor for Tmrs.

<Other public methods of off_LTmr. >+= (<-U) [<-D]
off_LTmr(const off_tmr_id_t &id, const off_ev_id_t &irq, off_TmrSrv *c) : 
  l_tmr(id,irq,c) {;}

Using the timer allocator, the timer server implements these operators to access existing timers.

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
//Gets a timer from its distributed or physical address.
inline off_Tmr *operator+(off_offset_t t);

<off_TmrSrv::operator+ implementation. >= (U->)
//Gets a timer from its distributed or physical address.
inline off_Tmr *off_TmrSrv::operator+(off_offset_t t)
{
  return &(t_alloc+t)->l_tmr;
}

The implementation uses a redefinition of the operator in the allocator to do it more efficiently.

<Other public methods of off_TmrAllocator. >= (<-U)
//Gets a timer from its distributed or physical address.
inline off_LTmr *operator+(natural_t t);

<off_TmrAllocator::operator + implementation. >= (U->)
//Gets a timer from its distributed or physical address.
inline off_LTmr *off_TmrAllocator::operator+(natural_t t)
{
  return t_tmr+t;
}

\subsection{Timer revocation}

The timer server must implement the notify method used to behave as a resource revocation trigger.

As of today, there is no revocation for timers.

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
// Notifies that run queue is exhausted.
void notify(void) { return; }

\subsection{Timer handling}

The implementation of timers is the one typically used in OSes. We maintain a list of timers in increasing expiration order where each timer keeps the number of ticks to expiration relative to the previous one (which could also be zero).

<Other private members of off_TmrSrv. >+= (<-U) [<-D->]
DLinkedQueue t_events;          // List of pending events.

<Off timer server dependencies. >+= (U->) [<-D->]
#include <klib/dqueue.h>        // for DLinkedQueue

This relative count is handled not by the timer, but by the timer server activate method.

<Other protected members of off_Tmr. >= (<-U)
friend class off_TmrSrv;        // for activate()
natural_t t_rticks;              // Relative number of ticks. 

<Other public methods of off_Tmr. >+= (<-U) [<-D]
// Returns the number of ticks for expiration relative to the previous 
// event.
inline natural_t get_rticks(void);

<off_Tmr::get_rticks implementation. >= (U->)
// Returns the number of ticks for expiration relative to the previous 
// event.
extern inline natural_t off_Tmr::get_rticks(void) 
{
  return t_rticks;
}

The number of ticks until the first event in the queue happens is cached in the timer server.

<Other private members of off_TmrSrv. >+= (<-U) [<-D->]
natural_t t_remaining;          // # of ticks until next event.

<Initialize other aggregate members of off_TmrSrv. >+= (<-U) [<-D->]
t_remaining(1),

After the clock interrupt has been allocated, clock_handler is called every time the clock ticks. Such routine calls a single timer server on non SMP systems and dispatches the event to the current processor timer server on SMP systems.

<off_clock_handler implementation. >= (U->)
extern "C" {
  void off_clock_handler(void)
  {
      off_Processor::self()->get_tmr().clock_handler();
  }
}

Defines off_clock_handler (links are to index).

<Off timer server implementation dependencies. >+= (U->) [<-D->]
#include <hw/Processor.h>       // for self

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
// Another clock tick in the wall. 
inline void clock_handler(void);

It decrements the number of ticks until the first event in the queue and then calls expired when it becomes zero.

<off_TmrSrv::clock_handler implementation. >= (U->)
// Another clock tick in the wall. 
inline void off_TmrSrv::clock_handler(void)
{
  
  if (--t_remaining)
    expired();
}

expired is used both to handle the event and to reset t_remaining to the number of ticks until further events.

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
// It is called when the period until next event expires.
// The number of ticks until next event is returned. 
volatile void expired(void);

<off_TmrSrv::expired implementation. >= (U->)
// It is called when the period until next event expires.
// The number of ticks until next event is returned. 
volatile void off_TmrSrv::expired(void)
{
  off_LTmr *ev;
  <off_TmrSrv::expired local variables. >

  <Pick up first pending ev and reset t_remaining. >
  <Handle expired event ev. >
}

When the first pending event expires, we get a reference to it (to handle it later) and reset the clock counter with the relative count for the next timer. The queue is also handled from interrupts, thus we clear interrupts and lock the queue for enqueue and dequeue operations.

<Pick up first pending ev and reset t_remaining. >= (<-U)
clrd=off_Processor::has_clri();
off_Processor::clri();
w_lock();
ev = (off_LTmr*)t_events.dequeue();
t_remaining=((off_LTmr*)t_events.get_first())->l_tmr.get_rticks();
w_unlock();
if (!clrd)
  off_Processor::seti();

<off_TmrSrv::expired local variables. >= (<-U)
boolean_t clrd;

To handle a timer we usually raise its virtual interrupt; but for a special timer which will be discussed later.

<Handle expired event ev. >= (<-U) [D->]
if (<It is a special ev to be handled. >){
  <Handle special ev. >
}
else 
  off_Processor::self()->get_irq(ev->l_tmr.get_irqline())->raise();

We still have to show how are timers created. When a timer is created, we must find the place in the list of active timers where it should be placed and adjust both its relative number of ticks and the relative number of ticks of the following timers. Both tasks are done by the timer protected method activate.

<Other protected methods of off_Tmr. >= (<-U) [D->]
// Activates the timer by linking it in the active timer queue. 
void activate(void);

which is called by the constructor when the timer is created.

<Initialize other private members of off_Tmr. >= (<-U)
activate();

Note that when the timer is periodic, it is activated when expired too.

<Handle expired event ev. >+= (<-U) [<-D]
if (ev->l_tmr.is_periodic())
  ev->l_tmr.activate();

The timer activate method simply calls a counterpart in the timer server.

<off_Tmr::activate implementation. >= (U->)
// Activates the timer by linking it in the active timer queue. 
void off_Tmr::activate(void)
{
  ((off_TmrSrv*)get_container())->activate(this);
}

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
// Activates the timer by linking it in the active timer queue. 
void activate(off_Tmr *t);

The timer server method is used to maintain (to link timers in) the active timer queue. To do so, we need a pointer to the LTmr the timer is in so we could reuse the pointers used by the timer allocator; then we walk the queue maintaining in ticks the relative number of ticks (with respect the queue node being visited) for timer expiration.

<off_TmrSrv::activate implementation. >= (U->)
// Activates the timer by linking it in the active timer queue. 
void off_TmrSrv::activate(off_Tmr *t)
{
  boolean_t clrd;
  off_LTmr *lt=(off_LTmr*)(((char*)t)-(int)&off_LTmr::l_tmr);
  natural_t &ticks=t->t_rticks;

  ticks=t->get_ticks();
  clrd=off_Processor::has_clri();
  off_Processor::clri();
  w_lock();

  if (t_events.is_empty()){
    <Place timer t to expire in ticks at head of t_events. >
  }
  else {
    <Find place in t_events for timer t to expire in ticks >
  }
  <Activate HW clock interrupt if necessary. >

  w_unlock();
  if (!clrd)
    off_Processor::seti();

}

If there is no timer we simply put the timer in the head of the queue.

<Place timer t to expire in ticks at head of t_events. >= (<-U)
t->t_rticks=ticks;
t_events.enqueue(lt);

If there are timers, we start scanning the queue from its head using a queue iterator itr. If the iterator was not placed after the last node was visited, we link the node at the end of the queue.

Every time a new node is visited we maintain ticks as a relative count starting at it. When the node is finally placed, ticks contains a relative count and we adjust the relative count of the following node to discount ticks.

<Find place in t_events for timer t to expire in ticks >= (<-U)
DLinkedQueueItr itr,head;
boolean_t placed=FALSE;
head=itr=t_events.get_head(); 
do {
  natural_t &nticks= ((off_LTmr*)itr.get_element())->l_tmr.t_rticks;
  if (nticks >= ticks){
    ticks -= nticks;
  }
  else {
    placed=TRUE;
    nticks -= ticks;
    t_events.link_before(lt,itr);
  }
  ++itr;
} while (!placed && itr != head);

if (!placed){
  DLinkedQueueItr i=t_events.get_tail();
  t_events.link_after(lt,i);
}

Finally, we do not want to maintain the hardware clock interrupt always enabled. It is enabled only when there are timers to be serviced. The timer server enables the hardware clock interrupt when the first timer is activated

<Activate HW clock interrupt if necessary. >= (<-U)
t_clkirq->unmask();

and disables it again when the last active timer is disabled.

<Deactivate HW clock interrupt if necessary. >= (<-U)
if (!t_alloc.get_nalloc())
  t_clkirq->mask();

\subsubsection{Helping processors with their quanta}

Every processor with a run queue will always want to be interrupted to implement quanta. Those interrupts take part in the critical path for the context switch, hence they are handled apart.

The timer server includes a alloc_pclk method intended to start the ``scheduling'' clock.

<Other public methods of off_TmrSrv. >+= (<-U) [<-D->]
// Starts the scheduling clock timer.
void alloc_pclk(natural_t nticks);

It programs a special timer which is handled by the timer server itself.

<off_TmrSrv::alloc_pclk implementation. >= (U->)
// Starts the scheduling clock timer.
void off_TmrSrv::alloc_pclk(natural_t nticks)
{
  if (!t_pclk){
    off_Tmr *t=new off_Tmr(get_protection(),get_domain(),nticks,TRUE);
    t_pclk=(off_LTmr*)(((char*)t)-(int)&off_LTmr::l_tmr);
  }
}

What makes it so special is that when time has come to handle it the timer server checks the timer address to see if it is the same of t_pclk. If it matches, the current processor new_quantum method is called instead of raising a virtual interrupt. Thus,

<It is a special ev to be handled. >= (<-U)
ev == t_pclk

<Initialize other aggregate members of off_TmrSrv. >+= (<-U) [<-D->]
t_pclk(NULL),

<Other private members of off_TmrSrv. >+= (<-U) [<-D->]
off_LTmr *t_pclk;               // Special processor clock timer.

Now, to handle such event we call new_quantum. But before doing that we reactivate the timer.

<Handle special ev. >= (<-U)
ev->l_tmr.activate();
off_Processor::self()->new_quantum();

The new_quantum routine will (perhaps) leave us in the context for a new shuttle before it returns.