1  // Copyright 2018 Citra Emulator Project
  2  // Licensed under GPLv2 or any later version
  3  // Refer to the license.txt file included.
  4  
  5  #pragma once
  6  
  7  #include <algorithm>
  8  #include <array>
  9  #include <atomic>
 10  #include <cstddef>
 11  #include <cstring>
 12  #include <limits>
 13  #include <new>
 14  #include <span>
 15  #include <type_traits>
 16  #include <vector>
 17  #include "common/common_types.h"
 18  
 19  namespace Common {
 20  
 21  /// SPSC ring buffer
 22  /// @tparam T            Element type
 23  /// @tparam capacity     Number of slots in ring buffer
 24  /// @tparam granularity  Slot size in terms of number of elements
 25  template <typename T, std::size_t capacity, std::size_t granularity = 1>
 26  class RingBuffer {
 27      /// A "slot" is made of `granularity` elements of `T`.
 28      static constexpr std::size_t slot_size = granularity * sizeof(T);
 29      // T must be safely memcpy-able and have a trivial default constructor.
 30      static_assert(std::is_trivial_v<T>);
 31      // Ensure capacity is sensible.
 32      static_assert(capacity < std::numeric_limits<std::size_t>::max() / 2 / granularity);
 33      static_assert((capacity & (capacity - 1)) == 0, "capacity must be a power of two");
 34      // Ensure lock-free.
 35      static_assert(std::atomic_size_t::is_always_lock_free);
 36  
 37  public:
 38      /// Pushes slots into the ring buffer
 39      /// @param new_slots   Pointer to the slots to push
 40      /// @param slot_count  Number of slots to push
 41      /// @returns The number of slots actually pushed
 42      std::size_t Push(const void* new_slots, std::size_t slot_count) {
 43          const std::size_t write_index = m_write_index.load();
 44          const std::size_t slots_free = capacity + m_read_index.load() - write_index;
 45          const std::size_t push_count = std::min(slot_count, slots_free);
 46  
 47          const std::size_t pos = write_index % capacity;
 48          const std::size_t first_copy = std::min(capacity - pos, push_count);
 49          const std::size_t second_copy = push_count - first_copy;
 50  
 51          const char* in = static_cast<const char*>(new_slots);
 52          std::memcpy(m_data.data() + pos * granularity, in, first_copy * slot_size);
 53          in += first_copy * slot_size;
 54          std::memcpy(m_data.data(), in, second_copy * slot_size);
 55  
 56          m_write_index.store(write_index + push_count);
 57  
 58          return push_count;
 59      }
 60  
 61      std::size_t Push(std::span<const T> input) {
 62          return Push(input.data(), input.size() / granularity);
 63      }
 64  
 65      /// Pops slots from the ring buffer
 66      /// @param output     Where to store the popped slots
 67      /// @param max_slots  Maximum number of slots to pop
 68      /// @returns The number of slots actually popped
 69      std::size_t Pop(void* output, std::size_t max_slots = ~std::size_t(0)) {
 70          const std::size_t read_index = m_read_index.load();
 71          const std::size_t slots_filled = m_write_index.load() - read_index;
 72          const std::size_t pop_count = std::min(slots_filled, max_slots);
 73  
 74          const std::size_t pos = read_index % capacity;
 75          const std::size_t first_copy = std::min(capacity - pos, pop_count);
 76          const std::size_t second_copy = pop_count - first_copy;
 77  
 78          char* out = static_cast<char*>(output);
 79          std::memcpy(out, m_data.data() + pos * granularity, first_copy * slot_size);
 80          out += first_copy * slot_size;
 81          std::memcpy(out, m_data.data(), second_copy * slot_size);
 82  
 83          m_read_index.store(read_index + pop_count);
 84  
 85          return pop_count;
 86      }
 87  
 88      std::vector<T> Pop(std::size_t max_slots = ~std::size_t(0)) {
 89          std::vector<T> out(std::min(max_slots, capacity) * granularity);
 90          const std::size_t count = Pop(out.data(), out.size() / granularity);
 91          out.resize(count * granularity);
 92          return out;
 93      }
 94  
 95      /// @returns Number of slots used
 96      [[nodiscard]] std::size_t Size() const {
 97          return m_write_index.load() - m_read_index.load();
 98      }
 99  
100      /// @returns Maximum size of ring buffer
101      [[nodiscard]] constexpr std::size_t Capacity() const {
102          return capacity;
103      }
104  
105  private:
106      // It is important to separate the below atomics for performance reasons:
107      // Having them on the same cache-line would result in false-sharing between them.
108  #ifdef __cpp_lib_hardware_interference_size
109      static constexpr std::size_t padding_size =
110          std::hardware_destructive_interference_size - sizeof(std::atomic_size_t);
111  #else
112      static constexpr std::size_t padding_size = 128 - sizeof(std::atomic_size_t);
113  #endif
114  
115      std::atomic_size_t m_read_index{0};
116      char padding1[padding_size];
117  
118      std::atomic_size_t m_write_index{0};
119      char padding2[padding_size];
120  
121      std::array<T, granularity * capacity> m_data;
122  };
123  
124  } // namespace Common