| 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 | |
| 19 | static struct reftable_table_offsets * |
| 20 | table_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 | |
| 33 | enum reftable_hash reftable_table_hash_id(struct reftable_table *t) |
| 34 | { |
| 35 | return t->hash_id; |
| 36 | } |
| 37 | |
| 38 | const char *reftable_table_name(struct reftable_table *t) |
| 39 | { |
| 40 | return t->name; |
| 41 | } |
| 42 | |
| 43 | static 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; |
| 126 | done: |
| 127 | return err; |
| 128 | } |
| 129 | |
| 130 | struct 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 | |
| 139 | static 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 | |
| 149 | static 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 | |
| 160 | static void table_iter_block_done(struct table_iter *ti) |
| 161 | { |
| 162 | reftable_block_release(&ti->block); |
| 163 | block_iter_reset(&ti->bi); |
| 164 | } |
| 165 | |
| 166 | int 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 | |
| 182 | static 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 | |
| 189 | static 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 | |
| 207 | static 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 | |
| 240 | static 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 REFTABLE_FORMAT_ERROR; |
| 247 | if (err != 0) |
| 248 | return err; |
| 249 | |
| 250 | ti->typ = reftable_block_type(&ti->block); |
| 251 | ti->block_off = off; |
| 252 | block_iter_init(&ti->bi, &ti->block); |
| 253 | ti->is_finished = 0; |
| 254 | return 0; |
| 255 | } |
| 256 | |
| 257 | static int table_iter_seek_start(struct table_iter *ti, uint8_t typ, int index) |
| 258 | { |
| 259 | struct reftable_table_offsets *offs = table_offsets_for(ti->table, typ); |
| 260 | uint64_t off = offs->offset; |
| 261 | if (index) { |
| 262 | off = offs->index_offset; |
| 263 | if (off == 0) { |
| 264 | return 1; |
| 265 | } |
| 266 | typ = REFTABLE_BLOCK_TYPE_INDEX; |
| 267 | } |
| 268 | |
| 269 | return table_iter_seek_to(ti, off, typ); |
| 270 | } |
| 271 | |
| 272 | static int table_iter_seek_linear(struct table_iter *ti, |
| 273 | struct reftable_record *want) |
| 274 | { |
| 275 | struct reftable_buf want_key = REFTABLE_BUF_INIT; |
| 276 | struct reftable_buf got_key = REFTABLE_BUF_INIT; |
| 277 | struct reftable_record rec; |
| 278 | int err; |
| 279 | |
| 280 | err = reftable_record_init(&rec, reftable_record_type(want)); |
| 281 | if (err < 0) |
| 282 | goto done; |
| 283 | |
| 284 | err = reftable_record_key(want, &want_key); |
| 285 | if (err < 0) |
| 286 | goto done; |
| 287 | |
| 288 | /* |
| 289 | * First we need to locate the block that must contain our record. To |
| 290 | * do so we scan through blocks linearly until we find the first block |
| 291 | * whose first key is bigger than our wanted key. Once we have found |
| 292 | * that block we know that the key must be contained in the preceding |
| 293 | * block. |
| 294 | * |
| 295 | * This algorithm is somewhat unfortunate because it means that we |
| 296 | * always have to seek one block too far and then back up. But as we |
| 297 | * can only decode the _first_ key of a block but not its _last_ key we |
| 298 | * have no other way to do this. |
| 299 | */ |
| 300 | while (1) { |
| 301 | struct table_iter next = *ti; |
| 302 | |
| 303 | /* |
| 304 | * We must be careful to not modify underlying data of `ti` |
| 305 | * because we may find that `next` does not contain our desired |
| 306 | * block, but that `ti` does. In that case, we would discard |
| 307 | * `next` and continue with `ti`. |
| 308 | * |
| 309 | * This also means that we cannot reuse allocated memory for |
| 310 | * `next` here. While it would be great if we could, it should |
| 311 | * in practice not be too bad given that we should only ever |
| 312 | * end up doing linear seeks with at most three blocks. As soon |
| 313 | * as we have more than three blocks we would have an index, so |
| 314 | * we would not do a linear search there anymore. |
| 315 | */ |
| 316 | memset(&next.block.block_data, 0, sizeof(next.block.block_data)); |
| 317 | next.block.zstream = NULL; |
| 318 | next.block.uncompressed_data = NULL; |
| 319 | next.block.uncompressed_cap = 0; |
| 320 | |
| 321 | err = table_iter_next_block(&next); |
| 322 | if (err < 0) |
| 323 | goto done; |
| 324 | if (err > 0) |
| 325 | break; |
| 326 | |
| 327 | err = reftable_block_first_key(&next.block, &got_key); |
| 328 | if (err < 0) |
| 329 | goto done; |
| 330 | |
| 331 | if (reftable_buf_cmp(&got_key, &want_key) > 0) { |
| 332 | table_iter_block_done(&next); |
| 333 | break; |
| 334 | } |
| 335 | |
| 336 | table_iter_block_done(ti); |
| 337 | *ti = next; |
| 338 | } |
| 339 | |
| 340 | /* |
| 341 | * We have located the block that must contain our record, so we seek |
| 342 | * the wanted key inside of it. If the block does not contain our key |
| 343 | * we know that the corresponding record does not exist. |
| 344 | */ |
| 345 | block_iter_init(&ti->bi, &ti->block); |
| 346 | err = block_iter_seek_key(&ti->bi, &want_key); |
| 347 | if (err < 0) |
| 348 | goto done; |
| 349 | err = 0; |
| 350 | |
| 351 | done: |
| 352 | reftable_record_release(&rec); |
| 353 | reftable_buf_release(&want_key); |
| 354 | reftable_buf_release(&got_key); |
| 355 | return err; |
| 356 | } |
| 357 | |
| 358 | static int table_iter_seek_indexed(struct table_iter *ti, |
| 359 | struct reftable_record *rec) |
| 360 | { |
| 361 | struct reftable_record want_index = { |
| 362 | .type = REFTABLE_BLOCK_TYPE_INDEX, .u.idx = { .last_key = REFTABLE_BUF_INIT } |
| 363 | }; |
| 364 | struct reftable_record index_result = { |
| 365 | .type = REFTABLE_BLOCK_TYPE_INDEX, |
| 366 | .u.idx = { .last_key = REFTABLE_BUF_INIT }, |
| 367 | }; |
| 368 | int err; |
| 369 | |
| 370 | err = reftable_record_key(rec, &want_index.u.idx.last_key); |
| 371 | if (err < 0) |
| 372 | goto done; |
| 373 | |
| 374 | /* |
| 375 | * The index may consist of multiple levels, where each level may have |
| 376 | * multiple index blocks. We start by doing a linear search in the |
| 377 | * highest layer that identifies the relevant index block as well as |
| 378 | * the record inside that block that corresponds to our wanted key. |
| 379 | */ |
| 380 | err = table_iter_seek_linear(ti, &want_index); |
| 381 | if (err < 0) |
| 382 | goto done; |
| 383 | |
| 384 | /* |
| 385 | * Traverse down the levels until we find a non-index entry. |
| 386 | */ |
| 387 | while (1) { |
| 388 | /* |
| 389 | * In case we seek a record that does not exist the index iter |
| 390 | * will tell us that the iterator is over. This works because |
| 391 | * the last index entry of the current level will contain the |
| 392 | * last key it knows about. So in case our seeked key is larger |
| 393 | * than the last indexed key we know that it won't exist. |
| 394 | * |
| 395 | * There is one subtlety in the layout of the index section |
| 396 | * that makes this work as expected: the highest-level index is |
| 397 | * at end of the section and will point backwards and thus we |
| 398 | * start reading from the end of the index section, not the |
| 399 | * beginning. |
| 400 | * |
| 401 | * If that wasn't the case and the order was reversed then the |
| 402 | * linear seek would seek into the lower levels and traverse |
| 403 | * all levels of the index only to find out that the key does |
| 404 | * not exist. |
| 405 | */ |
| 406 | err = table_iter_next(ti, &index_result); |
| 407 | if (err != 0) |
| 408 | goto done; |
| 409 | |
| 410 | err = table_iter_seek_to(ti, index_result.u.idx.offset, 0); |
| 411 | if (err != 0) |
| 412 | goto done; |
| 413 | |
| 414 | block_iter_init(&ti->bi, &ti->block); |
| 415 | |
| 416 | err = block_iter_seek_key(&ti->bi, &want_index.u.idx.last_key); |
| 417 | if (err < 0) |
| 418 | goto done; |
| 419 | |
| 420 | if (ti->typ == reftable_record_type(rec)) { |
| 421 | err = 0; |
| 422 | break; |
| 423 | } |
| 424 | |
| 425 | if (ti->typ != REFTABLE_BLOCK_TYPE_INDEX) { |
| 426 | err = REFTABLE_FORMAT_ERROR; |
| 427 | goto done; |
| 428 | } |
| 429 | } |
| 430 | |
| 431 | done: |
| 432 | reftable_record_release(&want_index); |
| 433 | reftable_record_release(&index_result); |
| 434 | return err; |
| 435 | } |
| 436 | |
| 437 | static int table_iter_seek(struct table_iter *ti, |
| 438 | struct reftable_record *want) |
| 439 | { |
| 440 | uint8_t typ = reftable_record_type(want); |
| 441 | struct reftable_table_offsets *offs = table_offsets_for(ti->table, typ); |
| 442 | int err; |
| 443 | |
| 444 | err = table_iter_seek_start(ti, reftable_record_type(want), |
| 445 | !!offs->index_offset); |
| 446 | if (err < 0) |
| 447 | goto out; |
| 448 | |
| 449 | if (offs->index_offset) |
| 450 | err = table_iter_seek_indexed(ti, want); |
| 451 | else |
| 452 | err = table_iter_seek_linear(ti, want); |
| 453 | if (err) |
| 454 | goto out; |
| 455 | |
| 456 | out: |
| 457 | return err; |
| 458 | } |
| 459 | |
| 460 | static int table_iter_seek_void(void *ti, struct reftable_record *want) |
| 461 | { |
| 462 | return table_iter_seek(ti, want); |
| 463 | } |
| 464 | |
| 465 | static int table_iter_next_void(void *ti, struct reftable_record *rec) |
| 466 | { |
| 467 | return table_iter_next(ti, rec); |
| 468 | } |
| 469 | |
| 470 | static void table_iter_close_void(void *ti) |
| 471 | { |
| 472 | table_iter_close(ti); |
| 473 | } |
| 474 | |
| 475 | static struct reftable_iterator_vtable table_iter_vtable = { |
| 476 | .seek = &table_iter_seek_void, |
| 477 | .next = &table_iter_next_void, |
| 478 | .close = &table_iter_close_void, |
| 479 | }; |
| 480 | |
| 481 | static void iterator_from_table_iter(struct reftable_iterator *it, |
| 482 | struct table_iter *ti) |
| 483 | { |
| 484 | assert(!it->ops); |
| 485 | it->iter_arg = ti; |
| 486 | it->ops = &table_iter_vtable; |
| 487 | } |
| 488 | |
| 489 | int table_init_iter(struct reftable_table *t, |
| 490 | struct reftable_iterator *it, |
| 491 | uint8_t typ) |
| 492 | { |
| 493 | struct reftable_table_offsets *offs = table_offsets_for(t, typ); |
| 494 | |
| 495 | if (offs->is_present) { |
| 496 | struct table_iter *ti; |
| 497 | REFTABLE_ALLOC_ARRAY(ti, 1); |
| 498 | if (!ti) |
| 499 | return REFTABLE_OUT_OF_MEMORY_ERROR; |
| 500 | |
| 501 | table_iter_init(ti, t); |
| 502 | iterator_from_table_iter(it, ti); |
| 503 | } else { |
| 504 | iterator_set_empty(it); |
| 505 | } |
| 506 | |
| 507 | return 0; |
| 508 | } |
| 509 | |
| 510 | int reftable_table_init_ref_iterator(struct reftable_table *t, |
| 511 | struct reftable_iterator *it) |
| 512 | { |
| 513 | return table_init_iter(t, it, REFTABLE_BLOCK_TYPE_REF); |
| 514 | } |
| 515 | |
| 516 | int reftable_table_init_log_iterator(struct reftable_table *t, |
| 517 | struct reftable_iterator *it) |
| 518 | { |
| 519 | return table_init_iter(t, it, REFTABLE_BLOCK_TYPE_LOG); |
| 520 | } |
| 521 | |
| 522 | int reftable_table_new(struct reftable_table **out, |
| 523 | struct reftable_block_source *source, char const *name) |
| 524 | { |
| 525 | struct reftable_block_data footer = { 0 }; |
| 526 | struct reftable_block_data header = { 0 }; |
| 527 | struct reftable_table *t; |
| 528 | uint64_t file_size = block_source_size(source); |
| 529 | uint32_t read_size; |
| 530 | ssize_t bytes_read; |
| 531 | int err; |
| 532 | |
| 533 | REFTABLE_CALLOC_ARRAY(t, 1); |
| 534 | if (!t) { |
| 535 | err = REFTABLE_OUT_OF_MEMORY_ERROR; |
| 536 | goto done; |
| 537 | } |
| 538 | |
| 539 | /* |
| 540 | * We need one extra byte to read the type of first block. We also |
| 541 | * pretend to always be reading v2 of the format because it is larger. |
| 542 | */ |
| 543 | read_size = header_size(2) + 1; |
| 544 | if (read_size > file_size) { |
| 545 | err = REFTABLE_FORMAT_ERROR; |
| 546 | goto done; |
| 547 | } |
| 548 | |
| 549 | bytes_read = block_source_read_data(source, &header, 0, read_size); |
| 550 | if (bytes_read < 0 || (size_t)bytes_read != read_size) { |
| 551 | err = REFTABLE_IO_ERROR; |
| 552 | goto done; |
| 553 | } |
| 554 | |
| 555 | if (memcmp(header.data, "REFT", 4)) { |
| 556 | err = REFTABLE_FORMAT_ERROR; |
| 557 | goto done; |
| 558 | } |
| 559 | t->version = header.data[4]; |
| 560 | if (t->version != 1 && t->version != 2) { |
| 561 | err = REFTABLE_FORMAT_ERROR; |
| 562 | goto done; |
| 563 | } |
| 564 | |
| 565 | if (file_size < header_size(t->version) + footer_size(t->version)) { |
| 566 | err = REFTABLE_FORMAT_ERROR; |
| 567 | goto done; |
| 568 | } |
| 569 | |
| 570 | t->size = file_size - footer_size(t->version); |
| 571 | t->source = *source; |
| 572 | t->name = reftable_strdup(name); |
| 573 | if (!t->name) { |
| 574 | err = REFTABLE_OUT_OF_MEMORY_ERROR; |
| 575 | goto done; |
| 576 | } |
| 577 | t->hash_id = 0; |
| 578 | t->refcount = 1; |
| 579 | |
| 580 | bytes_read = block_source_read_data(source, &footer, t->size, |
| 581 | footer_size(t->version)); |
| 582 | if (bytes_read < 0 || (size_t)bytes_read != footer_size(t->version)) { |
| 583 | err = REFTABLE_IO_ERROR; |
| 584 | goto done; |
| 585 | } |
| 586 | |
| 587 | err = parse_footer(t, footer.data, header.data); |
| 588 | if (err) |
| 589 | goto done; |
| 590 | |
| 591 | *out = t; |
| 592 | |
| 593 | done: |
| 594 | block_source_release_data(&footer); |
| 595 | block_source_release_data(&header); |
| 596 | if (err) { |
| 597 | if (t) |
| 598 | reftable_free(t->name); |
| 599 | reftable_free(t); |
| 600 | block_source_close(source); |
| 601 | } |
| 602 | return err; |
| 603 | } |
| 604 | |
| 605 | void reftable_table_incref(struct reftable_table *t) |
| 606 | { |
| 607 | t->refcount++; |
| 608 | } |
| 609 | |
| 610 | void reftable_table_decref(struct reftable_table *t) |
| 611 | { |
| 612 | if (!t) |
| 613 | return; |
| 614 | if (--t->refcount) |
| 615 | return; |
| 616 | block_source_close(&t->source); |
| 617 | REFTABLE_FREE_AND_NULL(t->name); |
| 618 | reftable_free(t); |
| 619 | } |
| 620 | |
| 621 | static int reftable_table_refs_for_indexed(struct reftable_table *t, |
| 622 | struct reftable_iterator *it, |
| 623 | uint8_t *oid) |
| 624 | { |
| 625 | struct reftable_record want = { |
| 626 | .type = REFTABLE_BLOCK_TYPE_OBJ, |
| 627 | .u.obj = { |
| 628 | .hash_prefix = oid, |
| 629 | .hash_prefix_len = t->object_id_len, |
| 630 | }, |
| 631 | }; |
| 632 | struct reftable_iterator oit = { NULL }; |
| 633 | struct reftable_record got = { |
| 634 | .type = REFTABLE_BLOCK_TYPE_OBJ, |
| 635 | .u.obj = { 0 }, |
| 636 | }; |
| 637 | int err = 0; |
| 638 | struct indexed_table_ref_iter *itr = NULL; |
| 639 | |
| 640 | /* Look through the reverse index. */ |
| 641 | err = table_init_iter(t, &oit, REFTABLE_BLOCK_TYPE_OBJ); |
| 642 | if (err < 0) |
| 643 | goto done; |
| 644 | |
| 645 | err = iterator_seek(&oit, &want); |
| 646 | if (err != 0) |
| 647 | goto done; |
| 648 | |
| 649 | /* read out the reftable_obj_record */ |
| 650 | err = iterator_next(&oit, &got); |
| 651 | if (err < 0) |
| 652 | goto done; |
| 653 | |
| 654 | if (err > 0 || memcmp(want.u.obj.hash_prefix, got.u.obj.hash_prefix, |
| 655 | t->object_id_len)) { |
| 656 | /* didn't find it; return empty iterator */ |
| 657 | iterator_set_empty(it); |
| 658 | err = 0; |
| 659 | goto done; |
| 660 | } |
| 661 | |
| 662 | err = indexed_table_ref_iter_new(&itr, t, oid, hash_size(t->hash_id), |
| 663 | got.u.obj.offsets, |
| 664 | got.u.obj.offset_len); |
| 665 | if (err < 0) |
| 666 | goto done; |
| 667 | got.u.obj.offsets = NULL; |
| 668 | iterator_from_indexed_table_ref_iter(it, itr); |
| 669 | |
| 670 | done: |
| 671 | reftable_iterator_destroy(&oit); |
| 672 | reftable_record_release(&got); |
| 673 | return err; |
| 674 | } |
| 675 | |
| 676 | static int reftable_table_refs_for_unindexed(struct reftable_table *t, |
| 677 | struct reftable_iterator *it, |
| 678 | uint8_t *oid) |
| 679 | { |
| 680 | struct table_iter *ti; |
| 681 | struct filtering_ref_iterator *filter = NULL; |
| 682 | struct filtering_ref_iterator empty = FILTERING_REF_ITERATOR_INIT; |
| 683 | uint32_t oid_len = hash_size(t->hash_id); |
| 684 | int err; |
| 685 | |
| 686 | REFTABLE_ALLOC_ARRAY(ti, 1); |
| 687 | if (!ti) { |
| 688 | err = REFTABLE_OUT_OF_MEMORY_ERROR; |
| 689 | goto out; |
| 690 | } |
| 691 | |
| 692 | table_iter_init(ti, t); |
| 693 | err = table_iter_seek_start(ti, REFTABLE_BLOCK_TYPE_REF, 0); |
| 694 | if (err < 0) |
| 695 | goto out; |
| 696 | |
| 697 | filter = reftable_malloc(sizeof(*filter)); |
| 698 | if (!filter) { |
| 699 | err = REFTABLE_OUT_OF_MEMORY_ERROR; |
| 700 | goto out; |
| 701 | } |
| 702 | *filter = empty; |
| 703 | |
| 704 | err = reftable_buf_add(&filter->oid, oid, oid_len); |
| 705 | if (err < 0) |
| 706 | goto out; |
| 707 | |
| 708 | iterator_from_table_iter(&filter->it, ti); |
| 709 | |
| 710 | iterator_from_filtering_ref_iterator(it, filter); |
| 711 | |
| 712 | err = 0; |
| 713 | |
| 714 | out: |
| 715 | if (err < 0) { |
| 716 | if (ti) |
| 717 | table_iter_close(ti); |
| 718 | reftable_free(ti); |
| 719 | if (filter) { |
| 720 | reftable_buf_release(&filter->oid); |
| 721 | reftable_free(filter); |
| 722 | } |
| 723 | } |
| 724 | return err; |
| 725 | } |
| 726 | |
| 727 | int reftable_table_refs_for(struct reftable_table *t, |
| 728 | struct reftable_iterator *it, uint8_t *oid) |
| 729 | { |
| 730 | if (t->obj_offsets.is_present) |
| 731 | return reftable_table_refs_for_indexed(t, it, oid); |
| 732 | return reftable_table_refs_for_unindexed(t, it, oid); |
| 733 | } |
| 734 | |
| 735 | uint64_t reftable_table_max_update_index(struct reftable_table *t) |
| 736 | { |
| 737 | return t->max_update_index; |
| 738 | } |
| 739 | |
| 740 | uint64_t reftable_table_min_update_index(struct reftable_table *t) |
| 741 | { |
| 742 | return t->min_update_index; |
| 743 | } |
| 744 | |
| 745 | int reftable_table_iterator_init(struct reftable_table_iterator *it, |
| 746 | struct reftable_table *t) |
| 747 | { |
| 748 | struct table_iter *ti; |
| 749 | int err; |
| 750 | |
| 751 | REFTABLE_ALLOC_ARRAY(ti, 1); |
| 752 | if (!ti) |
| 753 | return REFTABLE_OUT_OF_MEMORY_ERROR; |
| 754 | |
| 755 | err = table_iter_init(ti, t); |
| 756 | if (err < 0) |
| 757 | goto out; |
| 758 | |
| 759 | it->iter_arg = ti; |
| 760 | err = 0; |
| 761 | |
| 762 | out: |
| 763 | if (err < 0) |
| 764 | reftable_free(ti); |
| 765 | return err; |
| 766 | } |
| 767 | |
| 768 | void reftable_table_iterator_release(struct reftable_table_iterator *it) |
| 769 | { |
| 770 | if (!it->iter_arg) |
| 771 | return; |
| 772 | table_iter_close(it->iter_arg); |
| 773 | reftable_free(it->iter_arg); |
| 774 | it->iter_arg = NULL; |
| 775 | } |
| 776 | |
| 777 | int reftable_table_iterator_next(struct reftable_table_iterator *it, |
| 778 | const struct reftable_block **out) |
| 779 | { |
| 780 | struct table_iter *ti = it->iter_arg; |
| 781 | int err; |
| 782 | |
| 783 | err = table_iter_next_block(ti); |
| 784 | if (err) |
| 785 | return err; |
| 786 | |
| 787 | *out = &ti->block; |
| 788 | |
| 789 | return 0; |
| 790 | } |