1// Copyright (c) 2003, Google Inc. 2// All rights reserved. 3// 4// Redistribution and use in source and binary forms, with or without 5// modification, are permitted provided that the following conditions are 6// met: 7// 8// * Redistributions of source code must retain the above copyright 9// notice, this list of conditions and the following disclaimer. 10// * Redistributions in binary form must reproduce the above 11// copyright notice, this list of conditions and the following disclaimer 12// in the documentation and/or other materials provided with the 13// distribution. 14// * Neither the name of Google Inc. nor the names of its 15// contributors may be used to endorse or promote products derived from 16// this software without specific prior written permission. 17// 18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 29 30// --- 31// Author: Sanjay Ghemawat 32 33#include "config_for_unittests.h" 34#include <stdio.h> 35#include <stdlib.h> 36#if defined HAVE_STDINT_H 37#include <stdint.h> // to get intptr_t 38#elif defined HAVE_INTTYPES_H 39#include <inttypes.h> // another place intptr_t might be defined 40#endif 41#include <sys/types.h> 42#include <vector> 43#include "base/logging.h" 44#include "pagemap.h" 45 46using std::vector; 47 48static void Permute(vector<intptr_t>* elements) { 49 if (elements->empty()) 50 return; 51 const size_t num_elements = elements->size(); 52 for (size_t i = num_elements - 1; i > 0; --i) { 53 const size_t newpos = rand() % (i + 1); 54 const intptr_t tmp = (*elements)[i]; // swap 55 (*elements)[i] = (*elements)[newpos]; 56 (*elements)[newpos] = tmp; 57 } 58} 59 60// Note: we leak memory every time a map is constructed, so do not 61// create too many maps. 62 63// Test specified map type 64template <class Type> 65void TestMap(int limit, bool limit_is_below_the_overflow_boundary) { 66 RAW_LOG(INFO, "Running test with %d iterations...\n", limit); 67 68 { // Test sequential ensure/assignment 69 Type map(malloc); 70 for (intptr_t i = 0; i < static_cast<intptr_t>(limit); i++) { 71 map.Ensure(i, 1); 72 map.set(i, (void*)(i+1)); 73 CHECK_EQ(map.get(i), (void*)(i+1)); 74 } 75 for (intptr_t i = 0; i < static_cast<intptr_t>(limit); i++) { 76 CHECK_EQ(map.get(i), (void*)(i+1)); 77 } 78 } 79 80 { // Test bulk Ensure 81 Type map(malloc); 82 map.Ensure(0, limit); 83 for (intptr_t i = 0; i < static_cast<intptr_t>(limit); i++) { 84 map.set(i, (void*)(i+1)); 85 CHECK_EQ(map.get(i), (void*)(i+1)); 86 } 87 for (intptr_t i = 0; i < static_cast<intptr_t>(limit); i++) { 88 CHECK_EQ(map.get(i), (void*)(i+1)); 89 } 90 } 91 92 // Test that we correctly notice overflow 93 { 94 Type map(malloc); 95 CHECK_EQ(map.Ensure(limit, limit+1), limit_is_below_the_overflow_boundary); 96 } 97 98 { // Test randomized accesses 99 srand(301); // srand isn't great, but it's portable 100 vector<intptr_t> elements; 101 for (intptr_t i = 0; i < static_cast<intptr_t>(limit); i++) elements.push_back(i); 102 Permute(&elements); 103 104 Type map(malloc); 105 for (intptr_t i = 0; i < static_cast<intptr_t>(limit); i++) { 106 map.Ensure(elements[i], 1); 107 map.set(elements[i], (void*)(elements[i]+1)); 108 CHECK_EQ(map.get(elements[i]), (void*)(elements[i]+1)); 109 } 110 for (intptr_t i = 0; i < static_cast<intptr_t>(limit); i++) { 111 CHECK_EQ(map.get(i), (void*)(i+1)); 112 } 113 } 114} 115 116// REQUIRES: BITS==10, i.e., valid range is [0,1023]. 117// Representations for different types will end up being: 118// PageMap1: array[1024] 119// PageMap2: array[32][32] 120// PageMap3: array[16][16][4] 121template <class Type> 122void TestNext(const char* name) { 123 RAW_LOG(ERROR, "Running NextTest %s\n", name); 124 Type map(malloc); 125 char a, b, c, d, e; 126 127 // When map is empty 128 CHECK(map.Next(0) == NULL); 129 CHECK(map.Next(5) == NULL); 130 CHECK(map.Next(1<<30) == NULL); 131 132 // Add a single value 133 map.Ensure(40, 1); 134 map.set(40, &a); 135 CHECK(map.Next(0) == &a); 136 CHECK(map.Next(39) == &a); 137 CHECK(map.Next(40) == &a); 138 CHECK(map.Next(41) == NULL); 139 CHECK(map.Next(1<<30) == NULL); 140 141 // Add a few values 142 map.Ensure(41, 1); 143 map.Ensure(100, 3); 144 map.set(41, &b); 145 map.set(100, &c); 146 map.set(101, &d); 147 map.set(102, &e); 148 CHECK(map.Next(0) == &a); 149 CHECK(map.Next(39) == &a); 150 CHECK(map.Next(40) == &a); 151 CHECK(map.Next(41) == &b); 152 CHECK(map.Next(42) == &c); 153 CHECK(map.Next(63) == &c); 154 CHECK(map.Next(64) == &c); 155 CHECK(map.Next(65) == &c); 156 CHECK(map.Next(99) == &c); 157 CHECK(map.Next(100) == &c); 158 CHECK(map.Next(101) == &d); 159 CHECK(map.Next(102) == &e); 160 CHECK(map.Next(103) == NULL); 161} 162 163int main(int argc, char** argv) { 164 TestMap< TCMalloc_PageMap1<10> > (100, true); 165 TestMap< TCMalloc_PageMap1<10> > (1 << 10, false); 166 TestMap< TCMalloc_PageMap2<20> > (100, true); 167 TestMap< TCMalloc_PageMap2<20> > (1 << 20, false); 168 TestMap< TCMalloc_PageMap3<20> > (100, true); 169 TestMap< TCMalloc_PageMap3<20> > (1 << 20, false); 170 171 TestNext< TCMalloc_PageMap1<10> >("PageMap1"); 172 TestNext< TCMalloc_PageMap2<10> >("PageMap2"); 173 TestNext< TCMalloc_PageMap3<10> >("PageMap3"); 174 175 printf("PASS\n"); 176 return 0; 177} 178