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