1 // Copyright (c) 2004, 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 // Test realloc() functionality 34 35 #include "config_for_unittests.h" 36 #include <assert.h> // for assert 37 #include <stdio.h> 38 #include <stddef.h> // for size_t, NULL 39 #include <stdlib.h> // for free, malloc, realloc 40 #include <algorithm> // for min 41 #include "base/logging.h" 42 43 using std::min; 44 45 46 // Fill a buffer of the specified size with a predetermined pattern 47 static void Fill(unsigned char* buffer, int n) { 48 for (int i = 0; i < n; i++) { 49 buffer[i] = (i & 0xff); 50 } 51 } 52 53 // Check that the specified buffer has the predetermined pattern 54 // generated by Fill() 55 static bool Valid(unsigned char* buffer, int n) { 56 for (int i = 0; i < n; i++) { 57 if (buffer[i] != (i & 0xff)) { 58 return false; 59 } 60 } 61 return true; 62 } 63 64 // Return the next interesting size/delta to check. Returns -1 if no more. 65 static int NextSize(int size) { 66 if (size < 100) { 67 return size+1; 68 } else if (size < 100000) { 69 // Find next power of two 70 int power = 1; 71 while (power < size) { 72 power <<= 1; 73 } 74 75 // Yield (power-1, power, power+1) 76 if (size < power-1) { 77 return power-1; 78 } else if (size == power-1) { 79 return power; 80 } else { 81 assert(size == power); 82 return power+1; 83 } 84 } else { 85 return -1; 86 } 87 } 88 89 int main(int argc, char** argv) { 90 for (int src_size = 0; src_size >= 0; src_size = NextSize(src_size)) { 91 for (int dst_size = 0; dst_size >= 0; dst_size = NextSize(dst_size)) { 92 unsigned char* src = (unsigned char*) malloc(src_size); 93 Fill(src, src_size); 94 unsigned char* dst = (unsigned char*) realloc(src, dst_size); 95 CHECK(Valid(dst, min(src_size, dst_size))); 96 Fill(dst, dst_size); 97 CHECK(Valid(dst, dst_size)); 98 if (dst != NULL) free(dst); 99 } 100 } 101 102 // Now make sure realloc works correctly even when we overflow the 103 // packed cache, so some entries are evicted from the cache. 104 // The cache has 2^12 entries, keyed by page number. 105 const int kNumEntries = 1 << 14; 106 int** p = (int**)malloc(sizeof(*p) * kNumEntries); 107 int sum = 0; 108 for (int i = 0; i < kNumEntries; i++) { 109 p[i] = (int*)malloc(8192); // no page size is likely to be bigger 110 p[i][1000] = i; // use memory deep in the heart of p 111 } 112 for (int i = 0; i < kNumEntries; i++) { 113 p[i] = (int*)realloc(p[i], 9000); 114 } 115 for (int i = 0; i < kNumEntries; i++) { 116 sum += p[i][1000]; 117 free(p[i]); 118 } 119 CHECK_EQ(kNumEntries/2 * (kNumEntries - 1), sum); // assume kNE is even 120 free(p); 121 122 printf("PASS\n"); 123 return 0; 124 } 125