common/JackAtomicArrayState.h

   1 /*
   2  Copyright (C) 2004-2008 Grame
   3
   4  This program is free software; you can redistribute it and/or modify
   5  it under the terms of the GNU Lesser General Public License as published by
   6  the Free Software Foundation; either version 2.1 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 Lesser General Public License for more details.
  13
  14  You should have received a copy of the GNU Lesser General Public License
  15  along with this program; if not, write to the Free Software
  16  Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 PRE_PACKED_STRUCTURE
  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 independently 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 PRE_PACKED_STRUCTURE
 113 template <class T>
 114 class JackAtomicArrayState
 115 {
 116
 117     protected:
 118
 119         // fState[0] ==> current
 120         // fState[1] ==> pending
 121         // fState[2] ==> request
 122
 123         T fState[3];
 124         volatile AtomicArrayCounter fCounter;
 125
 126         UInt32 WriteNextStateStartAux(int state, bool* result)
 127         {
 128             AtomicArrayCounter old_val;
 129             AtomicArrayCounter new_val;
 130             UInt32 cur_index;
 131             UInt32 next_index;
 132             bool need_copy;
 133             do {
 134                 old_val = fCounter;
 135                 new_val = old_val;
 136                 *result = GetIndex1(new_val, state);
 137                 cur_index = GetIndex1(new_val, 0);
 138                 next_index = SwapIndex1(fCounter, state);
 139                 need_copy = (GetIndex1(new_val, state) == 0);   // Written = false, switch just occurred
 140                 SetIndex1(new_val, state, 0);                                   // Written = false, invalidate state
 141             } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter));
 142             if (need_copy)
 143                 memcpy(&fState[next_index], &fState[cur_index], sizeof(T));
 144             return next_index;
 145         }
 146
 147         void WriteNextStateStopAux(int state)
 148         {
 149             AtomicArrayCounter old_val;
 150             AtomicArrayCounter new_val;
 151             do {
 152                 old_val = fCounter;
 153                 new_val = old_val;
 154                 SetIndex1(new_val, state, 1);  // Written = true, state becomes "switchable"
 155             } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter));
 156         }
 157
 158     public:
 159
 160         JackAtomicArrayState()
 161         {
 162             Counter1(fCounter) = 0;
 163         }
 164
 165         ~JackAtomicArrayState() // Not virtual ??
 166         {}
 167
 168         /*!
 169         \brief Returns the current state : only valid in the RT reader thread
 170         */
 171
 172         T* ReadCurrentState()
 173         {
 174             return &fState[GetIndex1(fCounter, 0)];
 175         }
 176
 177         /*!
 178         \brief Returns the current switch counter
 179         */
 180
 181         UInt16 GetCurrentIndex()
 182         {
 183             return GetIndex1(fCounter, 3);
 184         }
 185
 186         /*!
 187         \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)
 188         */
 189
 190         T* TrySwitchState(int state)
 191         {
 192             AtomicArrayCounter old_val;
 193             AtomicArrayCounter new_val;
 194             do {
 195                 old_val = fCounter;
 196                 new_val = old_val;
 197                 if (GetIndex1(new_val, state)) {                                                // If state has been written
 198                     SetIndex1(new_val, 0, SwapIndex1(new_val, state));  // Prepare switch
 199                     SetIndex1(new_val, state, 0);                                               // Invalidate the state "state"
 200                     IncIndex1(new_val, 3);                                                              // Inc switch
 201                 }
 202             } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter));
 203             return &fState[GetIndex1(fCounter, 0)];     // Read the counter again
 204         }
 205
 206         /*!
 207         \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)
 208         */
 209
 210         T* TrySwitchState(int state, bool* result)
 211         {
 212             AtomicArrayCounter old_val;
 213             AtomicArrayCounter new_val;
 214             do {
 215                 old_val = fCounter;
 216                 new_val = old_val;
 217                 if ((*result = GetIndex1(new_val, state))) {                    // If state has been written
 218                     SetIndex1(new_val, 0, SwapIndex1(new_val, state));  // Prepare switch
 219                     SetIndex1(new_val, state, 0);                                               // Invalidate the state "state"
 220                     IncIndex1(new_val, 3);                                                              // Inc switch
 221                 }
 222             } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter));
 223             return &fState[GetIndex1(fCounter, 0)];     // Read the counter again
 224         }
 225
 226         /*!
 227         \brief Start write operation : setup and returns the next state to update, check for recursive write calls.
 228         */
 229
 230         T* WriteNextStateStart(int state)
 231         {
 232             bool tmp;
 233             UInt32 index = WriteNextStateStartAux(state, &tmp);
 234             return &fState[index];
 235         }
 236
 237         T* WriteNextStateStart(int state, bool* result)
 238         {
 239             UInt32 index = WriteNextStateStartAux(state, result);
 240             return &fState[index];
 241         }
 242
 243         /*!
 244         \brief Stop write operation : make the next state ready to be used by the RT thread
 245         */
 246
 247         void WriteNextStateStop(int state)
 248         {
 249             WriteNextStateStopAux(state);
 250         }
 251
 252 } POST_PACKED_STRUCTURE;
 253
 254 } // end of namespace
 255
 256
 257 #endif
 258