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
42 struct 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
59 test_block gBlocks[MAX_BLOCKS];
60 block_cache* gCache;
61 size_t gBlockSize;
62 int32 gTest;
63 int32 gSubTest;
64 const char* gTestName;
65
66
67 void
dump_cache()68 dump_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
81 void
error(int32 line,const char * format,...)82 error(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
99 void
or_block(void * block,int32 value)100 or_block(void* block, int32 value)
101 {
102 int32* data = (int32*)block;
103 *data |= value;
104 }
105
106
107 void
set_block(void * block,int32 value)108 set_block(void* block, int32 value)
109 {
110 int32* data = (int32*)block;
111 *data = value;
112 }
113
114
115 void
reset_block(void * block,int32 index)116 reset_block(void* block, int32 index)
117 {
118 int32* data = (int32*)block;
119 *data = index + 1;
120 }
121
122
123 ssize_t
block_cache_write_pos(int fd,off_t offset,const void * buffer,size_t size)124 block_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
136 ssize_t
block_cache_read_pos(int fd,off_t offset,void * buffer,size_t size)137 block_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
150 void
init_test_blocks()151 init_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
162 void
test_transaction(int32 id,int32 numBlocks,int32 numMainBlocks,int32 numSubBlocks,int32 line)163 test_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
184 void
test_blocks(off_t number,int32 count,int32 line)185 test_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
225 void
stop_test(void)226 stop_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
237 void
start_test(const char * name,bool init=true)238 start_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 */
263 void
basic_test_discard_in_sub(int32 id,bool touchedInMain)264 basic_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
327 void
test_abort_transaction()328 test_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
379 void
test_abort_sub_transaction()380 test_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
475 void
test_block_cache_discard()476 test_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
634 int
main(int argc,char ** argv)635 main(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