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"
20 uint64_t block_source_size(struct reftable_block_source
*source
)
22 return source
->ops
->size(source
->arg
);
25 int block_source_read_block(struct reftable_block_source
*source
,
26 struct reftable_block
*dest
, uint64_t off
,
29 int result
= source
->ops
->read_block(source
->arg
, dest
, off
, size
);
30 dest
->source
= *source
;
34 void block_source_close(struct reftable_block_source
*source
)
40 source
->ops
->close(source
->arg
);
44 static struct reftable_reader_offsets
*
45 reader_offsets_for(struct reftable_reader
*r
, uint8_t typ
)
49 return &r
->ref_offsets
;
51 return &r
->log_offsets
;
53 return &r
->obj_offsets
;
58 static int reader_get_block(struct reftable_reader
*r
,
59 struct reftable_block
*dest
, uint64_t off
,
65 if (off
+ sz
> r
->size
) {
69 return block_source_read_block(&r
->source
, dest
, off
, sz
);
72 uint32_t reftable_reader_hash_id(struct reftable_reader
*r
)
77 const char *reader_name(struct reftable_reader
*r
)
82 static int parse_footer(struct reftable_reader
*r
, uint8_t *footer
,
86 uint8_t first_block_typ
;
88 uint32_t computed_crc
;
91 if (memcmp(f
, "REFT", 4)) {
92 err
= REFTABLE_FORMAT_ERROR
;
97 if (memcmp(footer
, header
, header_size(r
->version
))) {
98 err
= REFTABLE_FORMAT_ERROR
;
103 r
->block_size
= get_be24(f
);
106 r
->min_update_index
= get_be64(f
);
108 r
->max_update_index
= get_be64(f
);
111 if (r
->version
== 1) {
112 r
->hash_id
= GIT_SHA1_FORMAT_ID
;
114 r
->hash_id
= get_be32(f
);
115 switch (r
->hash_id
) {
116 case GIT_SHA1_FORMAT_ID
:
118 case GIT_SHA256_FORMAT_ID
:
121 err
= REFTABLE_FORMAT_ERROR
;
127 r
->ref_offsets
.index_offset
= get_be64(f
);
130 r
->obj_offsets
.offset
= get_be64(f
);
133 r
->object_id_len
= r
->obj_offsets
.offset
& ((1 << 5) - 1);
134 r
->obj_offsets
.offset
>>= 5;
136 r
->obj_offsets
.index_offset
= get_be64(f
);
138 r
->log_offsets
.offset
= get_be64(f
);
140 r
->log_offsets
.index_offset
= get_be64(f
);
143 computed_crc
= crc32(0, footer
, f
- footer
);
144 file_crc
= get_be32(f
);
146 if (computed_crc
!= file_crc
) {
147 err
= REFTABLE_FORMAT_ERROR
;
151 first_block_typ
= header
[header_size(r
->version
)];
152 r
->ref_offsets
.is_present
= (first_block_typ
== BLOCK_TYPE_REF
);
153 r
->ref_offsets
.offset
= 0;
154 r
->log_offsets
.is_present
= (first_block_typ
== BLOCK_TYPE_LOG
||
155 r
->log_offsets
.offset
> 0);
156 r
->obj_offsets
.is_present
= r
->obj_offsets
.offset
> 0;
157 if (r
->obj_offsets
.is_present
&& !r
->object_id_len
) {
158 err
= REFTABLE_FORMAT_ERROR
;
167 int init_reader(struct reftable_reader
*r
, struct reftable_block_source
*source
,
170 struct reftable_block footer
= { NULL
};
171 struct reftable_block header
= { NULL
};
173 uint64_t file_size
= block_source_size(source
);
175 /* Need +1 to read type of first block. */
176 uint32_t read_size
= header_size(2) + 1; /* read v2 because it's larger. */
177 memset(r
, 0, sizeof(struct reftable_reader
));
179 if (read_size
> file_size
) {
180 err
= REFTABLE_FORMAT_ERROR
;
184 err
= block_source_read_block(source
, &header
, 0, read_size
);
185 if (err
!= read_size
) {
186 err
= REFTABLE_IO_ERROR
;
190 if (memcmp(header
.data
, "REFT", 4)) {
191 err
= REFTABLE_FORMAT_ERROR
;
194 r
->version
= header
.data
[4];
195 if (r
->version
!= 1 && r
->version
!= 2) {
196 err
= REFTABLE_FORMAT_ERROR
;
200 r
->size
= file_size
- footer_size(r
->version
);
202 r
->name
= xstrdup(name
);
205 err
= block_source_read_block(source
, &footer
, r
->size
,
206 footer_size(r
->version
));
207 if (err
!= footer_size(r
->version
)) {
208 err
= REFTABLE_IO_ERROR
;
212 err
= parse_footer(r
, footer
.data
, header
.data
);
214 reftable_block_done(&footer
);
215 reftable_block_done(&header
);
220 struct reftable_reader
*r
;
223 struct block_iter bi
;
226 #define TABLE_ITER_INIT { \
227 .bi = BLOCK_ITER_INIT \
230 static void table_iter_copy_from(struct table_iter
*dest
,
231 struct table_iter
*src
)
234 dest
->typ
= src
->typ
;
235 dest
->block_off
= src
->block_off
;
236 dest
->is_finished
= src
->is_finished
;
237 block_iter_copy_from(&dest
->bi
, &src
->bi
);
240 static int table_iter_next_in_block(struct table_iter
*ti
,
241 struct reftable_record
*rec
)
243 int res
= block_iter_next(&ti
->bi
, rec
);
244 if (res
== 0 && reftable_record_type(rec
) == BLOCK_TYPE_REF
) {
245 rec
->u
.ref
.update_index
+= ti
->r
->min_update_index
;
251 static void table_iter_block_done(struct table_iter
*ti
)
256 reftable_block_done(&ti
->bi
.br
->block
);
257 FREE_AND_NULL(ti
->bi
.br
);
259 ti
->bi
.last_key
.len
= 0;
263 static int32_t extract_block_size(uint8_t *data
, uint8_t *typ
, uint64_t off
,
269 data
+= header_size(version
);
273 if (reftable_is_block_type(*typ
)) {
274 result
= get_be24(data
+ 1);
279 int reader_init_block_reader(struct reftable_reader
*r
, struct block_reader
*br
,
280 uint64_t next_off
, uint8_t want_typ
)
282 int32_t guess_block_size
= r
->block_size
? r
->block_size
:
284 struct reftable_block block
= { NULL
};
285 uint8_t block_typ
= 0;
287 uint32_t header_off
= next_off
? 0 : header_size(r
->version
);
288 int32_t block_size
= 0;
290 if (next_off
>= r
->size
)
293 err
= reader_get_block(r
, &block
, next_off
, guess_block_size
);
297 block_size
= extract_block_size(block
.data
, &block_typ
, next_off
,
299 if (block_size
< 0) {
303 if (want_typ
!= BLOCK_TYPE_ANY
&& block_typ
!= want_typ
) {
308 if (block_size
> guess_block_size
) {
309 reftable_block_done(&block
);
310 err
= reader_get_block(r
, &block
, next_off
, block_size
);
316 err
= block_reader_init(br
, &block
, header_off
, r
->block_size
,
317 hash_size(r
->hash_id
));
319 reftable_block_done(&block
);
324 static int table_iter_next_block(struct table_iter
*dest
,
325 struct table_iter
*src
)
327 uint64_t next_block_off
= src
->block_off
+ src
->bi
.br
->full_block_size
;
328 struct block_reader br
= { 0 };
332 dest
->typ
= src
->typ
;
333 dest
->block_off
= next_block_off
;
335 err
= reader_init_block_reader(src
->r
, &br
, next_block_off
, src
->typ
);
337 dest
->is_finished
= 1;
343 struct block_reader
*brp
=
344 reftable_malloc(sizeof(struct block_reader
));
347 dest
->is_finished
= 0;
348 block_reader_start(brp
, &dest
->bi
);
353 static int table_iter_next(struct table_iter
*ti
, struct reftable_record
*rec
)
355 if (reftable_record_type(rec
) != ti
->typ
)
356 return REFTABLE_API_ERROR
;
359 struct table_iter next
= TABLE_ITER_INIT
;
361 if (ti
->is_finished
) {
365 err
= table_iter_next_in_block(ti
, rec
);
370 err
= table_iter_next_block(&next
, ti
);
374 table_iter_block_done(ti
);
378 table_iter_copy_from(ti
, &next
);
379 block_iter_close(&next
.bi
);
383 static int table_iter_next_void(void *ti
, struct reftable_record
*rec
)
385 return table_iter_next(ti
, rec
);
388 static void table_iter_close(void *p
)
390 struct table_iter
*ti
= p
;
391 table_iter_block_done(ti
);
392 block_iter_close(&ti
->bi
);
395 static struct reftable_iterator_vtable table_iter_vtable
= {
396 .next
= &table_iter_next_void
,
397 .close
= &table_iter_close
,
400 static void iterator_from_table_iter(struct reftable_iterator
*it
,
401 struct table_iter
*ti
)
405 it
->ops
= &table_iter_vtable
;
408 static int reader_table_iter_at(struct reftable_reader
*r
,
409 struct table_iter
*ti
, uint64_t off
,
412 struct block_reader br
= { 0 };
413 struct block_reader
*brp
= NULL
;
415 int err
= reader_init_block_reader(r
, &br
, off
, typ
);
419 brp
= reftable_malloc(sizeof(struct block_reader
));
422 ti
->typ
= block_reader_type(brp
);
424 block_reader_start(brp
, &ti
->bi
);
428 static int reader_start(struct reftable_reader
*r
, struct table_iter
*ti
,
429 uint8_t typ
, int index
)
431 struct reftable_reader_offsets
*offs
= reader_offsets_for(r
, typ
);
432 uint64_t off
= offs
->offset
;
434 off
= offs
->index_offset
;
438 typ
= BLOCK_TYPE_INDEX
;
441 return reader_table_iter_at(r
, ti
, off
, typ
);
444 static int reader_seek_linear(struct table_iter
*ti
,
445 struct reftable_record
*want
)
447 struct reftable_record rec
=
448 reftable_new_record(reftable_record_type(want
));
449 struct strbuf want_key
= STRBUF_INIT
;
450 struct strbuf got_key
= STRBUF_INIT
;
451 struct table_iter next
= TABLE_ITER_INIT
;
454 reftable_record_key(want
, &want_key
);
457 err
= table_iter_next_block(&next
, ti
);
465 err
= block_reader_first_key(next
.bi
.br
, &got_key
);
469 if (strbuf_cmp(&got_key
, &want_key
) > 0) {
470 table_iter_block_done(&next
);
474 table_iter_block_done(ti
);
475 table_iter_copy_from(ti
, &next
);
478 err
= block_iter_seek(&ti
->bi
, &want_key
);
484 block_iter_close(&next
.bi
);
485 reftable_record_release(&rec
);
486 strbuf_release(&want_key
);
487 strbuf_release(&got_key
);
491 static int reader_seek_indexed(struct reftable_reader
*r
,
492 struct reftable_iterator
*it
,
493 struct reftable_record
*rec
)
495 struct reftable_record want_index
= {
496 .type
= BLOCK_TYPE_INDEX
, .u
.idx
= { .last_key
= STRBUF_INIT
}
498 struct reftable_record index_result
= {
499 .type
= BLOCK_TYPE_INDEX
,
500 .u
.idx
= { .last_key
= STRBUF_INIT
},
502 struct table_iter index_iter
= TABLE_ITER_INIT
;
503 struct table_iter next
= TABLE_ITER_INIT
;
506 reftable_record_key(rec
, &want_index
.u
.idx
.last_key
);
507 err
= reader_start(r
, &index_iter
, reftable_record_type(rec
), 1);
511 err
= reader_seek_linear(&index_iter
, &want_index
);
513 err
= table_iter_next(&index_iter
, &index_result
);
514 table_iter_block_done(&index_iter
);
518 err
= reader_table_iter_at(r
, &next
, index_result
.u
.idx
.offset
,
523 err
= block_iter_seek(&next
.bi
, &want_index
.u
.idx
.last_key
);
527 if (next
.typ
== reftable_record_type(rec
)) {
532 if (next
.typ
!= BLOCK_TYPE_INDEX
) {
533 err
= REFTABLE_FORMAT_ERROR
;
537 table_iter_copy_from(&index_iter
, &next
);
541 struct table_iter empty
= TABLE_ITER_INIT
;
542 struct table_iter
*malloced
=
543 reftable_calloc(sizeof(struct table_iter
));
545 table_iter_copy_from(malloced
, &next
);
546 iterator_from_table_iter(it
, malloced
);
549 block_iter_close(&next
.bi
);
550 table_iter_close(&index_iter
);
551 reftable_record_release(&want_index
);
552 reftable_record_release(&index_result
);
556 static int reader_seek_internal(struct reftable_reader
*r
,
557 struct reftable_iterator
*it
,
558 struct reftable_record
*rec
)
560 struct reftable_reader_offsets
*offs
=
561 reader_offsets_for(r
, reftable_record_type(rec
));
562 uint64_t idx
= offs
->index_offset
;
563 struct table_iter ti
= TABLE_ITER_INIT
;
566 return reader_seek_indexed(r
, it
, rec
);
568 err
= reader_start(r
, &ti
, reftable_record_type(rec
), 0);
571 err
= reader_seek_linear(&ti
, rec
);
575 struct table_iter
*p
=
576 reftable_malloc(sizeof(struct table_iter
));
578 iterator_from_table_iter(it
, p
);
584 static int reader_seek(struct reftable_reader
*r
, struct reftable_iterator
*it
,
585 struct reftable_record
*rec
)
587 uint8_t typ
= reftable_record_type(rec
);
589 struct reftable_reader_offsets
*offs
= reader_offsets_for(r
, typ
);
590 if (!offs
->is_present
) {
591 iterator_set_empty(it
);
595 return reader_seek_internal(r
, it
, rec
);
598 int reftable_reader_seek_ref(struct reftable_reader
*r
,
599 struct reftable_iterator
*it
, const char *name
)
601 struct reftable_record rec
= {
602 .type
= BLOCK_TYPE_REF
,
604 .refname
= (char *)name
,
607 return reader_seek(r
, it
, &rec
);
610 int reftable_reader_seek_log_at(struct reftable_reader
*r
,
611 struct reftable_iterator
*it
, const char *name
,
612 uint64_t update_index
)
614 struct reftable_record rec
= { .type
= BLOCK_TYPE_LOG
,
616 .refname
= (char *)name
,
617 .update_index
= update_index
,
619 return reader_seek(r
, it
, &rec
);
622 int reftable_reader_seek_log(struct reftable_reader
*r
,
623 struct reftable_iterator
*it
, const char *name
)
625 uint64_t max
= ~((uint64_t)0);
626 return reftable_reader_seek_log_at(r
, it
, name
, max
);
629 void reader_close(struct reftable_reader
*r
)
631 block_source_close(&r
->source
);
632 FREE_AND_NULL(r
->name
);
635 int reftable_new_reader(struct reftable_reader
**p
,
636 struct reftable_block_source
*src
, char const *name
)
638 struct reftable_reader
*rd
=
639 reftable_calloc(sizeof(struct reftable_reader
));
640 int err
= init_reader(rd
, src
, name
);
644 block_source_close(src
);
650 void reftable_reader_free(struct reftable_reader
*r
)
658 static int reftable_reader_refs_for_indexed(struct reftable_reader
*r
,
659 struct reftable_iterator
*it
,
662 struct reftable_record want
= {
663 .type
= BLOCK_TYPE_OBJ
,
666 .hash_prefix_len
= r
->object_id_len
,
669 struct reftable_iterator oit
= { NULL
};
670 struct reftable_record got
= {
671 .type
= BLOCK_TYPE_OBJ
,
675 struct indexed_table_ref_iter
*itr
= NULL
;
677 /* Look through the reverse index. */
678 err
= reader_seek(r
, &oit
, &want
);
682 /* read out the reftable_obj_record */
683 err
= iterator_next(&oit
, &got
);
687 if (err
> 0 || memcmp(want
.u
.obj
.hash_prefix
, got
.u
.obj
.hash_prefix
,
689 /* didn't find it; return empty iterator */
690 iterator_set_empty(it
);
695 err
= new_indexed_table_ref_iter(&itr
, r
, oid
, hash_size(r
->hash_id
),
697 got
.u
.obj
.offset_len
);
700 got
.u
.obj
.offsets
= NULL
;
701 iterator_from_indexed_table_ref_iter(it
, itr
);
704 reftable_iterator_destroy(&oit
);
705 reftable_record_release(&got
);
709 static int reftable_reader_refs_for_unindexed(struct reftable_reader
*r
,
710 struct reftable_iterator
*it
,
713 struct table_iter ti_empty
= TABLE_ITER_INIT
;
714 struct table_iter
*ti
= reftable_calloc(sizeof(struct table_iter
));
715 struct filtering_ref_iterator
*filter
= NULL
;
716 struct filtering_ref_iterator empty
= FILTERING_REF_ITERATOR_INIT
;
717 int oid_len
= hash_size(r
->hash_id
);
721 err
= reader_start(r
, ti
, BLOCK_TYPE_REF
, 0);
727 filter
= reftable_malloc(sizeof(struct filtering_ref_iterator
));
730 strbuf_add(&filter
->oid
, oid
, oid_len
);
731 reftable_table_from_reader(&filter
->tab
, r
);
732 filter
->double_check
= 0;
733 iterator_from_table_iter(&filter
->it
, ti
);
735 iterator_from_filtering_ref_iterator(it
, filter
);
739 int reftable_reader_refs_for(struct reftable_reader
*r
,
740 struct reftable_iterator
*it
, uint8_t *oid
)
742 if (r
->obj_offsets
.is_present
)
743 return reftable_reader_refs_for_indexed(r
, it
, oid
);
744 return reftable_reader_refs_for_unindexed(r
, it
, oid
);
747 uint64_t reftable_reader_max_update_index(struct reftable_reader
*r
)
749 return r
->max_update_index
;
752 uint64_t reftable_reader_min_update_index(struct reftable_reader
*r
)
754 return r
->min_update_index
;
757 /* generic table interface. */
759 static int reftable_reader_seek_void(void *tab
, struct reftable_iterator
*it
,
760 struct reftable_record
*rec
)
762 return reader_seek(tab
, it
, rec
);
765 static uint32_t reftable_reader_hash_id_void(void *tab
)
767 return reftable_reader_hash_id(tab
);
770 static uint64_t reftable_reader_min_update_index_void(void *tab
)
772 return reftable_reader_min_update_index(tab
);
775 static uint64_t reftable_reader_max_update_index_void(void *tab
)
777 return reftable_reader_max_update_index(tab
);
780 static struct reftable_table_vtable reader_vtable
= {
781 .seek_record
= reftable_reader_seek_void
,
782 .hash_id
= reftable_reader_hash_id_void
,
783 .min_update_index
= reftable_reader_min_update_index_void
,
784 .max_update_index
= reftable_reader_max_update_index_void
,
787 void reftable_table_from_reader(struct reftable_table
*tab
,
788 struct reftable_reader
*reader
)
791 tab
->ops
= &reader_vtable
;
792 tab
->table_arg
= reader
;
796 int reftable_reader_print_file(const char *tablename
)
798 struct reftable_block_source src
= { NULL
};
799 int err
= reftable_block_source_from_file(&src
, tablename
);
800 struct reftable_reader
*r
= NULL
;
801 struct reftable_table tab
= { NULL
};
805 err
= reftable_new_reader(&r
, &src
, tablename
);
809 reftable_table_from_reader(&tab
, r
);
810 err
= reftable_table_print(&tab
);
812 reftable_reader_free(r
);