/* Copyright (C) 2004-2008 Grame This program is free software; you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation; either version 2.1 of the License, or (at your option) any later version. This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details. You should have received a copy of the GNU Lesser General Public License along with this program; if not, write to the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ #ifndef __JackAtomicArrayState__ #define __JackAtomicArrayState__ #include "JackAtomic.h" #include "JackCompilerDeps.h" #include // for memcpy #include namespace Jack { /*! \brief Counter for CAS */ PRE_PACKED_STRUCTURE struct AtomicArrayCounter { union { struct { unsigned char fByteVal[4]; } scounter; UInt32 fLongVal; }info; AtomicArrayCounter() { info.fLongVal = 0; } AtomicArrayCounter(volatile const AtomicArrayCounter& obj) { info.fLongVal = obj.info.fLongVal; } AtomicArrayCounter(volatile AtomicArrayCounter& obj) { info.fLongVal = obj.info.fLongVal; } AtomicArrayCounter& operator=(volatile AtomicArrayCounter& obj) { info.fLongVal = obj.info.fLongVal; return *this; } AtomicArrayCounter& operator=(AtomicArrayCounter& obj) { info.fLongVal = obj.info.fLongVal; return *this; } } POST_PACKED_STRUCTURE; #define Counter1(e) (e).info.fLongVal #define GetIndex1(e, state) ((e).info.scounter.fByteVal[state]) #define SetIndex1(e, state, val) ((e).info.scounter.fByteVal[state] = val) #define IncIndex1(e, state) ((e).info.scounter.fByteVal[state]++) #define SwapIndex1(e, state) (((e).info.scounter.fByteVal[0] == state) ? 0 : state) /*! \brief A class to handle several states in a lock-free manner Requirement: - a "current" state - several possible "pending" state - an TrySwitchState(int state) operation to atomically switch a "pending" to the "current" state (the pending becomes the current). 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) - a WriteNextStartState(int state) returns a "pending" state to be written into - a WriteNextStartStop(int state) make the written "pending" state become "switchable" Different pending states can be written independently and concurrently. GetCurrentIndex() *must* return an increasing value to be able to check reading current state coherency The fCounter is an array of indexes to access the current and 3 different "pending" states. WriteNextStateStart(int index) must return a valid state to be written into, and must invalidate state "index" ==> cur state switch. WriteNextStateStop(int index) makes the "index" state become "switchable" with the current state. TrySwitchState(int index) must detect that pending state is a new state, and does the switch ReadCurrentState() must return the state GetCurrentIndex() must return an index increased each new switch. WriteNextStateStart(int index1) and WriteNextStateStart(int index2) can be interleaved [switch counter][index state][index state][cur index] */ // CHECK livelock PRE_PACKED_STRUCTURE template class JackAtomicArrayState { protected: // fState[0] ==> current // fState[1] ==> pending // fState[2] ==> request T fState[3]; alignas(UInt32) alignas(AtomicArrayCounter) volatile AtomicArrayCounter fCounter; UInt32 WriteNextStateStartAux(int state, bool* result) { AtomicArrayCounter old_val; AtomicArrayCounter new_val; UInt32 cur_index; UInt32 next_index; bool need_copy; do { old_val = fCounter; new_val = old_val; *result = GetIndex1(new_val, state); cur_index = GetIndex1(new_val, 0); next_index = SwapIndex1(fCounter, state); need_copy = (GetIndex1(new_val, state) == 0); // Written = false, switch just occurred SetIndex1(new_val, state, 0); // Written = false, invalidate state } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter)); if (need_copy) memcpy(&fState[next_index], &fState[cur_index], sizeof(T)); return next_index; } void WriteNextStateStopAux(int state) { AtomicArrayCounter old_val; AtomicArrayCounter new_val; do { old_val = fCounter; new_val = old_val; SetIndex1(new_val, state, 1); // Written = true, state becomes "switchable" } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter)); } public: JackAtomicArrayState() { static_assert(offsetof(JackAtomicArrayState, fCounter) % sizeof(fCounter) == 0, "fCounter must be aligned within JackAtomicArrayState"); Counter1(fCounter) = 0; } ~JackAtomicArrayState() // Not virtual ?? {} /*! \brief Returns the current state : only valid in the RT reader thread */ T* ReadCurrentState() { return &fState[GetIndex1(fCounter, 0)]; } /*! \brief Returns the current switch counter */ UInt16 GetCurrentIndex() { return GetIndex1(fCounter, 3); } /*! \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) */ T* TrySwitchState(int state) { AtomicArrayCounter old_val; AtomicArrayCounter new_val; do { old_val = fCounter; new_val = old_val; if (GetIndex1(new_val, state)) { // If state has been written SetIndex1(new_val, 0, SwapIndex1(new_val, state)); // Prepare switch SetIndex1(new_val, state, 0); // Invalidate the state "state" IncIndex1(new_val, 3); // Inc switch } } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter)); return &fState[GetIndex1(fCounter, 0)]; // Read the counter again } /*! \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) */ T* TrySwitchState(int state, bool* result) { AtomicArrayCounter old_val; AtomicArrayCounter new_val; do { old_val = fCounter; new_val = old_val; if ((*result = GetIndex1(new_val, state))) { // If state has been written SetIndex1(new_val, 0, SwapIndex1(new_val, state)); // Prepare switch SetIndex1(new_val, state, 0); // Invalidate the state "state" IncIndex1(new_val, 3); // Inc switch } } while (!CAS(Counter1(old_val), Counter1(new_val), (UInt32*)&fCounter)); return &fState[GetIndex1(fCounter, 0)]; // Read the counter again } /*! \brief Start write operation : setup and returns the next state to update, check for recursive write calls. */ T* WriteNextStateStart(int state) { bool tmp; UInt32 index = WriteNextStateStartAux(state, &tmp); return &fState[index]; } T* WriteNextStateStart(int state, bool* result) { UInt32 index = WriteNextStateStartAux(state, result); return &fState[index]; } /*! \brief Stop write operation : make the next state ready to be used by the RT thread */ void WriteNextStateStop(int state) { WriteNextStateStopAux(state); } } POST_PACKED_STRUCTURE; } // end of namespace #endif