[thirdparty/git.git] / reftable / writer.c

/*
Copyright 2020 Google LLC

Use of this source code is governed by a BSD-style
license that can be found in the LICENSE file or at
https://developers.google.com/open-source/licenses/bsd
*/

#include "writer.h"

#include "system.h"

#include "block.h"
#include "constants.h"
#include "record.h"
#include "tree.h"
#include "reftable-error.h"

/* finishes a block, and writes it to storage */
static int writer_flush_block(struct reftable_writer *w);

/* deallocates memory related to the index */
static void writer_clear_index(struct reftable_writer *w);

/* finishes writing a 'r' (refs) or 'g' (reflogs) section */
static int writer_finish_public_section(struct reftable_writer *w);

static struct reftable_block_stats *
writer_reftable_block_stats(struct reftable_writer *w, uint8_t typ)
{
	switch (typ) {
	case 'r':
		return &w->stats.ref_stats;
	case 'o':
		return &w->stats.obj_stats;
	case 'i':
		return &w->stats.idx_stats;
	case 'g':
		return &w->stats.log_stats;
	}
	abort();
	return NULL;
}

/* write data, queuing the padding for the next write. Returns negative for
 * error. */
static int padded_write(struct reftable_writer *w, uint8_t *data, size_t len,
			int padding)
{
	int n = 0;
	if (w->pending_padding > 0) {
		uint8_t *zeroed = reftable_calloc(w->pending_padding);
		int n = w->write(w->write_arg, zeroed, w->pending_padding);
		if (n < 0)
			return n;

		w->pending_padding = 0;
		reftable_free(zeroed);
	}

	w->pending_padding = padding;
	n = w->write(w->write_arg, data, len);
	if (n < 0)
		return n;
	n += padding;
	return 0;
}

static void options_set_defaults(struct reftable_write_options *opts)
{
	if (opts->restart_interval == 0) {
		opts->restart_interval = 16;
	}

	if (opts->hash_id == 0) {
		opts->hash_id = GIT_SHA1_FORMAT_ID;
	}
	if (opts->block_size == 0) {
		opts->block_size = DEFAULT_BLOCK_SIZE;
	}
}

static int writer_version(struct reftable_writer *w)
{
	return (w->opts.hash_id == 0 || w->opts.hash_id == GIT_SHA1_FORMAT_ID) ?
			     1 :
			     2;
}

static int writer_write_header(struct reftable_writer *w, uint8_t *dest)
{
	memcpy(dest, "REFT", 4);

	dest[4] = writer_version(w);

	put_be24(dest + 5, w->opts.block_size);
	put_be64(dest + 8, w->min_update_index);
	put_be64(dest + 16, w->max_update_index);
	if (writer_version(w) == 2) {
		put_be32(dest + 24, w->opts.hash_id);
	}
	return header_size(writer_version(w));
}

static void writer_reinit_block_writer(struct reftable_writer *w, uint8_t typ)
{
	int block_start = 0;
	if (w->next == 0) {
		block_start = header_size(writer_version(w));
	}

	strbuf_release(&w->last_key);
	block_writer_init(&w->block_writer_data, typ, w->block,
			  w->opts.block_size, block_start,
			  hash_size(w->opts.hash_id));
	w->block_writer = &w->block_writer_data;
	w->block_writer->restart_interval = w->opts.restart_interval;
}

static struct strbuf reftable_empty_strbuf = STRBUF_INIT;

struct reftable_writer *
reftable_new_writer(ssize_t (*writer_func)(void *, const void *, size_t),
		    void *writer_arg, struct reftable_write_options *opts)
{
	struct reftable_writer *wp =
		reftable_calloc(sizeof(struct reftable_writer));
	strbuf_init(&wp->block_writer_data.last_key, 0);
	options_set_defaults(opts);
	if (opts->block_size >= (1 << 24)) {
		/* TODO - error return? */
		abort();
	}
	wp->last_key = reftable_empty_strbuf;
	wp->block = reftable_calloc(opts->block_size);
	wp->write = writer_func;
	wp->write_arg = writer_arg;
	wp->opts = *opts;
	writer_reinit_block_writer(wp, BLOCK_TYPE_REF);

	return wp;
}

void reftable_writer_set_limits(struct reftable_writer *w, uint64_t min,
				uint64_t max)
{
	w->min_update_index = min;
	w->max_update_index = max;
}

void reftable_writer_free(struct reftable_writer *w)
{
	if (!w)
		return;
	reftable_free(w->block);
	reftable_free(w);
}

struct obj_index_tree_node {
	struct strbuf hash;
	uint64_t *offsets;
	size_t offset_len;
	size_t offset_cap;
};

#define OBJ_INDEX_TREE_NODE_INIT    \
	{                           \
		.hash = STRBUF_INIT \
	}

static int obj_index_tree_node_compare(const void *a, const void *b)
{
	return strbuf_cmp(&((const struct obj_index_tree_node *)a)->hash,
			  &((const struct obj_index_tree_node *)b)->hash);
}

static void writer_index_hash(struct reftable_writer *w, struct strbuf *hash)
{
	uint64_t off = w->next;

	struct obj_index_tree_node want = { .hash = *hash };

	struct tree_node *node = tree_search(&want, &w->obj_index_tree,
					     &obj_index_tree_node_compare, 0);
	struct obj_index_tree_node *key = NULL;
	if (!node) {
		struct obj_index_tree_node empty = OBJ_INDEX_TREE_NODE_INIT;
		key = reftable_malloc(sizeof(struct obj_index_tree_node));
		*key = empty;

		strbuf_reset(&key->hash);
		strbuf_addbuf(&key->hash, hash);
		tree_search((void *)key, &w->obj_index_tree,
			    &obj_index_tree_node_compare, 1);
	} else {
		key = node->key;
	}

	if (key->offset_len > 0 && key->offsets[key->offset_len - 1] == off) {
		return;
	}

	if (key->offset_len == key->offset_cap) {
		key->offset_cap = 2 * key->offset_cap + 1;
		key->offsets = reftable_realloc(
			key->offsets, sizeof(uint64_t) * key->offset_cap);
	}

	key->offsets[key->offset_len++] = off;
}

static int writer_add_record(struct reftable_writer *w,
			     struct reftable_record *rec)
{
	struct strbuf key = STRBUF_INIT;
	int err = -1;
	reftable_record_key(rec, &key);
	if (strbuf_cmp(&w->last_key, &key) >= 0) {
		err = REFTABLE_API_ERROR;
		goto done;
	}

	strbuf_reset(&w->last_key);
	strbuf_addbuf(&w->last_key, &key);
	if (!w->block_writer) {
		writer_reinit_block_writer(w, reftable_record_type(rec));
	}

	assert(block_writer_type(w->block_writer) == reftable_record_type(rec));

	if (block_writer_add(w->block_writer, rec) == 0) {
		err = 0;
		goto done;
	}

	err = writer_flush_block(w);
	if (err < 0) {
		goto done;
	}

	writer_reinit_block_writer(w, reftable_record_type(rec));
	err = block_writer_add(w->block_writer, rec);
	if (err == -1) {
		/* we are writing into memory, so an error can only mean it
		 * doesn't fit. */
		err = REFTABLE_ENTRY_TOO_BIG_ERROR;
		goto done;
	}

done:
	strbuf_release(&key);
	return err;
}

int reftable_writer_add_ref(struct reftable_writer *w,
			    struct reftable_ref_record *ref)
{
	struct reftable_record rec = {
		.type = BLOCK_TYPE_REF,
		.u = {
			.ref = *ref
		},
	};
	int err = 0;

	if (!ref->refname)
		return REFTABLE_API_ERROR;
	if (ref->update_index < w->min_update_index ||
	    ref->update_index > w->max_update_index)
		return REFTABLE_API_ERROR;

	rec.u.ref.update_index -= w->min_update_index;

	err = writer_add_record(w, &rec);
	if (err < 0)
		return err;

	if (!w->opts.skip_index_objects && reftable_ref_record_val1(ref)) {
		struct strbuf h = STRBUF_INIT;
		strbuf_add(&h, (char *)reftable_ref_record_val1(ref),
			   hash_size(w->opts.hash_id));
		writer_index_hash(w, &h);
		strbuf_release(&h);
	}

	if (!w->opts.skip_index_objects && reftable_ref_record_val2(ref)) {
		struct strbuf h = STRBUF_INIT;
		strbuf_add(&h, reftable_ref_record_val2(ref),
			   hash_size(w->opts.hash_id));
		writer_index_hash(w, &h);
		strbuf_release(&h);
	}
	return 0;
}

int reftable_writer_add_refs(struct reftable_writer *w,
			     struct reftable_ref_record *refs, int n)
{
	int err = 0;
	int i = 0;
	QSORT(refs, n, reftable_ref_record_compare_name);
	for (i = 0; err == 0 && i < n; i++) {
		err = reftable_writer_add_ref(w, &refs[i]);
	}
	return err;
}

static int reftable_writer_add_log_verbatim(struct reftable_writer *w,
					    struct reftable_log_record *log)
{
	struct reftable_record rec = {
		.type = BLOCK_TYPE_LOG,
		.u = {
			.log = *log,
		},
	};
	if (w->block_writer &&
	    block_writer_type(w->block_writer) == BLOCK_TYPE_REF) {
		int err = writer_finish_public_section(w);
		if (err < 0)
			return err;
	}

	w->next -= w->pending_padding;
	w->pending_padding = 0;
	return writer_add_record(w, &rec);
}

int reftable_writer_add_log(struct reftable_writer *w,
			    struct reftable_log_record *log)
{
	char *input_log_message = NULL;
	struct strbuf cleaned_message = STRBUF_INIT;
	int err = 0;

	if (log->value_type == REFTABLE_LOG_DELETION)
		return reftable_writer_add_log_verbatim(w, log);

	if (!log->refname)
		return REFTABLE_API_ERROR;

	input_log_message = log->value.update.message;
	if (!w->opts.exact_log_message && log->value.update.message) {
		strbuf_addstr(&cleaned_message, log->value.update.message);
		while (cleaned_message.len &&
		       cleaned_message.buf[cleaned_message.len - 1] == '\n')
			strbuf_setlen(&cleaned_message,
				      cleaned_message.len - 1);
		if (strchr(cleaned_message.buf, '\n')) {
			/* multiple lines not allowed. */
			err = REFTABLE_API_ERROR;
			goto done;
		}
		strbuf_addstr(&cleaned_message, "\n");
		log->value.update.message = cleaned_message.buf;
	}

	err = reftable_writer_add_log_verbatim(w, log);
	log->value.update.message = input_log_message;
done:
	strbuf_release(&cleaned_message);
	return err;
}

int reftable_writer_add_logs(struct reftable_writer *w,
			     struct reftable_log_record *logs, int n)
{
	int err = 0;
	int i = 0;
	QSORT(logs, n, reftable_log_record_compare_key);

	for (i = 0; err == 0 && i < n; i++) {
		err = reftable_writer_add_log(w, &logs[i]);
	}
	return err;
}

static int writer_finish_section(struct reftable_writer *w)
{
	uint8_t typ = block_writer_type(w->block_writer);
	uint64_t index_start = 0;
	int max_level = 0;
	int threshold = w->opts.unpadded ? 1 : 3;
	int before_blocks = w->stats.idx_stats.blocks;
	int err = writer_flush_block(w);
	int i = 0;
	struct reftable_block_stats *bstats = NULL;
	if (err < 0)
		return err;

	while (w->index_len > threshold) {
		struct reftable_index_record *idx = NULL;
		int idx_len = 0;

		max_level++;
		index_start = w->next;
		writer_reinit_block_writer(w, BLOCK_TYPE_INDEX);

		idx = w->index;
		idx_len = w->index_len;

		w->index = NULL;
		w->index_len = 0;
		w->index_cap = 0;
		for (i = 0; i < idx_len; i++) {
			struct reftable_record rec = {
				.type = BLOCK_TYPE_INDEX,
				.u = {
					.idx = idx[i],
				},
			};
			if (block_writer_add(w->block_writer, &rec) == 0) {
				continue;
			}

			err = writer_flush_block(w);
			if (err < 0)
				return err;

			writer_reinit_block_writer(w, BLOCK_TYPE_INDEX);

			err = block_writer_add(w->block_writer, &rec);
			if (err != 0) {
				/* write into fresh block should always succeed
				 */
				abort();
			}
		}
		for (i = 0; i < idx_len; i++) {
			strbuf_release(&idx[i].last_key);
		}
		reftable_free(idx);
	}

	err = writer_flush_block(w);
	if (err < 0)
		return err;

	writer_clear_index(w);

	bstats = writer_reftable_block_stats(w, typ);
	bstats->index_blocks = w->stats.idx_stats.blocks - before_blocks;
	bstats->index_offset = index_start;
	bstats->max_index_level = max_level;

	/* Reinit lastKey, as the next section can start with any key. */
	w->last_key.len = 0;

	return 0;
}

struct common_prefix_arg {
	struct strbuf *last;
	int max;
};

static void update_common(void *void_arg, void *key)
{
	struct common_prefix_arg *arg = void_arg;
	struct obj_index_tree_node *entry = key;
	if (arg->last) {
		int n = common_prefix_size(&entry->hash, arg->last);
		if (n > arg->max) {
			arg->max = n;
		}
	}
	arg->last = &entry->hash;
}

struct write_record_arg {
	struct reftable_writer *w;
	int err;
};

static void write_object_record(void *void_arg, void *key)
{
	struct write_record_arg *arg = void_arg;
	struct obj_index_tree_node *entry = key;
	struct reftable_record
		rec = { .type = BLOCK_TYPE_OBJ,
			.u.obj = {
				.hash_prefix = (uint8_t *)entry->hash.buf,
				.hash_prefix_len = arg->w->stats.object_id_len,
				.offsets = entry->offsets,
				.offset_len = entry->offset_len,
			} };
	if (arg->err < 0)
		goto done;

	arg->err = block_writer_add(arg->w->block_writer, &rec);
	if (arg->err == 0)
		goto done;

	arg->err = writer_flush_block(arg->w);
	if (arg->err < 0)
		goto done;

	writer_reinit_block_writer(arg->w, BLOCK_TYPE_OBJ);
	arg->err = block_writer_add(arg->w->block_writer, &rec);
	if (arg->err == 0)
		goto done;

	rec.u.obj.offset_len = 0;
	arg->err = block_writer_add(arg->w->block_writer, &rec);

	/* Should be able to write into a fresh block. */
	assert(arg->err == 0);

done:;
}

static void object_record_free(void *void_arg, void *key)
{
	struct obj_index_tree_node *entry = key;

	FREE_AND_NULL(entry->offsets);
	strbuf_release(&entry->hash);
	reftable_free(entry);
}

static int writer_dump_object_index(struct reftable_writer *w)
{
	struct write_record_arg closure = { .w = w };
	struct common_prefix_arg common = {
		.max = 1,		/* obj_id_len should be >= 2. */
	};
	if (w->obj_index_tree) {
		infix_walk(w->obj_index_tree, &update_common, &common);
	}
	w->stats.object_id_len = common.max + 1;

	writer_reinit_block_writer(w, BLOCK_TYPE_OBJ);

	if (w->obj_index_tree) {
		infix_walk(w->obj_index_tree, &write_object_record, &closure);
	}

	if (closure.err < 0)
		return closure.err;
	return writer_finish_section(w);
}

static int writer_finish_public_section(struct reftable_writer *w)
{
	uint8_t typ = 0;
	int err = 0;

	if (!w->block_writer)
		return 0;

	typ = block_writer_type(w->block_writer);
	err = writer_finish_section(w);
	if (err < 0)
		return err;
	if (typ == BLOCK_TYPE_REF && !w->opts.skip_index_objects &&
	    w->stats.ref_stats.index_blocks > 0) {
		err = writer_dump_object_index(w);
		if (err < 0)
			return err;
	}

	if (w->obj_index_tree) {
		infix_walk(w->obj_index_tree, &object_record_free, NULL);
		tree_free(w->obj_index_tree);
		w->obj_index_tree = NULL;
	}

	w->block_writer = NULL;
	return 0;
}

int reftable_writer_close(struct reftable_writer *w)
{
	uint8_t footer[72];
	uint8_t *p = footer;
	int err = writer_finish_public_section(w);
	int empty_table = w->next == 0;
	if (err != 0)
		goto done;
	w->pending_padding = 0;
	if (empty_table) {
		/* Empty tables need a header anyway. */
		uint8_t header[28];
		int n = writer_write_header(w, header);
		err = padded_write(w, header, n, 0);
		if (err < 0)
			goto done;
	}

	p += writer_write_header(w, footer);
	put_be64(p, w->stats.ref_stats.index_offset);
	p += 8;
	put_be64(p, (w->stats.obj_stats.offset) << 5 | w->stats.object_id_len);
	p += 8;
	put_be64(p, w->stats.obj_stats.index_offset);
	p += 8;

	put_be64(p, w->stats.log_stats.offset);
	p += 8;
	put_be64(p, w->stats.log_stats.index_offset);
	p += 8;

	put_be32(p, crc32(0, footer, p - footer));
	p += 4;

	err = padded_write(w, footer, footer_size(writer_version(w)), 0);
	if (err < 0)
		goto done;

	if (empty_table) {
		err = REFTABLE_EMPTY_TABLE_ERROR;
		goto done;
	}

done:
	/* free up memory. */
	block_writer_release(&w->block_writer_data);
	writer_clear_index(w);
	strbuf_release(&w->last_key);
	return err;
}

static void writer_clear_index(struct reftable_writer *w)
{
	int i = 0;
	for (i = 0; i < w->index_len; i++) {
		strbuf_release(&w->index[i].last_key);
	}

	FREE_AND_NULL(w->index);
	w->index_len = 0;
	w->index_cap = 0;
}

static const int debug = 0;

static int writer_flush_nonempty_block(struct reftable_writer *w)
{
	uint8_t typ = block_writer_type(w->block_writer);
	struct reftable_block_stats *bstats =
		writer_reftable_block_stats(w, typ);
	uint64_t block_typ_off = (bstats->blocks == 0) ? w->next : 0;
	int raw_bytes = block_writer_finish(w->block_writer);
	int padding = 0;
	int err = 0;
	struct reftable_index_record ir = { .last_key = STRBUF_INIT };
	if (raw_bytes < 0)
		return raw_bytes;

	if (!w->opts.unpadded && typ != BLOCK_TYPE_LOG) {
		padding = w->opts.block_size - raw_bytes;
	}

	if (block_typ_off > 0) {
		bstats->offset = block_typ_off;
	}

	bstats->entries += w->block_writer->entries;
	bstats->restarts += w->block_writer->restart_len;
	bstats->blocks++;
	w->stats.blocks++;

	if (debug) {
		fprintf(stderr, "block %c off %" PRIu64 " sz %d (%d)\n", typ,
			w->next, raw_bytes,
			get_be24(w->block + w->block_writer->header_off + 1));
	}

	if (w->next == 0) {
		writer_write_header(w, w->block);
	}

	err = padded_write(w, w->block, raw_bytes, padding);
	if (err < 0)
		return err;

	if (w->index_cap == w->index_len) {
		w->index_cap = 2 * w->index_cap + 1;
		w->index = reftable_realloc(
			w->index,
			sizeof(struct reftable_index_record) * w->index_cap);
	}

	ir.offset = w->next;
	strbuf_reset(&ir.last_key);
	strbuf_addbuf(&ir.last_key, &w->block_writer->last_key);
	w->index[w->index_len] = ir;

	w->index_len++;
	w->next += padding + raw_bytes;
	w->block_writer = NULL;
	return 0;
}

static int writer_flush_block(struct reftable_writer *w)
{
	if (!w->block_writer)
		return 0;
	if (w->block_writer->entries == 0)
		return 0;
	return writer_flush_nonempty_block(w);
}

const struct reftable_stats *reftable_writer_stats(struct reftable_writer *w)
{
	return &w->stats;
}
Commit	Line	Data
f14bd719 HWN	1	/*
	2	Copyright 2020 Google LLC
	3
	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	*/
	8
	9	#include "writer.h"
	10
	11	#include "system.h"
	12
	13	#include "block.h"
	14	#include "constants.h"
	15	#include "record.h"
	16	#include "tree.h"
	17	#include "reftable-error.h"
	18
	19	/* finishes a block, and writes it to storage */
	20	static int writer_flush_block(struct reftable_writer *w);
	21
	22	/* deallocates memory related to the index */
	23	static void writer_clear_index(struct reftable_writer *w);
	24
	25	/* finishes writing a 'r' (refs) or 'g' (reflogs) section */
	26	static int writer_finish_public_section(struct reftable_writer *w);
	27
	28	static struct reftable_block_stats *
	29	writer_reftable_block_stats(struct reftable_writer *w, uint8_t typ)
	30	{
	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;
	40	}
	41	abort();
	42	return NULL;
	43	}
	44
	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)
	49	{
	50	int n = 0;
	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);
	54	if (n < 0)
	55	return n;
	56
	57	w->pending_padding = 0;
	58	reftable_free(zeroed);
	59	}
	60
	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;
67	}
68
69	static void options_set_defaults(struct reftable_write_options *opts)
70	{
71	if (opts->restart_interval == 0) {
72	opts->restart_interval = 16;
73	}
74
75	if (opts->hash_id == 0) {
76	opts->hash_id = GIT_SHA1_FORMAT_ID;
77	}
78	if (opts->block_size == 0) {
79	opts->block_size = DEFAULT_BLOCK_SIZE;
80	}
81	}
82
83	static int writer_version(struct reftable_writer *w)
84	{
85	return (w->opts.hash_id == 0 \|\| w->opts.hash_id == GIT_SHA1_FORMAT_ID) ?
86	1 :
87	2;
88	}
89
90	static int writer_write_header(struct reftable_writer w, uint8_t dest)
91	{
92	memcpy(dest, "REFT", 4);
93
94	dest[4] = writer_version(w);
95
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);
101	}
102	return header_size(writer_version(w));
103	}
104
105	static void writer_reinit_block_writer(struct reftable_writer *w, uint8_t typ)
106	{
107	int block_start = 0;
108	if (w->next == 0) {
109	block_start = header_size(writer_version(w));
110	}
111
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;
118	}
119
120	static struct strbuf reftable_empty_strbuf = STRBUF_INIT;
121
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)
125	{
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? */
132	abort();
133	}
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;
138	wp->opts = *opts;
139	writer_reinit_block_writer(wp, BLOCK_TYPE_REF);
140
141	return wp;
142	}
143
144	void reftable_writer_set_limits(struct reftable_writer *w, uint64_t min,
145	uint64_t max)
146	{
147	w->min_update_index = min;
148	w->max_update_index = max;
149	}
150
151	void reftable_writer_free(struct reftable_writer *w)
152	{
33e92243 HWN	153	if (!w)
33e92243 HWN	154	return;
f14bd719 HWN	155	reftable_free(w->block);
	156	reftable_free(w);
	157	}
	158
	159	struct obj_index_tree_node {
	160	struct strbuf hash;
	161	uint64_t *offsets;
	162	size_t offset_len;
	163	size_t offset_cap;
	164	};
	165
	166	#define OBJ_INDEX_TREE_NODE_INIT \
	167	{ \
	168	.hash = STRBUF_INIT \
	169	}
	170
	171	static int obj_index_tree_node_compare(const void a, const void b)
	172	{
	173	return strbuf_cmp(&((const struct obj_index_tree_node *)a)->hash,
	174	&((const struct obj_index_tree_node *)b)->hash);
	175	}
	176
	177	static void writer_index_hash(struct reftable_writer w, struct strbuf hash)
	178	{
	179	uint64_t off = w->next;
	180
	181	struct obj_index_tree_node want = { .hash = *hash };
	182
	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;
72a4ea71	186	if (!node) {
f14bd719 HWN	187	struct obj_index_tree_node empty = OBJ_INDEX_TREE_NODE_INIT;
	188	key = reftable_malloc(sizeof(struct obj_index_tree_node));
	189	*key = empty;
	190
	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);
	195	} else {
	196	key = node->key;
	197	}
	198
	199	if (key->offset_len > 0 && key->offsets[key->offset_len - 1] == off) {
	200	return;
	201	}
	202
	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);
	207	}
	208
	209	key->offsets[key->offset_len++] = off;
	210	}
	211
	212	static int writer_add_record(struct reftable_writer *w,
	213	struct reftable_record *rec)
	214	{
	215	struct strbuf key = STRBUF_INIT;
	216	int err = -1;
	217	reftable_record_key(rec, &key);
	218	if (strbuf_cmp(&w->last_key, &key) >= 0) {
	219	err = REFTABLE_API_ERROR;
	220	goto done;
	221	}
	222
	223	strbuf_reset(&w->last_key);
	224	strbuf_addbuf(&w->last_key, &key);
72a4ea71	225	if (!w->block_writer) {
f14bd719 HWN	226	writer_reinit_block_writer(w, reftable_record_type(rec));
	227	}
	228
	229	assert(block_writer_type(w->block_writer) == reftable_record_type(rec));
	230
	231	if (block_writer_add(w->block_writer, rec) == 0) {
	232	err = 0;
	233	goto done;
	234	}
	235
	236	err = writer_flush_block(w);
	237	if (err < 0) {
	238	goto done;
	239	}
	240
	241	writer_reinit_block_writer(w, reftable_record_type(rec));
	242	err = block_writer_add(w->block_writer, rec);
45c2fcc2	243	if (err == -1) {
0dd44584 HWN	244	/* we are writing into memory, so an error can only mean it
	245	* doesn't fit. */
	246	err = REFTABLE_ENTRY_TOO_BIG_ERROR;
f14bd719 HWN	247	goto done;
	248	}
	249
f14bd719 HWN	250	done:
	251	strbuf_release(&key);
	252	return err;
	253	}
	254
	255	int reftable_writer_add_ref(struct reftable_writer *w,
	256	struct reftable_ref_record *ref)
	257	{
66c0daba HWN	258	struct reftable_record rec = {
66c0daba HWN	259	.type = BLOCK_TYPE_REF,
33665d98 ÆAB	260	.u = {
	261	.ref = *ref
	262	},
66c0daba	263	};
f14bd719 HWN	264	int err = 0;
f14bd719 HWN	265
72a4ea71	266	if (!ref->refname)
f14bd719 HWN	267	return REFTABLE_API_ERROR;
	268	if (ref->update_index < w->min_update_index \|\|
	269	ref->update_index > w->max_update_index)
	270	return REFTABLE_API_ERROR;
	271
66c0daba	272	rec.u.ref.update_index -= w->min_update_index;
f14bd719 HWN	273
	274	err = writer_add_record(w, &rec);
	275	if (err < 0)
	276	return err;
	277
	278	if (!w->opts.skip_index_objects && reftable_ref_record_val1(ref)) {
	279	struct strbuf h = STRBUF_INIT;
	280	strbuf_add(&h, (char *)reftable_ref_record_val1(ref),
	281	hash_size(w->opts.hash_id));
	282	writer_index_hash(w, &h);
	283	strbuf_release(&h);
	284	}
	285
	286	if (!w->opts.skip_index_objects && reftable_ref_record_val2(ref)) {
	287	struct strbuf h = STRBUF_INIT;
	288	strbuf_add(&h, reftable_ref_record_val2(ref),
	289	hash_size(w->opts.hash_id));
	290	writer_index_hash(w, &h);
	291	strbuf_release(&h);
	292	}
	293	return 0;
	294	}
	295
	296	int reftable_writer_add_refs(struct reftable_writer *w,
	297	struct reftable_ref_record *refs, int n)
	298	{
	299	int err = 0;
	300	int i = 0;
	301	QSORT(refs, n, reftable_ref_record_compare_name);
	302	for (i = 0; err == 0 && i < n; i++) {
	303	err = reftable_writer_add_ref(w, &refs[i]);
	304	}
	305	return err;
	306	}
	307
	308	static int reftable_writer_add_log_verbatim(struct reftable_writer *w,
	309	struct reftable_log_record *log)
	310	{
66c0daba HWN	311	struct reftable_record rec = {
66c0daba HWN	312	.type = BLOCK_TYPE_LOG,
33665d98 ÆAB	313	.u = {
	314	.log = *log,
	315	},
66c0daba	316	};
f14bd719 HWN	317	if (w->block_writer &&
	318	block_writer_type(w->block_writer) == BLOCK_TYPE_REF) {
	319	int err = writer_finish_public_section(w);
	320	if (err < 0)
	321	return err;
	322	}
	323
	324	w->next -= w->pending_padding;
	325	w->pending_padding = 0;
f14bd719 HWN	326	return writer_add_record(w, &rec);
	327	}
	328
	329	int reftable_writer_add_log(struct reftable_writer *w,
	330	struct reftable_log_record *log)
	331	{
	332	char *input_log_message = NULL;
	333	struct strbuf cleaned_message = STRBUF_INIT;
	334	int err = 0;
	335
	336	if (log->value_type == REFTABLE_LOG_DELETION)
	337	return reftable_writer_add_log_verbatim(w, log);
	338
72a4ea71	339	if (!log->refname)
f14bd719 HWN	340	return REFTABLE_API_ERROR;
	341
	342	input_log_message = log->value.update.message;
	343	if (!w->opts.exact_log_message && log->value.update.message) {
	344	strbuf_addstr(&cleaned_message, log->value.update.message);
	345	while (cleaned_message.len &&
	346	cleaned_message.buf[cleaned_message.len - 1] == '\n')
	347	strbuf_setlen(&cleaned_message,
	348	cleaned_message.len - 1);
	349	if (strchr(cleaned_message.buf, '\n')) {
	350	/* multiple lines not allowed. */
	351	err = REFTABLE_API_ERROR;
	352	goto done;
	353	}
	354	strbuf_addstr(&cleaned_message, "\n");
	355	log->value.update.message = cleaned_message.buf;
	356	}
	357
	358	err = reftable_writer_add_log_verbatim(w, log);
	359	log->value.update.message = input_log_message;
	360	done:
	361	strbuf_release(&cleaned_message);
	362	return err;
	363	}
	364
	365	int reftable_writer_add_logs(struct reftable_writer *w,
	366	struct reftable_log_record *logs, int n)
	367	{
	368	int err = 0;
	369	int i = 0;
	370	QSORT(logs, n, reftable_log_record_compare_key);
	371
	372	for (i = 0; err == 0 && i < n; i++) {
	373	err = reftable_writer_add_log(w, &logs[i]);
	374	}
	375	return err;
	376	}
	377
	378	static int writer_finish_section(struct reftable_writer *w)
	379	{
	380	uint8_t typ = block_writer_type(w->block_writer);
	381	uint64_t index_start = 0;
	382	int max_level = 0;
	383	int threshold = w->opts.unpadded ? 1 : 3;
	384	int before_blocks = w->stats.idx_stats.blocks;
	385	int err = writer_flush_block(w);
	386	int i = 0;
	387	struct reftable_block_stats *bstats = NULL;
	388	if (err < 0)
	389	return err;
	390
	391	while (w->index_len > threshold) {
	392	struct reftable_index_record *idx = NULL;
	393	int idx_len = 0;
	394
	395	max_level++;
	396	index_start = w->next;
	397	writer_reinit_block_writer(w, BLOCK_TYPE_INDEX);
	398
	399	idx = w->index;
	400	idx_len = w->index_len;
	401
	402	w->index = NULL;
	403	w->index_len = 0;
404	w->index_cap = 0;
405	for (i = 0; i < idx_len; i++) {
66c0daba HWN	406	struct reftable_record rec = {
66c0daba HWN	407	.type = BLOCK_TYPE_INDEX,
33665d98 ÆAB	408	.u = {
	409	.idx = idx[i],
	410	},
66c0daba	411	};
f14bd719 HWN	412	if (block_writer_add(w->block_writer, &rec) == 0) {
	413	continue;
	414	}
	415
	416	err = writer_flush_block(w);
	417	if (err < 0)
	418	return err;
	419
	420	writer_reinit_block_writer(w, BLOCK_TYPE_INDEX);
	421
	422	err = block_writer_add(w->block_writer, &rec);
	423	if (err != 0) {
	424	/* write into fresh block should always succeed
	425	*/
	426	abort();
	427	}
	428	}
	429	for (i = 0; i < idx_len; i++) {
	430	strbuf_release(&idx[i].last_key);
	431	}
	432	reftable_free(idx);
	433	}
	434
f14bd719 HWN	435	err = writer_flush_block(w);
	436	if (err < 0)
	437	return err;
	438
ddac9659 PS	439	writer_clear_index(w);
ddac9659 PS	440
f14bd719 HWN	441	bstats = writer_reftable_block_stats(w, typ);
	442	bstats->index_blocks = w->stats.idx_stats.blocks - before_blocks;
	443	bstats->index_offset = index_start;
	444	bstats->max_index_level = max_level;
	445
	446	/* Reinit lastKey, as the next section can start with any key. */
	447	w->last_key.len = 0;
	448
	449	return 0;
	450	}
	451
	452	struct common_prefix_arg {
	453	struct strbuf *last;
	454	int max;
	455	};
	456
	457	static void update_common(void void_arg, void key)
	458	{
	459	struct common_prefix_arg *arg = void_arg;
	460	struct obj_index_tree_node *entry = key;
	461	if (arg->last) {
	462	int n = common_prefix_size(&entry->hash, arg->last);
	463	if (n > arg->max) {
	464	arg->max = n;
	465	}
	466	}
	467	arg->last = &entry->hash;
	468	}
	469
	470	struct write_record_arg {
	471	struct reftable_writer *w;
	472	int err;
	473	};
	474
	475	static void write_object_record(void void_arg, void key)
	476	{
	477	struct write_record_arg *arg = void_arg;
	478	struct obj_index_tree_node *entry = key;
66c0daba HWN	479	struct reftable_record
	480	rec = { .type = BLOCK_TYPE_OBJ,
	481	.u.obj = {
	482	.hash_prefix = (uint8_t *)entry->hash.buf,
	483	.hash_prefix_len = arg->w->stats.object_id_len,
	484	.offsets = entry->offsets,
	485	.offset_len = entry->offset_len,
	486	} };
f14bd719 HWN	487	if (arg->err < 0)
	488	goto done;
	489
f14bd719 HWN	490	arg->err = block_writer_add(arg->w->block_writer, &rec);
	491	if (arg->err == 0)
	492	goto done;
	493
	494	arg->err = writer_flush_block(arg->w);
	495	if (arg->err < 0)
	496	goto done;
	497
	498	writer_reinit_block_writer(arg->w, BLOCK_TYPE_OBJ);
	499	arg->err = block_writer_add(arg->w->block_writer, &rec);
	500	if (arg->err == 0)
	501	goto done;
66c0daba HWN	502
66c0daba HWN	503	rec.u.obj.offset_len = 0;
f14bd719 HWN	504	arg->err = block_writer_add(arg->w->block_writer, &rec);
	505
	506	/* Should be able to write into a fresh block. */
	507	assert(arg->err == 0);
	508
	509	done:;
	510	}
	511
	512	static void object_record_free(void void_arg, void key)
	513	{
	514	struct obj_index_tree_node *entry = key;
	515
	516	FREE_AND_NULL(entry->offsets);
	517	strbuf_release(&entry->hash);
	518	reftable_free(entry);
	519	}
	520
	521	static int writer_dump_object_index(struct reftable_writer *w)
	522	{
	523	struct write_record_arg closure = { .w = w };
b4007fcc HWN	524	struct common_prefix_arg common = {
	525	.max = 1, /* obj_id_len should be >= 2. */
	526	};
f14bd719 HWN	527	if (w->obj_index_tree) {
	528	infix_walk(w->obj_index_tree, &update_common, &common);
	529	}
	530	w->stats.object_id_len = common.max + 1;
	531
	532	writer_reinit_block_writer(w, BLOCK_TYPE_OBJ);
	533
	534	if (w->obj_index_tree) {
	535	infix_walk(w->obj_index_tree, &write_object_record, &closure);
	536	}
	537
	538	if (closure.err < 0)
	539	return closure.err;
	540	return writer_finish_section(w);
	541	}
	542
	543	static int writer_finish_public_section(struct reftable_writer *w)
	544	{
	545	uint8_t typ = 0;
	546	int err = 0;
	547
72a4ea71	548	if (!w->block_writer)
f14bd719 HWN	549	return 0;
	550
	551	typ = block_writer_type(w->block_writer);
	552	err = writer_finish_section(w);
	553	if (err < 0)
	554	return err;
	555	if (typ == BLOCK_TYPE_REF && !w->opts.skip_index_objects &&
	556	w->stats.ref_stats.index_blocks > 0) {
	557	err = writer_dump_object_index(w);
	558	if (err < 0)
	559	return err;
	560	}
	561
	562	if (w->obj_index_tree) {
	563	infix_walk(w->obj_index_tree, &object_record_free, NULL);
	564	tree_free(w->obj_index_tree);
	565	w->obj_index_tree = NULL;
	566	}
	567
	568	w->block_writer = NULL;
	569	return 0;
	570	}
	571
	572	int reftable_writer_close(struct reftable_writer *w)
	573	{
	574	uint8_t footer[72];
	575	uint8_t *p = footer;
	576	int err = writer_finish_public_section(w);
	577	int empty_table = w->next == 0;
	578	if (err != 0)
	579	goto done;
	580	w->pending_padding = 0;
	581	if (empty_table) {
	582	/* Empty tables need a header anyway. */
	583	uint8_t header[28];
	584	int n = writer_write_header(w, header);
	585	err = padded_write(w, header, n, 0);
	586	if (err < 0)
	587	goto done;
	588	}
	589
	590	p += writer_write_header(w, footer);
	591	put_be64(p, w->stats.ref_stats.index_offset);
	592	p += 8;
	593	put_be64(p, (w->stats.obj_stats.offset) << 5 \| w->stats.object_id_len);
	594	p += 8;
	595	put_be64(p, w->stats.obj_stats.index_offset);
	596	p += 8;
	597
	598	put_be64(p, w->stats.log_stats.offset);
	599	p += 8;
	600	put_be64(p, w->stats.log_stats.index_offset);
	601	p += 8;
	602
	603	put_be32(p, crc32(0, footer, p - footer));
	604	p += 4;
	605
	606	err = padded_write(w, footer, footer_size(writer_version(w)), 0);
	607	if (err < 0)
	608	goto done;
	609
	610	if (empty_table) {
	611	err = REFTABLE_EMPTY_TABLE_ERROR;
	612	goto done;
613	}
614
615	done:
616	/* free up memory. */
617	block_writer_release(&w->block_writer_data);
618	writer_clear_index(w);
619	strbuf_release(&w->last_key);
620	return err;
621	}
622
623	static void writer_clear_index(struct reftable_writer *w)
624	{
625	int i = 0;
626	for (i = 0; i < w->index_len; i++) {
627	strbuf_release(&w->index[i].last_key);
628	}
629
630	FREE_AND_NULL(w->index);
631	w->index_len = 0;
632	w->index_cap = 0;
633	}
634
635	static const int debug = 0;
636
637	static int writer_flush_nonempty_block(struct reftable_writer *w)
638	{
639	uint8_t typ = block_writer_type(w->block_writer);
640	struct reftable_block_stats *bstats =
641	writer_reftable_block_stats(w, typ);
642	uint64_t block_typ_off = (bstats->blocks == 0) ? w->next : 0;
643	int raw_bytes = block_writer_finish(w->block_writer);
644	int padding = 0;
645	int err = 0;
646	struct reftable_index_record ir = { .last_key = STRBUF_INIT };
647	if (raw_bytes < 0)
648	return raw_bytes;
649
650	if (!w->opts.unpadded && typ != BLOCK_TYPE_LOG) {
651	padding = w->opts.block_size - raw_bytes;
652	}
653
654	if (block_typ_off > 0) {
655	bstats->offset = block_typ_off;
656	}
657
658	bstats->entries += w->block_writer->entries;
659	bstats->restarts += w->block_writer->restart_len;
660	bstats->blocks++;
661	w->stats.blocks++;
662
663	if (debug) {
664	fprintf(stderr, "block %c off %" PRIu64 " sz %d (%d)\n", typ,
665	w->next, raw_bytes,
666	get_be24(w->block + w->block_writer->header_off + 1));
667	}
668
669	if (w->next == 0) {
670	writer_write_header(w, w->block);
671	}
672
673	err = padded_write(w, w->block, raw_bytes, padding);
674	if (err < 0)
675	return err;
676
677	if (w->index_cap == w->index_len) {
678	w->index_cap = 2 * w->index_cap + 1;
679	w->index = reftable_realloc(
680	w->index,
681	sizeof(struct reftable_index_record) * w->index_cap);
682	}
683
684	ir.offset = w->next;
685	strbuf_reset(&ir.last_key);
686	strbuf_addbuf(&ir.last_key, &w->block_writer->last_key);
687	w->index[w->index_len] = ir;
688
689	w->index_len++;
690	w->next += padding + raw_bytes;
691	w->block_writer = NULL;
692	return 0;
693	}
694
695	static int writer_flush_block(struct reftable_writer *w)
696	{
72a4ea71	697	if (!w->block_writer)
f14bd719 HWN	698	return 0;
	699	if (w->block_writer->entries == 0)
	700	return 0;
	701	return writer_flush_nonempty_block(w);
	702	}
	703
73a4c188	704	const struct reftable_stats reftable_writer_stats(struct reftable_writer w)
f14bd719 HWN	705	{
	706	return &w->stats;
	707	}