| 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 "block.h" |
| 10 | |
| 11 | #include "blocksource.h" |
| 12 | #include "constants.h" |
| 13 | #include "iter.h" |
| 14 | #include "record.h" |
| 15 | #include "reftable-error.h" |
| 16 | #include "system.h" |
| 17 | |
| 18 | size_t header_size(int version) |
| 19 | { |
| 20 | switch (version) { |
| 21 | case 1: |
| 22 | return 24; |
| 23 | case 2: |
| 24 | return 28; |
| 25 | } |
| 26 | abort(); |
| 27 | } |
| 28 | |
| 29 | size_t footer_size(int version) |
| 30 | { |
| 31 | switch (version) { |
| 32 | case 1: |
| 33 | return 68; |
| 34 | case 2: |
| 35 | return 72; |
| 36 | } |
| 37 | abort(); |
| 38 | } |
| 39 | |
| 40 | static int block_writer_register_restart(struct block_writer *w, int n, |
| 41 | int is_restart, struct reftable_buf *key) |
| 42 | { |
| 43 | uint32_t rlen; |
| 44 | int err; |
| 45 | |
| 46 | rlen = w->restart_len; |
| 47 | if (rlen >= MAX_RESTARTS) |
| 48 | is_restart = 0; |
| 49 | |
| 50 | if (is_restart) |
| 51 | rlen++; |
| 52 | if (2 + 3 * rlen + n > w->block_size - w->next) |
| 53 | return REFTABLE_ENTRY_TOO_BIG_ERROR; |
| 54 | if (is_restart) { |
| 55 | REFTABLE_ALLOC_GROW_OR_NULL(w->restarts, w->restart_len + 1, |
| 56 | w->restart_cap); |
| 57 | if (!w->restarts) |
| 58 | return REFTABLE_OUT_OF_MEMORY_ERROR; |
| 59 | w->restarts[w->restart_len++] = w->next; |
| 60 | } |
| 61 | |
| 62 | w->next += n; |
| 63 | |
| 64 | reftable_buf_reset(&w->last_key); |
| 65 | err = reftable_buf_add(&w->last_key, key->buf, key->len); |
| 66 | if (err < 0) |
| 67 | return err; |
| 68 | |
| 69 | w->entries++; |
| 70 | return 0; |
| 71 | } |
| 72 | |
| 73 | int block_writer_init(struct block_writer *bw, uint8_t typ, uint8_t *block, |
| 74 | uint32_t block_size, uint32_t header_off, uint32_t hash_size) |
| 75 | { |
| 76 | bw->block = block; |
| 77 | bw->hash_size = hash_size; |
| 78 | bw->block_size = block_size; |
| 79 | bw->header_off = header_off; |
| 80 | bw->block[header_off] = typ; |
| 81 | bw->next = header_off + 4; |
| 82 | bw->restart_interval = 16; |
| 83 | bw->entries = 0; |
| 84 | bw->restart_len = 0; |
| 85 | bw->last_key.len = 0; |
| 86 | if (!bw->zstream) { |
| 87 | REFTABLE_CALLOC_ARRAY(bw->zstream, 1); |
| 88 | if (!bw->zstream) |
| 89 | return REFTABLE_OUT_OF_MEMORY_ERROR; |
| 90 | if (deflateInit(bw->zstream, 9) != Z_OK) |
| 91 | return REFTABLE_ZLIB_ERROR; |
| 92 | } |
| 93 | |
| 94 | return 0; |
| 95 | } |
| 96 | |
| 97 | uint8_t block_writer_type(struct block_writer *bw) |
| 98 | { |
| 99 | return bw->block[bw->header_off]; |
| 100 | } |
| 101 | |
| 102 | /* |
| 103 | * Adds the reftable_record to the block. Returns 0 on success and |
| 104 | * appropriate error codes on failure. |
| 105 | */ |
| 106 | int block_writer_add(struct block_writer *w, struct reftable_record *rec) |
| 107 | { |
| 108 | struct reftable_buf empty = REFTABLE_BUF_INIT; |
| 109 | struct reftable_buf last = |
| 110 | w->entries % w->restart_interval == 0 ? empty : w->last_key; |
| 111 | struct string_view out = { |
| 112 | .buf = w->block + w->next, |
| 113 | .len = w->block_size - w->next, |
| 114 | }; |
| 115 | struct string_view start = out; |
| 116 | int is_restart = 0; |
| 117 | int n = 0; |
| 118 | int err; |
| 119 | |
| 120 | err = reftable_record_key(rec, &w->scratch); |
| 121 | if (err < 0) |
| 122 | goto done; |
| 123 | |
| 124 | if (!w->scratch.len) { |
| 125 | err = REFTABLE_API_ERROR; |
| 126 | goto done; |
| 127 | } |
| 128 | |
| 129 | n = reftable_encode_key(&is_restart, out, last, w->scratch, |
| 130 | reftable_record_val_type(rec)); |
| 131 | if (n < 0) { |
| 132 | err = n; |
| 133 | goto done; |
| 134 | } |
| 135 | string_view_consume(&out, n); |
| 136 | |
| 137 | n = reftable_record_encode(rec, out, w->hash_size); |
| 138 | if (n < 0) { |
| 139 | err = n; |
| 140 | goto done; |
| 141 | } |
| 142 | string_view_consume(&out, n); |
| 143 | |
| 144 | err = block_writer_register_restart(w, start.len - out.len, is_restart, |
| 145 | &w->scratch); |
| 146 | done: |
| 147 | return err; |
| 148 | } |
| 149 | |
| 150 | int block_writer_finish(struct block_writer *w) |
| 151 | { |
| 152 | for (uint32_t i = 0; i < w->restart_len; i++) { |
| 153 | reftable_put_be24(w->block + w->next, w->restarts[i]); |
| 154 | w->next += 3; |
| 155 | } |
| 156 | |
| 157 | reftable_put_be16(w->block + w->next, w->restart_len); |
| 158 | w->next += 2; |
| 159 | reftable_put_be24(w->block + 1 + w->header_off, w->next); |
| 160 | |
| 161 | /* |
| 162 | * Log records are stored zlib-compressed. Note that the compression |
| 163 | * also spans over the restart points we have just written. |
| 164 | */ |
| 165 | if (block_writer_type(w) == REFTABLE_BLOCK_TYPE_LOG) { |
| 166 | int block_header_skip = 4 + w->header_off; |
| 167 | uLongf src_len = w->next - block_header_skip, compressed_len; |
| 168 | int ret; |
| 169 | |
| 170 | ret = deflateReset(w->zstream); |
| 171 | if (ret != Z_OK) |
| 172 | return REFTABLE_ZLIB_ERROR; |
| 173 | |
| 174 | /* |
| 175 | * Precompute the upper bound of how many bytes the compressed |
| 176 | * data may end up with. Combined with `Z_FINISH`, `deflate()` |
| 177 | * is guaranteed to return `Z_STREAM_END`. |
| 178 | */ |
| 179 | compressed_len = deflateBound(w->zstream, src_len); |
| 180 | REFTABLE_ALLOC_GROW_OR_NULL(w->compressed, compressed_len, |
| 181 | w->compressed_cap); |
| 182 | if (!w->compressed) { |
| 183 | ret = REFTABLE_OUT_OF_MEMORY_ERROR; |
| 184 | return ret; |
| 185 | } |
| 186 | |
| 187 | w->zstream->next_out = w->compressed; |
| 188 | w->zstream->avail_out = compressed_len; |
| 189 | w->zstream->next_in = w->block + block_header_skip; |
| 190 | w->zstream->avail_in = src_len; |
| 191 | |
| 192 | /* |
| 193 | * We want to perform all decompression in a single step, which |
| 194 | * is why we can pass Z_FINISH here. As we have precomputed the |
| 195 | * deflated buffer's size via `deflateBound()` this function is |
| 196 | * guaranteed to succeed according to the zlib documentation. |
| 197 | */ |
| 198 | ret = deflate(w->zstream, Z_FINISH); |
| 199 | if (ret != Z_STREAM_END) |
| 200 | return REFTABLE_ZLIB_ERROR; |
| 201 | |
| 202 | /* |
| 203 | * Overwrite the uncompressed data we have already written and |
| 204 | * adjust the `next` pointer to point right after the |
| 205 | * compressed data. |
| 206 | */ |
| 207 | memcpy(w->block + block_header_skip, w->compressed, |
| 208 | w->zstream->total_out); |
| 209 | w->next = w->zstream->total_out + block_header_skip; |
| 210 | } |
| 211 | |
| 212 | return w->next; |
| 213 | } |
| 214 | |
| 215 | static int read_block(struct reftable_block_source *source, |
| 216 | struct reftable_block_data *dest, uint64_t off, |
| 217 | uint32_t sz) |
| 218 | { |
| 219 | size_t size = block_source_size(source); |
| 220 | block_source_release_data(dest); |
| 221 | if (off >= size) |
| 222 | return 0; |
| 223 | if (off + sz > size) |
| 224 | sz = size - off; |
| 225 | return block_source_read_data(source, dest, off, sz); |
| 226 | } |
| 227 | |
| 228 | int reftable_block_init(struct reftable_block *block, |
| 229 | struct reftable_block_source *source, |
| 230 | uint32_t offset, uint32_t header_size, |
| 231 | uint32_t table_block_size, uint32_t hash_size, |
| 232 | uint8_t want_type) |
| 233 | { |
| 234 | uint32_t guess_block_size = table_block_size ? |
| 235 | table_block_size : DEFAULT_BLOCK_SIZE; |
| 236 | uint32_t full_block_size = table_block_size; |
| 237 | uint16_t restart_count; |
| 238 | uint32_t restart_off; |
| 239 | uint32_t block_size; |
| 240 | uint8_t block_type; |
| 241 | int err; |
| 242 | |
| 243 | err = read_block(source, &block->block_data, offset, guess_block_size); |
| 244 | if (err < 0) |
| 245 | goto done; |
| 246 | |
| 247 | block_type = block->block_data.data[header_size]; |
| 248 | if (!reftable_is_block_type(block_type)) { |
| 249 | err = REFTABLE_FORMAT_ERROR; |
| 250 | goto done; |
| 251 | } |
| 252 | if (want_type != REFTABLE_BLOCK_TYPE_ANY && block_type != want_type) { |
| 253 | err = 1; |
| 254 | goto done; |
| 255 | } |
| 256 | |
| 257 | block_size = reftable_get_be24(block->block_data.data + header_size + 1); |
| 258 | if (block_size > guess_block_size) { |
| 259 | err = read_block(source, &block->block_data, offset, block_size); |
| 260 | if (err < 0) |
| 261 | goto done; |
| 262 | } |
| 263 | |
| 264 | /* |
| 265 | * Verify that the block size covers at least the table header, block |
| 266 | * header and the 2 byte restart counter. |
| 267 | */ |
| 268 | if (block_size < header_size + 4 + 2) { |
| 269 | err = REFTABLE_FORMAT_ERROR; |
| 270 | goto done; |
| 271 | } |
| 272 | |
| 273 | if (block_type == REFTABLE_BLOCK_TYPE_LOG) { |
| 274 | uint32_t block_header_skip = 4 + header_size; |
| 275 | uLong dst_len = block_size - block_header_skip; |
| 276 | uLong src_len = block->block_data.len - block_header_skip; |
| 277 | |
| 278 | /* Log blocks specify the *uncompressed* size in their header. */ |
| 279 | REFTABLE_ALLOC_GROW_OR_NULL(block->uncompressed_data, block_size, |
| 280 | block->uncompressed_cap); |
| 281 | if (!block->uncompressed_data) { |
| 282 | err = REFTABLE_OUT_OF_MEMORY_ERROR; |
| 283 | goto done; |
| 284 | } |
| 285 | |
| 286 | /* Copy over the block header verbatim. It's not compressed. */ |
| 287 | memcpy(block->uncompressed_data, block->block_data.data, block_header_skip); |
| 288 | |
| 289 | if (!block->zstream) { |
| 290 | REFTABLE_CALLOC_ARRAY(block->zstream, 1); |
| 291 | if (!block->zstream) { |
| 292 | err = REFTABLE_OUT_OF_MEMORY_ERROR; |
| 293 | goto done; |
| 294 | } |
| 295 | |
| 296 | err = inflateInit(block->zstream); |
| 297 | } else { |
| 298 | err = inflateReset(block->zstream); |
| 299 | } |
| 300 | if (err != Z_OK) { |
| 301 | err = REFTABLE_ZLIB_ERROR; |
| 302 | goto done; |
| 303 | } |
| 304 | |
| 305 | block->zstream->next_in = block->block_data.data + block_header_skip; |
| 306 | block->zstream->avail_in = src_len; |
| 307 | block->zstream->next_out = block->uncompressed_data + block_header_skip; |
| 308 | block->zstream->avail_out = dst_len; |
| 309 | |
| 310 | /* |
| 311 | * We know both input as well as output size, and we know that |
| 312 | * the sizes should never be bigger than `uInt_MAX` because |
| 313 | * blocks can at most be 16MB large. We can thus use `Z_FINISH` |
| 314 | * here to instruct zlib to inflate the data in one go, which |
| 315 | * is more efficient than using `Z_NO_FLUSH`. |
| 316 | */ |
| 317 | err = inflate(block->zstream, Z_FINISH); |
| 318 | if (err != Z_STREAM_END) { |
| 319 | err = REFTABLE_ZLIB_ERROR; |
| 320 | goto done; |
| 321 | } |
| 322 | err = 0; |
| 323 | |
| 324 | if (block->zstream->total_out + block_header_skip != block_size) { |
| 325 | err = REFTABLE_FORMAT_ERROR; |
| 326 | goto done; |
| 327 | } |
| 328 | |
| 329 | /* We're done with the input data. */ |
| 330 | block_source_release_data(&block->block_data); |
| 331 | block->block_data.data = block->uncompressed_data; |
| 332 | block->block_data.len = block_size; |
| 333 | full_block_size = src_len + block_header_skip - block->zstream->avail_in; |
| 334 | } else if (full_block_size == 0) { |
| 335 | full_block_size = block_size; |
| 336 | } else if (block_size < full_block_size && block_size < block->block_data.len && |
| 337 | block->block_data.data[block_size] != 0) { |
| 338 | /* If the block is smaller than the full block size, it is |
| 339 | padded (data followed by '\0') or the next block is |
| 340 | unaligned. */ |
| 341 | full_block_size = block_size; |
| 342 | } |
| 343 | |
| 344 | /* |
| 345 | * Ensure that we have sufficient data available now to satisfy the |
| 346 | * claimed block size. |
| 347 | */ |
| 348 | if (block_size > block->block_data.len) { |
| 349 | err = REFTABLE_FORMAT_ERROR; |
| 350 | goto done; |
| 351 | } |
| 352 | |
| 353 | restart_count = reftable_get_be16(block->block_data.data + block_size - 2); |
| 354 | restart_off = block_size - 2 - 3 * restart_count; |
| 355 | if (restart_off < header_size + 4 || restart_off > block_size - 2) { |
| 356 | err = REFTABLE_FORMAT_ERROR; |
| 357 | goto done; |
| 358 | } |
| 359 | |
| 360 | block->block_type = block_type; |
| 361 | block->hash_size = hash_size; |
| 362 | block->restart_off = restart_off; |
| 363 | block->full_block_size = full_block_size; |
| 364 | block->header_off = header_size; |
| 365 | block->restart_count = restart_count; |
| 366 | |
| 367 | err = 0; |
| 368 | |
| 369 | done: |
| 370 | if (err < 0) |
| 371 | reftable_block_release(block); |
| 372 | return err; |
| 373 | } |
| 374 | |
| 375 | void reftable_block_release(struct reftable_block *block) |
| 376 | { |
| 377 | inflateEnd(block->zstream); |
| 378 | reftable_free(block->zstream); |
| 379 | reftable_free(block->uncompressed_data); |
| 380 | block_source_release_data(&block->block_data); |
| 381 | memset(block, 0, sizeof(*block)); |
| 382 | } |
| 383 | |
| 384 | uint8_t reftable_block_type(const struct reftable_block *b) |
| 385 | { |
| 386 | return b->block_data.data[b->header_off]; |
| 387 | } |
| 388 | |
| 389 | int reftable_block_first_key(const struct reftable_block *block, struct reftable_buf *key) |
| 390 | { |
| 391 | int off = block->header_off + 4, n; |
| 392 | struct string_view in = { |
| 393 | .buf = block->block_data.data + off, |
| 394 | .len = block->restart_off - off, |
| 395 | }; |
| 396 | uint8_t extra = 0; |
| 397 | |
| 398 | reftable_buf_reset(key); |
| 399 | |
| 400 | n = reftable_decode_key(key, &extra, in); |
| 401 | if (n < 0) |
| 402 | return n; |
| 403 | if (!key->len) |
| 404 | return REFTABLE_FORMAT_ERROR; |
| 405 | |
| 406 | return 0; |
| 407 | } |
| 408 | |
| 409 | static uint32_t block_restart_offset(const struct reftable_block *b, size_t idx) |
| 410 | { |
| 411 | return reftable_get_be24(b->block_data.data + b->restart_off + 3 * idx); |
| 412 | } |
| 413 | |
| 414 | void block_iter_init(struct block_iter *it, const struct reftable_block *block) |
| 415 | { |
| 416 | it->block = block; |
| 417 | block_iter_seek_start(it); |
| 418 | } |
| 419 | |
| 420 | void block_iter_seek_start(struct block_iter *it) |
| 421 | { |
| 422 | reftable_buf_reset(&it->last_key); |
| 423 | it->next_off = it->block->header_off + 4; |
| 424 | } |
| 425 | |
| 426 | struct restart_needle_less_args { |
| 427 | int error; |
| 428 | struct reftable_buf needle; |
| 429 | const struct reftable_block *block; |
| 430 | }; |
| 431 | |
| 432 | static int restart_needle_less(size_t idx, void *_args) |
| 433 | { |
| 434 | struct restart_needle_less_args *args = _args; |
| 435 | uint32_t off = block_restart_offset(args->block, idx); |
| 436 | struct string_view in = { |
| 437 | .buf = args->block->block_data.data + off, |
| 438 | .len = args->block->restart_off - off, |
| 439 | }; |
| 440 | uint64_t prefix_len, suffix_len; |
| 441 | uint8_t extra; |
| 442 | int n; |
| 443 | |
| 444 | /* |
| 445 | * The restart offset must point to a record, which is stored before |
| 446 | * the restart table. Verify that this is the case. |
| 447 | */ |
| 448 | if (off >= args->block->restart_off) { |
| 449 | args->error = 1; |
| 450 | return -1; |
| 451 | } |
| 452 | |
| 453 | /* |
| 454 | * Records at restart points are stored without prefix compression, so |
| 455 | * there is no need to fully decode the record key here. This removes |
| 456 | * the need for allocating memory. |
| 457 | */ |
| 458 | n = reftable_decode_keylen(in, &prefix_len, &suffix_len, &extra); |
| 459 | if (n < 0 || prefix_len) { |
| 460 | args->error = 1; |
| 461 | return -1; |
| 462 | } |
| 463 | |
| 464 | string_view_consume(&in, n); |
| 465 | if (suffix_len > in.len) { |
| 466 | args->error = 1; |
| 467 | return -1; |
| 468 | } |
| 469 | |
| 470 | n = memcmp(args->needle.buf, in.buf, |
| 471 | args->needle.len < suffix_len ? args->needle.len : suffix_len); |
| 472 | if (n) |
| 473 | return n < 0; |
| 474 | return args->needle.len < suffix_len; |
| 475 | } |
| 476 | |
| 477 | int block_iter_next(struct block_iter *it, struct reftable_record *rec) |
| 478 | { |
| 479 | struct string_view in = { |
| 480 | .buf = (unsigned char *) it->block->block_data.data + it->next_off, |
| 481 | .len = it->block->restart_off - it->next_off, |
| 482 | }; |
| 483 | struct string_view start = in; |
| 484 | uint8_t extra = 0; |
| 485 | int n = 0; |
| 486 | |
| 487 | if (it->next_off >= it->block->restart_off) |
| 488 | return 1; |
| 489 | |
| 490 | n = reftable_decode_key(&it->last_key, &extra, in); |
| 491 | if (n < 0) |
| 492 | return -1; |
| 493 | if (!it->last_key.len) |
| 494 | return REFTABLE_FORMAT_ERROR; |
| 495 | |
| 496 | string_view_consume(&in, n); |
| 497 | n = reftable_record_decode(rec, it->last_key, extra, in, it->block->hash_size, |
| 498 | &it->scratch); |
| 499 | if (n < 0) |
| 500 | return -1; |
| 501 | string_view_consume(&in, n); |
| 502 | |
| 503 | it->next_off += start.len - in.len; |
| 504 | return 0; |
| 505 | } |
| 506 | |
| 507 | void block_iter_reset(struct block_iter *it) |
| 508 | { |
| 509 | reftable_buf_reset(&it->last_key); |
| 510 | it->next_off = 0; |
| 511 | it->block = NULL; |
| 512 | } |
| 513 | |
| 514 | void block_iter_close(struct block_iter *it) |
| 515 | { |
| 516 | reftable_buf_release(&it->last_key); |
| 517 | reftable_buf_release(&it->scratch); |
| 518 | } |
| 519 | |
| 520 | int block_iter_seek_key(struct block_iter *it, struct reftable_buf *want) |
| 521 | { |
| 522 | struct restart_needle_less_args args = { |
| 523 | .needle = *want, |
| 524 | .block = it->block, |
| 525 | }; |
| 526 | struct reftable_record rec; |
| 527 | int err = 0; |
| 528 | size_t i; |
| 529 | |
| 530 | err = reftable_record_init(&rec, reftable_block_type(it->block)); |
| 531 | if (err < 0) |
| 532 | goto done; |
| 533 | |
| 534 | /* |
| 535 | * Perform a binary search over the block's restart points, which |
| 536 | * avoids doing a linear scan over the whole block. Like this, we |
| 537 | * identify the section of the block that should contain our key. |
| 538 | * |
| 539 | * Note that we explicitly search for the first restart point _greater_ |
| 540 | * than the sought-after record, not _greater or equal_ to it. In case |
| 541 | * the sought-after record is located directly at the restart point we |
| 542 | * would otherwise start doing the linear search at the preceding |
| 543 | * restart point. While that works alright, we would end up scanning |
| 544 | * too many record. |
| 545 | */ |
| 546 | i = binsearch(it->block->restart_count, &restart_needle_less, &args); |
| 547 | if (args.error) { |
| 548 | err = REFTABLE_FORMAT_ERROR; |
| 549 | goto done; |
| 550 | } |
| 551 | |
| 552 | /* |
| 553 | * Now there are multiple cases: |
| 554 | * |
| 555 | * - `i == 0`: The wanted record is smaller than the record found at |
| 556 | * the first restart point. As the first restart point is the first |
| 557 | * record in the block, our wanted record cannot be located in this |
| 558 | * block at all. We still need to position the iterator so that the |
| 559 | * next call to `block_iter_next()` will yield an end-of-iterator |
| 560 | * signal. |
| 561 | * |
| 562 | * - `i == restart_count`: The wanted record was not found at any of |
| 563 | * the restart points. As there is no restart point at the end of |
| 564 | * the section the record may thus be contained in the last block. |
| 565 | * |
| 566 | * - `i > 0`: The wanted record must be contained in the section |
| 567 | * before the found restart point. We thus do a linear search |
| 568 | * starting from the preceding restart point. |
| 569 | */ |
| 570 | if (i > 0) |
| 571 | it->next_off = block_restart_offset(it->block, i - 1); |
| 572 | else |
| 573 | it->next_off = it->block->header_off + 4; |
| 574 | |
| 575 | /* |
| 576 | * We're looking for the last entry less than the wanted key so that |
| 577 | * the next call to `block_reader_next()` would yield the wanted |
| 578 | * record. We thus don't want to position our iterator at the sought |
| 579 | * after record, but one before. To do so, we have to go one entry too |
| 580 | * far and then back up. |
| 581 | */ |
| 582 | while (1) { |
| 583 | size_t prev_off = it->next_off; |
| 584 | |
| 585 | err = block_iter_next(it, &rec); |
| 586 | if (err < 0) |
| 587 | goto done; |
| 588 | if (err > 0) { |
| 589 | it->next_off = prev_off; |
| 590 | err = 0; |
| 591 | goto done; |
| 592 | } |
| 593 | |
| 594 | err = reftable_record_key(&rec, &it->last_key); |
| 595 | if (err < 0) |
| 596 | goto done; |
| 597 | |
| 598 | /* |
| 599 | * Check whether the current key is greater or equal to the |
| 600 | * sought-after key. In case it is greater we know that the |
| 601 | * record does not exist in the block and can thus abort early. |
| 602 | * In case it is equal to the sought-after key we have found |
| 603 | * the desired record. |
| 604 | * |
| 605 | * Note that we store the next record's key record directly in |
| 606 | * `last_key` without restoring the key of the preceding record |
| 607 | * in case we need to go one record back. This is safe to do as |
| 608 | * `block_iter_next()` would return the ref whose key is equal |
| 609 | * to `last_key` now, and naturally all keys share a prefix |
| 610 | * with themselves. |
| 611 | */ |
| 612 | if (reftable_buf_cmp(&it->last_key, want) >= 0) { |
| 613 | it->next_off = prev_off; |
| 614 | goto done; |
| 615 | } |
| 616 | } |
| 617 | |
| 618 | done: |
| 619 | reftable_record_release(&rec); |
| 620 | return err; |
| 621 | } |
| 622 | |
| 623 | static int block_iter_seek_void(void *it, struct reftable_record *want) |
| 624 | { |
| 625 | struct reftable_buf buf = REFTABLE_BUF_INIT; |
| 626 | struct block_iter *bi = it; |
| 627 | int err; |
| 628 | |
| 629 | if (bi->block->block_type != want->type) |
| 630 | return REFTABLE_API_ERROR; |
| 631 | |
| 632 | err = reftable_record_key(want, &buf); |
| 633 | if (err < 0) |
| 634 | goto out; |
| 635 | |
| 636 | err = block_iter_seek_key(it, &buf); |
| 637 | if (err < 0) |
| 638 | goto out; |
| 639 | |
| 640 | err = 0; |
| 641 | |
| 642 | out: |
| 643 | reftable_buf_release(&buf); |
| 644 | return err; |
| 645 | } |
| 646 | |
| 647 | static int block_iter_next_void(void *it, struct reftable_record *rec) |
| 648 | { |
| 649 | return block_iter_next(it, rec); |
| 650 | } |
| 651 | |
| 652 | static void block_iter_close_void(void *it) |
| 653 | { |
| 654 | block_iter_close(it); |
| 655 | } |
| 656 | |
| 657 | static struct reftable_iterator_vtable block_iter_vtable = { |
| 658 | .seek = &block_iter_seek_void, |
| 659 | .next = &block_iter_next_void, |
| 660 | .close = &block_iter_close_void, |
| 661 | }; |
| 662 | |
| 663 | int reftable_block_init_iterator(const struct reftable_block *b, |
| 664 | struct reftable_iterator *it) |
| 665 | { |
| 666 | struct block_iter *bi; |
| 667 | |
| 668 | REFTABLE_CALLOC_ARRAY(bi, 1); |
| 669 | block_iter_init(bi, b); |
| 670 | |
| 671 | assert(!it->ops); |
| 672 | it->iter_arg = bi; |
| 673 | it->ops = &block_iter_vtable; |
| 674 | |
| 675 | return 0; |
| 676 | } |
| 677 | |
| 678 | void block_writer_release(struct block_writer *bw) |
| 679 | { |
| 680 | deflateEnd(bw->zstream); |
| 681 | REFTABLE_FREE_AND_NULL(bw->zstream); |
| 682 | REFTABLE_FREE_AND_NULL(bw->restarts); |
| 683 | REFTABLE_FREE_AND_NULL(bw->compressed); |
| 684 | reftable_buf_release(&bw->scratch); |
| 685 | reftable_buf_release(&bw->last_key); |
| 686 | /* the block is not owned. */ |
| 687 | } |