src/3rdparty/v8/src/circular-queue.h

   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.
  45 class SamplingCircularQueue {
  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);
  51   ~SamplingCircularQueue();
  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_