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
)
155 reftable_free(w
->block
);
159 struct obj_index_tree_node
{
166 #define OBJ_INDEX_TREE_NODE_INIT \
168 .hash = STRBUF_INIT \
171 static int obj_index_tree_node_compare(const void *a
, const void *b
)
173 return strbuf_cmp(&((const struct obj_index_tree_node
*)a
)->hash
,
174 &((const struct obj_index_tree_node
*)b
)->hash
);
177 static void writer_index_hash(struct reftable_writer
*w
, struct strbuf
*hash
)
179 uint64_t off
= w
->next
;
181 struct obj_index_tree_node want
= { .hash
= *hash
};
183 struct tree_node
*node
= tree_search(&want
, &w
->obj_index_tree
,
184 &obj_index_tree_node_compare
, 0);
185 struct obj_index_tree_node
*key
= NULL
;
187 struct obj_index_tree_node empty
= OBJ_INDEX_TREE_NODE_INIT
;
188 key
= reftable_malloc(sizeof(struct obj_index_tree_node
));
191 strbuf_reset(&key
->hash
);
192 strbuf_addbuf(&key
->hash
, hash
);
193 tree_search((void *)key
, &w
->obj_index_tree
,
194 &obj_index_tree_node_compare
, 1);
199 if (key
->offset_len
> 0 && key
->offsets
[key
->offset_len
- 1] == off
) {
203 if (key
->offset_len
== key
->offset_cap
) {
204 key
->offset_cap
= 2 * key
->offset_cap
+ 1;
205 key
->offsets
= reftable_realloc(
206 key
->offsets
, sizeof(uint64_t) * key
->offset_cap
);
209 key
->offsets
[key
->offset_len
++] = off
;
212 static int writer_add_record(struct reftable_writer
*w
,
213 struct reftable_record
*rec
)
215 struct strbuf key
= STRBUF_INIT
;
217 reftable_record_key(rec
, &key
);
218 if (strbuf_cmp(&w
->last_key
, &key
) >= 0) {
219 err
= REFTABLE_API_ERROR
;
223 strbuf_reset(&w
->last_key
);
224 strbuf_addbuf(&w
->last_key
, &key
);
225 if (w
->block_writer
== NULL
) {
226 writer_reinit_block_writer(w
, reftable_record_type(rec
));
229 assert(block_writer_type(w
->block_writer
) == reftable_record_type(rec
));
231 if (block_writer_add(w
->block_writer
, rec
) == 0) {
236 err
= writer_flush_block(w
);
241 writer_reinit_block_writer(w
, reftable_record_type(rec
));
242 err
= block_writer_add(w
->block_writer
, rec
);
244 /* we are writing into memory, so an error can only mean it
246 err
= REFTABLE_ENTRY_TOO_BIG_ERROR
;
251 strbuf_release(&key
);
255 int reftable_writer_add_ref(struct reftable_writer
*w
,
256 struct reftable_ref_record
*ref
)
258 struct reftable_record rec
= {
259 .type
= BLOCK_TYPE_REF
,
264 if (ref
->refname
== NULL
)
265 return REFTABLE_API_ERROR
;
266 if (ref
->update_index
< w
->min_update_index
||
267 ref
->update_index
> w
->max_update_index
)
268 return REFTABLE_API_ERROR
;
270 rec
.u
.ref
.update_index
-= w
->min_update_index
;
272 err
= writer_add_record(w
, &rec
);
276 if (!w
->opts
.skip_index_objects
&& reftable_ref_record_val1(ref
)) {
277 struct strbuf h
= STRBUF_INIT
;
278 strbuf_add(&h
, (char *)reftable_ref_record_val1(ref
),
279 hash_size(w
->opts
.hash_id
));
280 writer_index_hash(w
, &h
);
284 if (!w
->opts
.skip_index_objects
&& reftable_ref_record_val2(ref
)) {
285 struct strbuf h
= STRBUF_INIT
;
286 strbuf_add(&h
, reftable_ref_record_val2(ref
),
287 hash_size(w
->opts
.hash_id
));
288 writer_index_hash(w
, &h
);
294 int reftable_writer_add_refs(struct reftable_writer
*w
,
295 struct reftable_ref_record
*refs
, int n
)
299 QSORT(refs
, n
, reftable_ref_record_compare_name
);
300 for (i
= 0; err
== 0 && i
< n
; i
++) {
301 err
= reftable_writer_add_ref(w
, &refs
[i
]);
306 static int reftable_writer_add_log_verbatim(struct reftable_writer
*w
,
307 struct reftable_log_record
*log
)
309 struct reftable_record rec
= {
310 .type
= BLOCK_TYPE_LOG
,
313 if (w
->block_writer
&&
314 block_writer_type(w
->block_writer
) == BLOCK_TYPE_REF
) {
315 int err
= writer_finish_public_section(w
);
320 w
->next
-= w
->pending_padding
;
321 w
->pending_padding
= 0;
322 return writer_add_record(w
, &rec
);
325 int reftable_writer_add_log(struct reftable_writer
*w
,
326 struct reftable_log_record
*log
)
328 char *input_log_message
= NULL
;
329 struct strbuf cleaned_message
= STRBUF_INIT
;
332 if (log
->value_type
== REFTABLE_LOG_DELETION
)
333 return reftable_writer_add_log_verbatim(w
, log
);
335 if (log
->refname
== NULL
)
336 return REFTABLE_API_ERROR
;
338 input_log_message
= log
->value
.update
.message
;
339 if (!w
->opts
.exact_log_message
&& log
->value
.update
.message
) {
340 strbuf_addstr(&cleaned_message
, log
->value
.update
.message
);
341 while (cleaned_message
.len
&&
342 cleaned_message
.buf
[cleaned_message
.len
- 1] == '\n')
343 strbuf_setlen(&cleaned_message
,
344 cleaned_message
.len
- 1);
345 if (strchr(cleaned_message
.buf
, '\n')) {
346 /* multiple lines not allowed. */
347 err
= REFTABLE_API_ERROR
;
350 strbuf_addstr(&cleaned_message
, "\n");
351 log
->value
.update
.message
= cleaned_message
.buf
;
354 err
= reftable_writer_add_log_verbatim(w
, log
);
355 log
->value
.update
.message
= input_log_message
;
357 strbuf_release(&cleaned_message
);
361 int reftable_writer_add_logs(struct reftable_writer
*w
,
362 struct reftable_log_record
*logs
, int n
)
366 QSORT(logs
, n
, reftable_log_record_compare_key
);
368 for (i
= 0; err
== 0 && i
< n
; i
++) {
369 err
= reftable_writer_add_log(w
, &logs
[i
]);
374 static int writer_finish_section(struct reftable_writer
*w
)
376 uint8_t typ
= block_writer_type(w
->block_writer
);
377 uint64_t index_start
= 0;
379 int threshold
= w
->opts
.unpadded
? 1 : 3;
380 int before_blocks
= w
->stats
.idx_stats
.blocks
;
381 int err
= writer_flush_block(w
);
383 struct reftable_block_stats
*bstats
= NULL
;
387 while (w
->index_len
> threshold
) {
388 struct reftable_index_record
*idx
= NULL
;
392 index_start
= w
->next
;
393 writer_reinit_block_writer(w
, BLOCK_TYPE_INDEX
);
396 idx_len
= w
->index_len
;
401 for (i
= 0; i
< idx_len
; i
++) {
402 struct reftable_record rec
= {
403 .type
= BLOCK_TYPE_INDEX
,
406 if (block_writer_add(w
->block_writer
, &rec
) == 0) {
410 err
= writer_flush_block(w
);
414 writer_reinit_block_writer(w
, BLOCK_TYPE_INDEX
);
416 err
= block_writer_add(w
->block_writer
, &rec
);
418 /* write into fresh block should always succeed
423 for (i
= 0; i
< idx_len
; i
++) {
424 strbuf_release(&idx
[i
].last_key
);
429 writer_clear_index(w
);
431 err
= writer_flush_block(w
);
435 bstats
= writer_reftable_block_stats(w
, typ
);
436 bstats
->index_blocks
= w
->stats
.idx_stats
.blocks
- before_blocks
;
437 bstats
->index_offset
= index_start
;
438 bstats
->max_index_level
= max_level
;
440 /* Reinit lastKey, as the next section can start with any key. */
446 struct common_prefix_arg
{
451 static void update_common(void *void_arg
, void *key
)
453 struct common_prefix_arg
*arg
= void_arg
;
454 struct obj_index_tree_node
*entry
= key
;
456 int n
= common_prefix_size(&entry
->hash
, arg
->last
);
461 arg
->last
= &entry
->hash
;
464 struct write_record_arg
{
465 struct reftable_writer
*w
;
469 static void write_object_record(void *void_arg
, void *key
)
471 struct write_record_arg
*arg
= void_arg
;
472 struct obj_index_tree_node
*entry
= key
;
473 struct reftable_record
474 rec
= { .type
= BLOCK_TYPE_OBJ
,
476 .hash_prefix
= (uint8_t *)entry
->hash
.buf
,
477 .hash_prefix_len
= arg
->w
->stats
.object_id_len
,
478 .offsets
= entry
->offsets
,
479 .offset_len
= entry
->offset_len
,
484 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
488 arg
->err
= writer_flush_block(arg
->w
);
492 writer_reinit_block_writer(arg
->w
, BLOCK_TYPE_OBJ
);
493 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
497 rec
.u
.obj
.offset_len
= 0;
498 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
500 /* Should be able to write into a fresh block. */
501 assert(arg
->err
== 0);
506 static void object_record_free(void *void_arg
, void *key
)
508 struct obj_index_tree_node
*entry
= key
;
510 FREE_AND_NULL(entry
->offsets
);
511 strbuf_release(&entry
->hash
);
512 reftable_free(entry
);
515 static int writer_dump_object_index(struct reftable_writer
*w
)
517 struct write_record_arg closure
= { .w
= w
};
518 struct common_prefix_arg common
= {
519 .max
= 1, /* obj_id_len should be >= 2. */
521 if (w
->obj_index_tree
) {
522 infix_walk(w
->obj_index_tree
, &update_common
, &common
);
524 w
->stats
.object_id_len
= common
.max
+ 1;
526 writer_reinit_block_writer(w
, BLOCK_TYPE_OBJ
);
528 if (w
->obj_index_tree
) {
529 infix_walk(w
->obj_index_tree
, &write_object_record
, &closure
);
534 return writer_finish_section(w
);
537 static int writer_finish_public_section(struct reftable_writer
*w
)
542 if (w
->block_writer
== NULL
)
545 typ
= block_writer_type(w
->block_writer
);
546 err
= writer_finish_section(w
);
549 if (typ
== BLOCK_TYPE_REF
&& !w
->opts
.skip_index_objects
&&
550 w
->stats
.ref_stats
.index_blocks
> 0) {
551 err
= writer_dump_object_index(w
);
556 if (w
->obj_index_tree
) {
557 infix_walk(w
->obj_index_tree
, &object_record_free
, NULL
);
558 tree_free(w
->obj_index_tree
);
559 w
->obj_index_tree
= NULL
;
562 w
->block_writer
= NULL
;
566 int reftable_writer_close(struct reftable_writer
*w
)
570 int err
= writer_finish_public_section(w
);
571 int empty_table
= w
->next
== 0;
574 w
->pending_padding
= 0;
576 /* Empty tables need a header anyway. */
578 int n
= writer_write_header(w
, header
);
579 err
= padded_write(w
, header
, n
, 0);
584 p
+= writer_write_header(w
, footer
);
585 put_be64(p
, w
->stats
.ref_stats
.index_offset
);
587 put_be64(p
, (w
->stats
.obj_stats
.offset
) << 5 | w
->stats
.object_id_len
);
589 put_be64(p
, w
->stats
.obj_stats
.index_offset
);
592 put_be64(p
, w
->stats
.log_stats
.offset
);
594 put_be64(p
, w
->stats
.log_stats
.index_offset
);
597 put_be32(p
, crc32(0, footer
, p
- footer
));
600 err
= padded_write(w
, footer
, footer_size(writer_version(w
)), 0);
605 err
= REFTABLE_EMPTY_TABLE_ERROR
;
610 /* free up memory. */
611 block_writer_release(&w
->block_writer_data
);
612 writer_clear_index(w
);
613 strbuf_release(&w
->last_key
);
617 static void writer_clear_index(struct reftable_writer
*w
)
620 for (i
= 0; i
< w
->index_len
; i
++) {
621 strbuf_release(&w
->index
[i
].last_key
);
624 FREE_AND_NULL(w
->index
);
629 static const int debug
= 0;
631 static int writer_flush_nonempty_block(struct reftable_writer
*w
)
633 uint8_t typ
= block_writer_type(w
->block_writer
);
634 struct reftable_block_stats
*bstats
=
635 writer_reftable_block_stats(w
, typ
);
636 uint64_t block_typ_off
= (bstats
->blocks
== 0) ? w
->next
: 0;
637 int raw_bytes
= block_writer_finish(w
->block_writer
);
640 struct reftable_index_record ir
= { .last_key
= STRBUF_INIT
};
644 if (!w
->opts
.unpadded
&& typ
!= BLOCK_TYPE_LOG
) {
645 padding
= w
->opts
.block_size
- raw_bytes
;
648 if (block_typ_off
> 0) {
649 bstats
->offset
= block_typ_off
;
652 bstats
->entries
+= w
->block_writer
->entries
;
653 bstats
->restarts
+= w
->block_writer
->restart_len
;
658 fprintf(stderr
, "block %c off %" PRIu64
" sz %d (%d)\n", typ
,
660 get_be24(w
->block
+ w
->block_writer
->header_off
+ 1));
664 writer_write_header(w
, w
->block
);
667 err
= padded_write(w
, w
->block
, raw_bytes
, padding
);
671 if (w
->index_cap
== w
->index_len
) {
672 w
->index_cap
= 2 * w
->index_cap
+ 1;
673 w
->index
= reftable_realloc(
675 sizeof(struct reftable_index_record
) * w
->index_cap
);
679 strbuf_reset(&ir
.last_key
);
680 strbuf_addbuf(&ir
.last_key
, &w
->block_writer
->last_key
);
681 w
->index
[w
->index_len
] = ir
;
684 w
->next
+= padding
+ raw_bytes
;
685 w
->block_writer
= NULL
;
689 static int writer_flush_block(struct reftable_writer
*w
)
691 if (w
->block_writer
== NULL
)
693 if (w
->block_writer
->entries
== 0)
695 return writer_flush_nonempty_block(w
);
698 const struct reftable_stats
*reftable_writer_stats(struct reftable_writer
*w
)