common/JackAtomicArrayState.h

   1 /*
   2 Copyright (C) 2004-2006 Grame
   3
   4 This program is free software; you can redistribute it and/or modify
   5 it under the terms of the GNU General Public License as published by
   6 the Free Software Foundation; either version 2 of the License, or
   7 (at your option) any later version.
   8
   9 This program is distributed in the hope that it will be useful,
  10 but WITHOUT ANY WARRANTY; without even the implied warranty of
  11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12 GNU General Public License for more details.
  13
  14 You should have received a copy of the GNU General Public License
  15 along with this program; if not, write to the Free Software
  16 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  17
  18 */
  19
  20 #ifndef __JackAtomicArrayState__
  21 #define __JackAtomicArrayState__
  22
  23 #include "JackAtomic.h"
  24 #include "JackCompilerDeps.h"
  25 #include <string.h> // for memcpy
  26
  27 namespace Jack
  28 {
  29
  30 /*!
  31 \brief Counter for CAS
  32 */
  33
  34 struct AtomicArrayCounter
  35 {
  36     union {
  37         struct {
  38             unsigned char fByteVal[4];
  39         }
  40         scounter;
  41         UInt32 fLongVal;
  42     }info;
  43
  44     AtomicArrayCounter()
  45     {
  46         info.fLongVal = 0;
  47     }
  48
  49     AtomicArrayCounter(volatile const AtomicArrayCounter& obj)
  50     {
  51         info.fLongVal = obj.info.fLongVal;
  52     }
  53
  54     AtomicArrayCounter(volatile AtomicArrayCounter& obj)
  55     {
  56         info.fLongVal = obj.info.fLongVal;
  57     }
  58
  59     AtomicArrayCounter& operator=(volatile AtomicArrayCounter& obj)
  60     {
  61         info.fLongVal = obj.info.fLongVal;
  62         return *this;
  63     }
  64
  65         AtomicArrayCounter& operator=(AtomicArrayCounter& obj)
  66         {
  67         info.fLongVal = obj.info.fLongVal;
  68         return *this;
  69     }
  70
  71 } POST_PACKED_STRUCTURE;
  72
  73 #define Counter1(e) (e).info.fLongVal
  74 #define GetIndex1(e, state) ((e).info.scounter.fByteVal[state])
  75 #define SetIndex1(e, state, val) ((e).info.scounter.fByteVal[state] = val)
  76 #define IncIndex1(e, state) ((e).info.scounter.fByteVal[state]++)
  77 #define SwapIndex1(e, state) (((e).info.scounter.fByteVal[0] == state) ? 0 : state)
  78
  79 /*!
  80 \brief A class to handle several states in a lock-free manner
  81
  82 Requirement:
  83
  84         - a "current" state
  85         - several possible "pending" state
  86         - an TrySwitchState(int state) operation to atomically switch a "pending" to the "current" state (the pending becomes the current).
  87
  88         The TrySwitchState operation returns a "current" state (either the same if switch fails or the new one, one can know if the switch has succeeded)
  89
  90         - a WriteNextStartState(int state) returns a "pending" state to be written into
  91         - a WriteNextStartStop(int state) make the written "pending" state become "switchable"
  92
  93         Different pending states can be written independantly and concurrently.
  94
  95         GetCurrentIndex() *must* return an increasing value to be able to check reading current state coherency
  96
  97         The fCounter is an array of indexes to access the current and 3 different "pending" states.
  98
  99           WriteNextStateStart(int index) must return a valid state to be written into, and must invalidate state "index" ==> cur state switch.
 100           WriteNextStateStop(int index) makes the "index" state become "switchable" with the current state.
 101           TrySwitchState(int index) must detect that pending state is a new state, and does the switch
 102           ReadCurrentState() must return the state
 103           GetCurrentIndex() must return an index increased each new switch.
 104           WriteNextStateStart(int index1) and WriteNextStateStart(int index2) can be interleaved
 105
 106         [switch counter][index state][index state][cur index]
 107
 108 */
 109
 110 // CHECK livelock
 111
 112 template <class T>
 113 class JackAtomicArrayState
 114 {
 115
 116     protected:
 117
 118         // fState[0] ==> current
 119         // fState[1] ==> pending
 120         // fState[2] ==> request
 121
 122         T fState[3];
 123         volatile AtomicArrayCounter fCounter;
 124
 125         UInt32 WriteNextStateStartAux(int state, bool* result)
 126         {
 127             AtomicArrayCounter old_val;
 128             AtomicArrayCounter new_val;
 129             UInt32 cur_index;
 130             UInt32 next_index;
 131             bool need_copy;
 132             do {
 133                 old_val = fCounter;
 134                 new_val = old_val;
 135                 *result = GetIndex1(new_val, state);
 136                 cur_index = GetIndex1(new_val, 0);
 137                 next_index = SwapIndex1(fCounter, state);
 138                 need_copy = (GetIndex1(new_val, state) == 0);   // Written = false, switch just occured
 139                 SetIndex1(new_val, state, 0);                                   // Written = false, invalidate state
 140             } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter));
 141             if (need_copy)
 142                 memcpy(&fState[next_index], &fState[cur_index], sizeof(T));
 143             return next_index;
 144         }
 145
 146         void WriteNextStateStopAux(int state)
 147         {
 148             AtomicArrayCounter old_val;
 149             AtomicArrayCounter new_val;
 150             do {
 151                 old_val = fCounter;
 152                 new_val = old_val;
 153                 SetIndex1(new_val, state, 1);  // Written = true, state becomes "switchable"
 154             } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter));
 155         }
 156
 157     public:
 158
 159         JackAtomicArrayState()
 160         {
 161             Counter1(fCounter) = 0;
 162         }
 163
 164         ~JackAtomicArrayState() // Not virtual ??
 165         {}
 166
 167         /*!
 168         \brief Returns the current state : only valid in the RT reader thread
 169         */
 170
 171         T* ReadCurrentState()
 172         {
 173             return &fState[GetIndex1(fCounter, 0)];
 174         }
 175
 176         /*!
 177         \brief Returns the current switch counter
 178         */
 179
 180         UInt16 GetCurrentIndex()
 181         {
 182             return GetIndex1(fCounter, 3);
 183         }
 184
 185         /*!
 186         \brief Tries to switch to the next state and returns the new current state (either the same as before if case of switch failure or the new one)
 187         */
 188
 189         T* TrySwitchState(int state)
 190         {
 191             AtomicArrayCounter old_val;
 192             AtomicArrayCounter new_val;
 193             do {
 194                 old_val = fCounter;
 195                 new_val = old_val;
 196                 if (GetIndex1(new_val, state)) {                                                // If state has been written
 197                     SetIndex1(new_val, 0, SwapIndex1(new_val, state));  // Prepare switch
 198                     SetIndex1(new_val, state, 0);                                               // Invalidate the state "state"
 199                     IncIndex1(new_val, 3);                                                              // Inc switch
 200                 }
 201             } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter));
 202             return &fState[GetIndex1(fCounter, 0)];     // Read the counter again
 203         }
 204
 205         /*!
 206         \brief Tries to switch to the next state and returns the new current state (either the same as before if case of switch failure or the new one)
 207         */
 208
 209         T* TrySwitchState(int state, bool* result)
 210         {
 211             AtomicArrayCounter old_val;
 212             AtomicArrayCounter new_val;
 213             do {
 214                 old_val = fCounter;
 215                 new_val = old_val;
 216                 if ((*result = GetIndex1(new_val, state))) {                    // If state has been written
 217                     SetIndex1(new_val, 0, SwapIndex1(new_val, state));  // Prepare switch
 218                     SetIndex1(new_val, state, 0);                                               // Invalidate the state "state"
 219                     IncIndex1(new_val, 3);                                                              // Inc switch
 220                 }
 221             } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter));
 222             return &fState[GetIndex1(fCounter, 0)];     // Read the counter again
 223         }
 224
 225         /*!
 226         \brief Start write operation : setup and returns the next state to update, check for recursive write calls.
 227         */
 228
 229         T* WriteNextStateStart(int state)
 230         {
 231             bool tmp;
 232             UInt32 index = WriteNextStateStartAux(state, &tmp);
 233             return &fState[index];
 234         }
 235
 236         T* WriteNextStateStart(int state, bool* result)
 237         {
 238             UInt32 index = WriteNextStateStartAux(state, result);
 239             return &fState[index];
 240         }
 241
 242         /*!
 243         \brief Stop write operation : make the next state ready to be used by the RT thread
 244         */
 245
 246         void WriteNextStateStop(int state)
 247         {
 248             WriteNextStateStopAux(state);
 249         }
 250
 251 } POST_PACKED_STRUCTURE;
 252
 253 } // end of namespace
 254
 255
 256 #endif
 257