freshlybakedca.ke
Git fork
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 "table.h"
10
11#include "system.h"
12#include "block.h"
13#include "blocksource.h"
14#include "constants.h"
15#include "iter.h"
16#include "record.h"
17#include "reftable-error.h"
18
19static struct reftable_table_offsets *
20table_offsets_for(struct reftable_table *t, uint8_t typ)
21{
22 switch (typ) {
23 case REFTABLE_BLOCK_TYPE_REF:
24 return &t->ref_offsets;
25 case REFTABLE_BLOCK_TYPE_LOG:
26 return &t->log_offsets;
27 case REFTABLE_BLOCK_TYPE_OBJ:
28 return &t->obj_offsets;
29 }
30 abort();
31}
32
33enum reftable_hash reftable_table_hash_id(struct reftable_table *t)
34{
35 return t->hash_id;
36}
37
38const char *reftable_table_name(struct reftable_table *t)
39{
40 return t->name;
41}
42
43static int parse_footer(struct reftable_table *t, uint8_t *footer,
44 uint8_t *header)
45{
46 uint8_t *f = footer;
47 uint8_t first_block_typ;
48 int err = 0;
49 uint32_t computed_crc;
50 uint32_t file_crc;
51
52 if (memcmp(f, "REFT", 4)) {
53 err = REFTABLE_FORMAT_ERROR;
54 goto done;
55 }
56 f += 4;
57
58 if (memcmp(footer, header, header_size(t->version))) {
59 err = REFTABLE_FORMAT_ERROR;
60 goto done;
61 }
62
63 f++;
64 t->block_size = reftable_get_be24(f);
65
66 f += 3;
67 t->min_update_index = reftable_get_be64(f);
68 f += 8;
69 t->max_update_index = reftable_get_be64(f);
70 f += 8;
71
72 if (t->version == 1) {
73 t->hash_id = REFTABLE_HASH_SHA1;
74 } else {
75 switch (reftable_get_be32(f)) {
76 case REFTABLE_FORMAT_ID_SHA1:
77 t->hash_id = REFTABLE_HASH_SHA1;
78 break;
79 case REFTABLE_FORMAT_ID_SHA256:
80 t->hash_id = REFTABLE_HASH_SHA256;
81 break;
82 default:
83 err = REFTABLE_FORMAT_ERROR;
84 goto done;
85 }
86
87 f += 4;
88 }
89
90 t->ref_offsets.index_offset = reftable_get_be64(f);
91 f += 8;
92
93 t->obj_offsets.offset = reftable_get_be64(f);
94 f += 8;
95
96 t->object_id_len = t->obj_offsets.offset & ((1 << 5) - 1);
97 t->obj_offsets.offset >>= 5;
98
99 t->obj_offsets.index_offset = reftable_get_be64(f);
100 f += 8;
101 t->log_offsets.offset = reftable_get_be64(f);
102 f += 8;
103 t->log_offsets.index_offset = reftable_get_be64(f);
104 f += 8;
105
106 computed_crc = crc32(0, footer, f - footer);
107 file_crc = reftable_get_be32(f);
108 f += 4;
109 if (computed_crc != file_crc) {
110 err = REFTABLE_FORMAT_ERROR;
111 goto done;
112 }
113
114 first_block_typ = header[header_size(t->version)];
115 t->ref_offsets.is_present = (first_block_typ == REFTABLE_BLOCK_TYPE_REF);
116 t->ref_offsets.offset = 0;
117 t->log_offsets.is_present = (first_block_typ == REFTABLE_BLOCK_TYPE_LOG ||
118 t->log_offsets.offset > 0);
119 t->obj_offsets.is_present = t->obj_offsets.offset > 0;
120 if (t->obj_offsets.is_present && !t->object_id_len) {
121 err = REFTABLE_FORMAT_ERROR;
122 goto done;
123 }
124
125 err = 0;
126done:
127 return err;
128}
129
130struct table_iter {
131 struct reftable_table *table;
132 uint8_t typ;
133 uint64_t block_off;
134 struct reftable_block block;
135 struct block_iter bi;
136 int is_finished;
137};
138
139static int table_iter_init(struct table_iter *ti, struct reftable_table *t)
140{
141 struct block_iter bi = BLOCK_ITER_INIT;
142 memset(ti, 0, sizeof(*ti));
143 reftable_table_incref(t);
144 ti->table = t;
145 ti->bi = bi;
146 return 0;
147}
148
149static int table_iter_next_in_block(struct table_iter *ti,
150 struct reftable_record *rec)
151{
152 int res = block_iter_next(&ti->bi, rec);
153 if (res == 0 && reftable_record_type(rec) == REFTABLE_BLOCK_TYPE_REF) {
154 rec->u.ref.update_index += ti->table->min_update_index;
155 }
156
157 return res;
158}
159
160static void table_iter_block_done(struct table_iter *ti)
161{
162 reftable_block_release(&ti->block);
163 block_iter_reset(&ti->bi);
164}
165
166int table_init_block(struct reftable_table *t, struct reftable_block *block,
167 uint64_t next_off, uint8_t want_typ)
168{
169 uint32_t header_off = next_off ? 0 : header_size(t->version);
170 int err;
171
172 if (next_off >= t->size)
173 return 1;
174
175 err = reftable_block_init(block, &t->source, next_off, header_off,
176 t->block_size, hash_size(t->hash_id), want_typ);
177 if (err)
178 reftable_block_release(block);
179 return err;
180}
181
182static void table_iter_close(struct table_iter *ti)
183{
184 table_iter_block_done(ti);
185 block_iter_close(&ti->bi);
186 reftable_table_decref(ti->table);
187}
188
189static int table_iter_next_block(struct table_iter *ti)
190{
191 uint64_t next_block_off = ti->block_off + ti->block.full_block_size;
192 int err;
193
194 err = table_init_block(ti->table, &ti->block, next_block_off, ti->typ);
195 if (err > 0)
196 ti->is_finished = 1;
197 if (err)
198 return err;
199
200 ti->block_off = next_block_off;
201 ti->is_finished = 0;
202 block_iter_init(&ti->bi, &ti->block);
203
204 return 0;
205}
206
207static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)
208{
209 if (reftable_record_type(rec) != ti->typ)
210 return REFTABLE_API_ERROR;
211
212 while (1) {
213 int err;
214
215 if (ti->is_finished)
216 return 1;
217
218 /*
219 * Check whether the current block still has more records. If
220 * so, return it. If the iterator returns positive then the
221 * current block has been exhausted.
222 */
223 err = table_iter_next_in_block(ti, rec);
224 if (err <= 0)
225 return err;
226
227 /*
228 * Otherwise, we need to continue to the next block in the
229 * table and retry. If there are no more blocks then the
230 * iterator is drained.
231 */
232 err = table_iter_next_block(ti);
233 if (err) {
234 ti->is_finished = 1;
235 return err;
236 }
237 }
238}
239
240static int table_iter_seek_to(struct table_iter *ti, uint64_t off, uint8_t typ)
241{
242 int err;
243
244 err = table_init_block(ti->table, &ti->block, off, typ);
245 if (err != 0)
246 return err;
247
248 ti->typ = reftable_block_type(&ti->block);
249 ti->block_off = off;
250 block_iter_init(&ti->bi, &ti->block);
251 ti->is_finished = 0;
252 return 0;
253}
254
255static int table_iter_seek_start(struct table_iter *ti, uint8_t typ, int index)
256{
257 struct reftable_table_offsets *offs = table_offsets_for(ti->table, typ);
258 uint64_t off = offs->offset;
259 if (index) {
260 off = offs->index_offset;
261 if (off == 0) {
262 return 1;
263 }
264 typ = REFTABLE_BLOCK_TYPE_INDEX;
265 }
266
267 return table_iter_seek_to(ti, off, typ);
268}
269
270static int table_iter_seek_linear(struct table_iter *ti,
271 struct reftable_record *want)
272{
273 struct reftable_buf want_key = REFTABLE_BUF_INIT;
274 struct reftable_buf got_key = REFTABLE_BUF_INIT;
275 struct reftable_record rec;
276 int err;
277
278 err = reftable_record_init(&rec, reftable_record_type(want));
279 if (err < 0)
280 goto done;
281
282 err = reftable_record_key(want, &want_key);
283 if (err < 0)
284 goto done;
285
286 /*
287 * First we need to locate the block that must contain our record. To
288 * do so we scan through blocks linearly until we find the first block
289 * whose first key is bigger than our wanted key. Once we have found
290 * that block we know that the key must be contained in the preceding
291 * block.
292 *
293 * This algorithm is somewhat unfortunate because it means that we
294 * always have to seek one block too far and then back up. But as we
295 * can only decode the _first_ key of a block but not its _last_ key we
296 * have no other way to do this.
297 */
298 while (1) {
299 struct table_iter next = *ti;
300
301 /*
302 * We must be careful to not modify underlying data of `ti`
303 * because we may find that `next` does not contain our desired
304 * block, but that `ti` does. In that case, we would discard
305 * `next` and continue with `ti`.
306 *
307 * This also means that we cannot reuse allocated memory for
308 * `next` here. While it would be great if we could, it should
309 * in practice not be too bad given that we should only ever
310 * end up doing linear seeks with at most three blocks. As soon
311 * as we have more than three blocks we would have an index, so
312 * we would not do a linear search there anymore.
313 */
314 memset(&next.block.block_data, 0, sizeof(next.block.block_data));
315 next.block.zstream = NULL;
316 next.block.uncompressed_data = NULL;
317 next.block.uncompressed_cap = 0;
318
319 err = table_iter_next_block(&next);
320 if (err < 0)
321 goto done;
322 if (err > 0)
323 break;
324
325 err = reftable_block_first_key(&next.block, &got_key);
326 if (err < 0)
327 goto done;
328
329 if (reftable_buf_cmp(&got_key, &want_key) > 0) {
330 table_iter_block_done(&next);
331 break;
332 }
333
334 table_iter_block_done(ti);
335 *ti = next;
336 }
337
338 /*
339 * We have located the block that must contain our record, so we seek
340 * the wanted key inside of it. If the block does not contain our key
341 * we know that the corresponding record does not exist.
342 */
343 block_iter_init(&ti->bi, &ti->block);
344 err = block_iter_seek_key(&ti->bi, &want_key);
345 if (err < 0)
346 goto done;
347 err = 0;
348
349done:
350 reftable_record_release(&rec);
351 reftable_buf_release(&want_key);
352 reftable_buf_release(&got_key);
353 return err;
354}
355
356static int table_iter_seek_indexed(struct table_iter *ti,
357 struct reftable_record *rec)
358{
359 struct reftable_record want_index = {
360 .type = REFTABLE_BLOCK_TYPE_INDEX, .u.idx = { .last_key = REFTABLE_BUF_INIT }
361 };
362 struct reftable_record index_result = {
363 .type = REFTABLE_BLOCK_TYPE_INDEX,
364 .u.idx = { .last_key = REFTABLE_BUF_INIT },
365 };
366 int err;
367
368 err = reftable_record_key(rec, &want_index.u.idx.last_key);
369 if (err < 0)
370 goto done;
371
372 /*
373 * The index may consist of multiple levels, where each level may have
374 * multiple index blocks. We start by doing a linear search in the
375 * highest layer that identifies the relevant index block as well as
376 * the record inside that block that corresponds to our wanted key.
377 */
378 err = table_iter_seek_linear(ti, &want_index);
379 if (err < 0)
380 goto done;
381
382 /*
383 * Traverse down the levels until we find a non-index entry.
384 */
385 while (1) {
386 /*
387 * In case we seek a record that does not exist the index iter
388 * will tell us that the iterator is over. This works because
389 * the last index entry of the current level will contain the
390 * last key it knows about. So in case our seeked key is larger
391 * than the last indexed key we know that it won't exist.
392 *
393 * There is one subtlety in the layout of the index section
394 * that makes this work as expected: the highest-level index is
395 * at end of the section and will point backwards and thus we
396 * start reading from the end of the index section, not the
397 * beginning.
398 *
399 * If that wasn't the case and the order was reversed then the
400 * linear seek would seek into the lower levels and traverse
401 * all levels of the index only to find out that the key does
402 * not exist.
403 */
404 err = table_iter_next(ti, &index_result);
405 if (err != 0)
406 goto done;
407
408 err = table_iter_seek_to(ti, index_result.u.idx.offset, 0);
409 if (err != 0)
410 goto done;
411
412 block_iter_init(&ti->bi, &ti->block);
413
414 err = block_iter_seek_key(&ti->bi, &want_index.u.idx.last_key);
415 if (err < 0)
416 goto done;
417
418 if (ti->typ == reftable_record_type(rec)) {
419 err = 0;
420 break;
421 }
422
423 if (ti->typ != REFTABLE_BLOCK_TYPE_INDEX) {
424 err = REFTABLE_FORMAT_ERROR;
425 goto done;
426 }
427 }
428
429done:
430 reftable_record_release(&want_index);
431 reftable_record_release(&index_result);
432 return err;
433}
434
435static int table_iter_seek(struct table_iter *ti,
436 struct reftable_record *want)
437{
438 uint8_t typ = reftable_record_type(want);
439 struct reftable_table_offsets *offs = table_offsets_for(ti->table, typ);
440 int err;
441
442 err = table_iter_seek_start(ti, reftable_record_type(want),
443 !!offs->index_offset);
444 if (err < 0)
445 goto out;
446
447 if (offs->index_offset)
448 err = table_iter_seek_indexed(ti, want);
449 else
450 err = table_iter_seek_linear(ti, want);
451 if (err)
452 goto out;
453
454out:
455 return err;
456}
457
458static int table_iter_seek_void(void *ti, struct reftable_record *want)
459{
460 return table_iter_seek(ti, want);
461}
462
463static int table_iter_next_void(void *ti, struct reftable_record *rec)
464{
465 return table_iter_next(ti, rec);
466}
467
468static void table_iter_close_void(void *ti)
469{
470 table_iter_close(ti);
471}
472
473static struct reftable_iterator_vtable table_iter_vtable = {
474 .seek = &table_iter_seek_void,
475 .next = &table_iter_next_void,
476 .close = &table_iter_close_void,
477};
478
479static void iterator_from_table_iter(struct reftable_iterator *it,
480 struct table_iter *ti)
481{
482 assert(!it->ops);
483 it->iter_arg = ti;
484 it->ops = &table_iter_vtable;
485}
486
487int table_init_iter(struct reftable_table *t,
488 struct reftable_iterator *it,
489 uint8_t typ)
490{
491 struct reftable_table_offsets *offs = table_offsets_for(t, typ);
492
493 if (offs->is_present) {
494 struct table_iter *ti;
495 REFTABLE_ALLOC_ARRAY(ti, 1);
496 if (!ti)
497 return REFTABLE_OUT_OF_MEMORY_ERROR;
498
499 table_iter_init(ti, t);
500 iterator_from_table_iter(it, ti);
501 } else {
502 iterator_set_empty(it);
503 }
504
505 return 0;
506}
507
508int reftable_table_init_ref_iterator(struct reftable_table *t,
509 struct reftable_iterator *it)
510{
511 return table_init_iter(t, it, REFTABLE_BLOCK_TYPE_REF);
512}
513
514int reftable_table_init_log_iterator(struct reftable_table *t,
515 struct reftable_iterator *it)
516{
517 return table_init_iter(t, it, REFTABLE_BLOCK_TYPE_LOG);
518}
519
520int reftable_table_new(struct reftable_table **out,
521 struct reftable_block_source *source, char const *name)
522{
523 struct reftable_block_data footer = { 0 };
524 struct reftable_block_data header = { 0 };
525 struct reftable_table *t;
526 uint64_t file_size = block_source_size(source);
527 uint32_t read_size;
528 ssize_t bytes_read;
529 int err;
530
531 REFTABLE_CALLOC_ARRAY(t, 1);
532 if (!t) {
533 err = REFTABLE_OUT_OF_MEMORY_ERROR;
534 goto done;
535 }
536
537 /*
538 * We need one extra byte to read the type of first block. We also
539 * pretend to always be reading v2 of the format because it is larger.
540 */
541 read_size = header_size(2) + 1;
542 if (read_size > file_size) {
543 err = REFTABLE_FORMAT_ERROR;
544 goto done;
545 }
546
547 bytes_read = block_source_read_data(source, &header, 0, read_size);
548 if (bytes_read < 0 || (size_t)bytes_read != read_size) {
549 err = REFTABLE_IO_ERROR;
550 goto done;
551 }
552
553 if (memcmp(header.data, "REFT", 4)) {
554 err = REFTABLE_FORMAT_ERROR;
555 goto done;
556 }
557 t->version = header.data[4];
558 if (t->version != 1 && t->version != 2) {
559 err = REFTABLE_FORMAT_ERROR;
560 goto done;
561 }
562
563 t->size = file_size - footer_size(t->version);
564 t->source = *source;
565 t->name = reftable_strdup(name);
566 if (!t->name) {
567 err = REFTABLE_OUT_OF_MEMORY_ERROR;
568 goto done;
569 }
570 t->hash_id = 0;
571 t->refcount = 1;
572
573 bytes_read = block_source_read_data(source, &footer, t->size,
574 footer_size(t->version));
575 if (bytes_read < 0 || (size_t)bytes_read != footer_size(t->version)) {
576 err = REFTABLE_IO_ERROR;
577 goto done;
578 }
579
580 err = parse_footer(t, footer.data, header.data);
581 if (err)
582 goto done;
583
584 *out = t;
585
586done:
587 block_source_release_data(&footer);
588 block_source_release_data(&header);
589 if (err) {
590 if (t)
591 reftable_free(t->name);
592 reftable_free(t);
593 block_source_close(source);
594 }
595 return err;
596}
597
598void reftable_table_incref(struct reftable_table *t)
599{
600 t->refcount++;
601}
602
603void reftable_table_decref(struct reftable_table *t)
604{
605 if (!t)
606 return;
607 if (--t->refcount)
608 return;
609 block_source_close(&t->source);
610 REFTABLE_FREE_AND_NULL(t->name);
611 reftable_free(t);
612}
613
614static int reftable_table_refs_for_indexed(struct reftable_table *t,
615 struct reftable_iterator *it,
616 uint8_t *oid)
617{
618 struct reftable_record want = {
619 .type = REFTABLE_BLOCK_TYPE_OBJ,
620 .u.obj = {
621 .hash_prefix = oid,
622 .hash_prefix_len = t->object_id_len,
623 },
624 };
625 struct reftable_iterator oit = { NULL };
626 struct reftable_record got = {
627 .type = REFTABLE_BLOCK_TYPE_OBJ,
628 .u.obj = { 0 },
629 };
630 int err = 0;
631 struct indexed_table_ref_iter *itr = NULL;
632
633 /* Look through the reverse index. */
634 err = table_init_iter(t, &oit, REFTABLE_BLOCK_TYPE_OBJ);
635 if (err < 0)
636 goto done;
637
638 err = iterator_seek(&oit, &want);
639 if (err != 0)
640 goto done;
641
642 /* read out the reftable_obj_record */
643 err = iterator_next(&oit, &got);
644 if (err < 0)
645 goto done;
646
647 if (err > 0 || memcmp(want.u.obj.hash_prefix, got.u.obj.hash_prefix,
648 t->object_id_len)) {
649 /* didn't find it; return empty iterator */
650 iterator_set_empty(it);
651 err = 0;
652 goto done;
653 }
654
655 err = indexed_table_ref_iter_new(&itr, t, oid, hash_size(t->hash_id),
656 got.u.obj.offsets,
657 got.u.obj.offset_len);
658 if (err < 0)
659 goto done;
660 got.u.obj.offsets = NULL;
661 iterator_from_indexed_table_ref_iter(it, itr);
662
663done:
664 reftable_iterator_destroy(&oit);
665 reftable_record_release(&got);
666 return err;
667}
668
669static int reftable_table_refs_for_unindexed(struct reftable_table *t,
670 struct reftable_iterator *it,
671 uint8_t *oid)
672{
673 struct table_iter *ti;
674 struct filtering_ref_iterator *filter = NULL;
675 struct filtering_ref_iterator empty = FILTERING_REF_ITERATOR_INIT;
676 uint32_t oid_len = hash_size(t->hash_id);
677 int err;
678
679 REFTABLE_ALLOC_ARRAY(ti, 1);
680 if (!ti) {
681 err = REFTABLE_OUT_OF_MEMORY_ERROR;
682 goto out;
683 }
684
685 table_iter_init(ti, t);
686 err = table_iter_seek_start(ti, REFTABLE_BLOCK_TYPE_REF, 0);
687 if (err < 0)
688 goto out;
689
690 filter = reftable_malloc(sizeof(*filter));
691 if (!filter) {
692 err = REFTABLE_OUT_OF_MEMORY_ERROR;
693 goto out;
694 }
695 *filter = empty;
696
697 err = reftable_buf_add(&filter->oid, oid, oid_len);
698 if (err < 0)
699 goto out;
700
701 iterator_from_table_iter(&filter->it, ti);
702
703 iterator_from_filtering_ref_iterator(it, filter);
704
705 err = 0;
706
707out:
708 if (err < 0) {
709 if (ti)
710 table_iter_close(ti);
711 reftable_free(ti);
712 }
713 return err;
714}
715
716int reftable_table_refs_for(struct reftable_table *t,
717 struct reftable_iterator *it, uint8_t *oid)
718{
719 if (t->obj_offsets.is_present)
720 return reftable_table_refs_for_indexed(t, it, oid);
721 return reftable_table_refs_for_unindexed(t, it, oid);
722}
723
724uint64_t reftable_table_max_update_index(struct reftable_table *t)
725{
726 return t->max_update_index;
727}
728
729uint64_t reftable_table_min_update_index(struct reftable_table *t)
730{
731 return t->min_update_index;
732}
733
734int reftable_table_iterator_init(struct reftable_table_iterator *it,
735 struct reftable_table *t)
736{
737 struct table_iter *ti;
738 int err;
739
740 REFTABLE_ALLOC_ARRAY(ti, 1);
741 if (!ti)
742 return REFTABLE_OUT_OF_MEMORY_ERROR;
743
744 err = table_iter_init(ti, t);
745 if (err < 0)
746 goto out;
747
748 it->iter_arg = ti;
749 err = 0;
750
751out:
752 if (err < 0)
753 reftable_free(ti);
754 return err;
755}
756
757void reftable_table_iterator_release(struct reftable_table_iterator *it)
758{
759 if (!it->iter_arg)
760 return;
761 table_iter_close(it->iter_arg);
762 reftable_free(it->iter_arg);
763 it->iter_arg = NULL;
764}
765
766int reftable_table_iterator_next(struct reftable_table_iterator *it,
767 const struct reftable_block **out)
768{
769 struct table_iter *ti = it->iter_arg;
770 int err;
771
772 err = table_iter_next_block(ti);
773 if (err)
774 return err;
775
776 *out = &ti->block;
777
778 return 0;
779}