15c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)/* 2f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) * Copyright (C) 2013 Google Inc. All rights reserved. 35c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 45c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * Redistribution and use in source and binary forms, with or without 55c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * modification, are permitted provided that the following conditions 65c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * are met: 75c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 85c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 1. Redistributions of source code must retain the above copyright 95c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer. 105c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 2. Redistributions in binary form must reproduce the above copyright 115c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * notice, this list of conditions and the following disclaimer in the 125c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * documentation and/or other materials provided with the distribution. 135c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * 145c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 155c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 165c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 175c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 185c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 195c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 205c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 215c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 225c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 235c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 245c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) */ 255c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 265c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)#include "config.h" 271e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/PODFreeListArena.h" 285c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 291e202183a5dc46166763171984b285173f8585e5Torne (Richard Coles)#include "platform/testing/ArenaTestHelpers.h" 30591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/FastMalloc.h" 31591b958dee2cf159d33a0b931e6231072eaf38d5Ben Murdoch#include "wtf/RefPtr.h" 325c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 33f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)#include <gtest/gtest.h> 34f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) 35c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)namespace blink { 365c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 375c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)using ArenaTestHelpers::TrackedAllocator; 385c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 395c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)namespace { 405c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 415c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// A couple of simple structs to allocate. 425c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct TestClass1 { 435c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TestClass1() 445c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) : x(0), y(0), z(0), w(1) { } 455c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 465c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) float x, y, z, w; 475c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 485c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 495c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)struct TestClass2 { 505c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) TestClass2() 51f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) : padding(0) 52f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) { 53f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) static int TestIds = 0; 54f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) id = TestIds++; 55f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) } 56f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) int id; 57f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) int padding; 585c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 595c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 605c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} // anonymous namespace 615c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 62f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)class PODFreeListArenaTest : public testing::Test { 63f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)protected: 64f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) int getFreeListSize(const PassRefPtr<PODFreeListArena<TestClass1> > arena) const 65f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) { 66f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) return arena->getFreeListSizeForTesting(); 67f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) } 685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)}; 695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 705c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Make sure the arena can successfully allocate from more than one 715c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// region. 72f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)TEST_F(PODFreeListArenaTest, CanAllocateFromMoreThanOneRegion) 735c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 745c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) RefPtr<TrackedAllocator> allocator = TrackedAllocator::create(); 75f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) RefPtr<PODFreeListArena<TestClass1> > arena = PODFreeListArena<TestClass1>::create(allocator); 765c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) int numIterations = 10 * PODArena::DefaultChunkSize / sizeof(TestClass1); 775c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < numIterations; ++i) 78f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) arena->allocateObject(); 795c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_GT(allocator->numRegions(), 1); 805c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 815c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 825c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Make sure the arena frees all allocated regions during destruction. 83f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)TEST_F(PODFreeListArenaTest, FreesAllAllocatedRegions) 845c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 855c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) RefPtr<TrackedAllocator> allocator = TrackedAllocator::create(); 865c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) { 87f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) RefPtr<PODFreeListArena<TestClass1> > arena = PODFreeListArena<TestClass1>::create(allocator); 885c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < 3; i++) 89f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) arena->allocateObject(); 905c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_GT(allocator->numRegions(), 0); 915c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 925c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_TRUE(allocator->isEmpty()); 935c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 945c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 955c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)// Make sure the arena runs constructors of the objects allocated within. 96bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)TEST_F(PODFreeListArenaTest, RunsConstructorsOnNewObjects) 975c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles){ 98f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) RefPtr<PODFreeListArena<TestClass1> > arena = PODFreeListArena<TestClass1>::create(); 995c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) for (int i = 0; i < 10000; i++) { 100f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) TestClass1* tc1 = arena->allocateObject(); 1015c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(0, tc1->x); 1025c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(0, tc1->y); 1035c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(0, tc1->z); 1045c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) EXPECT_EQ(1, tc1->w); 105f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) } 106f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)} 107f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) 108bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)// Make sure the arena runs constructors of the objects allocated within. 109bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)TEST_F(PODFreeListArenaTest, RunsConstructorsOnReusedObjects) 110bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles){ 111bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) std::set<TestClass1*> objects; 112bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) RefPtr<PODFreeListArena<TestClass1> > arena = PODFreeListArena<TestClass1>::create(); 113bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) for (int i = 0; i < 100; i++) { 114bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) TestClass1* tc1 = arena->allocateObject(); 115bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) tc1->x = 100; 116bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) tc1->y = 101; 117bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) tc1->z = 102; 118bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) tc1->w = 103; 119bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 120bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) objects.insert(tc1); 121bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) } 122bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) for (std::set<TestClass1*>::iterator it = objects.begin(); it != objects.end(); ++it) { 123bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) arena->freeObject(*it); 124bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) } 125bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) for (int i = 0; i < 100; i++) { 126bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) TestClass1* cur = arena->allocateObject(); 127bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) EXPECT_TRUE(objects.find(cur) != objects.end()); 128bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) EXPECT_EQ(0, cur->x); 129bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) EXPECT_EQ(0, cur->y); 130bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) EXPECT_EQ(0, cur->z); 131bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) EXPECT_EQ(1, cur->w); 132bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 133bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) objects.erase(cur); 134bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) } 135bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles)} 136bfe3590b1806e3ff18f46ee3af5d4b83078f305aTorne (Richard Coles) 137f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)// Make sure freeObject puts the object in the free list. 138f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)TEST_F(PODFreeListArenaTest, AddsFreedObjectsToFreedList) 139f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles){ 140f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) std::vector<TestClass1*> objects; 141f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) RefPtr<PODFreeListArena<TestClass1> > arena = PODFreeListArena<TestClass1>::create(); 142f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) for (int i = 0; i < 100; i++) { 143f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) objects.push_back(arena->allocateObject()); 144f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) } 145f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) for (std::vector<TestClass1*>::iterator it = objects.begin(); it != objects.end(); ++it) { 146f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) arena->freeObject(*it); 147f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) } 148f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) EXPECT_EQ(100, getFreeListSize(arena)); 149f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)} 150f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) 151f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)// Make sure allocations use previously freed memory. 152f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles)TEST_F(PODFreeListArenaTest, ReusesPreviouslyFreedObjects) 153f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles){ 154f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) std::set<TestClass2*> objects; 155f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) RefPtr<PODFreeListArena<TestClass2> > arena = PODFreeListArena<TestClass2>::create(); 156f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) for (int i = 0; i < 100; i++) { 157f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) objects.insert(arena->allocateObject()); 158f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) } 159f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) for (std::set<TestClass2*>::iterator it = objects.begin(); it != objects.end(); ++it) { 160f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) arena->freeObject(*it); 161f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) } 162f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) for (int i = 0; i < 100; i++) { 163f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) TestClass2* cur = arena->allocateObject(); 164f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) EXPECT_TRUE(objects.find(cur) != objects.end()); 165f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) EXPECT_TRUE(cur->id >= 100 && cur->id < 200); 166f5e4ad553afbc08dd2e729bb77e937a9a94d5827Torne (Richard Coles) objects.erase(cur); 1675c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) } 1685c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles)} 1695c87bf8b86a7c82ef50fb7a89697d8e02e2553beTorne (Richard Coles) 170c1847b1379d12d0e05df27436bf19a9b1bf12deaTorne (Richard Coles)} // namespace blink 171