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 "atomic.h"
  82 #include "cpu_lock.h"
  83 #include "lock_guard.h"
  84 #include "context.h"
  85 #include "globals.h"
  86 #include "processor.h"
  87
  88
  89 //
  90 // Switch_lock inlines
  91 //
  92
  93 /**
  94  * Test if the lock is valid (uses the validity checker).
  95  * @return true if the lock really exists, false if not.
  96  */
  97 PUBLIC
  98 inline
  99 bool NO_INSTRUMENT
 100 Switch_lock::valid() const
 101 { return (_lock_owner & 1) == 0; }
 102
 103 /** Initialize Switch_lock.  Call this function if you cannot
 104     guarantee that your Switch_lock instance is allocated from
 105     zero-initialized memory. */
 106 PUBLIC
 107 inline
 108 void NO_INSTRUMENT
 109 Switch_lock::initialize()
 110 {
 111   _lock_owner = 0;
 112 }
 113
 114 /** Lock owner.
 115  *  @pre The lock must be valid (see valid()).
 116  *  @return current owner of the lock.  0 if there is no owner.
 117  */
 118 PUBLIC
 119 inline
 120 Context * NO_INSTRUMENT
 121 Switch_lock::lock_owner() const
 122 {
 123   auto guard = lock_guard(cpu_lock);
 124   return (Context*)(_lock_owner & ~1UL);
 125 }
 126
 127 /** Is lock set?.
 128     @return #Locked if lock is set, #Not_locked if not locked, and #Invalid if
 129             the lock does not exist (see valid()).
 130  */
 131 PUBLIC
 132 inline
 133 Switch_lock::Status NO_INSTRUMENT
 134 Switch_lock::test() const
 135 {
 136   auto guard = lock_guard(cpu_lock);
 137   Address o = access_once(&_lock_owner);
 138   if (EXPECT_FALSE(o & 1))
 139     return Invalid;
 140   return o ? 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   auto guard = lock_guard(cpu_lock);
 155
 156   if (EXPECT_FALSE(!valid()))
 157     return Invalid;
 158
 159   Context *c = current();
 160   bool ret = set_lock_owner(c);
 161
 162   if (ret)
 163     c->inc_lock_cnt();  // Do not lose this lock if current is deleted
 164
 165   return ret ? Locked : Not_locked;
 166 }
 167
 168 /** Acquire the lock with priority inheritance.
 169  *  If the lock is occupied, enqueue in list of helpers and lend CPU
 170  *  to current lock owner until we are the lock owner.
 171  *  @return #Locked if the lock was already locked by the current context.
 172  *          #Not_locked if the current context got the lock (the usual case).
 173  *          #Invalid if the lock does not exist (see valid()).
 174  */
 175 PUBLIC
 176 Switch_lock::Status NO_INSTRUMENT
 177 Switch_lock::lock()
 178 {
 179   auto guard = lock_guard(cpu_lock);
 180   return lock_dirty();
 181 }
 182
 183 PRIVATE
 184 void NO_INSTRUMENT
 185 Switch_lock::help(Context *curr, Context *owner, Address owner_id)
 186 {
 187   auto s = curr->switch_exec_helping(owner, Context::Helping, &_lock_owner,
 188                                      owner_id);
 189   if (s == Context::Switch::Failed)
 190     {
 191       if (curr->home_cpu() != current_cpu())
 192         curr->schedule();
 193       else
 194         Proc::preemption_point();
 195     }
 196 }
 197
 198 /** Acquire the lock with priority inheritance.
 199  *  If the lock is occupied, enqueue in list of helpers and lend CPU
 200  *  to current lock owner until we are the lock owner (see lock()).
 201  *  @pre caller holds cpu lock
 202  *  @return #Locked if the lock was already locked by the current context.
 203  *          #Not_locked if the current context got the lock (the usual case).
 204  *          #Invalid if the lock does not exist (see valid()).
 205  */
 206 PUBLIC
 207 inline NEEDS["context.h", "processor.h", Switch_lock::set_lock_owner]
 208 Switch_lock::Status NO_INSTRUMENT
 209 Switch_lock::lock_dirty()
 210 {
 211   assert(cpu_lock.test());
 212
 213   Mword o = access_once(&_lock_owner);
 214   if (EXPECT_FALSE(o & 1))
 215     return Invalid;
 216
 217   Context *c = current();
 218   if (o == Address(c))
 219     return Locked;
 220
 221   do
 222     {
 223       for (;;)
 224         {
 225           Mword o = access_once(&_lock_owner);
 226           if (o & 1)
 227             return Invalid;
 228
 229           if (!o)
 230             break;
 231
 232           help(c, (Context *)o, o);
 233         }
 234     }
 235   while (!set_lock_owner(c));
 236   Mem::mp_wmb();
 237   c->inc_lock_cnt();   // Do not lose this lock if current is deleted
 238   return Not_locked;
 239 }
 240
 241
 242 /** Acquire the lock with priority inheritance.
 243  *  @return #Locked if we owned the lock already.  #Not_locked otherwise.
 244  *          #Invalid is returned if the lock does not exist (see valid()).
 245  */
 246 PUBLIC
 247 inline NEEDS["globals.h"]
 248 Switch_lock::Status NO_INSTRUMENT
 249 Switch_lock::test_and_set()
 250 {
 251   return lock();
 252 }
 253
 254 /** Acquire the lock with priority inheritance (see test_and_set()).
 255  *  @return #Locked if we owned the lock already.  #Not_locked otherwise.
 256  *          #Invalid is returned if the lock does not exist (see valid()).
 257  *          @pre caller holds cpu lock
 258  */
 259 PUBLIC
 260 inline NEEDS["globals.h"]
 261 Switch_lock::Status NO_INSTRUMENT
 262 Switch_lock::test_and_set_dirty()
 263 {
 264   return lock_dirty();
 265 }
 266
 267 IMPLEMENTATION [!mp]:
 268
 269 PRIVATE inline
 270 void NO_INSTRUMENT
 271 Switch_lock::clear_lock_owner()
 272 {
 273   _lock_owner &= 1;
 274 }
 275
 276 PRIVATE inline
 277 bool NO_INSTRUMENT
 278 Switch_lock::set_lock_owner(Context *o)
 279 {
 280   _lock_owner = Address(o) | (_lock_owner & 1);
 281   return true;
 282 }
 283
 284
 285 IMPLEMENTATION [mp]:
 286
 287 PRIVATE inline
 288 void NO_INSTRUMENT
 289 Switch_lock::clear_lock_owner()
 290 {
 291   atomic_mp_and(&_lock_owner, 1);
 292 }
 293
 294 PRIVATE inline
 295 bool NO_INSTRUMENT
 296 Switch_lock::set_lock_owner(Context *o)
 297 {
 298   bool have_no_locks = access_once(&o->_lock_cnt) < 1;
 299
 300   if (have_no_locks)
 301     {
 302       assert (current_cpu() == o->home_cpu());
 303       for (;;)
 304         {
 305           if (EXPECT_FALSE(access_once(&o->_running_under_lock)))
 306             continue;
 307           if (EXPECT_TRUE(mp_cas(&o->_running_under_lock, Mword(false), Mword(true))))
 308             break;
 309         }
 310     }
 311   else
 312     assert (o->_running_under_lock);
 313
 314   Mem::mp_wmb();
 315
 316   if (EXPECT_FALSE(!mp_cas(&_lock_owner, Mword(0), Address(o))))
 317     {
 318       if (have_no_locks)
 319         {
 320           Mem::mp_wmb();
 321           write_now(&o->_running_under_lock, Mword(false));
 322         }
 323       return false;
 324     }
 325
 326   return true;
 327 }
 328
 329
 330 IMPLEMENTATION:
 331
 332 /**
 333  * Clear the lock, however do not switch to a potential helper yet.
 334  * This function is used when the lock must be cleared and the object
 335  * containing the lock will be deallocated atomically. We have to do the
 336  * switch later using switch_dirty(Lock_context).
 337  * @return the context for a later switch_dirty()
 338  * @pre The lock must be valid (see valid()).
 339  * @pre caller hold cpu lock
 340  * @post switch_dirty() must be called in the same atomical section
 341  */
 342 PROTECTED
 343 inline NEEDS[Switch_lock::clear_lock_owner]
 344 Switch_lock::Lock_context NO_INSTRUMENT
 345 Switch_lock::clear_no_switch_dirty()
 346 {
 347   Mem::mp_wmb();
 348   Lock_context c;
 349   c.owner = lock_owner();
 350   clear_lock_owner();
 351   c.owner->dec_lock_cnt();
 352   return c;
 353 }
 354
 355 /**
 356  * Do the switch part of clear() after a clear_no_switch_dirty().
 357  * This function does not touch the lock itself (may be called on
 358  * an invalid lock).
 359  * @param c the context returned by a former clear_no_switch_dirty().
 360  * @pre must be called atomically with clear_no_switch_dirty(),
 361  *      under the same cpu lock
 362  */
 363 PROTECTED
 364 static inline
 365 void NO_INSTRUMENT
 366 Switch_lock::switch_dirty(Lock_context const &c)
 367 {
 368   assert (current() == c.owner);
 369
 370   Context *h = c.owner->helper();
 371   /*
 372    * If someone helped us by lending its time slice to us.
 373    * Just switch back to the helper without changing its helping state.
 374    */
 375   if (h != c.owner)
 376     if (   EXPECT_FALSE(h->home_cpu() != current_cpu())
 377         || EXPECT_FALSE((long)c.owner->switch_exec_locked(h, Context::Ignore_Helping)))
 378       c.owner->schedule();
 379   /*
 380    * Someone apparently tries to delete us. Therefore we aren't
 381    * allowed to continue to run and therefore let the scheduler
 382    * pick the next thread to execute.
 383    */
 384   if (   c.owner->lock_cnt() == 0
 385       && (c.owner->home_cpu() != current_cpu() || c.owner->donatee()))
 386     c.owner->schedule();
 387 }
 388
 389 /** Free the lock.
 390     Return the CPU to helper if there is one, since it had to have a
 391     higher priority to be able to help (priority may be its own, it
 392     may run on a donated timeslice or round robin scheduling may have
 393     selected a thread on the same priority level as me)
 394
 395     @pre The lock must be valid (see valid()).
 396  */
 397 PUBLIC
 398 void NO_INSTRUMENT
 399 Switch_lock::clear()
 400 {
 401   auto guard = lock_guard(cpu_lock);
 402
 403   switch_dirty(clear_no_switch_dirty());
 404 }
 405
 406 PUBLIC
 407 void NO_INSTRUMENT
 408 Switch_lock::set(Status s)
 409 {
 410   if (s == Not_locked)
 411     clear();
 412 }
 413
 414 /** Free the lock.
 415     Return the CPU to helper if there is one, since it had to have a
 416     higher priority to be able to help (priority may be its own, it
 417     may run on a donated timeslice or round robin scheduling may have
 418     selected a thread on the same priority level as me).
 419     If _lock_owner is 0, then this is a no op
 420
 421     @pre The lock must be valid (see valid())
 422     @pre caller holds cpu lock
 423  */
 424 PUBLIC
 425 inline
 426 void NO_INSTRUMENT
 427 Switch_lock::clear_dirty()
 428 {
 429   assert(cpu_lock.test());
 430
 431   switch_dirty(clear_no_switch_dirty());
 432 }
 433
 434 PUBLIC inline
 435 void NO_INSTRUMENT
 436 Switch_lock::invalidate()
 437 {
 438   auto guard = lock_guard(cpu_lock);
 439   atomic_mp_or(&_lock_owner, 1);
 440 }
 441
 442 PUBLIC
 443 void NO_INSTRUMENT
 444 Switch_lock::wait_free()
 445 {
 446   auto guard = lock_guard(cpu_lock);
 447   Context *c = current();
 448
 449   assert (!valid());
 450
 451   if ((_lock_owner & ~1UL) == (Address)c)
 452     {
 453       clear_lock_owner();
 454       c->dec_lock_cnt();
 455       return;
 456     }
 457
 458   for(;;)
 459     {
 460       assert(cpu_lock.test());
 461
 462       Address _owner = access_once(&_lock_owner);
 463       Context *owner = (Context *)(_owner & ~1UL);
 464       if (!owner)
 465         break;
 466
 467       help(c, owner, _owner);
 468     }
 469 }