kernel/fiasco/src/kern/timeout.cpp

   1 INTERFACE:
   2
   3 #include <hlist>
   4 #include "l4_types.h"
   5 #include "per_cpu_data.h"
   6
   7 /** A timeout basic object. It contains the necessary queues and handles
   8     enqueuing, dequeuing and handling of timeouts. Real timeout classes
   9     should overwrite expired(), which will do the real work, if an
  10     timeout hits.
  11  */
  12 class Timeout : public cxx::H_list_item
  13 {
  14   friend class Jdb_timeout_list;
  15   friend class Jdb_list_timeouts;
  16   friend class Timeout_q;
  17
  18 public:
  19   typedef cxx::H_list<Timeout> To_list;
  20
  21 protected:
  22   /**
  23    * Absolute system time we want to be woken up at.
  24    */
  25   Unsigned64 _wakeup;
  26
  27 private:
  28   /**
  29    * Default copy constructor (is undefined).
  30    */
  31   Timeout(const Timeout&);
  32
  33   /**
  34    * Overwritten timeout handler function.
  35    * @return true if a reschedule is necessary, false otherwise.
  36    */
  37   virtual bool expired();
  38
  39   struct
  40   {
  41     bool     hit  : 1;
  42     unsigned res  : 6; // performance optimization
  43   } _flags;
  44 };
  45
  46
  47 class Timeout_q
  48 {
  49 private:
  50   /**
  51    * Timeout queue count (2^n) and  distance between two queues in 2^n.
  52    */
  53   enum
  54   {
  55     Wakeup_queue_count    = 8,
  56     Wakeup_queue_distance = 12 // i.e. (1<<12)us
  57   };
  58
  59   typedef Timeout::To_list To_list;
  60   typedef To_list::Iterator Iterator;
  61   typedef To_list::Const_iterator Const_iterator;
  62
  63   /**
  64    * The timeout queues.
  65    */
  66   To_list _q[Wakeup_queue_count];
  67
  68   /**
  69    * The current programmed timeout.
  70    */
  71   Unsigned64 _current;
  72   Unsigned64 _old_clock;
  73
  74 public:
  75   static Per_cpu<Timeout_q> timeout_queue;
  76 };
  77
  78 //----------------------------------------------------------------------------------
  79 IMPLEMENTATION:
  80
  81 #include <cassert>
  82 #include "cpu_lock.h"
  83 #include "kip.h"
  84 #include "lock_guard.h"
  85 #include "timer.h"
  86 #include "static_init.h"
  87 #include <climits>
  88 #include "config.h"
  89 #include "kdb_ke.h"
  90
  91
  92 DEFINE_PER_CPU Per_cpu<Timeout_q> Timeout_q::timeout_queue;
  93
  94
  95 PUBLIC inline
  96 Timeout_q::To_list &
  97 Timeout_q::first(int index)
  98 { return _q[index & (Wakeup_queue_count-1)]; }
  99
 100 PUBLIC inline
 101 Timeout_q::To_list const &
 102 Timeout_q::first(int index) const
 103 { return _q[index & (Wakeup_queue_count-1)]; }
 104
 105 PUBLIC inline
 106 unsigned
 107 Timeout_q::queues() const { return Wakeup_queue_count; }
 108
 109
 110 /**
 111  * Enqueue a new timeout.
 112  */
 113 PUBLIC inline NEEDS[Timeout_q::first, "timer.h", "config.h"]
 114 void
 115 Timeout_q::enqueue(Timeout *to)
 116 {
 117   int queue = (to->_wakeup >> Wakeup_queue_distance) & (Wakeup_queue_count-1);
 118
 119   To_list &q = first(queue);
 120   Iterator tmp = q.begin();
 121
 122   while (tmp != q.end() && tmp->_wakeup < to->_wakeup)
 123     ++tmp;
 124
 125   q.insert_before(to, tmp);
 126
 127   if (Config::Scheduler_one_shot && (to->_wakeup <= _current))
 128     {
 129       _current = to->_wakeup;
 130       Timer::update_timer(_current);
 131     }
 132 }
 133
 134
 135 /**
 136  * Timeout constructor.
 137  */
 138 PUBLIC inline
 139 Timeout::Timeout()
 140 {
 141   _flags.hit = 0;
 142   _flags.res = 0;
 143 }
 144
 145
 146 /**
 147  * Initializes an timeout object.
 148  */
 149 PUBLIC inline  NEEDS[<climits>]
 150 void
 151 Timeout::init()
 152 {
 153   _wakeup = ULONG_LONG_MAX;
 154 }
 155
 156 /* Yeah, i know, an derived and specialized timeout class for
 157    the root node would be nicer. I already had done this, but
 158    it was significantly slower than this solution */
 159 IMPLEMENT virtual bool
 160 Timeout::expired()
 161 {
 162   kdb_ke("Wakeup List Terminator reached");
 163   return false;
 164 }
 165
 166 /**
 167  * Check if timeout is set.
 168  */
 169 PUBLIC inline
 170 bool
 171 Timeout::is_set()
 172 {
 173   return To_list::in_list(this);
 174 }
 175
 176 /**
 177  * Check if timeout has hit.
 178  */
 179 PUBLIC inline
 180 bool
 181 Timeout::has_hit()
 182 {
 183   return _flags.hit;
 184 }
 185
 186
 187 PUBLIC inline NEEDS [<cassert>, "cpu_lock.h", "lock_guard.h",
 188                      Timeout_q::enqueue, Timeout::is_set]
 189 void
 190 Timeout::set(Unsigned64 clock, unsigned cpu)
 191 {
 192   // XXX uses global kernel lock
 193   auto guard = lock_guard(cpu_lock);
 194
 195   assert (!is_set());
 196
 197   _wakeup = clock;
 198   Timeout_q::timeout_queue.cpu(cpu).enqueue(this);
 199 }
 200
 201 /**
 202  * Return remaining time of timeout.
 203  */
 204 PUBLIC inline
 205 Signed64
 206 Timeout::get_timeout(Unsigned64 clock)
 207 {
 208   return _wakeup - clock;
 209 }
 210
 211 PUBLIC inline NEEDS [<cassert>, "cpu_lock.h", "lock_guard.h",
 212                      Timeout::is_set, Timeout_q::enqueue, Timeout::has_hit]
 213 void
 214 Timeout::set_again(unsigned cpu)
 215 {
 216   // XXX uses global kernel lock
 217   auto guard = lock_guard(cpu_lock);
 218
 219   assert(! is_set());
 220   if (has_hit())
 221     return;
 222
 223   Timeout_q::timeout_queue.cpu(cpu).enqueue(this);
 224 }
 225
 226 PUBLIC inline NEEDS ["cpu_lock.h", "lock_guard.h", "timer.h",
 227                      "kdb_ke.h", Timeout::is_set]
 228 void
 229 Timeout::reset()
 230 {
 231   assert_kdb (cpu_lock.test());
 232   To_list::remove(this);
 233
 234   // Normaly we should reprogramm the timer in one shot mode
 235   // But we let the timer interrupt handler to do this "lazily", to save cycles
 236 }
 237
 238 /**
 239  * Dequeue an expired timeout.
 240  * @return true if a reschedule is necessary, false otherwise.
 241  */
 242 PRIVATE inline
 243 bool
 244 Timeout::expire()
 245 {
 246   _flags.hit = 1;
 247   return expired();
 248 }
 249 /**
 250  * Dequeue an expired timeout.
 251  * @return true if a reschedule is necessary, false otherwise.
 252  */
 253 PUBLIC inline
 254 bool
 255 Timeout::dequeue(bool is_expired = true)
 256 {
 257   To_list::remove(this);
 258
 259   if (is_expired)
 260     return expire();
 261   else
 262     return false;
 263 }
 264
 265 /**
 266  * Handles the timeouts, i.e. call expired() for the expired timeouts
 267  * and programs the "oneshot timer" to the next timeout.
 268  * @return true if a reschedule is necessary, false otherwise.
 269  */
 270 PUBLIC inline NEEDS [<cassert>, <climits>, "kip.h", "timer.h", "config.h",
 271                      Timeout::expire]
 272 bool
 273 Timeout_q::do_timeouts()
 274 {
 275   bool reschedule = false;
 276
 277   // We test if the time between 2 activiations of this function is greater
 278   // than the distance between two timeout queues.
 279   // To avoid to lose timeouts, we calculating the missed queues and
 280   // scan them too.
 281   // This can only happen, if we dont enter the timer interrupt for a long
 282   // time, usual with one shot timer.
 283   // Because we initalize old_dequeue_time with zero,
 284   // we can get an "miss" on the first timerinterrupt.
 285   // But this is booting the system, which is uncritical.
 286
 287   // Calculate which timeout queues needs to be checked.
 288   int start = (_old_clock >> Wakeup_queue_distance);
 289   int diff  = (Kip::k()->clock >> Wakeup_queue_distance) - start;
 290   int end   = (start + diff + 1) & (Wakeup_queue_count - 1);
 291
 292   // wrap around
 293   start = start & (Wakeup_queue_count - 1);
 294
 295   // test if an complete miss
 296   if (diff >= Wakeup_queue_count)
 297     start = end = 0; // scan all queues
 298
 299   // update old_clock for the next run
 300   _old_clock = Kip::k()->clock;
 301
 302   // ensure we always terminate
 303   assert((end >= 0) && (end < Wakeup_queue_count));
 304
 305   for (;;)
 306     {
 307       To_list &q = first(start);
 308       Iterator timeout = q.begin();
 309
 310       // now scan this queue for timeouts below current clock
 311       while (timeout != q.end() && timeout->_wakeup <= (Kip::k()->clock))
 312         {
 313           reschedule |= timeout->expire();
 314           timeout = q.erase(timeout);
 315         }
 316
 317       // next queue
 318       start = (start + 1) & (Wakeup_queue_count - 1);
 319
 320       if (start == end)
 321         break;
 322     }
 323
 324   if (Config::Scheduler_one_shot)
 325     {
 326       // scan all queues for the next minimum
 327       //_current = (Unsigned64) ULONG_LONG_MAX;
 328       _current = Kip::k()->clock + 10000; //ms
 329       bool update_timer = true;
 330
 331       for (int i = 0; i < Wakeup_queue_count; i++)
 332         {
 333           // make sure that something enqueued other than the dummy element
 334           if (first(i).empty())
 335             continue;
 336
 337           update_timer = true;
 338
 339           if (first(i).front()->_wakeup < _current)
 340             _current =  first(i).front()->_wakeup;
 341         }
 342
 343       if (update_timer)
 344         Timer::update_timer(_current);
 345
 346     }
 347   return reschedule;
 348 }
 349
 350 PUBLIC inline
 351 Timeout_q::Timeout_q()
 352 : _current(ULONG_LONG_MAX), _old_clock(0)
 353 {}
 354
 355 PUBLIC inline
 356 bool
 357 Timeout_q::have_timeouts(Timeout const *ignore) const
 358 {
 359   for (unsigned i = 0; i < Wakeup_queue_count; ++i)
 360     {
 361       To_list const &t = first(i);
 362       if (!t.empty())
 363         {
 364           To_list::Const_iterator f = t.begin();
 365           if (*f == ignore && (++f) == t.end())
 366             continue;
 367
 368           return true;
 369         }
 370     }
 371
 372   return false;
 373 }
 374