v8  3.14.5(node0.10.28)
V8 is Google's open source JavaScript engine
 All Data Structures Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Pages
circular-queue.h
Go to the documentation of this file.
1 // Copyright 2010 the V8 project authors. All rights reserved.
2 // Redistribution and use in source and binary forms, with or without
3 // modification, are permitted provided that the following conditions are
4 // met:
5 //
6 // * Redistributions of source code must retain the above copyright
7 // notice, this list of conditions and the following disclaimer.
8 // * Redistributions in binary form must reproduce the above
9 // copyright notice, this list of conditions and the following
10 // disclaimer in the documentation and/or other materials provided
11 // with the distribution.
12 // * Neither the name of Google Inc. nor the names of its
13 // contributors may be used to endorse or promote products derived
14 // from this software without specific prior written permission.
15 //
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27 
28 #ifndef V8_CIRCULAR_QUEUE_H_
29 #define V8_CIRCULAR_QUEUE_H_
30 
31 namespace v8 {
32 namespace internal {
33 
34 
35 // Lock-free cache-friendly sampling circular queue for large
36 // records. Intended for fast transfer of large records between a
37 // single producer and a single consumer. If the queue is full,
38 // previous unread records are overwritten. The queue is designed with
39 // a goal in mind to evade cache lines thrashing by preventing
40 // simultaneous reads and writes to adjanced memory locations.
41 //
42 // IMPORTANT: as a producer never checks for chunks cleanness, it is
43 // possible that it can catch up and overwrite a chunk that a consumer
44 // is currently reading, resulting in a corrupt record being read.
46  public:
47  // Executed on the application thread.
48  SamplingCircularQueue(int record_size_in_bytes,
49  int desired_chunk_size_in_bytes,
50  int buffer_size_in_chunks);
52 
53  // Enqueue returns a pointer to a memory location for storing the next
54  // record.
55  INLINE(void* Enqueue());
56 
57  // Executed on the consumer (analyzer) thread.
58  // StartDequeue returns a pointer to a memory location for retrieving
59  // the next record. After the record had been read by a consumer,
60  // FinishDequeue must be called. Until that moment, subsequent calls
61  // to StartDequeue will return the same pointer.
62  void* StartDequeue();
63  void FinishDequeue();
64  // Due to a presence of slipping between the producer and the consumer,
65  // the queue must be notified whether producing has been finished in order
66  // to process remaining records from the buffer.
67  void FlushResidualRecords();
68 
69  typedef AtomicWord Cell;
70  // Reserved values for the first cell of a record.
71  static const Cell kClear = 0; // Marks clean (processed) chunks.
72  static const Cell kEnd = -1; // Marks the end of the buffer.
73 
74  private:
75  struct ProducerPosition {
76  Cell* enqueue_pos;
77  };
78  struct ConsumerPosition {
79  Cell* dequeue_chunk_pos;
80  Cell* dequeue_chunk_poll_pos;
81  Cell* dequeue_pos;
82  Cell* dequeue_end_pos;
83  };
84 
85  INLINE(void WrapPositionIfNeeded(Cell** pos));
86 
87  const int record_size_;
88  const int chunk_size_in_bytes_;
89  const int chunk_size_;
90  const int buffer_size_;
91  const int producer_consumer_distance_;
92  Cell* buffer_;
93  byte* positions_;
94  ProducerPosition* producer_pos_;
95  ConsumerPosition* consumer_pos_;
96 
97  DISALLOW_COPY_AND_ASSIGN(SamplingCircularQueue);
98 };
99 
100 
101 } } // namespace v8::internal
102 
103 #endif // V8_CIRCULAR_QUEUE_H_
SamplingCircularQueue(int record_size_in_bytes, int desired_chunk_size_in_bytes, int buffer_size_in_chunks)
uint8_t byte
Definition: globals.h:156
intptr_t AtomicWord
Definition: atomicops.h:75