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 */
20BlockCacheExerciseTest::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 */
36BlockCacheExerciseTest::~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 */
89void
90BlockCacheExerciseTest::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 */
159void
160BlockCacheExerciseTest::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 */
180void *
181BlockCacheExerciseTest::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 */
214void
215BlockCacheExerciseTest::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 */
249void
250BlockCacheExerciseTest::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 */
288void
289BlockCacheExerciseTest::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 */
342CppUnit::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