base/allocator/allocator_unittest.cc

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include <stdio.h>
   6 #include <stdlib.h>
   7 #include <algorithm>   // for min()
   8
   9 #include "base/macros.h"
  10 #include "testing/gtest/include/gtest/gtest.h"
  11
  12 // Number of bits in a size_t.
  13 static const int kSizeBits = 8 * sizeof(size_t);
  14 // The maximum size of a size_t.
  15 static const size_t kMaxSize = ~static_cast<size_t>(0);
  16 // Maximum positive size of a size_t if it were signed.
  17 static const size_t kMaxSignedSize = ((size_t(1) << (kSizeBits-1)) - 1);
  18
  19 namespace {
  20
  21 using std::min;
  22
  23 // Fill a buffer of the specified size with a predetermined pattern
  24 static void Fill(unsigned char* buffer, int n) {
  25   for (int i = 0; i < n; i++) {
  26     buffer[i] = (i & 0xff);
  27   }
  28 }
  29
  30 // Check that the specified buffer has the predetermined pattern
  31 // generated by Fill()
  32 static bool Valid(unsigned char* buffer, int n) {
  33   for (int i = 0; i < n; i++) {
  34     if (buffer[i] != (i & 0xff)) {
  35       return false;
  36     }
  37   }
  38   return true;
  39 }
  40
  41 // Check that a buffer is completely zeroed.
  42 static bool IsZeroed(unsigned char* buffer, int n) {
  43   for (int i = 0; i < n; i++) {
  44     if (buffer[i] != 0) {
  45       return false;
  46     }
  47   }
  48   return true;
  49 }
  50
  51 // Check alignment
  52 static void CheckAlignment(void* p, int align) {
  53   EXPECT_EQ(0, reinterpret_cast<uintptr_t>(p) & (align-1));
  54 }
  55
  56 // Return the next interesting size/delta to check.  Returns -1 if no more.
  57 static int NextSize(int size) {
  58   if (size < 100)
  59     return size+1;
  60
  61   if (size < 100000) {
  62     // Find next power of two
  63     int power = 1;
  64     while (power < size)
  65       power <<= 1;
  66
  67     // Yield (power-1, power, power+1)
  68     if (size < power-1)
  69       return power-1;
  70
  71     if (size == power-1)
  72       return power;
  73
  74     assert(size == power);
  75     return power+1;
  76   } else {
  77     return -1;
  78   }
  79 }
  80
  81 static void TestCalloc(size_t n, size_t s, bool ok) {
  82   char* p = reinterpret_cast<char*>(calloc(n, s));
  83   if (!ok) {
  84     EXPECT_EQ(NULL, p) << "calloc(n, s) should not succeed";
  85   } else {
  86     EXPECT_NE(reinterpret_cast<void*>(NULL), p) <<
  87         "calloc(n, s) should succeed";
  88     for (size_t i = 0; i < n*s; i++) {
  89       EXPECT_EQ('\0', p[i]);
  90     }
  91     free(p);
  92   }
  93 }
  94
  95 }  // namespace
  96
  97 //-----------------------------------------------------------------------------
  98
  99
 100 TEST(Allocators, Malloc) {
 101   // Try allocating data with a bunch of alignments and sizes
 102   for (int size = 1; size < 1048576; size *= 2) {
 103     unsigned char* ptr = reinterpret_cast<unsigned char*>(malloc(size));
 104     CheckAlignment(ptr, 2);  // Should be 2 byte aligned
 105     Fill(ptr, size);
 106     EXPECT_TRUE(Valid(ptr, size));
 107     free(ptr);
 108   }
 109 }
 110
 111 TEST(Allocators, Calloc) {
 112   TestCalloc(0, 0, true);
 113   TestCalloc(0, 1, true);
 114   TestCalloc(1, 1, true);
 115   TestCalloc(1<<10, 0, true);
 116   TestCalloc(1<<20, 0, true);
 117   TestCalloc(0, 1<<10, true);
 118   TestCalloc(0, 1<<20, true);
 119   TestCalloc(1<<20, 2, true);
 120   TestCalloc(2, 1<<20, true);
 121   TestCalloc(1000, 1000, true);
 122
 123   TestCalloc(kMaxSize, 2, false);
 124   TestCalloc(2, kMaxSize, false);
 125   TestCalloc(kMaxSize, kMaxSize, false);
 126
 127   TestCalloc(kMaxSignedSize, 3, false);
 128   TestCalloc(3, kMaxSignedSize, false);
 129   TestCalloc(kMaxSignedSize, kMaxSignedSize, false);
 130 }
 131
 132 // This makes sure that reallocing a small number of bytes in either
 133 // direction doesn't cause us to allocate new memory.
 134 TEST(Allocators, Realloc1) {
 135   int start_sizes[] = { 100, 1000, 10000, 100000 };
 136   int deltas[] = { 1, -2, 4, -8, 16, -32, 64, -128 };
 137
 138   for (int s = 0; s < sizeof(start_sizes)/sizeof(*start_sizes); ++s) {
 139     void* p = malloc(start_sizes[s]);
 140     ASSERT_TRUE(p);
 141     // The larger the start-size, the larger the non-reallocing delta.
 142     for (int d = 0; d < s*2; ++d) {
 143       void* new_p = realloc(p, start_sizes[s] + deltas[d]);
 144       ASSERT_EQ(p, new_p);  // realloc should not allocate new memory
 145     }
 146     // Test again, but this time reallocing smaller first.
 147     for (int d = 0; d < s*2; ++d) {
 148       void* new_p = realloc(p, start_sizes[s] - deltas[d]);
 149       ASSERT_EQ(p, new_p);  // realloc should not allocate new memory
 150     }
 151     free(p);
 152   }
 153 }
 154
 155 TEST(Allocators, Realloc2) {
 156   for (int src_size = 0; src_size >= 0; src_size = NextSize(src_size)) {
 157     for (int dst_size = 0; dst_size >= 0; dst_size = NextSize(dst_size)) {
 158       unsigned char* src = reinterpret_cast<unsigned char*>(malloc(src_size));
 159       Fill(src, src_size);
 160       unsigned char* dst =
 161           reinterpret_cast<unsigned char*>(realloc(src, dst_size));
 162       EXPECT_TRUE(Valid(dst, min(src_size, dst_size)));
 163       Fill(dst, dst_size);
 164       EXPECT_TRUE(Valid(dst, dst_size));
 165       if (dst != NULL) free(dst);
 166     }
 167   }
 168
 169   // Now make sure realloc works correctly even when we overflow the
 170   // packed cache, so some entries are evicted from the cache.
 171   // The cache has 2^12 entries, keyed by page number.
 172   const int kNumEntries = 1 << 14;
 173   int** p = reinterpret_cast<int**>(malloc(sizeof(*p) * kNumEntries));
 174   int sum = 0;
 175   for (int i = 0; i < kNumEntries; i++) {
 176     // no page size is likely to be bigger than 8192?
 177     p[i] = reinterpret_cast<int*>(malloc(8192));
 178     p[i][1000] = i;              // use memory deep in the heart of p
 179   }
 180   for (int i = 0; i < kNumEntries; i++) {
 181     p[i] = reinterpret_cast<int*>(realloc(p[i], 9000));
 182   }
 183   for (int i = 0; i < kNumEntries; i++) {
 184     sum += p[i][1000];
 185     free(p[i]);
 186   }
 187   EXPECT_EQ(kNumEntries/2 * (kNumEntries - 1), sum);  // assume kNE is even
 188   free(p);
 189 }
 190
 191 // Test recalloc
 192 TEST(Allocators, Recalloc) {
 193   for (int src_size = 0; src_size >= 0; src_size = NextSize(src_size)) {
 194     for (int dst_size = 0; dst_size >= 0; dst_size = NextSize(dst_size)) {
 195       unsigned char* src =
 196           reinterpret_cast<unsigned char*>(_recalloc(NULL, 1, src_size));
 197       EXPECT_TRUE(IsZeroed(src, src_size));
 198       Fill(src, src_size);
 199       unsigned char* dst =
 200           reinterpret_cast<unsigned char*>(_recalloc(src, 1, dst_size));
 201       EXPECT_TRUE(Valid(dst, min(src_size, dst_size)));
 202       Fill(dst, dst_size);
 203       EXPECT_TRUE(Valid(dst, dst_size));
 204       if (dst != NULL)
 205         free(dst);
 206     }
 207   }
 208 }
 209
 210 // Test windows specific _aligned_malloc() and _aligned_free() methods.
 211 TEST(Allocators, AlignedMalloc) {
 212   // Try allocating data with a bunch of alignments and sizes
 213   static const int kTestAlignments[] = {8, 16, 256, 4096, 8192, 16384};
 214   for (int size = 1; size > 0; size = NextSize(size)) {
 215     for (int i = 0; i < arraysize(kTestAlignments); ++i) {
 216       unsigned char* ptr = static_cast<unsigned char*>(
 217           _aligned_malloc(size, kTestAlignments[i]));
 218       CheckAlignment(ptr, kTestAlignments[i]);
 219       Fill(ptr, size);
 220       EXPECT_TRUE(Valid(ptr, size));
 221
 222       // Make a second allocation of the same size and alignment to prevent
 223       // allocators from passing this test by accident.  Per jar, tcmalloc
 224       // provides allocations for new (never before seen) sizes out of a thread
 225       // local heap of a given "size class."  Each time the test requests a new
 226       // size, it will usually get the first element of a span, which is a
 227       // 4K aligned allocation.
 228       unsigned char* ptr2 = static_cast<unsigned char*>(
 229           _aligned_malloc(size, kTestAlignments[i]));
 230       CheckAlignment(ptr2, kTestAlignments[i]);
 231       Fill(ptr2, size);
 232       EXPECT_TRUE(Valid(ptr2, size));
 233
 234       // Should never happen, but sanity check just in case.
 235       ASSERT_NE(ptr, ptr2);
 236       _aligned_free(ptr);
 237       _aligned_free(ptr2);
 238     }
 239   }
 240 }
 241
 242 int main(int argc, char** argv) {
 243   testing::InitGoogleTest(&argc, argv);
 244   return RUN_ALL_TESTS();
 245 }