reftable/writer.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 "writer.h"
  10
  11 #include "system.h"
  12
  13 #include "block.h"
  14 #include "constants.h"
  15 #include "record.h"
  16 #include "tree.h"
  17 #include "reftable-error.h"
  18
  19 /* finishes a block, and writes it to storage */
  20 static int writer_flush_block(struct reftable_writer *w);
  21
  22 /* deallocates memory related to the index */
  23 static void writer_clear_index(struct reftable_writer *w);
  24
  25 /* finishes writing a 'r' (refs) or 'g' (reflogs) section */
  26 static int writer_finish_public_section(struct reftable_writer *w);
  27
  28 static struct reftable_block_stats *
  29 writer_reftable_block_stats(struct reftable_writer *w, uint8_t typ)
  30 {
  31         switch (typ) {
  32         case 'r':
  33                 return &w->stats.ref_stats;
  34         case 'o':
  35                 return &w->stats.obj_stats;
  36         case 'i':
  37                 return &w->stats.idx_stats;
  38         case 'g':
  39                 return &w->stats.log_stats;
  40         }
  41         abort();
  42         return NULL;
  43 }
  44
  45 /* write data, queuing the padding for the next write. Returns negative for
  46  * error. */
  47 static int padded_write(struct reftable_writer *w, uint8_t *data, size_t len,
  48                         int padding)
  49 {
  50         int n = 0;
  51         if (w->pending_padding > 0) {
  52                 uint8_t *zeroed = reftable_calloc(w->pending_padding);
  53                 int n = w->write(w->write_arg, zeroed, w->pending_padding);
  54                 if (n < 0)
  55                         return n;
  56
  57                 w->pending_padding = 0;
  58                 reftable_free(zeroed);
  59         }
  60
  61         w->pending_padding = padding;
  62         n = w->write(w->write_arg, data, len);
  63         if (n < 0)
  64                 return n;
  65         n += padding;
  66         return 0;
  67 }
  68
  69 static void options_set_defaults(struct reftable_write_options *opts)
  70 {
  71         if (opts->restart_interval == 0) {
  72                 opts->restart_interval = 16;
  73         }
  74
  75         if (opts->hash_id == 0) {
  76                 opts->hash_id = GIT_SHA1_FORMAT_ID;
  77         }
  78         if (opts->block_size == 0) {
  79                 opts->block_size = DEFAULT_BLOCK_SIZE;
  80         }
  81 }
  82
  83 static int writer_version(struct reftable_writer *w)
  84 {
  85         return (w->opts.hash_id == 0 || w->opts.hash_id == GIT_SHA1_FORMAT_ID) ?
  86                              1 :
  87                              2;
  88 }
  89
  90 static int writer_write_header(struct reftable_writer *w, uint8_t *dest)
  91 {
  92         memcpy(dest, "REFT", 4);
  93
  94         dest[4] = writer_version(w);
  95
  96         put_be24(dest + 5, w->opts.block_size);
  97         put_be64(dest + 8, w->min_update_index);
  98         put_be64(dest + 16, w->max_update_index);
  99         if (writer_version(w) == 2) {
 100                 put_be32(dest + 24, w->opts.hash_id);
 101         }
 102         return header_size(writer_version(w));
 103 }
 104
 105 static void writer_reinit_block_writer(struct reftable_writer *w, uint8_t typ)
 106 {
 107         int block_start = 0;
 108         if (w->next == 0) {
 109                 block_start = header_size(writer_version(w));
 110         }
 111
 112         strbuf_release(&w->last_key);
 113         block_writer_init(&w->block_writer_data, typ, w->block,
 114                           w->opts.block_size, block_start,
 115                           hash_size(w->opts.hash_id));
 116         w->block_writer = &w->block_writer_data;
 117         w->block_writer->restart_interval = w->opts.restart_interval;
 118 }
 119
 120 static struct strbuf reftable_empty_strbuf = STRBUF_INIT;
 121
 122 struct reftable_writer *
 123 reftable_new_writer(ssize_t (*writer_func)(void *, const void *, size_t),
 124                     void *writer_arg, struct reftable_write_options *opts)
 125 {
 126         struct reftable_writer *wp =
 127                 reftable_calloc(sizeof(struct reftable_writer));
 128         strbuf_init(&wp->block_writer_data.last_key, 0);
 129         options_set_defaults(opts);
 130         if (opts->block_size >= (1 << 24)) {
 131                 /* TODO - error return? */
 132                 abort();
 133         }
 134         wp->last_key = reftable_empty_strbuf;
 135         wp->block = reftable_calloc(opts->block_size);
 136         wp->write = writer_func;
 137         wp->write_arg = writer_arg;
 138         wp->opts = *opts;
 139         writer_reinit_block_writer(wp, BLOCK_TYPE_REF);
 140
 141         return wp;
 142 }
 143
 144 void reftable_writer_set_limits(struct reftable_writer *w, uint64_t min,
 145                                 uint64_t max)
 146 {
 147         w->min_update_index = min;
 148         w->max_update_index = max;
 149 }
 150
 151 void reftable_writer_free(struct reftable_writer *w)
 152 {
 153         if (!w)
 154                 return;
 155         reftable_free(w->block);
 156         reftable_free(w);
 157 }
 158
 159 struct obj_index_tree_node {
 160         struct strbuf hash;
 161         uint64_t *offsets;
 162         size_t offset_len;
 163         size_t offset_cap;
 164 };
 165
 166 #define OBJ_INDEX_TREE_NODE_INIT    \
 167         {                           \
 168                 .hash = STRBUF_INIT \
 169         }
 170
 171 static int obj_index_tree_node_compare(const void *a, const void *b)
 172 {
 173         return strbuf_cmp(&((const struct obj_index_tree_node *)a)->hash,
 174                           &((const struct obj_index_tree_node *)b)->hash);
 175 }
 176
 177 static void writer_index_hash(struct reftable_writer *w, struct strbuf *hash)
 178 {
 179         uint64_t off = w->next;
 180
 181         struct obj_index_tree_node want = { .hash = *hash };
 182
 183         struct tree_node *node = tree_search(&want, &w->obj_index_tree,
 184                                              &obj_index_tree_node_compare, 0);
 185         struct obj_index_tree_node *key = NULL;
 186         if (!node) {
 187                 struct obj_index_tree_node empty = OBJ_INDEX_TREE_NODE_INIT;
 188                 key = reftable_malloc(sizeof(struct obj_index_tree_node));
 189                 *key = empty;
 190
 191                 strbuf_reset(&key->hash);
 192                 strbuf_addbuf(&key->hash, hash);
 193                 tree_search((void *)key, &w->obj_index_tree,
 194                             &obj_index_tree_node_compare, 1);
 195         } else {
 196                 key = node->key;
 197         }
 198
 199         if (key->offset_len > 0 && key->offsets[key->offset_len - 1] == off) {
 200                 return;
 201         }
 202
 203         if (key->offset_len == key->offset_cap) {
 204                 key->offset_cap = 2 * key->offset_cap + 1;
 205                 key->offsets = reftable_realloc(
 206                         key->offsets, sizeof(uint64_t) * key->offset_cap);
 207         }
 208
 209         key->offsets[key->offset_len++] = off;
 210 }
 211
 212 static int writer_add_record(struct reftable_writer *w,
 213                              struct reftable_record *rec)
 214 {
 215         struct strbuf key = STRBUF_INIT;
 216         int err = -1;
 217         reftable_record_key(rec, &key);
 218         if (strbuf_cmp(&w->last_key, &key) >= 0) {
 219                 err = REFTABLE_API_ERROR;
 220                 goto done;
 221         }
 222
 223         strbuf_reset(&w->last_key);
 224         strbuf_addbuf(&w->last_key, &key);
 225         if (!w->block_writer) {
 226                 writer_reinit_block_writer(w, reftable_record_type(rec));
 227         }
 228
 229         assert(block_writer_type(w->block_writer) == reftable_record_type(rec));
 230
 231         if (block_writer_add(w->block_writer, rec) == 0) {
 232                 err = 0;
 233                 goto done;
 234         }
 235
 236         err = writer_flush_block(w);
 237         if (err < 0) {
 238                 goto done;
 239         }
 240
 241         writer_reinit_block_writer(w, reftable_record_type(rec));
 242         err = block_writer_add(w->block_writer, rec);
 243         if (err == -1) {
 244                 /* we are writing into memory, so an error can only mean it
 245                  * doesn't fit. */
 246                 err = REFTABLE_ENTRY_TOO_BIG_ERROR;
 247                 goto done;
 248         }
 249
 250 done:
 251         strbuf_release(&key);
 252         return err;
 253 }
 254
 255 int reftable_writer_add_ref(struct reftable_writer *w,
 256                             struct reftable_ref_record *ref)
 257 {
 258         struct reftable_record rec = {
 259                 .type = BLOCK_TYPE_REF,
 260                 .u = {
 261                         .ref = *ref
 262                 },
 263         };
 264         int err = 0;
 265
 266         if (!ref->refname)
 267                 return REFTABLE_API_ERROR;
 268         if (ref->update_index < w->min_update_index ||
 269             ref->update_index > w->max_update_index)
 270                 return REFTABLE_API_ERROR;
 271
 272         rec.u.ref.update_index -= w->min_update_index;
 273
 274         err = writer_add_record(w, &rec);
 275         if (err < 0)
 276                 return err;
 277
 278         if (!w->opts.skip_index_objects && reftable_ref_record_val1(ref)) {
 279                 struct strbuf h = STRBUF_INIT;
 280                 strbuf_add(&h, (char *)reftable_ref_record_val1(ref),
 281                            hash_size(w->opts.hash_id));
 282                 writer_index_hash(w, &h);
 283                 strbuf_release(&h);
 284         }
 285
 286         if (!w->opts.skip_index_objects && reftable_ref_record_val2(ref)) {
 287                 struct strbuf h = STRBUF_INIT;
 288                 strbuf_add(&h, reftable_ref_record_val2(ref),
 289                            hash_size(w->opts.hash_id));
 290                 writer_index_hash(w, &h);
 291                 strbuf_release(&h);
 292         }
 293         return 0;
 294 }
 295
 296 int reftable_writer_add_refs(struct reftable_writer *w,
 297                              struct reftable_ref_record *refs, int n)
 298 {
 299         int err = 0;
 300         int i = 0;
 301         QSORT(refs, n, reftable_ref_record_compare_name);
 302         for (i = 0; err == 0 && i < n; i++) {
 303                 err = reftable_writer_add_ref(w, &refs[i]);
 304         }
 305         return err;
 306 }
 307
 308 static int reftable_writer_add_log_verbatim(struct reftable_writer *w,
 309                                             struct reftable_log_record *log)
 310 {
 311         struct reftable_record rec = {
 312                 .type = BLOCK_TYPE_LOG,
 313                 .u = {
 314                         .log = *log,
 315                 },
 316         };
 317         if (w->block_writer &&
 318             block_writer_type(w->block_writer) == BLOCK_TYPE_REF) {
 319                 int err = writer_finish_public_section(w);
 320                 if (err < 0)
 321                         return err;
 322         }
 323
 324         w->next -= w->pending_padding;
 325         w->pending_padding = 0;
 326         return writer_add_record(w, &rec);
 327 }
 328
 329 int reftable_writer_add_log(struct reftable_writer *w,
 330                             struct reftable_log_record *log)
 331 {
 332         char *input_log_message = NULL;
 333         struct strbuf cleaned_message = STRBUF_INIT;
 334         int err = 0;
 335
 336         if (log->value_type == REFTABLE_LOG_DELETION)
 337                 return reftable_writer_add_log_verbatim(w, log);
 338
 339         if (!log->refname)
 340                 return REFTABLE_API_ERROR;
 341
 342         input_log_message = log->value.update.message;
 343         if (!w->opts.exact_log_message && log->value.update.message) {
 344                 strbuf_addstr(&cleaned_message, log->value.update.message);
 345                 while (cleaned_message.len &&
 346                        cleaned_message.buf[cleaned_message.len - 1] == '\n')
 347                         strbuf_setlen(&cleaned_message,
 348                                       cleaned_message.len - 1);
 349                 if (strchr(cleaned_message.buf, '\n')) {
 350                         /* multiple lines not allowed. */
 351                         err = REFTABLE_API_ERROR;
 352                         goto done;
 353                 }
 354                 strbuf_addstr(&cleaned_message, "\n");
 355                 log->value.update.message = cleaned_message.buf;
 356         }
 357
 358         err = reftable_writer_add_log_verbatim(w, log);
 359         log->value.update.message = input_log_message;
 360 done:
 361         strbuf_release(&cleaned_message);
 362         return err;
 363 }
 364
 365 int reftable_writer_add_logs(struct reftable_writer *w,
 366                              struct reftable_log_record *logs, int n)
 367 {
 368         int err = 0;
 369         int i = 0;
 370         QSORT(logs, n, reftable_log_record_compare_key);
 371
 372         for (i = 0; err == 0 && i < n; i++) {
 373                 err = reftable_writer_add_log(w, &logs[i]);
 374         }
 375         return err;
 376 }
 377
 378 static int writer_finish_section(struct reftable_writer *w)
 379 {
 380         uint8_t typ = block_writer_type(w->block_writer);
 381         uint64_t index_start = 0;
 382         int max_level = 0;
 383         int threshold = w->opts.unpadded ? 1 : 3;
 384         int before_blocks = w->stats.idx_stats.blocks;
 385         int err = writer_flush_block(w);
 386         int i = 0;
 387         struct reftable_block_stats *bstats = NULL;
 388         if (err < 0)
 389                 return err;
 390
 391         while (w->index_len > threshold) {
 392                 struct reftable_index_record *idx = NULL;
 393                 int idx_len = 0;
 394
 395                 max_level++;
 396                 index_start = w->next;
 397                 writer_reinit_block_writer(w, BLOCK_TYPE_INDEX);
 398
 399                 idx = w->index;
 400                 idx_len = w->index_len;
 401
 402                 w->index = NULL;
 403                 w->index_len = 0;
 404                 w->index_cap = 0;
 405                 for (i = 0; i < idx_len; i++) {
 406                         struct reftable_record rec = {
 407                                 .type = BLOCK_TYPE_INDEX,
 408                                 .u = {
 409                                         .idx = idx[i],
 410                                 },
 411                         };
 412                         if (block_writer_add(w->block_writer, &rec) == 0) {
 413                                 continue;
 414                         }
 415
 416                         err = writer_flush_block(w);
 417                         if (err < 0)
 418                                 return err;
 419
 420                         writer_reinit_block_writer(w, BLOCK_TYPE_INDEX);
 421
 422                         err = block_writer_add(w->block_writer, &rec);
 423                         if (err != 0) {
 424                                 /* write into fresh block should always succeed
 425                                  */
 426                                 abort();
 427                         }
 428                 }
 429                 for (i = 0; i < idx_len; i++) {
 430                         strbuf_release(&idx[i].last_key);
 431                 }
 432                 reftable_free(idx);
 433         }
 434
 435         writer_clear_index(w);
 436
 437         err = writer_flush_block(w);
 438         if (err < 0)
 439                 return err;
 440
 441         bstats = writer_reftable_block_stats(w, typ);
 442         bstats->index_blocks = w->stats.idx_stats.blocks - before_blocks;
 443         bstats->index_offset = index_start;
 444         bstats->max_index_level = max_level;
 445
 446         /* Reinit lastKey, as the next section can start with any key. */
 447         w->last_key.len = 0;
 448
 449         return 0;
 450 }
 451
 452 struct common_prefix_arg {
 453         struct strbuf *last;
 454         int max;
 455 };
 456
 457 static void update_common(void *void_arg, void *key)
 458 {
 459         struct common_prefix_arg *arg = void_arg;
 460         struct obj_index_tree_node *entry = key;
 461         if (arg->last) {
 462                 int n = common_prefix_size(&entry->hash, arg->last);
 463                 if (n > arg->max) {
 464                         arg->max = n;
 465                 }
 466         }
 467         arg->last = &entry->hash;
 468 }
 469
 470 struct write_record_arg {
 471         struct reftable_writer *w;
 472         int err;
 473 };
 474
 475 static void write_object_record(void *void_arg, void *key)
 476 {
 477         struct write_record_arg *arg = void_arg;
 478         struct obj_index_tree_node *entry = key;
 479         struct reftable_record
 480                 rec = { .type = BLOCK_TYPE_OBJ,
 481                         .u.obj = {
 482                                 .hash_prefix = (uint8_t *)entry->hash.buf,
 483                                 .hash_prefix_len = arg->w->stats.object_id_len,
 484                                 .offsets = entry->offsets,
 485                                 .offset_len = entry->offset_len,
 486                         } };
 487         if (arg->err < 0)
 488                 goto done;
 489
 490         arg->err = block_writer_add(arg->w->block_writer, &rec);
 491         if (arg->err == 0)
 492                 goto done;
 493
 494         arg->err = writer_flush_block(arg->w);
 495         if (arg->err < 0)
 496                 goto done;
 497
 498         writer_reinit_block_writer(arg->w, BLOCK_TYPE_OBJ);
 499         arg->err = block_writer_add(arg->w->block_writer, &rec);
 500         if (arg->err == 0)
 501                 goto done;
 502
 503         rec.u.obj.offset_len = 0;
 504         arg->err = block_writer_add(arg->w->block_writer, &rec);
 505
 506         /* Should be able to write into a fresh block. */
 507         assert(arg->err == 0);
 508
 509 done:;
 510 }
 511
 512 static void object_record_free(void *void_arg, void *key)
 513 {
 514         struct obj_index_tree_node *entry = key;
 515
 516         FREE_AND_NULL(entry->offsets);
 517         strbuf_release(&entry->hash);
 518         reftable_free(entry);
 519 }
 520
 521 static int writer_dump_object_index(struct reftable_writer *w)
 522 {
 523         struct write_record_arg closure = { .w = w };
 524         struct common_prefix_arg common = {
 525                 .max = 1,               /* obj_id_len should be >= 2. */
 526         };
 527         if (w->obj_index_tree) {
 528                 infix_walk(w->obj_index_tree, &update_common, &common);
 529         }
 530         w->stats.object_id_len = common.max + 1;
 531
 532         writer_reinit_block_writer(w, BLOCK_TYPE_OBJ);
 533
 534         if (w->obj_index_tree) {
 535                 infix_walk(w->obj_index_tree, &write_object_record, &closure);
 536         }
 537
 538         if (closure.err < 0)
 539                 return closure.err;
 540         return writer_finish_section(w);
 541 }
 542
 543 static int writer_finish_public_section(struct reftable_writer *w)
 544 {
 545         uint8_t typ = 0;
 546         int err = 0;
 547
 548         if (!w->block_writer)
 549                 return 0;
 550
 551         typ = block_writer_type(w->block_writer);
 552         err = writer_finish_section(w);
 553         if (err < 0)
 554                 return err;
 555         if (typ == BLOCK_TYPE_REF && !w->opts.skip_index_objects &&
 556             w->stats.ref_stats.index_blocks > 0) {
 557                 err = writer_dump_object_index(w);
 558                 if (err < 0)
 559                         return err;
 560         }
 561
 562         if (w->obj_index_tree) {
 563                 infix_walk(w->obj_index_tree, &object_record_free, NULL);
 564                 tree_free(w->obj_index_tree);
 565                 w->obj_index_tree = NULL;
 566         }
 567
 568         w->block_writer = NULL;
 569         return 0;
 570 }
 571
 572 int reftable_writer_close(struct reftable_writer *w)
 573 {
 574         uint8_t footer[72];
 575         uint8_t *p = footer;
 576         int err = writer_finish_public_section(w);
 577         int empty_table = w->next == 0;
 578         if (err != 0)
 579                 goto done;
 580         w->pending_padding = 0;
 581         if (empty_table) {
 582                 /* Empty tables need a header anyway. */
 583                 uint8_t header[28];
 584                 int n = writer_write_header(w, header);
 585                 err = padded_write(w, header, n, 0);
 586                 if (err < 0)
 587                         goto done;
 588         }
 589
 590         p += writer_write_header(w, footer);
 591         put_be64(p, w->stats.ref_stats.index_offset);
 592         p += 8;
 593         put_be64(p, (w->stats.obj_stats.offset) << 5 | w->stats.object_id_len);
 594         p += 8;
 595         put_be64(p, w->stats.obj_stats.index_offset);
 596         p += 8;
 597
 598         put_be64(p, w->stats.log_stats.offset);
 599         p += 8;
 600         put_be64(p, w->stats.log_stats.index_offset);
 601         p += 8;
 602
 603         put_be32(p, crc32(0, footer, p - footer));
 604         p += 4;
 605
 606         err = padded_write(w, footer, footer_size(writer_version(w)), 0);
 607         if (err < 0)
 608                 goto done;
 609
 610         if (empty_table) {
 611                 err = REFTABLE_EMPTY_TABLE_ERROR;
 612                 goto done;
 613         }
 614
 615 done:
 616         /* free up memory. */
 617         block_writer_release(&w->block_writer_data);
 618         writer_clear_index(w);
 619         strbuf_release(&w->last_key);
 620         return err;
 621 }
 622
 623 static void writer_clear_index(struct reftable_writer *w)
 624 {
 625         int i = 0;
 626         for (i = 0; i < w->index_len; i++) {
 627                 strbuf_release(&w->index[i].last_key);
 628         }
 629
 630         FREE_AND_NULL(w->index);
 631         w->index_len = 0;
 632         w->index_cap = 0;
 633 }
 634
 635 static const int debug = 0;
 636
 637 static int writer_flush_nonempty_block(struct reftable_writer *w)
 638 {
 639         uint8_t typ = block_writer_type(w->block_writer);
 640         struct reftable_block_stats *bstats =
 641                 writer_reftable_block_stats(w, typ);
 642         uint64_t block_typ_off = (bstats->blocks == 0) ? w->next : 0;
 643         int raw_bytes = block_writer_finish(w->block_writer);
 644         int padding = 0;
 645         int err = 0;
 646         struct reftable_index_record ir = { .last_key = STRBUF_INIT };
 647         if (raw_bytes < 0)
 648                 return raw_bytes;
 649
 650         if (!w->opts.unpadded && typ != BLOCK_TYPE_LOG) {
 651                 padding = w->opts.block_size - raw_bytes;
 652         }
 653
 654         if (block_typ_off > 0) {
 655                 bstats->offset = block_typ_off;
 656         }
 657
 658         bstats->entries += w->block_writer->entries;
 659         bstats->restarts += w->block_writer->restart_len;
 660         bstats->blocks++;
 661         w->stats.blocks++;
 662
 663         if (debug) {
 664                 fprintf(stderr, "block %c off %" PRIu64 " sz %d (%d)\n", typ,
 665                         w->next, raw_bytes,
 666                         get_be24(w->block + w->block_writer->header_off + 1));
 667         }
 668
 669         if (w->next == 0) {
 670                 writer_write_header(w, w->block);
 671         }
 672
 673         err = padded_write(w, w->block, raw_bytes, padding);
 674         if (err < 0)
 675                 return err;
 676
 677         if (w->index_cap == w->index_len) {
 678                 w->index_cap = 2 * w->index_cap + 1;
 679                 w->index = reftable_realloc(
 680                         w->index,
 681                         sizeof(struct reftable_index_record) * w->index_cap);
 682         }
 683
 684         ir.offset = w->next;
 685         strbuf_reset(&ir.last_key);
 686         strbuf_addbuf(&ir.last_key, &w->block_writer->last_key);
 687         w->index[w->index_len] = ir;
 688
 689         w->index_len++;
 690         w->next += padding + raw_bytes;
 691         w->block_writer = NULL;
 692         return 0;
 693 }
 694
 695 static int writer_flush_block(struct reftable_writer *w)
 696 {
 697         if (!w->block_writer)
 698                 return 0;
 699         if (w->block_writer->entries == 0)
 700                 return 0;
 701         return writer_flush_nonempty_block(w);
 702 }
 703
 704 const struct reftable_stats *reftable_writer_stats(struct reftable_writer *w)
 705 {
 706         return &w->stats;
 707 }