16ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// Copyright 2010 the V8 project authors. All rights reserved. 2b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// Redistribution and use in source and binary forms, with or without 3b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// modification, are permitted provided that the following conditions are 4b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// met: 5b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 6b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// * Redistributions of source code must retain the above copyright 7b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// notice, this list of conditions and the following disclaimer. 8b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// * Redistributions in binary form must reproduce the above 9b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// copyright notice, this list of conditions and the following 10b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// disclaimer in the documentation and/or other materials provided 11b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// with the distribution. 12b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// * Neither the name of Google Inc. nor the names of its 13b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// contributors may be used to endorse or promote products derived 14b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// from this software without specific prior written permission. 15b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// 16b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 276ded16be15dd865a9b21ea304d5273c8be299c87Steve Block// 28f7060e27768c550ace7ec48ad8c093466db52dfaLeon Clarke// Tests of the circular queue. 296ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 30b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/v8.h" 31b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 32b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "src/circular-queue-inl.h" 33b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch#include "test/cctest/cctest.h" 346ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 356ded16be15dd865a9b21ea304d5273c8be299c87Steve Blockusing i::SamplingCircularQueue; 366ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 376ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 386ded16be15dd865a9b21ea304d5273c8be299c87Steve BlockTEST(SamplingCircularQueue) { 39b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch typedef v8::base::AtomicWord Record; 40b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch const int kMaxRecordsInQueue = 4; 41b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch SamplingCircularQueue<Record, kMaxRecordsInQueue> scq; 426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 436ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Check that we are using non-reserved values. 446ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Fill up the first chunk. 45b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(NULL, scq.Peek()); 46b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (Record i = 1; i < 1 + kMaxRecordsInQueue; ++i) { 47b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Record* rec = reinterpret_cast<Record*>(scq.StartEnqueue()); 486ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_NE(NULL, rec); 496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block *rec = i; 50b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch scq.FinishEnqueue(); 516ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 526ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 53b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // The queue is full, enqueue is not allowed. 54b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(NULL, scq.StartEnqueue()); 55b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 56b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Try to enqueue when the the queue is full. Consumption must be available. 57b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(NULL, scq.Peek()); 58b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (int i = 0; i < 10; ++i) { 59b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Record* rec = reinterpret_cast<Record*>(scq.StartEnqueue()); 60b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(NULL, rec); 61b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(NULL, scq.Peek()); 62b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch } 63b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 64b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Consume all records. 65b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (Record i = 1; i < 1 + kMaxRecordsInQueue; ++i) { 66b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Record* rec = reinterpret_cast<Record*>(scq.Peek()); 676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_NE(NULL, rec); 68b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(static_cast<int64_t>(i), static_cast<int64_t>(*rec)); 69b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(rec, reinterpret_cast<Record*>(scq.Peek())); 70b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch scq.Remove(); 71b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(rec, reinterpret_cast<Record*>(scq.Peek())); 726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 73b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // The queue is empty. 74b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(NULL, scq.Peek()); 756ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 766ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 77b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(NULL, scq.Peek()); 78b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (Record i = 0; i < kMaxRecordsInQueue / 2; ++i) { 79b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Record* rec = reinterpret_cast<Record*>(scq.StartEnqueue()); 806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_NE(NULL, rec); 81b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch *rec = i; 82b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch scq.FinishEnqueue(); 836ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 84b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 85b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // Consume all available kMaxRecordsInQueue / 2 records. 86b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(NULL, scq.Peek()); 87b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch for (Record i = 0; i < kMaxRecordsInQueue / 2; ++i) { 88b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Record* rec = reinterpret_cast<Record*>(scq.Peek()); 896ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_NE(NULL, rec); 906ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_EQ(static_cast<int64_t>(i), static_cast<int64_t>(*rec)); 91b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(rec, reinterpret_cast<Record*>(scq.Peek())); 92b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch scq.Remove(); 93b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(rec, reinterpret_cast<Record*>(scq.Peek())); 946ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 95b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch 96b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch // The queue is empty. 97b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(NULL, scq.Peek()); 986ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 996ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1006ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1016ded16be15dd865a9b21ea304d5273c8be299c87Steve Blocknamespace { 1026ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 103b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtypedef v8::base::AtomicWord Record; 104b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochtypedef SamplingCircularQueue<Record, 12> TestSampleQueue; 1056ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 106b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdochclass ProducerThread: public v8::base::Thread { 107b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch public: 108b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ProducerThread(TestSampleQueue* scq, int records_per_chunk, Record value, 109b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch v8::base::Semaphore* finished) 110b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch : Thread(Options("producer")), 11144f0eee88ff00398ff7f715fab053374d808c90dSteve Block scq_(scq), 1126ded16be15dd865a9b21ea304d5273c8be299c87Steve Block records_per_chunk_(records_per_chunk), 1136ded16be15dd865a9b21ea304d5273c8be299c87Steve Block value_(value), 114b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch finished_(finished) {} 1156ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1166ded16be15dd865a9b21ea304d5273c8be299c87Steve Block virtual void Run() { 1176ded16be15dd865a9b21ea304d5273c8be299c87Steve Block for (Record i = value_; i < value_ + records_per_chunk_; ++i) { 118b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Record* rec = reinterpret_cast<Record*>(scq_->StartEnqueue()); 1196ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_NE(NULL, rec); 1206ded16be15dd865a9b21ea304d5273c8be299c87Steve Block *rec = i; 121b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch scq_->FinishEnqueue(); 1226ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1236ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1246ded16be15dd865a9b21ea304d5273c8be299c87Steve Block finished_->Signal(); 1256ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1266ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1276ded16be15dd865a9b21ea304d5273c8be299c87Steve Block private: 128b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TestSampleQueue* scq_; 1296ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const int records_per_chunk_; 1306ded16be15dd865a9b21ea304d5273c8be299c87Steve Block Record value_; 131b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch v8::base::Semaphore* finished_; 1326ded16be15dd865a9b21ea304d5273c8be299c87Steve Block}; 1336ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1346ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} // namespace 1356ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1366ded16be15dd865a9b21ea304d5273c8be299c87Steve BlockTEST(SamplingCircularQueueMultithreading) { 1376ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // Emulate multiple VM threads working 'one thread at a time.' 1386ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // This test enqueues data from different threads. This corresponds 1396ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // to the case of profiling under Linux, where signal handler that 1406ded16be15dd865a9b21ea304d5273c8be299c87Steve Block // does sampling is called in the context of different VM threads. 1416ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 1426ded16be15dd865a9b21ea304d5273c8be299c87Steve Block const int kRecordsPerChunk = 4; 143b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch TestSampleQueue scq; 144b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch v8::base::Semaphore semaphore(0); 1456ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 146b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ProducerThread producer1(&scq, kRecordsPerChunk, 1, &semaphore); 147b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ProducerThread producer2(&scq, kRecordsPerChunk, 10, &semaphore); 148b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch ProducerThread producer3(&scq, kRecordsPerChunk, 20, &semaphore); 1496ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 150b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(NULL, scq.Peek()); 1516ded16be15dd865a9b21ea304d5273c8be299c87Steve Block producer1.Start(); 152b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch semaphore.Wait(); 1536ded16be15dd865a9b21ea304d5273c8be299c87Steve Block for (Record i = 1; i < 1 + kRecordsPerChunk; ++i) { 154b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Record* rec = reinterpret_cast<Record*>(scq.Peek()); 1556ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_NE(NULL, rec); 1566ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_EQ(static_cast<int64_t>(i), static_cast<int64_t>(*rec)); 157b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(rec, reinterpret_cast<Record*>(scq.Peek())); 158b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch scq.Remove(); 159b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(rec, reinterpret_cast<Record*>(scq.Peek())); 1606ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1616ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 162b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(NULL, scq.Peek()); 1636ded16be15dd865a9b21ea304d5273c8be299c87Steve Block producer2.Start(); 164b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch semaphore.Wait(); 1656ded16be15dd865a9b21ea304d5273c8be299c87Steve Block for (Record i = 10; i < 10 + kRecordsPerChunk; ++i) { 166b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Record* rec = reinterpret_cast<Record*>(scq.Peek()); 1676ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_NE(NULL, rec); 1686ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_EQ(static_cast<int64_t>(i), static_cast<int64_t>(*rec)); 169b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(rec, reinterpret_cast<Record*>(scq.Peek())); 170b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch scq.Remove(); 171b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(rec, reinterpret_cast<Record*>(scq.Peek())); 1726ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1736ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 174b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(NULL, scq.Peek()); 1756ded16be15dd865a9b21ea304d5273c8be299c87Steve Block producer3.Start(); 176b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch semaphore.Wait(); 1776ded16be15dd865a9b21ea304d5273c8be299c87Steve Block for (Record i = 20; i < 20 + kRecordsPerChunk; ++i) { 178b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch Record* rec = reinterpret_cast<Record*>(scq.Peek()); 1796ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_NE(NULL, rec); 1806ded16be15dd865a9b21ea304d5273c8be299c87Steve Block CHECK_EQ(static_cast<int64_t>(i), static_cast<int64_t>(*rec)); 181b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(rec, reinterpret_cast<Record*>(scq.Peek())); 182b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch scq.Remove(); 183b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_NE(rec, reinterpret_cast<Record*>(scq.Peek())); 1846ded16be15dd865a9b21ea304d5273c8be299c87Steve Block } 1856ded16be15dd865a9b21ea304d5273c8be299c87Steve Block 186b8a8cc1952d61a2f3a2568848933943a543b5d3eBen Murdoch CHECK_EQ(NULL, scq.Peek()); 1876ded16be15dd865a9b21ea304d5273c8be299c87Steve Block} 188