Merge branch 'bc/zsh-compatibility'
[git/gitster.git] / reftable / writer.c
blob10eccaaa07f568ecc78bcb58adc90429ad5393c7
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 "writer.h"
11 #include "system.h"
13 #include "block.h"
14 #include "constants.h"
15 #include "record.h"
16 #include "tree.h"
17 #include "reftable-error.h"
19 /* finishes a block, and writes it to storage */
20 static int writer_flush_block(struct reftable_writer *w);
22 /* deallocates memory related to the index */
23 static void writer_clear_index(struct reftable_writer *w);
25 /* finishes writing a 'r' (refs) or 'g' (reflogs) section */
26 static int writer_finish_public_section(struct reftable_writer *w);
28 static struct reftable_block_stats *
29 writer_reftable_block_stats(struct reftable_writer *w, uint8_t typ)
31 switch (typ) {
32 case 'r':
33 return &w->stats.ref_stats;
34 case 'o':
35 return &w->stats.obj_stats;
36 case 'i':
37 return &w->stats.idx_stats;
38 case 'g':
39 return &w->stats.log_stats;
41 abort();
42 return NULL;
45 /* write data, queuing the padding for the next write. Returns negative for
46 * error. */
47 static int padded_write(struct reftable_writer *w, uint8_t *data, size_t len,
48 int padding)
50 int n = 0;
51 if (w->pending_padding > 0) {
52 uint8_t *zeroed = reftable_calloc(w->pending_padding, sizeof(*zeroed));
53 int n = w->write(w->write_arg, zeroed, w->pending_padding);
54 if (n < 0)
55 return n;
57 w->pending_padding = 0;
58 reftable_free(zeroed);
61 w->pending_padding = padding;
62 n = w->write(w->write_arg, data, len);
63 if (n < 0)
64 return n;
65 n += padding;
66 return 0;
69 static void options_set_defaults(struct reftable_write_options *opts)
71 if (opts->restart_interval == 0) {
72 opts->restart_interval = 16;
75 if (opts->hash_id == 0) {
76 opts->hash_id = GIT_SHA1_FORMAT_ID;
78 if (opts->block_size == 0) {
79 opts->block_size = DEFAULT_BLOCK_SIZE;
83 static int writer_version(struct reftable_writer *w)
85 return (w->opts.hash_id == 0 || w->opts.hash_id == GIT_SHA1_FORMAT_ID) ?
86 1 :
90 static int writer_write_header(struct reftable_writer *w, uint8_t *dest)
92 memcpy(dest, "REFT", 4);
94 dest[4] = writer_version(w);
96 put_be24(dest + 5, w->opts.block_size);
97 put_be64(dest + 8, w->min_update_index);
98 put_be64(dest + 16, w->max_update_index);
99 if (writer_version(w) == 2) {
100 put_be32(dest + 24, w->opts.hash_id);
102 return header_size(writer_version(w));
105 static void writer_reinit_block_writer(struct reftable_writer *w, uint8_t typ)
107 int block_start = 0;
108 if (w->next == 0) {
109 block_start = header_size(writer_version(w));
112 strbuf_reset(&w->last_key);
113 block_writer_init(&w->block_writer_data, typ, w->block,
114 w->opts.block_size, block_start,
115 hash_size(w->opts.hash_id));
116 w->block_writer = &w->block_writer_data;
117 w->block_writer->restart_interval = w->opts.restart_interval;
120 static struct strbuf reftable_empty_strbuf = STRBUF_INIT;
122 struct reftable_writer *
123 reftable_new_writer(ssize_t (*writer_func)(void *, const void *, size_t),
124 int (*flush_func)(void *),
125 void *writer_arg, struct reftable_write_options *opts)
127 struct reftable_writer *wp = reftable_calloc(1, sizeof(*wp));
128 strbuf_init(&wp->block_writer_data.last_key, 0);
129 options_set_defaults(opts);
130 if (opts->block_size >= (1 << 24)) {
131 /* TODO - error return? */
132 abort();
134 wp->last_key = reftable_empty_strbuf;
135 REFTABLE_CALLOC_ARRAY(wp->block, opts->block_size);
136 wp->write = writer_func;
137 wp->write_arg = writer_arg;
138 wp->opts = *opts;
139 wp->flush = flush_func;
140 writer_reinit_block_writer(wp, BLOCK_TYPE_REF);
142 return wp;
145 void reftable_writer_set_limits(struct reftable_writer *w, uint64_t min,
146 uint64_t max)
148 w->min_update_index = min;
149 w->max_update_index = max;
152 static void writer_release(struct reftable_writer *w)
154 if (w) {
155 reftable_free(w->block);
156 w->block = NULL;
157 block_writer_release(&w->block_writer_data);
158 w->block_writer = NULL;
159 writer_clear_index(w);
160 strbuf_release(&w->last_key);
164 void reftable_writer_free(struct reftable_writer *w)
166 writer_release(w);
167 reftable_free(w);
170 struct obj_index_tree_node {
171 struct strbuf hash;
172 uint64_t *offsets;
173 size_t offset_len;
174 size_t offset_cap;
177 #define OBJ_INDEX_TREE_NODE_INIT \
179 .hash = STRBUF_INIT \
182 static int obj_index_tree_node_compare(const void *a, const void *b)
184 return strbuf_cmp(&((const struct obj_index_tree_node *)a)->hash,
185 &((const struct obj_index_tree_node *)b)->hash);
188 static void writer_index_hash(struct reftable_writer *w, struct strbuf *hash)
190 uint64_t off = w->next;
192 struct obj_index_tree_node want = { .hash = *hash };
194 struct tree_node *node = tree_search(&want, &w->obj_index_tree,
195 &obj_index_tree_node_compare, 0);
196 struct obj_index_tree_node *key = NULL;
197 if (!node) {
198 struct obj_index_tree_node empty = OBJ_INDEX_TREE_NODE_INIT;
199 key = reftable_malloc(sizeof(struct obj_index_tree_node));
200 *key = empty;
202 strbuf_reset(&key->hash);
203 strbuf_addbuf(&key->hash, hash);
204 tree_search((void *)key, &w->obj_index_tree,
205 &obj_index_tree_node_compare, 1);
206 } else {
207 key = node->key;
210 if (key->offset_len > 0 && key->offsets[key->offset_len - 1] == off) {
211 return;
214 REFTABLE_ALLOC_GROW(key->offsets, key->offset_len + 1, key->offset_cap);
215 key->offsets[key->offset_len++] = off;
218 static int writer_add_record(struct reftable_writer *w,
219 struct reftable_record *rec)
221 struct strbuf key = STRBUF_INIT;
222 int err;
224 reftable_record_key(rec, &key);
225 if (strbuf_cmp(&w->last_key, &key) >= 0) {
226 err = REFTABLE_API_ERROR;
227 goto done;
230 strbuf_reset(&w->last_key);
231 strbuf_addbuf(&w->last_key, &key);
232 if (!w->block_writer)
233 writer_reinit_block_writer(w, reftable_record_type(rec));
235 if (block_writer_type(w->block_writer) != reftable_record_type(rec))
236 BUG("record of type %d added to writer of type %d",
237 reftable_record_type(rec), block_writer_type(w->block_writer));
240 * Try to add the record to the writer. If this succeeds then we're
241 * done. Otherwise the block writer may have hit the block size limit
242 * and needs to be flushed.
244 if (!block_writer_add(w->block_writer, rec)) {
245 err = 0;
246 goto done;
250 * The current block is full, so we need to flush and reinitialize the
251 * writer to start writing the next block.
253 err = writer_flush_block(w);
254 if (err < 0)
255 goto done;
256 writer_reinit_block_writer(w, reftable_record_type(rec));
259 * Try to add the record to the writer again. If this still fails then
260 * the record does not fit into the block size.
262 * TODO: it would be great to have `block_writer_add()` return proper
263 * error codes so that we don't have to second-guess the failure
264 * mode here.
266 err = block_writer_add(w->block_writer, rec);
267 if (err) {
268 err = REFTABLE_ENTRY_TOO_BIG_ERROR;
269 goto done;
272 done:
273 strbuf_release(&key);
274 return err;
277 int reftable_writer_add_ref(struct reftable_writer *w,
278 struct reftable_ref_record *ref)
280 struct reftable_record rec = {
281 .type = BLOCK_TYPE_REF,
282 .u = {
283 .ref = *ref
286 int err = 0;
288 if (!ref->refname)
289 return REFTABLE_API_ERROR;
290 if (ref->update_index < w->min_update_index ||
291 ref->update_index > w->max_update_index)
292 return REFTABLE_API_ERROR;
294 rec.u.ref.update_index -= w->min_update_index;
296 err = writer_add_record(w, &rec);
297 if (err < 0)
298 return err;
300 if (!w->opts.skip_index_objects && reftable_ref_record_val1(ref)) {
301 struct strbuf h = STRBUF_INIT;
302 strbuf_add(&h, (char *)reftable_ref_record_val1(ref),
303 hash_size(w->opts.hash_id));
304 writer_index_hash(w, &h);
305 strbuf_release(&h);
308 if (!w->opts.skip_index_objects && reftable_ref_record_val2(ref)) {
309 struct strbuf h = STRBUF_INIT;
310 strbuf_add(&h, reftable_ref_record_val2(ref),
311 hash_size(w->opts.hash_id));
312 writer_index_hash(w, &h);
313 strbuf_release(&h);
315 return 0;
318 int reftable_writer_add_refs(struct reftable_writer *w,
319 struct reftable_ref_record *refs, int n)
321 int err = 0;
322 int i = 0;
323 QSORT(refs, n, reftable_ref_record_compare_name);
324 for (i = 0; err == 0 && i < n; i++) {
325 err = reftable_writer_add_ref(w, &refs[i]);
327 return err;
330 static int reftable_writer_add_log_verbatim(struct reftable_writer *w,
331 struct reftable_log_record *log)
333 struct reftable_record rec = {
334 .type = BLOCK_TYPE_LOG,
335 .u = {
336 .log = *log,
339 if (w->block_writer &&
340 block_writer_type(w->block_writer) == BLOCK_TYPE_REF) {
341 int err = writer_finish_public_section(w);
342 if (err < 0)
343 return err;
346 w->next -= w->pending_padding;
347 w->pending_padding = 0;
348 return writer_add_record(w, &rec);
351 int reftable_writer_add_log(struct reftable_writer *w,
352 struct reftable_log_record *log)
354 char *input_log_message = NULL;
355 struct strbuf cleaned_message = STRBUF_INIT;
356 int err = 0;
358 if (log->value_type == REFTABLE_LOG_DELETION)
359 return reftable_writer_add_log_verbatim(w, log);
361 if (!log->refname)
362 return REFTABLE_API_ERROR;
364 input_log_message = log->value.update.message;
365 if (!w->opts.exact_log_message && log->value.update.message) {
366 strbuf_addstr(&cleaned_message, log->value.update.message);
367 while (cleaned_message.len &&
368 cleaned_message.buf[cleaned_message.len - 1] == '\n')
369 strbuf_setlen(&cleaned_message,
370 cleaned_message.len - 1);
371 if (strchr(cleaned_message.buf, '\n')) {
372 /* multiple lines not allowed. */
373 err = REFTABLE_API_ERROR;
374 goto done;
376 strbuf_addstr(&cleaned_message, "\n");
377 log->value.update.message = cleaned_message.buf;
380 err = reftable_writer_add_log_verbatim(w, log);
381 log->value.update.message = input_log_message;
382 done:
383 strbuf_release(&cleaned_message);
384 return err;
387 int reftable_writer_add_logs(struct reftable_writer *w,
388 struct reftable_log_record *logs, int n)
390 int err = 0;
391 int i = 0;
392 QSORT(logs, n, reftable_log_record_compare_key);
394 for (i = 0; err == 0 && i < n; i++) {
395 err = reftable_writer_add_log(w, &logs[i]);
397 return err;
400 static int writer_finish_section(struct reftable_writer *w)
402 struct reftable_block_stats *bstats = NULL;
403 uint8_t typ = block_writer_type(w->block_writer);
404 uint64_t index_start = 0;
405 int max_level = 0;
406 size_t threshold = w->opts.unpadded ? 1 : 3;
407 int before_blocks = w->stats.idx_stats.blocks;
408 int err;
410 err = writer_flush_block(w);
411 if (err < 0)
412 return err;
415 * When the section we are about to index has a lot of blocks then the
416 * index itself may span across multiple blocks, as well. This would
417 * require a linear scan over index blocks only to find the desired
418 * indexed block, which is inefficient. Instead, we write a multi-level
419 * index where index records of level N+1 will refer to index blocks of
420 * level N. This isn't constant time, either, but at least logarithmic.
422 * This loop handles writing this multi-level index. Note that we write
423 * the lowest-level index pointing to the indexed blocks first. We then
424 * continue writing additional index levels until the current level has
425 * less blocks than the threshold so that the highest level will be at
426 * the end of the index section.
428 * Readers are thus required to start reading the index section from
429 * its end, which is why we set `index_start` to the beginning of the
430 * last index section.
432 while (w->index_len > threshold) {
433 struct reftable_index_record *idx = NULL;
434 size_t i, idx_len;
436 max_level++;
437 index_start = w->next;
438 writer_reinit_block_writer(w, BLOCK_TYPE_INDEX);
440 idx = w->index;
441 idx_len = w->index_len;
443 w->index = NULL;
444 w->index_len = 0;
445 w->index_cap = 0;
446 for (i = 0; i < idx_len; i++) {
447 struct reftable_record rec = {
448 .type = BLOCK_TYPE_INDEX,
449 .u = {
450 .idx = idx[i],
454 err = writer_add_record(w, &rec);
455 if (err < 0)
456 return err;
459 err = writer_flush_block(w);
460 if (err < 0)
461 return err;
463 for (i = 0; i < idx_len; i++)
464 strbuf_release(&idx[i].last_key);
465 reftable_free(idx);
469 * The index may still contain a number of index blocks lower than the
470 * threshold. Clear it so that these entries don't leak into the next
471 * index section.
473 writer_clear_index(w);
475 bstats = writer_reftable_block_stats(w, typ);
476 bstats->index_blocks = w->stats.idx_stats.blocks - before_blocks;
477 bstats->index_offset = index_start;
478 bstats->max_index_level = max_level;
480 /* Reinit lastKey, as the next section can start with any key. */
481 strbuf_reset(&w->last_key);
483 return 0;
486 struct common_prefix_arg {
487 struct strbuf *last;
488 int max;
491 static void update_common(void *void_arg, void *key)
493 struct common_prefix_arg *arg = void_arg;
494 struct obj_index_tree_node *entry = key;
495 if (arg->last) {
496 int n = common_prefix_size(&entry->hash, arg->last);
497 if (n > arg->max) {
498 arg->max = n;
501 arg->last = &entry->hash;
504 struct write_record_arg {
505 struct reftable_writer *w;
506 int err;
509 static void write_object_record(void *void_arg, void *key)
511 struct write_record_arg *arg = void_arg;
512 struct obj_index_tree_node *entry = key;
513 struct reftable_record
514 rec = { .type = BLOCK_TYPE_OBJ,
515 .u.obj = {
516 .hash_prefix = (uint8_t *)entry->hash.buf,
517 .hash_prefix_len = arg->w->stats.object_id_len,
518 .offsets = entry->offsets,
519 .offset_len = entry->offset_len,
520 } };
521 if (arg->err < 0)
522 goto done;
524 arg->err = block_writer_add(arg->w->block_writer, &rec);
525 if (arg->err == 0)
526 goto done;
528 arg->err = writer_flush_block(arg->w);
529 if (arg->err < 0)
530 goto done;
532 writer_reinit_block_writer(arg->w, BLOCK_TYPE_OBJ);
533 arg->err = block_writer_add(arg->w->block_writer, &rec);
534 if (arg->err == 0)
535 goto done;
537 rec.u.obj.offset_len = 0;
538 arg->err = block_writer_add(arg->w->block_writer, &rec);
540 /* Should be able to write into a fresh block. */
541 assert(arg->err == 0);
543 done:;
546 static void object_record_free(void *void_arg, void *key)
548 struct obj_index_tree_node *entry = key;
550 FREE_AND_NULL(entry->offsets);
551 strbuf_release(&entry->hash);
552 reftable_free(entry);
555 static int writer_dump_object_index(struct reftable_writer *w)
557 struct write_record_arg closure = { .w = w };
558 struct common_prefix_arg common = {
559 .max = 1, /* obj_id_len should be >= 2. */
561 if (w->obj_index_tree) {
562 infix_walk(w->obj_index_tree, &update_common, &common);
564 w->stats.object_id_len = common.max + 1;
566 writer_reinit_block_writer(w, BLOCK_TYPE_OBJ);
568 if (w->obj_index_tree) {
569 infix_walk(w->obj_index_tree, &write_object_record, &closure);
572 if (closure.err < 0)
573 return closure.err;
574 return writer_finish_section(w);
577 static int writer_finish_public_section(struct reftable_writer *w)
579 uint8_t typ = 0;
580 int err = 0;
582 if (!w->block_writer)
583 return 0;
585 typ = block_writer_type(w->block_writer);
586 err = writer_finish_section(w);
587 if (err < 0)
588 return err;
589 if (typ == BLOCK_TYPE_REF && !w->opts.skip_index_objects &&
590 w->stats.ref_stats.index_blocks > 0) {
591 err = writer_dump_object_index(w);
592 if (err < 0)
593 return err;
596 if (w->obj_index_tree) {
597 infix_walk(w->obj_index_tree, &object_record_free, NULL);
598 tree_free(w->obj_index_tree);
599 w->obj_index_tree = NULL;
602 w->block_writer = NULL;
603 return 0;
606 int reftable_writer_close(struct reftable_writer *w)
608 uint8_t footer[72];
609 uint8_t *p = footer;
610 int err = writer_finish_public_section(w);
611 int empty_table = w->next == 0;
612 if (err != 0)
613 goto done;
614 w->pending_padding = 0;
615 if (empty_table) {
616 /* Empty tables need a header anyway. */
617 uint8_t header[28];
618 int n = writer_write_header(w, header);
619 err = padded_write(w, header, n, 0);
620 if (err < 0)
621 goto done;
624 p += writer_write_header(w, footer);
625 put_be64(p, w->stats.ref_stats.index_offset);
626 p += 8;
627 put_be64(p, (w->stats.obj_stats.offset) << 5 | w->stats.object_id_len);
628 p += 8;
629 put_be64(p, w->stats.obj_stats.index_offset);
630 p += 8;
632 put_be64(p, w->stats.log_stats.offset);
633 p += 8;
634 put_be64(p, w->stats.log_stats.index_offset);
635 p += 8;
637 put_be32(p, crc32(0, footer, p - footer));
638 p += 4;
640 err = w->flush(w->write_arg);
641 if (err < 0) {
642 err = REFTABLE_IO_ERROR;
643 goto done;
646 err = padded_write(w, footer, footer_size(writer_version(w)), 0);
647 if (err < 0)
648 goto done;
650 if (empty_table) {
651 err = REFTABLE_EMPTY_TABLE_ERROR;
652 goto done;
655 done:
656 writer_release(w);
657 return err;
660 static void writer_clear_index(struct reftable_writer *w)
662 for (size_t i = 0; w->index && i < w->index_len; i++)
663 strbuf_release(&w->index[i].last_key);
664 FREE_AND_NULL(w->index);
665 w->index_len = 0;
666 w->index_cap = 0;
669 static int writer_flush_nonempty_block(struct reftable_writer *w)
671 struct reftable_index_record index_record = {
672 .last_key = STRBUF_INIT,
674 uint8_t typ = block_writer_type(w->block_writer);
675 struct reftable_block_stats *bstats;
676 int raw_bytes, padding = 0, err;
677 uint64_t block_typ_off;
680 * Finish the current block. This will cause the block writer to emit
681 * restart points and potentially compress records in case we are
682 * writing a log block.
684 * Note that this is still happening in memory.
686 raw_bytes = block_writer_finish(w->block_writer);
687 if (raw_bytes < 0)
688 return raw_bytes;
691 * By default, all records except for log records are padded to the
692 * block size.
694 if (!w->opts.unpadded && typ != BLOCK_TYPE_LOG)
695 padding = w->opts.block_size - raw_bytes;
697 bstats = writer_reftable_block_stats(w, typ);
698 block_typ_off = (bstats->blocks == 0) ? w->next : 0;
699 if (block_typ_off > 0)
700 bstats->offset = block_typ_off;
701 bstats->entries += w->block_writer->entries;
702 bstats->restarts += w->block_writer->restart_len;
703 bstats->blocks++;
704 w->stats.blocks++;
707 * If this is the first block we're writing to the table then we need
708 * to also write the reftable header.
710 if (!w->next)
711 writer_write_header(w, w->block);
713 err = padded_write(w, w->block, raw_bytes, padding);
714 if (err < 0)
715 return err;
718 * Add an index record for every block that we're writing. If we end up
719 * having more than a threshold of index records we will end up writing
720 * an index section in `writer_finish_section()`. Each index record
721 * contains the last record key of the block it is indexing as well as
722 * the offset of that block.
724 * Note that this also applies when flushing index blocks, in which
725 * case we will end up with a multi-level index.
727 REFTABLE_ALLOC_GROW(w->index, w->index_len + 1, w->index_cap);
728 index_record.offset = w->next;
729 strbuf_reset(&index_record.last_key);
730 strbuf_addbuf(&index_record.last_key, &w->block_writer->last_key);
731 w->index[w->index_len] = index_record;
732 w->index_len++;
734 w->next += padding + raw_bytes;
735 w->block_writer = NULL;
737 return 0;
740 static int writer_flush_block(struct reftable_writer *w)
742 if (!w->block_writer)
743 return 0;
744 if (w->block_writer->entries == 0)
745 return 0;
746 return writer_flush_nonempty_block(w);
749 const struct reftable_stats *reftable_writer_stats(struct reftable_writer *w)
751 return &w->stats;