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
14 #include "constants.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
)
33 return &w
->stats
.ref_stats
;
35 return &w
->stats
.obj_stats
;
37 return &w
->stats
.idx_stats
;
39 return &w
->stats
.log_stats
;
45 /* write data, queuing the padding for the next write. Returns negative for
47 static int padded_write(struct reftable_writer
*w
, uint8_t *data
, size_t len
,
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
);
57 w
->pending_padding
= 0;
58 reftable_free(zeroed
);
61 w
->pending_padding
= padding
;
62 n
= w
->write(w
->write_arg
, data
, len
);
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
) ?
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
)
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? */
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
;
139 wp
->flush
= flush_func
;
140 writer_reinit_block_writer(wp
, BLOCK_TYPE_REF
);
145 void reftable_writer_set_limits(struct reftable_writer
*w
, uint64_t min
,
148 w
->min_update_index
= min
;
149 w
->max_update_index
= max
;
152 static void writer_release(struct reftable_writer
*w
)
155 reftable_free(w
->block
);
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
)
170 struct obj_index_tree_node
{
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
;
198 struct obj_index_tree_node empty
= OBJ_INDEX_TREE_NODE_INIT
;
199 key
= reftable_malloc(sizeof(struct obj_index_tree_node
));
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);
210 if (key
->offset_len
> 0 && key
->offsets
[key
->offset_len
- 1] == off
) {
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
;
224 reftable_record_key(rec
, &key
);
225 if (strbuf_cmp(&w
->last_key
, &key
) >= 0) {
226 err
= REFTABLE_API_ERROR
;
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
)) {
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
);
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
266 err
= block_writer_add(w
->block_writer
, rec
);
268 err
= REFTABLE_ENTRY_TOO_BIG_ERROR
;
273 strbuf_release(&key
);
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
,
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
);
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
);
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
);
318 int reftable_writer_add_refs(struct reftable_writer
*w
,
319 struct reftable_ref_record
*refs
, int n
)
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
]);
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
,
339 if (w
->block_writer
&&
340 block_writer_type(w
->block_writer
) == BLOCK_TYPE_REF
) {
341 int err
= writer_finish_public_section(w
);
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
;
358 if (log
->value_type
== REFTABLE_LOG_DELETION
)
359 return reftable_writer_add_log_verbatim(w
, log
);
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
;
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
;
383 strbuf_release(&cleaned_message
);
387 int reftable_writer_add_logs(struct reftable_writer
*w
,
388 struct reftable_log_record
*logs
, int n
)
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
]);
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;
406 size_t threshold
= w
->opts
.unpadded
? 1 : 3;
407 int before_blocks
= w
->stats
.idx_stats
.blocks
;
410 err
= writer_flush_block(w
);
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
;
437 index_start
= w
->next
;
438 writer_reinit_block_writer(w
, BLOCK_TYPE_INDEX
);
441 idx_len
= w
->index_len
;
446 for (i
= 0; i
< idx_len
; i
++) {
447 struct reftable_record rec
= {
448 .type
= BLOCK_TYPE_INDEX
,
454 err
= writer_add_record(w
, &rec
);
459 err
= writer_flush_block(w
);
463 for (i
= 0; i
< idx_len
; i
++)
464 strbuf_release(&idx
[i
].last_key
);
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
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
);
486 struct common_prefix_arg
{
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
;
496 int n
= common_prefix_size(&entry
->hash
, arg
->last
);
501 arg
->last
= &entry
->hash
;
504 struct write_record_arg
{
505 struct reftable_writer
*w
;
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
,
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
,
524 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
528 arg
->err
= writer_flush_block(arg
->w
);
532 writer_reinit_block_writer(arg
->w
, BLOCK_TYPE_OBJ
);
533 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
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);
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
);
574 return writer_finish_section(w
);
577 static int writer_finish_public_section(struct reftable_writer
*w
)
582 if (!w
->block_writer
)
585 typ
= block_writer_type(w
->block_writer
);
586 err
= writer_finish_section(w
);
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
);
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
;
606 int reftable_writer_close(struct reftable_writer
*w
)
610 int err
= writer_finish_public_section(w
);
611 int empty_table
= w
->next
== 0;
614 w
->pending_padding
= 0;
616 /* Empty tables need a header anyway. */
618 int n
= writer_write_header(w
, header
);
619 err
= padded_write(w
, header
, n
, 0);
624 p
+= writer_write_header(w
, footer
);
625 put_be64(p
, w
->stats
.ref_stats
.index_offset
);
627 put_be64(p
, (w
->stats
.obj_stats
.offset
) << 5 | w
->stats
.object_id_len
);
629 put_be64(p
, w
->stats
.obj_stats
.index_offset
);
632 put_be64(p
, w
->stats
.log_stats
.offset
);
634 put_be64(p
, w
->stats
.log_stats
.index_offset
);
637 put_be32(p
, crc32(0, footer
, p
- footer
));
640 err
= w
->flush(w
->write_arg
);
642 err
= REFTABLE_IO_ERROR
;
646 err
= padded_write(w
, footer
, footer_size(writer_version(w
)), 0);
651 err
= REFTABLE_EMPTY_TABLE_ERROR
;
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
);
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
);
691 * By default, all records except for log records are padded to the
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
;
707 * If this is the first block we're writing to the table then we need
708 * to also write the reftable header.
711 writer_write_header(w
, w
->block
);
713 err
= padded_write(w
, w
->block
, raw_bytes
, padding
);
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
;
734 w
->next
+= padding
+ raw_bytes
;
735 w
->block_writer
= NULL
;
740 static int writer_flush_block(struct reftable_writer
*w
)
742 if (!w
->block_writer
)
744 if (w
->block_writer
->entries
== 0)
746 return writer_flush_nonempty_block(w
);
749 const struct reftable_stats
*reftable_writer_stats(struct reftable_writer
*w
)