@leroysheep / LeeRoySheep
Code Commits Pulls CI/CD 81,841
master
bisect jch maint master next seen test todo
c 609 lines 17.1 KB
Raw
1 /*
2 Copyright 2020 Google LLC
3
4 Use of this source code is governed by a BSD-style
5 license that can be found in the LICENSE file or at
6 https://developers.google.com/open-source/licenses/bsd
7 */
8
9 #include "unit-test.h"
10 #include "lib-reftable.h"
11 #include "reftable/block.h"
12 #include "reftable/blocksource.h"
13 #include "reftable/constants.h"
14 #include "reftable/reftable-error.h"
15 #include "strbuf.h"
16
17 static int cl_reftable_write_block(struct reftable_buf *buf,
18 uint8_t block_type,
19 struct reftable_record *recs,
20 size_t nrecs)
21 {
22 struct block_writer writer = {
23 .last_key = REFTABLE_BUF_INIT,
24 };
25 uint8_t block[1024];
26 int block_end;
27
28 cl_must_pass(block_writer_init(&writer, block_type, block, 1024,
29 0, hash_size(REFTABLE_HASH_SHA1)));
30 for (size_t i = 0; i < nrecs; i++)
31 cl_must_pass(block_writer_add(&writer, &recs[i]));
32
33 block_end = block_writer_finish(&writer);
34 cl_assert(block_end > 0);
35
36 cl_must_pass(reftable_buf_add(buf, block, block_end));
37
38 block_writer_release(&writer);
39 return block_end;
40 }
41
42 void test_reftable_block__read_write(void)
43 {
44 const int header_off = 21; /* random */
45 struct reftable_record recs[30];
46 const size_t N = ARRAY_SIZE(recs);
47 const size_t block_size = 1024;
48 struct reftable_block_source source = { 0 };
49 struct block_writer bw = {
50 .last_key = REFTABLE_BUF_INIT,
51 };
52 struct reftable_record rec = {
53 .type = REFTABLE_BLOCK_TYPE_REF,
54 };
55 size_t i = 0;
56 int ret;
57 struct reftable_block block = { 0 };
58 struct block_iter it = BLOCK_ITER_INIT;
59 struct reftable_buf want = REFTABLE_BUF_INIT;
60 struct reftable_buf block_data = REFTABLE_BUF_INIT;
61
62 REFTABLE_CALLOC_ARRAY(block_data.buf, block_size);
63 cl_assert(block_data.buf != NULL);
64 block_data.len = block_size;
65
66 ret = block_writer_init(&bw, REFTABLE_BLOCK_TYPE_REF,
67 (uint8_t *) block_data.buf, block_size,
68 header_off, hash_size(REFTABLE_HASH_SHA1));
69 cl_assert(!ret);
70
71 rec.u.ref.refname = (char *) "";
72 rec.u.ref.value_type = REFTABLE_REF_DELETION;
73 ret = block_writer_add(&bw, &rec);
74 cl_assert_equal_i(ret, REFTABLE_API_ERROR);
75
76 for (i = 0; i < N; i++) {
77 rec.u.ref.refname = xstrfmt("branch%02"PRIuMAX, (uintmax_t)i);
78 rec.u.ref.value_type = REFTABLE_REF_VAL1;
79 memset(rec.u.ref.value.val1, i, REFTABLE_HASH_SIZE_SHA1);
80
81 recs[i] = rec;
82 ret = block_writer_add(&bw, &rec);
83 rec.u.ref.refname = NULL;
84 rec.u.ref.value_type = REFTABLE_REF_DELETION;
85 cl_assert_equal_i(ret, 0);
86 }
87
88 ret = block_writer_finish(&bw);
89 cl_assert(ret > 0);
90
91 block_writer_release(&bw);
92
93 block_source_from_buf(&source ,&block_data);
94 reftable_block_init(&block, &source, 0, header_off, block_size,
95 REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_REF);
96
97 block_iter_init(&it, &block);
98
99 for (i = 0; ; i++) {
100 ret = block_iter_next(&it, &rec);
101 cl_assert(ret >= 0);
102 if (ret > 0) {
103 cl_assert_equal_i(i, N);
104 break;
105 }
106 cl_assert_equal_i(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
107 }
108
109 for (i = 0; i < N; i++) {
110 reftable_record_key(&recs[i], &want);
111
112 ret = block_iter_seek_key(&it, &want);
113 cl_assert_equal_i(ret, 0);
114
115 ret = block_iter_next(&it, &rec);
116 cl_assert_equal_i(ret, 0);
117
118 cl_assert_equal_i(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
119
120 want.len--;
121 ret = block_iter_seek_key(&it, &want);
122 cl_assert_equal_i(ret, 0);
123
124 ret = block_iter_next(&it, &rec);
125 cl_assert_equal_i(ret, 0);
126 cl_assert_equal_i(reftable_record_equal(&recs[10 * (i / 10)], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
127 }
128
129 reftable_block_release(&block);
130 block_iter_close(&it);
131 reftable_record_release(&rec);
132 reftable_buf_release(&want);
133 reftable_buf_release(&block_data);
134 for (i = 0; i < N; i++)
135 reftable_record_release(&recs[i]);
136 }
137
138 void test_reftable_block__log_read_write(void)
139 {
140 const int header_off = 21;
141 struct reftable_record recs[30];
142 const size_t N = ARRAY_SIZE(recs);
143 const size_t block_size = 2048;
144 struct reftable_block_source source = { 0 };
145 struct block_writer bw = {
146 .last_key = REFTABLE_BUF_INIT,
147 };
148 struct reftable_record rec = {
149 .type = REFTABLE_BLOCK_TYPE_LOG,
150 };
151 size_t i = 0;
152 int ret;
153 struct reftable_block block = { 0 };
154 struct block_iter it = BLOCK_ITER_INIT;
155 struct reftable_buf want = REFTABLE_BUF_INIT;
156 struct reftable_buf block_data = REFTABLE_BUF_INIT;
157
158 REFTABLE_CALLOC_ARRAY(block_data.buf, block_size);
159 cl_assert(block_data.buf != NULL);
160 block_data.len = block_size;
161
162 ret = block_writer_init(&bw, REFTABLE_BLOCK_TYPE_LOG, (uint8_t *) block_data.buf, block_size,
163 header_off, hash_size(REFTABLE_HASH_SHA1));
164 cl_assert(!ret);
165
166 for (i = 0; i < N; i++) {
167 rec.u.log.refname = xstrfmt("branch%02"PRIuMAX , (uintmax_t)i);
168 rec.u.log.update_index = i;
169 rec.u.log.value_type = REFTABLE_LOG_UPDATE;
170
171 recs[i] = rec;
172 ret = block_writer_add(&bw, &rec);
173 rec.u.log.refname = NULL;
174 rec.u.log.value_type = REFTABLE_LOG_DELETION;
175 cl_assert_equal_i(ret, 0);
176 }
177
178 ret = block_writer_finish(&bw);
179 cl_assert(ret > 0);
180
181 block_writer_release(&bw);
182
183 block_source_from_buf(&source, &block_data);
184 reftable_block_init(&block, &source, 0, header_off, block_size,
185 REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_LOG);
186
187 block_iter_init(&it, &block);
188
189 for (i = 0; ; i++) {
190 ret = block_iter_next(&it, &rec);
191 cl_assert(ret >= 0);
192 if (ret > 0) {
193 cl_assert_equal_i(i, N);
194 break;
195 }
196 cl_assert_equal_i(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
197 }
198
199 for (i = 0; i < N; i++) {
200 reftable_buf_reset(&want);
201 cl_assert(reftable_buf_addstr(&want, recs[i].u.log.refname) == 0);
202
203 ret = block_iter_seek_key(&it, &want);
204 cl_assert_equal_i(ret, 0);
205
206 ret = block_iter_next(&it, &rec);
207 cl_assert_equal_i(ret, 0);
208
209 cl_assert_equal_i(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
210
211 want.len--;
212 ret = block_iter_seek_key(&it, &want);
213 cl_assert_equal_i(ret, 0);
214
215 ret = block_iter_next(&it, &rec);
216 cl_assert_equal_i(ret, 0);
217 cl_assert_equal_i(reftable_record_equal(&recs[10 * (i / 10)], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
218 }
219
220 reftable_block_release(&block);
221 block_iter_close(&it);
222 reftable_record_release(&rec);
223 reftable_buf_release(&want);
224 reftable_buf_release(&block_data);
225 for (i = 0; i < N; i++)
226 reftable_record_release(&recs[i]);
227 }
228
229 void test_reftable_block__obj_read_write(void)
230 {
231 const int header_off = 21;
232 struct reftable_record recs[30];
233 const size_t N = ARRAY_SIZE(recs);
234 const size_t block_size = 1024;
235 struct reftable_block_source source = { 0 };
236 struct block_writer bw = {
237 .last_key = REFTABLE_BUF_INIT,
238 };
239 struct reftable_record rec = {
240 .type = REFTABLE_BLOCK_TYPE_OBJ,
241 };
242 size_t i = 0;
243 int ret;
244 struct reftable_block block = { 0 };
245 struct block_iter it = BLOCK_ITER_INIT;
246 struct reftable_buf want = REFTABLE_BUF_INIT;
247 struct reftable_buf block_data = REFTABLE_BUF_INIT;
248
249 REFTABLE_CALLOC_ARRAY(block_data.buf, block_size);
250 cl_assert(block_data.buf != NULL);
251 block_data.len = block_size;
252
253 ret = block_writer_init(&bw, REFTABLE_BLOCK_TYPE_OBJ, (uint8_t *) block_data.buf, block_size,
254 header_off, hash_size(REFTABLE_HASH_SHA1));
255 cl_assert(!ret);
256
257 for (i = 0; i < N; i++) {
258 uint8_t bytes[] = { i, i + 1, i + 2, i + 3, i + 5 }, *allocated;
259 DUP_ARRAY(allocated, bytes, ARRAY_SIZE(bytes));
260
261 rec.u.obj.hash_prefix = allocated;
262 rec.u.obj.hash_prefix_len = 5;
263
264 recs[i] = rec;
265 ret = block_writer_add(&bw, &rec);
266 rec.u.obj.hash_prefix = NULL;
267 rec.u.obj.hash_prefix_len = 0;
268 cl_assert_equal_i(ret, 0);
269 }
270
271 ret = block_writer_finish(&bw);
272 cl_assert(ret > 0);
273
274 block_writer_release(&bw);
275
276 block_source_from_buf(&source, &block_data);
277 reftable_block_init(&block, &source, 0, header_off, block_size,
278 REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_OBJ);
279
280 block_iter_init(&it, &block);
281
282 for (i = 0; ; i++) {
283 ret = block_iter_next(&it, &rec);
284 cl_assert(ret >= 0);
285 if (ret > 0) {
286 cl_assert_equal_i(i, N);
287 break;
288 }
289 cl_assert_equal_i(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
290 }
291
292 for (i = 0; i < N; i++) {
293 reftable_record_key(&recs[i], &want);
294
295 ret = block_iter_seek_key(&it, &want);
296 cl_assert_equal_i(ret, 0);
297
298 ret = block_iter_next(&it, &rec);
299 cl_assert_equal_i(ret, 0);
300
301 cl_assert_equal_i(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
302 }
303
304 reftable_block_release(&block);
305 block_iter_close(&it);
306 reftable_record_release(&rec);
307 reftable_buf_release(&want);
308 reftable_buf_release(&block_data);
309 for (i = 0; i < N; i++)
310 reftable_record_release(&recs[i]);
311 }
312
313 void test_reftable_block__ref_read_write(void)
314 {
315 const int header_off = 21;
316 struct reftable_record recs[30];
317 const size_t N = ARRAY_SIZE(recs);
318 const size_t block_size = 1024;
319 struct reftable_block_source source = { 0 };
320 struct block_writer bw = {
321 .last_key = REFTABLE_BUF_INIT,
322 };
323 struct reftable_record rec = {
324 .type = REFTABLE_BLOCK_TYPE_INDEX,
325 .u.idx.last_key = REFTABLE_BUF_INIT,
326 };
327 size_t i = 0;
328 int ret;
329 struct reftable_block block = { 0 };
330 struct block_iter it = BLOCK_ITER_INIT;
331 struct reftable_buf want = REFTABLE_BUF_INIT;
332 struct reftable_buf block_data = REFTABLE_BUF_INIT;
333
334 REFTABLE_CALLOC_ARRAY(block_data.buf, block_size);
335 cl_assert(block_data.buf != NULL);
336 block_data.len = block_size;
337
338 ret = block_writer_init(&bw, REFTABLE_BLOCK_TYPE_INDEX, (uint8_t *) block_data.buf, block_size,
339 header_off, hash_size(REFTABLE_HASH_SHA1));
340 cl_assert(!ret);
341
342 for (i = 0; i < N; i++) {
343 char buf[128];
344
345 snprintf(buf, sizeof(buf), "branch%02"PRIuMAX, (uintmax_t)i);
346
347 reftable_buf_init(&recs[i].u.idx.last_key);
348 recs[i].type = REFTABLE_BLOCK_TYPE_INDEX;
349 cl_assert(!reftable_buf_addstr(&recs[i].u.idx.last_key, buf));
350 recs[i].u.idx.offset = i;
351
352 ret = block_writer_add(&bw, &recs[i]);
353 cl_assert_equal_i(ret, 0);
354 }
355
356 ret = block_writer_finish(&bw);
357 cl_assert(ret > 0);
358
359 block_writer_release(&bw);
360
361 block_source_from_buf(&source, &block_data);
362 reftable_block_init(&block, &source, 0, header_off, block_size,
363 REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_INDEX);
364
365 block_iter_init(&it, &block);
366
367 for (i = 0; ; i++) {
368 ret = block_iter_next(&it, &rec);
369 cl_assert(ret >= 0);
370 if (ret > 0) {
371 cl_assert_equal_i(i, N);
372 break;
373 }
374 cl_assert_equal_i(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
375 }
376
377 for (i = 0; i < N; i++) {
378 reftable_record_key(&recs[i], &want);
379
380 ret = block_iter_seek_key(&it, &want);
381 cl_assert_equal_i(ret, 0);
382
383 ret = block_iter_next(&it, &rec);
384 cl_assert_equal_i(ret, 0);
385
386 cl_assert_equal_i(reftable_record_equal(&recs[i], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
387
388 want.len--;
389 ret = block_iter_seek_key(&it, &want);
390 cl_assert_equal_i(ret, 0);
391
392 ret = block_iter_next(&it, &rec);
393 cl_assert_equal_i(ret, 0);
394 cl_assert_equal_i(reftable_record_equal(&recs[10 * (i / 10)], &rec, REFTABLE_HASH_SIZE_SHA1), 1);
395 }
396
397 reftable_block_release(&block);
398 block_iter_close(&it);
399 reftable_record_release(&rec);
400 reftable_buf_release(&want);
401 reftable_buf_release(&block_data);
402 for (i = 0; i < N; i++)
403 reftable_record_release(&recs[i]);
404 }
405
406 void test_reftable_block__iterator(void)
407 {
408 struct reftable_block_source source = { 0 };
409 struct reftable_record expected_refs[20];
410 struct reftable_ref_record ref = { 0 };
411 struct reftable_iterator it = { 0 };
412 struct reftable_block block = { 0 };
413 struct reftable_buf data = REFTABLE_BUF_INIT;
414 int err;
415
416 for (size_t i = 0; i < ARRAY_SIZE(expected_refs); i++) {
417 expected_refs[i] = (struct reftable_record) {
418 .type = REFTABLE_BLOCK_TYPE_REF,
419 .u.ref = {
420 .value_type = REFTABLE_REF_VAL1,
421 .refname = xstrfmt("refs/heads/branch-%02"PRIuMAX, (uintmax_t)i),
422 },
423 };
424 memset(expected_refs[i].u.ref.value.val1, i, REFTABLE_HASH_SIZE_SHA1);
425 }
426
427 cl_reftable_write_block(&data, REFTABLE_BLOCK_TYPE_REF,
428 expected_refs, ARRAY_SIZE(expected_refs));
429
430 block_source_from_buf(&source, &data);
431 reftable_block_init(&block, &source, 0, 0, data.len,
432 REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_REF);
433
434 err = reftable_block_init_iterator(&block, &it);
435 cl_assert_equal_i(err, 0);
436
437 for (size_t i = 0; ; i++) {
438 err = reftable_iterator_next_ref(&it, &ref);
439 if (err > 0) {
440 cl_assert_equal_i(i, ARRAY_SIZE(expected_refs));
441 break;
442 }
443 cl_assert_equal_i(err, 0);
444
445 cl_assert(reftable_ref_record_equal(&ref,
446 &expected_refs[i].u.ref, REFTABLE_HASH_SIZE_SHA1));
447 }
448
449 err = reftable_iterator_seek_ref(&it, "refs/heads/does-not-exist");
450 cl_assert_equal_i(err, 0);
451 err = reftable_iterator_next_ref(&it, &ref);
452 cl_assert_equal_i(err, 1);
453
454 err = reftable_iterator_seek_ref(&it, "refs/heads/branch-13");
455 cl_assert_equal_i(err, 0);
456 err = reftable_iterator_next_ref(&it, &ref);
457 cl_assert_equal_i(err, 0);
458 cl_assert(reftable_ref_record_equal(&ref,
459 &expected_refs[13].u.ref,REFTABLE_HASH_SIZE_SHA1));
460
461 for (size_t i = 0; i < ARRAY_SIZE(expected_refs); i++)
462 reftable_free(expected_refs[i].u.ref.refname);
463 reftable_ref_record_release(&ref);
464 reftable_iterator_destroy(&it);
465 reftable_block_release(&block);
466 reftable_buf_release(&data);
467 }
468
469 void test_reftable_block__corrupt_log_block_size(void)
470 {
471 struct reftable_block_source source = { 0 };
472 struct reftable_record rec = {
473 .type = REFTABLE_BLOCK_TYPE_LOG,
474 .u.log = {
475 .refname = (char *) "refs/heads/main",
476 .update_index = 1,
477 .value_type = REFTABLE_LOG_UPDATE,
478 },
479 };
480 struct reftable_block block = { 0 };
481 struct reftable_buf data = REFTABLE_BUF_INIT;
482
483 cl_reftable_write_block(&data, REFTABLE_BLOCK_TYPE_LOG, &rec, 1);
484
485 /*
486 * Log blocks store their inflated size as a big-endian 24-bit integer
487 * right after the one-byte block type. Rewrite it to claim a size that
488 * is smaller than the block header.
489 */
490 reftable_put_be24((uint8_t *) data.buf + 1, 1);
491
492 block_source_from_buf(&source, &data);
493 cl_assert_equal_i(reftable_block_init(&block, &source, 0, 0, data.len,
494 REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_LOG),
495 REFTABLE_FORMAT_ERROR);
496
497 reftable_block_release(&block);
498 reftable_buf_release(&data);
499 }
500
501 void test_reftable_block__corrupt_block_size(void)
502 {
503 struct reftable_block_source source = { 0 };
504 struct reftable_record rec = {
505 .type = REFTABLE_BLOCK_TYPE_REF,
506 .u.ref = {
507 .value_type = REFTABLE_REF_VAL1,
508 .refname = (char *) "refs/heads/main",
509 },
510 };
511 struct reftable_block block = { 0 };
512 struct reftable_buf data = REFTABLE_BUF_INIT;
513 uint32_t block_size;
514 unsigned char *p;
515
516 cl_reftable_write_block(&data, REFTABLE_BLOCK_TYPE_REF, &rec, 1);
517
518 /*
519 * The block size is stored as a big-endian 24-bit integer right after
520 * the one-byte block type at the start of the block. Corrupt it to
521 * claim a size that is larger than the data we actually have. Reading
522 * the restart count and restart table relative to such a bogus block
523 * size must not access out-of-bounds memory.
524 */
525 p = (unsigned char *) data.buf + 1;
526 block_size = reftable_get_be24(p);
527 cl_assert_equal_i(block_size, 47);
528 reftable_put_be24(p, block_size + 1);
529
530 block_source_from_buf(&source, &data);
531 cl_assert_equal_i(reftable_block_init(&block, &source, 0, 0, data.len,
532 REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_REF),
533 REFTABLE_FORMAT_ERROR);
534
535 reftable_block_release(&block);
536 reftable_buf_release(&data);
537 }
538
539 void test_reftable_block__corrupt_restart_count(void)
540 {
541 struct reftable_block_source source = { 0 };
542 struct reftable_record rec = {
543 .type = REFTABLE_BLOCK_TYPE_REF,
544 .u.ref = {
545 .value_type = REFTABLE_REF_VAL1,
546 .refname = (char *) "refs/heads/main",
547 },
548 };
549 struct reftable_block block = { 0 };
550 struct reftable_buf data = REFTABLE_BUF_INIT;
551 int block_size;
552
553 block_size = cl_reftable_write_block(&data, REFTABLE_BLOCK_TYPE_REF, &rec, 1);
554
555 /*
556 * Corrupt the restart count to claim a bogus number of restart points.
557 * Note that this would only cause us to perform an out-of-bounds
558 * access when seeking into the block, but we want to refuse such a
559 * block outright.
560 */
561 reftable_put_be16((uint8_t *) data.buf + block_size - 2, 0xffff);
562
563 block_source_from_buf(&source, &data);
564 cl_assert_equal_i(reftable_block_init(&block, &source, 0, 0, data.len,
565 REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_REF),
566 REFTABLE_FORMAT_ERROR);
567
568 reftable_block_release(&block);
569 reftable_buf_release(&data);
570 }
571
572 void test_reftable_block__corrupt_restart_offset(void)
573 {
574 struct reftable_block_source source = { 0 };
575 struct reftable_record rec = {
576 .type = REFTABLE_BLOCK_TYPE_REF,
577 .u.ref = {
578 .value_type = REFTABLE_REF_VAL1,
579 .refname = (char *) "refs/heads/main",
580 },
581 };
582 struct reftable_block block = { 0 };
583 struct block_iter it = BLOCK_ITER_INIT;
584 struct reftable_buf want = REFTABLE_BUF_INIT;
585 struct reftable_buf data = REFTABLE_BUF_INIT;
586
587 cl_reftable_write_block(&data, REFTABLE_BLOCK_TYPE_REF, &rec, 1);
588
589 block_source_from_buf(&source, &data);
590 cl_must_pass(reftable_block_init(&block, &source, 0, 0, data.len,
591 REFTABLE_HASH_SIZE_SHA1, REFTABLE_BLOCK_TYPE_REF));
592
593 /*
594 * Corrupt the first restart offset, stored as a big-endian 24-bit
595 * integer at the start of the restart table, to point past the end of
596 * the records section. Seeking such a block must fail gracefully.
597 */
598 reftable_put_be24((uint8_t *) block.block_data.data + block.restart_off,
599 0xffffff);
600
601 block_iter_init(&it, &block);
602 cl_must_pass(reftable_buf_addstr(&want, "refs/heads/main"));
603 cl_assert_equal_i(block_iter_seek_key(&it, &want), REFTABLE_FORMAT_ERROR);
604
605 reftable_buf_release(&want);
606 block_iter_close(&it);
607 reftable_block_release(&block);
608 reftable_buf_release(&data);
609 }