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

#include "blocksource.h"
#include "constants.h"
#include "record.h"
#include "reftable-error.h"
#include "system.h"
#include <zlib.h>

int header_size(int version)
{
	switch (version) {
	case 1:
		return 24;
	case 2:
		return 28;
	}
	abort();
}

int footer_size(int version)
{
	switch (version) {
	case 1:
		return 68;
	case 2:
		return 72;
	}
	abort();
}

static int block_writer_register_restart(struct block_writer *w, int n,
					 int is_restart, struct strbuf *key)
{
	int rlen = w->restart_len;
	if (rlen >= MAX_RESTARTS) {
		is_restart = 0;
	}

	if (is_restart) {
		rlen++;
	}
	if (2 + 3 * rlen + n > w->block_size - w->next)
		return -1;
	if (is_restart) {
		REFTABLE_ALLOC_GROW(w->restarts, w->restart_len + 1, w->restart_cap);
		w->restarts[w->restart_len++] = w->next;
	}

	w->next += n;

	strbuf_reset(&w->last_key);
	strbuf_addbuf(&w->last_key, key);
	w->entries++;
	return 0;
}

void block_writer_init(struct block_writer *bw, uint8_t typ, uint8_t *buf,
		       uint32_t block_size, uint32_t header_off, int hash_size)
{
	bw->buf = buf;
	bw->hash_size = hash_size;
	bw->block_size = block_size;
	bw->header_off = header_off;
	bw->buf[header_off] = typ;
	bw->next = header_off + 4;
	bw->restart_interval = 16;
	bw->entries = 0;
	bw->restart_len = 0;
	bw->last_key.len = 0;
}

uint8_t block_writer_type(struct block_writer *bw)
{
	return bw->buf[bw->header_off];
}

/* Adds the reftable_record to the block. Returns -1 if it does not fit, 0 on
   success. Returns REFTABLE_API_ERROR if attempting to write a record with
   empty key. */
int block_writer_add(struct block_writer *w, struct reftable_record *rec)
{
	struct strbuf empty = STRBUF_INIT;
	struct strbuf last =
		w->entries % w->restart_interval == 0 ? empty : w->last_key;
	struct string_view out = {
		.buf = w->buf + w->next,
		.len = w->block_size - w->next,
	};

	struct string_view start = out;

	int is_restart = 0;
	struct strbuf key = STRBUF_INIT;
	int n = 0;
	int err = -1;

	reftable_record_key(rec, &key);
	if (!key.len) {
		err = REFTABLE_API_ERROR;
		goto done;
	}

	n = reftable_encode_key(&is_restart, out, last, key,
				reftable_record_val_type(rec));
	if (n < 0)
		goto done;
	string_view_consume(&out, n);

	n = reftable_record_encode(rec, out, w->hash_size);
	if (n < 0)
		goto done;
	string_view_consume(&out, n);

	err = block_writer_register_restart(w, start.len - out.len, is_restart,
					    &key);
done:
	strbuf_release(&key);
	return err;
}

int block_writer_finish(struct block_writer *w)
{
	int i;
	for (i = 0; i < w->restart_len; i++) {
		put_be24(w->buf + w->next, w->restarts[i]);
		w->next += 3;
	}

	put_be16(w->buf + w->next, w->restart_len);
	w->next += 2;
	put_be24(w->buf + 1 + w->header_off, w->next);

	if (block_writer_type(w) == BLOCK_TYPE_LOG) {
		int block_header_skip = 4 + w->header_off;
		uLongf src_len = w->next - block_header_skip;
		uLongf dest_cap = src_len * 1.001 + 12;
		uint8_t *compressed;

		REFTABLE_ALLOC_ARRAY(compressed, dest_cap);

		while (1) {
			uLongf out_dest_len = dest_cap;
			int zresult = compress2(compressed, &out_dest_len,
						w->buf + block_header_skip,
						src_len, 9);
			if (zresult == Z_BUF_ERROR && dest_cap < LONG_MAX) {
				dest_cap *= 2;
				compressed =
					reftable_realloc(compressed, dest_cap);
				if (compressed)
					continue;
			}

			if (Z_OK != zresult) {
				reftable_free(compressed);
				return REFTABLE_ZLIB_ERROR;
			}

			memcpy(w->buf + block_header_skip, compressed,
			       out_dest_len);
			w->next = out_dest_len + block_header_skip;
			reftable_free(compressed);
			break;
		}
	}
	return w->next;
}

uint8_t block_reader_type(struct block_reader *r)
{
	return r->block.data[r->header_off];
}

int block_reader_init(struct block_reader *br, struct reftable_block *block,
		      uint32_t header_off, uint32_t table_block_size,
		      int hash_size)
{
	uint32_t full_block_size = table_block_size;
	uint8_t typ = block->data[header_off];
	uint32_t sz = get_be24(block->data + header_off + 1);
	int err = 0;
	uint16_t restart_count = 0;
	uint32_t restart_start = 0;
	uint8_t *restart_bytes = NULL;
	uint8_t *uncompressed = NULL;

	if (!reftable_is_block_type(typ)) {
		err =  REFTABLE_FORMAT_ERROR;
		goto done;
	}

	if (typ == BLOCK_TYPE_LOG) {
		int block_header_skip = 4 + header_off;
		uLongf dst_len = sz - block_header_skip; /* total size of dest
							    buffer. */
		uLongf src_len = block->len - block_header_skip;

		/* Log blocks specify the *uncompressed* size in their header. */
		REFTABLE_ALLOC_ARRAY(uncompressed, sz);

		/* Copy over the block header verbatim. It's not compressed. */
		memcpy(uncompressed, block->data, block_header_skip);

		/* Uncompress */
		if (Z_OK !=
		    uncompress2(uncompressed + block_header_skip, &dst_len,
				block->data + block_header_skip, &src_len)) {
			err = REFTABLE_ZLIB_ERROR;
			goto done;
		}

		if (dst_len + block_header_skip != sz) {
			err = REFTABLE_FORMAT_ERROR;
			goto done;
		}

		/* We're done with the input data. */
		reftable_block_done(block);
		block->data = uncompressed;
		uncompressed = NULL;
		block->len = sz;
		block->source = malloc_block_source();
		full_block_size = src_len + block_header_skip;
	} else if (full_block_size == 0) {
		full_block_size = sz;
	} else if (sz < full_block_size && sz < block->len &&
		   block->data[sz] != 0) {
		/* If the block is smaller than the full block size, it is
		   padded (data followed by '\0') or the next block is
		   unaligned. */
		full_block_size = sz;
	}

	restart_count = get_be16(block->data + sz - 2);
	restart_start = sz - 2 - 3 * restart_count;
	restart_bytes = block->data + restart_start;

	/* transfer ownership. */
	br->block = *block;
	block->data = NULL;
	block->len = 0;

	br->hash_size = hash_size;
	br->block_len = restart_start;
	br->full_block_size = full_block_size;
	br->header_off = header_off;
	br->restart_count = restart_count;
	br->restart_bytes = restart_bytes;

done:
	reftable_free(uncompressed);
	return err;
}

static uint32_t block_reader_restart_offset(struct block_reader *br, int i)
{
	return get_be24(br->restart_bytes + 3 * i);
}

void block_reader_start(struct block_reader *br, struct block_iter *it)
{
	it->br = br;
	strbuf_reset(&it->last_key);
	it->next_off = br->header_off + 4;
}

struct restart_needle_less_args {
	int error;
	struct strbuf needle;
	struct block_reader *reader;
};

static int restart_needle_less(size_t idx, void *_args)
{
	struct restart_needle_less_args *args = _args;
	uint32_t off = block_reader_restart_offset(args->reader, idx);
	struct string_view in = {
		.buf = args->reader->block.data + off,
		.len = args->reader->block_len - off,
	};
	struct strbuf kth_restart_key = STRBUF_INIT;
	uint8_t unused_extra;
	int result, n;

	/*
	 * TODO: The restart key is verbatim in the block, so we can in theory
	 * avoid decoding the key and thus save some allocations.
	 */
	n = reftable_decode_key(&kth_restart_key, &unused_extra, in);
	if (n < 0) {
		args->error = 1;
		return -1;
	}

	result = strbuf_cmp(&args->needle, &kth_restart_key);
	strbuf_release(&kth_restart_key);
	return result < 0;
}

void block_iter_copy_from(struct block_iter *dest, struct block_iter *src)
{
	dest->br = src->br;
	dest->next_off = src->next_off;
	strbuf_reset(&dest->last_key);
	strbuf_addbuf(&dest->last_key, &src->last_key);
}

int block_iter_next(struct block_iter *it, struct reftable_record *rec)
{
	struct string_view in = {
		.buf = it->br->block.data + it->next_off,
		.len = it->br->block_len - it->next_off,
	};
	struct string_view start = in;
	uint8_t extra = 0;
	int n = 0;

	if (it->next_off >= it->br->block_len)
		return 1;

	n = reftable_decode_key(&it->last_key, &extra, in);
	if (n < 0)
		return -1;
	if (!it->last_key.len)
		return REFTABLE_FORMAT_ERROR;

	string_view_consume(&in, n);
	n = reftable_record_decode(rec, it->last_key, extra, in, it->br->hash_size,
				   &it->scratch);
	if (n < 0)
		return -1;
	string_view_consume(&in, n);

	it->next_off += start.len - in.len;
	return 0;
}

int block_reader_first_key(struct block_reader *br, struct strbuf *key)
{
	int off = br->header_off + 4, n;
	struct string_view in = {
		.buf = br->block.data + off,
		.len = br->block_len - off,
	};
	uint8_t extra = 0;

	strbuf_reset(key);

	n = reftable_decode_key(key, &extra, in);
	if (n < 0)
		return n;
	if (!key->len)
		return REFTABLE_FORMAT_ERROR;

	return 0;
}

int block_iter_seek(struct block_iter *it, struct strbuf *want)
{
	return block_reader_seek(it->br, it, want);
}

void block_iter_close(struct block_iter *it)
{
	strbuf_release(&it->last_key);
	strbuf_release(&it->scratch);
}

int block_reader_seek(struct block_reader *br, struct block_iter *it,
		      struct strbuf *want)
{
	struct restart_needle_less_args args = {
		.needle = *want,
		.reader = br,
	};
	struct block_iter next = BLOCK_ITER_INIT;
	struct reftable_record rec;
	int err = 0;
	size_t i;

	if (args.error) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}

	/*
	 * Perform a binary search over the block's restart points, which
	 * avoids doing a linear scan over the whole block. Like this, we
	 * identify the section of the block that should contain our key.
	 *
	 * Note that we explicitly search for the first restart point _greater_
	 * than the sought-after record, not _greater or equal_ to it. In case
	 * the sought-after record is located directly at the restart point we
	 * would otherwise start doing the linear search at the preceding
	 * restart point. While that works alright, we would end up scanning
	 * too many record.
	 */
	i = binsearch(br->restart_count, &restart_needle_less, &args);

	/*
	 * Now there are multiple cases:
	 *
	 *   - `i == 0`: The wanted record is smaller than the record found at
	 *     the first restart point. As the first restart point is the first
	 *     record in the block, our wanted record cannot be located in this
	 *     block at all. We still need to position the iterator so that the
	 *     next call to `block_iter_next()` will yield an end-of-iterator
	 *     signal.
	 *
	 *   - `i == restart_count`: The wanted record was not found at any of
	 *     the restart points. As there is no restart point at the end of
	 *     the section the record may thus be contained in the last block.
	 *
	 *   - `i > 0`: The wanted record must be contained in the section
	 *     before the found restart point. We thus do a linear search
	 *     starting from the preceding restart point.
	 */
	if (i > 0)
		it->next_off = block_reader_restart_offset(br, i - 1);
	else
		it->next_off = br->header_off + 4;
	it->br = br;

	reftable_record_init(&rec, block_reader_type(br));

	/*
	 * We're looking for the last entry less than the wanted key so that
	 * the next call to `block_reader_next()` would yield the wanted
	 * record. We thus don't want to position our reader at the sought
	 * after record, but one before. To do so, we have to go one entry too
	 * far and then back up.
	 */
	while (1) {
		block_iter_copy_from(&next, it);
		err = block_iter_next(&next, &rec);
		if (err < 0)
			goto done;
		if (err > 0) {
			err = 0;
			goto done;
		}

		/*
		 * Check whether the current key is greater or equal to the
		 * sought-after key. In case it is greater we know that the
		 * record does not exist in the block and can thus abort early.
		 * In case it is equal to the sought-after key we have found
		 * the desired record.
		 */
		reftable_record_key(&rec, &it->last_key);
		if (strbuf_cmp(&it->last_key, want) >= 0)
			goto done;

		block_iter_copy_from(it, &next);
	}

done:
	block_iter_close(&next);
	reftable_record_release(&rec);

	return err;
}

void block_writer_release(struct block_writer *bw)
{
	FREE_AND_NULL(bw->restarts);
	strbuf_release(&bw->last_key);
	/* the block is not owned. */
}

void reftable_block_done(struct reftable_block *blockp)
{
	struct reftable_block_source source = blockp->source;
	if (blockp && source.ops)
		source.ops->return_block(source.arg, blockp);
	blockp->data = NULL;
	blockp->len = 0;
	blockp->source.ops = NULL;
	blockp->source.arg = NULL;
}
Commit	Line	Data
e581fd72 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 "block.h"
	10
	11	#include "blocksource.h"
	12	#include "constants.h"
	13	#include "record.h"
	14	#include "reftable-error.h"
	15	#include "system.h"
	16	#include <zlib.h>
	17
	18	int header_size(int version)
	19	{
	20	switch (version) {
	21	case 1:
	22	return 24;
	23	case 2:
	24	return 28;
	25	}
	26	abort();
	27	}
	28
	29	int footer_size(int version)
	30	{
	31	switch (version) {
	32	case 1:
	33	return 68;
	34	case 2:
	35	return 72;
	36	}
	37	abort();
	38	}
	39
	40	static int block_writer_register_restart(struct block_writer *w, int n,
	41	int is_restart, struct strbuf *key)
	42	{
	43	int rlen = w->restart_len;
	44	if (rlen >= MAX_RESTARTS) {
	45	is_restart = 0;
	46	}
	47
	48	if (is_restart) {
	49	rlen++;
	50	}
	51	if (2 + 3 * rlen + n > w->block_size - w->next)
	52	return -1;
	53	if (is_restart) {
f6b58c1b	54	REFTABLE_ALLOC_GROW(w->restarts, w->restart_len + 1, w->restart_cap);
e581fd72 HWN	55	w->restarts[w->restart_len++] = w->next;
	56	}
	57
	58	w->next += n;
	59
	60	strbuf_reset(&w->last_key);
	61	strbuf_addbuf(&w->last_key, key);
	62	w->entries++;
	63	return 0;
	64	}
	65
	66	void block_writer_init(struct block_writer bw, uint8_t typ, uint8_t buf,
	67	uint32_t block_size, uint32_t header_off, int hash_size)
	68	{
	69	bw->buf = buf;
	70	bw->hash_size = hash_size;
	71	bw->block_size = block_size;
	72	bw->header_off = header_off;
	73	bw->buf[header_off] = typ;
	74	bw->next = header_off + 4;
	75	bw->restart_interval = 16;
	76	bw->entries = 0;
	77	bw->restart_len = 0;
	78	bw->last_key.len = 0;
	79	}
	80
	81	uint8_t block_writer_type(struct block_writer *bw)
	82	{
	83	return bw->buf[bw->header_off];
	84	}
	85
45c2fcc2 HWN	86	/* Adds the reftable_record to the block. Returns -1 if it does not fit, 0 on
	87	success. Returns REFTABLE_API_ERROR if attempting to write a record with
	88	empty key. */
e581fd72 HWN	89	int block_writer_add(struct block_writer w, struct reftable_record rec)
	90	{
	91	struct strbuf empty = STRBUF_INIT;
	92	struct strbuf last =
	93	w->entries % w->restart_interval == 0 ? empty : w->last_key;
	94	struct string_view out = {
	95	.buf = w->buf + w->next,
	96	.len = w->block_size - w->next,
	97	};
	98
	99	struct string_view start = out;
	100
	101	int is_restart = 0;
	102	struct strbuf key = STRBUF_INIT;
	103	int n = 0;
45c2fcc2	104	int err = -1;
e581fd72 HWN	105
e581fd72 HWN	106	reftable_record_key(rec, &key);
45c2fcc2 HWN	107	if (!key.len) {
	108	err = REFTABLE_API_ERROR;
	109	goto done;
	110	}
	111
e581fd72 HWN	112	n = reftable_encode_key(&is_restart, out, last, key,
	113	reftable_record_val_type(rec));
	114	if (n < 0)
	115	goto done;
	116	string_view_consume(&out, n);
	117
	118	n = reftable_record_encode(rec, out, w->hash_size);
	119	if (n < 0)
	120	goto done;
	121	string_view_consume(&out, n);
	122
45c2fcc2 HWN	123	err = block_writer_register_restart(w, start.len - out.len, is_restart,
45c2fcc2 HWN	124	&key);
e581fd72 HWN	125	done:
e581fd72 HWN	126	strbuf_release(&key);
45c2fcc2	127	return err;
e581fd72 HWN	128	}
	129
	130	int block_writer_finish(struct block_writer *w)
	131	{
	132	int i;
	133	for (i = 0; i < w->restart_len; i++) {
	134	put_be24(w->buf + w->next, w->restarts[i]);
	135	w->next += 3;
	136	}
	137
	138	put_be16(w->buf + w->next, w->restart_len);
	139	w->next += 2;
	140	put_be24(w->buf + 1 + w->header_off, w->next);
	141
	142	if (block_writer_type(w) == BLOCK_TYPE_LOG) {
	143	int block_header_skip = 4 + w->header_off;
	144	uLongf src_len = w->next - block_header_skip;
	145	uLongf dest_cap = src_len * 1.001 + 12;
b4ff12c8 PS	146	uint8_t *compressed;
	147
	148	REFTABLE_ALLOC_ARRAY(compressed, dest_cap);
e581fd72	149
e581fd72 HWN	150	while (1) {
	151	uLongf out_dest_len = dest_cap;
	152	int zresult = compress2(compressed, &out_dest_len,
	153	w->buf + block_header_skip,
	154	src_len, 9);
	155	if (zresult == Z_BUF_ERROR && dest_cap < LONG_MAX) {
	156	dest_cap *= 2;
	157	compressed =
	158	reftable_realloc(compressed, dest_cap);
	159	if (compressed)
	160	continue;
	161	}
	162
	163	if (Z_OK != zresult) {
	164	reftable_free(compressed);
	165	return REFTABLE_ZLIB_ERROR;
	166	}
	167
	168	memcpy(w->buf + block_header_skip, compressed,
	169	out_dest_len);
	170	w->next = out_dest_len + block_header_skip;
	171	reftable_free(compressed);
	172	break;
	173	}
	174	}
	175	return w->next;
	176	}
	177
	178	uint8_t block_reader_type(struct block_reader *r)
	179	{
	180	return r->block.data[r->header_off];
	181	}
	182
	183	int block_reader_init(struct block_reader br, struct reftable_block block,
	184	uint32_t header_off, uint32_t table_block_size,
	185	int hash_size)
	186	{
	187	uint32_t full_block_size = table_block_size;
	188	uint8_t typ = block->data[header_off];
	189	uint32_t sz = get_be24(block->data + header_off + 1);
24d4d38c	190	int err = 0;
e581fd72 HWN	191	uint16_t restart_count = 0;
	192	uint32_t restart_start = 0;
	193	uint8_t *restart_bytes = NULL;
24d4d38c	194	uint8_t *uncompressed = NULL;
e581fd72	195
24d4d38c HWN	196	if (!reftable_is_block_type(typ)) {
	197	err = REFTABLE_FORMAT_ERROR;
	198	goto done;
	199	}
e581fd72 HWN	200
	201	if (typ == BLOCK_TYPE_LOG) {
	202	int block_header_skip = 4 + header_off;
	203	uLongf dst_len = sz - block_header_skip; /* total size of dest
	204	buffer. */
	205	uLongf src_len = block->len - block_header_skip;
b4ff12c8 PS	206
	207	/* Log blocks specify the uncompressed size in their header. */
	208	REFTABLE_ALLOC_ARRAY(uncompressed, sz);
e581fd72 HWN	209
	210	/* Copy over the block header verbatim. It's not compressed. */
	211	memcpy(uncompressed, block->data, block_header_skip);
	212
	213	/* Uncompress */
	214	if (Z_OK !=
	215	uncompress2(uncompressed + block_header_skip, &dst_len,
	216	block->data + block_header_skip, &src_len)) {
24d4d38c HWN	217	err = REFTABLE_ZLIB_ERROR;
24d4d38c HWN	218	goto done;
e581fd72 HWN	219	}
e581fd72 HWN	220
24d4d38c HWN	221	if (dst_len + block_header_skip != sz) {
	222	err = REFTABLE_FORMAT_ERROR;
	223	goto done;
	224	}
e581fd72 HWN	225
	226	/* We're done with the input data. */
	227	reftable_block_done(block);
	228	block->data = uncompressed;
24d4d38c	229	uncompressed = NULL;
e581fd72 HWN	230	block->len = sz;
	231	block->source = malloc_block_source();
	232	full_block_size = src_len + block_header_skip;
	233	} else if (full_block_size == 0) {
	234	full_block_size = sz;
	235	} else if (sz < full_block_size && sz < block->len &&
	236	block->data[sz] != 0) {
	237	/* If the block is smaller than the full block size, it is
	238	padded (data followed by '\0') or the next block is
	239	unaligned. */
	240	full_block_size = sz;
	241	}
	242
	243	restart_count = get_be16(block->data + sz - 2);
	244	restart_start = sz - 2 - 3 * restart_count;
	245	restart_bytes = block->data + restart_start;
	246
	247	/* transfer ownership. */
	248	br->block = *block;
	249	block->data = NULL;
	250	block->len = 0;
	251
	252	br->hash_size = hash_size;
	253	br->block_len = restart_start;
	254	br->full_block_size = full_block_size;
	255	br->header_off = header_off;
	256	br->restart_count = restart_count;
	257	br->restart_bytes = restart_bytes;
	258
24d4d38c HWN	259	done:
	260	reftable_free(uncompressed);
	261	return err;
e581fd72 HWN	262	}
	263
	264	static uint32_t block_reader_restart_offset(struct block_reader *br, int i)
	265	{
	266	return get_be24(br->restart_bytes + 3 * i);
	267	}
	268
	269	void block_reader_start(struct block_reader br, struct block_iter it)
	270	{
	271	it->br = br;
	272	strbuf_reset(&it->last_key);
	273	it->next_off = br->header_off + 4;
	274	}
	275
77307a61	276	struct restart_needle_less_args {
e581fd72	277	int error;
77307a61 PS	278	struct strbuf needle;
77307a61 PS	279	struct block_reader *reader;
e581fd72 HWN	280	};
e581fd72 HWN	281
77307a61	282	static int restart_needle_less(size_t idx, void *_args)
e581fd72	283	{
77307a61 PS	284	struct restart_needle_less_args *args = _args;
77307a61 PS	285	uint32_t off = block_reader_restart_offset(args->reader, idx);
e581fd72	286	struct string_view in = {
77307a61 PS	287	.buf = args->reader->block.data + off,
77307a61 PS	288	.len = args->reader->block_len - off,
e581fd72	289	};
77307a61	290	struct strbuf kth_restart_key = STRBUF_INIT;
e581fd72	291	uint8_t unused_extra;
77307a61 PS	292	int result, n;
	293
	294	/*
	295	* TODO: The restart key is verbatim in the block, so we can in theory
	296	* avoid decoding the key and thus save some allocations.
	297	*/
	298	n = reftable_decode_key(&kth_restart_key, &unused_extra, in);
e581fd72	299	if (n < 0) {
77307a61	300	args->error = 1;
e581fd72 HWN	301	return -1;
	302	}
	303
77307a61 PS	304	result = strbuf_cmp(&args->needle, &kth_restart_key);
77307a61 PS	305	strbuf_release(&kth_restart_key);
fffd981e	306	return result < 0;
e581fd72 HWN	307	}
	308
	309	void block_iter_copy_from(struct block_iter dest, struct block_iter src)
	310	{
	311	dest->br = src->br;
	312	dest->next_off = src->next_off;
	313	strbuf_reset(&dest->last_key);
	314	strbuf_addbuf(&dest->last_key, &src->last_key);
	315	}
	316
	317	int block_iter_next(struct block_iter it, struct reftable_record rec)
	318	{
	319	struct string_view in = {
	320	.buf = it->br->block.data + it->next_off,
	321	.len = it->br->block_len - it->next_off,
	322	};
	323	struct string_view start = in;
e581fd72 HWN	324	uint8_t extra = 0;
	325	int n = 0;
	326
	327	if (it->next_off >= it->br->block_len)
	328	return 1;
	329
daf4f43d	330	n = reftable_decode_key(&it->last_key, &extra, in);
e581fd72 HWN	331	if (n < 0)
e581fd72 HWN	332	return -1;
daf4f43d	333	if (!it->last_key.len)
45c2fcc2 HWN	334	return REFTABLE_FORMAT_ERROR;
45c2fcc2 HWN	335
e581fd72	336	string_view_consume(&in, n);
7b8abc4d PS	337	n = reftable_record_decode(rec, it->last_key, extra, in, it->br->hash_size,
7b8abc4d PS	338	&it->scratch);
e581fd72 HWN	339	if (n < 0)
	340	return -1;
	341	string_view_consume(&in, n);
	342
e581fd72	343	it->next_off += start.len - in.len;
e581fd72 HWN	344	return 0;
	345	}
	346
	347	int block_reader_first_key(struct block_reader br, struct strbuf key)
	348	{
daf4f43d	349	int off = br->header_off + 4, n;
e581fd72 HWN	350	struct string_view in = {
	351	.buf = br->block.data + off,
	352	.len = br->block_len - off,
	353	};
e581fd72	354	uint8_t extra = 0;
daf4f43d PS	355
	356	strbuf_reset(key);
	357
	358	n = reftable_decode_key(key, &extra, in);
e581fd72 HWN	359	if (n < 0)
e581fd72 HWN	360	return n;
45c2fcc2 HWN	361	if (!key->len)
45c2fcc2 HWN	362	return REFTABLE_FORMAT_ERROR;
e581fd72 HWN	363
	364	return 0;
	365	}
	366
	367	int block_iter_seek(struct block_iter it, struct strbuf want)
	368	{
	369	return block_reader_seek(it->br, it, want);
	370	}
	371
	372	void block_iter_close(struct block_iter *it)
	373	{
	374	strbuf_release(&it->last_key);
7b8abc4d	375	strbuf_release(&it->scratch);
e581fd72 HWN	376	}
	377
	378	int block_reader_seek(struct block_reader br, struct block_iter it,
	379	struct strbuf *want)
	380	{
77307a61 PS	381	struct restart_needle_less_args args = {
	382	.needle = *want,
	383	.reader = br,
e581fd72	384	};
a8305bc6	385	struct block_iter next = BLOCK_ITER_INIT;
3ddef475	386	struct reftable_record rec;
3e7b36d1 PS	387	int err = 0;
3e7b36d1 PS	388	size_t i;
e581fd72	389
e581fd72 HWN	390	if (args.error) {
	391	err = REFTABLE_FORMAT_ERROR;
	392	goto done;
	393	}
	394
77307a61 PS	395	/*
	396	* Perform a binary search over the block's restart points, which
	397	* avoids doing a linear scan over the whole block. Like this, we
	398	* identify the section of the block that should contain our key.
	399	*
	400	* Note that we explicitly search for the first restart point _greater_
	401	* than the sought-after record, not _greater or equal_ to it. In case
	402	* the sought-after record is located directly at the restart point we
	403	* would otherwise start doing the linear search at the preceding
	404	* restart point. While that works alright, we would end up scanning
	405	* too many record.
	406	*/
	407	i = binsearch(br->restart_count, &restart_needle_less, &args);
	408
	409	/*
	410	* Now there are multiple cases:
	411	*
	412	* - `i == 0`: The wanted record is smaller than the record found at
	413	* the first restart point. As the first restart point is the first
	414	* record in the block, our wanted record cannot be located in this
	415	* block at all. We still need to position the iterator so that the
	416	* next call to `block_iter_next()` will yield an end-of-iterator
	417	* signal.
	418	*
	419	* - `i == restart_count`: The wanted record was not found at any of
	420	* the restart points. As there is no restart point at the end of
	421	* the section the record may thus be contained in the last block.
	422	*
	423	* - `i > 0`: The wanted record must be contained in the section
	424	* before the found restart point. We thus do a linear search
	425	* starting from the preceding restart point.
	426	*/
3ddef475 PS	427	if (i > 0)
	428	it->next_off = block_reader_restart_offset(br, i - 1);
	429	else
e581fd72	430	it->next_off = br->header_off + 4;
3ddef475 PS	431	it->br = br;
	432
	433	reftable_record_init(&rec, block_reader_type(br));
e581fd72	434
77307a61 PS	435	/*
	436	* We're looking for the last entry less than the wanted key so that
	437	* the next call to `block_reader_next()` would yield the wanted
	438	* record. We thus don't want to position our reader at the sought
	439	* after record, but one before. To do so, we have to go one entry too
	440	* far and then back up.
	441	*/
e581fd72 HWN	442	while (1) {
	443	block_iter_copy_from(&next, it);
	444	err = block_iter_next(&next, &rec);
	445	if (err < 0)
	446	goto done;
77307a61	447	if (err > 0) {
e581fd72 HWN	448	err = 0;
	449	goto done;
	450	}
	451
77307a61 PS	452	/*
	453	* Check whether the current key is greater or equal to the
	454	* sought-after key. In case it is greater we know that the
	455	* record does not exist in the block and can thus abort early.
	456	* In case it is equal to the sought-after key we have found
	457	* the desired record.
	458	*/
	459	reftable_record_key(&rec, &it->last_key);
	460	if (strbuf_cmp(&it->last_key, want) >= 0)
	461	goto done;
	462
e581fd72 HWN	463	block_iter_copy_from(it, &next);
	464	}
	465
	466	done:
c0cadb05	467	block_iter_close(&next);
66c0daba	468	reftable_record_release(&rec);
e581fd72 HWN	469
	470	return err;
	471	}
	472
	473	void block_writer_release(struct block_writer *bw)
	474	{
	475	FREE_AND_NULL(bw->restarts);
	476	strbuf_release(&bw->last_key);
	477	/* the block is not owned. */
	478	}
	479
	480	void reftable_block_done(struct reftable_block *blockp)
	481	{
	482	struct reftable_block_source source = blockp->source;
	483	if (blockp && source.ops)
	484	source.ops->return_block(source.arg, blockp);
	485	blockp->data = NULL;
	486	blockp->len = 0;
	487	blockp->source.ops = NULL;
	488	blockp->source.arg = NULL;
	489	}