reftable/writer: refactorings for `writer_add_record()`
[alt-git.git] / reftable / writer.c
blob0ad5eb8887ecca7b72ca47a1aa5e952cffaf9b15
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_release(&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 void reftable_writer_free(struct reftable_writer *w)
154 if (!w)
155 return;
156 reftable_free(w->block);
157 reftable_free(w);
160 struct obj_index_tree_node {
161 struct strbuf hash;
162 uint64_t *offsets;
163 size_t offset_len;
164 size_t offset_cap;
167 #define OBJ_INDEX_TREE_NODE_INIT \
169 .hash = STRBUF_INIT \
172 static int obj_index_tree_node_compare(const void *a, const void *b)
174 return strbuf_cmp(&((const struct obj_index_tree_node *)a)->hash,
175 &((const struct obj_index_tree_node *)b)->hash);
178 static void writer_index_hash(struct reftable_writer *w, struct strbuf *hash)
180 uint64_t off = w->next;
182 struct obj_index_tree_node want = { .hash = *hash };
184 struct tree_node *node = tree_search(&want, &w->obj_index_tree,
185 &obj_index_tree_node_compare, 0);
186 struct obj_index_tree_node *key = NULL;
187 if (!node) {
188 struct obj_index_tree_node empty = OBJ_INDEX_TREE_NODE_INIT;
189 key = reftable_malloc(sizeof(struct obj_index_tree_node));
190 *key = empty;
192 strbuf_reset(&key->hash);
193 strbuf_addbuf(&key->hash, hash);
194 tree_search((void *)key, &w->obj_index_tree,
195 &obj_index_tree_node_compare, 1);
196 } else {
197 key = node->key;
200 if (key->offset_len > 0 && key->offsets[key->offset_len - 1] == off) {
201 return;
204 REFTABLE_ALLOC_GROW(key->offsets, key->offset_len + 1, key->offset_cap);
205 key->offsets[key->offset_len++] = off;
208 static int writer_add_record(struct reftable_writer *w,
209 struct reftable_record *rec)
211 struct strbuf key = STRBUF_INIT;
212 int err;
214 reftable_record_key(rec, &key);
215 if (strbuf_cmp(&w->last_key, &key) >= 0) {
216 err = REFTABLE_API_ERROR;
217 goto done;
220 strbuf_reset(&w->last_key);
221 strbuf_addbuf(&w->last_key, &key);
222 if (!w->block_writer)
223 writer_reinit_block_writer(w, reftable_record_type(rec));
225 if (block_writer_type(w->block_writer) != reftable_record_type(rec))
226 BUG("record of type %d added to writer of type %d",
227 reftable_record_type(rec), block_writer_type(w->block_writer));
230 * Try to add the record to the writer. If this succeeds then we're
231 * done. Otherwise the block writer may have hit the block size limit
232 * and needs to be flushed.
234 if (!block_writer_add(w->block_writer, rec)) {
235 err = 0;
236 goto done;
240 * The current block is full, so we need to flush and reinitialize the
241 * writer to start writing the next block.
243 err = writer_flush_block(w);
244 if (err < 0)
245 goto done;
246 writer_reinit_block_writer(w, reftable_record_type(rec));
249 * Try to add the record to the writer again. If this still fails then
250 * the record does not fit into the block size.
252 * TODO: it would be great to have `block_writer_add()` return proper
253 * error codes so that we don't have to second-guess the failure
254 * mode here.
256 err = block_writer_add(w->block_writer, rec);
257 if (err) {
258 err = REFTABLE_ENTRY_TOO_BIG_ERROR;
259 goto done;
262 done:
263 strbuf_release(&key);
264 return err;
267 int reftable_writer_add_ref(struct reftable_writer *w,
268 struct reftable_ref_record *ref)
270 struct reftable_record rec = {
271 .type = BLOCK_TYPE_REF,
272 .u = {
273 .ref = *ref
276 int err = 0;
278 if (!ref->refname)
279 return REFTABLE_API_ERROR;
280 if (ref->update_index < w->min_update_index ||
281 ref->update_index > w->max_update_index)
282 return REFTABLE_API_ERROR;
284 rec.u.ref.update_index -= w->min_update_index;
286 err = writer_add_record(w, &rec);
287 if (err < 0)
288 return err;
290 if (!w->opts.skip_index_objects && reftable_ref_record_val1(ref)) {
291 struct strbuf h = STRBUF_INIT;
292 strbuf_add(&h, (char *)reftable_ref_record_val1(ref),
293 hash_size(w->opts.hash_id));
294 writer_index_hash(w, &h);
295 strbuf_release(&h);
298 if (!w->opts.skip_index_objects && reftable_ref_record_val2(ref)) {
299 struct strbuf h = STRBUF_INIT;
300 strbuf_add(&h, reftable_ref_record_val2(ref),
301 hash_size(w->opts.hash_id));
302 writer_index_hash(w, &h);
303 strbuf_release(&h);
305 return 0;
308 int reftable_writer_add_refs(struct reftable_writer *w,
309 struct reftable_ref_record *refs, int n)
311 int err = 0;
312 int i = 0;
313 QSORT(refs, n, reftable_ref_record_compare_name);
314 for (i = 0; err == 0 && i < n; i++) {
315 err = reftable_writer_add_ref(w, &refs[i]);
317 return err;
320 static int reftable_writer_add_log_verbatim(struct reftable_writer *w,
321 struct reftable_log_record *log)
323 struct reftable_record rec = {
324 .type = BLOCK_TYPE_LOG,
325 .u = {
326 .log = *log,
329 if (w->block_writer &&
330 block_writer_type(w->block_writer) == BLOCK_TYPE_REF) {
331 int err = writer_finish_public_section(w);
332 if (err < 0)
333 return err;
336 w->next -= w->pending_padding;
337 w->pending_padding = 0;
338 return writer_add_record(w, &rec);
341 int reftable_writer_add_log(struct reftable_writer *w,
342 struct reftable_log_record *log)
344 char *input_log_message = NULL;
345 struct strbuf cleaned_message = STRBUF_INIT;
346 int err = 0;
348 if (log->value_type == REFTABLE_LOG_DELETION)
349 return reftable_writer_add_log_verbatim(w, log);
351 if (!log->refname)
352 return REFTABLE_API_ERROR;
354 input_log_message = log->value.update.message;
355 if (!w->opts.exact_log_message && log->value.update.message) {
356 strbuf_addstr(&cleaned_message, log->value.update.message);
357 while (cleaned_message.len &&
358 cleaned_message.buf[cleaned_message.len - 1] == '\n')
359 strbuf_setlen(&cleaned_message,
360 cleaned_message.len - 1);
361 if (strchr(cleaned_message.buf, '\n')) {
362 /* multiple lines not allowed. */
363 err = REFTABLE_API_ERROR;
364 goto done;
366 strbuf_addstr(&cleaned_message, "\n");
367 log->value.update.message = cleaned_message.buf;
370 err = reftable_writer_add_log_verbatim(w, log);
371 log->value.update.message = input_log_message;
372 done:
373 strbuf_release(&cleaned_message);
374 return err;
377 int reftable_writer_add_logs(struct reftable_writer *w,
378 struct reftable_log_record *logs, int n)
380 int err = 0;
381 int i = 0;
382 QSORT(logs, n, reftable_log_record_compare_key);
384 for (i = 0; err == 0 && i < n; i++) {
385 err = reftable_writer_add_log(w, &logs[i]);
387 return err;
390 static int writer_finish_section(struct reftable_writer *w)
392 struct reftable_block_stats *bstats = NULL;
393 uint8_t typ = block_writer_type(w->block_writer);
394 uint64_t index_start = 0;
395 int max_level = 0;
396 size_t threshold = w->opts.unpadded ? 1 : 3;
397 int before_blocks = w->stats.idx_stats.blocks;
398 int err;
400 err = writer_flush_block(w);
401 if (err < 0)
402 return err;
405 * When the section we are about to index has a lot of blocks then the
406 * index itself may span across multiple blocks, as well. This would
407 * require a linear scan over index blocks only to find the desired
408 * indexed block, which is inefficient. Instead, we write a multi-level
409 * index where index records of level N+1 will refer to index blocks of
410 * level N. This isn't constant time, either, but at least logarithmic.
412 * This loop handles writing this multi-level index. Note that we write
413 * the lowest-level index pointing to the indexed blocks first. We then
414 * continue writing additional index levels until the current level has
415 * less blocks than the threshold so that the highest level will be at
416 * the end of the index section.
418 * Readers are thus required to start reading the index section from
419 * its end, which is why we set `index_start` to the beginning of the
420 * last index section.
422 while (w->index_len > threshold) {
423 struct reftable_index_record *idx = NULL;
424 size_t i, idx_len;
426 max_level++;
427 index_start = w->next;
428 writer_reinit_block_writer(w, BLOCK_TYPE_INDEX);
430 idx = w->index;
431 idx_len = w->index_len;
433 w->index = NULL;
434 w->index_len = 0;
435 w->index_cap = 0;
436 for (i = 0; i < idx_len; i++) {
437 struct reftable_record rec = {
438 .type = BLOCK_TYPE_INDEX,
439 .u = {
440 .idx = idx[i],
444 err = writer_add_record(w, &rec);
445 if (err < 0)
446 return err;
449 err = writer_flush_block(w);
450 if (err < 0)
451 return err;
453 for (i = 0; i < idx_len; i++)
454 strbuf_release(&idx[i].last_key);
455 reftable_free(idx);
459 * The index may still contain a number of index blocks lower than the
460 * threshold. Clear it so that these entries don't leak into the next
461 * index section.
463 writer_clear_index(w);
465 bstats = writer_reftable_block_stats(w, typ);
466 bstats->index_blocks = w->stats.idx_stats.blocks - before_blocks;
467 bstats->index_offset = index_start;
468 bstats->max_index_level = max_level;
470 /* Reinit lastKey, as the next section can start with any key. */
471 w->last_key.len = 0;
473 return 0;
476 struct common_prefix_arg {
477 struct strbuf *last;
478 int max;
481 static void update_common(void *void_arg, void *key)
483 struct common_prefix_arg *arg = void_arg;
484 struct obj_index_tree_node *entry = key;
485 if (arg->last) {
486 int n = common_prefix_size(&entry->hash, arg->last);
487 if (n > arg->max) {
488 arg->max = n;
491 arg->last = &entry->hash;
494 struct write_record_arg {
495 struct reftable_writer *w;
496 int err;
499 static void write_object_record(void *void_arg, void *key)
501 struct write_record_arg *arg = void_arg;
502 struct obj_index_tree_node *entry = key;
503 struct reftable_record
504 rec = { .type = BLOCK_TYPE_OBJ,
505 .u.obj = {
506 .hash_prefix = (uint8_t *)entry->hash.buf,
507 .hash_prefix_len = arg->w->stats.object_id_len,
508 .offsets = entry->offsets,
509 .offset_len = entry->offset_len,
510 } };
511 if (arg->err < 0)
512 goto done;
514 arg->err = block_writer_add(arg->w->block_writer, &rec);
515 if (arg->err == 0)
516 goto done;
518 arg->err = writer_flush_block(arg->w);
519 if (arg->err < 0)
520 goto done;
522 writer_reinit_block_writer(arg->w, BLOCK_TYPE_OBJ);
523 arg->err = block_writer_add(arg->w->block_writer, &rec);
524 if (arg->err == 0)
525 goto done;
527 rec.u.obj.offset_len = 0;
528 arg->err = block_writer_add(arg->w->block_writer, &rec);
530 /* Should be able to write into a fresh block. */
531 assert(arg->err == 0);
533 done:;
536 static void object_record_free(void *void_arg, void *key)
538 struct obj_index_tree_node *entry = key;
540 FREE_AND_NULL(entry->offsets);
541 strbuf_release(&entry->hash);
542 reftable_free(entry);
545 static int writer_dump_object_index(struct reftable_writer *w)
547 struct write_record_arg closure = { .w = w };
548 struct common_prefix_arg common = {
549 .max = 1, /* obj_id_len should be >= 2. */
551 if (w->obj_index_tree) {
552 infix_walk(w->obj_index_tree, &update_common, &common);
554 w->stats.object_id_len = common.max + 1;
556 writer_reinit_block_writer(w, BLOCK_TYPE_OBJ);
558 if (w->obj_index_tree) {
559 infix_walk(w->obj_index_tree, &write_object_record, &closure);
562 if (closure.err < 0)
563 return closure.err;
564 return writer_finish_section(w);
567 static int writer_finish_public_section(struct reftable_writer *w)
569 uint8_t typ = 0;
570 int err = 0;
572 if (!w->block_writer)
573 return 0;
575 typ = block_writer_type(w->block_writer);
576 err = writer_finish_section(w);
577 if (err < 0)
578 return err;
579 if (typ == BLOCK_TYPE_REF && !w->opts.skip_index_objects &&
580 w->stats.ref_stats.index_blocks > 0) {
581 err = writer_dump_object_index(w);
582 if (err < 0)
583 return err;
586 if (w->obj_index_tree) {
587 infix_walk(w->obj_index_tree, &object_record_free, NULL);
588 tree_free(w->obj_index_tree);
589 w->obj_index_tree = NULL;
592 w->block_writer = NULL;
593 return 0;
596 int reftable_writer_close(struct reftable_writer *w)
598 uint8_t footer[72];
599 uint8_t *p = footer;
600 int err = writer_finish_public_section(w);
601 int empty_table = w->next == 0;
602 if (err != 0)
603 goto done;
604 w->pending_padding = 0;
605 if (empty_table) {
606 /* Empty tables need a header anyway. */
607 uint8_t header[28];
608 int n = writer_write_header(w, header);
609 err = padded_write(w, header, n, 0);
610 if (err < 0)
611 goto done;
614 p += writer_write_header(w, footer);
615 put_be64(p, w->stats.ref_stats.index_offset);
616 p += 8;
617 put_be64(p, (w->stats.obj_stats.offset) << 5 | w->stats.object_id_len);
618 p += 8;
619 put_be64(p, w->stats.obj_stats.index_offset);
620 p += 8;
622 put_be64(p, w->stats.log_stats.offset);
623 p += 8;
624 put_be64(p, w->stats.log_stats.index_offset);
625 p += 8;
627 put_be32(p, crc32(0, footer, p - footer));
628 p += 4;
630 err = w->flush(w->write_arg);
631 if (err < 0) {
632 err = REFTABLE_IO_ERROR;
633 goto done;
636 err = padded_write(w, footer, footer_size(writer_version(w)), 0);
637 if (err < 0)
638 goto done;
640 if (empty_table) {
641 err = REFTABLE_EMPTY_TABLE_ERROR;
642 goto done;
645 done:
646 /* free up memory. */
647 block_writer_release(&w->block_writer_data);
648 writer_clear_index(w);
649 strbuf_release(&w->last_key);
650 return err;
653 static void writer_clear_index(struct reftable_writer *w)
655 for (size_t i = 0; i < w->index_len; i++)
656 strbuf_release(&w->index[i].last_key);
657 FREE_AND_NULL(w->index);
658 w->index_len = 0;
659 w->index_cap = 0;
662 static const int debug = 0;
664 static int writer_flush_nonempty_block(struct reftable_writer *w)
666 uint8_t typ = block_writer_type(w->block_writer);
667 struct reftable_block_stats *bstats =
668 writer_reftable_block_stats(w, typ);
669 uint64_t block_typ_off = (bstats->blocks == 0) ? w->next : 0;
670 int raw_bytes = block_writer_finish(w->block_writer);
671 int padding = 0;
672 int err = 0;
673 struct reftable_index_record ir = { .last_key = STRBUF_INIT };
674 if (raw_bytes < 0)
675 return raw_bytes;
677 if (!w->opts.unpadded && typ != BLOCK_TYPE_LOG) {
678 padding = w->opts.block_size - raw_bytes;
681 if (block_typ_off > 0) {
682 bstats->offset = block_typ_off;
685 bstats->entries += w->block_writer->entries;
686 bstats->restarts += w->block_writer->restart_len;
687 bstats->blocks++;
688 w->stats.blocks++;
690 if (debug) {
691 fprintf(stderr, "block %c off %" PRIu64 " sz %d (%d)\n", typ,
692 w->next, raw_bytes,
693 get_be24(w->block + w->block_writer->header_off + 1));
696 if (w->next == 0) {
697 writer_write_header(w, w->block);
700 err = padded_write(w, w->block, raw_bytes, padding);
701 if (err < 0)
702 return err;
704 REFTABLE_ALLOC_GROW(w->index, w->index_len + 1, w->index_cap);
706 ir.offset = w->next;
707 strbuf_reset(&ir.last_key);
708 strbuf_addbuf(&ir.last_key, &w->block_writer->last_key);
709 w->index[w->index_len] = ir;
711 w->index_len++;
712 w->next += padding + raw_bytes;
713 w->block_writer = NULL;
714 return 0;
717 static int writer_flush_block(struct reftable_writer *w)
719 if (!w->block_writer)
720 return 0;
721 if (w->block_writer->entries == 0)
722 return 0;
723 return writer_flush_nonempty_block(w);
726 const struct reftable_stats *reftable_writer_stats(struct reftable_writer *w)
728 return &w->stats;