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 46 using std::vector; 47 48 static 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 64 template <class Type> 65 void 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] 121 template <class Type> 122 void 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 163 int 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
