Home | History | Annotate | Download | only in src 
      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_
    104