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
11 #include "../write-or-die.h"
16 #include "reftable-error.h"
17 #include "reftable-record.h"
18 #include "reftable-merged.h"
22 static int stack_try_add(struct reftable_stack
*st
,
23 int (*write_table
)(struct reftable_writer
*wr
,
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
,
36 static void stack_filename(struct strbuf
*dest
, struct reftable_stack
*st
,
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
;
65 if (config
.hash_id
== 0) {
66 config
.hash_id
= GIT_SHA1_FORMAT_ID
;
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
);
77 p
->reftable_dir
= xstrdup(dir
);
80 err
= reftable_stack_reload_maybe_reuse(p
, 1);
82 reftable_stack_destroy(p
);
89 static int fd_read_lines(int fd
, char ***namesp
)
91 off_t size
= lseek(fd
, 0, SEEK_END
);
95 err
= REFTABLE_IO_ERROR
;
98 err
= lseek(fd
, 0, SEEK_SET
);
100 err
= REFTABLE_IO_ERROR
;
104 REFTABLE_ALLOC_ARRAY(buf
, size
+ 1);
105 if (read_in_full(fd
, buf
, size
) != size
) {
106 err
= REFTABLE_IO_ERROR
;
111 parse_names(buf
, size
, namesp
);
118 int read_lines(const char *filename
, char ***namesp
)
120 int fd
= open(filename
, O_RDONLY
);
123 if (errno
== ENOENT
) {
124 REFTABLE_CALLOC_ARRAY(*namesp
, 1);
128 return REFTABLE_IO_ERROR
;
130 err
= fd_read_lines(fd
, namesp
);
135 struct reftable_merged_table
*
136 reftable_stack_merged_table(struct reftable_stack
*st
)
141 static int has_name(char **names
, const char *name
)
144 if (!strcmp(*names
, name
))
151 /* Close and free the stack */
152 void reftable_stack_destroy(struct reftable_stack
*st
)
157 reftable_merged_table_free(st
->merged
);
161 err
= read_lines(st
->list_file
, &names
);
163 FREE_AND_NULL(names
);
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
]);
178 /* On Windows, can only unlink after closing. */
179 unlink(filename
.buf
);
182 strbuf_release(&filename
);
184 FREE_AND_NULL(st
->readers
);
187 if (st
->list_fd
>= 0) {
192 FREE_AND_NULL(st
->list_file
);
193 FREE_AND_NULL(st
->reftable_dir
);
198 static struct reftable_reader
**stack_copy_readers(struct reftable_stack
*st
,
201 struct reftable_reader
**cur
= reftable_calloc(cur_len
, sizeof(*cur
));
203 for (i
= 0; i
< cur_len
; i
++) {
204 cur
[i
] = st
->readers
[i
];
209 static int reftable_stack_reload_once(struct reftable_stack
*st
, char **names
,
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
;
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
)) {
240 struct reftable_block_source src
= { NULL
};
241 stack_filename(&table_path
, st
, name
);
243 err
= reftable_block_source_from_file(&src
,
248 err
= reftable_new_reader(&rd
, &src
, name
);
253 new_readers
[new_readers_len
] = rd
;
254 reftable_table_from_reader(&new_tables
[new_readers_len
], rd
);
259 err
= reftable_new_merged_table(&new_merged
, new_tables
,
260 new_readers_len
, st
->config
.hash_id
);
265 st
->readers_len
= new_readers_len
;
267 merged_table_release(st
->merged
);
268 reftable_merged_table_free(st
->merged
);
271 reftable_free(st
->readers
);
273 st
->readers
= new_readers
;
277 new_merged
->suppress_deletions
= 1;
278 st
->merged
= new_merged
;
279 for (i
= 0; i
< cur_len
; 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
);
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
);
300 strbuf_release(&table_path
);
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
;
316 static int reftable_stack_reload_maybe_reuse(struct reftable_stack
*st
,
319 char **names
= NULL
, **names_after
= NULL
;
320 struct timeval deadline
;
325 err
= gettimeofday(&deadline
, NULL
);
328 deadline
.tv_sec
+= 3;
333 err
= gettimeofday(&now
, NULL
);
338 * Only look at deadlines after the first few times. This
339 * simplifies debugging in GDB.
342 if (tries
> 3 && tv_cmp(&now
, &deadline
) >= 0)
345 fd
= open(st
->list_file
, O_RDONLY
);
347 if (errno
!= ENOENT
) {
348 err
= REFTABLE_IO_ERROR
;
352 REFTABLE_CALLOC_ARRAY(names
, 1);
354 err
= fd_read_lines(fd
, &names
);
359 err
= reftable_stack_reload_once(st
, names
, reuse_open
);
362 if (err
!= REFTABLE_NOT_EXIST_ERROR
)
366 * REFTABLE_NOT_EXIST_ERROR can be caused by a concurrent
367 * writer. Check if there was one by checking if the name list
370 err
= read_lines(st
->list_file
, &names_after
);
373 if (names_equal(names_after
, names
)) {
374 err
= REFTABLE_NOT_EXIST_ERROR
;
380 free_names(names_after
);
385 delay
= delay
+ (delay
* rand()) / RAND_MAX
+ 1;
386 sleep_millisec(delay
);
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) {
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
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
) {
445 free_names(names_after
);
452 static int stack_uptodate(struct reftable_stack
*st
)
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) {
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
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
487 if (st
->list_st
.st_dev
== list_st
.st_dev
&&
488 st
->list_st
.st_ino
== list_st
.st_ino
)
492 err
= read_lines(st
->list_file
, &names
);
496 for (i
= 0; i
< st
->readers_len
; i
++) {
502 if (strcmp(st
->readers
[i
]->name
, names
[i
])) {
508 if (names
[st
->merged
->stack_len
]) {
518 int reftable_stack_reload(struct reftable_stack
*st
)
520 int err
= stack_uptodate(st
);
522 return reftable_stack_reload_maybe_reuse(st
, 1);
526 int reftable_stack_add(struct reftable_stack
*st
,
527 int (*write
)(struct reftable_writer
*wr
, void *arg
),
530 int err
= stack_try_add(st
, write
, arg
);
532 if (err
== REFTABLE_OUTDATED_ERROR
) {
533 /* Ignore error return, we want to propagate
534 REFTABLE_OUTDATED_ERROR.
536 reftable_stack_reload(st
);
544 static void format_name(struct strbuf
*dest
, uint64_t min
, uint64_t max
)
547 uint32_t rnd
= (uint32_t)git_rand();
548 snprintf(buf
, sizeof(buf
), "0x%012" PRIx64
"-0x%012" PRIx64
"-%08x",
551 strbuf_addstr(dest
, buf
);
554 struct reftable_addition
{
555 struct tempfile
*lock_file
;
556 struct reftable_stack
*stack
;
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
;
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
;
579 err
= REFTABLE_IO_ERROR
;
583 if (st
->config
.default_permissions
) {
584 if (chmod(add
->lock_file
->filename
.buf
, st
->config
.default_permissions
) < 0) {
585 err
= REFTABLE_IO_ERROR
;
590 err
= stack_uptodate(st
);
594 err
= REFTABLE_OUTDATED_ERROR
;
598 add
->next_update_index
= reftable_stack_next_update_index(st
);
601 reftable_addition_close(add
);
603 strbuf_release(&lock_file_name
);
607 static void reftable_addition_close(struct reftable_addition
*add
)
609 struct strbuf nm
= STRBUF_INIT
;
612 for (i
= 0; i
< add
->new_tables_len
; i
++) {
613 stack_filename(&nm
, add
->stack
, add
->new_tables
[i
]);
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
);
627 void reftable_addition_destroy(struct reftable_addition
*add
)
632 reftable_addition_close(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
);
643 if (add
->new_tables_len
== 0)
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
);
658 err
= REFTABLE_IO_ERROR
;
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
);
667 err
= REFTABLE_IO_ERROR
;
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);
683 if (!add
->stack
->disable_auto_compact
)
684 err
= reftable_stack_auto_compact(add
->stack
);
687 reftable_addition_close(add
);
691 int reftable_stack_new_addition(struct reftable_addition
**dest
,
692 struct reftable_stack
*st
)
695 struct reftable_addition empty
= REFTABLE_ADDITION_INIT
;
696 REFTABLE_CALLOC_ARRAY(*dest
, 1);
698 err
= reftable_stack_init_addition(*dest
, st
);
700 reftable_free(*dest
);
706 static int stack_try_add(struct reftable_stack
*st
,
707 int (*write_table
)(struct reftable_writer
*wr
,
711 struct reftable_addition add
= REFTABLE_ADDITION_INIT
;
712 int err
= reftable_stack_init_addition(&add
, st
);
716 err
= reftable_addition_add(&add
, write_table
, arg
);
720 err
= reftable_addition_commit(&add
);
722 reftable_addition_close(&add
);
726 int reftable_addition_add(struct reftable_addition
*add
,
727 int (*write_table
)(struct reftable_writer
*wr
,
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
;
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
);
747 err
= REFTABLE_IO_ERROR
;
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
;
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
);
765 err
= reftable_writer_close(wr
);
766 if (err
== REFTABLE_EMPTY_TABLE_ERROR
) {
773 err
= close_tempfile_gently(tab_file
);
775 err
= REFTABLE_IO_ERROR
;
779 err
= stack_check_addition(add
->stack
, get_tempfile_path(tab_file
));
783 if (wr
->min_update_index
< add
->next_update_index
) {
784 err
= REFTABLE_API_ERROR
;
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
);
798 err
= REFTABLE_IO_ERROR
;
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
);
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
);
814 uint64_t reftable_stack_next_update_index(struct reftable_stack
*st
)
816 int sz
= st
->merged
->stack_len
;
818 return reftable_reader_max_update_index(st
->readers
[sz
- 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
;
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
);
842 err
= REFTABLE_IO_ERROR
;
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
;
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
);
859 err
= reftable_writer_close(wr
);
863 err
= close_tempfile_gently(tab_file
);
867 *tab_file_out
= tab_file
;
871 delete_tempfile(&tab_file
);
872 reftable_writer_free(wr
);
873 strbuf_release(&next_name
);
874 strbuf_release(&tab_file_path
);
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;
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
,
904 reftable_free(subtabs
);
908 err
= reftable_merged_table_seek_ref(mt
, &it
, "");
913 err
= reftable_iterator_next_ref(&it
, &ref
);
921 if (first
== 0 && reftable_ref_record_is_deletion(&ref
)) {
925 err
= reftable_writer_add_ref(wr
, &ref
);
930 reftable_iterator_destroy(&it
);
932 err
= reftable_merged_table_seek_log(mt
, &it
, "");
937 err
= reftable_iterator_next_log(&it
, &log
);
944 if (first
== 0 && reftable_log_record_is_deletion(&log
)) {
948 if (config
&& config
->min_update_index
> 0 &&
949 log
.update_index
< config
->min_update_index
) {
953 if (config
&& config
->time
> 0 &&
954 log
.value
.update
.time
< config
->time
) {
958 err
= reftable_writer_add_log(wr
, &log
);
965 reftable_iterator_destroy(&it
);
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
;
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;
991 if (first
> last
|| (!expiry
&& first
== last
)) {
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
,
1005 if (errno
== EEXIST
)
1008 err
= REFTABLE_IO_ERROR
;
1012 err
= stack_uptodate(st
);
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
);
1027 if (errno
== EEXIST
)
1030 err
= REFTABLE_IO_ERROR
;
1035 * We need to close the lockfiles as we might otherwise easily
1036 * run into file descriptor exhaustion when we compress a lot
1039 err
= close_lock_file_gently(&table_locks
[i
- first
]);
1041 err
= REFTABLE_IO_ERROR
;
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
);
1053 err
= REFTABLE_IO_ERROR
;
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
);
1064 if (err
!= REFTABLE_EMPTY_TABLE_ERROR
)
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
1074 err
= hold_lock_file_for_update(&tables_list_lock
, st
->list_file
,
1077 if (errno
== EEXIST
)
1080 err
= REFTABLE_IO_ERROR
;
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
;
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
);
1104 err
= REFTABLE_IO_ERROR
;
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
);
1124 err
= REFTABLE_IO_ERROR
;
1125 unlink(new_table_path
.buf
);
1129 err
= fsync_component(FSYNC_COMPONENT_REFERENCE
, get_lock_file_fd(&tables_list_lock
));
1131 err
= REFTABLE_IO_ERROR
;
1132 unlink(new_table_path
.buf
);
1136 err
= commit_lock_file(&tables_list_lock
);
1138 err
= REFTABLE_IO_ERROR
;
1139 unlink(new_table_path
.buf
);
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
1148 err
= reftable_stack_reload_maybe_reuse(st
, first
< last
);
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
);
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
);
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
);
1191 st
->stats
.failures
++;
1195 static int segment_size(struct segment
*s
)
1197 return s
->end
- s
->start
;
1200 int fastlog2(uint64_t sz
)
1205 for (; sz
; sz
/= 2) {
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 };
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
= {
1234 cur
.bytes
+= sizes
[i
];
1241 struct segment
suggest_compaction_segment(uint64_t *sizes
, size_t n
)
1243 struct segment min_seg
= {
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)
1254 if (segs
[i
].log
< min_seg
.log
)
1258 while (min_seg
.start
> 0) {
1259 size_t prev
= min_seg
.start
- 1;
1260 if (fastlog2(min_seg
.bytes
) < fastlog2(sizes
[prev
]))
1263 min_seg
.start
= prev
;
1264 min_seg
.bytes
+= sizes
[prev
];
1267 reftable_free(segs
);
1271 static uint64_t *stack_table_sizes_for_compaction(struct reftable_stack
*st
)
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;
1278 for (i
= 0; i
< st
->merged
->stack_len
; i
++) {
1279 sizes
[i
] = st
->readers
[i
]->size
- overhead
;
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,
1297 struct reftable_compaction_stats
*
1298 reftable_stack_compaction_stats(struct reftable_stack
*st
)
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
);
1320 err
= reftable_iterator_next_log(&it
, log
);
1324 if (strcmp(log
->refname
, refname
) ||
1325 reftable_log_record_is_deletion(log
)) {
1332 reftable_log_record_release(log
);
1334 reftable_iterator_destroy(&it
);
1338 static int stack_check_addition(struct reftable_stack
*st
,
1339 const char *new_tab_name
)
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
};
1351 if (st
->config
.skip_name_check
)
1354 err
= reftable_block_source_from_file(&src
, new_tab_name
);
1358 err
= reftable_new_reader(&rd
, &src
, new_tab_name
);
1362 err
= reftable_reader_seek_ref(rd
, &it
, "");
1371 struct reftable_ref_record ref
= { NULL
};
1372 err
= reftable_iterator_next_ref(&it
, &ref
);
1378 REFTABLE_ALLOC_GROW(refs
, len
+ 1, cap
);
1382 reftable_table_from_merged_table(&tab
, reftable_stack_merged_table(st
));
1384 err
= validate_ref_record_addition(tab
, refs
, len
);
1387 for (i
= 0; i
< len
; i
++) {
1388 reftable_ref_record_release(&refs
[i
]);
1392 reftable_iterator_destroy(&it
);
1393 reftable_reader_free(rd
);
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
,
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
);
1417 err
= reftable_new_reader(&rd
, &src
, name
);
1421 update_idx
= reftable_reader_max_update_index(rd
);
1422 reftable_reader_free(rd
);
1424 if (update_idx
<= max
) {
1425 unlink(table_path
.buf
);
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
;
1438 return REFTABLE_IO_ERROR
;
1441 while ((d
= readdir(dir
))) {
1444 if (!is_table_name(d
->d_name
))
1447 for (i
= 0; !found
&& i
< st
->readers_len
; i
++) {
1448 found
= !strcmp(reader_name(st
->readers
[i
]), d
->d_name
);
1453 remove_maybe_stale_table(st
, max
, d
->d_name
);
1460 int reftable_stack_clean(struct reftable_stack
*st
)
1462 struct reftable_addition
*add
= NULL
;
1463 int err
= reftable_stack_new_addition(&add
, st
);
1468 err
= reftable_stack_reload(st
);
1473 err
= reftable_stack_clean_locked(st
);
1476 reftable_addition_destroy(add
);
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
);
1491 merged
= reftable_stack_merged_table(stack
);
1492 reftable_table_from_merged_table(&table
, merged
);
1493 err
= reftable_table_print(&table
);
1496 reftable_stack_destroy(stack
);