[thirdparty/git.git] / reftable / reader.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 "reader.h"

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

uint64_t block_source_size(struct reftable_block_source *source)
{
	return source->ops->size(source->arg);
}

int block_source_read_block(struct reftable_block_source *source,
			    struct reftable_block *dest, uint64_t off,
			    uint32_t size)
{
	int result = source->ops->read_block(source->arg, dest, off, size);
	dest->source = *source;
	return result;
}

void block_source_close(struct reftable_block_source *source)
{
	if (!source->ops) {
		return;
	}

	source->ops->close(source->arg);
	source->ops = NULL;
}

static struct reftable_reader_offsets *
reader_offsets_for(struct reftable_reader *r, uint8_t typ)
{
	switch (typ) {
	case BLOCK_TYPE_REF:
		return &r->ref_offsets;
	case BLOCK_TYPE_LOG:
		return &r->log_offsets;
	case BLOCK_TYPE_OBJ:
		return &r->obj_offsets;
	}
	abort();
}

static int reader_get_block(struct reftable_reader *r,
			    struct reftable_block *dest, uint64_t off,
			    uint32_t sz)
{
	if (off >= r->size)
		return 0;

	if (off + sz > r->size) {
		sz = r->size - off;
	}

	return block_source_read_block(&r->source, dest, off, sz);
}

uint32_t reftable_reader_hash_id(struct reftable_reader *r)
{
	return r->hash_id;
}

const char *reader_name(struct reftable_reader *r)
{
	return r->name;
}

static int parse_footer(struct reftable_reader *r, 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(r->version))) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}

	f++;
	r->block_size = get_be24(f);

	f += 3;
	r->min_update_index = get_be64(f);
	f += 8;
	r->max_update_index = get_be64(f);
	f += 8;

	if (r->version == 1) {
		r->hash_id = GIT_SHA1_FORMAT_ID;
	} else {
		r->hash_id = get_be32(f);
		switch (r->hash_id) {
		case GIT_SHA1_FORMAT_ID:
			break;
		case GIT_SHA256_FORMAT_ID:
			break;
		default:
			err = REFTABLE_FORMAT_ERROR;
			goto done;
		}
		f += 4;
	}

	r->ref_offsets.index_offset = get_be64(f);
	f += 8;

	r->obj_offsets.offset = get_be64(f);
	f += 8;

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

	r->obj_offsets.index_offset = get_be64(f);
	f += 8;
	r->log_offsets.offset = get_be64(f);
	f += 8;
	r->log_offsets.index_offset = get_be64(f);
	f += 8;

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

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

	err = 0;
done:
	return err;
}

int init_reader(struct reftable_reader *r, struct reftable_block_source *source,
		const char *name)
{
	struct reftable_block footer = { NULL };
	struct reftable_block header = { NULL };
	int err = 0;
	uint64_t file_size = block_source_size(source);

	/* Need +1 to read type of first block. */
	uint32_t read_size = header_size(2) + 1; /* read v2 because it's larger.  */
	memset(r, 0, sizeof(struct reftable_reader));

	if (read_size > file_size) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}

	err = block_source_read_block(source, &header, 0, read_size);
	if (err != read_size) {
		err = REFTABLE_IO_ERROR;
		goto done;
	}

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

	r->size = file_size - footer_size(r->version);
	r->source = *source;
	r->name = xstrdup(name);
	r->hash_id = 0;

	err = block_source_read_block(source, &footer, r->size,
				      footer_size(r->version));
	if (err != footer_size(r->version)) {
		err = REFTABLE_IO_ERROR;
		goto done;
	}

	err = parse_footer(r, footer.data, header.data);
done:
	reftable_block_done(&footer);
	reftable_block_done(&header);
	return err;
}

struct table_iter {
	struct reftable_reader *r;
	uint8_t typ;
	uint64_t block_off;
	struct block_iter bi;
	int is_finished;
};
#define TABLE_ITER_INIT { \
	.bi = BLOCK_ITER_INIT \
}

static void table_iter_copy_from(struct table_iter *dest,
				 struct table_iter *src)
{
	dest->r = src->r;
	dest->typ = src->typ;
	dest->block_off = src->block_off;
	dest->is_finished = src->is_finished;
	block_iter_copy_from(&dest->bi, &src->bi);
}

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) == BLOCK_TYPE_REF) {
		rec->u.ref.update_index += ti->r->min_update_index;
	}

	return res;
}

static void table_iter_block_done(struct table_iter *ti)
{
	if (!ti->bi.br) {
		return;
	}
	reftable_block_done(&ti->bi.br->block);
	FREE_AND_NULL(ti->bi.br);

	ti->bi.last_key.len = 0;
	ti->bi.next_off = 0;
}

static int32_t extract_block_size(uint8_t *data, uint8_t *typ, uint64_t off,
				  int version)
{
	int32_t result = 0;

	if (off == 0) {
		data += header_size(version);
	}

	*typ = data[0];
	if (reftable_is_block_type(*typ)) {
		result = get_be24(data + 1);
	}
	return result;
}

int reader_init_block_reader(struct reftable_reader *r, struct block_reader *br,
			     uint64_t next_off, uint8_t want_typ)
{
	int32_t guess_block_size = r->block_size ? r->block_size :
							 DEFAULT_BLOCK_SIZE;
	struct reftable_block block = { NULL };
	uint8_t block_typ = 0;
	int err = 0;
	uint32_t header_off = next_off ? 0 : header_size(r->version);
	int32_t block_size = 0;

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

	err = reader_get_block(r, &block, next_off, guess_block_size);
	if (err < 0)
		goto done;

	block_size = extract_block_size(block.data, &block_typ, next_off,
					r->version);
	if (block_size < 0) {
		err = block_size;
		goto done;
	}
	if (want_typ != BLOCK_TYPE_ANY && block_typ != want_typ) {
		err = 1;
		goto done;
	}

	if (block_size > guess_block_size) {
		reftable_block_done(&block);
		err = reader_get_block(r, &block, next_off, block_size);
		if (err < 0) {
			goto done;
		}
	}

	err = block_reader_init(br, &block, header_off, r->block_size,
				hash_size(r->hash_id));
done:
	reftable_block_done(&block);

	return err;
}

static int table_iter_next_block(struct table_iter *dest,
				 struct table_iter *src)
{
	uint64_t next_block_off = src->block_off + src->bi.br->full_block_size;
	struct block_reader br = { 0 };
	int err = 0;

	dest->r = src->r;
	dest->typ = src->typ;
	dest->block_off = next_block_off;

	err = reader_init_block_reader(src->r, &br, next_block_off, src->typ);
	if (err > 0) {
		dest->is_finished = 1;
		return 1;
	}
	if (err != 0)
		return err;
	else {
		struct block_reader *brp =
			reftable_malloc(sizeof(struct block_reader));
		*brp = br;

		dest->is_finished = 0;
		block_reader_start(brp, &dest->bi);
	}
	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) {
		struct table_iter next = TABLE_ITER_INIT;
		int err = 0;
		if (ti->is_finished) {
			return 1;
		}

		err = table_iter_next_in_block(ti, rec);
		if (err <= 0) {
			return err;
		}

		err = table_iter_next_block(&next, ti);
		if (err != 0) {
			ti->is_finished = 1;
		}
		table_iter_block_done(ti);
		if (err != 0) {
			return err;
		}
		table_iter_copy_from(ti, &next);
		block_iter_close(&next.bi);
	}
}

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

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

static struct reftable_iterator_vtable table_iter_vtable = {
	.next = &table_iter_next_void,
	.close = &table_iter_close,
};

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;
}

static int reader_table_iter_at(struct reftable_reader *r,
				struct table_iter *ti, uint64_t off,
				uint8_t typ)
{
	struct block_reader br = { 0 };
	struct block_reader *brp = NULL;

	int err = reader_init_block_reader(r, &br, off, typ);
	if (err != 0)
		return err;

	brp = reftable_malloc(sizeof(struct block_reader));
	*brp = br;
	ti->r = r;
	ti->typ = block_reader_type(brp);
	ti->block_off = off;
	block_reader_start(brp, &ti->bi);
	return 0;
}

static int reader_start(struct reftable_reader *r, struct table_iter *ti,
			uint8_t typ, int index)
{
	struct reftable_reader_offsets *offs = reader_offsets_for(r, typ);
	uint64_t off = offs->offset;
	if (index) {
		off = offs->index_offset;
		if (off == 0) {
			return 1;
		}
		typ = BLOCK_TYPE_INDEX;
	}

	return reader_table_iter_at(r, ti, off, typ);
}

static int reader_seek_linear(struct table_iter *ti,
			      struct reftable_record *want)
{
	struct reftable_record rec =
		reftable_new_record(reftable_record_type(want));
	struct strbuf want_key = STRBUF_INIT;
	struct strbuf got_key = STRBUF_INIT;
	struct table_iter next = TABLE_ITER_INIT;
	int err = -1;

	reftable_record_key(want, &want_key);

	while (1) {
		err = table_iter_next_block(&next, ti);
		if (err < 0)
			goto done;

		if (err > 0) {
			break;
		}

		err = block_reader_first_key(next.bi.br, &got_key);
		if (err < 0)
			goto done;

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

		table_iter_block_done(ti);
		table_iter_copy_from(ti, &next);
	}

	err = block_iter_seek(&ti->bi, &want_key);
	if (err < 0)
		goto done;
	err = 0;

done:
	block_iter_close(&next.bi);
	reftable_record_release(&rec);
	strbuf_release(&want_key);
	strbuf_release(&got_key);
	return err;
}

static int reader_seek_indexed(struct reftable_reader *r,
			       struct reftable_iterator *it,
			       struct reftable_record *rec)
{
	struct reftable_record want_index = {
		.type = BLOCK_TYPE_INDEX, .u.idx = { .last_key = STRBUF_INIT }
	};
	struct reftable_record index_result = {
		.type = BLOCK_TYPE_INDEX,
		.u.idx = { .last_key = STRBUF_INIT },
	};
	struct table_iter index_iter = TABLE_ITER_INIT;
	struct table_iter next = TABLE_ITER_INIT;
	int err = 0;

	reftable_record_key(rec, &want_index.u.idx.last_key);
	err = reader_start(r, &index_iter, reftable_record_type(rec), 1);
	if (err < 0)
		goto done;

	err = reader_seek_linear(&index_iter, &want_index);
	while (1) {
		err = table_iter_next(&index_iter, &index_result);
		table_iter_block_done(&index_iter);
		if (err != 0)
			goto done;

		err = reader_table_iter_at(r, &next, index_result.u.idx.offset,
					   0);
		if (err != 0)
			goto done;

		err = block_iter_seek(&next.bi, &want_index.u.idx.last_key);
		if (err < 0)
			goto done;

		if (next.typ == reftable_record_type(rec)) {
			err = 0;
			break;
		}

		if (next.typ != BLOCK_TYPE_INDEX) {
			err = REFTABLE_FORMAT_ERROR;
			break;
		}

		table_iter_copy_from(&index_iter, &next);
	}

	if (err == 0) {
		struct table_iter empty = TABLE_ITER_INIT;
		struct table_iter *malloced =
			reftable_calloc(sizeof(struct table_iter));
		*malloced = empty;
		table_iter_copy_from(malloced, &next);
		iterator_from_table_iter(it, malloced);
	}
done:
	block_iter_close(&next.bi);
	table_iter_close(&index_iter);
	reftable_record_release(&want_index);
	reftable_record_release(&index_result);
	return err;
}

static int reader_seek_internal(struct reftable_reader *r,
				struct reftable_iterator *it,
				struct reftable_record *rec)
{
	struct reftable_reader_offsets *offs =
		reader_offsets_for(r, reftable_record_type(rec));
	uint64_t idx = offs->index_offset;
	struct table_iter ti = TABLE_ITER_INIT;
	int err = 0;
	if (idx > 0)
		return reader_seek_indexed(r, it, rec);

	err = reader_start(r, &ti, reftable_record_type(rec), 0);
	if (err < 0)
		return err;
	err = reader_seek_linear(&ti, rec);
	if (err < 0)
		return err;
	else {
		struct table_iter *p =
			reftable_malloc(sizeof(struct table_iter));
		*p = ti;
		iterator_from_table_iter(it, p);
	}

	return 0;
}

static int reader_seek(struct reftable_reader *r, struct reftable_iterator *it,
		       struct reftable_record *rec)
{
	uint8_t typ = reftable_record_type(rec);

	struct reftable_reader_offsets *offs = reader_offsets_for(r, typ);
	if (!offs->is_present) {
		iterator_set_empty(it);
		return 0;
	}

	return reader_seek_internal(r, it, rec);
}

int reftable_reader_seek_ref(struct reftable_reader *r,
			     struct reftable_iterator *it, const char *name)
{
	struct reftable_record rec = {
		.type = BLOCK_TYPE_REF,
		.u.ref = {
			.refname = (char *)name,
		},
	};
	return reader_seek(r, it, &rec);
}

int reftable_reader_seek_log_at(struct reftable_reader *r,
				struct reftable_iterator *it, const char *name,
				uint64_t update_index)
{
	struct reftable_record rec = { .type = BLOCK_TYPE_LOG,
				       .u.log = {
					       .refname = (char *)name,
					       .update_index = update_index,
				       } };
	return reader_seek(r, it, &rec);
}

int reftable_reader_seek_log(struct reftable_reader *r,
			     struct reftable_iterator *it, const char *name)
{
	uint64_t max = ~((uint64_t)0);
	return reftable_reader_seek_log_at(r, it, name, max);
}

void reader_close(struct reftable_reader *r)
{
	block_source_close(&r->source);
	FREE_AND_NULL(r->name);
}

int reftable_new_reader(struct reftable_reader **p,
			struct reftable_block_source *src, char const *name)
{
	struct reftable_reader *rd =
		reftable_calloc(sizeof(struct reftable_reader));
	int err = init_reader(rd, src, name);
	if (err == 0) {
		*p = rd;
	} else {
		block_source_close(src);
		reftable_free(rd);
	}
	return err;
}

void reftable_reader_free(struct reftable_reader *r)
{
	if (!r)
		return;
	reader_close(r);
	reftable_free(r);
}

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

	/* Look through the reverse index. */
	err = reader_seek(r, &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,
			      r->object_id_len)) {
		/* didn't find it; return empty iterator */
		iterator_set_empty(it);
		err = 0;
		goto done;
	}

	err = new_indexed_table_ref_iter(&itr, r, oid, hash_size(r->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_reader_refs_for_unindexed(struct reftable_reader *r,
					      struct reftable_iterator *it,
					      uint8_t *oid)
{
	struct table_iter ti_empty = TABLE_ITER_INIT;
	struct table_iter *ti = reftable_calloc(sizeof(struct table_iter));
	struct filtering_ref_iterator *filter = NULL;
	struct filtering_ref_iterator empty = FILTERING_REF_ITERATOR_INIT;
	int oid_len = hash_size(r->hash_id);
	int err;

	*ti = ti_empty;
	err = reader_start(r, ti, BLOCK_TYPE_REF, 0);
	if (err < 0) {
		reftable_free(ti);
		return err;
	}

	filter = reftable_malloc(sizeof(struct filtering_ref_iterator));
	*filter = empty;

	strbuf_add(&filter->oid, oid, oid_len);
	reftable_table_from_reader(&filter->tab, r);
	filter->double_check = 0;
	iterator_from_table_iter(&filter->it, ti);

	iterator_from_filtering_ref_iterator(it, filter);
	return 0;
}

int reftable_reader_refs_for(struct reftable_reader *r,
			     struct reftable_iterator *it, uint8_t *oid)
{
	if (r->obj_offsets.is_present)
		return reftable_reader_refs_for_indexed(r, it, oid);
	return reftable_reader_refs_for_unindexed(r, it, oid);
}

uint64_t reftable_reader_max_update_index(struct reftable_reader *r)
{
	return r->max_update_index;
}

uint64_t reftable_reader_min_update_index(struct reftable_reader *r)
{
	return r->min_update_index;
}

/* generic table interface. */

static int reftable_reader_seek_void(void *tab, struct reftable_iterator *it,
				     struct reftable_record *rec)
{
	return reader_seek(tab, it, rec);
}

static uint32_t reftable_reader_hash_id_void(void *tab)
{
	return reftable_reader_hash_id(tab);
}

static uint64_t reftable_reader_min_update_index_void(void *tab)
{
	return reftable_reader_min_update_index(tab);
}

static uint64_t reftable_reader_max_update_index_void(void *tab)
{
	return reftable_reader_max_update_index(tab);
}

static struct reftable_table_vtable reader_vtable = {
	.seek_record = reftable_reader_seek_void,
	.hash_id = reftable_reader_hash_id_void,
	.min_update_index = reftable_reader_min_update_index_void,
	.max_update_index = reftable_reader_max_update_index_void,
};

void reftable_table_from_reader(struct reftable_table *tab,
				struct reftable_reader *reader)
{
	assert(!tab->ops);
	tab->ops = &reader_vtable;
	tab->table_arg = reader;
}


int reftable_reader_print_file(const char *tablename)
{
	struct reftable_block_source src = { NULL };
	int err = reftable_block_source_from_file(&src, tablename);
	struct reftable_reader *r = NULL;
	struct reftable_table tab = { NULL };
	if (err < 0)
		goto done;

	err = reftable_new_reader(&r, &src, tablename);
	if (err < 0)
		goto done;

	reftable_table_from_reader(&tab, r);
	err = reftable_table_print(&tab);
done:
	reftable_reader_free(r);
	return err;
}
Commit	Line	Data
46bc0e73 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 "reader.h"
	10
	11	#include "system.h"
	12	#include "block.h"
	13	#include "constants.h"
	14	#include "generic.h"
	15	#include "iter.h"
	16	#include "record.h"
	17	#include "reftable-error.h"
	18	#include "reftable-generic.h"
	19	#include "tree.h"
	20
	21	uint64_t block_source_size(struct reftable_block_source *source)
	22	{
	23	return source->ops->size(source->arg);
	24	}
	25
	26	int block_source_read_block(struct reftable_block_source *source,
	27	struct reftable_block *dest, uint64_t off,
	28	uint32_t size)
	29	{
	30	int result = source->ops->read_block(source->arg, dest, off, size);
	31	dest->source = *source;
	32	return result;
	33	}
	34
	35	void block_source_close(struct reftable_block_source *source)
	36	{
	37	if (!source->ops) {
	38	return;
	39	}
	40
	41	source->ops->close(source->arg);
	42	source->ops = NULL;
	43	}
	44
	45	static struct reftable_reader_offsets *
	46	reader_offsets_for(struct reftable_reader *r, uint8_t typ)
	47	{
	48	switch (typ) {
	49	case BLOCK_TYPE_REF:
	50	return &r->ref_offsets;
	51	case BLOCK_TYPE_LOG:
	52	return &r->log_offsets;
	53	case BLOCK_TYPE_OBJ:
	54	return &r->obj_offsets;
	55	}
	56	abort();
	57	}
	58
	59	static int reader_get_block(struct reftable_reader *r,
	60	struct reftable_block *dest, uint64_t off,
	61	uint32_t sz)
	62	{
	63	if (off >= r->size)
	64	return 0;
65
66	if (off + sz > r->size) {
67	sz = r->size - off;
68	}
69
70	return block_source_read_block(&r->source, dest, off, sz);
71	}
72
73	uint32_t reftable_reader_hash_id(struct reftable_reader *r)
74	{
75	return r->hash_id;
76	}
77
78	const char reader_name(struct reftable_reader r)
79	{
80	return r->name;
81	}
82
83	static int parse_footer(struct reftable_reader r, uint8_t footer,
84	uint8_t *header)
85	{
86	uint8_t *f = footer;
87	uint8_t first_block_typ;
88	int err = 0;
89	uint32_t computed_crc;
90	uint32_t file_crc;
91
92	if (memcmp(f, "REFT", 4)) {
93	err = REFTABLE_FORMAT_ERROR;
94	goto done;
95	}
96	f += 4;
97
98	if (memcmp(footer, header, header_size(r->version))) {
99	err = REFTABLE_FORMAT_ERROR;
100	goto done;
101	}
102
103	f++;
104	r->block_size = get_be24(f);
105
106	f += 3;
107	r->min_update_index = get_be64(f);
108	f += 8;
109	r->max_update_index = get_be64(f);
110	f += 8;
111
112	if (r->version == 1) {
113	r->hash_id = GIT_SHA1_FORMAT_ID;
114	} else {
115	r->hash_id = get_be32(f);
116	switch (r->hash_id) {
117	case GIT_SHA1_FORMAT_ID:
118	break;
119	case GIT_SHA256_FORMAT_ID:
120	break;
121	default:
122	err = REFTABLE_FORMAT_ERROR;
123	goto done;
124	}
125	f += 4;
126	}
127
128	r->ref_offsets.index_offset = get_be64(f);
129	f += 8;
130
131	r->obj_offsets.offset = get_be64(f);
132	f += 8;
133
134	r->object_id_len = r->obj_offsets.offset & ((1 << 5) - 1);
135	r->obj_offsets.offset >>= 5;
136
137	r->obj_offsets.index_offset = get_be64(f);
138	f += 8;
139	r->log_offsets.offset = get_be64(f);
140	f += 8;
141	r->log_offsets.index_offset = get_be64(f);
142	f += 8;
143
144	computed_crc = crc32(0, footer, f - footer);
145	file_crc = get_be32(f);
146	f += 4;
147	if (computed_crc != file_crc) {
148	err = REFTABLE_FORMAT_ERROR;
149	goto done;
150	}
151
152	first_block_typ = header[header_size(r->version)];
153	r->ref_offsets.is_present = (first_block_typ == BLOCK_TYPE_REF);
154	r->ref_offsets.offset = 0;
155	r->log_offsets.is_present = (first_block_typ == BLOCK_TYPE_LOG \|\|
156	r->log_offsets.offset > 0);
157	r->obj_offsets.is_present = r->obj_offsets.offset > 0;
eff5832b HWN	158	if (r->obj_offsets.is_present && !r->object_id_len) {
	159	err = REFTABLE_FORMAT_ERROR;
	160	goto done;
	161	}
	162
46bc0e73 HWN	163	err = 0;
	164	done:
	165	return err;
	166	}
	167
	168	int init_reader(struct reftable_reader r, struct reftable_block_source source,
	169	const char *name)
	170	{
	171	struct reftable_block footer = { NULL };
	172	struct reftable_block header = { NULL };
	173	int err = 0;
	174	uint64_t file_size = block_source_size(source);
	175
	176	/* Need +1 to read type of first block. */
	177	uint32_t read_size = header_size(2) + 1; /* read v2 because it's larger. */
	178	memset(r, 0, sizeof(struct reftable_reader));
	179
	180	if (read_size > file_size) {
	181	err = REFTABLE_FORMAT_ERROR;
	182	goto done;
	183	}
	184
	185	err = block_source_read_block(source, &header, 0, read_size);
	186	if (err != read_size) {
	187	err = REFTABLE_IO_ERROR;
	188	goto done;
	189	}
	190
	191	if (memcmp(header.data, "REFT", 4)) {
	192	err = REFTABLE_FORMAT_ERROR;
	193	goto done;
	194	}
	195	r->version = header.data[4];
	196	if (r->version != 1 && r->version != 2) {
	197	err = REFTABLE_FORMAT_ERROR;
	198	goto done;
	199	}
	200
	201	r->size = file_size - footer_size(r->version);
	202	r->source = *source;
	203	r->name = xstrdup(name);
	204	r->hash_id = 0;
	205
	206	err = block_source_read_block(source, &footer, r->size,
	207	footer_size(r->version));
	208	if (err != footer_size(r->version)) {
	209	err = REFTABLE_IO_ERROR;
	210	goto done;
	211	}
	212
	213	err = parse_footer(r, footer.data, header.data);
	214	done:
	215	reftable_block_done(&footer);
	216	reftable_block_done(&header);
	217	return err;
	218	}
	219
	220	struct table_iter {
	221	struct reftable_reader *r;
	222	uint8_t typ;
	223	uint64_t block_off;
	224	struct block_iter bi;
	225	int is_finished;
	226	};
a8305bc6 PS	227	#define TABLE_ITER_INIT { \
	228	.bi = BLOCK_ITER_INIT \
	229	}
46bc0e73 HWN	230
	231	static void table_iter_copy_from(struct table_iter *dest,
	232	struct table_iter *src)
	233	{
	234	dest->r = src->r;
	235	dest->typ = src->typ;
	236	dest->block_off = src->block_off;
	237	dest->is_finished = src->is_finished;
	238	block_iter_copy_from(&dest->bi, &src->bi);
	239	}
	240
	241	static int table_iter_next_in_block(struct table_iter *ti,
	242	struct reftable_record *rec)
	243	{
	244	int res = block_iter_next(&ti->bi, rec);
	245	if (res == 0 && reftable_record_type(rec) == BLOCK_TYPE_REF) {
66c0daba	246	rec->u.ref.update_index += ti->r->min_update_index;
46bc0e73 HWN	247	}
	248
	249	return res;
	250	}
	251
	252	static void table_iter_block_done(struct table_iter *ti)
	253	{
	254	if (!ti->bi.br) {
	255	return;
	256	}
	257	reftable_block_done(&ti->bi.br->block);
	258	FREE_AND_NULL(ti->bi.br);
	259
	260	ti->bi.last_key.len = 0;
	261	ti->bi.next_off = 0;
	262	}
	263
	264	static int32_t extract_block_size(uint8_t data, uint8_t typ, uint64_t off,
	265	int version)
	266	{
	267	int32_t result = 0;
	268
	269	if (off == 0) {
	270	data += header_size(version);
	271	}
	272
	273	*typ = data[0];
	274	if (reftable_is_block_type(*typ)) {
	275	result = get_be24(data + 1);
	276	}
	277	return result;
	278	}
	279
	280	int reader_init_block_reader(struct reftable_reader r, struct block_reader br,
	281	uint64_t next_off, uint8_t want_typ)
	282	{
	283	int32_t guess_block_size = r->block_size ? r->block_size :
	284	DEFAULT_BLOCK_SIZE;
	285	struct reftable_block block = { NULL };
	286	uint8_t block_typ = 0;
	287	int err = 0;
	288	uint32_t header_off = next_off ? 0 : header_size(r->version);
	289	int32_t block_size = 0;
	290
	291	if (next_off >= r->size)
	292	return 1;
	293
	294	err = reader_get_block(r, &block, next_off, guess_block_size);
	295	if (err < 0)
24d4d38c	296	goto done;
46bc0e73 HWN	297
	298	block_size = extract_block_size(block.data, &block_typ, next_off,
	299	r->version);
24d4d38c HWN	300	if (block_size < 0) {
	301	err = block_size;
	302	goto done;
	303	}
46bc0e73	304	if (want_typ != BLOCK_TYPE_ANY && block_typ != want_typ) {
24d4d38c HWN	305	err = 1;
24d4d38c HWN	306	goto done;
46bc0e73 HWN	307	}
	308
	309	if (block_size > guess_block_size) {
	310	reftable_block_done(&block);
	311	err = reader_get_block(r, &block, next_off, block_size);
	312	if (err < 0) {
24d4d38c	313	goto done;
46bc0e73 HWN	314	}
	315	}
	316
24d4d38c HWN	317	err = block_reader_init(br, &block, header_off, r->block_size,
	318	hash_size(r->hash_id));
	319	done:
	320	reftable_block_done(&block);
	321
	322	return err;
46bc0e73 HWN	323	}
	324
	325	static int table_iter_next_block(struct table_iter *dest,
	326	struct table_iter *src)
	327	{
	328	uint64_t next_block_off = src->block_off + src->bi.br->full_block_size;
	329	struct block_reader br = { 0 };
	330	int err = 0;
	331
	332	dest->r = src->r;
	333	dest->typ = src->typ;
	334	dest->block_off = next_block_off;
	335
	336	err = reader_init_block_reader(src->r, &br, next_block_off, src->typ);
	337	if (err > 0) {
	338	dest->is_finished = 1;
	339	return 1;
	340	}
	341	if (err != 0)
	342	return err;
	343	else {
	344	struct block_reader *brp =
	345	reftable_malloc(sizeof(struct block_reader));
	346	*brp = br;
	347
	348	dest->is_finished = 0;
	349	block_reader_start(brp, &dest->bi);
	350	}
	351	return 0;
	352	}
	353
	354	static int table_iter_next(struct table_iter ti, struct reftable_record rec)
	355	{
	356	if (reftable_record_type(rec) != ti->typ)
	357	return REFTABLE_API_ERROR;
	358
	359	while (1) {
	360	struct table_iter next = TABLE_ITER_INIT;
	361	int err = 0;
	362	if (ti->is_finished) {
	363	return 1;
	364	}
	365
	366	err = table_iter_next_in_block(ti, rec);
	367	if (err <= 0) {
	368	return err;
	369	}
	370
	371	err = table_iter_next_block(&next, ti);
	372	if (err != 0) {
	373	ti->is_finished = 1;
	374	}
	375	table_iter_block_done(ti);
	376	if (err != 0) {
	377	return err;
	378	}
	379	table_iter_copy_from(ti, &next);
	380	block_iter_close(&next.bi);
	381	}
	382	}
	383
	384	static int table_iter_next_void(void ti, struct reftable_record rec)
	385	{
	386	return table_iter_next(ti, rec);
387	}
388
389	static void table_iter_close(void *p)
390	{
391	struct table_iter *ti = p;
392	table_iter_block_done(ti);
393	block_iter_close(&ti->bi);
394	}
395
396	static struct reftable_iterator_vtable table_iter_vtable = {
397	.next = &table_iter_next_void,
398	.close = &table_iter_close,
399	};
400
401	static void iterator_from_table_iter(struct reftable_iterator *it,
402	struct table_iter *ti)
403	{
404	assert(!it->ops);
405	it->iter_arg = ti;
406	it->ops = &table_iter_vtable;
407	}
408
409	static int reader_table_iter_at(struct reftable_reader *r,
410	struct table_iter *ti, uint64_t off,
411	uint8_t typ)
412	{
413	struct block_reader br = { 0 };
414	struct block_reader *brp = NULL;
415
416	int err = reader_init_block_reader(r, &br, off, typ);
417	if (err != 0)
418	return err;
419
420	brp = reftable_malloc(sizeof(struct block_reader));
421	*brp = br;
422	ti->r = r;
423	ti->typ = block_reader_type(brp);
424	ti->block_off = off;
425	block_reader_start(brp, &ti->bi);
426	return 0;
427	}
428
429	static int reader_start(struct reftable_reader r, struct table_iter ti,
430	uint8_t typ, int index)
431	{
432	struct reftable_reader_offsets *offs = reader_offsets_for(r, typ);
433	uint64_t off = offs->offset;
434	if (index) {
435	off = offs->index_offset;
436	if (off == 0) {
437	return 1;
438	}
439	typ = BLOCK_TYPE_INDEX;
440	}
441
442	return reader_table_iter_at(r, ti, off, typ);
443	}
444
21a40847	445	static int reader_seek_linear(struct table_iter *ti,
46bc0e73 HWN	446	struct reftable_record *want)
	447	{
	448	struct reftable_record rec =
	449	reftable_new_record(reftable_record_type(want));
	450	struct strbuf want_key = STRBUF_INIT;
	451	struct strbuf got_key = STRBUF_INIT;
	452	struct table_iter next = TABLE_ITER_INIT;
	453	int err = -1;
	454
	455	reftable_record_key(want, &want_key);
	456
	457	while (1) {
	458	err = table_iter_next_block(&next, ti);
	459	if (err < 0)
	460	goto done;
	461
	462	if (err > 0) {
	463	break;
	464	}
	465
	466	err = block_reader_first_key(next.bi.br, &got_key);
	467	if (err < 0)
	468	goto done;
	469
	470	if (strbuf_cmp(&got_key, &want_key) > 0) {
	471	table_iter_block_done(&next);
	472	break;
	473	}
	474
	475	table_iter_block_done(ti);
	476	table_iter_copy_from(ti, &next);
	477	}
	478
	479	err = block_iter_seek(&ti->bi, &want_key);
	480	if (err < 0)
	481	goto done;
	482	err = 0;
	483
	484	done:
	485	block_iter_close(&next.bi);
66c0daba	486	reftable_record_release(&rec);
46bc0e73 HWN	487	strbuf_release(&want_key);
	488	strbuf_release(&got_key);
	489	return err;
	490	}
	491
	492	static int reader_seek_indexed(struct reftable_reader *r,
	493	struct reftable_iterator *it,
	494	struct reftable_record *rec)
	495	{
66c0daba HWN	496	struct reftable_record want_index = {
	497	.type = BLOCK_TYPE_INDEX, .u.idx = { .last_key = STRBUF_INIT }
	498	};
	499	struct reftable_record index_result = {
	500	.type = BLOCK_TYPE_INDEX,
	501	.u.idx = { .last_key = STRBUF_INIT },
	502	};
46bc0e73 HWN	503	struct table_iter index_iter = TABLE_ITER_INIT;
	504	struct table_iter next = TABLE_ITER_INIT;
	505	int err = 0;
	506
66c0daba	507	reftable_record_key(rec, &want_index.u.idx.last_key);
46bc0e73 HWN	508	err = reader_start(r, &index_iter, reftable_record_type(rec), 1);
	509	if (err < 0)
	510	goto done;
	511
21a40847	512	err = reader_seek_linear(&index_iter, &want_index);
46bc0e73	513	while (1) {
66c0daba	514	err = table_iter_next(&index_iter, &index_result);
46bc0e73 HWN	515	table_iter_block_done(&index_iter);
	516	if (err != 0)
	517	goto done;
	518
66c0daba HWN	519	err = reader_table_iter_at(r, &next, index_result.u.idx.offset,
66c0daba HWN	520	0);
46bc0e73 HWN	521	if (err != 0)
	522	goto done;
	523
66c0daba	524	err = block_iter_seek(&next.bi, &want_index.u.idx.last_key);
46bc0e73 HWN	525	if (err < 0)
	526	goto done;
	527
	528	if (next.typ == reftable_record_type(rec)) {
	529	err = 0;
	530	break;
	531	}
	532
	533	if (next.typ != BLOCK_TYPE_INDEX) {
	534	err = REFTABLE_FORMAT_ERROR;
	535	break;
	536	}
	537
	538	table_iter_copy_from(&index_iter, &next);
	539	}
	540
	541	if (err == 0) {
	542	struct table_iter empty = TABLE_ITER_INIT;
	543	struct table_iter *malloced =
	544	reftable_calloc(sizeof(struct table_iter));
	545	*malloced = empty;
	546	table_iter_copy_from(malloced, &next);
	547	iterator_from_table_iter(it, malloced);
	548	}
	549	done:
	550	block_iter_close(&next.bi);
	551	table_iter_close(&index_iter);
66c0daba HWN	552	reftable_record_release(&want_index);
66c0daba HWN	553	reftable_record_release(&index_result);
46bc0e73 HWN	554	return err;
	555	}
	556
	557	static int reader_seek_internal(struct reftable_reader *r,
	558	struct reftable_iterator *it,
	559	struct reftable_record *rec)
	560	{
	561	struct reftable_reader_offsets *offs =
	562	reader_offsets_for(r, reftable_record_type(rec));
	563	uint64_t idx = offs->index_offset;
	564	struct table_iter ti = TABLE_ITER_INIT;
	565	int err = 0;
	566	if (idx > 0)
	567	return reader_seek_indexed(r, it, rec);
	568
	569	err = reader_start(r, &ti, reftable_record_type(rec), 0);
	570	if (err < 0)
	571	return err;
21a40847	572	err = reader_seek_linear(&ti, rec);
46bc0e73 HWN	573	if (err < 0)
	574	return err;
	575	else {
	576	struct table_iter *p =
	577	reftable_malloc(sizeof(struct table_iter));
	578	*p = ti;
	579	iterator_from_table_iter(it, p);
	580	}
	581
	582	return 0;
	583	}
	584
	585	static int reader_seek(struct reftable_reader r, struct reftable_iterator it,
	586	struct reftable_record *rec)
	587	{
	588	uint8_t typ = reftable_record_type(rec);
	589
	590	struct reftable_reader_offsets *offs = reader_offsets_for(r, typ);
	591	if (!offs->is_present) {
	592	iterator_set_empty(it);
	593	return 0;
	594	}
	595
	596	return reader_seek_internal(r, it, rec);
	597	}
	598
	599	int reftable_reader_seek_ref(struct reftable_reader *r,
	600	struct reftable_iterator it, const char name)
	601	{
66c0daba HWN	602	struct reftable_record rec = {
	603	.type = BLOCK_TYPE_REF,
	604	.u.ref = {
	605	.refname = (char *)name,
	606	},
46bc0e73	607	};
46bc0e73 HWN	608	return reader_seek(r, it, &rec);
	609	}
	610
	611	int reftable_reader_seek_log_at(struct reftable_reader *r,
	612	struct reftable_iterator it, const char name,
	613	uint64_t update_index)
	614	{
66c0daba HWN	615	struct reftable_record rec = { .type = BLOCK_TYPE_LOG,
	616	.u.log = {
	617	.refname = (char *)name,
	618	.update_index = update_index,
	619	} };
46bc0e73 HWN	620	return reader_seek(r, it, &rec);
	621	}
	622
	623	int reftable_reader_seek_log(struct reftable_reader *r,
	624	struct reftable_iterator it, const char name)
	625	{
	626	uint64_t max = ~((uint64_t)0);
	627	return reftable_reader_seek_log_at(r, it, name, max);
	628	}
	629
	630	void reader_close(struct reftable_reader *r)
	631	{
	632	block_source_close(&r->source);
	633	FREE_AND_NULL(r->name);
	634	}
	635
	636	int reftable_new_reader(struct reftable_reader **p,
	637	struct reftable_block_source src, char const name)
	638	{
	639	struct reftable_reader *rd =
	640	reftable_calloc(sizeof(struct reftable_reader));
	641	int err = init_reader(rd, src, name);
	642	if (err == 0) {
	643	*p = rd;
	644	} else {
	645	block_source_close(src);
	646	reftable_free(rd);
	647	}
	648	return err;
	649	}
	650
	651	void reftable_reader_free(struct reftable_reader *r)
	652	{
33e92243 HWN	653	if (!r)
33e92243 HWN	654	return;
46bc0e73 HWN	655	reader_close(r);
	656	reftable_free(r);
	657	}
	658
	659	static int reftable_reader_refs_for_indexed(struct reftable_reader *r,
	660	struct reftable_iterator *it,
	661	uint8_t *oid)
	662	{
66c0daba HWN	663	struct reftable_record want = {
	664	.type = BLOCK_TYPE_OBJ,
	665	.u.obj = {
	666	.hash_prefix = oid,
	667	.hash_prefix_len = r->object_id_len,
	668	},
46bc0e73	669	};
46bc0e73	670	struct reftable_iterator oit = { NULL };
66c0daba HWN	671	struct reftable_record got = {
	672	.type = BLOCK_TYPE_OBJ,
	673	.u.obj = { 0 },
	674	};
46bc0e73 HWN	675	int err = 0;
	676	struct indexed_table_ref_iter *itr = NULL;
	677
	678	/* Look through the reverse index. */
66c0daba	679	err = reader_seek(r, &oit, &want);
46bc0e73 HWN	680	if (err != 0)
	681	goto done;
	682
	683	/* read out the reftable_obj_record */
66c0daba	684	err = iterator_next(&oit, &got);
46bc0e73 HWN	685	if (err < 0)
	686	goto done;
	687
66c0daba HWN	688	if (err > 0 \|\| memcmp(want.u.obj.hash_prefix, got.u.obj.hash_prefix,
66c0daba HWN	689	r->object_id_len)) {
46bc0e73 HWN	690	/* didn't find it; return empty iterator */
	691	iterator_set_empty(it);
	692	err = 0;
	693	goto done;
	694	}
	695
	696	err = new_indexed_table_ref_iter(&itr, r, oid, hash_size(r->hash_id),
66c0daba HWN	697	got.u.obj.offsets,
66c0daba HWN	698	got.u.obj.offset_len);
46bc0e73 HWN	699	if (err < 0)
46bc0e73 HWN	700	goto done;
66c0daba	701	got.u.obj.offsets = NULL;
46bc0e73 HWN	702	iterator_from_indexed_table_ref_iter(it, itr);
	703
	704	done:
	705	reftable_iterator_destroy(&oit);
66c0daba	706	reftable_record_release(&got);
46bc0e73 HWN	707	return err;
	708	}
	709
	710	static int reftable_reader_refs_for_unindexed(struct reftable_reader *r,
	711	struct reftable_iterator *it,
	712	uint8_t *oid)
	713	{
	714	struct table_iter ti_empty = TABLE_ITER_INIT;
	715	struct table_iter *ti = reftable_calloc(sizeof(struct table_iter));
	716	struct filtering_ref_iterator *filter = NULL;
	717	struct filtering_ref_iterator empty = FILTERING_REF_ITERATOR_INIT;
	718	int oid_len = hash_size(r->hash_id);
	719	int err;
	720
	721	*ti = ti_empty;
	722	err = reader_start(r, ti, BLOCK_TYPE_REF, 0);
	723	if (err < 0) {
	724	reftable_free(ti);
	725	return err;
	726	}
	727
	728	filter = reftable_malloc(sizeof(struct filtering_ref_iterator));
	729	*filter = empty;
	730
	731	strbuf_add(&filter->oid, oid, oid_len);
	732	reftable_table_from_reader(&filter->tab, r);
	733	filter->double_check = 0;
	734	iterator_from_table_iter(&filter->it, ti);
	735
	736	iterator_from_filtering_ref_iterator(it, filter);
	737	return 0;
	738	}
	739
	740	int reftable_reader_refs_for(struct reftable_reader *r,
	741	struct reftable_iterator it, uint8_t oid)
	742	{
	743	if (r->obj_offsets.is_present)
	744	return reftable_reader_refs_for_indexed(r, it, oid);
	745	return reftable_reader_refs_for_unindexed(r, it, oid);
	746	}
	747
	748	uint64_t reftable_reader_max_update_index(struct reftable_reader *r)
	749	{
	750	return r->max_update_index;
	751	}
	752
	753	uint64_t reftable_reader_min_update_index(struct reftable_reader *r)
	754	{
	755	return r->min_update_index;
	756	}
	757
	758	/* generic table interface. */
	759
	760	static int reftable_reader_seek_void(void tab, struct reftable_iterator it,
	761	struct reftable_record *rec)
	762	{
	763	return reader_seek(tab, it, rec);
	764	}
	765
	766	static uint32_t reftable_reader_hash_id_void(void *tab)
	767	{
	768	return reftable_reader_hash_id(tab);
	769	}
	770
771	static uint64_t reftable_reader_min_update_index_void(void *tab)
772	{
773	return reftable_reader_min_update_index(tab);
774	}
775
776	static uint64_t reftable_reader_max_update_index_void(void *tab)
777	{
778	return reftable_reader_max_update_index(tab);
779	}
780
781	static struct reftable_table_vtable reader_vtable = {
782	.seek_record = reftable_reader_seek_void,
783	.hash_id = reftable_reader_hash_id_void,
784	.min_update_index = reftable_reader_min_update_index_void,
785	.max_update_index = reftable_reader_max_update_index_void,
786	};
787
788	void reftable_table_from_reader(struct reftable_table *tab,
789	struct reftable_reader *reader)
790	{
791	assert(!tab->ops);
792	tab->ops = &reader_vtable;
793	tab->table_arg = reader;
794	}
795
796
797	int reftable_reader_print_file(const char *tablename)
798	{
799	struct reftable_block_source src = { NULL };
800	int err = reftable_block_source_from_file(&src, tablename);
801	struct reftable_reader *r = NULL;
802	struct reftable_table tab = { NULL };
803	if (err < 0)
804	goto done;
805
806	err = reftable_new_reader(&r, &src, tablename);
807	if (err < 0)
808	goto done;
809
810	reftable_table_from_reader(&tab, r);
811	err = reftable_table_print(&tab);
812	done:
813	reftable_reader_free(r);
814	return err;
815	}