1 /* 2 * Copyright (C) 2013 The Android Open Source Project 3 * 4 * Licensed under the Apache License, Version 2.0 (the "License"); 5 * you may not use this file except in compliance with the License. 6 * You may obtain a copy of the License at 7 * 8 * http://www.apache.org/licenses/LICENSE-2.0 9 * 10 * Unless required by applicable law or agreed to in writing, software 11 * distributed under the License is distributed on an "AS IS" BASIS, 12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 * See the License for the specific language governing permissions and 14 * limitations under the License. 15 */ 16 17 #include "base/arena_allocator.h" 18 #include "base/arena_bit_vector.h" 19 #include "base/memory_tool.h" 20 #include "gtest/gtest.h" 21 22 namespace art { 23 24 class ArenaAllocatorTest : public testing::Test { 25 protected: 26 size_t NumberOfArenas(ArenaAllocator* arena) { 27 size_t result = 0u; 28 for (Arena* a = arena->arena_head_; a != nullptr; a = a->next_) { 29 ++result; 30 } 31 return result; 32 } 33 }; 34 35 TEST_F(ArenaAllocatorTest, Test) { 36 ArenaPool pool; 37 ArenaAllocator arena(&pool); 38 ArenaBitVector bv(&arena, 10, true); 39 bv.SetBit(5); 40 EXPECT_EQ(1U, bv.GetStorageSize()); 41 bv.SetBit(35); 42 EXPECT_EQ(2U, bv.GetStorageSize()); 43 } 44 45 TEST_F(ArenaAllocatorTest, MakeDefined) { 46 // Regression test to make sure we mark the allocated area defined. 47 ArenaPool pool; 48 static constexpr size_t kSmallArraySize = 10; 49 static constexpr size_t kLargeArraySize = 50; 50 uint32_t* small_array; 51 { 52 // Allocate a small array from an arena and release it. 53 ArenaAllocator arena(&pool); 54 small_array = arena.AllocArray<uint32_t>(kSmallArraySize); 55 ASSERT_EQ(0u, small_array[kSmallArraySize - 1u]); 56 } 57 { 58 // Reuse the previous arena and allocate more than previous allocation including red zone. 59 ArenaAllocator arena(&pool); 60 uint32_t* large_array = arena.AllocArray<uint32_t>(kLargeArraySize); 61 ASSERT_EQ(0u, large_array[kLargeArraySize - 1u]); 62 // Verify that the allocation was made on the same arena. 63 ASSERT_EQ(small_array, large_array); 64 } 65 } 66 67 TEST_F(ArenaAllocatorTest, LargeAllocations) { 68 { 69 ArenaPool pool; 70 ArenaAllocator arena(&pool); 71 // Note: Leaving some space for memory tool red zones. 72 void* alloc1 = arena.Alloc(Arena::kDefaultSize * 5 / 8); 73 void* alloc2 = arena.Alloc(Arena::kDefaultSize * 2 / 8); 74 ASSERT_NE(alloc1, alloc2); 75 ASSERT_EQ(1u, NumberOfArenas(&arena)); 76 } 77 { 78 ArenaPool pool; 79 ArenaAllocator arena(&pool); 80 void* alloc1 = arena.Alloc(Arena::kDefaultSize * 13 / 16); 81 void* alloc2 = arena.Alloc(Arena::kDefaultSize * 11 / 16); 82 ASSERT_NE(alloc1, alloc2); 83 ASSERT_EQ(2u, NumberOfArenas(&arena)); 84 void* alloc3 = arena.Alloc(Arena::kDefaultSize * 7 / 16); 85 ASSERT_NE(alloc1, alloc3); 86 ASSERT_NE(alloc2, alloc3); 87 ASSERT_EQ(3u, NumberOfArenas(&arena)); 88 } 89 { 90 ArenaPool pool; 91 ArenaAllocator arena(&pool); 92 void* alloc1 = arena.Alloc(Arena::kDefaultSize * 13 / 16); 93 void* alloc2 = arena.Alloc(Arena::kDefaultSize * 9 / 16); 94 ASSERT_NE(alloc1, alloc2); 95 ASSERT_EQ(2u, NumberOfArenas(&arena)); 96 // Note: Leaving some space for memory tool red zones. 97 void* alloc3 = arena.Alloc(Arena::kDefaultSize * 5 / 16); 98 ASSERT_NE(alloc1, alloc3); 99 ASSERT_NE(alloc2, alloc3); 100 ASSERT_EQ(2u, NumberOfArenas(&arena)); 101 } 102 { 103 ArenaPool pool; 104 ArenaAllocator arena(&pool); 105 void* alloc1 = arena.Alloc(Arena::kDefaultSize * 9 / 16); 106 void* alloc2 = arena.Alloc(Arena::kDefaultSize * 13 / 16); 107 ASSERT_NE(alloc1, alloc2); 108 ASSERT_EQ(2u, NumberOfArenas(&arena)); 109 // Note: Leaving some space for memory tool red zones. 110 void* alloc3 = arena.Alloc(Arena::kDefaultSize * 5 / 16); 111 ASSERT_NE(alloc1, alloc3); 112 ASSERT_NE(alloc2, alloc3); 113 ASSERT_EQ(2u, NumberOfArenas(&arena)); 114 } 115 { 116 ArenaPool pool; 117 ArenaAllocator arena(&pool); 118 // Note: Leaving some space for memory tool red zones. 119 for (size_t i = 0; i != 15; ++i) { 120 arena.Alloc(Arena::kDefaultSize * 1 / 16); // Allocate 15 times from the same arena. 121 ASSERT_EQ(i + 1u, NumberOfArenas(&arena)); 122 arena.Alloc(Arena::kDefaultSize * 17 / 16); // Allocate a separate arena. 123 ASSERT_EQ(i + 2u, NumberOfArenas(&arena)); 124 } 125 } 126 } 127 128 TEST_F(ArenaAllocatorTest, AllocAlignment) { 129 ArenaPool pool; 130 ArenaAllocator arena(&pool); 131 for (size_t iterations = 0; iterations <= 10; ++iterations) { 132 for (size_t size = 1; size <= ArenaAllocator::kAlignment + 1; ++size) { 133 void* allocation = arena.Alloc(size); 134 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(allocation)) 135 << reinterpret_cast<uintptr_t>(allocation); 136 } 137 } 138 } 139 140 TEST_F(ArenaAllocatorTest, ReallocReuse) { 141 // Realloc does not reuse arenas when running under sanitization. So we cannot do those 142 if (RUNNING_ON_MEMORY_TOOL != 0) { 143 printf("WARNING: TEST DISABLED FOR MEMORY_TOOL\n"); 144 return; 145 } 146 147 { 148 // Case 1: small aligned allocation, aligned extend inside arena. 149 ArenaPool pool; 150 ArenaAllocator arena(&pool); 151 152 const size_t original_size = ArenaAllocator::kAlignment * 2; 153 void* original_allocation = arena.Alloc(original_size); 154 155 const size_t new_size = ArenaAllocator::kAlignment * 3; 156 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 157 EXPECT_EQ(original_allocation, realloc_allocation); 158 } 159 160 { 161 // Case 2: small aligned allocation, non-aligned extend inside arena. 162 ArenaPool pool; 163 ArenaAllocator arena(&pool); 164 165 const size_t original_size = ArenaAllocator::kAlignment * 2; 166 void* original_allocation = arena.Alloc(original_size); 167 168 const size_t new_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2); 169 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 170 EXPECT_EQ(original_allocation, realloc_allocation); 171 } 172 173 { 174 // Case 3: small non-aligned allocation, aligned extend inside arena. 175 ArenaPool pool; 176 ArenaAllocator arena(&pool); 177 178 const size_t original_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2); 179 void* original_allocation = arena.Alloc(original_size); 180 181 const size_t new_size = ArenaAllocator::kAlignment * 4; 182 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 183 EXPECT_EQ(original_allocation, realloc_allocation); 184 } 185 186 { 187 // Case 4: small non-aligned allocation, aligned non-extend inside arena. 188 ArenaPool pool; 189 ArenaAllocator arena(&pool); 190 191 const size_t original_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2); 192 void* original_allocation = arena.Alloc(original_size); 193 194 const size_t new_size = ArenaAllocator::kAlignment * 3; 195 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 196 EXPECT_EQ(original_allocation, realloc_allocation); 197 } 198 199 // The next part is brittle, as the default size for an arena is variable, and we don't know about 200 // sanitization. 201 202 { 203 // Case 5: large allocation, aligned extend into next arena. 204 ArenaPool pool; 205 ArenaAllocator arena(&pool); 206 207 const size_t original_size = Arena::kDefaultSize - ArenaAllocator::kAlignment * 5; 208 void* original_allocation = arena.Alloc(original_size); 209 210 const size_t new_size = Arena::kDefaultSize + ArenaAllocator::kAlignment * 2; 211 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 212 EXPECT_NE(original_allocation, realloc_allocation); 213 } 214 215 { 216 // Case 6: large allocation, non-aligned extend into next arena. 217 ArenaPool pool; 218 ArenaAllocator arena(&pool); 219 220 const size_t original_size = Arena::kDefaultSize - 221 ArenaAllocator::kAlignment * 4 - 222 ArenaAllocator::kAlignment / 2; 223 void* original_allocation = arena.Alloc(original_size); 224 225 const size_t new_size = Arena::kDefaultSize + 226 ArenaAllocator::kAlignment * 2 + 227 ArenaAllocator::kAlignment / 2; 228 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 229 EXPECT_NE(original_allocation, realloc_allocation); 230 } 231 } 232 233 TEST_F(ArenaAllocatorTest, ReallocAlignment) { 234 { 235 // Case 1: small aligned allocation, aligned extend inside arena. 236 ArenaPool pool; 237 ArenaAllocator arena(&pool); 238 239 const size_t original_size = ArenaAllocator::kAlignment * 2; 240 void* original_allocation = arena.Alloc(original_size); 241 ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation)); 242 243 const size_t new_size = ArenaAllocator::kAlignment * 3; 244 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 245 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation)); 246 247 void* after_alloc = arena.Alloc(1); 248 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc)); 249 } 250 251 { 252 // Case 2: small aligned allocation, non-aligned extend inside arena. 253 ArenaPool pool; 254 ArenaAllocator arena(&pool); 255 256 const size_t original_size = ArenaAllocator::kAlignment * 2; 257 void* original_allocation = arena.Alloc(original_size); 258 ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation)); 259 260 const size_t new_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2); 261 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 262 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation)); 263 264 void* after_alloc = arena.Alloc(1); 265 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc)); 266 } 267 268 { 269 // Case 3: small non-aligned allocation, aligned extend inside arena. 270 ArenaPool pool; 271 ArenaAllocator arena(&pool); 272 273 const size_t original_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2); 274 void* original_allocation = arena.Alloc(original_size); 275 ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation)); 276 277 const size_t new_size = ArenaAllocator::kAlignment * 4; 278 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 279 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation)); 280 281 void* after_alloc = arena.Alloc(1); 282 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc)); 283 } 284 285 { 286 // Case 4: small non-aligned allocation, aligned non-extend inside arena. 287 ArenaPool pool; 288 ArenaAllocator arena(&pool); 289 290 const size_t original_size = ArenaAllocator::kAlignment * 2 + (ArenaAllocator::kAlignment / 2); 291 void* original_allocation = arena.Alloc(original_size); 292 ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation)); 293 294 const size_t new_size = ArenaAllocator::kAlignment * 3; 295 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 296 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation)); 297 298 void* after_alloc = arena.Alloc(1); 299 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc)); 300 } 301 302 // The next part is brittle, as the default size for an arena is variable, and we don't know about 303 // sanitization. 304 305 { 306 // Case 5: large allocation, aligned extend into next arena. 307 ArenaPool pool; 308 ArenaAllocator arena(&pool); 309 310 const size_t original_size = Arena::kDefaultSize - ArenaAllocator::kAlignment * 5; 311 void* original_allocation = arena.Alloc(original_size); 312 ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation)); 313 314 const size_t new_size = Arena::kDefaultSize + ArenaAllocator::kAlignment * 2; 315 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 316 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation)); 317 318 void* after_alloc = arena.Alloc(1); 319 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc)); 320 } 321 322 { 323 // Case 6: large allocation, non-aligned extend into next arena. 324 ArenaPool pool; 325 ArenaAllocator arena(&pool); 326 327 const size_t original_size = Arena::kDefaultSize - 328 ArenaAllocator::kAlignment * 4 - 329 ArenaAllocator::kAlignment / 2; 330 void* original_allocation = arena.Alloc(original_size); 331 ASSERT_TRUE(IsAligned<ArenaAllocator::kAlignment>(original_allocation)); 332 333 const size_t new_size = Arena::kDefaultSize + 334 ArenaAllocator::kAlignment * 2 + 335 ArenaAllocator::kAlignment / 2; 336 void* realloc_allocation = arena.Realloc(original_allocation, original_size, new_size); 337 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(realloc_allocation)); 338 339 void* after_alloc = arena.Alloc(1); 340 EXPECT_TRUE(IsAligned<ArenaAllocator::kAlignment>(after_alloc)); 341 } 342 } 343 344 345 } // namespace art 346