kernel/fiasco/src/kern/switch_lock.cpp

   1 INTERFACE:
   2
   3 #include "member_offs.h"
   4 #include <types.h>
   5
   6 #ifdef NO_INSTRUMENT
   7 #undef NO_INSTRUMENT
   8 #endif
   9 #define NO_INSTRUMENT __attribute__((no_instrument_function))
  10
  11 class Context;
  12
  13
  14 /** A lock that implements priority inheritance.
  15  *
  16  * The lock uses a validity checker (VALID) for doing an existence check
  17  * before the lock is actually acquired. With this mechanism the lock itself
  18  * may disappear while it is locked (see clear_no_switch_dirty() and
  19  * switch_dirty()), even if it is under contention. When the lock no longer
  20  * exists VALID::valid(void const *lock) must return false, true if it
  21  * exists (see Switch_lock_valid). This mechanism is used in Thread_lock
  22  * when thread control blocks are deallocated.
  23  *
  24  * The operations lock(), lock_dirty(), try_lock(), test(), test_and_set(),
  25  * and test_and_set_dirty() may return #Invalid if the lock does
  26  * no longer exist.
  27  *
  28  * The operations initialize(), lock_owner(), clear(), clear_dirty(), and
  29  * clear_no_switch_dirty() must not being called on and invalid lock,
  30  * thus the lock itself must be held for using these operations.
  31  * (Except initialize(), which is only useful for locks that are always
  32  * valid.)
  33  *
  34  * @param VALID must be set to a validity checker for the lock.
  35  *
  36  * The validity checker is used while aquiring the lock to test
  37  * if the lock itself existis. We assume that a lock may disappear
  38  * while we are blocked on it.
  39  */
  40 class Switch_lock
  41 {
  42   MEMBER_OFFSET();
  43
  44 private:
  45   // Warning: This lock's member variables must not need a
  46   // constructor.  Switch_lock instances must assume
  47   // zero-initialization or be initialized using the initialize()
  48   // member function.
  49   // Reason: to avoid overwriting the lock in the thread-ctor
  50   Address _lock_owner;
  51
  52 public:
  53   /**
  54    * @brief The result type of lock operations.
  55    */
  56   enum Status
  57   {
  58     Not_locked, ///< The lock was formerly not aquired and -- we got it
  59     Locked,     ///< The lock was already aquired by ourselves
  60     Invalid     ///< The lock does not exist (is invalid)
  61   };
  62
  63   /**
  64    * Stores the context of the lock for a later switch.
  65    * (see clear_no_switch_dirty(), switch_dirty())
  66    */
  67   struct Lock_context
  68   {
  69     Context *owner;
  70   };
  71 };
  72
  73 #undef NO_INSTRUMENT
  74 #define NO_INSTRUMENT
  75
  76
  77 IMPLEMENTATION:
  78
  79 #include <cassert>
  80
  81 #include "cpu.h"
  82 #include "atomic.h"
  83 #include "cpu_lock.h"
  84 #include "lock_guard.h"
  85 #include "context.h"
  86 #include "globals.h"
  87 #include "processor.h"
  88
  89
  90 //
  91 // Switch_lock inlines
  92 //
  93
  94 /**
  95  * Test if the lock is valid (uses the validity checker).
  96  * @return true if the lock really exists, false if not.
  97  */
  98 PUBLIC
  99 inline
 100 bool NO_INSTRUMENT
 101 Switch_lock::valid() const
 102 { return (_lock_owner & 1) == 0; }
 103
 104 /** Initialize Switch_lock.  Call this function if you cannot
 105     guarantee that your Switch_lock instance is allocated from
 106     zero-initialized memory. */
 107 PUBLIC
 108 inline
 109 void NO_INSTRUMENT
 110 Switch_lock::initialize()
 111 {
 112   _lock_owner = 0;
 113 }
 114
 115 /** Lock owner.
 116  *  @pre The lock must be valid (see valid()).
 117  *  @return current owner of the lock.  0 if there is no owner.
 118  */
 119 PUBLIC
 120 inline
 121 Context * NO_INSTRUMENT
 122 Switch_lock::lock_owner() const
 123 {
 124   Lock_guard<Cpu_lock> guard(&cpu_lock);
 125   return (Context*)(_lock_owner & ~1UL);
 126 }
 127
 128 /** Is lock set?.
 129     @return #Locked if lock is set, #Not_locked if not locked, and #Invalid if
 130             the lock does not exist (see valid()).
 131  */
 132 PUBLIC
 133 inline
 134 Switch_lock::Status NO_INSTRUMENT
 135 Switch_lock::test() const
 136 {
 137   Lock_guard<Cpu_lock> guard(&cpu_lock);
 138   if (EXPECT_FALSE(!valid()))
 139     return Invalid;
 140   return (_lock_owner  & ~1UL) ? Locked : Not_locked;
 141 }
 142
 143 /** Try to acquire the lock.
 144     @return #Locked if successful: current context is now the owner of the lock.
 145             #Not_locked if lock has previously been set.  Returns Not_locked
 146             even if the current context is already the lock owner.
 147             The result is #Invalid if the lock does not exist (see valid()).
 148  */
 149
 150 inline NEEDS["atomic.h"]
 151 Switch_lock::Status NO_INSTRUMENT
 152 Switch_lock::try_lock()
 153 {
 154   Lock_guard<Cpu_lock> guard(&cpu_lock);
 155
 156   if (EXPECT_FALSE(!valid()))
 157     return Invalid;
 158
 159   bool ret = cas(&_lock_owner, (Address)0, Address(current()));
 160
 161   if (ret)
 162     current()->inc_lock_cnt();  // Do not lose this lock if current is deleted
 163
 164   return ret ? Locked : Not_locked;
 165 }
 166
 167 /** Acquire the lock with priority inheritance.
 168  *  If the lock is occupied, enqueue in list of helpers and lend CPU
 169  *  to current lock owner until we are the lock owner.
 170  *  @return #Locked if the lock was already locked by the current context.
 171  *          #Not_locked if the current context got the lock (the usual case).
 172  *          #Invalid if the lock does not exist (see valid()).
 173  */
 174 PUBLIC
 175 Switch_lock::Status NO_INSTRUMENT
 176 Switch_lock::lock()
 177 {
 178   Lock_guard <Cpu_lock> guard(&cpu_lock);
 179   return lock_dirty();
 180 }
 181
 182 /** Acquire the lock with priority inheritance.
 183  *  If the lock is occupied, enqueue in list of helpers and lend CPU
 184  *  to current lock owner until we are the lock owner (see lock()).
 185  *  @pre caller holds cpu lock
 186  *  @return #Locked if the lock was already locked by the current context.
 187  *          #Not_locked if the current context got the lock (the usual case).
 188  *          #Invalid if the lock does not exist (see valid()).
 189  */
 190 PUBLIC
 191 inline NEEDS["cpu.h","context.h", "processor.h", Switch_lock::set_lock_owner]
 192 Switch_lock::Status NO_INSTRUMENT
 193 Switch_lock::lock_dirty()
 194 {
 195   assert(cpu_lock.test());
 196
 197   if (!valid())
 198     return Invalid;
 199
 200   // have we already the lock?
 201   if ((_lock_owner & ~1UL) == Address(current()))
 202     return Locked;
 203
 204   while (test())
 205     {
 206       assert(cpu_lock.test());
 207
 208       // Help lock owner until lock becomes free
 209       //      while (test())
 210       bool tmp = current()->switch_exec_locked(lock_owner(), Context::Helping);
 211       (void)tmp;
 212
 213       Proc::irq_chance();
 214
 215       if (!valid())
 216         return Invalid;
 217     }
 218
 219   set_lock_owner(current());
 220
 221   current()->inc_lock_cnt();   // Do not lose this lock if current is deleted
 222   return Not_locked;
 223 }
 224
 225
 226 /** Acquire the lock with priority inheritance.
 227  *  @return #Locked if we owned the lock already.  #Not_locked otherwise.
 228  *          #Invalid is returned if the lock does not exist (see valid()).
 229  */
 230 PUBLIC
 231 inline NEEDS["globals.h"]
 232 Switch_lock::Status NO_INSTRUMENT
 233 Switch_lock::test_and_set()
 234 {
 235   return lock();
 236 }
 237
 238 /** Acquire the lock with priority inheritance (see test_and_set()).
 239  *  @return #Locked if we owned the lock already.  #Not_locked otherwise.
 240  *          #Invalid is returned if the lock does not exist (see valid()).
 241  *          @pre caller holds cpu lock
 242  */
 243 PUBLIC
 244 inline NEEDS["globals.h"]
 245 Switch_lock::Status NO_INSTRUMENT
 246 Switch_lock::test_and_set_dirty()
 247 {
 248   return lock_dirty();
 249 }
 250
 251 PRIVATE inline
 252 void NO_INSTRUMENT
 253 Switch_lock::set_lock_owner(Context *o)
 254 {
 255   _lock_owner = Address(o) | (_lock_owner & 1);
 256 }
 257
 258 /**
 259  * Clear the lock, however do not switch to a potential helper yet.
 260  * This function is used when the lock must be cleared and the object
 261  * containing the lock will be deallocated atomically. We have to do the
 262  * switch later using switch_dirty(Lock_context).
 263  * @return the context for a later switch_dirty()
 264  * @pre The lock must be valid (see valid()).
 265  * @pre caller hold cpu lock
 266  * @post switch_dirty() must be called in the same atomical section
 267  */
 268 PROTECTED
 269 inline NEEDS[Switch_lock::set_lock_owner]
 270 Switch_lock::Lock_context NO_INSTRUMENT
 271 Switch_lock::clear_no_switch_dirty()
 272 {
 273   Lock_context c;
 274   c.owner = lock_owner();
 275   set_lock_owner(0);
 276   c.owner->dec_lock_cnt();
 277   return c;
 278 }
 279
 280 /**
 281  * Do the switch part of clear() after a clear_no_switch_dirty().
 282  * This function does not touch the lock itself (may be called on
 283  * an invalid lock).
 284  * @param c the context returned by a former clear_no_switch_dirty().
 285  * @pre must be called atomically with clear_no_switch_dirty(),
 286  *      under the same cpu lock
 287  */
 288 PROTECTED
 289 static inline
 290 void NO_INSTRUMENT
 291 Switch_lock::switch_dirty(Lock_context const &c)
 292 {
 293   assert_kdb (current() == c.owner);
 294
 295   Context *h = c.owner->helper();
 296   /*
 297    * If someone helped us by lending its time slice to us.
 298    * Just switch back to the helper without changing its helping state.
 299    */
 300   bool need_sched = false;
 301   if (h != c.owner)
 302     need_sched = c.owner->switch_exec_locked(h, Context::Ignore_Helping);
 303
 304   /*
 305    * Someone apparently tries to delete us. Therefore we aren't
 306    * allowed to continue to run and therefore let the scheduler
 307    * pick the next thread to execute.
 308    */
 309   if (need_sched || (c.owner->lock_cnt() == 0 && c.owner->donatee()))
 310     c.owner->schedule();
 311 }
 312
 313 /** Free the lock.
 314     Return the CPU to helper if there is one, since it had to have a
 315     higher priority to be able to help (priority may be its own, it
 316     may run on a donated timeslice or round robin scheduling may have
 317     selected a thread on the same priority level as me)
 318
 319     @pre The lock must be valid (see valid()).
 320  */
 321 PUBLIC
 322 void NO_INSTRUMENT
 323 Switch_lock::clear()
 324 {
 325   Lock_guard<Cpu_lock> guard(&cpu_lock);
 326
 327   switch_dirty(clear_no_switch_dirty());
 328 }
 329
 330 PUBLIC
 331 void NO_INSTRUMENT
 332 Switch_lock::set(Status s)
 333 {
 334   if (s == Not_locked)
 335     clear();
 336 }
 337
 338 /** Free the lock.
 339     Return the CPU to helper if there is one, since it had to have a
 340     higher priority to be able to help (priority may be its own, it
 341     may run on a donated timeslice or round robin scheduling may have
 342     selected a thread on the same priority level as me).
 343     If _lock_owner is 0, then this is a no op
 344
 345     @pre The lock must be valid (see valid())
 346     @pre caller holds cpu lock
 347  */
 348 PUBLIC
 349 inline
 350 void NO_INSTRUMENT
 351 Switch_lock::clear_dirty()
 352 {
 353   assert(cpu_lock.test());
 354
 355   switch_dirty(clear_no_switch_dirty());
 356 }
 357
 358 PUBLIC inline
 359 void NO_INSTRUMENT
 360 Switch_lock::invalidate()
 361 {
 362   Lock_guard<Cpu_lock> guard(&cpu_lock);
 363   _lock_owner |= 1;
 364 }
 365
 366 PUBLIC
 367 void NO_INSTRUMENT
 368 Switch_lock::wait_free()
 369 {
 370   Lock_guard<Cpu_lock> guard(&cpu_lock);
 371
 372   assert (!valid());
 373
 374   // have we already the lock?
 375   if ((_lock_owner & ~1UL) == (Address)current())
 376     {
 377       set_lock_owner(0);
 378       current()->dec_lock_cnt();
 379       return;
 380     }
 381
 382   while (Address(_lock_owner) & ~1UL)
 383     {
 384       assert(cpu_lock.test());
 385
 386       // Help lock owner until lock becomes free
 387       //      while (test())
 388       check (!current()->switch_exec_locked((Context*)(Address(_lock_owner & ~1UL)), Context::Helping));
 389
 390       Proc::irq_chance();
 391     }
 392 }