1 /*
2 * Copyright (C) 2016 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 "gtest/gtest.h"
18
19 #include "chre/util/memory_pool.h"
20
21 #include <random>
22 #include <vector>
23
24 using chre::MemoryPool;
25
TEST(MemoryPool,ExhaustPool)26 TEST(MemoryPool, ExhaustPool) {
27 MemoryPool<int, 3> memoryPool;
28 EXPECT_EQ(memoryPool.getFreeBlockCount(), 3);
29 EXPECT_NE(memoryPool.allocate(), nullptr);
30 EXPECT_EQ(memoryPool.getFreeBlockCount(), 2);
31 EXPECT_NE(memoryPool.allocate(), nullptr);
32 EXPECT_EQ(memoryPool.getFreeBlockCount(), 1);
33 EXPECT_NE(memoryPool.allocate(), nullptr);
34 EXPECT_EQ(memoryPool.getFreeBlockCount(), 0);
35 EXPECT_EQ(memoryPool.allocate(), nullptr);
36 EXPECT_EQ(memoryPool.getFreeBlockCount(), 0);
37 }
38
TEST(MemoryPool,OwnershipDeallocation)39 TEST(MemoryPool, OwnershipDeallocation) {
40 MemoryPool<int, 3> firstMemoryPool;
41 MemoryPool<int, 3> secondMemoryPool;
42
43 int *firstMemoryElement = firstMemoryPool.allocate();
44 EXPECT_TRUE(firstMemoryPool.containsAddress(firstMemoryElement));
45 EXPECT_FALSE(secondMemoryPool.containsAddress(firstMemoryElement));
46
47 EXPECT_DEATH(secondMemoryPool.deallocate(firstMemoryElement), "");
48 firstMemoryPool.deallocate(firstMemoryElement);
49 }
50
TEST(MemoryPool,ExhaustPoolThenDeallocateOneAndAllocateOne)51 TEST(MemoryPool, ExhaustPoolThenDeallocateOneAndAllocateOne) {
52 MemoryPool<int, 3> memoryPool;
53
54 // Exhaust the pool.
55 int *element1 = memoryPool.allocate();
56 int *element2 = memoryPool.allocate();
57 int *element3 = memoryPool.allocate();
58
59 // Perform some simple assignments. There is a chance we crash here if things
60 // are not implemented correctly.
61 *element1 = 0xcafe;
62 *element2 = 0xbeef;
63 *element3 = 0xface;
64
65 // Free one element and then allocate another.
66 memoryPool.deallocate(element1);
67 EXPECT_EQ(memoryPool.getFreeBlockCount(), 1);
68 element1 = memoryPool.allocate();
69 EXPECT_NE(element1, nullptr);
70
71 // Ensure that the pool remains exhausted.
72 EXPECT_EQ(memoryPool.allocate(), nullptr);
73
74 // Perform another simple assignment. There is a hope that this can crash if
75 // the pointer returned is very bad (like nullptr).
76 *element1 = 0xfade;
77
78 // Verify that the values stored were not corrupted by the deallocate
79 // allocate cycle.
80 EXPECT_EQ(*element1, 0xfade);
81 EXPECT_EQ(*element2, 0xbeef);
82 EXPECT_EQ(*element3, 0xface);
83 }
84
85 /*
86 * Pair an allocated pointer with the expected value that should be stored in
87 * that location.
88 */
89 struct AllocationExpectedValuePair {
90 size_t *allocation;
91 size_t expectedValue;
92 };
93
TEST(MemoryPool,ExhaustPoolThenRandomDeallocate)94 TEST(MemoryPool, ExhaustPoolThenRandomDeallocate) {
95 // The number of times to allocate and deallocate in random order.
96 const size_t kStressTestCount = 64;
97
98 // Construct a memory pool and a vector to maintain a list of all allocations.
99 const size_t kMemoryPoolSize = 64;
100 MemoryPool<size_t, kMemoryPoolSize> memoryPool;
101 std::vector<AllocationExpectedValuePair> allocations;
102
103 for (size_t i = 0; i < kStressTestCount; i++) {
104 // Exhaust the memory pool.
105 for (size_t j = 0; j < kMemoryPoolSize; j++) {
106 AllocationExpectedValuePair allocation = {
107 .allocation = memoryPool.allocate(),
108 .expectedValue = j,
109 };
110
111 *allocation.allocation = j;
112 allocations.push_back(allocation);
113 }
114
115 // Seed a random number generator with the loop iteration so that order is
116 // preserved across test runs.
117 std::mt19937 randomGenerator(i);
118
119 while (!allocations.empty()) {
120 // Generate a number with a uniform distribution between zero and the
121 // number of allocations remaining.
122 std::uniform_int_distribution<> distribution(0, allocations.size() - 1);
123 size_t deallocateIndex = distribution(randomGenerator);
124
125 // Verify the expected value and free the allocation.
126 EXPECT_EQ(*allocations[deallocateIndex].allocation,
127 allocations[deallocateIndex].expectedValue);
128 memoryPool.deallocate(allocations[deallocateIndex].allocation);
129
130 // Remove the freed allocation from the allocation list.
131 allocations.erase(allocations.begin() + deallocateIndex);
132 }
133 }
134 }
135