16ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Copyright 2010 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Use of this source code is governed by a BSD-style license that can be 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// found in the LICENSE file. 46ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 56ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#ifndef V8_CIRCULAR_QUEUE_H_ 66ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#define V8_CIRCULAR_QUEUE_H_ 76ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/base/atomicops.h" 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/globals.h" 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 116ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace v8 { 126ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace internal { 136ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 146ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 156ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Lock-free cache-friendly sampling circular queue for large 166ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// records. Intended for fast transfer of large records between a 176ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// single producer and a single consumer. If the queue is full, 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// StartEnqueue will return NULL. The queue is designed with 196ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// a goal in mind to evade cache lines thrashing by preventing 206ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// simultaneous reads and writes to adjanced memory locations. 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtemplate<typename T, unsigned Length> 226ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockclass SamplingCircularQueue { 236ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 246ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Executed on the application thread. 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SamplingCircularQueue(); 266ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ~SamplingCircularQueue(); 276ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 28b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // StartEnqueue returns a pointer to a memory location for storing the next 29b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // record or NULL if all entries are full at the moment. 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T* StartEnqueue(); 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Notifies the queue that the producer has complete writing data into the 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // memory returned by StartEnqueue and it can be passed to the consumer. 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void FinishEnqueue(); 346ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 356ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Executed on the consumer (analyzer) thread. 36b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Retrieves, but does not remove, the head of this queue, returning NULL 37b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // if this queue is empty. After the record had been read by a consumer, 38b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Remove must be called. 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T* Peek(); 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch void Remove(); 416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 43b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Reserved values for the entry marker. 44b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch enum { 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch kEmpty, // Marks clean (processed) entries. 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch kFull // Marks entries already filled by the producer but not yet 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // completely processed by the consumer. 486ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 49b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch struct V8_ALIGNED(PROCESSOR_CACHE_LINE_SIZE) Entry { 51b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Entry() : marker(kEmpty) {} 52b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch T record; 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch base::Atomic32 marker; 546ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Entry* Next(Entry* entry); 576ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Entry buffer_[Length]; 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch V8_ALIGNED(PROCESSOR_CACHE_LINE_SIZE) Entry* enqueue_pos_; 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch V8_ALIGNED(PROCESSOR_CACHE_LINE_SIZE) Entry* dequeue_pos_; 616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block DISALLOW_COPY_AND_ASSIGN(SamplingCircularQueue); 636ded16be15dd865a9b21ea304d5273c8be299c87Steve Block}; 646ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} } // namespace v8::internal 676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 686ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#endif // V8_CIRCULAR_QUEUE_H_ 69