1 /*
2 This file tests basic functionality of BBlockCache.
3 */
4
5
6 #include "BlockCacheExerciseTest.h"
7
8 #include <stdlib.h>
9
10 #include <BlockCache.h>
11
12 #include "cppunit/TestCaller.h"
13
14
15 /*
16 * Method: BlockCacheExerciseTest::BlockCacheExerciseTest()
17 * Descr: This method is the only constructor for the BlockCacheExerciseTest
18 * class.
19 */
BlockCacheExerciseTest(std::string name)20 BlockCacheExerciseTest::BlockCacheExerciseTest(std::string name)
21 :
22 TestCase(name),
23 theCache(NULL),
24 numBlocksInCache(0),
25 sizeOfBlocksInCache(0),
26 sizeOfNonCacheBlocks(0),
27 isMallocTest(false)
28 {
29 }
30
31
32 /*
33 * Method: BlockCacheExerciseTest::~BlockCacheExerciseTest()
34 * Descr: This method is the destructor for the BlockCacheExerciseTest class.
35 */
~BlockCacheExerciseTest()36 BlockCacheExerciseTest::~BlockCacheExerciseTest()
37 {
38 }
39
40
41 /*
42 * Method: BlockCacheExerciseTest::TestBlockCache()
43 * Descr: This method performs the tests on a particular BBlockCache.
44 * The goal of the method is to perform the following basic
45 * sequence:
46 * 1. Get (numBlocksInCache + 10) blocks of "cache size" from the
47 * BBlockCache. By doing this, we can guarantee that the cache
48 * has been exhausted and some elements are allocated to
49 * satisfy the caller. Then, they are all returned to the
50 * cache in most recent block to oldest block order. This
51 * confirms that regardless whether the block was initially
52 * part of the cache or created because the cache was empty,
53 * once it is returned to the cache, it is just placed on the
54 * cache. Imagine a cache of 4 blocks. Initally, the cache
55 * has the following blocks:
56 * A, B, C, D
57 * If five blocks are gotten from the cache, the caller will get
58 * A, B, C, D, E
59 * However, E wasn't initially part of the cache. It was allocated
60 * dynamically to satisfy the caller's request because the cache
61 * was empty. Now, if they are returned in the order E, D, C, B, A
62 * the cache will have the following blocks available in it:
63 * B, C, D, E
64 * When A is returned, the cache will find there is no more room
65 * for more free blocks and it will be freed. This is the
66 * behaviour which is confirmed initially.
67 *
68 * 2. After this is done, the cache is just "exercised". The following
69 * is done "numBlocksInCache" times:
70 * - 4 "cache sized" blocks are gotten from the cache
71 * - 4 "non-cache sized" blocks are gotten from the cache
72 * - 1 "cache sized" block is returned back to the cache
73 * - 1 "non-cache sized" block is returned back to the cache
74 * - 1 "cache sized" block is freed and not returned to the cache
75 * - 1 "non-cache sized" block is freed and not returned to the
76 * cache (but even if given to the BBlockCache, it would just
77 * be freed anyhow)
78 * What this means is that everytime through the loop, 2 "cache sized"
79 * and 2 "non-cache sized" blocks are kept in memory. At the end,
80 * 2 * numBlocksInCache items of size "cache size" and "non cache size"
81 * will exist.
82 *
83 * Then, numBlocksInCache / 4 items are returned to the cache and
84 * numBlocksInCache / 4 are freed. This ensures at the end of the
85 * test that there are some available blocks in the cache.
86 *
87 * The sum total of these actions test the BBlockCache.
88 */
89 void
TestBlockCache(void)90 BlockCacheExerciseTest::TestBlockCache(void)
91 {
92
93 // First get all items from the cache plus ten more
94 for (int i = 0; i < numBlocksInCache + 10; i++) {
95 GetBlock(sizeOfBlocksInCache);
96 }
97
98 // Put them all back in reverse order to confirm 1 from above
99 while (!usedList.IsEmpty()) {
100 SaveBlock(usedList.LastItem(), sizeOfBlocksInCache);
101 }
102
103 // Get a bunch of blocks and send some back to the cache
104 // to confirm 2 from above.
105 for (int i = 0; i < numBlocksInCache; i++) {
106 GetBlock(sizeOfBlocksInCache);
107 GetBlock(sizeOfBlocksInCache);
108 GetBlock(sizeOfNonCacheBlocks);
109 GetBlock(sizeOfNonCacheBlocks);
110
111 // We send one back from the middle of the lists so
112 // the most recent block is not the one returned.
113 SaveBlock(usedList.ItemAt(usedList.CountItems() / 2),
114 sizeOfBlocksInCache);
115 SaveBlock(nonCacheList.ItemAt(nonCacheList.CountItems() / 2),
116 sizeOfNonCacheBlocks);
117
118 GetBlock(sizeOfBlocksInCache);
119 GetBlock(sizeOfBlocksInCache);
120 GetBlock(sizeOfNonCacheBlocks);
121 GetBlock(sizeOfNonCacheBlocks);
122
123 // We free one from the middle of the lists so the
124 // most recent block is not the one freed.
125 FreeBlock(usedList.ItemAt(usedList.CountItems() / 2),
126 sizeOfBlocksInCache);
127 FreeBlock(nonCacheList.ItemAt(nonCacheList.CountItems() / 2),
128 sizeOfNonCacheBlocks);
129 }
130
131 // Now, send some blocks back to the cache and free some blocks
132 // so the cache is not empty at the end of the test.
133 for (int i = 0; i < numBlocksInCache / 4; i++) {
134 // Return the blocks which are 2/3s of the way through the
135 // lists.
136 SaveBlock(usedList.ItemAt(usedList.CountItems() * 2 / 3),
137 sizeOfBlocksInCache);
138 SaveBlock(nonCacheList.ItemAt(nonCacheList.CountItems() * 2 / 3),
139 sizeOfNonCacheBlocks);
140
141 // Free the blocks which are 1/3 of the way through the lists.
142 FreeBlock(usedList.ItemAt(usedList.CountItems() / 3),
143 sizeOfBlocksInCache);
144 FreeBlock(nonCacheList.ItemAt(nonCacheList.CountItems() / 3),
145 sizeOfNonCacheBlocks);
146 }
147 }
148
149
150 /*
151 * Method: BlockCacheExerciseTest::BuildLists()
152 * Descr: This method gets all of the blocks from the cache in order to
153 * track them for future tests. The assumption here is that the
154 * blocks are not deallocated and reallocated in the implementation
155 * of BBlockCache. Given the purpose is to provide a cheap way to
156 * access allocated memory without resorting to malloc()'s or new's,
157 * this should be a fair assumption.
158 */
159 void
BuildLists()160 BlockCacheExerciseTest::BuildLists()
161 {
162 freeList.MakeEmpty();
163 usedList.MakeEmpty();
164 nonCacheList.MakeEmpty();
165
166 for(int i = 0; i < numBlocksInCache; i++) {
167 freeList.AddItem(theCache->Get(sizeOfBlocksInCache));
168 }
169 for(int i = 0; i < numBlocksInCache; i++) {
170 theCache->Save(freeList.ItemAt(i), sizeOfBlocksInCache);
171 }
172 }
173
174
175 /*
176 * Method: BlockCacheExerciseTest::GetBlock()
177 * Descr: This method returns a pointer from the BBlockCache, checking
178 * the value before passing it to the caller.
179 */
180 void *
GetBlock(size_t blockSize)181 BlockCacheExerciseTest::GetBlock(size_t blockSize)
182 {
183 void *thePtr = theCache->Get(blockSize);
184
185 // This new pointer should not be one which we already
186 // have from the BBlockCache which we haven't given back
187 // yet.
188 CPPUNIT_ASSERT(!usedList.HasItem(thePtr));
189 CPPUNIT_ASSERT(!nonCacheList.HasItem(thePtr));
190
191 if (blockSize == sizeOfBlocksInCache) {
192 // If this block was one which could have come from the
193 // cache and there are free items on the cache, it
194 // should be one of those free blocks.
195 if (freeList.CountItems() > 0) {
196 CPPUNIT_ASSERT(freeList.RemoveItem(thePtr));
197 }
198 CPPUNIT_ASSERT(usedList.AddItem(thePtr));
199 } else {
200 // A "non-cache sized" block should never come from the
201 // free list.
202 CPPUNIT_ASSERT(!freeList.HasItem(thePtr));
203 CPPUNIT_ASSERT(nonCacheList.AddItem(thePtr));
204 }
205 return(thePtr);
206 }
207
208
209 /*
210 * Method: BlockCacheExerciseTest::SavedCacheBlock()
211 * Descr: This method passes the pointer back to the BBlockCache
212 * and checks the sanity of the lists.
213 */
214 void
SaveBlock(void * thePtr,size_t blockSize)215 BlockCacheExerciseTest::SaveBlock(void *thePtr, size_t blockSize)
216 {
217 // The memory block being returned to the cache should
218 // not already be free.
219 CPPUNIT_ASSERT(!freeList.HasItem(thePtr));
220
221 if (blockSize == sizeOfBlocksInCache) {
222 // If there is room on the free list, when this block
223 // is returned to the cache, it will be put on the
224 // free list. Therefore we will also track it as
225 // a free block on the cache.
226 if (freeList.CountItems() < numBlocksInCache) {
227 CPPUNIT_ASSERT(freeList.AddItem(thePtr));
228 }
229
230 // This block should not be on the non-cache list but it
231 // should be on the used list.
232 CPPUNIT_ASSERT(!nonCacheList.HasItem(thePtr));
233 CPPUNIT_ASSERT(usedList.RemoveItem(thePtr));
234 } else {
235 // This block should not be on the used list but it should
236 // be on the non-cache list.
237 CPPUNIT_ASSERT(!usedList.HasItem(thePtr));
238 CPPUNIT_ASSERT(nonCacheList.RemoveItem(thePtr));
239 }
240 theCache->Save(thePtr, blockSize);
241 }
242
243
244 /*
245 * Method: BlockCacheExerciseTest::FreeBlock()
246 * Descr: This method frees the block directly using delete[] or free(),
247 * checking the sanity of the lists as it does the operation.
248 */
249 void
FreeBlock(void * thePtr,size_t blockSize)250 BlockCacheExerciseTest::FreeBlock(void *thePtr, size_t blockSize)
251 {
252 // The block being freed should not already have been
253 // returned to the cache.
254 CPPUNIT_ASSERT(!freeList.HasItem(thePtr));
255
256 if (blockSize == sizeOfBlocksInCache) {
257 // This block should not be on the non-cache list but it
258 // should be on the used list.
259 CPPUNIT_ASSERT(!nonCacheList.HasItem(thePtr));
260 CPPUNIT_ASSERT(usedList.RemoveItem(thePtr));
261 } else {
262 // This block should not be on the used list but it should
263 // be on the non-cache list.
264 CPPUNIT_ASSERT(!usedList.HasItem(thePtr));
265 CPPUNIT_ASSERT(nonCacheList.RemoveItem(thePtr));
266 }
267 if (isMallocTest) {
268 free(thePtr);
269 } else {
270 delete[] (uint8*)thePtr;
271 }
272 }
273
274
275 /*
276 * Method: BlockCacheExerciseTest::PerformTest()
277 * Descr: This method performs the tests on a series of BBlockCache
278 * instances. It performs the tests with a series of
279 * block sizes and numbers of blocks. Also, it does the
280 * test using a B_OBJECT_CACHE and B_MALLOC_CACHE type
281 * cache. For each individual BBlockCache to be tested, it:
282 * 1. Queries the cache to find out the blocks which are
283 * on it.
284 * 2. Performs the test.
285 * 3. Frees all blocks left after the test to prevent
286 * memory leaks.
287 */
288 void
PerformTest(void)289 BlockCacheExerciseTest::PerformTest(void)
290 {
291 for (numBlocksInCache = 8; numBlocksInCache < 513; numBlocksInCache *= 2) {
292 for (sizeOfBlocksInCache = 13; sizeOfBlocksInCache < 9478; sizeOfBlocksInCache *= 3) {
293
294 // To test getting blocks which are not from the cache,
295 // we will get blocks of 6 bytes less than the size of
296 // the blocks on the cache.
297 sizeOfNonCacheBlocks = sizeOfBlocksInCache - 6;
298
299 isMallocTest = false;
300 theCache = new BBlockCache(numBlocksInCache, sizeOfBlocksInCache, B_OBJECT_CACHE);
301 CPPUNIT_ASSERT(theCache != NULL);
302
303 // Query the cache and determine the blocks in it.
304 BuildLists();
305 // Perform the test on this instance.
306 TestBlockCache();
307 delete theCache;
308 // Clean up remaining memory.
309 while (!usedList.IsEmpty()) {
310 FreeBlock(usedList.LastItem(), sizeOfBlocksInCache);
311 }
312 while (!nonCacheList.IsEmpty()) {
313 FreeBlock(nonCacheList.LastItem(), sizeOfNonCacheBlocks);
314 }
315
316 isMallocTest = true;
317 theCache = new BBlockCache(numBlocksInCache, sizeOfBlocksInCache, B_MALLOC_CACHE);
318 CPPUNIT_ASSERT(theCache != NULL);
319
320 // Query the cache and determine the blocks in it.
321 BuildLists();
322 // Perform the test on this instance.
323 TestBlockCache();
324 delete theCache;
325 // Clean up remaining memory.
326 while (!usedList.IsEmpty()) {
327 FreeBlock(usedList.LastItem(), sizeOfBlocksInCache);
328 }
329 while (!nonCacheList.IsEmpty()) {
330 FreeBlock(nonCacheList.LastItem(), sizeOfNonCacheBlocks);
331 }
332 }
333 }
334 }
335
336
337 /*
338 * Method: BlockCacheExerciseTest::suite()
339 * Descr: This static member function returns a test caller for performing
340 * the "BlockCacheExerciseTest" test.
341 */
suite()342 CppUnit::Test *BlockCacheExerciseTest::suite()
343 {
344 typedef CppUnit::TestCaller<BlockCacheExerciseTest>
345 BlockCacheExerciseTestCaller;
346
347 return(new BlockCacheExerciseTestCaller("BBlockCache::Exercise Test", &BlockCacheExerciseTest::PerformTest));
348 }
349
350
351
352