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