Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(52)

Unified Diff: src/circular-queue.h

Issue 1047002: Implement circular queues for the C++ version of CPU profiler. (Closed)
Patch Set: Comments addressed Created 10 years, 9 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
« no previous file with comments | « src/SConscript ('k') | src/circular-queue.cc » ('j') | no next file with comments »
Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
Index: src/circular-queue.h
diff --git a/src/circular-queue.h b/src/circular-queue.h
new file mode 100644
index 0000000000000000000000000000000000000000..11159e0388edc1d5fdfff922904d5b083a29dcd1
--- /dev/null
+++ b/src/circular-queue.h
@@ -0,0 +1,130 @@
+// Copyright 2010 the V8 project authors. All rights reserved.
+// Redistribution and use in source and binary forms, with or without
+// modification, are permitted provided that the following conditions are
+// met:
+//
+// * Redistributions of source code must retain the above copyright
+// notice, this list of conditions and the following disclaimer.
+// * Redistributions in binary form must reproduce the above
+// copyright notice, this list of conditions and the following
+// disclaimer in the documentation and/or other materials provided
+// with the distribution.
+// * Neither the name of Google Inc. nor the names of its
+// contributors may be used to endorse or promote products derived
+// from this software without specific prior written permission.
+//
+// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+
+#ifndef V8_CIRCULAR_QUEUE_H_
+#define V8_CIRCULAR_QUEUE_H_
+
+namespace v8 {
+namespace internal {
+
+
+// Lock-based blocking circular queue for small records. Intended for
+// transfer of small records between a single producer and a single
+// consumer. Blocks on enqueue operation if the queue is full.
+template<typename Record>
+class CircularQueue {
+ public:
+ inline explicit CircularQueue(int desired_buffer_size_in_bytes);
+ inline ~CircularQueue();
+
+ INLINE(void Dequeue(Record* rec));
+ INLINE(void Enqueue(const Record& rec));
+ INLINE(bool IsEmpty()) { return enqueue_pos_ == dequeue_pos_; }
+
+ private:
+ INLINE(Record* Next(Record* curr));
+
+ Record* buffer_;
+ Record* const buffer_end_;
+ Semaphore* enqueue_semaphore_;
+ Record* enqueue_pos_;
+ Record* dequeue_pos_;
+
+ DISALLOW_COPY_AND_ASSIGN(CircularQueue);
+};
+
+
+// Lock-free cache-friendly sampling circular queue for large
+// records. Intended for fast transfer of large records between a
+// single producer and a single consumer. If the queue is full,
+// previous unread records are overwritten. The queue is designed with
+// a goal in mind to evade cache lines thrashing by preventing
+// simultaneous reads and writes to adjanced memory locations.
+//
+// IMPORTANT: as a producer never checks for chunks cleanness, it is
+// possible that it can catch up and overwrite a chunk that a consumer
+// is currently reading, resulting in a corrupt record being read.
+class SamplingCircularQueue {
+ public:
+ // Executed on the application thread.
+ SamplingCircularQueue(int record_size_in_bytes,
+ int desired_chunk_size_in_bytes,
+ int buffer_size_in_chunks);
+ ~SamplingCircularQueue();
+
+ // Executed on the producer (sampler) or application thread.
+ void SetUpProducer();
+ // Enqueue returns a pointer to a memory location for storing the next
+ // record.
+ INLINE(void* Enqueue());
+ void TearDownProducer();
+
+ // Executed on the consumer (analyzer) thread.
+ void SetUpConsumer();
+ // StartDequeue returns a pointer to a memory location for retrieving
+ // the next record. After the record had been read by a consumer,
+ // FinishDequeue must be called. Until that moment, subsequent calls
+ // to StartDequeue will return the same pointer.
+ void* StartDequeue();
+ void FinishDequeue();
+ // Due to a presence of slipping between the producer and the consumer,
+ // the queue must be notified whether producing has been finished in order
+ // to process remaining records from the buffer.
+ void FlushResidualRecords();
+ void TearDownConsumer();
+
+ typedef AtomicWord Cell;
+ // Reserved values for the first cell of a record.
+ static const Cell kClear = 0; // Marks clean (processed) chunks.
+ static const Cell kEnd = -1; // Marks the end of the buffer.
+
+ private:
+ struct ConsumerPosition {
+ Cell* dequeue_chunk_pos;
+ Cell* dequeue_chunk_poll_pos;
+ Cell* dequeue_pos;
+ Cell* dequeue_end_pos;
+ };
+
+ INLINE(void WrapPositionIfNeeded(Cell** pos));
+
+ const int record_size_;
+ const int chunk_size_in_bytes_;
+ const int chunk_size_;
+ const int buffer_size_;
+ const int producer_consumer_distance_;
+ Cell* buffer_;
+ // Store producer and consumer data in TLS to avoid modifying the
+ // same CPU cache line from two threads simultaneously.
+ Thread::LocalStorageKey consumer_key_;
+ Thread::LocalStorageKey producer_key_;
+};
+
+
+} } // namespace v8::internal
+
+#endif // V8_CIRCULAR_QUEUE_H_
« no previous file with comments | « src/SConscript ('k') | src/circular-queue.cc » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698