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 43using std::min; 44 45 46// Fill a buffer of the specified size with a predetermined pattern 47static 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() 55static 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. 65static 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 89int 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