git/reftable/table.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 "table.h"

#include "system.h"
#include "block.h"
#include "blocksource.h"
#include "constants.h"
#include "iter.h"
#include "record.h"
#include "reftable-error.h"

static struct reftable_table_offsets *
table_offsets_for(struct reftable_table *t, uint8_t typ)
{
	switch (typ) {
	case REFTABLE_BLOCK_TYPE_REF:
		return &t->ref_offsets;
	case REFTABLE_BLOCK_TYPE_LOG:
		return &t->log_offsets;
	case REFTABLE_BLOCK_TYPE_OBJ:
		return &t->obj_offsets;
	}
	abort();
}

enum reftable_hash reftable_table_hash_id(struct reftable_table *t)
{
	return t->hash_id;
}

const char *reftable_table_name(struct reftable_table *t)
{
	return t->name;
}

static int parse_footer(struct reftable_table *t, uint8_t *footer,
			uint8_t *header)
{
	uint8_t *f = footer;
	uint8_t first_block_typ;
	int err = 0;
	uint32_t computed_crc;
	uint32_t file_crc;

	if (memcmp(f, "REFT", 4)) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}
	f += 4;

	if (memcmp(footer, header, header_size(t->version))) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}

	f++;
	t->block_size = reftable_get_be24(f);

	f += 3;
	t->min_update_index = reftable_get_be64(f);
	f += 8;
	t->max_update_index = reftable_get_be64(f);
	f += 8;

	if (t->version == 1) {
		t->hash_id = REFTABLE_HASH_SHA1;
	} else {
		switch (reftable_get_be32(f)) {
		case REFTABLE_FORMAT_ID_SHA1:
			t->hash_id = REFTABLE_HASH_SHA1;
			break;
		case REFTABLE_FORMAT_ID_SHA256:
			t->hash_id = REFTABLE_HASH_SHA256;
			break;
		default:
			err = REFTABLE_FORMAT_ERROR;
			goto done;
		}

		f += 4;
	}

	t->ref_offsets.index_offset = reftable_get_be64(f);
	f += 8;

	t->obj_offsets.offset = reftable_get_be64(f);
	f += 8;

	t->object_id_len = t->obj_offsets.offset & ((1 << 5) - 1);
	t->obj_offsets.offset >>= 5;

	t->obj_offsets.index_offset = reftable_get_be64(f);
	f += 8;
	t->log_offsets.offset = reftable_get_be64(f);
	f += 8;
	t->log_offsets.index_offset = reftable_get_be64(f);
	f += 8;

	computed_crc = crc32(0, footer, f - footer);
	file_crc = reftable_get_be32(f);
	f += 4;
	if (computed_crc != file_crc) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}

	first_block_typ = header[header_size(t->version)];
	t->ref_offsets.is_present = (first_block_typ == REFTABLE_BLOCK_TYPE_REF);
	t->ref_offsets.offset = 0;
	t->log_offsets.is_present = (first_block_typ == REFTABLE_BLOCK_TYPE_LOG ||
				     t->log_offsets.offset > 0);
	t->obj_offsets.is_present = t->obj_offsets.offset > 0;
	if (t->obj_offsets.is_present && !t->object_id_len) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}

	err = 0;
done:
	return err;
}

struct table_iter {
	struct reftable_table *table;
	uint8_t typ;
	uint64_t block_off;
	struct reftable_block block;
	struct block_iter bi;
	int is_finished;
};

static int table_iter_init(struct table_iter *ti, struct reftable_table *t)
{
	struct block_iter bi = BLOCK_ITER_INIT;
	memset(ti, 0, sizeof(*ti));
	reftable_table_incref(t);
	ti->table = t;
	ti->bi = bi;
	return 0;
}

static int table_iter_next_in_block(struct table_iter *ti,
				    struct reftable_record *rec)
{
	int res = block_iter_next(&ti->bi, rec);
	if (res == 0 && reftable_record_type(rec) == REFTABLE_BLOCK_TYPE_REF) {
		rec->u.ref.update_index += ti->table->min_update_index;
	}

	return res;
}

static void table_iter_block_done(struct table_iter *ti)
{
	reftable_block_release(&ti->block);
	block_iter_reset(&ti->bi);
}

int table_init_block(struct reftable_table *t, struct reftable_block *block,
		     uint64_t next_off, uint8_t want_typ)
{
	uint32_t header_off = next_off ? 0 : header_size(t->version);
	int err;

	if (next_off >= t->size)
		return 1;

	err = reftable_block_init(block, &t->source, next_off, header_off,
				  t->block_size, hash_size(t->hash_id), want_typ);
	if (err)
		reftable_block_release(block);
	return err;
}

static void table_iter_close(struct table_iter *ti)
{
	table_iter_block_done(ti);
	block_iter_close(&ti->bi);
	reftable_table_decref(ti->table);
}

static int table_iter_next_block(struct table_iter *ti)
{
	uint64_t next_block_off = ti->block_off + ti->block.full_block_size;
	int err;

	err = table_init_block(ti->table, &ti->block, next_block_off, ti->typ);
	if (err > 0)
		ti->is_finished = 1;
	if (err)
		return err;

	ti->block_off = next_block_off;
	ti->is_finished = 0;
	block_iter_init(&ti->bi, &ti->block);

	return 0;
}

static int table_iter_next(struct table_iter *ti, struct reftable_record *rec)
{
	if (reftable_record_type(rec) != ti->typ)
		return REFTABLE_API_ERROR;

	while (1) {
		int err;

		if (ti->is_finished)
			return 1;

		/*
		 * Check whether the current block still has more records. If
		 * so, return it. If the iterator returns positive then the
		 * current block has been exhausted.
		 */
		err = table_iter_next_in_block(ti, rec);
		if (err <= 0)
			return err;

		/*
		 * Otherwise, we need to continue to the next block in the
		 * table and retry. If there are no more blocks then the
		 * iterator is drained.
		 */
		err = table_iter_next_block(ti);
		if (err) {
			ti->is_finished = 1;
			return err;
		}
	}
}

static int table_iter_seek_to(struct table_iter *ti, uint64_t off, uint8_t typ)
{
	int err;

	err = table_init_block(ti->table, &ti->block, off, typ);
	if (err != 0)
		return err;

	ti->typ = reftable_block_type(&ti->block);
	ti->block_off = off;
	block_iter_init(&ti->bi, &ti->block);
	ti->is_finished = 0;
	return 0;
}

static int table_iter_seek_start(struct table_iter *ti, uint8_t typ, int index)
{
	struct reftable_table_offsets *offs = table_offsets_for(ti->table, typ);
	uint64_t off = offs->offset;
	if (index) {
		off = offs->index_offset;
		if (off == 0) {
			return 1;
		}
		typ = REFTABLE_BLOCK_TYPE_INDEX;
	}

	return table_iter_seek_to(ti, off, typ);
}

static int table_iter_seek_linear(struct table_iter *ti,
				  struct reftable_record *want)
{
	struct reftable_buf want_key = REFTABLE_BUF_INIT;
	struct reftable_buf got_key = REFTABLE_BUF_INIT;
	struct reftable_record rec;
	int err;

	err = reftable_record_init(&rec, reftable_record_type(want));
	if (err < 0)
		goto done;

	err = reftable_record_key(want, &want_key);
	if (err < 0)
		goto done;

	/*
	 * First we need to locate the block that must contain our record. To
	 * do so we scan through blocks linearly until we find the first block
	 * whose first key is bigger than our wanted key. Once we have found
	 * that block we know that the key must be contained in the preceding
	 * block.
	 *
	 * This algorithm is somewhat unfortunate because it means that we
	 * always have to seek one block too far and then back up. But as we
	 * can only decode the _first_ key of a block but not its _last_ key we
	 * have no other way to do this.
	 */
	while (1) {
		struct table_iter next = *ti;

		/*
		 * We must be careful to not modify underlying data of `ti`
		 * because we may find that `next` does not contain our desired
		 * block, but that `ti` does. In that case, we would discard
		 * `next` and continue with `ti`.
		 *
		 * This also means that we cannot reuse allocated memory for
		 * `next` here. While it would be great if we could, it should
		 * in practice not be too bad given that we should only ever
		 * end up doing linear seeks with at most three blocks. As soon
		 * as we have more than three blocks we would have an index, so
		 * we would not do a linear search there anymore.
		 */
		memset(&next.block.block_data, 0, sizeof(next.block.block_data));
		next.block.zstream = NULL;
		next.block.uncompressed_data = NULL;
		next.block.uncompressed_cap = 0;

		err = table_iter_next_block(&next);
		if (err < 0)
			goto done;
		if (err > 0)
			break;

		err = reftable_block_first_key(&next.block, &got_key);
		if (err < 0)
			goto done;

		if (reftable_buf_cmp(&got_key, &want_key) > 0) {
			table_iter_block_done(&next);
			break;
		}

		table_iter_block_done(ti);
		*ti = next;
	}

	/*
	 * We have located the block that must contain our record, so we seek
	 * the wanted key inside of it. If the block does not contain our key
	 * we know that the corresponding record does not exist.
	 */
	block_iter_init(&ti->bi, &ti->block);
	err = block_iter_seek_key(&ti->bi, &want_key);
	if (err < 0)
		goto done;
	err = 0;

done:
	reftable_record_release(&rec);
	reftable_buf_release(&want_key);
	reftable_buf_release(&got_key);
	return err;
}

static int table_iter_seek_indexed(struct table_iter *ti,
				   struct reftable_record *rec)
{
	struct reftable_record want_index = {
		.type = REFTABLE_BLOCK_TYPE_INDEX, .u.idx = { .last_key = REFTABLE_BUF_INIT }
	};
	struct reftable_record index_result = {
		.type = REFTABLE_BLOCK_TYPE_INDEX,
		.u.idx = { .last_key = REFTABLE_BUF_INIT },
	};
	int err;

	err = reftable_record_key(rec, &want_index.u.idx.last_key);
	if (err < 0)
		goto done;

	/*
	 * The index may consist of multiple levels, where each level may have
	 * multiple index blocks. We start by doing a linear search in the
	 * highest layer that identifies the relevant index block as well as
	 * the record inside that block that corresponds to our wanted key.
	 */
	err = table_iter_seek_linear(ti, &want_index);
	if (err < 0)
		goto done;

	/*
	 * Traverse down the levels until we find a non-index entry.
	 */
	while (1) {
		/*
		 * In case we seek a record that does not exist the index iter
		 * will tell us that the iterator is over. This works because
		 * the last index entry of the current level will contain the
		 * last key it knows about. So in case our seeked key is larger
		 * than the last indexed key we know that it won't exist.
		 *
		 * There is one subtlety in the layout of the index section
		 * that makes this work as expected: the highest-level index is
		 * at end of the section and will point backwards and thus we
		 * start reading from the end of the index section, not the
		 * beginning.
		 *
		 * If that wasn't the case and the order was reversed then the
		 * linear seek would seek into the lower levels and traverse
		 * all levels of the index only to find out that the key does
		 * not exist.
		 */
		err = table_iter_next(ti, &index_result);
		if (err != 0)
			goto done;

		err = table_iter_seek_to(ti, index_result.u.idx.offset, 0);
		if (err != 0)
			goto done;

		block_iter_init(&ti->bi, &ti->block);

		err = block_iter_seek_key(&ti->bi, &want_index.u.idx.last_key);
		if (err < 0)
			goto done;

		if (ti->typ == reftable_record_type(rec)) {
			err = 0;
			break;
		}

		if (ti->typ != REFTABLE_BLOCK_TYPE_INDEX) {
			err = REFTABLE_FORMAT_ERROR;
			goto done;
		}
	}

done:
	reftable_record_release(&want_index);
	reftable_record_release(&index_result);
	return err;
}

static int table_iter_seek(struct table_iter *ti,
			   struct reftable_record *want)
{
	uint8_t typ = reftable_record_type(want);
	struct reftable_table_offsets *offs = table_offsets_for(ti->table, typ);
	int err;

	err = table_iter_seek_start(ti, reftable_record_type(want),
				    !!offs->index_offset);
	if (err < 0)
		goto out;

	if (offs->index_offset)
		err = table_iter_seek_indexed(ti, want);
	else
		err = table_iter_seek_linear(ti, want);
	if (err)
		goto out;

out:
	return err;
}

static int table_iter_seek_void(void *ti, struct reftable_record *want)
{
	return table_iter_seek(ti, want);
}

static int table_iter_next_void(void *ti, struct reftable_record *rec)
{
	return table_iter_next(ti, rec);
}

static void table_iter_close_void(void *ti)
{
	table_iter_close(ti);
}

static struct reftable_iterator_vtable table_iter_vtable = {
	.seek = &table_iter_seek_void,
	.next = &table_iter_next_void,
	.close = &table_iter_close_void,
};

static void iterator_from_table_iter(struct reftable_iterator *it,
				     struct table_iter *ti)
{
	assert(!it->ops);
	it->iter_arg = ti;
	it->ops = &table_iter_vtable;
}

int table_init_iter(struct reftable_table *t,
		    struct reftable_iterator *it,
		    uint8_t typ)
{
	struct reftable_table_offsets *offs = table_offsets_for(t, typ);

	if (offs->is_present) {
		struct table_iter *ti;
		REFTABLE_ALLOC_ARRAY(ti, 1);
		if (!ti)
			return REFTABLE_OUT_OF_MEMORY_ERROR;

		table_iter_init(ti, t);
		iterator_from_table_iter(it, ti);
	} else {
		iterator_set_empty(it);
	}

	return 0;
}

int reftable_table_init_ref_iterator(struct reftable_table *t,
				     struct reftable_iterator *it)
{
	return table_init_iter(t, it, REFTABLE_BLOCK_TYPE_REF);
}

int reftable_table_init_log_iterator(struct reftable_table *t,
				     struct reftable_iterator *it)
{
	return table_init_iter(t, it, REFTABLE_BLOCK_TYPE_LOG);
}

int reftable_table_new(struct reftable_table **out,
		       struct reftable_block_source *source, char const *name)
{
	struct reftable_block_data footer = { 0 };
	struct reftable_block_data header = { 0 };
	struct reftable_table *t;
	uint64_t file_size = block_source_size(source);
	uint32_t read_size;
	ssize_t bytes_read;
	int err;

	REFTABLE_CALLOC_ARRAY(t, 1);
	if (!t) {
		err = REFTABLE_OUT_OF_MEMORY_ERROR;
		goto done;
	}

	/*
	 * We need one extra byte to read the type of first block. We also
	 * pretend to always be reading v2 of the format because it is larger.
	 */
	read_size = header_size(2) + 1;
	if (read_size > file_size) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}

	bytes_read = block_source_read_data(source, &header, 0, read_size);
	if (bytes_read < 0 || (size_t)bytes_read != read_size) {
		err = REFTABLE_IO_ERROR;
		goto done;
	}

	if (memcmp(header.data, "REFT", 4)) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}
	t->version = header.data[4];
	if (t->version != 1 && t->version != 2) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}

	t->size = file_size - footer_size(t->version);
	t->source = *source;
	t->name = reftable_strdup(name);
	if (!t->name) {
		err = REFTABLE_OUT_OF_MEMORY_ERROR;
		goto done;
	}
	t->hash_id = 0;
	t->refcount = 1;

	bytes_read = block_source_read_data(source, &footer, t->size,
					    footer_size(t->version));
	if (bytes_read < 0 || (size_t)bytes_read != footer_size(t->version)) {
		err = REFTABLE_IO_ERROR;
		goto done;
	}

	err = parse_footer(t, footer.data, header.data);
	if (err)
		goto done;

	*out = t;

done:
	block_source_release_data(&footer);
	block_source_release_data(&header);
	if (err) {
		if (t)
			reftable_free(t->name);
		reftable_free(t);
		block_source_close(source);
	}
	return err;
}

void reftable_table_incref(struct reftable_table *t)
{
	t->refcount++;
}

void reftable_table_decref(struct reftable_table *t)
{
	if (!t)
		return;
	if (--t->refcount)
		return;
	block_source_close(&t->source);
	REFTABLE_FREE_AND_NULL(t->name);
	reftable_free(t);
}

static int reftable_table_refs_for_indexed(struct reftable_table *t,
					   struct reftable_iterator *it,
					   uint8_t *oid)
{
	struct reftable_record want = {
		.type = REFTABLE_BLOCK_TYPE_OBJ,
		.u.obj = {
			.hash_prefix = oid,
			.hash_prefix_len = t->object_id_len,
		},
	};
	struct reftable_iterator oit = { NULL };
	struct reftable_record got = {
		.type = REFTABLE_BLOCK_TYPE_OBJ,
		.u.obj = { 0 },
	};
	int err = 0;
	struct indexed_table_ref_iter *itr = NULL;

	/* Look through the reverse index. */
	err = table_init_iter(t, &oit, REFTABLE_BLOCK_TYPE_OBJ);
	if (err < 0)
		goto done;

	err = iterator_seek(&oit, &want);
	if (err != 0)
		goto done;

	/* read out the reftable_obj_record */
	err = iterator_next(&oit, &got);
	if (err < 0)
		goto done;

	if (err > 0 || memcmp(want.u.obj.hash_prefix, got.u.obj.hash_prefix,
			      t->object_id_len)) {
		/* didn't find it; return empty iterator */
		iterator_set_empty(it);
		err = 0;
		goto done;
	}

	err = indexed_table_ref_iter_new(&itr, t, oid, hash_size(t->hash_id),
					 got.u.obj.offsets,
					 got.u.obj.offset_len);
	if (err < 0)
		goto done;
	got.u.obj.offsets = NULL;
	iterator_from_indexed_table_ref_iter(it, itr);

done:
	reftable_iterator_destroy(&oit);
	reftable_record_release(&got);
	return err;
}

static int reftable_table_refs_for_unindexed(struct reftable_table *t,
					     struct reftable_iterator *it,
					     uint8_t *oid)
{
	struct table_iter *ti;
	struct filtering_ref_iterator *filter = NULL;
	struct filtering_ref_iterator empty = FILTERING_REF_ITERATOR_INIT;
	uint32_t oid_len = hash_size(t->hash_id);
	int err;

	REFTABLE_ALLOC_ARRAY(ti, 1);
	if (!ti) {
		err = REFTABLE_OUT_OF_MEMORY_ERROR;
		goto out;
	}

	table_iter_init(ti, t);
	err = table_iter_seek_start(ti, REFTABLE_BLOCK_TYPE_REF, 0);
	if (err < 0)
		goto out;

	filter = reftable_malloc(sizeof(*filter));
	if (!filter) {
		err = REFTABLE_OUT_OF_MEMORY_ERROR;
		goto out;
	}
	*filter = empty;

	err = reftable_buf_add(&filter->oid, oid, oid_len);
	if (err < 0)
		goto out;

	iterator_from_table_iter(&filter->it, ti);

	iterator_from_filtering_ref_iterator(it, filter);

	err = 0;

out:
	if (err < 0) {
		if (ti)
			table_iter_close(ti);
		reftable_free(ti);
	}
	return err;
}

int reftable_table_refs_for(struct reftable_table *t,
			    struct reftable_iterator *it, uint8_t *oid)
{
	if (t->obj_offsets.is_present)
		return reftable_table_refs_for_indexed(t, it, oid);
	return reftable_table_refs_for_unindexed(t, it, oid);
}

uint64_t reftable_table_max_update_index(struct reftable_table *t)
{
	return t->max_update_index;
}

uint64_t reftable_table_min_update_index(struct reftable_table *t)
{
	return t->min_update_index;
}

int reftable_table_iterator_init(struct reftable_table_iterator *it,
				 struct reftable_table *t)
{
	struct table_iter *ti;
	int err;

	REFTABLE_ALLOC_ARRAY(ti, 1);
	if (!ti)
		return REFTABLE_OUT_OF_MEMORY_ERROR;

	err = table_iter_init(ti, t);
	if (err < 0)
		goto out;

	it->iter_arg = ti;
	err = 0;

out:
	if (err < 0)
		reftable_free(ti);
	return err;
}

void reftable_table_iterator_release(struct reftable_table_iterator *it)
{
	if (!it->iter_arg)
		return;
	table_iter_close(it->iter_arg);
	reftable_free(it->iter_arg);
	it->iter_arg = NULL;
}

int reftable_table_iterator_next(struct reftable_table_iterator *it,
				 const struct reftable_block **out)
{
	struct table_iter *ti = it->iter_arg;
	int err;

	err = table_iter_next_block(ti);
	if (err)
		return err;

	*out = &ti->block;

	return 0;
}