Update V8 to version 4.6.61.
[chromium-blink-merge.git] / content / renderer / devtools / lock_free_circular_queue.h
blobdfa780bb5e7bd44111da366c446c73ac3df37689
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.
5 #ifndef CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_
6 #define CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_
8 #include "base/atomicops.h"
9 #include "base/memory/aligned_memory.h"
11 #define CACHELINE_ALIGNED ALIGNAS(64)
13 namespace content {
15 MSVC_PUSH_DISABLE_WARNING(4324) // structure was padded due to align
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();
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();
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();
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);
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.
57 struct CACHELINE_ALIGNED Entry {
58 Entry() : marker(kEmpty) {}
59 T record;
60 base::subtle::Atomic32 marker;
63 Entry* Next(Entry* entry);
65 Entry buffer_[Length];
66 CACHELINE_ALIGNED Entry* enqueue_pos_;
67 CACHELINE_ALIGNED Entry* dequeue_pos_;
69 DISALLOW_COPY_AND_ASSIGN(LockFreeCircularQueue);
72 MSVC_POP_WARNING()
74 template <typename T, unsigned L>
75 LockFreeCircularQueue<T, L>::LockFreeCircularQueue()
76 : enqueue_pos_(buffer_), dequeue_pos_(buffer_) {
79 template <typename T, unsigned L>
80 LockFreeCircularQueue<T, L>::~LockFreeCircularQueue() {
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;
89 return nullptr;
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_);
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;
104 return nullptr;
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_);
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;
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));
128 template <typename T, unsigned L>
129 void LockFreeCircularQueue<T, L>::operator delete(void* ptr) {
130 base::AlignedFree(ptr);
133 } // namespace content
135 #endif // CONTENT_RENDERER_DEVTOOLS_LOCK_FREE_CIRCULAR_QUEUE_H_