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
);
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_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 void *writer_arg
, struct reftable_write_options
*opts
)
126 struct reftable_writer
*wp
=
127 reftable_calloc(sizeof(struct reftable_writer
));
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 wp
->block
= reftable_calloc(opts
->block_size
);
136 wp
->write
= writer_func
;
137 wp
->write_arg
= writer_arg
;
139 writer_reinit_block_writer(wp
, BLOCK_TYPE_REF
);
144 void reftable_writer_set_limits(struct reftable_writer
*w
, uint64_t min
,
147 w
->min_update_index
= min
;
148 w
->max_update_index
= max
;
151 void reftable_writer_free(struct reftable_writer
*w
)
153 reftable_free(w
->block
);
157 struct obj_index_tree_node
{
164 #define OBJ_INDEX_TREE_NODE_INIT \
166 .hash = STRBUF_INIT \
169 static int obj_index_tree_node_compare(const void *a
, const void *b
)
171 return strbuf_cmp(&((const struct obj_index_tree_node
*)a
)->hash
,
172 &((const struct obj_index_tree_node
*)b
)->hash
);
175 static void writer_index_hash(struct reftable_writer
*w
, struct strbuf
*hash
)
177 uint64_t off
= w
->next
;
179 struct obj_index_tree_node want
= { .hash
= *hash
};
181 struct tree_node
*node
= tree_search(&want
, &w
->obj_index_tree
,
182 &obj_index_tree_node_compare
, 0);
183 struct obj_index_tree_node
*key
= NULL
;
185 struct obj_index_tree_node empty
= OBJ_INDEX_TREE_NODE_INIT
;
186 key
= reftable_malloc(sizeof(struct obj_index_tree_node
));
189 strbuf_reset(&key
->hash
);
190 strbuf_addbuf(&key
->hash
, hash
);
191 tree_search((void *)key
, &w
->obj_index_tree
,
192 &obj_index_tree_node_compare
, 1);
197 if (key
->offset_len
> 0 && key
->offsets
[key
->offset_len
- 1] == off
) {
201 if (key
->offset_len
== key
->offset_cap
) {
202 key
->offset_cap
= 2 * key
->offset_cap
+ 1;
203 key
->offsets
= reftable_realloc(
204 key
->offsets
, sizeof(uint64_t) * key
->offset_cap
);
207 key
->offsets
[key
->offset_len
++] = off
;
210 static int writer_add_record(struct reftable_writer
*w
,
211 struct reftable_record
*rec
)
213 struct strbuf key
= STRBUF_INIT
;
215 reftable_record_key(rec
, &key
);
216 if (strbuf_cmp(&w
->last_key
, &key
) >= 0) {
217 err
= REFTABLE_API_ERROR
;
221 strbuf_reset(&w
->last_key
);
222 strbuf_addbuf(&w
->last_key
, &key
);
223 if (w
->block_writer
== NULL
) {
224 writer_reinit_block_writer(w
, reftable_record_type(rec
));
227 assert(block_writer_type(w
->block_writer
) == reftable_record_type(rec
));
229 if (block_writer_add(w
->block_writer
, rec
) == 0) {
234 err
= writer_flush_block(w
);
239 writer_reinit_block_writer(w
, reftable_record_type(rec
));
240 err
= block_writer_add(w
->block_writer
, rec
);
242 /* we are writing into memory, so an error can only mean it
244 err
= REFTABLE_ENTRY_TOO_BIG_ERROR
;
250 strbuf_release(&key
);
254 int reftable_writer_add_ref(struct reftable_writer
*w
,
255 struct reftable_ref_record
*ref
)
257 struct reftable_record rec
= { NULL
};
258 struct reftable_ref_record copy
= *ref
;
261 if (ref
->refname
== NULL
)
262 return REFTABLE_API_ERROR
;
263 if (ref
->update_index
< w
->min_update_index
||
264 ref
->update_index
> w
->max_update_index
)
265 return REFTABLE_API_ERROR
;
267 reftable_record_from_ref(&rec
, ©
);
268 copy
.update_index
-= w
->min_update_index
;
270 err
= writer_add_record(w
, &rec
);
274 if (!w
->opts
.skip_index_objects
&& reftable_ref_record_val1(ref
)) {
275 struct strbuf h
= STRBUF_INIT
;
276 strbuf_add(&h
, (char *)reftable_ref_record_val1(ref
),
277 hash_size(w
->opts
.hash_id
));
278 writer_index_hash(w
, &h
);
282 if (!w
->opts
.skip_index_objects
&& reftable_ref_record_val2(ref
)) {
283 struct strbuf h
= STRBUF_INIT
;
284 strbuf_add(&h
, reftable_ref_record_val2(ref
),
285 hash_size(w
->opts
.hash_id
));
286 writer_index_hash(w
, &h
);
292 int reftable_writer_add_refs(struct reftable_writer
*w
,
293 struct reftable_ref_record
*refs
, int n
)
297 QSORT(refs
, n
, reftable_ref_record_compare_name
);
298 for (i
= 0; err
== 0 && i
< n
; i
++) {
299 err
= reftable_writer_add_ref(w
, &refs
[i
]);
304 static int reftable_writer_add_log_verbatim(struct reftable_writer
*w
,
305 struct reftable_log_record
*log
)
307 struct reftable_record rec
= { NULL
};
308 if (w
->block_writer
&&
309 block_writer_type(w
->block_writer
) == BLOCK_TYPE_REF
) {
310 int err
= writer_finish_public_section(w
);
315 w
->next
-= w
->pending_padding
;
316 w
->pending_padding
= 0;
318 reftable_record_from_log(&rec
, log
);
319 return writer_add_record(w
, &rec
);
322 int reftable_writer_add_log(struct reftable_writer
*w
,
323 struct reftable_log_record
*log
)
325 char *input_log_message
= NULL
;
326 struct strbuf cleaned_message
= STRBUF_INIT
;
329 if (log
->value_type
== REFTABLE_LOG_DELETION
)
330 return reftable_writer_add_log_verbatim(w
, log
);
332 if (log
->refname
== NULL
)
333 return REFTABLE_API_ERROR
;
335 input_log_message
= log
->value
.update
.message
;
336 if (!w
->opts
.exact_log_message
&& log
->value
.update
.message
) {
337 strbuf_addstr(&cleaned_message
, log
->value
.update
.message
);
338 while (cleaned_message
.len
&&
339 cleaned_message
.buf
[cleaned_message
.len
- 1] == '\n')
340 strbuf_setlen(&cleaned_message
,
341 cleaned_message
.len
- 1);
342 if (strchr(cleaned_message
.buf
, '\n')) {
343 /* multiple lines not allowed. */
344 err
= REFTABLE_API_ERROR
;
347 strbuf_addstr(&cleaned_message
, "\n");
348 log
->value
.update
.message
= cleaned_message
.buf
;
351 err
= reftable_writer_add_log_verbatim(w
, log
);
352 log
->value
.update
.message
= input_log_message
;
354 strbuf_release(&cleaned_message
);
358 int reftable_writer_add_logs(struct reftable_writer
*w
,
359 struct reftable_log_record
*logs
, int n
)
363 QSORT(logs
, n
, reftable_log_record_compare_key
);
365 for (i
= 0; err
== 0 && i
< n
; i
++) {
366 err
= reftable_writer_add_log(w
, &logs
[i
]);
371 static int writer_finish_section(struct reftable_writer
*w
)
373 uint8_t typ
= block_writer_type(w
->block_writer
);
374 uint64_t index_start
= 0;
376 int threshold
= w
->opts
.unpadded
? 1 : 3;
377 int before_blocks
= w
->stats
.idx_stats
.blocks
;
378 int err
= writer_flush_block(w
);
380 struct reftable_block_stats
*bstats
= NULL
;
384 while (w
->index_len
> threshold
) {
385 struct reftable_index_record
*idx
= NULL
;
389 index_start
= w
->next
;
390 writer_reinit_block_writer(w
, BLOCK_TYPE_INDEX
);
393 idx_len
= w
->index_len
;
398 for (i
= 0; i
< idx_len
; i
++) {
399 struct reftable_record rec
= { NULL
};
400 reftable_record_from_index(&rec
, idx
+ i
);
401 if (block_writer_add(w
->block_writer
, &rec
) == 0) {
405 err
= writer_flush_block(w
);
409 writer_reinit_block_writer(w
, BLOCK_TYPE_INDEX
);
411 err
= block_writer_add(w
->block_writer
, &rec
);
413 /* write into fresh block should always succeed
418 for (i
= 0; i
< idx_len
; i
++) {
419 strbuf_release(&idx
[i
].last_key
);
424 writer_clear_index(w
);
426 err
= writer_flush_block(w
);
430 bstats
= writer_reftable_block_stats(w
, typ
);
431 bstats
->index_blocks
= w
->stats
.idx_stats
.blocks
- before_blocks
;
432 bstats
->index_offset
= index_start
;
433 bstats
->max_index_level
= max_level
;
435 /* Reinit lastKey, as the next section can start with any key. */
441 struct common_prefix_arg
{
446 static void update_common(void *void_arg
, void *key
)
448 struct common_prefix_arg
*arg
= void_arg
;
449 struct obj_index_tree_node
*entry
= key
;
451 int n
= common_prefix_size(&entry
->hash
, arg
->last
);
456 arg
->last
= &entry
->hash
;
459 struct write_record_arg
{
460 struct reftable_writer
*w
;
464 static void write_object_record(void *void_arg
, void *key
)
466 struct write_record_arg
*arg
= void_arg
;
467 struct obj_index_tree_node
*entry
= key
;
468 struct reftable_obj_record obj_rec
= {
469 .hash_prefix
= (uint8_t *)entry
->hash
.buf
,
470 .hash_prefix_len
= arg
->w
->stats
.object_id_len
,
471 .offsets
= entry
->offsets
,
472 .offset_len
= entry
->offset_len
,
474 struct reftable_record rec
= { NULL
};
478 reftable_record_from_obj(&rec
, &obj_rec
);
479 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
483 arg
->err
= writer_flush_block(arg
->w
);
487 writer_reinit_block_writer(arg
->w
, BLOCK_TYPE_OBJ
);
488 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
491 obj_rec
.offset_len
= 0;
492 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
494 /* Should be able to write into a fresh block. */
495 assert(arg
->err
== 0);
500 static void object_record_free(void *void_arg
, void *key
)
502 struct obj_index_tree_node
*entry
= key
;
504 FREE_AND_NULL(entry
->offsets
);
505 strbuf_release(&entry
->hash
);
506 reftable_free(entry
);
509 static int writer_dump_object_index(struct reftable_writer
*w
)
511 struct write_record_arg closure
= { .w
= w
};
512 struct common_prefix_arg common
= { NULL
};
513 if (w
->obj_index_tree
) {
514 infix_walk(w
->obj_index_tree
, &update_common
, &common
);
516 w
->stats
.object_id_len
= common
.max
+ 1;
518 writer_reinit_block_writer(w
, BLOCK_TYPE_OBJ
);
520 if (w
->obj_index_tree
) {
521 infix_walk(w
->obj_index_tree
, &write_object_record
, &closure
);
526 return writer_finish_section(w
);
529 static int writer_finish_public_section(struct reftable_writer
*w
)
534 if (w
->block_writer
== NULL
)
537 typ
= block_writer_type(w
->block_writer
);
538 err
= writer_finish_section(w
);
541 if (typ
== BLOCK_TYPE_REF
&& !w
->opts
.skip_index_objects
&&
542 w
->stats
.ref_stats
.index_blocks
> 0) {
543 err
= writer_dump_object_index(w
);
548 if (w
->obj_index_tree
) {
549 infix_walk(w
->obj_index_tree
, &object_record_free
, NULL
);
550 tree_free(w
->obj_index_tree
);
551 w
->obj_index_tree
= NULL
;
554 w
->block_writer
= NULL
;
558 int reftable_writer_close(struct reftable_writer
*w
)
562 int err
= writer_finish_public_section(w
);
563 int empty_table
= w
->next
== 0;
566 w
->pending_padding
= 0;
568 /* Empty tables need a header anyway. */
570 int n
= writer_write_header(w
, header
);
571 err
= padded_write(w
, header
, n
, 0);
576 p
+= writer_write_header(w
, footer
);
577 put_be64(p
, w
->stats
.ref_stats
.index_offset
);
579 put_be64(p
, (w
->stats
.obj_stats
.offset
) << 5 | w
->stats
.object_id_len
);
581 put_be64(p
, w
->stats
.obj_stats
.index_offset
);
584 put_be64(p
, w
->stats
.log_stats
.offset
);
586 put_be64(p
, w
->stats
.log_stats
.index_offset
);
589 put_be32(p
, crc32(0, footer
, p
- footer
));
592 err
= padded_write(w
, footer
, footer_size(writer_version(w
)), 0);
597 err
= REFTABLE_EMPTY_TABLE_ERROR
;
602 /* free up memory. */
603 block_writer_release(&w
->block_writer_data
);
604 writer_clear_index(w
);
605 strbuf_release(&w
->last_key
);
609 static void writer_clear_index(struct reftable_writer
*w
)
612 for (i
= 0; i
< w
->index_len
; i
++) {
613 strbuf_release(&w
->index
[i
].last_key
);
616 FREE_AND_NULL(w
->index
);
621 static const int debug
= 0;
623 static int writer_flush_nonempty_block(struct reftable_writer
*w
)
625 uint8_t typ
= block_writer_type(w
->block_writer
);
626 struct reftable_block_stats
*bstats
=
627 writer_reftable_block_stats(w
, typ
);
628 uint64_t block_typ_off
= (bstats
->blocks
== 0) ? w
->next
: 0;
629 int raw_bytes
= block_writer_finish(w
->block_writer
);
632 struct reftable_index_record ir
= { .last_key
= STRBUF_INIT
};
636 if (!w
->opts
.unpadded
&& typ
!= BLOCK_TYPE_LOG
) {
637 padding
= w
->opts
.block_size
- raw_bytes
;
640 if (block_typ_off
> 0) {
641 bstats
->offset
= block_typ_off
;
644 bstats
->entries
+= w
->block_writer
->entries
;
645 bstats
->restarts
+= w
->block_writer
->restart_len
;
650 fprintf(stderr
, "block %c off %" PRIu64
" sz %d (%d)\n", typ
,
652 get_be24(w
->block
+ w
->block_writer
->header_off
+ 1));
656 writer_write_header(w
, w
->block
);
659 err
= padded_write(w
, w
->block
, raw_bytes
, padding
);
663 if (w
->index_cap
== w
->index_len
) {
664 w
->index_cap
= 2 * w
->index_cap
+ 1;
665 w
->index
= reftable_realloc(
667 sizeof(struct reftable_index_record
) * w
->index_cap
);
671 strbuf_reset(&ir
.last_key
);
672 strbuf_addbuf(&ir
.last_key
, &w
->block_writer
->last_key
);
673 w
->index
[w
->index_len
] = ir
;
676 w
->next
+= padding
+ raw_bytes
;
677 w
->block_writer
= NULL
;
681 static int writer_flush_block(struct reftable_writer
*w
)
683 if (w
->block_writer
== NULL
)
685 if (w
->block_writer
->entries
== 0)
687 return writer_flush_nonempty_block(w
);
690 const struct reftable_stats
*writer_stats(struct reftable_writer
*w
)