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
);
249 strbuf_release(&key
);
253 int reftable_writer_add_ref(struct reftable_writer
*w
,
254 struct reftable_ref_record
*ref
)
256 struct reftable_record rec
= { NULL
};
257 struct reftable_ref_record copy
= *ref
;
260 if (ref
->refname
== NULL
)
261 return REFTABLE_API_ERROR
;
262 if (ref
->update_index
< w
->min_update_index
||
263 ref
->update_index
> w
->max_update_index
)
264 return REFTABLE_API_ERROR
;
266 reftable_record_from_ref(&rec
, ©
);
267 copy
.update_index
-= w
->min_update_index
;
269 err
= writer_add_record(w
, &rec
);
273 if (!w
->opts
.skip_index_objects
&& reftable_ref_record_val1(ref
)) {
274 struct strbuf h
= STRBUF_INIT
;
275 strbuf_add(&h
, (char *)reftable_ref_record_val1(ref
),
276 hash_size(w
->opts
.hash_id
));
277 writer_index_hash(w
, &h
);
281 if (!w
->opts
.skip_index_objects
&& reftable_ref_record_val2(ref
)) {
282 struct strbuf h
= STRBUF_INIT
;
283 strbuf_add(&h
, reftable_ref_record_val2(ref
),
284 hash_size(w
->opts
.hash_id
));
285 writer_index_hash(w
, &h
);
291 int reftable_writer_add_refs(struct reftable_writer
*w
,
292 struct reftable_ref_record
*refs
, int n
)
296 QSORT(refs
, n
, reftable_ref_record_compare_name
);
297 for (i
= 0; err
== 0 && i
< n
; i
++) {
298 err
= reftable_writer_add_ref(w
, &refs
[i
]);
303 static int reftable_writer_add_log_verbatim(struct reftable_writer
*w
,
304 struct reftable_log_record
*log
)
306 struct reftable_record rec
= { NULL
};
307 if (w
->block_writer
&&
308 block_writer_type(w
->block_writer
) == BLOCK_TYPE_REF
) {
309 int err
= writer_finish_public_section(w
);
314 w
->next
-= w
->pending_padding
;
315 w
->pending_padding
= 0;
317 reftable_record_from_log(&rec
, log
);
318 return writer_add_record(w
, &rec
);
321 int reftable_writer_add_log(struct reftable_writer
*w
,
322 struct reftable_log_record
*log
)
324 char *input_log_message
= NULL
;
325 struct strbuf cleaned_message
= STRBUF_INIT
;
328 if (log
->value_type
== REFTABLE_LOG_DELETION
)
329 return reftable_writer_add_log_verbatim(w
, log
);
331 if (log
->refname
== NULL
)
332 return REFTABLE_API_ERROR
;
334 input_log_message
= log
->value
.update
.message
;
335 if (!w
->opts
.exact_log_message
&& log
->value
.update
.message
) {
336 strbuf_addstr(&cleaned_message
, log
->value
.update
.message
);
337 while (cleaned_message
.len
&&
338 cleaned_message
.buf
[cleaned_message
.len
- 1] == '\n')
339 strbuf_setlen(&cleaned_message
,
340 cleaned_message
.len
- 1);
341 if (strchr(cleaned_message
.buf
, '\n')) {
342 /* multiple lines not allowed. */
343 err
= REFTABLE_API_ERROR
;
346 strbuf_addstr(&cleaned_message
, "\n");
347 log
->value
.update
.message
= cleaned_message
.buf
;
350 err
= reftable_writer_add_log_verbatim(w
, log
);
351 log
->value
.update
.message
= input_log_message
;
353 strbuf_release(&cleaned_message
);
357 int reftable_writer_add_logs(struct reftable_writer
*w
,
358 struct reftable_log_record
*logs
, int n
)
362 QSORT(logs
, n
, reftable_log_record_compare_key
);
364 for (i
= 0; err
== 0 && i
< n
; i
++) {
365 err
= reftable_writer_add_log(w
, &logs
[i
]);
370 static int writer_finish_section(struct reftable_writer
*w
)
372 uint8_t typ
= block_writer_type(w
->block_writer
);
373 uint64_t index_start
= 0;
375 int threshold
= w
->opts
.unpadded
? 1 : 3;
376 int before_blocks
= w
->stats
.idx_stats
.blocks
;
377 int err
= writer_flush_block(w
);
379 struct reftable_block_stats
*bstats
= NULL
;
383 while (w
->index_len
> threshold
) {
384 struct reftable_index_record
*idx
= NULL
;
388 index_start
= w
->next
;
389 writer_reinit_block_writer(w
, BLOCK_TYPE_INDEX
);
392 idx_len
= w
->index_len
;
397 for (i
= 0; i
< idx_len
; i
++) {
398 struct reftable_record rec
= { NULL
};
399 reftable_record_from_index(&rec
, idx
+ i
);
400 if (block_writer_add(w
->block_writer
, &rec
) == 0) {
404 err
= writer_flush_block(w
);
408 writer_reinit_block_writer(w
, BLOCK_TYPE_INDEX
);
410 err
= block_writer_add(w
->block_writer
, &rec
);
412 /* write into fresh block should always succeed
417 for (i
= 0; i
< idx_len
; i
++) {
418 strbuf_release(&idx
[i
].last_key
);
423 writer_clear_index(w
);
425 err
= writer_flush_block(w
);
429 bstats
= writer_reftable_block_stats(w
, typ
);
430 bstats
->index_blocks
= w
->stats
.idx_stats
.blocks
- before_blocks
;
431 bstats
->index_offset
= index_start
;
432 bstats
->max_index_level
= max_level
;
434 /* Reinit lastKey, as the next section can start with any key. */
440 struct common_prefix_arg
{
445 static void update_common(void *void_arg
, void *key
)
447 struct common_prefix_arg
*arg
= void_arg
;
448 struct obj_index_tree_node
*entry
= key
;
450 int n
= common_prefix_size(&entry
->hash
, arg
->last
);
455 arg
->last
= &entry
->hash
;
458 struct write_record_arg
{
459 struct reftable_writer
*w
;
463 static void write_object_record(void *void_arg
, void *key
)
465 struct write_record_arg
*arg
= void_arg
;
466 struct obj_index_tree_node
*entry
= key
;
467 struct reftable_obj_record obj_rec
= {
468 .hash_prefix
= (uint8_t *)entry
->hash
.buf
,
469 .hash_prefix_len
= arg
->w
->stats
.object_id_len
,
470 .offsets
= entry
->offsets
,
471 .offset_len
= entry
->offset_len
,
473 struct reftable_record rec
= { NULL
};
477 reftable_record_from_obj(&rec
, &obj_rec
);
478 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
482 arg
->err
= writer_flush_block(arg
->w
);
486 writer_reinit_block_writer(arg
->w
, BLOCK_TYPE_OBJ
);
487 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
490 obj_rec
.offset_len
= 0;
491 arg
->err
= block_writer_add(arg
->w
->block_writer
, &rec
);
493 /* Should be able to write into a fresh block. */
494 assert(arg
->err
== 0);
499 static void object_record_free(void *void_arg
, void *key
)
501 struct obj_index_tree_node
*entry
= key
;
503 FREE_AND_NULL(entry
->offsets
);
504 strbuf_release(&entry
->hash
);
505 reftable_free(entry
);
508 static int writer_dump_object_index(struct reftable_writer
*w
)
510 struct write_record_arg closure
= { .w
= w
};
511 struct common_prefix_arg common
= { NULL
};
512 if (w
->obj_index_tree
) {
513 infix_walk(w
->obj_index_tree
, &update_common
, &common
);
515 w
->stats
.object_id_len
= common
.max
+ 1;
517 writer_reinit_block_writer(w
, BLOCK_TYPE_OBJ
);
519 if (w
->obj_index_tree
) {
520 infix_walk(w
->obj_index_tree
, &write_object_record
, &closure
);
525 return writer_finish_section(w
);
528 static int writer_finish_public_section(struct reftable_writer
*w
)
533 if (w
->block_writer
== NULL
)
536 typ
= block_writer_type(w
->block_writer
);
537 err
= writer_finish_section(w
);
540 if (typ
== BLOCK_TYPE_REF
&& !w
->opts
.skip_index_objects
&&
541 w
->stats
.ref_stats
.index_blocks
> 0) {
542 err
= writer_dump_object_index(w
);
547 if (w
->obj_index_tree
) {
548 infix_walk(w
->obj_index_tree
, &object_record_free
, NULL
);
549 tree_free(w
->obj_index_tree
);
550 w
->obj_index_tree
= NULL
;
553 w
->block_writer
= NULL
;
557 int reftable_writer_close(struct reftable_writer
*w
)
561 int err
= writer_finish_public_section(w
);
562 int empty_table
= w
->next
== 0;
565 w
->pending_padding
= 0;
567 /* Empty tables need a header anyway. */
569 int n
= writer_write_header(w
, header
);
570 err
= padded_write(w
, header
, n
, 0);
575 p
+= writer_write_header(w
, footer
);
576 put_be64(p
, w
->stats
.ref_stats
.index_offset
);
578 put_be64(p
, (w
->stats
.obj_stats
.offset
) << 5 | w
->stats
.object_id_len
);
580 put_be64(p
, w
->stats
.obj_stats
.index_offset
);
583 put_be64(p
, w
->stats
.log_stats
.offset
);
585 put_be64(p
, w
->stats
.log_stats
.index_offset
);
588 put_be32(p
, crc32(0, footer
, p
- footer
));
591 err
= padded_write(w
, footer
, footer_size(writer_version(w
)), 0);
596 err
= REFTABLE_EMPTY_TABLE_ERROR
;
601 /* free up memory. */
602 block_writer_release(&w
->block_writer_data
);
603 writer_clear_index(w
);
604 strbuf_release(&w
->last_key
);
608 static void writer_clear_index(struct reftable_writer
*w
)
611 for (i
= 0; i
< w
->index_len
; i
++) {
612 strbuf_release(&w
->index
[i
].last_key
);
615 FREE_AND_NULL(w
->index
);
620 static const int debug
= 0;
622 static int writer_flush_nonempty_block(struct reftable_writer
*w
)
624 uint8_t typ
= block_writer_type(w
->block_writer
);
625 struct reftable_block_stats
*bstats
=
626 writer_reftable_block_stats(w
, typ
);
627 uint64_t block_typ_off
= (bstats
->blocks
== 0) ? w
->next
: 0;
628 int raw_bytes
= block_writer_finish(w
->block_writer
);
631 struct reftable_index_record ir
= { .last_key
= STRBUF_INIT
};
635 if (!w
->opts
.unpadded
&& typ
!= BLOCK_TYPE_LOG
) {
636 padding
= w
->opts
.block_size
- raw_bytes
;
639 if (block_typ_off
> 0) {
640 bstats
->offset
= block_typ_off
;
643 bstats
->entries
+= w
->block_writer
->entries
;
644 bstats
->restarts
+= w
->block_writer
->restart_len
;
649 fprintf(stderr
, "block %c off %" PRIu64
" sz %d (%d)\n", typ
,
651 get_be24(w
->block
+ w
->block_writer
->header_off
+ 1));
655 writer_write_header(w
, w
->block
);
658 err
= padded_write(w
, w
->block
, raw_bytes
, padding
);
662 if (w
->index_cap
== w
->index_len
) {
663 w
->index_cap
= 2 * w
->index_cap
+ 1;
664 w
->index
= reftable_realloc(
666 sizeof(struct reftable_index_record
) * w
->index_cap
);
670 strbuf_reset(&ir
.last_key
);
671 strbuf_addbuf(&ir
.last_key
, &w
->block_writer
->last_key
);
672 w
->index
[w
->index_len
] = ir
;
675 w
->next
+= padding
+ raw_bytes
;
676 w
->block_writer
= NULL
;
680 static int writer_flush_block(struct reftable_writer
*w
)
682 if (w
->block_writer
== NULL
)
684 if (w
->block_writer
->entries
== 0)
686 return writer_flush_nonempty_block(w
);
689 const struct reftable_stats
*writer_stats(struct reftable_writer
*w
)