[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) {
		if (w->restart_len == w->restart_cap) {
			w->restart_cap = w->restart_cap * 2 + 1;
			w->restarts = reftable_realloc(
				w->restarts, sizeof(uint32_t) * 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_malloc(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.
		 */
		uncompressed = reftable_malloc(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_find_args {
	int error;
	struct strbuf key;
	struct block_reader *r;
};

static int restart_key_less(size_t idx, void *args)
{
	struct restart_find_args *a = args;
	uint32_t off = block_reader_restart_offset(a->r, idx);
	struct string_view in = {
		.buf = a->r->block.data + off,
		.len = a->r->block_len - off,
	};

	/* the restart key is verbatim in the block, so this could avoid the
	   alloc for decoding the key */
	struct strbuf rkey = STRBUF_INIT;
	struct strbuf last_key = STRBUF_INIT;
	uint8_t unused_extra;
	int n = reftable_decode_key(&rkey, &unused_extra, last_key, in);
	int result;
	if (n < 0) {
		a->error = 1;
		return -1;
	}

	result = strbuf_cmp(&a->key, &rkey);
	strbuf_release(&rkey);
	return result;
}

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->key, &extra, it->last_key, in);
	if (n < 0)
		return -1;

	if (!it->key.len)
		return REFTABLE_FORMAT_ERROR;

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

	strbuf_reset(&it->last_key);
	strbuf_addbuf(&it->last_key, &it->key);
	it->next_off += start.len - in.len;
	return 0;
}

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

	uint8_t extra = 0;
	int n = reftable_decode_key(key, &extra, empty, 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->key);
}

int block_reader_seek(struct block_reader *br, struct block_iter *it,
		      struct strbuf *want)
{
	struct restart_find_args args = {
		.key = *want,
		.r = br,
	};
	struct reftable_record rec = reftable_new_record(block_reader_type(br));
	int err = 0;
	struct block_iter next = BLOCK_ITER_INIT;

	int i = binsearch(br->restart_count, &restart_key_less, &args);
	if (args.error) {
		err = REFTABLE_FORMAT_ERROR;
		goto done;
	}

	it->br = br;
	if (i > 0) {
		i--;
		it->next_off = block_reader_restart_offset(br, i);
	} else {
		it->next_off = br->header_off + 4;
	}

	/* We're looking for the last entry less/equal than the wanted key, 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;

		reftable_record_key(&rec, &it->key);
		if (err > 0 || strbuf_cmp(&it->key, want) >= 0) {
			err = 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) {
	54	if (w->restart_len == w->restart_cap) {
	55	w->restart_cap = w->restart_cap * 2 + 1;
	56	w->restarts = reftable_realloc(
	57	w->restarts, sizeof(uint32_t) * w->restart_cap);
	58	}
	59
	60	w->restarts[w->restart_len++] = w->next;
	61	}
	62
	63	w->next += n;
	64
65	strbuf_reset(&w->last_key);
66	strbuf_addbuf(&w->last_key, key);
67	w->entries++;
68	return 0;
69	}
70
71	void block_writer_init(struct block_writer bw, uint8_t typ, uint8_t buf,
72	uint32_t block_size, uint32_t header_off, int hash_size)
73	{
74	bw->buf = buf;
75	bw->hash_size = hash_size;
76	bw->block_size = block_size;
77	bw->header_off = header_off;
78	bw->buf[header_off] = typ;
79	bw->next = header_off + 4;
80	bw->restart_interval = 16;
81	bw->entries = 0;
82	bw->restart_len = 0;
83	bw->last_key.len = 0;
84	}
85
86	uint8_t block_writer_type(struct block_writer *bw)
87	{
88	return bw->buf[bw->header_off];
89	}
90
45c2fcc2 HWN	91	/* Adds the reftable_record to the block. Returns -1 if it does not fit, 0 on
	92	success. Returns REFTABLE_API_ERROR if attempting to write a record with
	93	empty key. */
e581fd72 HWN	94	int block_writer_add(struct block_writer w, struct reftable_record rec)
	95	{
	96	struct strbuf empty = STRBUF_INIT;
	97	struct strbuf last =
	98	w->entries % w->restart_interval == 0 ? empty : w->last_key;
	99	struct string_view out = {
	100	.buf = w->buf + w->next,
	101	.len = w->block_size - w->next,
	102	};
	103
	104	struct string_view start = out;
	105
	106	int is_restart = 0;
	107	struct strbuf key = STRBUF_INIT;
	108	int n = 0;
45c2fcc2	109	int err = -1;
e581fd72 HWN	110
e581fd72 HWN	111	reftable_record_key(rec, &key);
45c2fcc2 HWN	112	if (!key.len) {
	113	err = REFTABLE_API_ERROR;
	114	goto done;
	115	}
	116
e581fd72 HWN	117	n = reftable_encode_key(&is_restart, out, last, key,
	118	reftable_record_val_type(rec));
	119	if (n < 0)
	120	goto done;
	121	string_view_consume(&out, n);
	122
	123	n = reftable_record_encode(rec, out, w->hash_size);
	124	if (n < 0)
	125	goto done;
	126	string_view_consume(&out, n);
	127
45c2fcc2 HWN	128	err = block_writer_register_restart(w, start.len - out.len, is_restart,
45c2fcc2 HWN	129	&key);
e581fd72 HWN	130	done:
e581fd72 HWN	131	strbuf_release(&key);
45c2fcc2	132	return err;
e581fd72 HWN	133	}
	134
	135	int block_writer_finish(struct block_writer *w)
	136	{
	137	int i;
	138	for (i = 0; i < w->restart_len; i++) {
	139	put_be24(w->buf + w->next, w->restarts[i]);
	140	w->next += 3;
	141	}
	142
	143	put_be16(w->buf + w->next, w->restart_len);
	144	w->next += 2;
	145	put_be24(w->buf + 1 + w->header_off, w->next);
	146
	147	if (block_writer_type(w) == BLOCK_TYPE_LOG) {
	148	int block_header_skip = 4 + w->header_off;
	149	uLongf src_len = w->next - block_header_skip;
	150	uLongf dest_cap = src_len * 1.001 + 12;
	151
	152	uint8_t *compressed = reftable_malloc(dest_cap);
	153	while (1) {
	154	uLongf out_dest_len = dest_cap;
	155	int zresult = compress2(compressed, &out_dest_len,
	156	w->buf + block_header_skip,
	157	src_len, 9);
	158	if (zresult == Z_BUF_ERROR && dest_cap < LONG_MAX) {
	159	dest_cap *= 2;
	160	compressed =
	161	reftable_realloc(compressed, dest_cap);
	162	if (compressed)
	163	continue;
	164	}
	165
	166	if (Z_OK != zresult) {
	167	reftable_free(compressed);
	168	return REFTABLE_ZLIB_ERROR;
	169	}
	170
	171	memcpy(w->buf + block_header_skip, compressed,
	172	out_dest_len);
	173	w->next = out_dest_len + block_header_skip;
	174	reftable_free(compressed);
	175	break;
	176	}
	177	}
	178	return w->next;
	179	}
	180
	181	uint8_t block_reader_type(struct block_reader *r)
	182	{
	183	return r->block.data[r->header_off];
	184	}
	185
	186	int block_reader_init(struct block_reader br, struct reftable_block block,
	187	uint32_t header_off, uint32_t table_block_size,
	188	int hash_size)
	189	{
	190	uint32_t full_block_size = table_block_size;
	191	uint8_t typ = block->data[header_off];
	192	uint32_t sz = get_be24(block->data + header_off + 1);
24d4d38c	193	int err = 0;
e581fd72 HWN	194	uint16_t restart_count = 0;
	195	uint32_t restart_start = 0;
	196	uint8_t *restart_bytes = NULL;
24d4d38c	197	uint8_t *uncompressed = NULL;
e581fd72	198
24d4d38c HWN	199	if (!reftable_is_block_type(typ)) {
	200	err = REFTABLE_FORMAT_ERROR;
	201	goto done;
	202	}
e581fd72 HWN	203
	204	if (typ == BLOCK_TYPE_LOG) {
	205	int block_header_skip = 4 + header_off;
	206	uLongf dst_len = sz - block_header_skip; /* total size of dest
	207	buffer. */
	208	uLongf src_len = block->len - block_header_skip;
	209	/* Log blocks specify the uncompressed size in their header.
	210	*/
24d4d38c	211	uncompressed = reftable_malloc(sz);
e581fd72 HWN	212
	213	/* Copy over the block header verbatim. It's not compressed. */
	214	memcpy(uncompressed, block->data, block_header_skip);
	215
	216	/* Uncompress */
	217	if (Z_OK !=
	218	uncompress2(uncompressed + block_header_skip, &dst_len,
	219	block->data + block_header_skip, &src_len)) {
24d4d38c HWN	220	err = REFTABLE_ZLIB_ERROR;
24d4d38c HWN	221	goto done;
e581fd72 HWN	222	}
e581fd72 HWN	223
24d4d38c HWN	224	if (dst_len + block_header_skip != sz) {
	225	err = REFTABLE_FORMAT_ERROR;
	226	goto done;
	227	}
e581fd72 HWN	228
	229	/* We're done with the input data. */
	230	reftable_block_done(block);
	231	block->data = uncompressed;
24d4d38c	232	uncompressed = NULL;
e581fd72 HWN	233	block->len = sz;
	234	block->source = malloc_block_source();
	235	full_block_size = src_len + block_header_skip;
	236	} else if (full_block_size == 0) {
	237	full_block_size = sz;
	238	} else if (sz < full_block_size && sz < block->len &&
	239	block->data[sz] != 0) {
	240	/* If the block is smaller than the full block size, it is
	241	padded (data followed by '\0') or the next block is
	242	unaligned. */
	243	full_block_size = sz;
	244	}
	245
	246	restart_count = get_be16(block->data + sz - 2);
	247	restart_start = sz - 2 - 3 * restart_count;
	248	restart_bytes = block->data + restart_start;
	249
	250	/* transfer ownership. */
	251	br->block = *block;
	252	block->data = NULL;
	253	block->len = 0;
	254
	255	br->hash_size = hash_size;
	256	br->block_len = restart_start;
	257	br->full_block_size = full_block_size;
	258	br->header_off = header_off;
	259	br->restart_count = restart_count;
	260	br->restart_bytes = restart_bytes;
	261
24d4d38c HWN	262	done:
	263	reftable_free(uncompressed);
	264	return err;
e581fd72 HWN	265	}
	266
	267	static uint32_t block_reader_restart_offset(struct block_reader *br, int i)
	268	{
	269	return get_be24(br->restart_bytes + 3 * i);
	270	}
	271
	272	void block_reader_start(struct block_reader br, struct block_iter it)
	273	{
	274	it->br = br;
	275	strbuf_reset(&it->last_key);
	276	it->next_off = br->header_off + 4;
	277	}
	278
	279	struct restart_find_args {
	280	int error;
	281	struct strbuf key;
	282	struct block_reader *r;
	283	};
	284
	285	static int restart_key_less(size_t idx, void *args)
	286	{
	287	struct restart_find_args *a = args;
	288	uint32_t off = block_reader_restart_offset(a->r, idx);
	289	struct string_view in = {
	290	.buf = a->r->block.data + off,
	291	.len = a->r->block_len - off,
	292	};
	293
	294	/* the restart key is verbatim in the block, so this could avoid the
	295	alloc for decoding the key */
	296	struct strbuf rkey = STRBUF_INIT;
	297	struct strbuf last_key = STRBUF_INIT;
	298	uint8_t unused_extra;
	299	int n = reftable_decode_key(&rkey, &unused_extra, last_key, in);
	300	int result;
	301	if (n < 0) {
	302	a->error = 1;
	303	return -1;
	304	}
	305
	306	result = strbuf_cmp(&a->key, &rkey);
	307	strbuf_release(&rkey);
	308	return result;
	309	}
	310
	311	void block_iter_copy_from(struct block_iter dest, struct block_iter src)
	312	{
	313	dest->br = src->br;
	314	dest->next_off = src->next_off;
	315	strbuf_reset(&dest->last_key);
	316	strbuf_addbuf(&dest->last_key, &src->last_key);
	317	}
	318
	319	int block_iter_next(struct block_iter it, struct reftable_record rec)
	320	{
	321	struct string_view in = {
	322	.buf = it->br->block.data + it->next_off,
	323	.len = it->br->block_len - it->next_off,
	324	};
	325	struct string_view start = in;
e581fd72 HWN	326	uint8_t extra = 0;
	327	int n = 0;
	328
	329	if (it->next_off >= it->br->block_len)
	330	return 1;
	331
c0cadb05	332	n = reftable_decode_key(&it->key, &extra, it->last_key, in);
e581fd72 HWN	333	if (n < 0)
	334	return -1;
	335
c0cadb05	336	if (!it->key.len)
45c2fcc2 HWN	337	return REFTABLE_FORMAT_ERROR;
45c2fcc2 HWN	338
e581fd72	339	string_view_consume(&in, n);
c0cadb05	340	n = reftable_record_decode(rec, it->key, extra, in, it->br->hash_size);
e581fd72 HWN	341	if (n < 0)
	342	return -1;
	343	string_view_consume(&in, n);
	344
	345	strbuf_reset(&it->last_key);
c0cadb05	346	strbuf_addbuf(&it->last_key, &it->key);
e581fd72	347	it->next_off += start.len - in.len;
e581fd72 HWN	348	return 0;
	349	}
	350
	351	int block_reader_first_key(struct block_reader br, struct strbuf key)
	352	{
	353	struct strbuf empty = STRBUF_INIT;
	354	int off = br->header_off + 4;
	355	struct string_view in = {
	356	.buf = br->block.data + off,
	357	.len = br->block_len - off,
	358	};
	359
	360	uint8_t extra = 0;
	361	int n = reftable_decode_key(key, &extra, empty, in);
	362	if (n < 0)
	363	return n;
45c2fcc2 HWN	364	if (!key->len)
45c2fcc2 HWN	365	return REFTABLE_FORMAT_ERROR;
e581fd72 HWN	366
	367	return 0;
	368	}
	369
	370	int block_iter_seek(struct block_iter it, struct strbuf want)
	371	{
	372	return block_reader_seek(it->br, it, want);
	373	}
	374
	375	void block_iter_close(struct block_iter *it)
	376	{
	377	strbuf_release(&it->last_key);
c0cadb05	378	strbuf_release(&it->key);
e581fd72 HWN	379	}
	380
	381	int block_reader_seek(struct block_reader br, struct block_iter it,
	382	struct strbuf *want)
	383	{
	384	struct restart_find_args args = {
	385	.key = *want,
	386	.r = br,
	387	};
	388	struct reftable_record rec = reftable_new_record(block_reader_type(br));
e581fd72	389	int err = 0;
a8305bc6	390	struct block_iter next = BLOCK_ITER_INIT;
e581fd72 HWN	391
	392	int i = binsearch(br->restart_count, &restart_key_less, &args);
	393	if (args.error) {
	394	err = REFTABLE_FORMAT_ERROR;
	395	goto done;
	396	}
	397
	398	it->br = br;
	399	if (i > 0) {
	400	i--;
	401	it->next_off = block_reader_restart_offset(br, i);
	402	} else {
	403	it->next_off = br->header_off + 4;
	404	}
	405
	406	/* We're looking for the last entry less/equal than the wanted key, so
	407	we have to go one entry too far and then back up.
	408	*/
	409	while (1) {
	410	block_iter_copy_from(&next, it);
	411	err = block_iter_next(&next, &rec);
	412	if (err < 0)
	413	goto done;
	414
c0cadb05 PS	415	reftable_record_key(&rec, &it->key);
c0cadb05 PS	416	if (err > 0 \|\| strbuf_cmp(&it->key, want) >= 0) {
e581fd72 HWN	417	err = 0;
	418	goto done;
	419	}
	420
	421	block_iter_copy_from(it, &next);
	422	}
	423
	424	done:
c0cadb05	425	block_iter_close(&next);
66c0daba	426	reftable_record_release(&rec);
e581fd72 HWN	427
	428	return err;
	429	}
	430
	431	void block_writer_release(struct block_writer *bw)
	432	{
	433	FREE_AND_NULL(bw->restarts);
	434	strbuf_release(&bw->last_key);
	435	/* the block is not owned. */
	436	}
	437
	438	void reftable_block_done(struct reftable_block *blockp)
	439	{
	440	struct reftable_block_source source = blockp->source;
	441	if (blockp && source.ops)
	442	source.ops->return_block(source.arg, blockp);
	443	blockp->data = NULL;
	444	blockp->len = 0;
	445	blockp->source.ops = NULL;
	446	blockp->source.arg = NULL;
	447	}