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)
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
{
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.
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.
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.
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
);
50 // Reserved values for the entry marker.
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
) {}
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
);
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
;
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
;
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(
116 Entry
* next
= entry
+ 1;
117 if (next
== &buffer_
[L
])
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_