1/*
2 * Copyright 2008-2012, Axel D��rfler, axeld@pinc-software.de.
3 * Distributed under the terms of the MIT License.
4 */
5
6
7#define write_pos	block_cache_write_pos
8#define read_pos	block_cache_read_pos
9
10#include "block_cache.cpp"
11
12#undef write_pos
13#undef read_pos
14
15
16#define MAX_BLOCKS					100
17#define BLOCK_CHANGED_IN_MAIN		(1L << 16)
18#define BLOCK_CHANGED_IN_SUB		(2L << 16)
19#define BLOCK_CHANGED_IN_PREVIOUS	(4L << 16)
20
21#define TEST_BLOCKS(number, count) \
22	test_blocks(number, count, __LINE__)
23#define TEST_TRANSACTION(id, num, mainNum, subNum) \
24	test_transaction(id, num, mainNum, subNum, __LINE__)
25
26#define TEST_BLOCK_DATA(block, number, type) \
27	if ((block)->type ## _data != NULL && gBlocks[(number)]. type == 0) \
28		error(line, "Block %lld: " #type " should be NULL!", (number)); \
29	if ((block)->type ## _data != NULL && gBlocks[(number)]. type != 0 \
30		&& *(int32*)(block)->type ## _data != gBlocks[(number)]. type) { \
31		error(line, "Block %lld: " #type " wrong (0x%lx should be 0x%lx)!", \
32			(number), *(int32*)(block)->type ## _data, \
33			gBlocks[(number)]. type); \
34	}
35
36#define TEST_ASSERT(statement) \
37	if (!(statement)) { \
38		error(__LINE__, "Assertion failed: " #statement); \
39	}
40
41
42struct test_block {
43	int32	current;
44	int32	original;
45	int32	parent;
46	int32	previous_transaction;
47	int32	transaction;
48	bool	unused;
49	bool	is_dirty;
50	bool	discard;
51
52	bool	write;
53
54	bool	read;
55	bool	written;
56	bool	present;
57};
58
59test_block gBlocks[MAX_BLOCKS];
60block_cache* gCache;
61size_t gBlockSize;
62int32 gTest;
63int32 gSubTest;
64const char* gTestName;
65
66
67void
68dump_cache()
69{
70	char cacheString[32];
71	sprintf(cacheString, "%p", gCache);
72	char* argv[4];
73	argv[0] = "dump";
74	argv[1] = "-bt";
75	argv[2] = cacheString;
76	argv[3] = NULL;
77	dump_cache(3, argv);
78}
79
80
81void
82error(int32 line, const char* format, ...)
83{
84	va_list args;
85	va_start(args, format);
86
87	fprintf(stderr, "ERROR IN TEST LINE %ld: ", line);
88	vfprintf(stderr, format, args);
89	fprintf(stderr, "\n");
90
91	va_end(args);
92
93	dump_cache();
94
95	exit(1);
96}
97
98
99void
100or_block(void* block, int32 value)
101{
102	int32* data = (int32*)block;
103	*data |= value;
104}
105
106
107void
108set_block(void* block, int32 value)
109{
110	int32* data = (int32*)block;
111	*data = value;
112}
113
114
115void
116reset_block(void* block, int32 index)
117{
118	int32* data = (int32*)block;
119	*data = index + 1;
120}
121
122
123ssize_t
124block_cache_write_pos(int fd, off_t offset, const void* buffer, size_t size)
125{
126	int32 index = offset / gBlockSize;
127
128	gBlocks[index].written = true;
129	if (!gBlocks[index].write)
130		error(__LINE__, "Block %ld should not be written!\n", index);
131
132	return size;
133}
134
135
136ssize_t
137block_cache_read_pos(int fd, off_t offset, void* buffer, size_t size)
138{
139	int32 index = offset / gBlockSize;
140
141	memset(buffer, 0xcc, size);
142	reset_block(buffer, index);
143	if (!gBlocks[index].read)
144		error(__LINE__, "Block %ld should not be read!\n", index);
145
146	return size;
147}
148
149
150void
151init_test_blocks()
152{
153	memset(gBlocks, 0, sizeof(test_block) * MAX_BLOCKS);
154
155	for (uint32 i = 0; i < MAX_BLOCKS; i++) {
156		gBlocks[i].current = i + 1;
157		gBlocks[i].unused = true;
158	}
159}
160
161
162void
163test_transaction(int32 id, int32 numBlocks, int32 numMainBlocks,
164	int32 numSubBlocks, int32 line)
165{
166	MutexLocker locker(&gCache->lock);
167	cache_transaction* transaction = lookup_transaction(gCache, id);
168
169	if (numBlocks != transaction->num_blocks) {
170		error(line, "Transaction %d has wrong num_blocks (is %d, should be "
171			"%d)!", id, transaction->num_blocks, numBlocks);
172	}
173	if (numMainBlocks != transaction->main_num_blocks) {
174		error(line, "Transaction %d has wrong num_blocks (is %d, should be "
175			"%d)!", id, transaction->main_num_blocks, numMainBlocks);
176	}
177	if (numSubBlocks != transaction->sub_num_blocks) {
178		error(line, "Transaction %d has wrong num_blocks (is %d, should be "
179			"%d)!", id, transaction->sub_num_blocks, numSubBlocks);
180	}
181}
182
183
184void
185test_blocks(off_t number, int32 count, int32 line)
186{
187	printf("  %ld\n", gSubTest++);
188
189	for (int32 i = 0; i < count; i++, number++) {
190		MutexLocker locker(&gCache->lock);
191
192		cached_block* block = (cached_block*)hash_lookup(gCache->hash, &number);
193		if (block == NULL) {
194			if (gBlocks[number].present)
195				error(line, "Block %lld not found!", number);
196			continue;
197		}
198		if (!gBlocks[number].present)
199			error(line, "Block %lld is present, but should not!", number);
200
201		if (block->is_dirty != gBlocks[number].is_dirty) {
202			error(line, "Block %lld: dirty bit differs (is %d should be %d)!",
203				number, block->is_dirty, gBlocks[number].is_dirty);
204		}
205#if 0
206		if (block->unused != gBlocks[number].unused) {
207			error("Block %ld: unused bit differs (%d should be %d)!", number,
208				block->unused, gBlocks[number].unused);
209		}
210#endif
211		if (block->discard != gBlocks[number].discard) {
212			error(line, "Block %lld: discard bit differs (is %d should be %d)!",
213				number, block->discard, gBlocks[number].discard);
214		}
215		if (gBlocks[number].write && !gBlocks[number].written)
216			error(line, "Block %lld: has not been written yet!", number);
217
218		TEST_BLOCK_DATA(block, number, current);
219		TEST_BLOCK_DATA(block, number, original);
220		TEST_BLOCK_DATA(block, number, parent);
221	}
222}
223
224
225void
226stop_test(void)
227{
228	if (gCache == NULL)
229		return;
230	TEST_BLOCKS(0, MAX_BLOCKS);
231
232//	dump_cache();
233	block_cache_delete(gCache, true);
234}
235
236
237void
238start_test(const char* name, bool init = true)
239{
240	if (init) {
241		stop_test();
242
243		gBlockSize = 2048;
244		gCache = (block_cache*)block_cache_create(-1, MAX_BLOCKS, gBlockSize,
245			false);
246
247		init_test_blocks();
248	}
249
250	gTest++;
251	gTestName = name;
252	gSubTest = 1;
253
254	printf("----------- Test %ld%s%s -----------\n", gTest,
255		gTestName[0] ? " - " : "", gTestName);
256}
257
258
259/*!	Changes block 1 in main, block 2 if touchedInMain is \c true.
260	Changes block 0 in sub, discards block 2.
261	Performs two block tests.
262*/
263void
264basic_test_discard_in_sub(int32 id, bool touchedInMain)
265{
266	gBlocks[1].present = true;
267	gBlocks[1].read = true;
268	gBlocks[1].is_dirty = true;
269	gBlocks[1].original = gBlocks[1].current;
270	gBlocks[1].current |= BLOCK_CHANGED_IN_MAIN;
271
272	void* block = block_cache_get_writable(gCache, 1, id);
273	or_block(block, BLOCK_CHANGED_IN_MAIN);
274	block_cache_put(gCache, 1);
275
276	TEST_BLOCKS(0, 2);
277
278	if (touchedInMain) {
279		gBlocks[2].present = true;
280		gBlocks[2].is_dirty = true;
281		gBlocks[2].current |= BLOCK_CHANGED_IN_MAIN;
282
283		block = block_cache_get_empty(gCache, 2, id);
284		reset_block(block, 2);
285		or_block(block, BLOCK_CHANGED_IN_MAIN);
286		block_cache_put(gCache, 2);
287	}
288
289	cache_start_sub_transaction(gCache, id);
290
291	gBlocks[0].present = true;
292	gBlocks[0].read = true;
293	gBlocks[0].is_dirty = true;
294	if ((gBlocks[0].current & BLOCK_CHANGED_IN_MAIN) != 0)
295		gBlocks[0].parent = gBlocks[0].current;
296	else
297		gBlocks[0].original = gBlocks[0].current;
298	gBlocks[0].current |= BLOCK_CHANGED_IN_SUB;
299
300	gBlocks[1].parent = gBlocks[1].current;
301	if (touchedInMain)
302		gBlocks[2].parent = gBlocks[2].current;
303
304	block = block_cache_get_writable(gCache, 0, id);
305	or_block(block, BLOCK_CHANGED_IN_SUB);
306	block_cache_put(gCache, 0);
307
308	gBlocks[2].discard = true;
309
310	block_cache_discard(gCache, 2, 1);
311
312	TEST_BLOCKS(0, 2);
313
314	gBlocks[0].is_dirty = false;
315	gBlocks[0].write = true;
316	gBlocks[1].is_dirty = false;
317	gBlocks[1].write = true;
318	gBlocks[2].present = false;
319	gBlocks[2].write = touchedInMain;
320	gBlocks[2].is_dirty = false;
321}
322
323
324// #pragma mark - Tests
325
326
327void
328test_abort_transaction()
329{
330	start_test("Abort main");
331
332	int32 id = cache_start_transaction(gCache);
333
334	gBlocks[0].present = true;
335	gBlocks[0].read = false;
336	gBlocks[0].write = false;
337	gBlocks[0].is_dirty = true;
338	gBlocks[1].present = true;
339	gBlocks[1].read = true;
340	gBlocks[1].write = false;
341	gBlocks[1].is_dirty = true;
342
343	void* block = block_cache_get_empty(gCache, 0, id);
344	or_block(block, BLOCK_CHANGED_IN_PREVIOUS);
345	gBlocks[0].current = BLOCK_CHANGED_IN_PREVIOUS;
346
347	block = block_cache_get_writable(gCache, 1, id);
348	or_block(block, BLOCK_CHANGED_IN_PREVIOUS);
349	gBlocks[1].original = gBlocks[1].current;
350	gBlocks[1].current |= BLOCK_CHANGED_IN_PREVIOUS;
351
352	block_cache_put(gCache, 0);
353	block_cache_put(gCache, 1);
354
355	cache_end_transaction(gCache, id, NULL, NULL);
356	TEST_BLOCKS(0, 2);
357
358	id = cache_start_transaction(gCache);
359
360	block = block_cache_get_writable(gCache, 0, id);
361	or_block(block, BLOCK_CHANGED_IN_MAIN);
362
363	block = block_cache_get_writable(gCache, 1, id);
364	or_block(block, BLOCK_CHANGED_IN_MAIN);
365
366	block_cache_put(gCache, 0);
367	block_cache_put(gCache, 1);
368
369	cache_abort_transaction(gCache, id);
370
371	gBlocks[0].write = true;
372	gBlocks[0].is_dirty = false;
373	gBlocks[1].write = true;
374	gBlocks[1].is_dirty = false;
375	cache_sync_transaction(gCache, id);
376}
377
378
379void
380test_abort_sub_transaction()
381{
382	start_test("Abort sub");
383
384	int32 id = cache_start_transaction(gCache);
385
386	gBlocks[0].present = true;
387	gBlocks[0].read = false;
388	gBlocks[0].write = false;
389	gBlocks[0].is_dirty = true;
390	gBlocks[1].present = true;
391	gBlocks[1].read = true;
392	gBlocks[1].write = false;
393	gBlocks[1].is_dirty = true;
394
395	void* block = block_cache_get_empty(gCache, 0, id);
396	or_block(block, BLOCK_CHANGED_IN_PREVIOUS);
397	gBlocks[0].current = BLOCK_CHANGED_IN_PREVIOUS;
398
399	block = block_cache_get_writable(gCache, 1, id);
400	or_block(block, BLOCK_CHANGED_IN_PREVIOUS);
401	gBlocks[1].original = gBlocks[1].current;
402	gBlocks[1].current |= BLOCK_CHANGED_IN_PREVIOUS;
403
404	block_cache_put(gCache, 0);
405	block_cache_put(gCache, 1);
406
407	cache_start_sub_transaction(gCache, id);
408
409	gBlocks[0].parent = gBlocks[0].current;
410	gBlocks[1].parent = gBlocks[1].current;
411	TEST_BLOCKS(0, 2);
412
413	block = block_cache_get_writable(gCache, 1, id);
414	or_block(block, BLOCK_CHANGED_IN_MAIN);
415
416	block_cache_put(gCache, 1);
417
418	TEST_TRANSACTION(id, 2, 2, 1);
419	cache_abort_sub_transaction(gCache, id);
420	TEST_TRANSACTION(id, 2, 2, 0);
421
422	gBlocks[0].write = true;
423	gBlocks[0].is_dirty = false;
424	gBlocks[1].write = true;
425	gBlocks[1].is_dirty = false;
426
427	cache_end_transaction(gCache, id, NULL, NULL);
428	cache_sync_transaction(gCache, id);
429
430	start_test("Abort sub with empty block");
431	id = cache_start_transaction(gCache);
432
433	gBlocks[1].present = true;
434	gBlocks[1].read = true;
435
436	block = block_cache_get_writable(gCache, 1, id);
437	or_block(block, BLOCK_CHANGED_IN_PREVIOUS);
438	gBlocks[1].original = gBlocks[1].current;
439	gBlocks[1].current |= BLOCK_CHANGED_IN_PREVIOUS;
440
441	block_cache_put(gCache, 1);
442
443	gBlocks[1].is_dirty = true;
444	TEST_BLOCKS(1, 1);
445
446	TEST_TRANSACTION(id, 1, 0, 0);
447	cache_start_sub_transaction(gCache, id);
448	TEST_TRANSACTION(id, 1, 1, 0);
449
450	gBlocks[0].present = true;
451
452	block = block_cache_get_empty(gCache, 0, id);
453	or_block(block, BLOCK_CHANGED_IN_SUB);
454	gBlocks[0].current = BLOCK_CHANGED_IN_SUB;
455
456	block_cache_put(gCache, 0);
457
458	TEST_TRANSACTION(id, 2, 1, 1);
459	cache_abort_sub_transaction(gCache, id);
460	TEST_TRANSACTION(id, 1, 1, 0);
461
462	gBlocks[0].write = false;
463	gBlocks[0].is_dirty = false;
464	gBlocks[0].parent = 0;
465	gBlocks[0].original = 0;
466	TEST_BLOCKS(0, 1);
467
468	gBlocks[1].write = true;
469	gBlocks[1].is_dirty = false;
470	cache_end_transaction(gCache, id, NULL, NULL);
471	cache_sync_transaction(gCache, id);
472}
473
474
475void
476test_block_cache_discard()
477{
478	// Test transactions and block caches
479
480	start_test("Discard in main");
481
482	int32 id = cache_start_transaction(gCache);
483
484	gBlocks[0].present = true;
485	gBlocks[0].read = true;
486
487	block_cache_get(gCache, 0);
488	block_cache_put(gCache, 0);
489
490	gBlocks[1].present = true;
491	gBlocks[1].read = true;
492	gBlocks[1].write = true;
493
494	void* block = block_cache_get_writable(gCache, 1, id);
495	block_cache_put(gCache, 1);
496
497	gBlocks[2].present = false;
498
499	TEST_TRANSACTION(id, 1, 0, 0);
500	block = block_cache_get_empty(gCache, 2, id);
501	TEST_TRANSACTION(id, 2, 0, 0);
502	block_cache_discard(gCache, 2, 1);
503	block_cache_put(gCache, 2);
504
505	cache_end_transaction(gCache, id, NULL, NULL);
506	TEST_TRANSACTION(id, 1, 0, 0);
507	cache_sync_transaction(gCache, id);
508
509	start_test("Discard in sub");
510
511	id = cache_start_transaction(gCache);
512
513	basic_test_discard_in_sub(id, false);
514	TEST_ASSERT(cache_blocks_in_sub_transaction(gCache, id) == 1);
515
516	cache_end_transaction(gCache, id, NULL, NULL);
517	cache_sync_transaction(gCache, id);
518
519	gBlocks[0].is_dirty = false;
520	gBlocks[1].is_dirty = false;
521
522	start_test("Discard in sub, present in main");
523
524	id = cache_start_transaction(gCache);
525
526	basic_test_discard_in_sub(id, true);
527
528	cache_end_transaction(gCache, id, NULL, NULL);
529	cache_sync_transaction(gCache, id);
530
531	gBlocks[0].is_dirty = false;
532	gBlocks[1].is_dirty = false;
533
534	start_test("Discard in sub, changed in main, abort sub");
535
536	id = cache_start_transaction(gCache);
537
538	basic_test_discard_in_sub(id, true);
539	TEST_ASSERT(cache_blocks_in_sub_transaction(gCache, id) == 1);
540
541	gBlocks[0].current &= ~BLOCK_CHANGED_IN_SUB;
542	gBlocks[0].is_dirty = false;
543	gBlocks[0].write = false;
544	gBlocks[1].write = false;
545	gBlocks[1].is_dirty = true;
546	gBlocks[2].present = true;
547	gBlocks[2].is_dirty = true;
548	gBlocks[2].write = false;
549	gBlocks[2].discard = false;
550	cache_abort_sub_transaction(gCache, id);
551	TEST_BLOCKS(0, 2);
552
553	gBlocks[1].is_dirty = false;
554	gBlocks[1].write = true;
555	gBlocks[2].is_dirty = false;
556	gBlocks[2].write = true;
557	cache_end_transaction(gCache, id, NULL, NULL);
558	cache_sync_transaction(gCache, id);
559
560	start_test("Discard in sub, changed in main, new sub");
561
562	id = cache_start_transaction(gCache);
563
564	basic_test_discard_in_sub(id, true);
565
566	cache_start_sub_transaction(gCache, id);
567	cache_end_transaction(gCache, id, NULL, NULL);
568	cache_sync_transaction(gCache, id);
569
570	start_test("Discard in sub, changed in main, detach sub");
571
572	id = cache_start_transaction(gCache);
573
574	basic_test_discard_in_sub(id, true);
575
576	id = cache_detach_sub_transaction(gCache, id, NULL, NULL);
577
578	gBlocks[0].is_dirty = true;
579	gBlocks[0].write = false;
580	gBlocks[1].is_dirty = true;
581	gBlocks[1].write = false;
582
583	TEST_BLOCKS(0, 2);
584
585	gBlocks[0].is_dirty = false;
586	gBlocks[0].write = true;
587	gBlocks[1].is_dirty = false;
588	gBlocks[1].write = true;
589
590	cache_end_transaction(gCache, id, NULL, NULL);
591	cache_sync_transaction(gCache, id);
592
593	start_test("Discard in sub, all changed in main, detach sub");
594
595	id = cache_start_transaction(gCache);
596
597	gBlocks[0].present = true;
598	gBlocks[0].read = true;
599	gBlocks[0].is_dirty = true;
600	gBlocks[0].original = gBlocks[0].current;
601	gBlocks[0].current |= BLOCK_CHANGED_IN_MAIN;
602
603	block = block_cache_get_writable(gCache, 0, id);
604	or_block(block, BLOCK_CHANGED_IN_MAIN);
605	block_cache_put(gCache, 0);
606
607	basic_test_discard_in_sub(id, true);
608
609	id = cache_detach_sub_transaction(gCache, id, NULL, NULL);
610
611	gBlocks[0].is_dirty = true;
612	gBlocks[0].write = false;
613	gBlocks[0].original |= BLOCK_CHANGED_IN_MAIN;
614	gBlocks[1].is_dirty = true;
615	gBlocks[1].write = false;
616
617	TEST_BLOCKS(0, 2);
618
619	gBlocks[0].is_dirty = false;
620	gBlocks[0].write = true;
621	gBlocks[1].is_dirty = false;
622	gBlocks[1].write = true;
623
624	cache_end_transaction(gCache, id, NULL, NULL);
625	cache_sync_transaction(gCache, id);
626
627	stop_test();
628}
629
630
631// #pragma mark -
632
633
634int
635main(int argc, char** argv)
636{
637	block_cache_init();
638
639	// TODO: test transaction-less block caches
640	// TODO: test read-only block caches
641	test_abort_transaction();
642	test_abort_sub_transaction();
643	test_block_cache_discard();
644	return 0;
645}
646