content/renderer/devtools/lock_free_circular_queue.h

   1 // Copyright 2015 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #ifndef CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_
   6 #define CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_
   7
   8 #include "base/atomicops.h"
   9 #include "base/memory/aligned_memory.h"
  10
  11 #define CACHELINE_ALIGNED ALIGNAS(64)
  12
  13 namespace content {
  14
  15 MSVC_PUSH_DISABLE_WARNING(4324)  // structure was padded due to align
  16
  17 // Lock-free cache-friendly sampling circular queue for large
  18 // records. Intended for fast transfer of large records between a
  19 // single producer and a single consumer. If the queue is full,
  20 // StartEnqueue will return nullptr. The queue is designed with
  21 // a goal in mind to evade cache lines thrashing by preventing
  22 // simultaneous reads and writes to adjanced memory locations.
  23 template <typename T, unsigned Length>
  24 class LockFreeCircularQueue {
  25  public:
  26   // Executed on the application thread.
  27   LockFreeCircularQueue();
  28   ~LockFreeCircularQueue();
  29
  30   // StartEnqueue returns a pointer to a memory location for storing the next
  31   // record or nullptr if all entries are full at the moment.
  32   T* StartEnqueue();
  33   // Notifies the queue that the producer has complete writing data into the
  34   // memory returned by StartEnqueue and it can be passed to the consumer.
  35   void FinishEnqueue();
  36
  37   // Executed on the consumer (analyzer) thread.
  38   // Retrieves, but does not remove, the head of this queue, returning nullptr
  39   // if this queue is empty. After the record had been read by a consumer,
  40   // Remove must be called.
  41   T* Peek();
  42   void Remove();
  43
  44   // The class fields have stricter alignment requirements than a normal new
  45   // can fulfil, so we need to provide our own new/delete here.
  46   void* operator new(size_t size);
  47   void operator delete(void* ptr);
  48
  49  private:
  50   // Reserved values for the entry marker.
  51   enum {
  52     kEmpty,  // Marks clean (processed) entries.
  53     kFull    // Marks entries already filled by the producer but not yet
  54              // completely processed by the consumer.
  55   };
  56
  57   struct CACHELINE_ALIGNED Entry {
  58     Entry() : marker(kEmpty) {}
  59     T record;
  60     base::subtle::Atomic32 marker;
  61   };
  62
  63   Entry* Next(Entry* entry);
  64
  65   Entry buffer_[Length];
  66   CACHELINE_ALIGNED Entry* enqueue_pos_;
  67   CACHELINE_ALIGNED Entry* dequeue_pos_;
  68
  69   DISALLOW_COPY_AND_ASSIGN(LockFreeCircularQueue);
  70 };
  71
  72 MSVC_POP_WARNING()
  73
  74 template <typename T, unsigned L>
  75 LockFreeCircularQueue<T, L>::LockFreeCircularQueue()
  76     : enqueue_pos_(buffer_), dequeue_pos_(buffer_) {
  77 }
  78
  79 template <typename T, unsigned L>
  80 LockFreeCircularQueue<T, L>::~LockFreeCircularQueue() {
  81 }
  82
  83 template <typename T, unsigned L>
  84 T* LockFreeCircularQueue<T, L>::Peek() {
  85   base::subtle::MemoryBarrier();
  86   if (base::subtle::Acquire_Load(&dequeue_pos_->marker) == kFull) {
  87     return &dequeue_pos_->record;
  88   }
  89   return nullptr;
  90 }
  91
  92 template <typename T, unsigned L>
  93 void LockFreeCircularQueue<T, L>::Remove() {
  94   base::subtle::Release_Store(&dequeue_pos_->marker, kEmpty);
  95   dequeue_pos_ = Next(dequeue_pos_);
  96 }
  97
  98 template <typename T, unsigned L>
  99 T* LockFreeCircularQueue<T, L>::StartEnqueue() {
 100   base::subtle::MemoryBarrier();
 101   if (base::subtle::Acquire_Load(&enqueue_pos_->marker) == kEmpty) {
 102     return &enqueue_pos_->record;
 103   }
 104   return nullptr;
 105 }
 106
 107 template <typename T, unsigned L>
 108 void LockFreeCircularQueue<T, L>::FinishEnqueue() {
 109   base::subtle::Release_Store(&enqueue_pos_->marker, kFull);
 110   enqueue_pos_ = Next(enqueue_pos_);
 111 }
 112
 113 template <typename T, unsigned L>
 114 typename LockFreeCircularQueue<T, L>::Entry* LockFreeCircularQueue<T, L>::Next(
 115     Entry* entry) {
 116   Entry* next = entry + 1;
 117   if (next == &buffer_[L])
 118     return buffer_;
 119   return next;
 120 }
 121
 122 template <typename T, unsigned L>
 123 void* LockFreeCircularQueue<T, L>::operator new(size_t size) {
 124   typedef LockFreeCircularQueue<T, L> QueueTypeAlias;
 125   return base::AlignedAlloc(size, ALIGNOF(QueueTypeAlias));
 126 }
 127
 128 template <typename T, unsigned L>
 129 void LockFreeCircularQueue<T, L>::operator delete(void* ptr) {
 130   base::AlignedFree(ptr);
 131 }
 132
 133 }  // namespace content
 134
 135 #endif  // CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_