| // Copyright 2015 The Chromium Authors. All rights reserved. |
| // Use of this source code is governed by a BSD-style license that can be |
| // found in the LICENSE file. |
| |
| #ifndef CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_ |
| #define CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_ |
| |
| #include <stddef.h> |
| |
| #include "base/atomicops.h" |
| #include "base/macros.h" |
| #include "base/memory/aligned_memory.h" |
| |
| #define CACHELINE_ALIGNED ALIGNAS(64) |
| |
| namespace content { |
| |
| MSVC_PUSH_DISABLE_WARNING(4324) // structure was padded due to align |
| |
| // Lock-free cache-friendly sampling circular queue for large |
| // records. Intended for fast transfer of large records between a |
| // single producer and a single consumer. If the queue is full, |
| // StartEnqueue will return nullptr. The queue is designed with |
| // a goal in mind to evade cache lines thrashing by preventing |
| // simultaneous reads and writes to adjanced memory locations. |
| template <typename T, unsigned Length> |
| class LockFreeCircularQueue { |
| public: |
| // Executed on the application thread. |
| LockFreeCircularQueue(); |
| ~LockFreeCircularQueue(); |
| |
| // StartEnqueue returns a pointer to a memory location for storing the next |
| // record or nullptr if all entries are full at the moment. |
| T* StartEnqueue(); |
| // Notifies the queue that the producer has complete writing data into the |
| // memory returned by StartEnqueue and it can be passed to the consumer. |
| void FinishEnqueue(); |
| |
| // Executed on the consumer (analyzer) thread. |
| // Retrieves, but does not remove, the head of this queue, returning nullptr |
| // if this queue is empty. After the record had been read by a consumer, |
| // Remove must be called. |
| T* Peek(); |
| void Remove(); |
| |
| // The class fields have stricter alignment requirements than a normal new |
| // can fulfil, so we need to provide our own new/delete here. |
| void* operator new(size_t size); |
| void operator delete(void* ptr); |
| |
| private: |
| // Reserved values for the entry marker. |
| enum { |
| kEmpty, // Marks clean (processed) entries. |
| kFull // Marks entries already filled by the producer but not yet |
| // completely processed by the consumer. |
| }; |
| |
| struct CACHELINE_ALIGNED Entry { |
| Entry() : marker(kEmpty) {} |
| T record; |
| base::subtle::Atomic32 marker; |
| }; |
| |
| Entry* Next(Entry* entry); |
| |
| Entry buffer_[Length]; |
| CACHELINE_ALIGNED Entry* enqueue_pos_; |
| CACHELINE_ALIGNED Entry* dequeue_pos_; |
| |
| DISALLOW_COPY_AND_ASSIGN(LockFreeCircularQueue); |
| }; |
| |
| MSVC_POP_WARNING() |
| |
| template <typename T, unsigned L> |
| LockFreeCircularQueue<T, L>::LockFreeCircularQueue() |
| : enqueue_pos_(buffer_), dequeue_pos_(buffer_) { |
| } |
| |
| template <typename T, unsigned L> |
| LockFreeCircularQueue<T, L>::~LockFreeCircularQueue() { |
| } |
| |
| template <typename T, unsigned L> |
| T* LockFreeCircularQueue<T, L>::Peek() { |
| base::subtle::MemoryBarrier(); |
| if (base::subtle::Acquire_Load(&dequeue_pos_->marker) == kFull) { |
| return &dequeue_pos_->record; |
| } |
| return nullptr; |
| } |
| |
| template <typename T, unsigned L> |
| void LockFreeCircularQueue<T, L>::Remove() { |
| base::subtle::Release_Store(&dequeue_pos_->marker, kEmpty); |
| dequeue_pos_ = Next(dequeue_pos_); |
| } |
| |
| template <typename T, unsigned L> |
| T* LockFreeCircularQueue<T, L>::StartEnqueue() { |
| base::subtle::MemoryBarrier(); |
| if (base::subtle::Acquire_Load(&enqueue_pos_->marker) == kEmpty) { |
| return &enqueue_pos_->record; |
| } |
| return nullptr; |
| } |
| |
| template <typename T, unsigned L> |
| void LockFreeCircularQueue<T, L>::FinishEnqueue() { |
| base::subtle::Release_Store(&enqueue_pos_->marker, kFull); |
| enqueue_pos_ = Next(enqueue_pos_); |
| } |
| |
| template <typename T, unsigned L> |
| typename LockFreeCircularQueue<T, L>::Entry* LockFreeCircularQueue<T, L>::Next( |
| Entry* entry) { |
| Entry* next = entry + 1; |
| if (next == &buffer_[L]) |
| return buffer_; |
| return next; |
| } |
| |
| template <typename T, unsigned L> |
| void* LockFreeCircularQueue<T, L>::operator new(size_t size) { |
| typedef LockFreeCircularQueue<T, L> QueueTypeAlias; |
| return base::AlignedAlloc(size, ALIGNOF(QueueTypeAlias)); |
| } |
| |
| template <typename T, unsigned L> |
| void LockFreeCircularQueue<T, L>::operator delete(void* ptr) { |
| base::AlignedFree(ptr); |
| } |
| |
| } // namespace content |
| |
| #endif // CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_ |