@leroysheep / rag-system
Code Commits Pulls CI/CD 81,295
bisect
bisect jch maint master next seen test todo
c 1,830 lines 44.5 KB
Raw
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 "constants.h"
13 #include "merged.h"
14 #include "reftable-error.h"
15 #include "reftable-record.h"
16 #include "reftable-merged.h"
17 #include "table.h"
18 #include "writer.h"
19
20 static int stack_filename(struct reftable_buf *dest, struct reftable_stack *st,
21 const char *name)
22 {
23 int err;
24 reftable_buf_reset(dest);
25 if ((err = reftable_buf_addstr(dest, st->reftable_dir)) < 0 ||
26 (err = reftable_buf_addstr(dest, "/")) < 0 ||
27 (err = reftable_buf_addstr(dest, name)) < 0)
28 return err;
29 return 0;
30 }
31
32 static ssize_t reftable_write_data(int fd, const void *data, size_t size)
33 {
34 size_t total_written = 0;
35 const char *p = data;
36
37 while (total_written < size) {
38 ssize_t bytes_written = write(fd, p, size - total_written);
39 if (bytes_written < 0 && (errno == EAGAIN || errno == EINTR))
40 continue;
41 if (bytes_written < 0)
42 return REFTABLE_IO_ERROR;
43
44 total_written += bytes_written;
45 p += bytes_written;
46 }
47
48 return total_written;
49 }
50
51 struct fd_writer {
52 const struct reftable_write_options *opts;
53 int fd;
54 };
55
56 static ssize_t fd_writer_write(void *arg, const void *data, size_t sz)
57 {
58 struct fd_writer *writer = arg;
59 return reftable_write_data(writer->fd, data, sz);
60 }
61
62 static int fd_writer_flush(void *arg)
63 {
64 struct fd_writer *writer = arg;
65 return fsync(writer->fd);
66 }
67
68 static int fd_read_lines(int fd, char ***namesp)
69 {
70 char *buf = NULL;
71 int err = 0;
72 off_t size;
73
74 size = lseek(fd, 0, SEEK_END);
75 if (size < 0) {
76 err = REFTABLE_IO_ERROR;
77 goto done;
78 }
79
80 err = lseek(fd, 0, SEEK_SET);
81 if (err < 0) {
82 err = REFTABLE_IO_ERROR;
83 goto done;
84 }
85
86 REFTABLE_ALLOC_ARRAY(buf, size + 1);
87 if (!buf) {
88 err = REFTABLE_OUT_OF_MEMORY_ERROR;
89 goto done;
90 }
91
92 for (off_t total_read = 0; total_read < size; ) {
93 ssize_t bytes_read = read(fd, buf + total_read, size - total_read);
94 if (bytes_read < 0 && (errno == EAGAIN || errno == EINTR))
95 continue;
96 if (bytes_read < 0 || !bytes_read) {
97 err = REFTABLE_IO_ERROR;
98 goto done;
99 }
100
101 total_read += bytes_read;
102 }
103 buf[size] = 0;
104
105 err = parse_names(buf, size, namesp);
106 done:
107 reftable_free(buf);
108 return err;
109 }
110
111 int read_lines(const char *filename, char ***namesp)
112 {
113 int fd = open(filename, O_RDONLY);
114 int err = 0;
115 if (fd < 0) {
116 if (errno == ENOENT) {
117 REFTABLE_CALLOC_ARRAY(*namesp, 1);
118 if (!*namesp)
119 return REFTABLE_OUT_OF_MEMORY_ERROR;
120 return 0;
121 }
122
123 return REFTABLE_IO_ERROR;
124 }
125 err = fd_read_lines(fd, namesp);
126 close(fd);
127 return err;
128 }
129
130 int reftable_stack_init_ref_iterator(struct reftable_stack *st,
131 struct reftable_iterator *it)
132 {
133 return merged_table_init_iter(reftable_stack_merged_table(st),
134 it, REFTABLE_BLOCK_TYPE_REF);
135 }
136
137 int reftable_stack_init_log_iterator(struct reftable_stack *st,
138 struct reftable_iterator *it)
139 {
140 return merged_table_init_iter(reftable_stack_merged_table(st),
141 it, REFTABLE_BLOCK_TYPE_LOG);
142 }
143
144 struct reftable_merged_table *
145 reftable_stack_merged_table(struct reftable_stack *st)
146 {
147 return st->merged;
148 }
149
150 static int has_name(char **names, const char *name)
151 {
152 while (*names) {
153 if (!strcmp(*names, name))
154 return 1;
155 names++;
156 }
157 return 0;
158 }
159
160 /* Close and free the stack */
161 void reftable_stack_destroy(struct reftable_stack *st)
162 {
163 char **names = NULL;
164 int err = 0;
165
166 if (!st)
167 return;
168
169 if (st->merged) {
170 reftable_merged_table_free(st->merged);
171 st->merged = NULL;
172 }
173
174 err = read_lines(st->list_file, &names);
175 if (err < 0) {
176 REFTABLE_FREE_AND_NULL(names);
177 }
178
179 if (st->tables) {
180 struct reftable_buf filename = REFTABLE_BUF_INIT;
181
182 for (size_t i = 0; i < st->tables_len; i++) {
183 const char *name = reftable_table_name(st->tables[i]);
184 int try_unlinking = 1;
185
186 reftable_buf_reset(&filename);
187 if (names && !has_name(names, name)) {
188 if (stack_filename(&filename, st, name) < 0)
189 try_unlinking = 0;
190 }
191 reftable_table_decref(st->tables[i]);
192
193 if (try_unlinking && filename.len) {
194 /* On Windows, can only unlink after closing. */
195 unlink(filename.buf);
196 }
197 }
198
199 reftable_buf_release(&filename);
200 st->tables_len = 0;
201 REFTABLE_FREE_AND_NULL(st->tables);
202 }
203
204 if (st->list_fd >= 0) {
205 close(st->list_fd);
206 st->list_fd = -1;
207 }
208
209 REFTABLE_FREE_AND_NULL(st->list_file);
210 REFTABLE_FREE_AND_NULL(st->reftable_dir);
211 reftable_free(st);
212 free_names(names);
213 }
214
215 static struct reftable_table **stack_copy_tables(struct reftable_stack *st,
216 size_t cur_len)
217 {
218 struct reftable_table **cur = reftable_calloc(cur_len, sizeof(*cur));
219 if (!cur)
220 return NULL;
221 for (size_t i = 0; i < cur_len; i++)
222 cur[i] = st->tables[i];
223 return cur;
224 }
225
226 static int reftable_stack_reload_once(struct reftable_stack *st,
227 const char **names,
228 int reuse_open)
229 {
230 size_t cur_len = !st->merged ? 0 : st->merged->tables_len;
231 struct reftable_table **cur = NULL;
232 struct reftable_table **reused = NULL;
233 struct reftable_table **new_tables = NULL;
234 size_t reused_len = 0, reused_alloc = 0, names_len;
235 size_t new_tables_len = 0;
236 struct reftable_merged_table *new_merged = NULL;
237 struct reftable_buf table_path = REFTABLE_BUF_INIT;
238 int err = 0;
239 size_t i;
240
241 if (cur_len) {
242 cur = stack_copy_tables(st, cur_len);
243 if (!cur) {
244 err = REFTABLE_OUT_OF_MEMORY_ERROR;
245 goto done;
246 }
247 }
248
249 names_len = names_length(names);
250
251 if (names_len) {
252 new_tables = reftable_calloc(names_len, sizeof(*new_tables));
253 if (!new_tables) {
254 err = REFTABLE_OUT_OF_MEMORY_ERROR;
255 goto done;
256 }
257 }
258
259 while (*names) {
260 struct reftable_table *table = NULL;
261 const char *name = *names++;
262
263 /* this is linear; we assume compaction keeps the number of
264 tables under control so this is not quadratic. */
265 for (i = 0; reuse_open && i < cur_len; i++) {
266 if (cur[i] && 0 == strcmp(cur[i]->name, name)) {
267 table = cur[i];
268 cur[i] = NULL;
269
270 /*
271 * When reloading the stack fails, we end up
272 * releasing all new tables. This also
273 * includes the reused tables, even though
274 * they are still in used by the old stack. We
275 * thus need to keep them alive here, which we
276 * do by bumping their refcount.
277 */
278 REFTABLE_ALLOC_GROW_OR_NULL(reused,
279 reused_len + 1,
280 reused_alloc);
281 if (!reused) {
282 err = REFTABLE_OUT_OF_MEMORY_ERROR;
283 goto done;
284 }
285 reused[reused_len++] = table;
286 reftable_table_incref(table);
287 break;
288 }
289 }
290
291 if (!table) {
292 struct reftable_block_source src = { NULL };
293
294 err = stack_filename(&table_path, st, name);
295 if (err < 0)
296 goto done;
297
298 err = reftable_block_source_from_file(&src,
299 table_path.buf);
300 if (err < 0)
301 goto done;
302
303 err = reftable_table_new(&table, &src, name);
304 if (err < 0)
305 goto done;
306 }
307
308 new_tables[new_tables_len] = table;
309 new_tables_len++;
310 }
311
312 /* success! */
313 err = reftable_merged_table_new(&new_merged, new_tables,
314 new_tables_len, st->opts.hash_id);
315 if (err < 0)
316 goto done;
317
318 /*
319 * Close the old, non-reused tables and proactively try to unlink
320 * them. This is done for systems like Windows, where the underlying
321 * file of such an open table wouldn't have been possible to be
322 * unlinked by the compacting process.
323 */
324 for (i = 0; i < cur_len; i++) {
325 if (cur[i]) {
326 const char *name = reftable_table_name(cur[i]);
327
328 err = stack_filename(&table_path, st, name);
329 if (err < 0)
330 goto done;
331
332 reftable_table_decref(cur[i]);
333 unlink(table_path.buf);
334 }
335 }
336
337 /* Update the stack to point to the new tables. */
338 if (st->merged)
339 reftable_merged_table_free(st->merged);
340 new_merged->suppress_deletions = 1;
341 st->merged = new_merged;
342
343 if (st->tables)
344 reftable_free(st->tables);
345 st->tables = new_tables;
346 st->tables_len = new_tables_len;
347 new_tables = NULL;
348 new_tables_len = 0;
349
350 /*
351 * Decrement the refcount of reused tables again. This only needs to
352 * happen on the successful case, because on the unsuccessful one we
353 * decrement their refcount via `new_tables`.
354 */
355 for (i = 0; i < reused_len; i++)
356 reftable_table_decref(reused[i]);
357
358 done:
359 for (i = 0; i < new_tables_len; i++)
360 reftable_table_decref(new_tables[i]);
361 reftable_free(new_tables);
362 reftable_free(reused);
363 reftable_free(cur);
364 reftable_buf_release(&table_path);
365 return err;
366 }
367
368 static int reftable_stack_reload_maybe_reuse(struct reftable_stack *st,
369 int reuse_open)
370 {
371 char **names = NULL, **names_after = NULL;
372 uint64_t deadline;
373 int64_t delay = 0;
374 int tries = 0, err;
375 int fd = -1;
376
377 deadline = reftable_time_ms() + 3000;
378
379 while (1) {
380 uint64_t now = reftable_time_ms();
381
382 /*
383 * Only look at deadlines after the first few times. This
384 * simplifies debugging in GDB.
385 */
386 tries++;
387 if (tries > 3 && now >= deadline)
388 goto out;
389
390 fd = open(st->list_file, O_RDONLY);
391 if (fd < 0) {
392 if (errno != ENOENT) {
393 err = REFTABLE_IO_ERROR;
394 goto out;
395 }
396
397 REFTABLE_CALLOC_ARRAY(names, 1);
398 if (!names) {
399 err = REFTABLE_OUT_OF_MEMORY_ERROR;
400 goto out;
401 }
402 } else {
403 err = fd_read_lines(fd, &names);
404 if (err < 0)
405 goto out;
406 }
407
408 err = reftable_stack_reload_once(st, (const char **) names, reuse_open);
409 if (!err)
410 break;
411 if (err != REFTABLE_NOT_EXIST_ERROR)
412 goto out;
413
414 /*
415 * REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent
416 * writer. Check if there was one by checking if the name list
417 * changed.
418 */
419 err = read_lines(st->list_file, &names_after);
420 if (err < 0)
421 goto out;
422 if (names_equal((const char **) names_after,
423 (const char **) names)) {
424 err = REFTABLE_NOT_EXIST_ERROR;
425 goto out;
426 }
427
428 free_names(names);
429 names = NULL;
430 free_names(names_after);
431 names_after = NULL;
432 close(fd);
433 fd = -1;
434
435 delay = delay + (delay * reftable_rand()) / UINT32_MAX + 1;
436 poll(NULL, 0, delay);
437 }
438
439 out:
440 /*
441 * Invalidate the stat cache. It is sufficient to only close the file
442 * descriptor and keep the cached stat info because we never use the
443 * latter when the former is negative.
444 */
445 if (st->list_fd >= 0) {
446 close(st->list_fd);
447 st->list_fd = -1;
448 }
449
450 /*
451 * Cache stat information in case it provides a useful signal to us.
452 * According to POSIX, "The st_ino and st_dev fields taken together
453 * uniquely identify the file within the system." That being said,
454 * Windows is not POSIX compliant and we do not have these fields
455 * available. So the information we have there is insufficient to
456 * determine whether two file descriptors point to the same file.
457 *
458 * While we could fall back to using other signals like the file's
459 * mtime, those are not sufficient to avoid races. We thus refrain from
460 * using the stat cache on such systems and fall back to the secondary
461 * caching mechanism, which is to check whether contents of the file
462 * have changed.
463 *
464 * On other systems which are POSIX compliant we must keep the file
465 * descriptor open. This is to avoid a race condition where two
466 * processes access the reftable stack at the same point in time:
467 *
468 * 1. A reads the reftable stack and caches its stat info.
469 *
470 * 2. B updates the stack, appending a new table to "tables.list".
471 * This will both use a new inode and result in a different file
472 * size, thus invalidating A's cache in theory.
473 *
474 * 3. B decides to auto-compact the stack and merges two tables. The
475 * file size now matches what A has cached again. Furthermore, the
476 * filesystem may decide to recycle the inode number of the file
477 * we have replaced in (2) because it is not in use anymore.
478 *
479 * 4. A reloads the reftable stack. Neither the inode number nor the
480 * file size changed. If the timestamps did not change either then
481 * we think the cached copy of our stack is up-to-date.
482 *
483 * By keeping the file descriptor open the inode number cannot be
484 * recycled, mitigating the race.
485 */
486 if (!err && fd >= 0 && !fstat(fd, &st->list_st) &&
487 st->list_st.st_dev && st->list_st.st_ino) {
488 st->list_fd = fd;
489 fd = -1;
490 }
491
492 if (fd >= 0)
493 close(fd);
494 free_names(names);
495 free_names(names_after);
496
497 if (st->opts.on_reload)
498 st->opts.on_reload(st->opts.on_reload_payload);
499
500 return err;
501 }
502
503 int reftable_new_stack(struct reftable_stack **dest, const char *dir,
504 const struct reftable_write_options *_opts)
505 {
506 struct reftable_buf list_file_name = REFTABLE_BUF_INIT;
507 struct reftable_write_options opts = { 0 };
508 struct reftable_stack *p;
509 int err;
510
511 p = reftable_calloc(1, sizeof(*p));
512 if (!p) {
513 err = REFTABLE_OUT_OF_MEMORY_ERROR;
514 goto out;
515 }
516
517 if (_opts)
518 opts = *_opts;
519 if (opts.hash_id == 0)
520 opts.hash_id = REFTABLE_HASH_SHA1;
521
522 *dest = NULL;
523
524 reftable_buf_reset(&list_file_name);
525 if ((err = reftable_buf_addstr(&list_file_name, dir)) < 0 ||
526 (err = reftable_buf_addstr(&list_file_name, "/tables.list")) < 0)
527 goto out;
528
529 p->list_file = reftable_buf_detach(&list_file_name);
530 p->list_fd = -1;
531 p->opts = opts;
532 p->reftable_dir = reftable_strdup(dir);
533 if (!p->reftable_dir) {
534 err = REFTABLE_OUT_OF_MEMORY_ERROR;
535 goto out;
536 }
537
538 err = reftable_stack_reload_maybe_reuse(p, 1);
539 if (err < 0)
540 goto out;
541
542 *dest = p;
543 err = 0;
544
545 out:
546 if (err < 0)
547 reftable_stack_destroy(p);
548 return err;
549 }
550
551 /*
552 * Check whether the given stack is up-to-date with what we have in memory.
553 * Returns 0 if so, 1 if the stack is out-of-date or a negative error code
554 * otherwise.
555 */
556 static int stack_uptodate(struct reftable_stack *st)
557 {
558 char **names = NULL;
559 int err;
560
561 /*
562 * When we have cached stat information available then we use it to
563 * verify whether the file has been rewritten.
564 *
565 * Note that we explicitly do not want to use `stat_validity_check()`
566 * and friends here because they may end up not comparing the `st_dev`
567 * and `st_ino` fields. These functions thus cannot guarantee that we
568 * indeed still have the same file.
569 */
570 if (st->list_fd >= 0) {
571 struct stat list_st;
572
573 if (stat(st->list_file, &list_st) < 0) {
574 /*
575 * It's fine for "tables.list" to not exist. In that
576 * case, we have to refresh when the loaded stack has
577 * any tables.
578 */
579 if (errno == ENOENT)
580 return !!st->tables_len;
581 return REFTABLE_IO_ERROR;
582 }
583
584 /*
585 * When "tables.list" refers to the same file we can assume
586 * that it didn't change. This is because we always use
587 * rename(3P) to update the file and never write to it
588 * directly.
589 */
590 if (st->list_st.st_dev == list_st.st_dev &&
591 st->list_st.st_ino == list_st.st_ino)
592 return 0;
593 }
594
595 err = read_lines(st->list_file, &names);
596 if (err < 0)
597 return err;
598
599 for (size_t i = 0; i < st->tables_len; i++) {
600 if (!names[i]) {
601 err = 1;
602 goto done;
603 }
604
605 if (strcmp(st->tables[i]->name, names[i])) {
606 err = 1;
607 goto done;
608 }
609 }
610
611 if (names[st->merged->tables_len]) {
612 err = 1;
613 goto done;
614 }
615
616 done:
617 free_names(names);
618 return err;
619 }
620
621 int reftable_stack_reload(struct reftable_stack *st)
622 {
623 int err = stack_uptodate(st);
624 if (err > 0)
625 return reftable_stack_reload_maybe_reuse(st, 1);
626 return err;
627 }
628
629 struct reftable_addition {
630 struct reftable_flock tables_list_lock;
631 struct reftable_stack *stack;
632
633 char **new_tables;
634 size_t new_tables_len, new_tables_cap;
635 uint64_t next_update_index;
636 };
637
638 static void reftable_addition_close(struct reftable_addition *add)
639 {
640 struct reftable_buf nm = REFTABLE_BUF_INIT;
641 size_t i;
642
643 for (i = 0; i < add->new_tables_len; i++) {
644 if (!stack_filename(&nm, add->stack, add->new_tables[i]))
645 unlink(nm.buf);
646 reftable_free(add->new_tables[i]);
647 add->new_tables[i] = NULL;
648 }
649 reftable_free(add->new_tables);
650 add->new_tables = NULL;
651 add->new_tables_len = 0;
652 add->new_tables_cap = 0;
653
654 flock_release(&add->tables_list_lock);
655 reftable_buf_release(&nm);
656 }
657
658 static int reftable_stack_init_addition(struct reftable_addition *add,
659 struct reftable_stack *st,
660 unsigned int flags)
661 {
662 struct reftable_buf lock_file_name = REFTABLE_BUF_INIT;
663 int err;
664
665 memset(add, 0, sizeof(*add));
666 add->stack = st;
667
668 err = flock_acquire(&add->tables_list_lock, st->list_file,
669 st->opts.lock_timeout_ms);
670 if (err < 0)
671 goto done;
672
673 if (st->opts.default_permissions) {
674 if (chmod(add->tables_list_lock.path,
675 st->opts.default_permissions) < 0) {
676 err = REFTABLE_IO_ERROR;
677 goto done;
678 }
679 }
680
681 err = stack_uptodate(st);
682 if (err < 0)
683 goto done;
684 if (err > 0 && flags & REFTABLE_STACK_NEW_ADDITION_RELOAD) {
685 err = reftable_stack_reload_maybe_reuse(add->stack, 1);
686 if (err)
687 goto done;
688 }
689 if (err > 0) {
690 err = REFTABLE_OUTDATED_ERROR;
691 goto done;
692 }
693
694 add->next_update_index = reftable_stack_next_update_index(st);
695 done:
696 if (err)
697 reftable_addition_close(add);
698 reftable_buf_release(&lock_file_name);
699 return err;
700 }
701
702 static int stack_try_add(struct reftable_stack *st,
703 int (*write_table)(struct reftable_writer *wr,
704 void *arg),
705 void *arg, unsigned flags)
706 {
707 struct reftable_addition add;
708 int err;
709
710 err = reftable_stack_init_addition(&add, st, flags);
711 if (err < 0)
712 goto done;
713
714 err = reftable_addition_add(&add, write_table, arg);
715 if (err < 0)
716 goto done;
717
718 err = reftable_addition_commit(&add);
719 done:
720 reftable_addition_close(&add);
721 return err;
722 }
723
724 int reftable_stack_add(struct reftable_stack *st,
725 int (*write)(struct reftable_writer *wr, void *arg),
726 void *arg, unsigned flags)
727 {
728 int err = stack_try_add(st, write, arg, flags);
729 if (err < 0) {
730 if (err == REFTABLE_OUTDATED_ERROR) {
731 /* Ignore error return, we want to propagate
732 REFTABLE_OUTDATED_ERROR.
733 */
734 reftable_stack_reload(st);
735 }
736 return err;
737 }
738
739 return 0;
740 }
741
742 static int format_name(struct reftable_buf *dest, uint64_t min, uint64_t max)
743 {
744 char buf[100];
745 uint32_t rnd = reftable_rand();
746 snprintf(buf, sizeof(buf), "0x%012" PRIx64 "-0x%012" PRIx64 "-%08x",
747 min, max, rnd);
748 reftable_buf_reset(dest);
749 return reftable_buf_addstr(dest, buf);
750 }
751
752 void reftable_addition_destroy(struct reftable_addition *add)
753 {
754 if (!add) {
755 return;
756 }
757 reftable_addition_close(add);
758 reftable_free(add);
759 }
760
761 int reftable_addition_commit(struct reftable_addition *add)
762 {
763 struct reftable_buf table_list = REFTABLE_BUF_INIT;
764 int err = 0;
765 size_t i;
766
767 if (add->new_tables_len == 0)
768 goto done;
769
770 for (i = 0; i < add->stack->merged->tables_len; i++) {
771 if ((err = reftable_buf_addstr(&table_list, add->stack->tables[i]->name)) < 0 ||
772 (err = reftable_buf_addstr(&table_list, "\n")) < 0)
773 goto done;
774 }
775 for (i = 0; i < add->new_tables_len; i++) {
776 if ((err = reftable_buf_addstr(&table_list, add->new_tables[i])) < 0 ||
777 (err = reftable_buf_addstr(&table_list, "\n")) < 0)
778 goto done;
779 }
780
781 err = reftable_write_data(add->tables_list_lock.fd,
782 table_list.buf, table_list.len);
783 reftable_buf_release(&table_list);
784 if (err < 0) {
785 err = REFTABLE_IO_ERROR;
786 goto done;
787 }
788
789 err = fsync(add->tables_list_lock.fd);
790 if (err < 0) {
791 err = REFTABLE_IO_ERROR;
792 goto done;
793 }
794
795 err = flock_commit(&add->tables_list_lock);
796 if (err < 0) {
797 err = REFTABLE_IO_ERROR;
798 goto done;
799 }
800
801 /* success, no more state to clean up. */
802 for (i = 0; i < add->new_tables_len; i++)
803 reftable_free(add->new_tables[i]);
804 reftable_free(add->new_tables);
805 add->new_tables = NULL;
806 add->new_tables_len = 0;
807 add->new_tables_cap = 0;
808
809 err = reftable_stack_reload_maybe_reuse(add->stack, 1);
810 if (err)
811 goto done;
812
813 if (!add->stack->opts.disable_auto_compact) {
814 /*
815 * Auto-compact the stack to keep the number of tables in
816 * control. It is possible that a concurrent writer is already
817 * trying to compact parts of the stack, which would lead to a
818 * `REFTABLE_LOCK_ERROR` because parts of the stack are locked
819 * already. Similarly, the stack may have been rewritten by a
820 * concurrent writer, which causes `REFTABLE_OUTDATED_ERROR`.
821 * Both of these errors are benign, so we simply ignore them.
822 */
823 err = reftable_stack_auto_compact(add->stack);
824 if (err < 0 && err != REFTABLE_LOCK_ERROR &&
825 err != REFTABLE_OUTDATED_ERROR)
826 goto done;
827 err = 0;
828 }
829
830 done:
831 reftable_addition_close(add);
832 return err;
833 }
834
835 int reftable_stack_new_addition(struct reftable_addition **dest,
836 struct reftable_stack *st,
837 unsigned int flags)
838 {
839 int err;
840
841 REFTABLE_CALLOC_ARRAY(*dest, 1);
842 if (!*dest)
843 return REFTABLE_OUT_OF_MEMORY_ERROR;
844
845 err = reftable_stack_init_addition(*dest, st, flags);
846 if (err) {
847 reftable_free(*dest);
848 *dest = NULL;
849 }
850
851 return err;
852 }
853
854 int reftable_addition_add(struct reftable_addition *add,
855 int (*write_table)(struct reftable_writer *wr,
856 void *arg),
857 void *arg)
858 {
859 struct reftable_buf temp_tab_file_name = REFTABLE_BUF_INIT;
860 struct reftable_buf tab_file_name = REFTABLE_BUF_INIT;
861 struct reftable_buf next_name = REFTABLE_BUF_INIT;
862 struct reftable_writer *wr = NULL;
863 struct reftable_tmpfile tab_file = REFTABLE_TMPFILE_INIT;
864 struct fd_writer writer = {
865 .opts = &add->stack->opts,
866 };
867 int err = 0;
868
869 reftable_buf_reset(&next_name);
870
871 err = format_name(&next_name, add->next_update_index, add->next_update_index);
872 if (err < 0)
873 goto done;
874
875 err = stack_filename(&temp_tab_file_name, add->stack, next_name.buf);
876 if (err < 0)
877 goto done;
878
879 err = reftable_buf_addstr(&temp_tab_file_name, ".temp.XXXXXX");
880 if (err < 0)
881 goto done;
882
883 err = tmpfile_from_pattern(&tab_file, temp_tab_file_name.buf);
884 if (err < 0)
885 goto done;
886 if (add->stack->opts.default_permissions) {
887 if (chmod(tab_file.path,
888 add->stack->opts.default_permissions)) {
889 err = REFTABLE_IO_ERROR;
890 goto done;
891 }
892 }
893
894 writer.fd = tab_file.fd;
895 err = reftable_writer_new(&wr, fd_writer_write, fd_writer_flush,
896 &writer, &add->stack->opts);
897 if (err < 0)
898 goto done;
899
900 err = write_table(wr, arg);
901 if (err < 0)
902 goto done;
903
904 err = reftable_writer_close(wr);
905 if (err == REFTABLE_EMPTY_TABLE_ERROR) {
906 err = 0;
907 goto done;
908 }
909 if (err < 0)
910 goto done;
911
912 err = tmpfile_close(&tab_file);
913 if (err < 0)
914 goto done;
915
916 if (wr->min_update_index < add->next_update_index) {
917 err = REFTABLE_API_ERROR;
918 goto done;
919 }
920
921 err = format_name(&next_name, wr->min_update_index, wr->max_update_index);
922 if (err < 0)
923 goto done;
924
925 err = reftable_buf_addstr(&next_name, ".ref");
926 if (err < 0)
927 goto done;
928
929 err = stack_filename(&tab_file_name, add->stack, next_name.buf);
930 if (err < 0)
931 goto done;
932
933 /*
934 On windows, this relies on rand() picking a unique destination name.
935 Maybe we should do retry loop as well?
936 */
937 err = tmpfile_rename(&tab_file, tab_file_name.buf);
938 if (err < 0)
939 goto done;
940
941 REFTABLE_ALLOC_GROW_OR_NULL(add->new_tables, add->new_tables_len + 1,
942 add->new_tables_cap);
943 if (!add->new_tables) {
944 err = REFTABLE_OUT_OF_MEMORY_ERROR;
945 goto done;
946 }
947 add->new_tables[add->new_tables_len++] = reftable_buf_detach(&next_name);
948
949 done:
950 tmpfile_delete(&tab_file);
951 reftable_buf_release(&temp_tab_file_name);
952 reftable_buf_release(&tab_file_name);
953 reftable_buf_release(&next_name);
954 reftable_writer_free(wr);
955 return err;
956 }
957
958 uint64_t reftable_stack_next_update_index(struct reftable_stack *st)
959 {
960 int sz = st->merged->tables_len;
961 if (sz > 0)
962 return reftable_table_max_update_index(st->tables[sz - 1]) +
963 1;
964 return 1;
965 }
966
967 static int stack_write_compact(struct reftable_stack *st,
968 struct reftable_writer *wr,
969 size_t first, size_t last,
970 struct reftable_log_expiry_config *config)
971 {
972 struct reftable_merged_table *mt = NULL;
973 struct reftable_iterator it = { NULL };
974 struct reftable_ref_record ref = { NULL };
975 struct reftable_log_record log = { NULL };
976 size_t subtabs_len = last - first + 1;
977 uint64_t entries = 0;
978 int err = 0;
979
980 for (size_t i = first; i <= last; i++)
981 st->stats.bytes += st->tables[i]->size;
982 err = reftable_writer_set_limits(wr, st->tables[first]->min_update_index,
983 st->tables[last]->max_update_index);
984 if (err < 0)
985 goto done;
986
987 err = reftable_merged_table_new(&mt, st->tables + first, subtabs_len,
988 st->opts.hash_id);
989 if (err < 0)
990 goto done;
991
992 err = merged_table_init_iter(mt, &it, REFTABLE_BLOCK_TYPE_REF);
993 if (err < 0)
994 goto done;
995
996 err = reftable_iterator_seek_ref(&it, "");
997 if (err < 0)
998 goto done;
999
1000 while (1) {
1001 err = reftable_iterator_next_ref(&it, &ref);
1002 if (err > 0) {
1003 err = 0;
1004 break;
1005 }
1006 if (err < 0)
1007 goto done;
1008
1009 if (first == 0 && reftable_ref_record_is_deletion(&ref)) {
1010 continue;
1011 }
1012
1013 err = reftable_writer_add_ref(wr, &ref);
1014 if (err < 0)
1015 goto done;
1016 entries++;
1017 }
1018 reftable_iterator_destroy(&it);
1019
1020 err = merged_table_init_iter(mt, &it, REFTABLE_BLOCK_TYPE_LOG);
1021 if (err < 0)
1022 goto done;
1023
1024 err = reftable_iterator_seek_log(&it, "");
1025 if (err < 0)
1026 goto done;
1027
1028 while (1) {
1029 err = reftable_iterator_next_log(&it, &log);
1030 if (err > 0) {
1031 err = 0;
1032 break;
1033 }
1034 if (err < 0)
1035 goto done;
1036 if (first == 0 && reftable_log_record_is_deletion(&log)) {
1037 continue;
1038 }
1039
1040 if (config && config->min_update_index > 0 &&
1041 log.update_index < config->min_update_index) {
1042 continue;
1043 }
1044
1045 if (config && config->time > 0 &&
1046 log.value.update.time < config->time) {
1047 continue;
1048 }
1049
1050 err = reftable_writer_add_log(wr, &log);
1051 if (err < 0)
1052 goto done;
1053 entries++;
1054 }
1055
1056 done:
1057 reftable_iterator_destroy(&it);
1058 if (mt)
1059 reftable_merged_table_free(mt);
1060 reftable_ref_record_release(&ref);
1061 reftable_log_record_release(&log);
1062 st->stats.entries_written += entries;
1063 return err;
1064 }
1065
1066 static int stack_compact_locked(struct reftable_stack *st,
1067 size_t first, size_t last,
1068 struct reftable_log_expiry_config *config,
1069 struct reftable_tmpfile *tab_file_out)
1070 {
1071 struct reftable_buf next_name = REFTABLE_BUF_INIT;
1072 struct reftable_buf tab_file_path = REFTABLE_BUF_INIT;
1073 struct reftable_writer *wr = NULL;
1074 struct fd_writer writer= {
1075 .opts = &st->opts,
1076 };
1077 struct reftable_tmpfile tab_file = REFTABLE_TMPFILE_INIT;
1078 int err = 0;
1079
1080 err = format_name(&next_name, reftable_table_min_update_index(st->tables[first]),
1081 reftable_table_max_update_index(st->tables[last]));
1082 if (err < 0)
1083 goto done;
1084
1085 err = stack_filename(&tab_file_path, st, next_name.buf);
1086 if (err < 0)
1087 goto done;
1088
1089 err = reftable_buf_addstr(&tab_file_path, ".temp.XXXXXX");
1090 if (err < 0)
1091 goto done;
1092
1093 err = tmpfile_from_pattern(&tab_file, tab_file_path.buf);
1094 if (err < 0)
1095 goto done;
1096
1097 if (st->opts.default_permissions &&
1098 chmod(tab_file.path, st->opts.default_permissions) < 0) {
1099 err = REFTABLE_IO_ERROR;
1100 goto done;
1101 }
1102
1103 writer.fd = tab_file.fd;
1104 err = reftable_writer_new(&wr, fd_writer_write, fd_writer_flush,
1105 &writer, &st->opts);
1106 if (err < 0)
1107 goto done;
1108
1109 err = stack_write_compact(st, wr, first, last, config);
1110 if (err < 0)
1111 goto done;
1112
1113 err = reftable_writer_close(wr);
1114 if (err < 0)
1115 goto done;
1116
1117 err = tmpfile_close(&tab_file);
1118 if (err < 0)
1119 goto done;
1120
1121 *tab_file_out = tab_file;
1122 tab_file = REFTABLE_TMPFILE_INIT;
1123
1124 done:
1125 tmpfile_delete(&tab_file);
1126 reftable_writer_free(wr);
1127 reftable_buf_release(&next_name);
1128 reftable_buf_release(&tab_file_path);
1129 return err;
1130 }
1131
1132 enum stack_compact_range_flags {
1133 /*
1134 * Perform a best-effort compaction. That is, even if we cannot lock
1135 * all tables in the specified range, we will try to compact the
1136 * remaining slice.
1137 */
1138 STACK_COMPACT_RANGE_BEST_EFFORT = (1 << 0),
1139 };
1140
1141 /*
1142 * Compact all tables in the range `[first, last)` into a single new table.
1143 *
1144 * This function returns `0` on success or a code `< 0` on failure. When the
1145 * stack or any of the tables in the specified range are already locked then
1146 * this function returns `REFTABLE_LOCK_ERROR`. This is a benign error that
1147 * callers can either ignore, or they may choose to retry compaction after some
1148 * amount of time.
1149 */
1150 static int stack_compact_range(struct reftable_stack *st,
1151 size_t first, size_t last,
1152 struct reftable_log_expiry_config *expiry,
1153 unsigned int flags)
1154 {
1155 struct reftable_buf tables_list_buf = REFTABLE_BUF_INIT;
1156 struct reftable_buf new_table_name = REFTABLE_BUF_INIT;
1157 struct reftable_buf new_table_path = REFTABLE_BUF_INIT;
1158 struct reftable_buf table_name = REFTABLE_BUF_INIT;
1159 struct reftable_flock tables_list_lock = REFTABLE_FLOCK_INIT;
1160 struct reftable_flock *table_locks = NULL;
1161 struct reftable_tmpfile new_table = REFTABLE_TMPFILE_INIT;
1162 int is_empty_table = 0, err = 0;
1163 size_t first_to_replace, last_to_replace;
1164 size_t i, nlocks = 0;
1165 char **names = NULL;
1166
1167 if (first > last || (!expiry && first == last)) {
1168 err = 0;
1169 goto done;
1170 }
1171
1172 st->stats.attempts++;
1173
1174 /*
1175 * Hold the lock so that we can read "tables.list" and lock all tables
1176 * which are part of the user-specified range.
1177 */
1178 err = flock_acquire(&tables_list_lock, st->list_file, st->opts.lock_timeout_ms);
1179 if (err < 0)
1180 goto done;
1181
1182 /*
1183 * Check whether the stack is up-to-date. We unfortunately cannot
1184 * handle the situation gracefully in case it's _not_ up-to-date
1185 * because the range of tables that the user has requested us to
1186 * compact may have been changed. So instead we abort.
1187 *
1188 * We could in theory improve the situation by having the caller not
1189 * pass in a range, but instead the list of tables to compact. If so,
1190 * we could check that relevant tables still exist. But for now it's
1191 * good enough to just abort.
1192 */
1193 err = stack_uptodate(st);
1194 if (err < 0)
1195 goto done;
1196 if (err > 0) {
1197 err = REFTABLE_OUTDATED_ERROR;
1198 goto done;
1199 }
1200
1201 /*
1202 * Lock all tables in the user-provided range. This is the slice of our
1203 * stack which we'll compact.
1204 *
1205 * Note that we lock tables in reverse order from last to first. The
1206 * intent behind this is to allow a newer process to perform best
1207 * effort compaction of tables that it has added in the case where an
1208 * older process is still busy compacting tables which are preexisting
1209 * from the point of view of the newer process.
1210 */
1211 REFTABLE_ALLOC_ARRAY(table_locks, last - first + 1);
1212 if (!table_locks) {
1213 err = REFTABLE_OUT_OF_MEMORY_ERROR;
1214 goto done;
1215 }
1216 for (i = 0; i < last - first + 1; i++)
1217 table_locks[i] = REFTABLE_FLOCK_INIT;
1218
1219 for (i = last + 1; i > first; i--) {
1220 err = stack_filename(&table_name, st, reftable_table_name(st->tables[i - 1]));
1221 if (err < 0)
1222 goto done;
1223
1224 err = flock_acquire(&table_locks[nlocks], table_name.buf, 0);
1225 if (err < 0) {
1226 /*
1227 * When the table is locked already we may do a
1228 * best-effort compaction and compact only the tables
1229 * that we have managed to lock so far. This of course
1230 * requires that we have been able to lock at least two
1231 * tables, otherwise there would be nothing to compact.
1232 * In that case, we return a lock error to our caller.
1233 */
1234 if (err == REFTABLE_LOCK_ERROR && last - (i - 1) >= 2 &&
1235 flags & STACK_COMPACT_RANGE_BEST_EFFORT) {
1236 err = 0;
1237 /*
1238 * The subtraction is to offset the index, the
1239 * addition is to only compact up to the table
1240 * of the preceding iteration. They obviously
1241 * cancel each other out, but that may be
1242 * non-obvious when it was omitted.
1243 */
1244 first = (i - 1) + 1;
1245 break;
1246 }
1247
1248 goto done;
1249 }
1250
1251 /*
1252 * We need to close the lockfiles as we might otherwise easily
1253 * run into file descriptor exhaustion when we compress a lot
1254 * of tables.
1255 */
1256 err = flock_close(&table_locks[nlocks++]);
1257 if (err < 0)
1258 goto done;
1259 }
1260
1261 /*
1262 * We have locked all tables in our range and can thus release the
1263 * "tables.list" lock while compacting the locked tables. This allows
1264 * concurrent updates to the stack to proceed.
1265 */
1266 err = flock_release(&tables_list_lock);
1267 if (err < 0) {
1268 err = REFTABLE_IO_ERROR;
1269 goto done;
1270 }
1271
1272 /*
1273 * Compact the now-locked tables into a new table. Note that compacting
1274 * these tables may end up with an empty new table in case tombstones
1275 * end up cancelling out all refs in that range.
1276 */
1277 err = stack_compact_locked(st, first, last, expiry, &new_table);
1278 if (err < 0) {
1279 if (err != REFTABLE_EMPTY_TABLE_ERROR)
1280 goto done;
1281 is_empty_table = 1;
1282 }
1283
1284 /*
1285 * Now that we have written the new, compacted table we need to re-lock
1286 * "tables.list". We'll then replace the compacted range of tables with
1287 * the new table.
1288 */
1289 err = flock_acquire(&tables_list_lock, st->list_file, st->opts.lock_timeout_ms);
1290 if (err < 0)
1291 goto done;
1292
1293 if (st->opts.default_permissions) {
1294 if (chmod(tables_list_lock.path,
1295 st->opts.default_permissions) < 0) {
1296 err = REFTABLE_IO_ERROR;
1297 goto done;
1298 }
1299 }
1300
1301 /*
1302 * As we have unlocked the stack while compacting our slice of tables
1303 * it may have happened that a concurrently running process has updated
1304 * the stack while we were compacting. In that case, we need to check
1305 * whether the tables that we have just compacted still exist in the
1306 * stack in the exact same order as we have compacted them.
1307 *
1308 * If they do exist, then it is fine to continue and replace those
1309 * tables with our compacted version. If they don't, then we need to
1310 * abort.
1311 */
1312 err = stack_uptodate(st);
1313 if (err < 0)
1314 goto done;
1315 if (err > 0) {
1316 ssize_t new_offset = -1;
1317 int fd;
1318
1319 fd = open(st->list_file, O_RDONLY);
1320 if (fd < 0) {
1321 err = REFTABLE_IO_ERROR;
1322 goto done;
1323 }
1324
1325 err = fd_read_lines(fd, &names);
1326 close(fd);
1327 if (err < 0)
1328 goto done;
1329
1330 /*
1331 * Search for the offset of the first table that we have
1332 * compacted in the updated "tables.list" file.
1333 */
1334 for (size_t i = 0; names[i]; i++) {
1335 if (strcmp(names[i], st->tables[first]->name))
1336 continue;
1337
1338 /*
1339 * We have found the first entry. Verify that all the
1340 * subsequent tables we have compacted still exist in
1341 * the modified stack in the exact same order as we
1342 * have compacted them.
1343 */
1344 for (size_t j = 1; j < last - first + 1; j++) {
1345 const char *old = first + j < st->merged->tables_len ?
1346 st->tables[first + j]->name : NULL;
1347 const char *new = names[i + j];
1348
1349 /*
1350 * If some entries are missing or in case the tables
1351 * have changed then we need to bail out. Again, this
1352 * shouldn't ever happen because we have locked the
1353 * tables we are compacting.
1354 */
1355 if (!old || !new || strcmp(old, new)) {
1356 err = REFTABLE_OUTDATED_ERROR;
1357 goto done;
1358 }
1359 }
1360
1361 new_offset = i;
1362 break;
1363 }
1364
1365 /*
1366 * In case we didn't find our compacted tables in the stack we
1367 * need to bail out. In theory, this should have never happened
1368 * because we locked the tables we are compacting.
1369 */
1370 if (new_offset < 0) {
1371 err = REFTABLE_OUTDATED_ERROR;
1372 goto done;
1373 }
1374
1375 /*
1376 * We have found the new range that we want to replace, so
1377 * let's update the range of tables that we want to replace.
1378 */
1379 first_to_replace = new_offset;
1380 last_to_replace = last + (new_offset - first);
1381 } else {
1382 /*
1383 * `fd_read_lines()` uses a `NULL` sentinel to indicate that
1384 * the array is at its end. As we use `free_names()` to free
1385 * the array, we need to include this sentinel value here and
1386 * thus have to allocate `tables_len + 1` many entries.
1387 */
1388 REFTABLE_CALLOC_ARRAY(names, st->merged->tables_len + 1);
1389 if (!names) {
1390 err = REFTABLE_OUT_OF_MEMORY_ERROR;
1391 goto done;
1392 }
1393
1394 for (size_t i = 0; i < st->merged->tables_len; i++) {
1395 names[i] = reftable_strdup(st->tables[i]->name);
1396 if (!names[i]) {
1397 err = REFTABLE_OUT_OF_MEMORY_ERROR;
1398 goto done;
1399 }
1400 }
1401 first_to_replace = first;
1402 last_to_replace = last;
1403 }
1404
1405 /*
1406 * If the resulting compacted table is not empty, then we need to move
1407 * it into place now.
1408 */
1409 if (!is_empty_table) {
1410 err = format_name(&new_table_name, st->tables[first]->min_update_index,
1411 st->tables[last]->max_update_index);
1412 if (err < 0)
1413 goto done;
1414
1415 err = reftable_buf_addstr(&new_table_name, ".ref");
1416 if (err < 0)
1417 goto done;
1418
1419 err = stack_filename(&new_table_path, st, new_table_name.buf);
1420 if (err < 0)
1421 goto done;
1422
1423 err = tmpfile_rename(&new_table, new_table_path.buf);
1424 if (err < 0)
1425 goto done;
1426 }
1427
1428 /*
1429 * Write the new "tables.list" contents with the compacted table we
1430 * have just written. In case the compacted table became empty we
1431 * simply skip writing it.
1432 */
1433 for (i = 0; i < first_to_replace; i++) {
1434 if ((err = reftable_buf_addstr(&tables_list_buf, names[i])) < 0 ||
1435 (err = reftable_buf_addstr(&tables_list_buf, "\n")) < 0)
1436 goto done;
1437 }
1438 if (!is_empty_table) {
1439 if ((err = reftable_buf_addstr(&tables_list_buf, new_table_name.buf)) < 0 ||
1440 (err = reftable_buf_addstr(&tables_list_buf, "\n")) < 0)
1441 goto done;
1442 }
1443 for (i = last_to_replace + 1; names[i]; i++) {
1444 if ((err = reftable_buf_addstr(&tables_list_buf, names[i])) < 0 ||
1445 (err = reftable_buf_addstr(&tables_list_buf, "\n")) < 0)
1446 goto done;
1447 }
1448
1449 err = reftable_write_data(tables_list_lock.fd,
1450 tables_list_buf.buf, tables_list_buf.len);
1451 if (err < 0) {
1452 err = REFTABLE_IO_ERROR;
1453 unlink(new_table_path.buf);
1454 goto done;
1455 }
1456
1457 err = fsync(tables_list_lock.fd);
1458 if (err < 0) {
1459 err = REFTABLE_IO_ERROR;
1460 unlink(new_table_path.buf);
1461 goto done;
1462 }
1463
1464 err = flock_commit(&tables_list_lock);
1465 if (err < 0) {
1466 err = REFTABLE_IO_ERROR;
1467 unlink(new_table_path.buf);
1468 goto done;
1469 }
1470
1471 /*
1472 * Reload the stack before deleting the compacted tables. We can only
1473 * delete the files after we closed them on Windows, so this needs to
1474 * happen first.
1475 */
1476 err = reftable_stack_reload_maybe_reuse(st, first < last);
1477 if (err < 0)
1478 goto done;
1479
1480 /*
1481 * Delete the old tables. They may still be in use by concurrent
1482 * readers, so it is expected that unlinking tables may fail.
1483 */
1484 for (i = 0; i < nlocks; i++) {
1485 struct reftable_flock *table_lock = &table_locks[i];
1486
1487 reftable_buf_reset(&table_name);
1488 err = reftable_buf_add(&table_name, table_lock->path,
1489 strlen(table_lock->path) - strlen(".lock"));
1490 if (err)
1491 continue;
1492
1493 unlink(table_name.buf);
1494 }
1495
1496 done:
1497 flock_release(&tables_list_lock);
1498 for (i = 0; table_locks && i < nlocks; i++)
1499 flock_release(&table_locks[i]);
1500 reftable_free(table_locks);
1501
1502 tmpfile_delete(&new_table);
1503 reftable_buf_release(&new_table_name);
1504 reftable_buf_release(&new_table_path);
1505 reftable_buf_release(&tables_list_buf);
1506 reftable_buf_release(&table_name);
1507 free_names(names);
1508
1509 if (err == REFTABLE_LOCK_ERROR)
1510 st->stats.failures++;
1511
1512 return err;
1513 }
1514
1515 int reftable_stack_compact_all(struct reftable_stack *st,
1516 struct reftable_log_expiry_config *config)
1517 {
1518 size_t last = st->merged->tables_len ? st->merged->tables_len - 1 : 0;
1519 return stack_compact_range(st, 0, last, config, 0);
1520 }
1521
1522 static int segment_size(struct segment *s)
1523 {
1524 return s->end - s->start;
1525 }
1526
1527 struct segment suggest_compaction_segment(uint64_t *sizes, size_t n,
1528 uint8_t factor)
1529 {
1530 struct segment seg = { 0 };
1531 uint64_t bytes;
1532 size_t i;
1533
1534 if (!factor)
1535 factor = DEFAULT_GEOMETRIC_FACTOR;
1536
1537 /*
1538 * If there are no tables or only a single one then we don't have to
1539 * compact anything. The sequence is geometric by definition already.
1540 */
1541 if (n <= 1)
1542 return seg;
1543
1544 /*
1545 * Find the ending table of the compaction segment needed to restore the
1546 * geometric sequence. Note that the segment end is exclusive.
1547 *
1548 * To do so, we iterate backwards starting from the most recent table
1549 * until a valid segment end is found. If the preceding table is smaller
1550 * than the current table multiplied by the geometric factor (2), the
1551 * compaction segment end has been identified.
1552 *
1553 * Tables after the ending point are not added to the byte count because
1554 * they are already valid members of the geometric sequence. Due to the
1555 * properties of a geometric sequence, it is not possible for the sum of
1556 * these tables to exceed the value of the ending point table.
1557 *
1558 * Example table size sequence requiring no compaction:
1559 * 64, 32, 16, 8, 4, 2, 1
1560 *
1561 * Example table size sequence where compaction segment end is set to
1562 * the last table. Since the segment end is exclusive, the last table is
1563 * excluded during subsequent compaction and the table with size 3 is
1564 * the final table included:
1565 * 64, 32, 16, 8, 4, 3, 1
1566 */
1567 for (i = n - 1; i > 0; i--) {
1568 if (sizes[i - 1] < sizes[i] * factor) {
1569 seg.end = i + 1;
1570 bytes = sizes[i];
1571 break;
1572 }
1573 }
1574
1575 /*
1576 * Find the starting table of the compaction segment by iterating
1577 * through the remaining tables and keeping track of the accumulated
1578 * size of all tables seen from the segment end table. The previous
1579 * table is compared to the accumulated size because the tables from the
1580 * segment end are merged backwards recursively.
1581 *
1582 * Note that we keep iterating even after we have found the first
1583 * starting point. This is because there may be tables in the stack
1584 * preceding that first starting point which violate the geometric
1585 * sequence.
1586 *
1587 * Example compaction segment start set to table with size 32:
1588 * 128, 32, 16, 8, 4, 3, 1
1589 */
1590 for (; i > 0; i--) {
1591 uint64_t curr = bytes;
1592 bytes += sizes[i - 1];
1593
1594 if (sizes[i - 1] < curr * factor) {
1595 seg.start = i - 1;
1596 seg.bytes = bytes;
1597 }
1598 }
1599
1600 return seg;
1601 }
1602
1603 static int stack_segments_for_compaction(struct reftable_stack *st,
1604 struct segment *seg)
1605 {
1606 int version = (st->opts.hash_id == REFTABLE_HASH_SHA1) ? 1 : 2;
1607 int overhead = header_size(version) - 1;
1608 uint64_t *sizes;
1609
1610 REFTABLE_CALLOC_ARRAY(sizes, st->merged->tables_len);
1611 if (!sizes)
1612 return REFTABLE_OUT_OF_MEMORY_ERROR;
1613
1614 for (size_t i = 0; i < st->merged->tables_len; i++)
1615 sizes[i] = st->tables[i]->size - overhead;
1616
1617 *seg = suggest_compaction_segment(sizes, st->merged->tables_len,
1618 st->opts.auto_compaction_factor);
1619 reftable_free(sizes);
1620
1621 return 0;
1622 }
1623
1624 static int update_segment_if_compaction_required(struct reftable_stack *st,
1625 struct segment *seg,
1626 bool use_geometric,
1627 bool *required)
1628 {
1629 int err;
1630
1631 if (st->merged->tables_len < 2) {
1632 *required = false;
1633 return 0;
1634 }
1635
1636 if (!use_geometric) {
1637 *required = true;
1638 return 0;
1639 }
1640
1641 err = stack_segments_for_compaction(st, seg);
1642 if (err)
1643 return err;
1644
1645 *required = segment_size(seg) > 0;
1646 return 0;
1647 }
1648
1649 int reftable_stack_compaction_required(struct reftable_stack *st,
1650 bool use_heuristics,
1651 bool *required)
1652 {
1653 struct segment seg;
1654 return update_segment_if_compaction_required(st, &seg, use_heuristics,
1655 required);
1656 }
1657
1658 int reftable_stack_auto_compact(struct reftable_stack *st)
1659 {
1660 struct segment seg;
1661 bool required;
1662 int err;
1663
1664 err = update_segment_if_compaction_required(st, &seg, true, &required);
1665 if (err)
1666 return err;
1667
1668 if (required)
1669 return stack_compact_range(st, seg.start, seg.end - 1,
1670 NULL, STACK_COMPACT_RANGE_BEST_EFFORT);
1671
1672 return 0;
1673 }
1674
1675 struct reftable_compaction_stats *
1676 reftable_stack_compaction_stats(struct reftable_stack *st)
1677 {
1678 return &st->stats;
1679 }
1680
1681 int reftable_stack_read_ref(struct reftable_stack *st, const char *refname,
1682 struct reftable_ref_record *ref)
1683 {
1684 struct reftable_iterator it = { 0 };
1685 int ret;
1686
1687 ret = reftable_merged_table_init_ref_iterator(st->merged, &it);
1688 if (ret)
1689 goto out;
1690
1691 ret = reftable_iterator_seek_ref(&it, refname);
1692 if (ret)
1693 goto out;
1694
1695 ret = reftable_iterator_next_ref(&it, ref);
1696 if (ret)
1697 goto out;
1698
1699 if (strcmp(ref->refname, refname) ||
1700 reftable_ref_record_is_deletion(ref)) {
1701 reftable_ref_record_release(ref);
1702 ret = 1;
1703 goto out;
1704 }
1705
1706 out:
1707 reftable_iterator_destroy(&it);
1708 return ret;
1709 }
1710
1711 int reftable_stack_read_log(struct reftable_stack *st, const char *refname,
1712 struct reftable_log_record *log)
1713 {
1714 struct reftable_iterator it = {0};
1715 int err;
1716
1717 err = reftable_stack_init_log_iterator(st, &it);
1718 if (err)
1719 goto done;
1720
1721 err = reftable_iterator_seek_log(&it, refname);
1722 if (err)
1723 goto done;
1724
1725 err = reftable_iterator_next_log(&it, log);
1726 if (err)
1727 goto done;
1728
1729 if (strcmp(log->refname, refname) ||
1730 reftable_log_record_is_deletion(log)) {
1731 err = 1;
1732 goto done;
1733 }
1734
1735 done:
1736 if (err) {
1737 reftable_log_record_release(log);
1738 }
1739 reftable_iterator_destroy(&it);
1740 return err;
1741 }
1742
1743 static int is_table_name(const char *s)
1744 {
1745 const char *dot = strrchr(s, '.');
1746 return dot && !strcmp(dot, ".ref");
1747 }
1748
1749 static void remove_maybe_stale_table(struct reftable_stack *st, uint64_t max,
1750 const char *name)
1751 {
1752 int err = 0;
1753 uint64_t update_idx = 0;
1754 struct reftable_block_source src = { NULL };
1755 struct reftable_table *table = NULL;
1756 struct reftable_buf table_path = REFTABLE_BUF_INIT;
1757
1758 err = stack_filename(&table_path, st, name);
1759 if (err < 0)
1760 goto done;
1761
1762 err = reftable_block_source_from_file(&src, table_path.buf);
1763 if (err < 0)
1764 goto done;
1765
1766 err = reftable_table_new(&table, &src, name);
1767 if (err < 0)
1768 goto done;
1769
1770 update_idx = reftable_table_max_update_index(table);
1771 reftable_table_decref(table);
1772
1773 if (update_idx <= max) {
1774 unlink(table_path.buf);
1775 }
1776 done:
1777 reftable_buf_release(&table_path);
1778 }
1779
1780 static int reftable_stack_clean_locked(struct reftable_stack *st)
1781 {
1782 uint64_t max = reftable_merged_table_max_update_index(
1783 reftable_stack_merged_table(st));
1784 DIR *dir = opendir(st->reftable_dir);
1785 struct dirent *d = NULL;
1786 if (!dir) {
1787 return REFTABLE_IO_ERROR;
1788 }
1789
1790 while ((d = readdir(dir))) {
1791 int found = 0;
1792 if (!is_table_name(d->d_name))
1793 continue;
1794
1795 for (size_t i = 0; !found && i < st->tables_len; i++)
1796 found = !strcmp(reftable_table_name(st->tables[i]), d->d_name);
1797 if (found)
1798 continue;
1799
1800 remove_maybe_stale_table(st, max, d->d_name);
1801 }
1802
1803 closedir(dir);
1804 return 0;
1805 }
1806
1807 int reftable_stack_clean(struct reftable_stack *st)
1808 {
1809 struct reftable_addition *add = NULL;
1810 int err = reftable_stack_new_addition(&add, st, 0);
1811 if (err < 0) {
1812 goto done;
1813 }
1814
1815 err = reftable_stack_reload(st);
1816 if (err < 0) {
1817 goto done;
1818 }
1819
1820 err = reftable_stack_clean_locked(st);
1821
1822 done:
1823 reftable_addition_destroy(add);
1824 return err;
1825 }
1826
1827 enum reftable_hash reftable_stack_hash_id(struct reftable_stack *st)
1828 {
1829 return reftable_merged_table_hash_id(st->merged);
1830 }