kernel/fiasco/src/kern/rcupdate.cpp

   1 INTERFACE:
   2
   3 #include "cpu_mask.h"
   4 #include "per_cpu_data.h"
   5 #include "spin_lock.h"
   6 #include <slist>
   7
   8 class Rcu_glbl;
   9 class Rcu_data;
  10
  11 /**
  12  * \brief Encapsulation of RCU batch number.
  13  */
  14 class Rcu_batch
  15 {
  16   friend class Jdb_rcupdate;
  17 public:
  18   /// create uninitialized batch.
  19   Rcu_batch() {}
  20   /// create a btach initialized with \a b.
  21   Rcu_batch(long b) : _b(b) {}
  22
  23   /// less than comparison.
  24   bool operator < (Rcu_batch const &o) const { return (_b - o._b) < 0; }
  25   /// greater than comparison.
  26   bool operator > (Rcu_batch const &o) const { return (_b - o._b) > 0; }
  27   /// greater than comparison.
  28   bool operator >= (Rcu_batch const &o) const { return (_b - o._b) >= 0; }
  29   /// equelity check.
  30   bool operator == (Rcu_batch const &o) const { return _b == o._b; }
  31   /// inequality test.
  32   bool operator != (Rcu_batch const &o) const { return _b != o._b; }
  33   /// increment batch.
  34   Rcu_batch &operator ++ () { ++_b; return *this; }
  35   /// increase batch with \a r.
  36   Rcu_batch operator + (long r) { return Rcu_batch(_b + r); }
  37
  38
  39 private:
  40   long _b;
  41 };
  42
  43 /**
  44  * \brief Item that can bequeued for the next grace period.
  45  *
  46  * An RCU item is basically a pointer to a callback which is called
  47  * after one grace period.
  48  */
  49 class Rcu_item : public cxx::S_list_item
  50 {
  51   friend class Rcu_data;
  52   friend class Rcu;
  53   friend class Jdb_rcupdate;
  54
  55 private:
  56   bool (*_call_back)(Rcu_item *);
  57 };
  58
  59
  60 /**
  61  * \brief List of Rcu_items.
  62  *
  63  * RCU lists are used a lot of times in the RCU implementation and are
  64  * implemented as single linked lists with FIFO semantics.
  65  *
  66  * \note Concurrent access to the list is not synchronized.
  67  */
  68 class Rcu_list : public cxx::S_list_tail<Rcu_item>
  69 {
  70 private:
  71   typedef cxx::S_list_tail<Rcu_item> Base;
  72 public:
  73   Rcu_list() {}
  74   Rcu_list(Rcu_list &&o) : Base(static_cast<Base &&>(o)) {}
  75   Rcu_list &operator = (Rcu_list &&o)
  76   {
  77     Base::operator = (static_cast<Base &&>(o));
  78     return *this;
  79   }
  80
  81 private:
  82   friend class Jdb_rcupdate;
  83 };
  84
  85 /**
  86  * \brief CPU local data structure for RCU.
  87  */
  88 class Rcu_data
  89 {
  90   friend class Jdb_rcupdate;
  91 public:
  92
  93   Rcu_batch _q_batch;   ///< batch nr. for grace period
  94   bool _q_passed;       ///< quiescent state passed?
  95   bool _pending;        ///< wait for quiescent state
  96   bool _idle;
  97
  98   Rcu_batch _batch;
  99   Rcu_list _n;
 100   long _len;
 101   Rcu_list _c;
 102   Rcu_list _d;
 103   unsigned _cpu;
 104 };
 105
 106
 107 /**
 108  * \brief Global RCU data structure.
 109  */
 110 class Rcu_glbl
 111 {
 112   friend class Rcu_data;
 113   friend class Rcu;
 114   friend class Jdb_rcupdate;
 115
 116 private:
 117   Rcu_batch _current;      ///< current batch
 118   Rcu_batch _completed;    ///< last completed batch
 119   bool _next_pending;      ///< next batch already pending?
 120   Spin_lock<> _lock;
 121   Cpu_mask _cpus;
 122
 123   Cpu_mask _active_cpus;
 124
 125 };
 126
 127 /**
 128  * \brief encapsulation of RCU implementation.
 129  *
 130  * This calss aggregates per CPU data structures as well as the global
 131  * data structure for RCU and provides a common RCU interface.
 132  */
 133 class Rcu
 134 {
 135   friend class Rcu_data;
 136   friend class Jdb_rcupdate;
 137
 138 public:
 139   /// The lock to prevent a quiescent state.
 140   typedef Cpu_lock Lock;
 141   enum { Period = 3000 /* 10ms */ };
 142   static Rcu_glbl *rcu() { return &_rcu; }
 143 private:
 144   static Rcu_glbl _rcu;
 145   static Per_cpu<Rcu_data> _rcu_data;
 146 };
 147
 148 // ------------------------------------------------------------------------
 149 INTERFACE [debug]:
 150
 151 #include "tb_entry.h"
 152
 153 EXTENSION class Rcu
 154 {
 155 public:
 156   struct Log_rcu : public Tb_entry
 157   {
 158     unsigned cpu;
 159     Rcu_item *item;
 160     void *cb;
 161     unsigned char event;
 162     unsigned print(int max, char *buf) const;
 163   } __attribute__((packed));
 164
 165   enum Rcu_events
 166   {
 167     Rcu_call = 0,
 168     Rcu_process = 1,
 169   };
 170 };
 171
 172
 173 // --------------------------------------------------------------------------
 174 IMPLEMENTATION [debug]:
 175
 176 #include "logdefs.h"
 177
 178 IMPLEMENT
 179 unsigned
 180 Rcu::Log_rcu::print(int max, char *buf) const
 181 {
 182   char const *events[] = { "call", "process"};
 183   return snprintf(buf, max, "rcu-%s (cpu=%u) item=%p", events[event], cpu, item);
 184 }
 185
 186
 187 //--------------------------------------------------------------------------
 188 IMPLEMENTATION:
 189
 190 #include "cpu.h"
 191 #include "cpu_lock.h"
 192 #include "globals.h"
 193 #include "kdb_ke.h"
 194 #include "lock_guard.h"
 195 #include "mem.h"
 196 #include "static_init.h"
 197 #include "timeout.h"
 198 #include "logdefs.h"
 199
 200 // XXX: includes for debugging
 201 // #include "logdefs.h"
 202
 203
 204 class Rcu_timeout : public Timeout
 205 {
 206 };
 207
 208 /**
 209  * Timeout expiration callback function
 210  * @return true if reschedule is necessary, false otherwise
 211  */
 212 PRIVATE
 213 bool
 214 Rcu_timeout::expired()
 215 { return Rcu::process_callbacks(); }
 216
 217
 218 Rcu_glbl Rcu::_rcu INIT_PRIORITY(EARLY_INIT_PRIO);
 219 DEFINE_PER_CPU Per_cpu<Rcu_data> Rcu::_rcu_data(true);
 220 DEFINE_PER_CPU static Per_cpu<Rcu_timeout> _rcu_timeout;
 221
 222 PUBLIC
 223 Rcu_glbl::Rcu_glbl()
 224 : _current(-300),
 225   _completed(-300)
 226 {}
 227
 228 PUBLIC
 229 Rcu_data::Rcu_data(unsigned cpu)
 230 : _idle(true),
 231   _cpu(cpu)
 232 {}
 233
 234
 235 /**
 236  * \brief Enqueue Rcu_item into the list (at the tail).
 237  * \prarm i the RCU item to enqueue.
 238  */
 239 PUBLIC inline void Rcu_list::enqueue(Rcu_item *i){ push_back(i); }
 240
 241 /**
 242  * \pre must run under cpu lock
 243  */
 244 PUBLIC inline
 245 void
 246 Rcu_data::enqueue(Rcu_item *i)
 247 {
 248   _n.enqueue(i);
 249   ++_len;
 250 }
 251
 252 PRIVATE inline NOEXPORT NEEDS["cpu_lock.h", "lock_guard.h"]
 253 bool
 254 Rcu_data::do_batch()
 255 {
 256   int count = 0;
 257   bool need_resched = false;
 258   for (Rcu_list::Const_iterator l = _d.begin(); l != _d.end();)
 259     {
 260       Rcu_item *i = *l;
 261       ++l;
 262
 263       need_resched |= i->_call_back(i);
 264       ++count;
 265     }
 266
 267   // XXX: I do not know why this and the former stuff is w/o cpu lock
 268   //      but the couting needs it ?
 269   _d.clear();
 270
 271   // XXX: we use clear, we seemingly worked through the whole list
 272   //_d.head(l);
 273
 274     {
 275       auto guard = lock_guard(cpu_lock);
 276       _len -= count;
 277     }
 278 #if 0
 279   if (_d.full())
 280     {
 281       Timeout *t = &_rcu_timeout.cpu(_cpu);
 282       t->set(t->get_timeout(0) + Rcu::Period, _cpu);
 283     }
 284 #endif
 285   return need_resched;
 286 }
 287
 288 PRIVATE inline NOEXPORT
 289 void
 290 Rcu_glbl::start_batch()
 291 {
 292   if (_next_pending && _completed == _current)
 293     {
 294       _next_pending = 0;
 295       Mem::mp_wmb();
 296       ++_current;
 297       Mem::mp_mb();
 298       _cpus = _active_cpus;
 299     }
 300 }
 301
 302 PUBLIC static inline
 303 void
 304 Rcu::enter_idle(unsigned cpu)
 305 {
 306   Rcu_data *rdp = &_rcu_data.cpu(cpu);
 307   if (EXPECT_TRUE(!rdp->_idle))
 308     {
 309       rdp->_idle = true;
 310       auto guard = lock_guard(rcu()->_lock);
 311       rcu()->_active_cpus.clear(cpu);
 312     }
 313 }
 314
 315 PUBLIC static inline
 316 void
 317 Rcu::leave_idle(unsigned cpu)
 318 {
 319   Rcu_data *rdp = &_rcu_data.cpu(cpu);
 320   if (EXPECT_FALSE(rdp->_idle))
 321     {
 322       rdp->_idle = false;
 323       auto guard = lock_guard(rcu()->_lock);
 324       rcu()->_active_cpus.set(cpu);
 325       rdp->_q_batch = Rcu::rcu()->_current;
 326     }
 327 }
 328
 329
 330 PRIVATE inline NOEXPORT
 331 void
 332 Rcu_glbl::cpu_quiet(unsigned cpu)
 333 {
 334   _cpus.clear(cpu);
 335   if (_cpus.empty())
 336     {
 337       _completed = _current;
 338       start_batch();
 339     }
 340 }
 341
 342 PRIVATE
 343 void
 344 Rcu_data::check_quiescent_state(Rcu_glbl *rgp)
 345 {
 346   if (_q_batch != rgp->_current)
 347     {
 348       // start new grace period
 349       _pending = 1;
 350       _q_passed = 0;
 351       _q_batch = rgp->_current;
 352       return;
 353     }
 354
 355   // Is the grace period already completed for this cpu?
 356   // use _pending, not bitmap to avoid cache trashing
 357   if (!_pending)
 358     return;
 359
 360   // Was there a quiescent state since the beginning of the grace period?
 361   if (!_q_passed)
 362     return;
 363
 364   _pending = 0;
 365
 366   auto guard = lock_guard(rgp->_lock);
 367
 368   if (EXPECT_TRUE(_q_batch == rgp->_current))
 369     rgp->cpu_quiet(_cpu);
 370 }
 371
 372
 373 PUBLIC static //inline NEEDS["cpu_lock.h", "globals.h", "lock_guard.h", "logdefs.h"]
 374 void
 375 Rcu::call(Rcu_item *i, bool (*cb)(Rcu_item *))
 376 {
 377   i->_call_back = cb;
 378   LOG_TRACE("Rcu call", "rcu", ::current(), Log_rcu,
 379       l->cpu   = current_cpu();
 380       l->event = Rcu_call;
 381       l->item = i;
 382       l->cb = (void*)cb);
 383
 384   auto guard = lock_guard(cpu_lock);
 385
 386   Rcu_data *rdp = &_rcu_data.current();
 387   rdp->enqueue(i);
 388 }
 389
 390 PRIVATE
 391 void
 392 Rcu_data::move_batch(Rcu_list &l)
 393 {
 394   auto guard = lock_guard(cpu_lock);
 395   _n.append(l);
 396 }
 397
 398
 399 PUBLIC
 400 Rcu_data::~Rcu_data()
 401 {
 402   if (current_cpu() == _cpu)
 403     return;
 404
 405   Rcu_data *current_rdp = &Rcu::_rcu_data.current();
 406   Rcu_glbl *rgp = Rcu::rcu();
 407
 408     {
 409       auto guard = lock_guard(rgp->_lock);
 410       if (rgp->_current != rgp->_completed)
 411         rgp->cpu_quiet(_cpu);
 412     }
 413
 414   current_rdp->move_batch(_c);
 415   current_rdp->move_batch(_n);
 416   current_rdp->move_batch(_d);
 417 }
 418
 419 PUBLIC
 420 bool FIASCO_WARN_RESULT
 421 Rcu_data::process_callbacks(Rcu_glbl *rgp)
 422 {
 423   LOG_TRACE("Rcu callbacks", "rcu", ::current(), Rcu::Log_rcu,
 424       l->cpu = _cpu;
 425       l->item = 0;
 426       l->event = Rcu::Rcu_process);
 427
 428   if (!_c.empty() && rgp->_completed >= _batch)
 429     _d.append(_c);
 430
 431   if (!_n.empty() && _c.empty())
 432     {
 433         {
 434           auto guard = lock_guard(cpu_lock);
 435           _c = cxx::move(_n);
 436         }
 437
 438       // start the next batch of callbacks
 439
 440       _batch = rgp->_current + 1;
 441       Mem::mp_rmb();
 442
 443       if (!rgp->_next_pending)
 444         {
 445           // start the batch and schedule start if it's a new batch
 446           auto guard = lock_guard(rgp->_lock);
 447           rgp->_next_pending = 1;
 448           rgp->start_batch();
 449         }
 450     }
 451
 452   check_quiescent_state(rgp);
 453   if (!_d.empty())
 454     return do_batch();
 455
 456   return false;
 457 }
 458
 459 PUBLIC inline
 460 bool
 461 Rcu_data::pending(Rcu_glbl *rgp) const
 462 {
 463   // The CPU has pending RCU callbacks and the grace period for them
 464   // has been completed.
 465   if (!_c.empty() && rgp->_completed >= _batch)
 466     return 1;
 467
 468   // The CPU has no pending RCU callbacks, however there are new callbacks
 469   if (_c.empty() && !_n.empty())
 470     return 1;
 471
 472   // The CPU has callbacks to be invoked finally
 473   if (!_d.empty())
 474     return 1;
 475
 476   // RCU waits for a quiescent state from the CPU
 477   if ((_q_batch != rgp->_current) || _pending)
 478     return 1;
 479
 480   // OK, no RCU work to do
 481   return 0;
 482
 483 }
 484
 485 PUBLIC static inline NEEDS["globals.h"]
 486 bool FIASCO_WARN_RESULT
 487 Rcu::process_callbacks()
 488 { return _rcu_data.current().process_callbacks(&_rcu); }
 489
 490 PUBLIC static inline NEEDS["globals.h"]
 491 bool FIASCO_WARN_RESULT
 492 Rcu::process_callbacks(unsigned cpu)
 493 { return _rcu_data.cpu(cpu).process_callbacks(&_rcu); }
 494
 495 PUBLIC static inline
 496 bool
 497 Rcu::pending(unsigned cpu)
 498 {
 499   return _rcu_data.cpu(cpu).pending(&_rcu);
 500 }
 501
 502 PUBLIC static inline
 503 bool
 504 Rcu::idle(unsigned cpu)
 505 {
 506   Rcu_data const *d = &_rcu_data.cpu(cpu);
 507   return d->_c.empty() && !d->pending(&_rcu);
 508 }
 509
 510 PUBLIC static inline
 511 void
 512 Rcu::inc_q_cnt(unsigned cpu)
 513 { _rcu_data.cpu(cpu)._q_passed = 1; }
 514
 515 PUBLIC static
 516 void
 517 Rcu::schedule_callbacks(unsigned cpu, Unsigned64 clock)
 518 {
 519   Timeout *t = &_rcu_timeout.cpu(cpu);
 520   if (!t->is_set())
 521     t->set(clock, cpu);
 522 }
 523
 524 PUBLIC static inline NEEDS["cpu_lock.h"]
 525 Rcu::Lock *
 526 Rcu::lock()
 527 { return &cpu_lock; }
 528
 529
 530 PUBLIC static inline
 531 bool
 532 Rcu::do_pending_work(unsigned cpu)
 533 {
 534   if (pending(cpu))
 535     {
 536       inc_q_cnt(cpu);
 537       return process_callbacks(cpu);
 538 #if 0
 539       Rcu::schedule_callbacks(cpu, Kip::k()->clock + Rcu::Period);
 540 #endif
 541     }
 542   return false;
 543 }