whesse@chromium.org | cec079d | 2010-03-22 14:44:04 +0000 | [diff] [blame] | 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 | |
whesse@chromium.org | cec079d | 2010-03-22 14:44:04 +0000 | [diff] [blame] | 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 | |
whesse@chromium.org | cec079d | 2010-03-22 14:44:04 +0000 | [diff] [blame] | 53 | // Enqueue returns a pointer to a memory location for storing the next |
| 54 | // record. |
| 55 | INLINE(void* Enqueue()); |
whesse@chromium.org | cec079d | 2010-03-22 14:44:04 +0000 | [diff] [blame] | 56 | |
| 57 | // Executed on the consumer (analyzer) thread. |
whesse@chromium.org | cec079d | 2010-03-22 14:44:04 +0000 | [diff] [blame] | 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(); |
whesse@chromium.org | cec079d | 2010-03-22 14:44:04 +0000 | [diff] [blame] | 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: |
kmillikin@chromium.org | 5d8f0e6 | 2010-03-24 08:21:20 +0000 | [diff] [blame] | 75 | struct ProducerPosition { |
| 76 | Cell* enqueue_pos; |
| 77 | }; |
whesse@chromium.org | cec079d | 2010-03-22 14:44:04 +0000 | [diff] [blame] | 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_; |
kmillikin@chromium.org | 5d8f0e6 | 2010-03-24 08:21:20 +0000 | [diff] [blame] | 93 | byte* positions_; |
| 94 | ProducerPosition* producer_pos_; |
| 95 | ConsumerPosition* consumer_pos_; |
lrn@chromium.org | 25156de | 2010-04-06 13:10:27 +0000 | [diff] [blame] | 96 | |
| 97 | DISALLOW_COPY_AND_ASSIGN(SamplingCircularQueue); |
whesse@chromium.org | cec079d | 2010-03-22 14:44:04 +0000 | [diff] [blame] | 98 | }; |
| 99 | |
| 100 | |
| 101 | } } // namespace v8::internal |
| 102 | |
| 103 | #endif // V8_CIRCULAR_QUEUE_H_ |