1cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org// Copyright 2010 the V8 project authors. All rights reserved. 23484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// Use of this source code is governed by a BSD-style license that can be 33484964a86451e86dcf04be9bd8c0d76ee04f081rossberg@chromium.org// found in the LICENSE file. 4cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 5cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org#ifndef V8_CIRCULAR_QUEUE_H_ 6cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org#define V8_CIRCULAR_QUEUE_H_ 7cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 81e2d50cf3d94ff48285da107b7a9da1ad0fc873dmachenbach@chromium.org#include "src/base/atomicops.h" 9196eb601290dc49c3754da728dc58700dff2de1bmachenbach@chromium.org#include "src/globals.h" 109259716434187c932704601f700375e53d865de8rossberg@chromium.org 11cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.orgnamespace v8 { 12cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.orgnamespace internal { 13cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 14cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 15cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org// Lock-free cache-friendly sampling circular queue for large 16cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org// records. Intended for fast transfer of large records between a 17cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org// single producer and a single consumer. If the queue is full, 189259716434187c932704601f700375e53d865de8rossberg@chromium.org// StartEnqueue will return NULL. The queue is designed with 19cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org// a goal in mind to evade cache lines thrashing by preventing 20cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org// simultaneous reads and writes to adjanced memory locations. 219259716434187c932704601f700375e53d865de8rossberg@chromium.orgtemplate<typename T, unsigned Length> 22cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.orgclass SamplingCircularQueue { 23cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org public: 24cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org // Executed on the application thread. 259259716434187c932704601f700375e53d865de8rossberg@chromium.org SamplingCircularQueue(); 26cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org ~SamplingCircularQueue(); 27cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 289259716434187c932704601f700375e53d865de8rossberg@chromium.org // StartEnqueue returns a pointer to a memory location for storing the next 299259716434187c932704601f700375e53d865de8rossberg@chromium.org // record or NULL if all entries are full at the moment. 309259716434187c932704601f700375e53d865de8rossberg@chromium.org T* StartEnqueue(); 319259716434187c932704601f700375e53d865de8rossberg@chromium.org // Notifies the queue that the producer has complete writing data into the 329259716434187c932704601f700375e53d865de8rossberg@chromium.org // memory returned by StartEnqueue and it can be passed to the consumer. 339259716434187c932704601f700375e53d865de8rossberg@chromium.org void FinishEnqueue(); 34cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 35cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org // Executed on the consumer (analyzer) thread. 362c9426bdda5e95459527292063d885c98180cb0fjkummerow@chromium.org // Retrieves, but does not remove, the head of this queue, returning NULL 372c9426bdda5e95459527292063d885c98180cb0fjkummerow@chromium.org // if this queue is empty. After the record had been read by a consumer, 382c9426bdda5e95459527292063d885c98180cb0fjkummerow@chromium.org // Remove must be called. 392c9426bdda5e95459527292063d885c98180cb0fjkummerow@chromium.org T* Peek(); 402c9426bdda5e95459527292063d885c98180cb0fjkummerow@chromium.org void Remove(); 41cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 42cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org private: 439259716434187c932704601f700375e53d865de8rossberg@chromium.org // Reserved values for the entry marker. 44ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org enum { 459259716434187c932704601f700375e53d865de8rossberg@chromium.org kEmpty, // Marks clean (processed) entries. 469259716434187c932704601f700375e53d865de8rossberg@chromium.org kFull // Marks entries already filled by the producer but not yet 479259716434187c932704601f700375e53d865de8rossberg@chromium.org // completely processed by the consumer. 48ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org }; 49ba72ec861b69b67139c93fc6dd56f4a73c9b3135jkummerow@chromium.org 501e8da746019f818a22dfdc6f691dbc0447048cadjkummerow@chromium.org struct V8_ALIGNED(PROCESSOR_CACHE_LINE_SIZE) Entry { 519259716434187c932704601f700375e53d865de8rossberg@chromium.org Entry() : marker(kEmpty) {} 529259716434187c932704601f700375e53d865de8rossberg@chromium.org T record; 531e2d50cf3d94ff48285da107b7a9da1ad0fc873dmachenbach@chromium.org base::Atomic32 marker; 54cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org }; 55cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 569259716434187c932704601f700375e53d865de8rossberg@chromium.org Entry* Next(Entry* entry); 57cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 589259716434187c932704601f700375e53d865de8rossberg@chromium.org Entry buffer_[Length]; 591e8da746019f818a22dfdc6f691dbc0447048cadjkummerow@chromium.org V8_ALIGNED(PROCESSOR_CACHE_LINE_SIZE) Entry* enqueue_pos_; 601e8da746019f818a22dfdc6f691dbc0447048cadjkummerow@chromium.org V8_ALIGNED(PROCESSOR_CACHE_LINE_SIZE) Entry* dequeue_pos_; 6125156ded31ef771a2d799ed902483d83b3ebcbdclrn@chromium.org 6225156ded31ef771a2d799ed902483d83b3ebcbdclrn@chromium.org DISALLOW_COPY_AND_ASSIGN(SamplingCircularQueue); 63cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org}; 64cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 65cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 66cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org} } // namespace v8::internal 67cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org 68cec079d8ed1f0920a0ea3dc9a3e81966013287c1whesse@chromium.org#endif // V8_CIRCULAR_QUEUE_H_ 69