Concurrent.h

Go to the documentation of this file.

/*
 * Copyright (c) 2018-2019 pongasoft
 *
 * Licensed under the Apache License, Version 2.0 or the MIT license,
 * at your option. You may not use this file except in compliance with
 * one of these licenses. You may obtain copies of the licenses at:
 *
 * https://www.apache.org/licenses/LICENSE-2.0
 * https://opensource.org/licenses/MIT
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 *
 * @author Yan Pujante
 */
#ifndef __PONGASOFT_UTILS_CONCURRENT_CONCURRENT_H__
#define __PONGASOFT_UTILS_CONCURRENT_CONCURRENT_H__
 
#include "SpinLock.h"
 
#include <memory>
 
namespace pongasoft {
namespace Utils {

template<typename M, typename T>
concept ElementModifier = std::invocable<M, T*>;

template<typename M, typename T>
concept ElementPredicate =
  std::invocable<M, T*> &&
  std::convertible_to<std::invoke_result_t<M, T*>, bool>;
 
namespace Concurrent {
 
/*
 * One of the big issues in the VST world comes from the fact that the processing thread maintains the state, but it
 * is being accessed/changed by the UI thread (AudioEffect::setState and AudioEffect::getState). Moreover, if the
 * processing thread needs to send a message to the UI thread, this must happen in a timer (running in the UI thread),
 * meaning the processing thread needs to have a way to communicate the content of the message to the timer in a
 * thread-safe way. See thread https://sdk.steinberg.net/viewtopic.php?f=4&t=516 for discussion.
 *
 * The 2 primitives required are an atomic value (for getState) and a queue with one element (where the element in the
 * queue can be updated if not popped yet) (for setState / timer message)
 *
 * The golden rules of real time audio programming are not to use locks or memory allocation. Here are 2
 * implementations with different tradeoffs.
 *
 * The LockFree namespace implements a version that does not use locks or allocate memory at runtime (only when
 * the classes are created). The tradeoff is that it uses more memory (3 instances of T) and it is only thread
 * safe when there is a single thread calling 'get' (resp 'pop') and another single thread calling 'set' (rep 'push').
 *
 * The WithSpinLock namespace a version which uses a very lightweight lock: a user space spin lock. The SpinLock
 * implementation is not allocating any memory in any thread and is relying on the std::atomic_flag concept which is
 * guaranteed to be lock free. It also does not make any system calls. The tradeoff is that the queue and atomic
 * value do lock for the duration of the copy of T. The advantages are less memory use and fully multi thread safe.
 */
 
//------------------------------------------------------------------------
// Lock Free Implementation of AtomicValue and SingleQueueElement
//------------------------------------------------------------------------
namespace LockFree {
template<typename T>
class SingleElementStorage
{
public:
  // wraps a unique pointer of type T and whether it is a new value or not
  struct Element
  {
    Element(std::unique_ptr<T> iElement, bool iNew) noexcept : fElement{std::move(iElement)}, fNew{iNew} {}
 
    std::unique_ptr<T> fElement;
    bool fNew;
  };
 
public:
  // Constructor
  SingleElementStorage(std::unique_ptr<T> iElement, bool iIsEmpty) noexcept :
    fSingleElement{new Element(std::move(iElement), !iIsEmpty)}
  {}
 
  // Destructor - Deletes the element created in the constructor
  ~SingleElementStorage()
  {
    delete fSingleElement.exchange(nullptr);
  }
 
  // isEmpty
  bool isEmpty() const
  {
    return !fSingleElement.load()->fNew;
  }

  bool __isLockFree() const { return fSingleElement.is_lock_free(); }
 
protected:
  std::unique_ptr<Element> store(std::unique_ptr<Element> iElement)
  {
    iElement->fNew = true;
    iElement.reset(fSingleElement.exchange(iElement.release()));
    return std::move(iElement);
  }

  std::unique_ptr<Element> load(std::unique_ptr<Element> iElement)
  {
    iElement->fNew = false;
    iElement.reset(fSingleElement.exchange(iElement.release()));
    return std::move(iElement);
  }
 
  // __newT => create a new T by using copy constructor
  std::unique_ptr<T> __newT() const { return std::make_unique<T>(*(fSingleElement.load()->fElement)); }
 
  // __newElement
  std::unique_ptr<Element> __newElement() const { return std::make_unique<Element>(std::move(__newT()), false); }
 
private:
  // using a std::atomic on a pointer which should be lock free (check __isLockFree for sanity check!)
  std::atomic<Element *> fSingleElement;
};

template<typename T>
class SingleElementQueue : public SingleElementStorage<T>
{
public:
  // Constructor
  SingleElementQueue() :
    SingleElementStorage<T>{std::make_unique<T>(), true},
    fPopValue{std::move(SingleElementStorage<T>::__newElement())},
    fPushValue{std::move(SingleElementStorage<T>::__newElement())}
  {}

  explicit SingleElementQueue(std::unique_ptr<T> iElement, bool iIsEmpty = false) :
    SingleElementStorage<T>{std::move(iElement), iIsEmpty},
    fPopValue{std::move(SingleElementStorage<T>::__newElement())},
    fPushValue{std::move(SingleElementStorage<T>::__newElement())}
  {
  }
 
  //------------------------------------------------------------------------------------------------------------
  // WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
  //
  // All the following methods (pop and last) should be called in a single thread
  //
  // WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
  //------------------------------------------------------------------------------------------------------------
  T *pop()
  {
    if(!this->isEmpty())
    {
      fPopValue = std::move(SingleElementStorage<T>::load(std::move(fPopValue)));
    }
 
    if(fPopValue->fNew)
    {
      fPopValue->fNew = false;
      return fPopValue->fElement.get();
    }
 
    return nullptr;
  }

  bool pop(T &oElement)
  {
    auto element = pop();
    if(element)
    {
      oElement = *element;
      return true;
    }
 
    return false;
  }

  T const *last() const
  {
    return fPopValue->fElement.get();
  }
 

  void last(T &oElement) const
  {
    oElement = *last();
  }

  T const *popOrLast()
  {
    auto element = pop();
 
    if(element)
      return element;
    else
      return fPopValue->fElement.get();
  }
 

  void popOrLast(T &oElement)
  {
    oElement = *popOrLast();
  }
 
  //------------------------------------------------------------------------------------------------------------
  // WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
  //
  // All the following methods (push and updateAndPush) should be called in a single thread
  //
  // WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
  //------------------------------------------------------------------------------------------------------------

  void push(T const &iElement)
  {
    *(fPushValue->fElement.get()) = iElement;
    pushValue();
  }

  void push(T const *iElement)
  {
    *(fPushValue->fElement.get()) = *iElement;
    pushValue();
  }

  template<ElementModifier<T> Modifier>
  void updateAndPush(Modifier const &iElementModifier)
  {
    std::invoke(iElementModifier, fPushValue->fElement.get());
    pushValue();
  }

  template<ElementPredicate<T> Modifier>
  bool updateAndPushIf(Modifier const &iElementModifier)
  {
    if(std::invoke(iElementModifier, fPushValue->fElement.get()))
    {
      pushValue();
      return true;
    }
    return false;
  }
private:
  void pushValue()
  {
    fPushValue = std::move(SingleElementStorage<T>::store(std::move(fPushValue)));
  }
 
private:
  using Element = SingleElementStorage<T>::Element;
 
  std::unique_ptr<Element> fPopValue;
  std::unique_ptr<Element> fPushValue;
};

template<typename T>
class AtomicValue : public SingleElementStorage<T>
{
public:
  // Constructor - needs a value for initalizing the object
  explicit AtomicValue(std::unique_ptr<T> iValue) :
    SingleElementStorage<T>{std::move(iValue), false},
    fGetValue{std::move(SingleElementStorage<T>::__newElement())},
    fSetValue{std::move(SingleElementStorage<T>::__newElement())}
  {}
 
  //------------------------------------------------------------------------------------------------------------
  // WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
  //
  // All the following methods (get) should be called in a single thread
  //
  // WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
  //------------------------------------------------------------------------------------------------------------

  T const *get()
  {
    if(!this->isEmpty())
    {
      fGetValue = std::move(SingleElementStorage<T>::load(std::move(fGetValue)));
    }
 
    return fGetValue->fElement.get();
  }

  T getCopy()
  {
    return *get();
  }

  void get(T &oElement)
  {
    oElement = *get();
  }

  void get(T *oElement)
  {
    *oElement = *get();
  }
 
  //------------------------------------------------------------------------------------------------------------
  // WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
  //
  // All the following methods (set / update) should be called in a single thread
  //
  // WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING
  //------------------------------------------------------------------------------------------------------------

  void set(T const &iValue)
  {
    *(fSetValue->fElement.get()) = iValue;
    fSetValue = std::move(SingleElementStorage<T>::store(std::move(fSetValue)));
  }

  void set(T const *iValue)
  {
    *(fSetValue->fElement.get()) = *iValue;
    fSetValue = std::move(SingleElementStorage<T>::store(std::move(fSetValue)));
  }

  template<ElementModifier<T> Modifier>
  void update(Modifier const &iElementModifier)
  {
    std::invoke(iElementModifier, fSetValue->fElement.get());
    fSetValue = std::move(SingleElementStorage<T>::store(std::move(fSetValue)));
  }

  template<ElementPredicate<T> Modifier>
  bool updateIf(Modifier const &iElementModifier)
  {
    if(std::invoke(iElementModifier, fSetValue->fElement.get()))
    {
      fSetValue = std::move(SingleElementStorage<T>::store(std::move(fSetValue)));
      return true;
    }
 
    return false;
  }
 
private:
  using Element = SingleElementStorage<T>::Element;
 
  std::unique_ptr<Element> fGetValue;
  std::unique_ptr<Element> fSetValue;
};
}

namespace WithSpinLock {

template<typename T>
class SingleElementQueue
{
public:
  SingleElementQueue() : fSingleElement{std::make_unique<T>()}, fIsEmpty{true}, fSpinLock{}
  {}

  explicit SingleElementQueue(std::unique_ptr<T> iFirstElement,
                              bool iIsEmpty = false) :
    fSingleElement{std::move(iFirstElement)},
    fIsEmpty{iIsEmpty},
    fSpinLock{}
  {}

  bool isEmpty() const
  {
    auto lock = fSpinLock.acquire();
    return fIsEmpty;
  }

  bool pop(T &oElement)
  {
    auto lock = fSpinLock.acquire();
    if(fIsEmpty)
      return false;
 
    oElement = *fSingleElement;
    fIsEmpty = true;
 
    return true;
  }

  bool pop(T *oElement)
  {
    auto lock = fSpinLock.acquire();
    if(fIsEmpty)
      return false;
 
    *oElement = *fSingleElement;
    fIsEmpty = true;
 
    return true;
  }
 

  void push(T const &iElement)
  {
    auto lock = fSpinLock.acquire();
    *fSingleElement = iElement;
    fIsEmpty = false;
  }

  void push(T const *iElement)
  {
    auto lock = fSpinLock.acquire();
    *fSingleElement = *iElement;
    fIsEmpty = false;
  }
 
private:
  std::unique_ptr<T> fSingleElement;
  bool fIsEmpty;
  mutable SpinLock fSpinLock;
};

template<typename T>
class AtomicValue
{
public:
  explicit AtomicValue(std::unique_ptr<T> iValue) : fValue{std::move(iValue)}, fSpinLock{} {}
 
  explicit AtomicValue(T const &iValue) : fValue{std::make_unique<T>(iValue)}, fSpinLock{} {}

  T get()
  {
    auto lock = fSpinLock.acquire();
    return *fValue;
  }

  void get(T &oElement)
  {
    auto lock = fSpinLock.acquire();
    oElement = *fValue;
  }

  void get(T *oElement)
  {
    auto lock = fSpinLock.acquire();
    *oElement = *fValue;
  }

  void set(T const &iValue)
  {
    auto lock = fSpinLock.acquire();
    *fValue = iValue;
  }

  void set(T const *iValue)
  {
    auto lock = fSpinLock.acquire();
    *fValue = *iValue;
  }
 
private:
  std::unique_ptr<T> fValue;
  SpinLock fSpinLock;
};
 
 
}
}
}
}
 
#endif // __PONGASOFT_UTILS_CONCURRENT_CONCURRENT_H__