reftable/error: discern locked/outdated errors
[alt-git.git] / reftable / stack.c
blobeaa8bb9c99fe924eb6131d86405e0a19051959fc
1 /*
2 Copyright 2020 Google LLC
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 */
9 #include "stack.h"
11 #include "../write-or-die.h"
12 #include "system.h"
13 #include "merged.h"
14 #include "reader.h"
15 #include "refname.h"
16 #include "reftable-error.h"
17 #include "reftable-record.h"
18 #include "reftable-merged.h"
19 #include "writer.h"
20 #include "tempfile.h"
22 static int stack_try_add(struct reftable_stack *st,
23 int (*write_table)(struct reftable_writer *wr,
24 void *arg),
25 void *arg);
26 static int stack_write_compact(struct reftable_stack *st,
27 struct reftable_writer *wr,
28 size_t first, size_t last,
29 struct reftable_log_expiry_config *config);
30 static int stack_check_addition(struct reftable_stack *st,
31 const char *new_tab_name);
32 static void reftable_addition_close(struct reftable_addition *add);
33 static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
34 int reuse_open);
36 static void stack_filename(struct strbuf *dest, struct reftable_stack *st,
37 const char *name)
39 strbuf_reset(dest);
40 strbuf_addstr(dest, st->reftable_dir);
41 strbuf_addstr(dest, "/");
42 strbuf_addstr(dest, name);
45 static ssize_t reftable_fd_write(void *arg, const void *data, size_t sz)
47 int *fdp = (int *)arg;
48 return write_in_full(*fdp, data, sz);
51 static int reftable_fd_flush(void *arg)
53 int *fdp = (int *)arg;
55 return fsync_component(FSYNC_COMPONENT_REFERENCE, *fdp);
58 int reftable_new_stack(struct reftable_stack **dest, const char *dir,
59 struct reftable_write_options config)
61 struct reftable_stack *p = reftable_calloc(1, sizeof(*p));
62 struct strbuf list_file_name = STRBUF_INIT;
63 int err = 0;
65 if (config.hash_id == 0) {
66 config.hash_id = GIT_SHA1_FORMAT_ID;
69 *dest = NULL;
71 strbuf_reset(&list_file_name);
72 strbuf_addstr(&list_file_name, dir);
73 strbuf_addstr(&list_file_name, "/tables.list");
75 p->list_file = strbuf_detach(&list_file_name, NULL);
76 p->list_fd = -1;
77 p->reftable_dir = xstrdup(dir);
78 p->config = config;
80 err = reftable_stack_reload_maybe_reuse(p, 1);
81 if (err < 0) {
82 reftable_stack_destroy(p);
83 } else {
84 *dest = p;
86 return err;
89 static int fd_read_lines(int fd, char ***namesp)
91 off_t size = lseek(fd, 0, SEEK_END);
92 char *buf = NULL;
93 int err = 0;
94 if (size < 0) {
95 err = REFTABLE_IO_ERROR;
96 goto done;
98 err = lseek(fd, 0, SEEK_SET);
99 if (err < 0) {
100 err = REFTABLE_IO_ERROR;
101 goto done;
104 REFTABLE_ALLOC_ARRAY(buf, size + 1);
105 if (read_in_full(fd, buf, size) != size) {
106 err = REFTABLE_IO_ERROR;
107 goto done;
109 buf[size] = 0;
111 parse_names(buf, size, namesp);
113 done:
114 reftable_free(buf);
115 return err;
118 int read_lines(const char *filename, char ***namesp)
120 int fd = open(filename, O_RDONLY);
121 int err = 0;
122 if (fd < 0) {
123 if (errno == ENOENT) {
124 REFTABLE_CALLOC_ARRAY(*namesp, 1);
125 return 0;
128 return REFTABLE_IO_ERROR;
130 err = fd_read_lines(fd, namesp);
131 close(fd);
132 return err;
135 struct reftable_merged_table *
136 reftable_stack_merged_table(struct reftable_stack *st)
138 return st->merged;
141 static int has_name(char **names, const char *name)
143 while (*names) {
144 if (!strcmp(*names, name))
145 return 1;
146 names++;
148 return 0;
151 /* Close and free the stack */
152 void reftable_stack_destroy(struct reftable_stack *st)
154 char **names = NULL;
155 int err = 0;
156 if (st->merged) {
157 reftable_merged_table_free(st->merged);
158 st->merged = NULL;
161 err = read_lines(st->list_file, &names);
162 if (err < 0) {
163 FREE_AND_NULL(names);
166 if (st->readers) {
167 int i = 0;
168 struct strbuf filename = STRBUF_INIT;
169 for (i = 0; i < st->readers_len; i++) {
170 const char *name = reader_name(st->readers[i]);
171 strbuf_reset(&filename);
172 if (names && !has_name(names, name)) {
173 stack_filename(&filename, st, name);
175 reftable_reader_free(st->readers[i]);
177 if (filename.len) {
178 /* On Windows, can only unlink after closing. */
179 unlink(filename.buf);
182 strbuf_release(&filename);
183 st->readers_len = 0;
184 FREE_AND_NULL(st->readers);
187 if (st->list_fd >= 0) {
188 close(st->list_fd);
189 st->list_fd = -1;
192 FREE_AND_NULL(st->list_file);
193 FREE_AND_NULL(st->reftable_dir);
194 reftable_free(st);
195 free_names(names);
198 static struct reftable_reader **stack_copy_readers(struct reftable_stack *st,
199 int cur_len)
201 struct reftable_reader **cur = reftable_calloc(cur_len, sizeof(*cur));
202 int i = 0;
203 for (i = 0; i < cur_len; i++) {
204 cur[i] = st->readers[i];
206 return cur;
209 static int reftable_stack_reload_once(struct reftable_stack *st, char **names,
210 int reuse_open)
212 size_t cur_len = !st->merged ? 0 : st->merged->stack_len;
213 struct reftable_reader **cur = stack_copy_readers(st, cur_len);
214 size_t names_len = names_length(names);
215 struct reftable_reader **new_readers =
216 reftable_calloc(names_len, sizeof(*new_readers));
217 struct reftable_table *new_tables =
218 reftable_calloc(names_len, sizeof(*new_tables));
219 size_t new_readers_len = 0;
220 struct reftable_merged_table *new_merged = NULL;
221 struct strbuf table_path = STRBUF_INIT;
222 int err = 0;
223 size_t i;
225 while (*names) {
226 struct reftable_reader *rd = NULL;
227 char *name = *names++;
229 /* this is linear; we assume compaction keeps the number of
230 tables under control so this is not quadratic. */
231 for (i = 0; reuse_open && i < cur_len; i++) {
232 if (cur[i] && 0 == strcmp(cur[i]->name, name)) {
233 rd = cur[i];
234 cur[i] = NULL;
235 break;
239 if (!rd) {
240 struct reftable_block_source src = { NULL };
241 stack_filename(&table_path, st, name);
243 err = reftable_block_source_from_file(&src,
244 table_path.buf);
245 if (err < 0)
246 goto done;
248 err = reftable_new_reader(&rd, &src, name);
249 if (err < 0)
250 goto done;
253 new_readers[new_readers_len] = rd;
254 reftable_table_from_reader(&new_tables[new_readers_len], rd);
255 new_readers_len++;
258 /* success! */
259 err = reftable_new_merged_table(&new_merged, new_tables,
260 new_readers_len, st->config.hash_id);
261 if (err < 0)
262 goto done;
264 new_tables = NULL;
265 st->readers_len = new_readers_len;
266 if (st->merged) {
267 merged_table_release(st->merged);
268 reftable_merged_table_free(st->merged);
270 if (st->readers) {
271 reftable_free(st->readers);
273 st->readers = new_readers;
274 new_readers = NULL;
275 new_readers_len = 0;
277 new_merged->suppress_deletions = 1;
278 st->merged = new_merged;
279 for (i = 0; i < cur_len; i++) {
280 if (cur[i]) {
281 const char *name = reader_name(cur[i]);
282 stack_filename(&table_path, st, name);
284 reader_close(cur[i]);
285 reftable_reader_free(cur[i]);
287 /* On Windows, can only unlink after closing. */
288 unlink(table_path.buf);
292 done:
293 for (i = 0; i < new_readers_len; i++) {
294 reader_close(new_readers[i]);
295 reftable_reader_free(new_readers[i]);
297 reftable_free(new_readers);
298 reftable_free(new_tables);
299 reftable_free(cur);
300 strbuf_release(&table_path);
301 return err;
304 /* return negative if a before b. */
305 static int tv_cmp(struct timeval *a, struct timeval *b)
307 time_t diff = a->tv_sec - b->tv_sec;
308 int udiff = a->tv_usec - b->tv_usec;
310 if (diff != 0)
311 return diff;
313 return udiff;
316 static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
317 int reuse_open)
319 char **names = NULL, **names_after = NULL;
320 struct timeval deadline;
321 int64_t delay = 0;
322 int tries = 0, err;
323 int fd = -1;
325 err = gettimeofday(&deadline, NULL);
326 if (err < 0)
327 goto out;
328 deadline.tv_sec += 3;
330 while (1) {
331 struct timeval now;
333 err = gettimeofday(&now, NULL);
334 if (err < 0)
335 goto out;
338 * Only look at deadlines after the first few times. This
339 * simplifies debugging in GDB.
341 tries++;
342 if (tries > 3 && tv_cmp(&now, &deadline) >= 0)
343 goto out;
345 fd = open(st->list_file, O_RDONLY);
346 if (fd < 0) {
347 if (errno != ENOENT) {
348 err = REFTABLE_IO_ERROR;
349 goto out;
352 REFTABLE_CALLOC_ARRAY(names, 1);
353 } else {
354 err = fd_read_lines(fd, &names);
355 if (err < 0)
356 goto out;
359 err = reftable_stack_reload_once(st, names, reuse_open);
360 if (!err)
361 break;
362 if (err != REFTABLE_NOT_EXIST_ERROR)
363 goto out;
366 * REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent
367 * writer. Check if there was one by checking if the name list
368 * changed.
370 err = read_lines(st->list_file, &names_after);
371 if (err < 0)
372 goto out;
373 if (names_equal(names_after, names)) {
374 err = REFTABLE_NOT_EXIST_ERROR;
375 goto out;
378 free_names(names);
379 names = NULL;
380 free_names(names_after);
381 names_after = NULL;
382 close(fd);
383 fd = -1;
385 delay = delay + (delay * rand()) / RAND_MAX + 1;
386 sleep_millisec(delay);
389 out:
391 * Invalidate the stat cache. It is sufficient to only close the file
392 * descriptor and keep the cached stat info because we never use the
393 * latter when the former is negative.
395 if (st->list_fd >= 0) {
396 close(st->list_fd);
397 st->list_fd = -1;
401 * Cache stat information in case it provides a useful signal to us.
402 * According to POSIX, "The st_ino and st_dev fields taken together
403 * uniquely identify the file within the system." That being said,
404 * Windows is not POSIX compliant and we do not have these fields
405 * available. So the information we have there is insufficient to
406 * determine whether two file descriptors point to the same file.
408 * While we could fall back to using other signals like the file's
409 * mtime, those are not sufficient to avoid races. We thus refrain from
410 * using the stat cache on such systems and fall back to the secondary
411 * caching mechanism, which is to check whether contents of the file
412 * have changed.
414 * On other systems which are POSIX compliant we must keep the file
415 * descriptor open. This is to avoid a race condition where two
416 * processes access the reftable stack at the same point in time:
418 * 1. A reads the reftable stack and caches its stat info.
420 * 2. B updates the stack, appending a new table to "tables.list".
421 * This will both use a new inode and result in a different file
422 * size, thus invalidating A's cache in theory.
424 * 3. B decides to auto-compact the stack and merges two tables. The
425 * file size now matches what A has cached again. Furthermore, the
426 * filesystem may decide to recycle the inode number of the file
427 * we have replaced in (2) because it is not in use anymore.
429 * 4. A reloads the reftable stack. Neither the inode number nor the
430 * file size changed. If the timestamps did not change either then
431 * we think the cached copy of our stack is up-to-date.
433 * By keeping the file descriptor open the inode number cannot be
434 * recycled, mitigating the race.
436 if (!err && fd >= 0 && !fstat(fd, &st->list_st) &&
437 st->list_st.st_dev && st->list_st.st_ino) {
438 st->list_fd = fd;
439 fd = -1;
442 if (fd >= 0)
443 close(fd);
444 free_names(names);
445 free_names(names_after);
446 return err;
449 /* -1 = error
450 0 = up to date
451 1 = changed. */
452 static int stack_uptodate(struct reftable_stack *st)
454 char **names = NULL;
455 int err;
456 int i = 0;
459 * When we have cached stat information available then we use it to
460 * verify whether the file has been rewritten.
462 * Note that we explicitly do not want to use `stat_validity_check()`
463 * and friends here because they may end up not comparing the `st_dev`
464 * and `st_ino` fields. These functions thus cannot guarantee that we
465 * indeed still have the same file.
467 if (st->list_fd >= 0) {
468 struct stat list_st;
470 if (stat(st->list_file, &list_st) < 0) {
472 * It's fine for "tables.list" to not exist. In that
473 * case, we have to refresh when the loaded stack has
474 * any readers.
476 if (errno == ENOENT)
477 return !!st->readers_len;
478 return REFTABLE_IO_ERROR;
482 * When "tables.list" refers to the same file we can assume
483 * that it didn't change. This is because we always use
484 * rename(3P) to update the file and never write to it
485 * directly.
487 if (st->list_st.st_dev == list_st.st_dev &&
488 st->list_st.st_ino == list_st.st_ino)
489 return 0;
492 err = read_lines(st->list_file, &names);
493 if (err < 0)
494 return err;
496 for (i = 0; i < st->readers_len; i++) {
497 if (!names[i]) {
498 err = 1;
499 goto done;
502 if (strcmp(st->readers[i]->name, names[i])) {
503 err = 1;
504 goto done;
508 if (names[st->merged->stack_len]) {
509 err = 1;
510 goto done;
513 done:
514 free_names(names);
515 return err;
518 int reftable_stack_reload(struct reftable_stack *st)
520 int err = stack_uptodate(st);
521 if (err > 0)
522 return reftable_stack_reload_maybe_reuse(st, 1);
523 return err;
526 int reftable_stack_add(struct reftable_stack *st,
527 int (*write)(struct reftable_writer *wr, void *arg),
528 void *arg)
530 int err = stack_try_add(st, write, arg);
531 if (err < 0) {
532 if (err == REFTABLE_OUTDATED_ERROR) {
533 /* Ignore error return, we want to propagate
534 REFTABLE_OUTDATED_ERROR.
536 reftable_stack_reload(st);
538 return err;
541 return 0;
544 static void format_name(struct strbuf *dest, uint64_t min, uint64_t max)
546 char buf[100];
547 uint32_t rnd = (uint32_t)git_rand();
548 snprintf(buf, sizeof(buf), "0x%012" PRIx64 "-0x%012" PRIx64 "-%08x",
549 min, max, rnd);
550 strbuf_reset(dest);
551 strbuf_addstr(dest, buf);
554 struct reftable_addition {
555 struct tempfile *lock_file;
556 struct reftable_stack *stack;
558 char **new_tables;
559 size_t new_tables_len, new_tables_cap;
560 uint64_t next_update_index;
563 #define REFTABLE_ADDITION_INIT {0}
565 static int reftable_stack_init_addition(struct reftable_addition *add,
566 struct reftable_stack *st)
568 struct strbuf lock_file_name = STRBUF_INIT;
569 int err = 0;
570 add->stack = st;
572 strbuf_addf(&lock_file_name, "%s.lock", st->list_file);
574 add->lock_file = create_tempfile(lock_file_name.buf);
575 if (!add->lock_file) {
576 if (errno == EEXIST) {
577 err = REFTABLE_LOCK_ERROR;
578 } else {
579 err = REFTABLE_IO_ERROR;
581 goto done;
583 if (st->config.default_permissions) {
584 if (chmod(add->lock_file->filename.buf, st->config.default_permissions) < 0) {
585 err = REFTABLE_IO_ERROR;
586 goto done;
590 err = stack_uptodate(st);
591 if (err < 0)
592 goto done;
593 if (err > 0) {
594 err = REFTABLE_OUTDATED_ERROR;
595 goto done;
598 add->next_update_index = reftable_stack_next_update_index(st);
599 done:
600 if (err) {
601 reftable_addition_close(add);
603 strbuf_release(&lock_file_name);
604 return err;
607 static void reftable_addition_close(struct reftable_addition *add)
609 struct strbuf nm = STRBUF_INIT;
610 size_t i;
612 for (i = 0; i < add->new_tables_len; i++) {
613 stack_filename(&nm, add->stack, add->new_tables[i]);
614 unlink(nm.buf);
615 reftable_free(add->new_tables[i]);
616 add->new_tables[i] = NULL;
618 reftable_free(add->new_tables);
619 add->new_tables = NULL;
620 add->new_tables_len = 0;
621 add->new_tables_cap = 0;
623 delete_tempfile(&add->lock_file);
624 strbuf_release(&nm);
627 void reftable_addition_destroy(struct reftable_addition *add)
629 if (!add) {
630 return;
632 reftable_addition_close(add);
633 reftable_free(add);
636 int reftable_addition_commit(struct reftable_addition *add)
638 struct strbuf table_list = STRBUF_INIT;
639 int lock_file_fd = get_tempfile_fd(add->lock_file);
640 int err = 0;
641 size_t i;
643 if (add->new_tables_len == 0)
644 goto done;
646 for (i = 0; i < add->stack->merged->stack_len; i++) {
647 strbuf_addstr(&table_list, add->stack->readers[i]->name);
648 strbuf_addstr(&table_list, "\n");
650 for (i = 0; i < add->new_tables_len; i++) {
651 strbuf_addstr(&table_list, add->new_tables[i]);
652 strbuf_addstr(&table_list, "\n");
655 err = write_in_full(lock_file_fd, table_list.buf, table_list.len);
656 strbuf_release(&table_list);
657 if (err < 0) {
658 err = REFTABLE_IO_ERROR;
659 goto done;
662 fsync_component_or_die(FSYNC_COMPONENT_REFERENCE, lock_file_fd,
663 get_tempfile_path(add->lock_file));
665 err = rename_tempfile(&add->lock_file, add->stack->list_file);
666 if (err < 0) {
667 err = REFTABLE_IO_ERROR;
668 goto done;
671 /* success, no more state to clean up. */
672 for (i = 0; i < add->new_tables_len; i++)
673 reftable_free(add->new_tables[i]);
674 reftable_free(add->new_tables);
675 add->new_tables = NULL;
676 add->new_tables_len = 0;
677 add->new_tables_cap = 0;
679 err = reftable_stack_reload_maybe_reuse(add->stack, 1);
680 if (err)
681 goto done;
683 if (!add->stack->disable_auto_compact)
684 err = reftable_stack_auto_compact(add->stack);
686 done:
687 reftable_addition_close(add);
688 return err;
691 int reftable_stack_new_addition(struct reftable_addition **dest,
692 struct reftable_stack *st)
694 int err = 0;
695 struct reftable_addition empty = REFTABLE_ADDITION_INIT;
696 REFTABLE_CALLOC_ARRAY(*dest, 1);
697 **dest = empty;
698 err = reftable_stack_init_addition(*dest, st);
699 if (err) {
700 reftable_free(*dest);
701 *dest = NULL;
703 return err;
706 static int stack_try_add(struct reftable_stack *st,
707 int (*write_table)(struct reftable_writer *wr,
708 void *arg),
709 void *arg)
711 struct reftable_addition add = REFTABLE_ADDITION_INIT;
712 int err = reftable_stack_init_addition(&add, st);
713 if (err < 0)
714 goto done;
716 err = reftable_addition_add(&add, write_table, arg);
717 if (err < 0)
718 goto done;
720 err = reftable_addition_commit(&add);
721 done:
722 reftable_addition_close(&add);
723 return err;
726 int reftable_addition_add(struct reftable_addition *add,
727 int (*write_table)(struct reftable_writer *wr,
728 void *arg),
729 void *arg)
731 struct strbuf temp_tab_file_name = STRBUF_INIT;
732 struct strbuf tab_file_name = STRBUF_INIT;
733 struct strbuf next_name = STRBUF_INIT;
734 struct reftable_writer *wr = NULL;
735 struct tempfile *tab_file = NULL;
736 int err = 0;
737 int tab_fd;
739 strbuf_reset(&next_name);
740 format_name(&next_name, add->next_update_index, add->next_update_index);
742 stack_filename(&temp_tab_file_name, add->stack, next_name.buf);
743 strbuf_addstr(&temp_tab_file_name, ".temp.XXXXXX");
745 tab_file = mks_tempfile(temp_tab_file_name.buf);
746 if (!tab_file) {
747 err = REFTABLE_IO_ERROR;
748 goto done;
750 if (add->stack->config.default_permissions) {
751 if (chmod(get_tempfile_path(tab_file),
752 add->stack->config.default_permissions)) {
753 err = REFTABLE_IO_ERROR;
754 goto done;
757 tab_fd = get_tempfile_fd(tab_file);
759 wr = reftable_new_writer(reftable_fd_write, reftable_fd_flush, &tab_fd,
760 &add->stack->config);
761 err = write_table(wr, arg);
762 if (err < 0)
763 goto done;
765 err = reftable_writer_close(wr);
766 if (err == REFTABLE_EMPTY_TABLE_ERROR) {
767 err = 0;
768 goto done;
770 if (err < 0)
771 goto done;
773 err = close_tempfile_gently(tab_file);
774 if (err < 0) {
775 err = REFTABLE_IO_ERROR;
776 goto done;
779 err = stack_check_addition(add->stack, get_tempfile_path(tab_file));
780 if (err < 0)
781 goto done;
783 if (wr->min_update_index < add->next_update_index) {
784 err = REFTABLE_API_ERROR;
785 goto done;
788 format_name(&next_name, wr->min_update_index, wr->max_update_index);
789 strbuf_addstr(&next_name, ".ref");
790 stack_filename(&tab_file_name, add->stack, next_name.buf);
793 On windows, this relies on rand() picking a unique destination name.
794 Maybe we should do retry loop as well?
796 err = rename_tempfile(&tab_file, tab_file_name.buf);
797 if (err < 0) {
798 err = REFTABLE_IO_ERROR;
799 goto done;
802 REFTABLE_ALLOC_GROW(add->new_tables, add->new_tables_len + 1,
803 add->new_tables_cap);
804 add->new_tables[add->new_tables_len++] = strbuf_detach(&next_name, NULL);
805 done:
806 delete_tempfile(&tab_file);
807 strbuf_release(&temp_tab_file_name);
808 strbuf_release(&tab_file_name);
809 strbuf_release(&next_name);
810 reftable_writer_free(wr);
811 return err;
814 uint64_t reftable_stack_next_update_index(struct reftable_stack *st)
816 int sz = st->merged->stack_len;
817 if (sz > 0)
818 return reftable_reader_max_update_index(st->readers[sz - 1]) +
820 return 1;
823 static int stack_compact_locked(struct reftable_stack *st,
824 size_t first, size_t last,
825 struct reftable_log_expiry_config *config,
826 struct tempfile **tab_file_out)
828 struct strbuf next_name = STRBUF_INIT;
829 struct strbuf tab_file_path = STRBUF_INIT;
830 struct reftable_writer *wr = NULL;
831 struct tempfile *tab_file;
832 int tab_fd, err = 0;
834 format_name(&next_name,
835 reftable_reader_min_update_index(st->readers[first]),
836 reftable_reader_max_update_index(st->readers[last]));
837 stack_filename(&tab_file_path, st, next_name.buf);
838 strbuf_addstr(&tab_file_path, ".temp.XXXXXX");
840 tab_file = mks_tempfile(tab_file_path.buf);
841 if (!tab_file) {
842 err = REFTABLE_IO_ERROR;
843 goto done;
845 tab_fd = get_tempfile_fd(tab_file);
847 if (st->config.default_permissions &&
848 chmod(get_tempfile_path(tab_file), st->config.default_permissions) < 0) {
849 err = REFTABLE_IO_ERROR;
850 goto done;
853 wr = reftable_new_writer(reftable_fd_write, reftable_fd_flush,
854 &tab_fd, &st->config);
855 err = stack_write_compact(st, wr, first, last, config);
856 if (err < 0)
857 goto done;
859 err = reftable_writer_close(wr);
860 if (err < 0)
861 goto done;
863 err = close_tempfile_gently(tab_file);
864 if (err < 0)
865 goto done;
867 *tab_file_out = tab_file;
868 tab_file = NULL;
870 done:
871 delete_tempfile(&tab_file);
872 reftable_writer_free(wr);
873 strbuf_release(&next_name);
874 strbuf_release(&tab_file_path);
875 return err;
878 static int stack_write_compact(struct reftable_stack *st,
879 struct reftable_writer *wr,
880 size_t first, size_t last,
881 struct reftable_log_expiry_config *config)
883 size_t subtabs_len = last - first + 1;
884 struct reftable_table *subtabs = reftable_calloc(
885 last - first + 1, sizeof(*subtabs));
886 struct reftable_merged_table *mt = NULL;
887 struct reftable_iterator it = { NULL };
888 struct reftable_ref_record ref = { NULL };
889 struct reftable_log_record log = { NULL };
890 uint64_t entries = 0;
891 int err = 0;
893 for (size_t i = first, j = 0; i <= last; i++) {
894 struct reftable_reader *t = st->readers[i];
895 reftable_table_from_reader(&subtabs[j++], t);
896 st->stats.bytes += t->size;
898 reftable_writer_set_limits(wr, st->readers[first]->min_update_index,
899 st->readers[last]->max_update_index);
901 err = reftable_new_merged_table(&mt, subtabs, subtabs_len,
902 st->config.hash_id);
903 if (err < 0) {
904 reftable_free(subtabs);
905 goto done;
908 err = reftable_merged_table_seek_ref(mt, &it, "");
909 if (err < 0)
910 goto done;
912 while (1) {
913 err = reftable_iterator_next_ref(&it, &ref);
914 if (err > 0) {
915 err = 0;
916 break;
918 if (err < 0)
919 goto done;
921 if (first == 0 && reftable_ref_record_is_deletion(&ref)) {
922 continue;
925 err = reftable_writer_add_ref(wr, &ref);
926 if (err < 0)
927 goto done;
928 entries++;
930 reftable_iterator_destroy(&it);
932 err = reftable_merged_table_seek_log(mt, &it, "");
933 if (err < 0)
934 goto done;
936 while (1) {
937 err = reftable_iterator_next_log(&it, &log);
938 if (err > 0) {
939 err = 0;
940 break;
942 if (err < 0)
943 goto done;
944 if (first == 0 && reftable_log_record_is_deletion(&log)) {
945 continue;
948 if (config && config->min_update_index > 0 &&
949 log.update_index < config->min_update_index) {
950 continue;
953 if (config && config->time > 0 &&
954 log.value.update.time < config->time) {
955 continue;
958 err = reftable_writer_add_log(wr, &log);
959 if (err < 0)
960 goto done;
961 entries++;
964 done:
965 reftable_iterator_destroy(&it);
966 if (mt) {
967 merged_table_release(mt);
968 reftable_merged_table_free(mt);
970 reftable_ref_record_release(&ref);
971 reftable_log_record_release(&log);
972 st->stats.entries_written += entries;
973 return err;
976 /* < 0: error. 0 == OK, > 0 attempt failed; could retry. */
977 static int stack_compact_range(struct reftable_stack *st,
978 size_t first, size_t last,
979 struct reftable_log_expiry_config *expiry)
981 struct strbuf tables_list_buf = STRBUF_INIT;
982 struct strbuf new_table_name = STRBUF_INIT;
983 struct strbuf new_table_path = STRBUF_INIT;
984 struct strbuf table_name = STRBUF_INIT;
985 struct lock_file tables_list_lock = LOCK_INIT;
986 struct lock_file *table_locks = NULL;
987 struct tempfile *new_table = NULL;
988 int is_empty_table = 0, err = 0;
989 size_t i;
991 if (first > last || (!expiry && first == last)) {
992 err = 0;
993 goto done;
996 st->stats.attempts++;
999 * Hold the lock so that we can read "tables.list" and lock all tables
1000 * which are part of the user-specified range.
1002 err = hold_lock_file_for_update(&tables_list_lock, st->list_file,
1003 LOCK_NO_DEREF);
1004 if (err < 0) {
1005 if (errno == EEXIST)
1006 err = 1;
1007 else
1008 err = REFTABLE_IO_ERROR;
1009 goto done;
1012 err = stack_uptodate(st);
1013 if (err)
1014 goto done;
1017 * Lock all tables in the user-provided range. This is the slice of our
1018 * stack which we'll compact.
1020 REFTABLE_CALLOC_ARRAY(table_locks, last - first + 1);
1021 for (i = first; i <= last; i++) {
1022 stack_filename(&table_name, st, reader_name(st->readers[i]));
1024 err = hold_lock_file_for_update(&table_locks[i - first],
1025 table_name.buf, LOCK_NO_DEREF);
1026 if (err < 0) {
1027 if (errno == EEXIST)
1028 err = 1;
1029 else
1030 err = REFTABLE_IO_ERROR;
1031 goto done;
1035 * We need to close the lockfiles as we might otherwise easily
1036 * run into file descriptor exhaustion when we compress a lot
1037 * of tables.
1039 err = close_lock_file_gently(&table_locks[i - first]);
1040 if (err < 0) {
1041 err = REFTABLE_IO_ERROR;
1042 goto done;
1047 * We have locked all tables in our range and can thus release the
1048 * "tables.list" lock while compacting the locked tables. This allows
1049 * concurrent updates to the stack to proceed.
1051 err = rollback_lock_file(&tables_list_lock);
1052 if (err < 0) {
1053 err = REFTABLE_IO_ERROR;
1054 goto done;
1058 * Compact the now-locked tables into a new table. Note that compacting
1059 * these tables may end up with an empty new table in case tombstones
1060 * end up cancelling out all refs in that range.
1062 err = stack_compact_locked(st, first, last, expiry, &new_table);
1063 if (err < 0) {
1064 if (err != REFTABLE_EMPTY_TABLE_ERROR)
1065 goto done;
1066 is_empty_table = 1;
1070 * Now that we have written the new, compacted table we need to re-lock
1071 * "tables.list". We'll then replace the compacted range of tables with
1072 * the new table.
1074 err = hold_lock_file_for_update(&tables_list_lock, st->list_file,
1075 LOCK_NO_DEREF);
1076 if (err < 0) {
1077 if (errno == EEXIST)
1078 err = 1;
1079 else
1080 err = REFTABLE_IO_ERROR;
1081 goto done;
1084 if (st->config.default_permissions) {
1085 if (chmod(get_lock_file_path(&tables_list_lock),
1086 st->config.default_permissions) < 0) {
1087 err = REFTABLE_IO_ERROR;
1088 goto done;
1093 * If the resulting compacted table is not empty, then we need to move
1094 * it into place now.
1096 if (!is_empty_table) {
1097 format_name(&new_table_name, st->readers[first]->min_update_index,
1098 st->readers[last]->max_update_index);
1099 strbuf_addstr(&new_table_name, ".ref");
1100 stack_filename(&new_table_path, st, new_table_name.buf);
1102 err = rename_tempfile(&new_table, new_table_path.buf);
1103 if (err < 0) {
1104 err = REFTABLE_IO_ERROR;
1105 goto done;
1110 * Write the new "tables.list" contents with the compacted table we
1111 * have just written. In case the compacted table became empty we
1112 * simply skip writing it.
1114 for (i = 0; i < first; i++)
1115 strbuf_addf(&tables_list_buf, "%s\n", st->readers[i]->name);
1116 if (!is_empty_table)
1117 strbuf_addf(&tables_list_buf, "%s\n", new_table_name.buf);
1118 for (i = last + 1; i < st->merged->stack_len; i++)
1119 strbuf_addf(&tables_list_buf, "%s\n", st->readers[i]->name);
1121 err = write_in_full(get_lock_file_fd(&tables_list_lock),
1122 tables_list_buf.buf, tables_list_buf.len);
1123 if (err < 0) {
1124 err = REFTABLE_IO_ERROR;
1125 unlink(new_table_path.buf);
1126 goto done;
1129 err = fsync_component(FSYNC_COMPONENT_REFERENCE, get_lock_file_fd(&tables_list_lock));
1130 if (err < 0) {
1131 err = REFTABLE_IO_ERROR;
1132 unlink(new_table_path.buf);
1133 goto done;
1136 err = commit_lock_file(&tables_list_lock);
1137 if (err < 0) {
1138 err = REFTABLE_IO_ERROR;
1139 unlink(new_table_path.buf);
1140 goto done;
1144 * Reload the stack before deleting the compacted tables. We can only
1145 * delete the files after we closed them on Windows, so this needs to
1146 * happen first.
1148 err = reftable_stack_reload_maybe_reuse(st, first < last);
1149 if (err < 0)
1150 goto done;
1153 * Delete the old tables. They may still be in use by concurrent
1154 * readers, so it is expected that unlinking tables may fail.
1156 for (i = first; i <= last; i++) {
1157 struct lock_file *table_lock = &table_locks[i - first];
1158 char *table_path = get_locked_file_path(table_lock);
1159 unlink(table_path);
1160 free(table_path);
1163 done:
1164 rollback_lock_file(&tables_list_lock);
1165 for (i = first; table_locks && i <= last; i++)
1166 rollback_lock_file(&table_locks[i - first]);
1167 reftable_free(table_locks);
1169 delete_tempfile(&new_table);
1170 strbuf_release(&new_table_name);
1171 strbuf_release(&new_table_path);
1173 strbuf_release(&tables_list_buf);
1174 strbuf_release(&table_name);
1175 return err;
1178 int reftable_stack_compact_all(struct reftable_stack *st,
1179 struct reftable_log_expiry_config *config)
1181 return stack_compact_range(st, 0, st->merged->stack_len ?
1182 st->merged->stack_len - 1 : 0, config);
1185 static int stack_compact_range_stats(struct reftable_stack *st,
1186 size_t first, size_t last,
1187 struct reftable_log_expiry_config *config)
1189 int err = stack_compact_range(st, first, last, config);
1190 if (err > 0)
1191 st->stats.failures++;
1192 return err;
1195 static int segment_size(struct segment *s)
1197 return s->end - s->start;
1200 int fastlog2(uint64_t sz)
1202 int l = 0;
1203 if (sz == 0)
1204 return 0;
1205 for (; sz; sz /= 2) {
1206 l++;
1208 return l - 1;
1211 struct segment *sizes_to_segments(size_t *seglen, uint64_t *sizes, size_t n)
1213 struct segment *segs = reftable_calloc(n, sizeof(*segs));
1214 struct segment cur = { 0 };
1215 size_t next = 0, i;
1217 if (n == 0) {
1218 *seglen = 0;
1219 return segs;
1221 for (i = 0; i < n; i++) {
1222 int log = fastlog2(sizes[i]);
1223 if (cur.log != log && cur.bytes > 0) {
1224 struct segment fresh = {
1225 .start = i,
1228 segs[next++] = cur;
1229 cur = fresh;
1232 cur.log = log;
1233 cur.end = i + 1;
1234 cur.bytes += sizes[i];
1236 segs[next++] = cur;
1237 *seglen = next;
1238 return segs;
1241 struct segment suggest_compaction_segment(uint64_t *sizes, size_t n)
1243 struct segment min_seg = {
1244 .log = 64,
1246 struct segment *segs;
1247 size_t seglen = 0, i;
1249 segs = sizes_to_segments(&seglen, sizes, n);
1250 for (i = 0; i < seglen; i++) {
1251 if (segment_size(&segs[i]) == 1)
1252 continue;
1254 if (segs[i].log < min_seg.log)
1255 min_seg = segs[i];
1258 while (min_seg.start > 0) {
1259 size_t prev = min_seg.start - 1;
1260 if (fastlog2(min_seg.bytes) < fastlog2(sizes[prev]))
1261 break;
1263 min_seg.start = prev;
1264 min_seg.bytes += sizes[prev];
1267 reftable_free(segs);
1268 return min_seg;
1271 static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack *st)
1273 uint64_t *sizes =
1274 reftable_calloc(st->merged->stack_len, sizeof(*sizes));
1275 int version = (st->config.hash_id == GIT_SHA1_FORMAT_ID) ? 1 : 2;
1276 int overhead = header_size(version) - 1;
1277 int i = 0;
1278 for (i = 0; i < st->merged->stack_len; i++) {
1279 sizes[i] = st->readers[i]->size - overhead;
1281 return sizes;
1284 int reftable_stack_auto_compact(struct reftable_stack *st)
1286 uint64_t *sizes = stack_table_sizes_for_compaction(st);
1287 struct segment seg =
1288 suggest_compaction_segment(sizes, st->merged->stack_len);
1289 reftable_free(sizes);
1290 if (segment_size(&seg) > 0)
1291 return stack_compact_range_stats(st, seg.start, seg.end - 1,
1292 NULL);
1294 return 0;
1297 struct reftable_compaction_stats *
1298 reftable_stack_compaction_stats(struct reftable_stack *st)
1300 return &st->stats;
1303 int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,
1304 struct reftable_ref_record *ref)
1306 struct reftable_table tab = { NULL };
1307 reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st));
1308 return reftable_table_read_ref(&tab, refname, ref);
1311 int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
1312 struct reftable_log_record *log)
1314 struct reftable_iterator it = { NULL };
1315 struct reftable_merged_table *mt = reftable_stack_merged_table(st);
1316 int err = reftable_merged_table_seek_log(mt, &it, refname);
1317 if (err)
1318 goto done;
1320 err = reftable_iterator_next_log(&it, log);
1321 if (err)
1322 goto done;
1324 if (strcmp(log->refname, refname) ||
1325 reftable_log_record_is_deletion(log)) {
1326 err = 1;
1327 goto done;
1330 done:
1331 if (err) {
1332 reftable_log_record_release(log);
1334 reftable_iterator_destroy(&it);
1335 return err;
1338 static int stack_check_addition(struct reftable_stack *st,
1339 const char *new_tab_name)
1341 int err = 0;
1342 struct reftable_block_source src = { NULL };
1343 struct reftable_reader *rd = NULL;
1344 struct reftable_table tab = { NULL };
1345 struct reftable_ref_record *refs = NULL;
1346 struct reftable_iterator it = { NULL };
1347 int cap = 0;
1348 int len = 0;
1349 int i = 0;
1351 if (st->config.skip_name_check)
1352 return 0;
1354 err = reftable_block_source_from_file(&src, new_tab_name);
1355 if (err < 0)
1356 goto done;
1358 err = reftable_new_reader(&rd, &src, new_tab_name);
1359 if (err < 0)
1360 goto done;
1362 err = reftable_reader_seek_ref(rd, &it, "");
1363 if (err > 0) {
1364 err = 0;
1365 goto done;
1367 if (err < 0)
1368 goto done;
1370 while (1) {
1371 struct reftable_ref_record ref = { NULL };
1372 err = reftable_iterator_next_ref(&it, &ref);
1373 if (err > 0)
1374 break;
1375 if (err < 0)
1376 goto done;
1378 REFTABLE_ALLOC_GROW(refs, len + 1, cap);
1379 refs[len++] = ref;
1382 reftable_table_from_merged_table(&tab, reftable_stack_merged_table(st));
1384 err = validate_ref_record_addition(tab, refs, len);
1386 done:
1387 for (i = 0; i < len; i++) {
1388 reftable_ref_record_release(&refs[i]);
1391 free(refs);
1392 reftable_iterator_destroy(&it);
1393 reftable_reader_free(rd);
1394 return err;
1397 static int is_table_name(const char *s)
1399 const char *dot = strrchr(s, '.');
1400 return dot && !strcmp(dot, ".ref");
1403 static void remove_maybe_stale_table(struct reftable_stack *st, uint64_t max,
1404 const char *name)
1406 int err = 0;
1407 uint64_t update_idx = 0;
1408 struct reftable_block_source src = { NULL };
1409 struct reftable_reader *rd = NULL;
1410 struct strbuf table_path = STRBUF_INIT;
1411 stack_filename(&table_path, st, name);
1413 err = reftable_block_source_from_file(&src, table_path.buf);
1414 if (err < 0)
1415 goto done;
1417 err = reftable_new_reader(&rd, &src, name);
1418 if (err < 0)
1419 goto done;
1421 update_idx = reftable_reader_max_update_index(rd);
1422 reftable_reader_free(rd);
1424 if (update_idx <= max) {
1425 unlink(table_path.buf);
1427 done:
1428 strbuf_release(&table_path);
1431 static int reftable_stack_clean_locked(struct reftable_stack *st)
1433 uint64_t max = reftable_merged_table_max_update_index(
1434 reftable_stack_merged_table(st));
1435 DIR *dir = opendir(st->reftable_dir);
1436 struct dirent *d = NULL;
1437 if (!dir) {
1438 return REFTABLE_IO_ERROR;
1441 while ((d = readdir(dir))) {
1442 int i = 0;
1443 int found = 0;
1444 if (!is_table_name(d->d_name))
1445 continue;
1447 for (i = 0; !found && i < st->readers_len; i++) {
1448 found = !strcmp(reader_name(st->readers[i]), d->d_name);
1450 if (found)
1451 continue;
1453 remove_maybe_stale_table(st, max, d->d_name);
1456 closedir(dir);
1457 return 0;
1460 int reftable_stack_clean(struct reftable_stack *st)
1462 struct reftable_addition *add = NULL;
1463 int err = reftable_stack_new_addition(&add, st);
1464 if (err < 0) {
1465 goto done;
1468 err = reftable_stack_reload(st);
1469 if (err < 0) {
1470 goto done;
1473 err = reftable_stack_clean_locked(st);
1475 done:
1476 reftable_addition_destroy(add);
1477 return err;
1480 int reftable_stack_print_directory(const char *stackdir, uint32_t hash_id)
1482 struct reftable_stack *stack = NULL;
1483 struct reftable_write_options cfg = { .hash_id = hash_id };
1484 struct reftable_merged_table *merged = NULL;
1485 struct reftable_table table = { NULL };
1487 int err = reftable_new_stack(&stack, stackdir, cfg);
1488 if (err < 0)
1489 goto done;
1491 merged = reftable_stack_merged_table(stack);
1492 reftable_table_from_merged_table(&table, merged);
1493 err = reftable_table_print(&table);
1494 done:
1495 if (stack)
1496 reftable_stack_destroy(stack);
1497 return err;