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