kernel/fiasco/src/kern/ready_queue_wfq.cpp

   1 INTERFACE[sched_wfq || sched_fp_wfq]:
   2
   3 #include "member_offs.h"
   4 #include "types.h"
   5 #include "globals.h"
   6
   7 struct L4_sched_param_wfq : public L4_sched_param
   8 {
   9   enum : Smword { Class = -2 };
  10   Mword quantum;
  11   Mword weight;
  12 };
  13
  14 template< typename E >
  15 class Ready_queue_wfq
  16 {
  17   friend class Jdb_thread_list;
  18   template<typename T>
  19   friend class Jdb_thread_list_policy;
  20
  21 public:
  22   E *current_sched() const { return _current_sched; }
  23   void activate(E *s) { _current_sched = s; }
  24   E *idle;
  25
  26   void set_idle(E *sc)
  27   {
  28     idle = sc;
  29     _e(sc)->_ready_link = &idle;
  30     _e(sc)->_idle = 1;
  31   }
  32
  33   void enqueue(E *, bool is_current);
  34   void dequeue(E *);
  35   E *next_to_run() const;
  36
  37 private:
  38   void swap(unsigned a, unsigned b);
  39   void heap_up(unsigned a);
  40   void heap_down(unsigned a);
  41
  42   E *_current_sched;
  43   unsigned _cnt;
  44   E *_heap[1024];
  45
  46   static typename E::Wfq_sc *_e(E *e) { return E::wfq_elem(e); }
  47 };
  48
  49 template< typename IMPL >
  50 class Sched_context_wfq
  51 {
  52 public:
  53   bool operator <= (Sched_context_wfq const &o) const
  54   { return _impl()._dl <= o._impl()._dl; }
  55
  56   bool operator < (Sched_context_wfq const &o) const
  57   { return _impl()._dl < o._impl()._dl; }
  58
  59 private:
  60   IMPL const &_impl() const { return static_cast<IMPL const &>(*this); }
  61   IMPL &_impl() { return static_cast<IMPL &>(*this); }
  62 };
  63
  64
  65 // --------------------------------------------------------------------------
  66 IMPLEMENTATION [sched_wfq || sched_fp_wfq]:
  67
  68 #include <cassert>
  69 #include "config.h"
  70 #include "cpu_lock.h"
  71 #include "kdb_ke.h"
  72 #include "std_macros.h"
  73
  74
  75 IMPLEMENT inline
  76 template<typename E>
  77 E *
  78 Ready_queue_wfq<E>::next_to_run() const
  79 {
  80   if (_cnt)
  81     return _heap[0];
  82
  83   if (_current_sched)
  84     _e(idle)->_dl = _e(_current_sched)->_dl;
  85
  86   return idle;
  87 }
  88
  89 IMPLEMENT inline
  90 template<typename E>
  91 void
  92 Ready_queue_wfq<E>::swap(unsigned a, unsigned b)
  93 {
  94   _e(_heap[a])->_ready_link = &_heap[b];
  95   _e(_heap[b])->_ready_link = &_heap[a];
  96   E *s = _heap[a];
  97   _heap[a] = _heap[b];
  98   _heap[b] = s;
  99 }
 100
 101 IMPLEMENT inline
 102 template<typename E>
 103 void
 104 Ready_queue_wfq<E>::heap_up(unsigned a)
 105 {
 106   for (;a > 0;)
 107     {
 108       unsigned p = (a-1)/2;
 109       if (*_e(_heap[p]) < *_e(_heap[a]))
 110         return;
 111       swap(p, a);
 112       a = p;
 113     }
 114 }
 115
 116 IMPLEMENT inline
 117 template<typename E>
 118 void
 119 Ready_queue_wfq<E>::heap_down(unsigned a)
 120 {
 121   for (;;)
 122     {
 123       unsigned c1 = 2*a + 1;
 124       unsigned c2 = 2*a + 2;
 125
 126       if (_cnt <= c1)
 127         return;
 128
 129       if (_cnt > c2 && *_e(_heap[c2]) <= *_e(_heap[c1]))
 130         c1 = c2;
 131
 132       if (*_e(_heap[a]) <= *_e(_heap[c1]))
 133         return;
 134
 135       swap(c1, a);
 136
 137       a = c1;
 138     }
 139 }
 140
 141 /**
 142  * Enqueue context in ready-list.
 143  */
 144 IMPLEMENT
 145 template<typename E>
 146 void
 147 Ready_queue_wfq<E>::enqueue(E *i, bool /*is_current_sched**/)
 148 {
 149   assert_kdb(cpu_lock.test());
 150
 151   // Don't enqueue threads which are already enqueued
 152   if (EXPECT_FALSE (i->in_ready_list()))
 153     return;
 154
 155   unsigned n = _cnt++;
 156
 157   E *&h = _heap[n];
 158   h = i;
 159   _e(i)->_ready_link = &h;
 160
 161   heap_up(n);
 162 }
 163
 164 /**
 165  * Remove context from ready-list.
 166  */
 167 IMPLEMENT inline NEEDS ["cpu_lock.h", "kdb_ke.h", "std_macros.h"]
 168 template<typename E>
 169 void
 170 Ready_queue_wfq<E>::dequeue(E *i)
 171 {
 172   assert_kdb (cpu_lock.test());
 173
 174   // Don't dequeue threads which aren't enqueued
 175   if (EXPECT_FALSE (!i->in_ready_list() || i == idle))
 176     return;
 177
 178   unsigned x = _e(i)->_ready_link - _heap;
 179
 180   if (x == --_cnt)
 181     {
 182       _e(i)->_ready_link = 0;
 183       return;
 184     }
 185
 186   swap(x, _cnt);
 187   heap_down(x);
 188   _e(i)->_ready_link = 0;
 189 }
 190
 191 /**
 192  * Enqueue context in ready-list.
 193  */
 194 PUBLIC
 195 template<typename E>
 196 void
 197 Ready_queue_wfq<E>::requeue(E *i)
 198 {
 199   if (!i->in_ready_list())
 200     enqueue(i, false);
 201
 202   heap_down(_e(i)->_ready_link - _heap);
 203 }
 204
 205
 206 PUBLIC template< typename E > inline
 207 void
 208 Ready_queue_wfq<E>::deblock_refill(E *sc)
 209 {
 210   Unsigned64 da = 0;
 211   if (EXPECT_TRUE(_current_sched != 0))
 212     da = _e(_current_sched)->_dl;
 213
 214   if (_e(sc)->_dl >= da)
 215     return;
 216
 217   _e(sc)->_left += (da - _e(sc)->_dl) * _e(sc)->_w;
 218   if (_e(sc)->_left > _e(sc)->_q)
 219     _e(sc)->_left = _e(sc)->_q;
 220   _e(sc)->_dl = da;
 221 }
 222