16ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Copyright 2010 the V8 project authors. All rights reserved. 26ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Redistribution and use in source and binary forms, with or without 36ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// modification, are permitted provided that the following conditions are 46ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// met: 56ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 66ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// * Redistributions of source code must retain the above copyright 76ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// notice, this list of conditions and the following disclaimer. 86ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// * Redistributions in binary form must reproduce the above 96ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// copyright notice, this list of conditions and the following 106ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// disclaimer in the documentation and/or other materials provided 116ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// with the distribution. 126ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// * Neither the name of Google Inc. nor the names of its 136ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// contributors may be used to endorse or promote products derived 146ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// from this software without specific prior written permission. 156ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 166ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 176ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 186ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 196ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 206ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 216ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 226ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 236ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 246ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 256ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 266ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 276ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 286ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#ifndef V8_CIRCULAR_QUEUE_H_ 296ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#define V8_CIRCULAR_QUEUE_H_ 306ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 316ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace v8 { 326ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace internal { 336ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 346ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 356ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Lock-free cache-friendly sampling circular queue for large 366ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// records. Intended for fast transfer of large records between a 376ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// single producer and a single consumer. If the queue is full, 386ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// previous unread records are overwritten. The queue is designed with 396ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// a goal in mind to evade cache lines thrashing by preventing 406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// simultaneous reads and writes to adjanced memory locations. 416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// IMPORTANT: as a producer never checks for chunks cleanness, it is 436ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// possible that it can catch up and overwrite a chunk that a consumer 446ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// is currently reading, resulting in a corrupt record being read. 456ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockclass SamplingCircularQueue { 466ded16be15dd865a9b21ea304d5273c8be299c87Steve Block public: 476ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Executed on the application thread. 486ded16be15dd865a9b21ea304d5273c8be299c87Steve Block SamplingCircularQueue(int record_size_in_bytes, 496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block int desired_chunk_size_in_bytes, 506ded16be15dd865a9b21ea304d5273c8be299c87Steve Block int buffer_size_in_chunks); 516ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ~SamplingCircularQueue(); 526ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 536ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Enqueue returns a pointer to a memory location for storing the next 546ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // record. 556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block INLINE(void* Enqueue()); 566ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 576ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Executed on the consumer (analyzer) thread. 586ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // StartDequeue returns a pointer to a memory location for retrieving 596ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // the next record. After the record had been read by a consumer, 606ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // FinishDequeue must be called. Until that moment, subsequent calls 616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // to StartDequeue will return the same pointer. 626ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void* StartDequeue(); 636ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void FinishDequeue(); 646ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Due to a presence of slipping between the producer and the consumer, 656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // the queue must be notified whether producing has been finished in order 666ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // to process remaining records from the buffer. 676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block void FlushResidualRecords(); 686ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 696ded16be15dd865a9b21ea304d5273c8be299c87Steve Block typedef AtomicWord Cell; 706ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Reserved values for the first cell of a record. 716ded16be15dd865a9b21ea304d5273c8be299c87Steve Block static const Cell kClear = 0; // Marks clean (processed) chunks. 726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block static const Cell kEnd = -1; // Marks the end of the buffer. 736ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 746ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 756ded16be15dd865a9b21ea304d5273c8be299c87Steve Block struct ProducerPosition { 766ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Cell* enqueue_pos; 776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 786ded16be15dd865a9b21ea304d5273c8be299c87Steve Block struct ConsumerPosition { 796ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Cell* dequeue_chunk_pos; 806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Cell* dequeue_chunk_poll_pos; 816ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Cell* dequeue_pos; 826ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Cell* dequeue_end_pos; 836ded16be15dd865a9b21ea304d5273c8be299c87Steve Block }; 846ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 856ded16be15dd865a9b21ea304d5273c8be299c87Steve Block INLINE(void WrapPositionIfNeeded(Cell** pos)); 866ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 876ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const int record_size_; 886ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const int chunk_size_in_bytes_; 896ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const int chunk_size_; 906ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const int buffer_size_; 916ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const int producer_consumer_distance_; 926ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Cell* buffer_; 936ded16be15dd865a9b21ea304d5273c8be299c87Steve Block byte* positions_; 946ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ProducerPosition* producer_pos_; 956ded16be15dd865a9b21ea304d5273c8be299c87Steve Block ConsumerPosition* consumer_pos_; 966ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 976ded16be15dd865a9b21ea304d5273c8be299c87Steve Block DISALLOW_COPY_AND_ASSIGN(SamplingCircularQueue); 986ded16be15dd865a9b21ea304d5273c8be299c87Steve Block}; 996ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1006ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1016ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} } // namespace v8::internal 1026ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1036ded16be15dd865a9b21ea304d5273c8be299c87Steve Block#endif // V8_CIRCULAR_QUEUE_H_ 104