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 */ 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 */ 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 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 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 * 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 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 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 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 */ 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