reftable/reader.c

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