reftable/stack.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 "stack.h"
  10
  11 #include "system.h"
  12 #include "merged.h"
  13 #include "reader.h"
  14 #include "refname.h"
  15 #include "reftable-error.h"
  16 #include "reftable-record.h"
  17 #include "reftable-merged.h"
  18 #include "writer.h"
  19
  20 static int stack_try_add(struct reftable_stack *st,
  21                          int (*write_table)(struct reftable_writer *wr,
  22                                             void *arg),
  23                          void *arg);
  24 static int stack_write_compact(struct reftable_stack *st,
  25                                struct reftable_writer *wr, int first, int last,
  26                                struct reftable_log_expiry_config *config);
  27 static int stack_check_addition(struct reftable_stack *st,
  28                                 const char *new_tab_name);
  29 static void reftable_addition_close(struct reftable_addition *add);
  30 static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
  31                                              int reuse_open);
  32
  33 static void stack_filename(struct strbuf *dest, struct reftable_stack *st,
  34                            const char *name)
  35 {
  36         strbuf_reset(dest);
  37         strbuf_addstr(dest, st->reftable_dir);
  38         strbuf_addstr(dest, "/");
  39         strbuf_addstr(dest, name);
  40 }
  41
  42 static ssize_t reftable_fd_write(void *arg, const void *data, size_t sz)
  43 {
  44         int *fdp = (int *)arg;
  45         return write(*fdp, data, sz);
  46 }
  47
  48 int reftable_new_stack(struct reftable_stack **dest, const char *dir,
  49                        struct reftable_write_options config)
  50 {
  51         struct reftable_stack *p =
  52                 reftable_calloc(sizeof(struct reftable_stack));
  53         struct strbuf list_file_name = STRBUF_INIT;
  54         int err = 0;
  55
  56         if (config.hash_id == 0) {
  57                 config.hash_id = GIT_SHA1_FORMAT_ID;
  58         }
  59
  60         *dest = NULL;
  61
  62         strbuf_reset(&list_file_name);
  63         strbuf_addstr(&list_file_name, dir);
  64         strbuf_addstr(&list_file_name, "/tables.list");
  65
  66         p->list_file = strbuf_detach(&list_file_name, NULL);
  67         p->reftable_dir = xstrdup(dir);
  68         p->config = config;
  69
  70         err = reftable_stack_reload_maybe_reuse(p, 1);
  71         if (err < 0) {
  72                 reftable_stack_destroy(p);
  73         } else {
  74                 *dest = p;
  75         }
  76         return err;
  77 }
  78
  79 static int fd_read_lines(int fd, char ***namesp)
  80 {
  81         off_t size = lseek(fd, 0, SEEK_END);
  82         char *buf = NULL;
  83         int err = 0;
  84         if (size < 0) {
  85                 err = REFTABLE_IO_ERROR;
  86                 goto done;
  87         }
  88         err = lseek(fd, 0, SEEK_SET);
  89         if (err < 0) {
  90                 err = REFTABLE_IO_ERROR;
  91                 goto done;
  92         }
  93
  94         buf = reftable_malloc(size + 1);
  95         if (read(fd, buf, size) != size) {
  96                 err = REFTABLE_IO_ERROR;
  97                 goto done;
  98         }
  99         buf[size] = 0;
 100
 101         parse_names(buf, size, namesp);
 102
 103 done:
 104         reftable_free(buf);
 105         return err;
 106 }
 107
 108 int read_lines(const char *filename, char ***namesp)
 109 {
 110         int fd = open(filename, O_RDONLY);
 111         int err = 0;
 112         if (fd < 0) {
 113                 if (errno == ENOENT) {
 114                         *namesp = reftable_calloc(sizeof(char *));
 115                         return 0;
 116                 }
 117
 118                 return REFTABLE_IO_ERROR;
 119         }
 120         err = fd_read_lines(fd, namesp);
 121         close(fd);
 122         return err;
 123 }
 124
 125 struct reftable_merged_table *
 126 reftable_stack_merged_table(struct reftable_stack *st)
 127 {
 128         return st->merged;
 129 }
 130
 131 static int has_name(char **names, const char *name)
 132 {
 133         while (*names) {
 134                 if (!strcmp(*names, name))
 135                         return 1;
 136                 names++;
 137         }
 138         return 0;
 139 }
 140
 141 /* Close and free the stack */
 142 void reftable_stack_destroy(struct reftable_stack *st)
 143 {
 144         char **names = NULL;
 145         int err = 0;
 146         if (st->merged) {
 147                 reftable_merged_table_free(st->merged);
 148                 st->merged = NULL;
 149         }
 150
 151         err = read_lines(st->list_file, &names);
 152         if (err < 0) {
 153                 FREE_AND_NULL(names);
 154         }
 155
 156         if (st->readers) {
 157                 int i = 0;
 158                 struct strbuf filename = STRBUF_INIT;
 159                 for (i = 0; i < st->readers_len; i++) {
 160                         const char *name = reader_name(st->readers[i]);
 161                         strbuf_reset(&filename);
 162                         if (names && !has_name(names, name)) {
 163                                 stack_filename(&filename, st, name);
 164                         }
 165                         reftable_reader_free(st->readers[i]);
 166
 167                         if (filename.len) {
 168                                 /* On Windows, can only unlink after closing. */
 169                                 unlink(filename.buf);
 170                         }
 171                 }
 172                 strbuf_release(&filename);
 173                 st->readers_len = 0;
 174                 FREE_AND_NULL(st->readers);
 175         }
 176         FREE_AND_NULL(st->list_file);
 177         FREE_AND_NULL(st->reftable_dir);
 178         reftable_free(st);
 179         free_names(names);
 180 }
 181
 182 static struct reftable_reader **stack_copy_readers(struct reftable_stack *st,
 183                                                    int cur_len)
 184 {
 185         struct reftable_reader **cur =
 186                 reftable_calloc(sizeof(struct reftable_reader *) * cur_len);
 187         int i = 0;
 188         for (i = 0; i < cur_len; i++) {
 189                 cur[i] = st->readers[i];
 190         }
 191         return cur;
 192 }
 193
 194 static int reftable_stack_reload_once(struct reftable_stack *st, char **names,
 195                                       int reuse_open)
 196 {
 197         int cur_len = !st->merged ? 0 : st->merged->stack_len;
 198         struct reftable_reader **cur = stack_copy_readers(st, cur_len);
 199         int err = 0;
 200         int names_len = names_length(names);
 201         struct reftable_reader **new_readers =
 202                 reftable_calloc(sizeof(struct reftable_reader *) * names_len);
 203         struct reftable_table *new_tables =
 204                 reftable_calloc(sizeof(struct reftable_table) * names_len);
 205         int new_readers_len = 0;
 206         struct reftable_merged_table *new_merged = NULL;
 207         int i;
 208
 209         while (*names) {
 210                 struct reftable_reader *rd = NULL;
 211                 char *name = *names++;
 212
 213                 /* this is linear; we assume compaction keeps the number of
 214                    tables under control so this is not quadratic. */
 215                 int j = 0;
 216                 for (j = 0; reuse_open && j < cur_len; j++) {
 217                         if (cur[j] && 0 == strcmp(cur[j]->name, name)) {
 218                                 rd = cur[j];
 219                                 cur[j] = NULL;
 220                                 break;
 221                         }
 222                 }
 223
 224                 if (!rd) {
 225                         struct reftable_block_source src = { NULL };
 226                         struct strbuf table_path = STRBUF_INIT;
 227                         stack_filename(&table_path, st, name);
 228
 229                         err = reftable_block_source_from_file(&src,
 230                                                               table_path.buf);
 231                         strbuf_release(&table_path);
 232
 233                         if (err < 0)
 234                                 goto done;
 235
 236                         err = reftable_new_reader(&rd, &src, name);
 237                         if (err < 0)
 238                                 goto done;
 239                 }
 240
 241                 new_readers[new_readers_len] = rd;
 242                 reftable_table_from_reader(&new_tables[new_readers_len], rd);
 243                 new_readers_len++;
 244         }
 245
 246         /* success! */
 247         err = reftable_new_merged_table(&new_merged, new_tables,
 248                                         new_readers_len, st->config.hash_id);
 249         if (err < 0)
 250                 goto done;
 251
 252         new_tables = NULL;
 253         st->readers_len = new_readers_len;
 254         if (st->merged) {
 255                 merged_table_release(st->merged);
 256                 reftable_merged_table_free(st->merged);
 257         }
 258         if (st->readers) {
 259                 reftable_free(st->readers);
 260         }
 261         st->readers = new_readers;
 262         new_readers = NULL;
 263         new_readers_len = 0;
 264
 265         new_merged->suppress_deletions = 1;
 266         st->merged = new_merged;
 267         for (i = 0; i < cur_len; i++) {
 268                 if (cur[i]) {
 269                         const char *name = reader_name(cur[i]);
 270                         struct strbuf filename = STRBUF_INIT;
 271                         stack_filename(&filename, st, name);
 272
 273                         reader_close(cur[i]);
 274                         reftable_reader_free(cur[i]);
 275
 276                         /* On Windows, can only unlink after closing. */
 277                         unlink(filename.buf);
 278
 279                         strbuf_release(&filename);
 280                 }
 281         }
 282
 283 done:
 284         for (i = 0; i < new_readers_len; i++) {
 285                 reader_close(new_readers[i]);
 286                 reftable_reader_free(new_readers[i]);
 287         }
 288         reftable_free(new_readers);
 289         reftable_free(new_tables);
 290         reftable_free(cur);
 291         return err;
 292 }
 293
 294 /* return negative if a before b. */
 295 static int tv_cmp(struct timeval *a, struct timeval *b)
 296 {
 297         time_t diff = a->tv_sec - b->tv_sec;
 298         int udiff = a->tv_usec - b->tv_usec;
 299
 300         if (diff != 0)
 301                 return diff;
 302
 303         return udiff;
 304 }
 305
 306 static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
 307                                              int reuse_open)
 308 {
 309         struct timeval deadline = { 0 };
 310         int err = gettimeofday(&deadline, NULL);
 311         int64_t delay = 0;
 312         int tries = 0;
 313         if (err < 0)
 314                 return err;
 315
 316         deadline.tv_sec += 3;
 317         while (1) {
 318                 char **names = NULL;
 319                 char **names_after = NULL;
 320                 struct timeval now = { 0 };
 321                 int err = gettimeofday(&now, NULL);
 322                 int err2 = 0;
 323                 if (err < 0) {
 324                         return err;
 325                 }
 326
 327                 /* Only look at deadlines after the first few times. This
 328                    simplifies debugging in GDB */
 329                 tries++;
 330                 if (tries > 3 && tv_cmp(&now, &deadline) >= 0) {
 331                         break;
 332                 }
 333
 334                 err = read_lines(st->list_file, &names);
 335                 if (err < 0) {
 336                         free_names(names);
 337                         return err;
 338                 }
 339                 err = reftable_stack_reload_once(st, names, reuse_open);
 340                 if (err == 0) {
 341                         free_names(names);
 342                         break;
 343                 }
 344                 if (err != REFTABLE_NOT_EXIST_ERROR) {
 345                         free_names(names);
 346                         return err;
 347                 }
 348
 349                 /* err == REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent
 350                    writer. Check if there was one by checking if the name list
 351                    changed.
 352                 */
 353                 err2 = read_lines(st->list_file, &names_after);
 354                 if (err2 < 0) {
 355                         free_names(names);
 356                         return err2;
 357                 }
 358
 359                 if (names_equal(names_after, names)) {
 360                         free_names(names);
 361                         free_names(names_after);
 362                         return err;
 363                 }
 364                 free_names(names);
 365                 free_names(names_after);
 366
 367                 delay = delay + (delay * rand()) / RAND_MAX + 1;
 368                 sleep_millisec(delay);
 369         }
 370
 371         return 0;
 372 }
 373
 374 /* -1 = error
 375  0 = up to date
 376  1 = changed. */
 377 static int stack_uptodate(struct reftable_stack *st)
 378 {
 379         char **names = NULL;
 380         int err = read_lines(st->list_file, &names);
 381         int i = 0;
 382         if (err < 0)
 383                 return err;
 384
 385         for (i = 0; i < st->readers_len; i++) {
 386                 if (!names[i]) {
 387                         err = 1;
 388                         goto done;
 389                 }
 390
 391                 if (strcmp(st->readers[i]->name, names[i])) {
 392                         err = 1;
 393                         goto done;
 394                 }
 395         }
 396
 397         if (names[st->merged->stack_len]) {
 398                 err = 1;
 399                 goto done;
 400         }
 401
 402 done:
 403         free_names(names);
 404         return err;
 405 }
 406
 407 int reftable_stack_reload(struct reftable_stack *st)
 408 {
 409         int err = stack_uptodate(st);
 410         if (err > 0)
 411                 return reftable_stack_reload_maybe_reuse(st, 1);
 412         return err;
 413 }
 414
 415 int reftable_stack_add(struct reftable_stack *st,
 416                        int (*write)(struct reftable_writer *wr, void *arg),
 417                        void *arg)
 418 {
 419         int err = stack_try_add(st, write, arg);
 420         if (err < 0) {
 421                 if (err == REFTABLE_LOCK_ERROR) {
 422                         /* Ignore error return, we want to propagate
 423                            REFTABLE_LOCK_ERROR.
 424                         */
 425                         reftable_stack_reload(st);
 426                 }
 427                 return err;
 428         }
 429
 430         if (!st->disable_auto_compact)
 431                 return reftable_stack_auto_compact(st);
 432
 433         return 0;
 434 }
 435
 436 static void format_name(struct strbuf *dest, uint64_t min, uint64_t max)
 437 {
 438         char buf[100];
 439         uint32_t rnd = (uint32_t)rand();
 440         snprintf(buf, sizeof(buf), "0x%012" PRIx64 "-0x%012" PRIx64 "-%08x",
 441                  min, max, rnd);
 442         strbuf_reset(dest);
 443         strbuf_addstr(dest, buf);
 444 }
 445
 446 struct reftable_addition {
 447         int lock_file_fd;
 448         struct strbuf lock_file_name;
 449         struct reftable_stack *stack;
 450
 451         char **new_tables;
 452         int new_tables_len;
 453         uint64_t next_update_index;
 454 };
 455
 456 #define REFTABLE_ADDITION_INIT                \
 457         {                                     \
 458                 .lock_file_name = STRBUF_INIT \
 459         }
 460
 461 static int reftable_stack_init_addition(struct reftable_addition *add,
 462                                         struct reftable_stack *st)
 463 {
 464         int err = 0;
 465         add->stack = st;
 466
 467         strbuf_reset(&add->lock_file_name);
 468         strbuf_addstr(&add->lock_file_name, st->list_file);
 469         strbuf_addstr(&add->lock_file_name, ".lock");
 470
 471         add->lock_file_fd = open(add->lock_file_name.buf,
 472                                  O_EXCL | O_CREAT | O_WRONLY, 0666);
 473         if (add->lock_file_fd < 0) {
 474                 if (errno == EEXIST) {
 475                         err = REFTABLE_LOCK_ERROR;
 476                 } else {
 477                         err = REFTABLE_IO_ERROR;
 478                 }
 479                 goto done;
 480         }
 481         if (st->config.default_permissions) {
 482                 if (chmod(add->lock_file_name.buf, st->config.default_permissions) < 0) {
 483                         err = REFTABLE_IO_ERROR;
 484                         goto done;
 485                 }
 486         }
 487
 488         err = stack_uptodate(st);
 489         if (err < 0)
 490                 goto done;
 491
 492         if (err > 1) {
 493                 err = REFTABLE_LOCK_ERROR;
 494                 goto done;
 495         }
 496
 497         add->next_update_index = reftable_stack_next_update_index(st);
 498 done:
 499         if (err) {
 500                 reftable_addition_close(add);
 501         }
 502         return err;
 503 }
 504
 505 static void reftable_addition_close(struct reftable_addition *add)
 506 {
 507         int i = 0;
 508         struct strbuf nm = STRBUF_INIT;
 509         for (i = 0; i < add->new_tables_len; i++) {
 510                 stack_filename(&nm, add->stack, add->new_tables[i]);
 511                 unlink(nm.buf);
 512                 reftable_free(add->new_tables[i]);
 513                 add->new_tables[i] = NULL;
 514         }
 515         reftable_free(add->new_tables);
 516         add->new_tables = NULL;
 517         add->new_tables_len = 0;
 518
 519         if (add->lock_file_fd > 0) {
 520                 close(add->lock_file_fd);
 521                 add->lock_file_fd = 0;
 522         }
 523         if (add->lock_file_name.len > 0) {
 524                 unlink(add->lock_file_name.buf);
 525                 strbuf_release(&add->lock_file_name);
 526         }
 527
 528         strbuf_release(&nm);
 529 }
 530
 531 void reftable_addition_destroy(struct reftable_addition *add)
 532 {
 533         if (!add) {
 534                 return;
 535         }
 536         reftable_addition_close(add);
 537         reftable_free(add);
 538 }
 539
 540 int reftable_addition_commit(struct reftable_addition *add)
 541 {
 542         struct strbuf table_list = STRBUF_INIT;
 543         int i = 0;
 544         int err = 0;
 545         if (add->new_tables_len == 0)
 546                 goto done;
 547
 548         for (i = 0; i < add->stack->merged->stack_len; i++) {
 549                 strbuf_addstr(&table_list, add->stack->readers[i]->name);
 550                 strbuf_addstr(&table_list, "\n");
 551         }
 552         for (i = 0; i < add->new_tables_len; i++) {
 553                 strbuf_addstr(&table_list, add->new_tables[i]);
 554                 strbuf_addstr(&table_list, "\n");
 555         }
 556
 557         err = write(add->lock_file_fd, table_list.buf, table_list.len);
 558         strbuf_release(&table_list);
 559         if (err < 0) {
 560                 err = REFTABLE_IO_ERROR;
 561                 goto done;
 562         }
 563
 564         err = close(add->lock_file_fd);
 565         add->lock_file_fd = 0;
 566         if (err < 0) {
 567                 err = REFTABLE_IO_ERROR;
 568                 goto done;
 569         }
 570
 571         err = rename(add->lock_file_name.buf, add->stack->list_file);
 572         if (err < 0) {
 573                 err = REFTABLE_IO_ERROR;
 574                 goto done;
 575         }
 576
 577         /* success, no more state to clean up. */
 578         strbuf_release(&add->lock_file_name);
 579         for (i = 0; i < add->new_tables_len; i++) {
 580                 reftable_free(add->new_tables[i]);
 581         }
 582         reftable_free(add->new_tables);
 583         add->new_tables = NULL;
 584         add->new_tables_len = 0;
 585
 586         err = reftable_stack_reload(add->stack);
 587 done:
 588         reftable_addition_close(add);
 589         return err;
 590 }
 591
 592 int reftable_stack_new_addition(struct reftable_addition **dest,
 593                                 struct reftable_stack *st)
 594 {
 595         int err = 0;
 596         struct reftable_addition empty = REFTABLE_ADDITION_INIT;
 597         *dest = reftable_calloc(sizeof(**dest));
 598         **dest = empty;
 599         err = reftable_stack_init_addition(*dest, st);
 600         if (err) {
 601                 reftable_free(*dest);
 602                 *dest = NULL;
 603         }
 604         return err;
 605 }
 606
 607 static int stack_try_add(struct reftable_stack *st,
 608                          int (*write_table)(struct reftable_writer *wr,
 609                                             void *arg),
 610                          void *arg)
 611 {
 612         struct reftable_addition add = REFTABLE_ADDITION_INIT;
 613         int err = reftable_stack_init_addition(&add, st);
 614         if (err < 0)
 615                 goto done;
 616         if (err > 0) {
 617                 err = REFTABLE_LOCK_ERROR;
 618                 goto done;
 619         }
 620
 621         err = reftable_addition_add(&add, write_table, arg);
 622         if (err < 0)
 623                 goto done;
 624
 625         err = reftable_addition_commit(&add);
 626 done:
 627         reftable_addition_close(&add);
 628         return err;
 629 }
 630
 631 int reftable_addition_add(struct reftable_addition *add,
 632                           int (*write_table)(struct reftable_writer *wr,
 633                                              void *arg),
 634                           void *arg)
 635 {
 636         struct strbuf temp_tab_file_name = STRBUF_INIT;
 637         struct strbuf tab_file_name = STRBUF_INIT;
 638         struct strbuf next_name = STRBUF_INIT;
 639         struct reftable_writer *wr = NULL;
 640         int err = 0;
 641         int tab_fd = 0;
 642
 643         strbuf_reset(&next_name);
 644         format_name(&next_name, add->next_update_index, add->next_update_index);
 645
 646         stack_filename(&temp_tab_file_name, add->stack, next_name.buf);
 647         strbuf_addstr(&temp_tab_file_name, ".temp.XXXXXX");
 648
 649         tab_fd = mkstemp(temp_tab_file_name.buf);
 650         if (tab_fd < 0) {
 651                 err = REFTABLE_IO_ERROR;
 652                 goto done;
 653         }
 654         if (add->stack->config.default_permissions) {
 655                 if (chmod(temp_tab_file_name.buf, add->stack->config.default_permissions)) {
 656                         err = REFTABLE_IO_ERROR;
 657                         goto done;
 658                 }
 659         }
 660         wr = reftable_new_writer(reftable_fd_write, &tab_fd,
 661                                  &add->stack->config);
 662         err = write_table(wr, arg);
 663         if (err < 0)
 664                 goto done;
 665
 666         err = reftable_writer_close(wr);
 667         if (err == REFTABLE_EMPTY_TABLE_ERROR) {
 668                 err = 0;
 669                 goto done;
 670         }
 671         if (err < 0)
 672                 goto done;
 673
 674         err = close(tab_fd);
 675         tab_fd = 0;
 676         if (err < 0) {
 677                 err = REFTABLE_IO_ERROR;
 678                 goto done;
 679         }
 680
 681         err = stack_check_addition(add->stack, temp_tab_file_name.buf);
 682         if (err < 0)
 683                 goto done;
 684
 685         if (wr->min_update_index < add->next_update_index) {
 686                 err = REFTABLE_API_ERROR;
 687                 goto done;
 688         }
 689
 690         format_name(&next_name, wr->min_update_index, wr->max_update_index);
 691         strbuf_addstr(&next_name, ".ref");
 692
 693         stack_filename(&tab_file_name, add->stack, next_name.buf);
 694
 695         /*
 696           On windows, this relies on rand() picking a unique destination name.
 697           Maybe we should do retry loop as well?
 698          */
 699         err = rename(temp_tab_file_name.buf, tab_file_name.buf);
 700         if (err < 0) {
 701                 err = REFTABLE_IO_ERROR;
 702                 goto done;
 703         }
 704
 705         add->new_tables = reftable_realloc(add->new_tables,
 706                                            sizeof(*add->new_tables) *
 707                                                    (add->new_tables_len + 1));
 708         add->new_tables[add->new_tables_len] = strbuf_detach(&next_name, NULL);
 709         add->new_tables_len++;
 710 done:
 711         if (tab_fd > 0) {
 712                 close(tab_fd);
 713                 tab_fd = 0;
 714         }
 715         if (temp_tab_file_name.len > 0) {
 716                 unlink(temp_tab_file_name.buf);
 717         }
 718
 719         strbuf_release(&temp_tab_file_name);
 720         strbuf_release(&tab_file_name);
 721         strbuf_release(&next_name);
 722         reftable_writer_free(wr);
 723         return err;
 724 }
 725
 726 uint64_t reftable_stack_next_update_index(struct reftable_stack *st)
 727 {
 728         int sz = st->merged->stack_len;
 729         if (sz > 0)
 730                 return reftable_reader_max_update_index(st->readers[sz - 1]) +
 731                        1;
 732         return 1;
 733 }
 734
 735 static int stack_compact_locked(struct reftable_stack *st, int first, int last,
 736                                 struct strbuf *temp_tab,
 737                                 struct reftable_log_expiry_config *config)
 738 {
 739         struct strbuf next_name = STRBUF_INIT;
 740         int tab_fd = -1;
 741         struct reftable_writer *wr = NULL;
 742         int err = 0;
 743
 744         format_name(&next_name,
 745                     reftable_reader_min_update_index(st->readers[first]),
 746                     reftable_reader_max_update_index(st->readers[last]));
 747
 748         stack_filename(temp_tab, st, next_name.buf);
 749         strbuf_addstr(temp_tab, ".temp.XXXXXX");
 750
 751         tab_fd = mkstemp(temp_tab->buf);
 752         wr = reftable_new_writer(reftable_fd_write, &tab_fd, &st->config);
 753
 754         err = stack_write_compact(st, wr, first, last, config);
 755         if (err < 0)
 756                 goto done;
 757         err = reftable_writer_close(wr);
 758         if (err < 0)
 759                 goto done;
 760
 761         err = close(tab_fd);
 762         tab_fd = 0;
 763
 764 done:
 765         reftable_writer_free(wr);
 766         if (tab_fd > 0) {
 767                 close(tab_fd);
 768                 tab_fd = 0;
 769         }
 770         if (err != 0 && temp_tab->len > 0) {
 771                 unlink(temp_tab->buf);
 772                 strbuf_release(temp_tab);
 773         }
 774         strbuf_release(&next_name);
 775         return err;
 776 }
 777
 778 static int stack_write_compact(struct reftable_stack *st,
 779                                struct reftable_writer *wr, int first, int last,
 780                                struct reftable_log_expiry_config *config)
 781 {
 782         int subtabs_len = last - first + 1;
 783         struct reftable_table *subtabs = reftable_calloc(
 784                 sizeof(struct reftable_table) * (last - first + 1));
 785         struct reftable_merged_table *mt = NULL;
 786         int err = 0;
 787         struct reftable_iterator it = { NULL };
 788         struct reftable_ref_record ref = { NULL };
 789         struct reftable_log_record log = { NULL };
 790
 791         uint64_t entries = 0;
 792
 793         int i = 0, j = 0;
 794         for (i = first, j = 0; i <= last; i++) {
 795                 struct reftable_reader *t = st->readers[i];
 796                 reftable_table_from_reader(&subtabs[j++], t);
 797                 st->stats.bytes += t->size;
 798         }
 799         reftable_writer_set_limits(wr, st->readers[first]->min_update_index,
 800                                    st->readers[last]->max_update_index);
 801
 802         err = reftable_new_merged_table(&mt, subtabs, subtabs_len,
 803                                         st->config.hash_id);
 804         if (err < 0) {
 805                 reftable_free(subtabs);
 806                 goto done;
 807         }
 808
 809         err = reftable_merged_table_seek_ref(mt, &it, "");
 810         if (err < 0)
 811                 goto done;
 812
 813         while (1) {
 814                 err = reftable_iterator_next_ref(&it, &ref);
 815                 if (err > 0) {
 816                         err = 0;
 817                         break;
 818                 }
 819                 if (err < 0) {
 820                         break;
 821                 }
 822
 823                 if (first == 0 && reftable_ref_record_is_deletion(&ref)) {
 824                         continue;
 825                 }
 826
 827                 err = reftable_writer_add_ref(wr, &ref);
 828                 if (err < 0) {
 829                         break;
 830                 }
 831                 entries++;
 832         }
 833         reftable_iterator_destroy(&it);
 834
 835         err = reftable_merged_table_seek_log(mt, &it, "");
 836         if (err < 0)
 837                 goto done;
 838
 839         while (1) {
 840                 err = reftable_iterator_next_log(&it, &log);
 841                 if (err > 0) {
 842                         err = 0;
 843                         break;
 844                 }
 845                 if (err < 0) {
 846                         break;
 847                 }
 848                 if (first == 0 && reftable_log_record_is_deletion(&log)) {
 849                         continue;
 850                 }
 851
 852                 if (config && config->min_update_index > 0 &&
 853                     log.update_index < config->min_update_index) {
 854                         continue;
 855                 }
 856
 857                 if (config && config->time > 0 &&
 858                     log.value.update.time < config->time) {
 859                         continue;
 860                 }
 861
 862                 err = reftable_writer_add_log(wr, &log);
 863                 if (err < 0) {
 864                         break;
 865                 }
 866                 entries++;
 867         }
 868
 869 done:
 870         reftable_iterator_destroy(&it);
 871         if (mt) {
 872                 merged_table_release(mt);
 873                 reftable_merged_table_free(mt);
 874         }
 875         reftable_ref_record_release(&ref);
 876         reftable_log_record_release(&log);
 877         st->stats.entries_written += entries;
 878         return err;
 879 }
 880
 881 /* <  0: error. 0 == OK, > 0 attempt failed; could retry. */
 882 static int stack_compact_range(struct reftable_stack *st, int first, int last,
 883                                struct reftable_log_expiry_config *expiry)
 884 {
 885         struct strbuf temp_tab_file_name = STRBUF_INIT;
 886         struct strbuf new_table_name = STRBUF_INIT;
 887         struct strbuf lock_file_name = STRBUF_INIT;
 888         struct strbuf ref_list_contents = STRBUF_INIT;
 889         struct strbuf new_table_path = STRBUF_INIT;
 890         int err = 0;
 891         int have_lock = 0;
 892         int lock_file_fd = -1;
 893         int compact_count = last - first + 1;
 894         char **listp = NULL;
 895         char **delete_on_success =
 896                 reftable_calloc(sizeof(char *) * (compact_count + 1));
 897         char **subtable_locks =
 898                 reftable_calloc(sizeof(char *) * (compact_count + 1));
 899         int i = 0;
 900         int j = 0;
 901         int is_empty_table = 0;
 902
 903         if (first > last || (!expiry && first == last)) {
 904                 err = 0;
 905                 goto done;
 906         }
 907
 908         st->stats.attempts++;
 909
 910         strbuf_reset(&lock_file_name);
 911         strbuf_addstr(&lock_file_name, st->list_file);
 912         strbuf_addstr(&lock_file_name, ".lock");
 913
 914         lock_file_fd =
 915                 open(lock_file_name.buf, O_EXCL | O_CREAT | O_WRONLY, 0666);
 916         if (lock_file_fd < 0) {
 917                 if (errno == EEXIST) {
 918                         err = 1;
 919                 } else {
 920                         err = REFTABLE_IO_ERROR;
 921                 }
 922                 goto done;
 923         }
 924         /* Don't want to write to the lock for now.  */
 925         close(lock_file_fd);
 926         lock_file_fd = -1;
 927
 928         have_lock = 1;
 929         err = stack_uptodate(st);
 930         if (err != 0)
 931                 goto done;
 932
 933         for (i = first, j = 0; i <= last; i++) {
 934                 struct strbuf subtab_file_name = STRBUF_INIT;
 935                 struct strbuf subtab_lock = STRBUF_INIT;
 936                 int sublock_file_fd = -1;
 937
 938                 stack_filename(&subtab_file_name, st,
 939                                reader_name(st->readers[i]));
 940
 941                 strbuf_reset(&subtab_lock);
 942                 strbuf_addbuf(&subtab_lock, &subtab_file_name);
 943                 strbuf_addstr(&subtab_lock, ".lock");
 944
 945                 sublock_file_fd = open(subtab_lock.buf,
 946                                        O_EXCL | O_CREAT | O_WRONLY, 0666);
 947                 if (sublock_file_fd >= 0) {
 948                         close(sublock_file_fd);
 949                 } else if (sublock_file_fd < 0) {
 950                         if (errno == EEXIST) {
 951                                 err = 1;
 952                         } else {
 953                                 err = REFTABLE_IO_ERROR;
 954                         }
 955                 }
 956
 957                 subtable_locks[j] = subtab_lock.buf;
 958                 delete_on_success[j] = subtab_file_name.buf;
 959                 j++;
 960
 961                 if (err != 0)
 962                         goto done;
 963         }
 964
 965         err = unlink(lock_file_name.buf);
 966         if (err < 0)
 967                 goto done;
 968         have_lock = 0;
 969
 970         err = stack_compact_locked(st, first, last, &temp_tab_file_name,
 971                                    expiry);
 972         /* Compaction + tombstones can create an empty table out of non-empty
 973          * tables. */
 974         is_empty_table = (err == REFTABLE_EMPTY_TABLE_ERROR);
 975         if (is_empty_table) {
 976                 err = 0;
 977         }
 978         if (err < 0)
 979                 goto done;
 980
 981         lock_file_fd =
 982                 open(lock_file_name.buf, O_EXCL | O_CREAT | O_WRONLY, 0666);
 983         if (lock_file_fd < 0) {
 984                 if (errno == EEXIST) {
 985                         err = 1;
 986                 } else {
 987                         err = REFTABLE_IO_ERROR;
 988                 }
 989                 goto done;
 990         }
 991         have_lock = 1;
 992         if (st->config.default_permissions) {
 993                 if (chmod(lock_file_name.buf, st->config.default_permissions) < 0) {
 994                         err = REFTABLE_IO_ERROR;
 995                         goto done;
 996                 }
 997         }
 998
 999         format_name(&new_table_name, st->readers[first]->min_update_index,
1000                     st->readers[last]->max_update_index);
1001         strbuf_addstr(&new_table_name, ".ref");
1002
1003         stack_filename(&new_table_path, st, new_table_name.buf);
1004
1005         if (!is_empty_table) {
1006                 /* retry? */
1007                 err = rename(temp_tab_file_name.buf, new_table_path.buf);
1008                 if (err < 0) {
1009                         err = REFTABLE_IO_ERROR;
1010                         goto done;
1011                 }
1012         }
1013
1014         for (i = 0; i < first; i++) {
1015                 strbuf_addstr(&ref_list_contents, st->readers[i]->name);
1016                 strbuf_addstr(&ref_list_contents, "\n");
1017         }
1018         if (!is_empty_table) {
1019                 strbuf_addbuf(&ref_list_contents, &new_table_name);
1020                 strbuf_addstr(&ref_list_contents, "\n");
1021         }
1022         for (i = last + 1; i < st->merged->stack_len; i++) {
1023                 strbuf_addstr(&ref_list_contents, st->readers[i]->name);
1024                 strbuf_addstr(&ref_list_contents, "\n");
1025         }
1026
1027         err = write(lock_file_fd, ref_list_contents.buf, ref_list_contents.len);
1028         if (err < 0) {
1029                 err = REFTABLE_IO_ERROR;
1030                 unlink(new_table_path.buf);
1031                 goto done;
1032         }
1033         err = close(lock_file_fd);
1034         lock_file_fd = -1;
1035         if (err < 0) {
1036                 err = REFTABLE_IO_ERROR;
1037                 unlink(new_table_path.buf);
1038                 goto done;
1039         }
1040
1041         err = rename(lock_file_name.buf, st->list_file);
1042         if (err < 0) {
1043                 err = REFTABLE_IO_ERROR;
1044                 unlink(new_table_path.buf);
1045                 goto done;
1046         }
1047         have_lock = 0;
1048
1049         /* Reload the stack before deleting. On windows, we can only delete the
1050            files after we closed them.
1051         */
1052         err = reftable_stack_reload_maybe_reuse(st, first < last);
1053
1054         listp = delete_on_success;
1055         while (*listp) {
1056                 if (strcmp(*listp, new_table_path.buf)) {
1057                         unlink(*listp);
1058                 }
1059                 listp++;
1060         }
1061
1062 done:
1063         free_names(delete_on_success);
1064
1065         listp = subtable_locks;
1066         while (*listp) {
1067                 unlink(*listp);
1068                 listp++;
1069         }
1070         free_names(subtable_locks);
1071         if (lock_file_fd >= 0) {
1072                 close(lock_file_fd);
1073                 lock_file_fd = -1;
1074         }
1075         if (have_lock) {
1076                 unlink(lock_file_name.buf);
1077         }
1078         strbuf_release(&new_table_name);
1079         strbuf_release(&new_table_path);
1080         strbuf_release(&ref_list_contents);
1081         strbuf_release(&temp_tab_file_name);
1082         strbuf_release(&lock_file_name);
1083         return err;
1084 }
1085
1086 int reftable_stack_compact_all(struct reftable_stack *st,
1087                                struct reftable_log_expiry_config *config)
1088 {
1089         return stack_compact_range(st, 0, st->merged->stack_len - 1, config);
1090 }
1091
1092 static int stack_compact_range_stats(struct reftable_stack *st, int first,
1093                                      int last,
1094                                      struct reftable_log_expiry_config *config)
1095 {
1096         int err = stack_compact_range(st, first, last, config);
1097         if (err > 0) {
1098                 st->stats.failures++;
1099         }
1100         return err;
1101 }
1102
1103 static int segment_size(struct segment *s)
1104 {
1105         return s->end - s->start;
1106 }
1107
1108 int fastlog2(uint64_t sz)
1109 {
1110         int l = 0;
1111         if (sz == 0)
1112                 return 0;
1113         for (; sz; sz /= 2) {
1114                 l++;
1115         }
1116         return l - 1;
1117 }
1118
1119 struct segment *sizes_to_segments(int *seglen, uint64_t *sizes, int n)
1120 {
1121         struct segment *segs = reftable_calloc(sizeof(struct segment) * n);
1122         int next = 0;
1123         struct segment cur = { 0 };
1124         int i = 0;
1125
1126         if (n == 0) {
1127                 *seglen = 0;
1128                 return segs;
1129         }
1130         for (i = 0; i < n; i++) {
1131                 int log = fastlog2(sizes[i]);
1132                 if (cur.log != log && cur.bytes > 0) {
1133                         struct segment fresh = {
1134                                 .start = i,
1135                         };
1136
1137                         segs[next++] = cur;
1138                         cur = fresh;
1139                 }
1140
1141                 cur.log = log;
1142                 cur.end = i + 1;
1143                 cur.bytes += sizes[i];
1144         }
1145         segs[next++] = cur;
1146         *seglen = next;
1147         return segs;
1148 }
1149
1150 struct segment suggest_compaction_segment(uint64_t *sizes, int n)
1151 {
1152         int seglen = 0;
1153         struct segment *segs = sizes_to_segments(&seglen, sizes, n);
1154         struct segment min_seg = {
1155                 .log = 64,
1156         };
1157         int i = 0;
1158         for (i = 0; i < seglen; i++) {
1159                 if (segment_size(&segs[i]) == 1) {
1160                         continue;
1161                 }
1162
1163                 if (segs[i].log < min_seg.log) {
1164                         min_seg = segs[i];
1165                 }
1166         }
1167
1168         while (min_seg.start > 0) {
1169                 int prev = min_seg.start - 1;
1170                 if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev])) {
1171                         break;
1172                 }
1173
1174                 min_seg.start = prev;
1175                 min_seg.bytes += sizes[prev];
1176         }
1177
1178         reftable_free(segs);
1179         return min_seg;
1180 }
1181
1182 static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack *st)
1183 {
1184         uint64_t *sizes =
1185                 reftable_calloc(sizeof(uint64_t) * st->merged->stack_len);
1186         int version = (st->config.hash_id == GIT_SHA1_FORMAT_ID) ? 1 : 2;
1187         int overhead = header_size(version) - 1;
1188         int i = 0;
1189         for (i = 0; i < st->merged->stack_len; i++) {
1190                 sizes[i] = st->readers[i]->size - overhead;
1191         }
1192         return sizes;
1193 }
1194
1195 int reftable_stack_auto_compact(struct reftable_stack *st)
1196 {
1197         uint64_t *sizes = stack_table_sizes_for_compaction(st);
1198         struct segment seg =
1199                 suggest_compaction_segment(sizes, st->merged->stack_len);
1200         reftable_free(sizes);
1201         if (segment_size(&seg) > 0)
1202                 return stack_compact_range_stats(st, seg.start, seg.end - 1,
1203                                                  NULL);
1204
1205         return 0;
1206 }
1207
1208 struct reftable_compaction_stats *
1209 reftable_stack_compaction_stats(struct reftable_stack *st)
1210 {
1211         return &st->stats;
1212 }
1213
1214 int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,
1215                             struct reftable_ref_record *ref)
1216 {
1217         struct reftable_table tab = { NULL };
1218         reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st));
1219         return reftable_table_read_ref(&tab, refname, ref);
1220 }
1221
1222 int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
1223                             struct reftable_log_record *log)
1224 {
1225         struct reftable_iterator it = { NULL };
1226         struct reftable_merged_table *mt = reftable_stack_merged_table(st);
1227         int err = reftable_merged_table_seek_log(mt, &it, refname);
1228         if (err)
1229                 goto done;
1230
1231         err = reftable_iterator_next_log(&it, log);
1232         if (err)
1233                 goto done;
1234
1235         if (strcmp(log->refname, refname) ||
1236             reftable_log_record_is_deletion(log)) {
1237                 err = 1;
1238                 goto done;
1239         }
1240
1241 done:
1242         if (err) {
1243                 reftable_log_record_release(log);
1244         }
1245         reftable_iterator_destroy(&it);
1246         return err;
1247 }
1248
1249 static int stack_check_addition(struct reftable_stack *st,
1250                                 const char *new_tab_name)
1251 {
1252         int err = 0;
1253         struct reftable_block_source src = { NULL };
1254         struct reftable_reader *rd = NULL;
1255         struct reftable_table tab = { NULL };
1256         struct reftable_ref_record *refs = NULL;
1257         struct reftable_iterator it = { NULL };
1258         int cap = 0;
1259         int len = 0;
1260         int i = 0;
1261
1262         if (st->config.skip_name_check)
1263                 return 0;
1264
1265         err = reftable_block_source_from_file(&src, new_tab_name);
1266         if (err < 0)
1267                 goto done;
1268
1269         err = reftable_new_reader(&rd, &src, new_tab_name);
1270         if (err < 0)
1271                 goto done;
1272
1273         err = reftable_reader_seek_ref(rd, &it, "");
1274         if (err > 0) {
1275                 err = 0;
1276                 goto done;
1277         }
1278         if (err < 0)
1279                 goto done;
1280
1281         while (1) {
1282                 struct reftable_ref_record ref = { NULL };
1283                 err = reftable_iterator_next_ref(&it, &ref);
1284                 if (err > 0) {
1285                         break;
1286                 }
1287                 if (err < 0)
1288                         goto done;
1289
1290                 if (len >= cap) {
1291                         cap = 2 * cap + 1;
1292                         refs = reftable_realloc(refs, cap * sizeof(refs[0]));
1293                 }
1294
1295                 refs[len++] = ref;
1296         }
1297
1298         reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st));
1299
1300         err = validate_ref_record_addition(tab, refs, len);
1301
1302 done:
1303         for (i = 0; i < len; i++) {
1304                 reftable_ref_record_release(&refs[i]);
1305         }
1306
1307         free(refs);
1308         reftable_iterator_destroy(&it);
1309         reftable_reader_free(rd);
1310         return err;
1311 }
1312
1313 static int is_table_name(const char *s)
1314 {
1315         const char *dot = strrchr(s, '.');
1316         return dot && !strcmp(dot, ".ref");
1317 }
1318
1319 static void remove_maybe_stale_table(struct reftable_stack *st, uint64_t max,
1320                                      const char *name)
1321 {
1322         int err = 0;
1323         uint64_t update_idx = 0;
1324         struct reftable_block_source src = { NULL };
1325         struct reftable_reader *rd = NULL;
1326         struct strbuf table_path = STRBUF_INIT;
1327         stack_filename(&table_path, st, name);
1328
1329         err = reftable_block_source_from_file(&src, table_path.buf);
1330         if (err < 0)
1331                 goto done;
1332
1333         err = reftable_new_reader(&rd, &src, name);
1334         if (err < 0)
1335                 goto done;
1336
1337         update_idx = reftable_reader_max_update_index(rd);
1338         reftable_reader_free(rd);
1339
1340         if (update_idx <= max) {
1341                 unlink(table_path.buf);
1342         }
1343 done:
1344         strbuf_release(&table_path);
1345 }
1346
1347 static int reftable_stack_clean_locked(struct reftable_stack *st)
1348 {
1349         uint64_t max = reftable_merged_table_max_update_index(
1350                 reftable_stack_merged_table(st));
1351         DIR *dir = opendir(st->reftable_dir);
1352         struct dirent *d = NULL;
1353         if (!dir) {
1354                 return REFTABLE_IO_ERROR;
1355         }
1356
1357         while ((d = readdir(dir))) {
1358                 int i = 0;
1359                 int found = 0;
1360                 if (!is_table_name(d->d_name))
1361                         continue;
1362
1363                 for (i = 0; !found && i < st->readers_len; i++) {
1364                         found = !strcmp(reader_name(st->readers[i]), d->d_name);
1365                 }
1366                 if (found)
1367                         continue;
1368
1369                 remove_maybe_stale_table(st, max, d->d_name);
1370         }
1371
1372         closedir(dir);
1373         return 0;
1374 }
1375
1376 int reftable_stack_clean(struct reftable_stack *st)
1377 {
1378         struct reftable_addition *add = NULL;
1379         int err = reftable_stack_new_addition(&add, st);
1380         if (err < 0) {
1381                 goto done;
1382         }
1383
1384         err = reftable_stack_reload(st);
1385         if (err < 0) {
1386                 goto done;
1387         }
1388
1389         err = reftable_stack_clean_locked(st);
1390
1391 done:
1392         reftable_addition_destroy(add);
1393         return err;
1394 }
1395
1396 int reftable_stack_print_directory(const char *stackdir, uint32_t hash_id)
1397 {
1398         struct reftable_stack *stack = NULL;
1399         struct reftable_write_options cfg = { .hash_id = hash_id };
1400         struct reftable_merged_table *merged = NULL;
1401         struct reftable_table table = { NULL };
1402
1403         int err = reftable_new_stack(&stack, stackdir, cfg);
1404         if (err < 0)
1405                 goto done;
1406
1407         merged = reftable_stack_merged_table(stack);
1408         reftable_table_from_merged_table(&table, merged);
1409         err = reftable_table_print(&table);
1410 done:
1411         if (stack)
1412                 reftable_stack_destroy(stack);
1413         return err;
1414 }