xpcom/tests/gtest/TestArenaAllocator.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #include "mozilla/ArenaAllocator.h"
   8 #include "mozilla/ArenaAllocatorExtensions.h"
   9 #include "nsIMemoryReporter.h"  // MOZ_MALLOC_SIZE_OF
  10
  11 #include "gtest/gtest.h"
  12
  13 using mozilla::ArenaAllocator;
  14
  15 TEST(ArenaAllocator, Constructor)
  16 { ArenaAllocator<4096, 4> a; }
  17
  18 TEST(ArenaAllocator, DefaultAllocate)
  19 {
  20   // Test default 1-byte alignment.
  21   ArenaAllocator<1024> a;
  22   void* x = a.Allocate(101);
  23   void* y = a.Allocate(101);
  24
  25   // Given 1-byte aligment, we expect the allocations to follow
  26   // each other exactly.
  27   EXPECT_EQ(uintptr_t(x) + 101, uintptr_t(y));
  28 }
  29
  30 TEST(ArenaAllocator, AllocateAlignment)
  31 {
  32   // Test non-default 8-byte alignment.
  33   static const size_t kAlignment = 8;
  34   ArenaAllocator<1024, kAlignment> a;
  35
  36   // Make sure aligment is correct for 1-8.
  37   for (size_t i = 1; i <= kAlignment; i++) {
  38     // All of these should be 8 bytes
  39     void* x = a.Allocate(i);
  40     void* y = a.Allocate(i);
  41     EXPECT_EQ(uintptr_t(x) + kAlignment, uintptr_t(y));
  42   }
  43
  44   // Test with slightly larger than specified alignment.
  45   void* x = a.Allocate(kAlignment + 1);
  46   void* y = a.Allocate(kAlignment + 1);
  47
  48   // Given 8-byte aligment, and a non-8-byte aligned request we expect the
  49   // allocations to be padded.
  50   EXPECT_NE(uintptr_t(x) + kAlignment, uintptr_t(y));
  51
  52   // We expect 7 bytes of padding to have been added.
  53   EXPECT_EQ(uintptr_t(x) + kAlignment * 2, uintptr_t(y));
  54 }
  55
  56 #if 0
  57 TEST(ArenaAllocator, AllocateZeroBytes)
  58 {
  59   // This would have to be a death test. Since we chose to provide an
  60   // infallible allocator we can't just return nullptr in the 0 case as
  61   // there's no way to differentiate that from the OOM case.
  62   ArenaAllocator<1024> a;
  63   void* x = a.Allocate(0);
  64   EXPECT_FALSE(x);
  65 }
  66
  67 TEST(ArenaAllocator, BadAlignment)
  68 {
  69   // This test causes build failures by triggering the static assert enforcing
  70   // a power-of-two alignment.
  71   ArenaAllocator<256, 3> a;
  72   ArenaAllocator<256, 7> b;
  73   ArenaAllocator<256, 17> c;
  74 }
  75 #endif
  76
  77 TEST(ArenaAllocator, AllocateMultipleSizes)
  78 {
  79   // Test non-default 4-byte alignment.
  80   ArenaAllocator<4096, 4> a;
  81
  82   for (int i = 1; i < 50; i++) {
  83     void* x = a.Allocate(i);
  84     // All the allocations should be aligned properly.
  85     EXPECT_EQ(uintptr_t(x) % 4, uintptr_t(0));
  86   }
  87
  88   // Test a large 64-byte alignment
  89   ArenaAllocator<8192, 64> b;
  90   for (int i = 1; i < 100; i++) {
  91     void* x = b.Allocate(i);
  92     // All the allocations should be aligned properly.
  93     EXPECT_EQ(uintptr_t(x) % 64, uintptr_t(0));
  94   }
  95 }
  96
  97 TEST(ArenaAllocator, AllocateInDifferentChunks)
  98 {
  99   // Test default 1-byte alignment.
 100   ArenaAllocator<4096> a;
 101   void* x = a.Allocate(4000);
 102   void* y = a.Allocate(4000);
 103   EXPECT_NE(uintptr_t(x) + 4000, uintptr_t(y));
 104 }
 105
 106 TEST(ArenaAllocator, AllocateLargerThanArenaSize)
 107 {
 108   // Test default 1-byte alignment.
 109   ArenaAllocator<256> a;
 110   void* x = a.Allocate(4000);
 111   void* y = a.Allocate(4000);
 112   EXPECT_TRUE(x);
 113   EXPECT_TRUE(y);
 114
 115   // Now try a normal allocation, it should behave as expected.
 116   x = a.Allocate(8);
 117   y = a.Allocate(8);
 118   EXPECT_EQ(uintptr_t(x) + 8, uintptr_t(y));
 119 }
 120
 121 TEST(ArenaAllocator, AllocationsPerChunk)
 122 {
 123   // Test that expected number of allocations fit in one chunk.
 124   // We use an alignment of 64-bytes to avoid worrying about differences in
 125   // the header size on 32 and 64-bit platforms.
 126   const size_t kArenaSize = 1024;
 127   const size_t kAlignment = 64;
 128   ArenaAllocator<kArenaSize, kAlignment> a;
 129
 130   // With an alignment of 64 bytes we expect the header to take up the first
 131   // alignment sized slot leaving bytes leaving the rest available for
 132   // allocation.
 133   const size_t kAllocationsPerChunk = (kArenaSize / kAlignment) - 1;
 134   void* x = nullptr;
 135   void* y = a.Allocate(kAlignment);
 136   EXPECT_TRUE(y);
 137   for (size_t i = 1; i < kAllocationsPerChunk; i++) {
 138     x = y;
 139     y = a.Allocate(kAlignment);
 140     EXPECT_EQ(uintptr_t(x) + kAlignment, uintptr_t(y));
 141   }
 142
 143   // The next allocation should be in a different chunk.
 144   x = y;
 145   y = a.Allocate(kAlignment);
 146   EXPECT_NE(uintptr_t(x) + kAlignment, uintptr_t(y));
 147 }
 148
 149 TEST(ArenaAllocator, MemoryIsValid)
 150 {
 151   // Make multiple allocations and actually access the memory. This is
 152   // expected to trip up ASAN or valgrind if out of bounds memory is
 153   // accessed.
 154   static const size_t kArenaSize = 1024;
 155   static const size_t kAlignment = 64;
 156   static const char kMark = char(0xBC);
 157   ArenaAllocator<kArenaSize, kAlignment> a;
 158
 159   // Single allocation that should fill the arena.
 160   size_t sz = kArenaSize - kAlignment;
 161   char* x = (char*)a.Allocate(sz);
 162   EXPECT_EQ(uintptr_t(x) % kAlignment, uintptr_t(0));
 163   memset(x, kMark, sz);
 164   for (size_t i = 0; i < sz; i++) {
 165     EXPECT_EQ(x[i], kMark);
 166   }
 167
 168   // Allocation over arena size.
 169   sz = kArenaSize * 2;
 170   x = (char*)a.Allocate(sz);
 171   EXPECT_EQ(uintptr_t(x) % kAlignment, uintptr_t(0));
 172   memset(x, kMark, sz);
 173   for (size_t i = 0; i < sz; i++) {
 174     EXPECT_EQ(x[i], kMark);
 175   }
 176
 177   // Allocation half the arena size.
 178   sz = kArenaSize / 2;
 179   x = (char*)a.Allocate(sz);
 180   EXPECT_EQ(uintptr_t(x) % kAlignment, uintptr_t(0));
 181   memset(x, kMark, sz);
 182   for (size_t i = 0; i < sz; i++) {
 183     EXPECT_EQ(x[i], kMark);
 184   }
 185
 186   // Repeat, this should actually end up in a new chunk.
 187   x = (char*)a.Allocate(sz);
 188   EXPECT_EQ(uintptr_t(x) % kAlignment, uintptr_t(0));
 189   memset(x, kMark, sz);
 190   for (size_t i = 0; i < sz; i++) {
 191     EXPECT_EQ(x[i], kMark);
 192   }
 193 }
 194
 195 MOZ_DEFINE_MALLOC_SIZE_OF(TestSizeOf);
 196
 197 TEST(ArenaAllocator, SizeOf)
 198 {
 199   // This tests the sizeof functionality. We can't test for equality as we
 200   // can't reliably guarantee what sizes the underlying allocator is going to
 201   // choose, so we just test that things grow (or not) as expected.
 202   static const size_t kArenaSize = 4096;
 203   ArenaAllocator<kArenaSize> a;
 204
 205   // Excluding *this we expect an empty arena allocator to have no overhead.
 206   size_t sz = a.SizeOfExcludingThis(TestSizeOf);
 207   EXPECT_EQ(sz, size_t(0));
 208
 209   // Cause one chunk to be allocated.
 210   (void)a.Allocate(kArenaSize / 2);
 211   size_t prev_sz = sz;
 212   sz = a.SizeOfExcludingThis(TestSizeOf);
 213   EXPECT_GT(sz, prev_sz);
 214
 215   // Allocate within the current chunk.
 216   (void)a.Allocate(kArenaSize / 4);
 217   prev_sz = sz;
 218   sz = a.SizeOfExcludingThis(TestSizeOf);
 219   EXPECT_EQ(sz, prev_sz);
 220
 221   // Overflow to a new chunk.
 222   (void)a.Allocate(kArenaSize / 2);
 223   prev_sz = sz;
 224   sz = a.SizeOfExcludingThis(TestSizeOf);
 225   EXPECT_GT(sz, prev_sz);
 226
 227   // Allocate an oversized chunk with enough room for a header to fit in page
 228   // size. We expect the underlying allocator to round up to page alignment.
 229   (void)a.Allocate((kArenaSize * 2) - 64);
 230   sz = a.SizeOfExcludingThis(TestSizeOf);
 231   EXPECT_GT(sz, prev_sz);
 232 }
 233
 234 TEST(ArenaAllocator, Clear)
 235 {
 236   // Tests that the Clear function works as expected. The best proxy for
 237   // checking if a clear is successful is to measure the size. If it's empty we
 238   // expect the size to be 0.
 239   static const size_t kArenaSize = 128;
 240   ArenaAllocator<kArenaSize> a;
 241
 242   // Clearing an empty arena should work.
 243   a.Clear();
 244
 245   size_t sz = a.SizeOfExcludingThis(TestSizeOf);
 246   EXPECT_EQ(sz, size_t(0));
 247
 248   // Allocating should work after clearing an empty arena.
 249   void* x = a.Allocate(10);
 250   EXPECT_TRUE(x);
 251
 252   size_t prev_sz = sz;
 253   sz = a.SizeOfExcludingThis(TestSizeOf);
 254   EXPECT_GT(sz, prev_sz);
 255
 256   // Allocate enough for a few arena chunks to be necessary.
 257   for (size_t i = 0; i < kArenaSize * 2; i++) {
 258     x = a.Allocate(1);
 259     EXPECT_TRUE(x);
 260   }
 261
 262   prev_sz = sz;
 263   sz = a.SizeOfExcludingThis(TestSizeOf);
 264   EXPECT_GT(sz, prev_sz);
 265
 266   // Clearing should reduce the size back to zero.
 267   a.Clear();
 268   sz = a.SizeOfExcludingThis(TestSizeOf);
 269   EXPECT_EQ(sz, size_t(0));
 270
 271   // Allocating should work after clearing an arena with allocations.
 272   x = a.Allocate(10);
 273   EXPECT_TRUE(x);
 274
 275   prev_sz = sz;
 276   sz = a.SizeOfExcludingThis(TestSizeOf);
 277   EXPECT_GT(sz, prev_sz);
 278 }
 279
 280 TEST(ArenaAllocator, Extensions)
 281 {
 282   ArenaAllocator<4096, 8> a;
 283
 284   // Test with raw strings.
 285   const char* const kTestCStr = "This is a test string.";
 286   char* c_dup = mozilla::ArenaStrdup(kTestCStr, a);
 287   EXPECT_STREQ(c_dup, kTestCStr);
 288
 289   const char16_t* const kTestStr = u"This is a wide test string.";
 290   char16_t* dup = mozilla::ArenaStrdup(kTestStr, a);
 291   EXPECT_TRUE(nsString(dup).Equals(kTestStr));
 292
 293   // Make sure it works with literal strings.
 294   constexpr auto wideStr = u"A wide string."_ns;
 295   nsLiteralString::char_type* wide = mozilla::ArenaStrdup(wideStr, a);
 296   EXPECT_TRUE(wideStr.Equals(wide));
 297
 298   constexpr auto cStr = "A c-string."_ns;
 299   nsLiteralCString::char_type* cstr = mozilla::ArenaStrdup(cStr, a);
 300   EXPECT_TRUE(cStr.Equals(cstr));
 301
 302   // Make sure it works with normal strings.
 303   nsAutoString x(u"testing wide");
 304   nsAutoString::char_type* x_copy = mozilla::ArenaStrdup(x, a);
 305   EXPECT_TRUE(x.Equals(x_copy));
 306
 307   nsAutoCString y("testing c-string");
 308   nsAutoCString::char_type* y_copy = mozilla::ArenaStrdup(y, a);
 309   EXPECT_TRUE(y.Equals(y_copy));
 310 }