junction/QSBR.cpp

   1 /*------------------------------------------------------------------------
   2   Junction: Concurrent data structures in C++
   3   Copyright (c) 2016 Jeff Preshing
   4
   5   Distributed under the Simplified BSD License.
   6   Original location: https://github.com/preshing/junction
   7
   8   This software is distributed WITHOUT ANY WARRANTY; without even the
   9   implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
  10   See the LICENSE file for more information.
  11 ------------------------------------------------------------------------*/
  12
  13 #include <junction/QSBR.h>
  14 #include <turf/Thread.h>
  15 #include <turf/Mutex.h>
  16 #include <turf/RaceDetector.h>
  17 #include <unordered_map>
  18 #include <vector>
  19
  20 namespace junction {
  21
  22 QSBR DefaultQSBR;
  23
  24 QSBR::Context QSBR::createContext() {
  25     turf::LockGuard<turf::Mutex> guard(m_mutex);
  26     TURF_RACE_DETECT_GUARD(m_flushRaceDetector);
  27     m_numContexts++;
  28     m_remaining++;
  29     TURF_ASSERT(m_numContexts < (1 << 14));
  30     sreg context = m_freeIndex;
  31     if (context >= 0) {
  32         TURF_ASSERT(context < (sreg) m_status.size());
  33         TURF_ASSERT(!m_status[context].inUse);
  34         m_freeIndex = m_status[context].nextFree;
  35         m_status[context] = Status();
  36     } else {
  37         context = m_status.size();
  38         m_status.push_back(Status());
  39     }
  40     return context;
  41 }
  42
  43 void QSBR::destroyContext(QSBR::Context context) {
  44     std::vector<Action> actions;
  45     {
  46         turf::LockGuard<turf::Mutex> guard(m_mutex);
  47         TURF_RACE_DETECT_GUARD(m_flushRaceDetector);
  48         TURF_ASSERT(context < m_status.size());
  49         if (m_status[context].inUse && !m_status[context].wasIdle) {
  50             TURF_ASSERT(m_remaining > 0);
  51             --m_remaining;
  52         }
  53         m_status[context].inUse = 0;
  54         m_status[context].nextFree = m_freeIndex;
  55         m_freeIndex = context;
  56         m_numContexts--;
  57         if (m_remaining == 0)
  58             onAllQuiescentStatesPassed(actions);
  59     }
  60     for (ureg i = 0; i < actions.size(); i++)
  61         actions[i]();
  62 }
  63
  64 void QSBR::onAllQuiescentStatesPassed(std::vector<Action>& actions) {
  65     // m_mutex must be held
  66     actions.swap(m_pendingActions);
  67     m_pendingActions.swap(m_deferredActions);
  68     m_remaining = m_numContexts;
  69     for (ureg i = 0; i < m_status.size(); i++)
  70         m_status[i].wasIdle = 0;
  71 }
  72
  73 void QSBR::update(QSBR::Context context) {
  74     std::vector<Action> actions;
  75     {
  76         turf::LockGuard<turf::Mutex> guard(m_mutex);
  77         TURF_RACE_DETECT_GUARD(m_flushRaceDetector);
  78         TURF_ASSERT(context < m_status.size());
  79         Status& status = m_status[context];
  80         TURF_ASSERT(status.inUse);
  81         if (status.wasIdle)
  82             return;
  83         status.wasIdle = 1;
  84         TURF_ASSERT(m_remaining > 0);
  85         if (--m_remaining > 0)
  86             return;
  87         onAllQuiescentStatesPassed(actions);
  88     }
  89     for (ureg i = 0; i < actions.size(); i++)
  90         actions[i]();
  91 }
  92
  93 void QSBR::flush() {
  94     // This is like saying that all contexts are quiescent,
  95     // so we can issue all actions at once.
  96     // No lock is taken.
  97     TURF_RACE_DETECT_GUARD(m_flushRaceDetector); // There should be no concurrent operations
  98     for (ureg i = 0; i < m_pendingActions.size(); i++)
  99         m_pendingActions[i]();
 100     m_pendingActions.clear();
 101     for (ureg i = 0; i < m_deferredActions.size(); i++)
 102         m_deferredActions[i]();
 103     m_deferredActions.clear();
 104     m_remaining = m_numContexts;
 105 }
 106
 107 } // namespace junction