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// Tests of the circular queue.
29
30#include "src/v8.h"
31
32#include "src/circular-queue-inl.h"
33#include "test/cctest/cctest.h"
34
35using i::SamplingCircularQueue;
36
37
38TEST(SamplingCircularQueue) {
39  typedef v8::base::AtomicWord Record;
40  const int kMaxRecordsInQueue = 4;
41  SamplingCircularQueue<Record, kMaxRecordsInQueue> scq;
42
43  // Check that we are using non-reserved values.
44  // Fill up the first chunk.
45  CHECK_EQ(NULL, scq.Peek());
46  for (Record i = 1; i < 1 + kMaxRecordsInQueue; ++i) {
47    Record* rec = reinterpret_cast<Record*>(scq.StartEnqueue());
48    CHECK_NE(NULL, rec);
49    *rec = i;
50    scq.FinishEnqueue();
51  }
52
53  // The queue is full, enqueue is not allowed.
54  CHECK_EQ(NULL, scq.StartEnqueue());
55
56  // Try to enqueue when the the queue is full. Consumption must be available.
57  CHECK_NE(NULL, scq.Peek());
58  for (int i = 0; i < 10; ++i) {
59    Record* rec = reinterpret_cast<Record*>(scq.StartEnqueue());
60    CHECK_EQ(NULL, rec);
61    CHECK_NE(NULL, scq.Peek());
62  }
63
64  // Consume all records.
65  for (Record i = 1; i < 1 + kMaxRecordsInQueue; ++i) {
66    Record* rec = reinterpret_cast<Record*>(scq.Peek());
67    CHECK_NE(NULL, rec);
68    CHECK_EQ(static_cast<int64_t>(i), static_cast<int64_t>(*rec));
69    CHECK_EQ(rec, reinterpret_cast<Record*>(scq.Peek()));
70    scq.Remove();
71    CHECK_NE(rec, reinterpret_cast<Record*>(scq.Peek()));
72  }
73  // The queue is empty.
74  CHECK_EQ(NULL, scq.Peek());
75
76
77  CHECK_EQ(NULL, scq.Peek());
78  for (Record i = 0; i < kMaxRecordsInQueue / 2; ++i) {
79    Record* rec = reinterpret_cast<Record*>(scq.StartEnqueue());
80    CHECK_NE(NULL, rec);
81    *rec = i;
82    scq.FinishEnqueue();
83  }
84
85  // Consume all available kMaxRecordsInQueue / 2 records.
86  CHECK_NE(NULL, scq.Peek());
87  for (Record i = 0; i < kMaxRecordsInQueue / 2; ++i) {
88    Record* rec = reinterpret_cast<Record*>(scq.Peek());
89    CHECK_NE(NULL, rec);
90    CHECK_EQ(static_cast<int64_t>(i), static_cast<int64_t>(*rec));
91    CHECK_EQ(rec, reinterpret_cast<Record*>(scq.Peek()));
92    scq.Remove();
93    CHECK_NE(rec, reinterpret_cast<Record*>(scq.Peek()));
94  }
95
96  // The queue is empty.
97  CHECK_EQ(NULL, scq.Peek());
98}
99
100
101namespace {
102
103typedef v8::base::AtomicWord Record;
104typedef SamplingCircularQueue<Record, 12> TestSampleQueue;
105
106class ProducerThread: public v8::base::Thread {
107 public:
108  ProducerThread(TestSampleQueue* scq, int records_per_chunk, Record value,
109                 v8::base::Semaphore* finished)
110      : Thread(Options("producer")),
111        scq_(scq),
112        records_per_chunk_(records_per_chunk),
113        value_(value),
114        finished_(finished) {}
115
116  virtual void Run() {
117    for (Record i = value_; i < value_ + records_per_chunk_; ++i) {
118      Record* rec = reinterpret_cast<Record*>(scq_->StartEnqueue());
119      CHECK_NE(NULL, rec);
120      *rec = i;
121      scq_->FinishEnqueue();
122    }
123
124    finished_->Signal();
125  }
126
127 private:
128  TestSampleQueue* scq_;
129  const int records_per_chunk_;
130  Record value_;
131  v8::base::Semaphore* finished_;
132};
133
134}  // namespace
135
136TEST(SamplingCircularQueueMultithreading) {
137  // Emulate multiple VM threads working 'one thread at a time.'
138  // This test enqueues data from different threads. This corresponds
139  // to the case of profiling under Linux, where signal handler that
140  // does sampling is called in the context of different VM threads.
141
142  const int kRecordsPerChunk = 4;
143  TestSampleQueue scq;
144  v8::base::Semaphore semaphore(0);
145
146  ProducerThread producer1(&scq, kRecordsPerChunk, 1, &semaphore);
147  ProducerThread producer2(&scq, kRecordsPerChunk, 10, &semaphore);
148  ProducerThread producer3(&scq, kRecordsPerChunk, 20, &semaphore);
149
150  CHECK_EQ(NULL, scq.Peek());
151  producer1.Start();
152  semaphore.Wait();
153  for (Record i = 1; i < 1 + kRecordsPerChunk; ++i) {
154    Record* rec = reinterpret_cast<Record*>(scq.Peek());
155    CHECK_NE(NULL, rec);
156    CHECK_EQ(static_cast<int64_t>(i), static_cast<int64_t>(*rec));
157    CHECK_EQ(rec, reinterpret_cast<Record*>(scq.Peek()));
158    scq.Remove();
159    CHECK_NE(rec, reinterpret_cast<Record*>(scq.Peek()));
160  }
161
162  CHECK_EQ(NULL, scq.Peek());
163  producer2.Start();
164  semaphore.Wait();
165  for (Record i = 10; i < 10 + kRecordsPerChunk; ++i) {
166    Record* rec = reinterpret_cast<Record*>(scq.Peek());
167    CHECK_NE(NULL, rec);
168    CHECK_EQ(static_cast<int64_t>(i), static_cast<int64_t>(*rec));
169    CHECK_EQ(rec, reinterpret_cast<Record*>(scq.Peek()));
170    scq.Remove();
171    CHECK_NE(rec, reinterpret_cast<Record*>(scq.Peek()));
172  }
173
174  CHECK_EQ(NULL, scq.Peek());
175  producer3.Start();
176  semaphore.Wait();
177  for (Record i = 20; i < 20 + kRecordsPerChunk; ++i) {
178    Record* rec = reinterpret_cast<Record*>(scq.Peek());
179    CHECK_NE(NULL, rec);
180    CHECK_EQ(static_cast<int64_t>(i), static_cast<int64_t>(*rec));
181    CHECK_EQ(rec, reinterpret_cast<Record*>(scq.Peek()));
182    scq.Remove();
183    CHECK_NE(rec, reinterpret_cast<Record*>(scq.Peek()));
184  }
185
186  CHECK_EQ(NULL, scq.Peek());
187}
188