2 Copyright 2020 Google LLC
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
13 #include "constants.h"
17 #include "reftable-error.h"
18 #include "reftable-generic.h"
21 uint64_t block_source_size(struct reftable_block_source
*source
)
23 return source
->ops
->size(source
->arg
);
26 int block_source_read_block(struct reftable_block_source
*source
,
27 struct reftable_block
*dest
, uint64_t off
,
30 int result
= source
->ops
->read_block(source
->arg
, dest
, off
, size
);
31 dest
->source
= *source
;
35 void block_source_close(struct reftable_block_source
*source
)
41 source
->ops
->close(source
->arg
);
45 static struct reftable_reader_offsets
*
46 reader_offsets_for(struct reftable_reader
*r
, uint8_t typ
)
50 return &r
->ref_offsets
;
52 return &r
->log_offsets
;
54 return &r
->obj_offsets
;
59 static int reader_get_block(struct reftable_reader
*r
,
60 struct reftable_block
*dest
, uint64_t off
,
66 if (off
+ sz
> r
->size
) {
70 return block_source_read_block(&r
->source
, dest
, off
, sz
);
73 uint32_t reftable_reader_hash_id(struct reftable_reader
*r
)
78 const char *reader_name(struct reftable_reader
*r
)
83 static int parse_footer(struct reftable_reader
*r
, uint8_t *footer
,
87 uint8_t first_block_typ
;
89 uint32_t computed_crc
;
92 if (memcmp(f
, "REFT", 4)) {
93 err
= REFTABLE_FORMAT_ERROR
;
98 if (memcmp(footer
, header
, header_size(r
->version
))) {
99 err
= REFTABLE_FORMAT_ERROR
;
104 r
->block_size
= get_be24(f
);
107 r
->min_update_index
= get_be64(f
);
109 r
->max_update_index
= get_be64(f
);
112 if (r
->version
== 1) {
113 r
->hash_id
= GIT_SHA1_FORMAT_ID
;
115 r
->hash_id
= get_be32(f
);
116 switch (r
->hash_id
) {
117 case GIT_SHA1_FORMAT_ID
:
119 case GIT_SHA256_FORMAT_ID
:
122 err
= REFTABLE_FORMAT_ERROR
;
128 r
->ref_offsets
.index_offset
= get_be64(f
);
131 r
->obj_offsets
.offset
= get_be64(f
);
134 r
->object_id_len
= r
->obj_offsets
.offset
& ((1 << 5) - 1);
135 r
->obj_offsets
.offset
>>= 5;
137 r
->obj_offsets
.index_offset
= get_be64(f
);
139 r
->log_offsets
.offset
= get_be64(f
);
141 r
->log_offsets
.index_offset
= get_be64(f
);
144 computed_crc
= crc32(0, footer
, f
- footer
);
145 file_crc
= get_be32(f
);
147 if (computed_crc
!= file_crc
) {
148 err
= REFTABLE_FORMAT_ERROR
;
152 first_block_typ
= header
[header_size(r
->version
)];
153 r
->ref_offsets
.is_present
= (first_block_typ
== BLOCK_TYPE_REF
);
154 r
->ref_offsets
.offset
= 0;
155 r
->log_offsets
.is_present
= (first_block_typ
== BLOCK_TYPE_LOG
||
156 r
->log_offsets
.offset
> 0);
157 r
->obj_offsets
.is_present
= r
->obj_offsets
.offset
> 0;
163 int init_reader(struct reftable_reader
*r
, struct reftable_block_source
*source
,
166 struct reftable_block footer
= { NULL
};
167 struct reftable_block header
= { NULL
};
169 uint64_t file_size
= block_source_size(source
);
171 /* Need +1 to read type of first block. */
172 uint32_t read_size
= header_size(2) + 1; /* read v2 because it's larger. */
173 memset(r
, 0, sizeof(struct reftable_reader
));
175 if (read_size
> file_size
) {
176 err
= REFTABLE_FORMAT_ERROR
;
180 err
= block_source_read_block(source
, &header
, 0, read_size
);
181 if (err
!= read_size
) {
182 err
= REFTABLE_IO_ERROR
;
186 if (memcmp(header
.data
, "REFT", 4)) {
187 err
= REFTABLE_FORMAT_ERROR
;
190 r
->version
= header
.data
[4];
191 if (r
->version
!= 1 && r
->version
!= 2) {
192 err
= REFTABLE_FORMAT_ERROR
;
196 r
->size
= file_size
- footer_size(r
->version
);
198 r
->name
= xstrdup(name
);
201 err
= block_source_read_block(source
, &footer
, r
->size
,
202 footer_size(r
->version
));
203 if (err
!= footer_size(r
->version
)) {
204 err
= REFTABLE_IO_ERROR
;
208 err
= parse_footer(r
, footer
.data
, header
.data
);
210 reftable_block_done(&footer
);
211 reftable_block_done(&header
);
216 struct reftable_reader
*r
;
219 struct block_iter bi
;
222 #define TABLE_ITER_INIT \
224 .bi = {.last_key = STRBUF_INIT } \
227 static void table_iter_copy_from(struct table_iter
*dest
,
228 struct table_iter
*src
)
231 dest
->typ
= src
->typ
;
232 dest
->block_off
= src
->block_off
;
233 dest
->is_finished
= src
->is_finished
;
234 block_iter_copy_from(&dest
->bi
, &src
->bi
);
237 static int table_iter_next_in_block(struct table_iter
*ti
,
238 struct reftable_record
*rec
)
240 int res
= block_iter_next(&ti
->bi
, rec
);
241 if (res
== 0 && reftable_record_type(rec
) == BLOCK_TYPE_REF
) {
242 ((struct reftable_ref_record
*)rec
->data
)->update_index
+=
243 ti
->r
->min_update_index
;
249 static void table_iter_block_done(struct table_iter
*ti
)
254 reftable_block_done(&ti
->bi
.br
->block
);
255 FREE_AND_NULL(ti
->bi
.br
);
257 ti
->bi
.last_key
.len
= 0;
261 static int32_t extract_block_size(uint8_t *data
, uint8_t *typ
, uint64_t off
,
267 data
+= header_size(version
);
271 if (reftable_is_block_type(*typ
)) {
272 result
= get_be24(data
+ 1);
277 int reader_init_block_reader(struct reftable_reader
*r
, struct block_reader
*br
,
278 uint64_t next_off
, uint8_t want_typ
)
280 int32_t guess_block_size
= r
->block_size
? r
->block_size
:
282 struct reftable_block block
= { NULL
};
283 uint8_t block_typ
= 0;
285 uint32_t header_off
= next_off
? 0 : header_size(r
->version
);
286 int32_t block_size
= 0;
288 if (next_off
>= r
->size
)
291 err
= reader_get_block(r
, &block
, next_off
, guess_block_size
);
295 block_size
= extract_block_size(block
.data
, &block_typ
, next_off
,
297 if (block_size
< 0) {
301 if (want_typ
!= BLOCK_TYPE_ANY
&& block_typ
!= want_typ
) {
306 if (block_size
> guess_block_size
) {
307 reftable_block_done(&block
);
308 err
= reader_get_block(r
, &block
, next_off
, block_size
);
314 err
= block_reader_init(br
, &block
, header_off
, r
->block_size
,
315 hash_size(r
->hash_id
));
317 reftable_block_done(&block
);
322 static int table_iter_next_block(struct table_iter
*dest
,
323 struct table_iter
*src
)
325 uint64_t next_block_off
= src
->block_off
+ src
->bi
.br
->full_block_size
;
326 struct block_reader br
= { 0 };
330 dest
->typ
= src
->typ
;
331 dest
->block_off
= next_block_off
;
333 err
= reader_init_block_reader(src
->r
, &br
, next_block_off
, src
->typ
);
335 dest
->is_finished
= 1;
341 struct block_reader
*brp
=
342 reftable_malloc(sizeof(struct block_reader
));
345 dest
->is_finished
= 0;
346 block_reader_start(brp
, &dest
->bi
);
351 static int table_iter_next(struct table_iter
*ti
, struct reftable_record
*rec
)
353 if (reftable_record_type(rec
) != ti
->typ
)
354 return REFTABLE_API_ERROR
;
357 struct table_iter next
= TABLE_ITER_INIT
;
359 if (ti
->is_finished
) {
363 err
= table_iter_next_in_block(ti
, rec
);
368 err
= table_iter_next_block(&next
, ti
);
372 table_iter_block_done(ti
);
376 table_iter_copy_from(ti
, &next
);
377 block_iter_close(&next
.bi
);
381 static int table_iter_next_void(void *ti
, struct reftable_record
*rec
)
383 return table_iter_next(ti
, rec
);
386 static void table_iter_close(void *p
)
388 struct table_iter
*ti
= p
;
389 table_iter_block_done(ti
);
390 block_iter_close(&ti
->bi
);
393 static struct reftable_iterator_vtable table_iter_vtable
= {
394 .next
= &table_iter_next_void
,
395 .close
= &table_iter_close
,
398 static void iterator_from_table_iter(struct reftable_iterator
*it
,
399 struct table_iter
*ti
)
403 it
->ops
= &table_iter_vtable
;
406 static int reader_table_iter_at(struct reftable_reader
*r
,
407 struct table_iter
*ti
, uint64_t off
,
410 struct block_reader br
= { 0 };
411 struct block_reader
*brp
= NULL
;
413 int err
= reader_init_block_reader(r
, &br
, off
, typ
);
417 brp
= reftable_malloc(sizeof(struct block_reader
));
420 ti
->typ
= block_reader_type(brp
);
422 block_reader_start(brp
, &ti
->bi
);
426 static int reader_start(struct reftable_reader
*r
, struct table_iter
*ti
,
427 uint8_t typ
, int index
)
429 struct reftable_reader_offsets
*offs
= reader_offsets_for(r
, typ
);
430 uint64_t off
= offs
->offset
;
432 off
= offs
->index_offset
;
436 typ
= BLOCK_TYPE_INDEX
;
439 return reader_table_iter_at(r
, ti
, off
, typ
);
442 static int reader_seek_linear(struct reftable_reader
*r
, struct table_iter
*ti
,
443 struct reftable_record
*want
)
445 struct reftable_record rec
=
446 reftable_new_record(reftable_record_type(want
));
447 struct strbuf want_key
= STRBUF_INIT
;
448 struct strbuf got_key
= STRBUF_INIT
;
449 struct table_iter next
= TABLE_ITER_INIT
;
452 reftable_record_key(want
, &want_key
);
455 err
= table_iter_next_block(&next
, ti
);
463 err
= block_reader_first_key(next
.bi
.br
, &got_key
);
467 if (strbuf_cmp(&got_key
, &want_key
) > 0) {
468 table_iter_block_done(&next
);
472 table_iter_block_done(ti
);
473 table_iter_copy_from(ti
, &next
);
476 err
= block_iter_seek(&ti
->bi
, &want_key
);
482 block_iter_close(&next
.bi
);
483 reftable_record_destroy(&rec
);
484 strbuf_release(&want_key
);
485 strbuf_release(&got_key
);
489 static int reader_seek_indexed(struct reftable_reader
*r
,
490 struct reftable_iterator
*it
,
491 struct reftable_record
*rec
)
493 struct reftable_index_record want_index
= { .last_key
= STRBUF_INIT
};
494 struct reftable_record want_index_rec
= { NULL
};
495 struct reftable_index_record index_result
= { .last_key
= STRBUF_INIT
};
496 struct reftable_record index_result_rec
= { NULL
};
497 struct table_iter index_iter
= TABLE_ITER_INIT
;
498 struct table_iter next
= TABLE_ITER_INIT
;
501 reftable_record_key(rec
, &want_index
.last_key
);
502 reftable_record_from_index(&want_index_rec
, &want_index
);
503 reftable_record_from_index(&index_result_rec
, &index_result
);
505 err
= reader_start(r
, &index_iter
, reftable_record_type(rec
), 1);
509 err
= reader_seek_linear(r
, &index_iter
, &want_index_rec
);
511 err
= table_iter_next(&index_iter
, &index_result_rec
);
512 table_iter_block_done(&index_iter
);
516 err
= reader_table_iter_at(r
, &next
, index_result
.offset
, 0);
520 err
= block_iter_seek(&next
.bi
, &want_index
.last_key
);
524 if (next
.typ
== reftable_record_type(rec
)) {
529 if (next
.typ
!= BLOCK_TYPE_INDEX
) {
530 err
= REFTABLE_FORMAT_ERROR
;
534 table_iter_copy_from(&index_iter
, &next
);
538 struct table_iter empty
= TABLE_ITER_INIT
;
539 struct table_iter
*malloced
=
540 reftable_calloc(sizeof(struct table_iter
));
542 table_iter_copy_from(malloced
, &next
);
543 iterator_from_table_iter(it
, malloced
);
546 block_iter_close(&next
.bi
);
547 table_iter_close(&index_iter
);
548 reftable_record_release(&want_index_rec
);
549 reftable_record_release(&index_result_rec
);
553 static int reader_seek_internal(struct reftable_reader
*r
,
554 struct reftable_iterator
*it
,
555 struct reftable_record
*rec
)
557 struct reftable_reader_offsets
*offs
=
558 reader_offsets_for(r
, reftable_record_type(rec
));
559 uint64_t idx
= offs
->index_offset
;
560 struct table_iter ti
= TABLE_ITER_INIT
;
563 return reader_seek_indexed(r
, it
, rec
);
565 err
= reader_start(r
, &ti
, reftable_record_type(rec
), 0);
568 err
= reader_seek_linear(r
, &ti
, rec
);
572 struct table_iter
*p
=
573 reftable_malloc(sizeof(struct table_iter
));
575 iterator_from_table_iter(it
, p
);
581 static int reader_seek(struct reftable_reader
*r
, struct reftable_iterator
*it
,
582 struct reftable_record
*rec
)
584 uint8_t typ
= reftable_record_type(rec
);
586 struct reftable_reader_offsets
*offs
= reader_offsets_for(r
, typ
);
587 if (!offs
->is_present
) {
588 iterator_set_empty(it
);
592 return reader_seek_internal(r
, it
, rec
);
595 int reftable_reader_seek_ref(struct reftable_reader
*r
,
596 struct reftable_iterator
*it
, const char *name
)
598 struct reftable_ref_record ref
= {
599 .refname
= (char *)name
,
601 struct reftable_record rec
= { NULL
};
602 reftable_record_from_ref(&rec
, &ref
);
603 return reader_seek(r
, it
, &rec
);
606 int reftable_reader_seek_log_at(struct reftable_reader
*r
,
607 struct reftable_iterator
*it
, const char *name
,
608 uint64_t update_index
)
610 struct reftable_log_record log
= {
611 .refname
= (char *)name
,
612 .update_index
= update_index
,
614 struct reftable_record rec
= { NULL
};
615 reftable_record_from_log(&rec
, &log
);
616 return reader_seek(r
, it
, &rec
);
619 int reftable_reader_seek_log(struct reftable_reader
*r
,
620 struct reftable_iterator
*it
, const char *name
)
622 uint64_t max
= ~((uint64_t)0);
623 return reftable_reader_seek_log_at(r
, it
, name
, max
);
626 void reader_close(struct reftable_reader
*r
)
628 block_source_close(&r
->source
);
629 FREE_AND_NULL(r
->name
);
632 int reftable_new_reader(struct reftable_reader
**p
,
633 struct reftable_block_source
*src
, char const *name
)
635 struct reftable_reader
*rd
=
636 reftable_calloc(sizeof(struct reftable_reader
));
637 int err
= init_reader(rd
, src
, name
);
641 block_source_close(src
);
647 void reftable_reader_free(struct reftable_reader
*r
)
655 static int reftable_reader_refs_for_indexed(struct reftable_reader
*r
,
656 struct reftable_iterator
*it
,
659 struct reftable_obj_record want
= {
661 .hash_prefix_len
= r
->object_id_len
,
663 struct reftable_record want_rec
= { NULL
};
664 struct reftable_iterator oit
= { NULL
};
665 struct reftable_obj_record got
= { NULL
};
666 struct reftable_record got_rec
= { NULL
};
668 struct indexed_table_ref_iter
*itr
= NULL
;
670 /* Look through the reverse index. */
671 reftable_record_from_obj(&want_rec
, &want
);
672 err
= reader_seek(r
, &oit
, &want_rec
);
676 /* read out the reftable_obj_record */
677 reftable_record_from_obj(&got_rec
, &got
);
678 err
= iterator_next(&oit
, &got_rec
);
683 memcmp(want
.hash_prefix
, got
.hash_prefix
, r
->object_id_len
)) {
684 /* didn't find it; return empty iterator */
685 iterator_set_empty(it
);
690 err
= new_indexed_table_ref_iter(&itr
, r
, oid
, hash_size(r
->hash_id
),
691 got
.offsets
, got
.offset_len
);
695 iterator_from_indexed_table_ref_iter(it
, itr
);
698 reftable_iterator_destroy(&oit
);
699 reftable_record_release(&got_rec
);
703 static int reftable_reader_refs_for_unindexed(struct reftable_reader
*r
,
704 struct reftable_iterator
*it
,
707 struct table_iter ti_empty
= TABLE_ITER_INIT
;
708 struct table_iter
*ti
= reftable_calloc(sizeof(struct table_iter
));
709 struct filtering_ref_iterator
*filter
= NULL
;
710 struct filtering_ref_iterator empty
= FILTERING_REF_ITERATOR_INIT
;
711 int oid_len
= hash_size(r
->hash_id
);
715 err
= reader_start(r
, ti
, BLOCK_TYPE_REF
, 0);
721 filter
= reftable_malloc(sizeof(struct filtering_ref_iterator
));
724 strbuf_add(&filter
->oid
, oid
, oid_len
);
725 reftable_table_from_reader(&filter
->tab
, r
);
726 filter
->double_check
= 0;
727 iterator_from_table_iter(&filter
->it
, ti
);
729 iterator_from_filtering_ref_iterator(it
, filter
);
733 int reftable_reader_refs_for(struct reftable_reader
*r
,
734 struct reftable_iterator
*it
, uint8_t *oid
)
736 if (r
->obj_offsets
.is_present
)
737 return reftable_reader_refs_for_indexed(r
, it
, oid
);
738 return reftable_reader_refs_for_unindexed(r
, it
, oid
);
741 uint64_t reftable_reader_max_update_index(struct reftable_reader
*r
)
743 return r
->max_update_index
;
746 uint64_t reftable_reader_min_update_index(struct reftable_reader
*r
)
748 return r
->min_update_index
;
751 /* generic table interface. */
753 static int reftable_reader_seek_void(void *tab
, struct reftable_iterator
*it
,
754 struct reftable_record
*rec
)
756 return reader_seek(tab
, it
, rec
);
759 static uint32_t reftable_reader_hash_id_void(void *tab
)
761 return reftable_reader_hash_id(tab
);
764 static uint64_t reftable_reader_min_update_index_void(void *tab
)
766 return reftable_reader_min_update_index(tab
);
769 static uint64_t reftable_reader_max_update_index_void(void *tab
)
771 return reftable_reader_max_update_index(tab
);
774 static struct reftable_table_vtable reader_vtable
= {
775 .seek_record
= reftable_reader_seek_void
,
776 .hash_id
= reftable_reader_hash_id_void
,
777 .min_update_index
= reftable_reader_min_update_index_void
,
778 .max_update_index
= reftable_reader_max_update_index_void
,
781 void reftable_table_from_reader(struct reftable_table
*tab
,
782 struct reftable_reader
*reader
)
785 tab
->ops
= &reader_vtable
;
786 tab
->table_arg
= reader
;
790 int reftable_reader_print_file(const char *tablename
)
792 struct reftable_block_source src
= { NULL
};
793 int err
= reftable_block_source_from_file(&src
, tablename
);
794 struct reftable_reader
*r
= NULL
;
795 struct reftable_table tab
= { NULL
};
799 err
= reftable_new_reader(&r
, &src
, tablename
);
803 reftable_table_from_reader(&tab
, r
);
804 err
= reftable_table_print(&tab
);
806 reftable_reader_free(r
);