diff --git a/reftable/block.c b/reftable/block.c
index 4f62b823db8..697b8b41531 100644
--- a/reftable/block.c
+++ b/reftable/block.c
@@ -111,9 +111,12 @@ int block_writer_add(struct block_writer *w, struct reftable_record *rec)
 	int is_restart = 0;
 	struct reftable_buf key = REFTABLE_BUF_INIT;
 	int n = 0;
-	int err = -1;
+	int err;
+
+	err = reftable_record_key(rec, &key);
+	if (err < 0)
+		goto done;
 
-	reftable_record_key(rec, &key);
 	if (!key.len) {
 		err = REFTABLE_API_ERROR;
 		goto done;
@@ -121,13 +124,17 @@ int block_writer_add(struct block_writer *w, struct reftable_record *rec)
 
 	n = reftable_encode_key(&is_restart, out, last, key,
 				reftable_record_val_type(rec));
-	if (n < 0)
+	if (n < 0) {
+		err = -1;
 		goto done;
+	}
 	string_view_consume(&out, n);
 
 	n = reftable_record_encode(rec, out, w->hash_size);
-	if (n < 0)
+	if (n < 0) {
+		err = -1;
 		goto done;
+	}
 	string_view_consume(&out, n);
 
 	err = block_writer_register_restart(w, start.len - out.len, is_restart,
@@ -522,6 +529,10 @@ int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,
 			goto done;
 		}
 
+		err = reftable_record_key(&rec, &it->last_key);
+		if (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
@@ -536,7 +547,6 @@ int block_iter_seek_key(struct block_iter *it, const struct block_reader *br,
 		 * to `last_key` now, and naturally all keys share a prefix
 		 * with themselves.
 		 */
-		reftable_record_key(&rec, &it->last_key);
 		if (reftable_buf_cmp(&it->last_key, want) >= 0) {
 			it->next_off = prev_off;
 			goto done;
diff --git a/reftable/reader.c b/reftable/reader.c
index 388f8bf6d7b..ab89efd9c55 100644
--- a/reftable/reader.c
+++ b/reftable/reader.c
@@ -356,7 +356,9 @@ static int table_iter_seek_linear(struct table_iter *ti,
 	int err;
 
 	reftable_record_init(&rec, reftable_record_type(want));
-	reftable_record_key(want, &want_key);
+	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
@@ -439,7 +441,9 @@ static int table_iter_seek_indexed(struct table_iter *ti,
 	};
 	int err;
 
-	reftable_record_key(rec, &want_index.u.idx.last_key);
+	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
diff --git a/reftable/record.c b/reftable/record.c
index 0182c973437..672c5f909a9 100644
--- a/reftable/record.c
+++ b/reftable/record.c
@@ -207,12 +207,12 @@ int reftable_decode_key(struct reftable_buf *last_key, uint8_t *extra,
 	return start_len - in.len;
 }
 
-static void reftable_ref_record_key(const void *r, struct reftable_buf *dest)
+static int reftable_ref_record_key(const void *r, struct reftable_buf *dest)
 {
 	const struct reftable_ref_record *rec =
 		(const struct reftable_ref_record *)r;
 	reftable_buf_reset(dest);
-	reftable_buf_addstr(dest, rec->refname);
+	return reftable_buf_addstr(dest, rec->refname);
 }
 
 static int reftable_ref_record_copy_from(void *rec, const void *src_rec,
@@ -465,12 +465,12 @@ static struct reftable_record_vtable reftable_ref_record_vtable = {
 	.cmp = &reftable_ref_record_cmp_void,
 };
 
-static void reftable_obj_record_key(const void *r, struct reftable_buf *dest)
+static int reftable_obj_record_key(const void *r, struct reftable_buf *dest)
 {
 	const struct reftable_obj_record *rec =
 		(const struct reftable_obj_record *)r;
 	reftable_buf_reset(dest);
-	reftable_buf_add(dest, rec->hash_prefix, rec->hash_prefix_len);
+	return reftable_buf_add(dest, rec->hash_prefix, rec->hash_prefix_len);
 }
 
 static void reftable_obj_record_release(void *rec)
@@ -664,19 +664,27 @@ static struct reftable_record_vtable reftable_obj_record_vtable = {
 	.cmp = &reftable_obj_record_cmp_void,
 };
 
-static void reftable_log_record_key(const void *r, struct reftable_buf *dest)
+static int reftable_log_record_key(const void *r, struct reftable_buf *dest)
 {
 	const struct reftable_log_record *rec =
 		(const struct reftable_log_record *)r;
-	int len = strlen(rec->refname);
+	int len = strlen(rec->refname), err;
 	uint8_t i64[8];
 	uint64_t ts = 0;
+
 	reftable_buf_reset(dest);
-	reftable_buf_add(dest, (uint8_t *)rec->refname, len + 1);
+	err = reftable_buf_add(dest, (uint8_t *)rec->refname, len + 1);
+	if (err < 0)
+		return err;
 
 	ts = (~ts) - rec->update_index;
 	put_be64(&i64[0], ts);
-	reftable_buf_add(dest, i64, sizeof(i64));
+
+	err = reftable_buf_add(dest, i64, sizeof(i64));
+	if (err < 0)
+		return err;
+
+	return 0;
 }
 
 static int reftable_log_record_copy_from(void *rec, const void *src_rec,
@@ -1027,11 +1035,11 @@ static struct reftable_record_vtable reftable_log_record_vtable = {
 	.cmp = &reftable_log_record_cmp_void,
 };
 
-static void reftable_index_record_key(const void *r, struct reftable_buf *dest)
+static int reftable_index_record_key(const void *r, struct reftable_buf *dest)
 {
 	const struct reftable_index_record *rec = r;
 	reftable_buf_reset(dest);
-	reftable_buf_add(dest, rec->last_key.buf, rec->last_key.len);
+	return reftable_buf_add(dest, rec->last_key.buf, rec->last_key.len);
 }
 
 static int reftable_index_record_copy_from(void *rec, const void *src_rec,
@@ -1124,9 +1132,9 @@ static struct reftable_record_vtable reftable_index_record_vtable = {
 	.cmp = &reftable_index_record_cmp,
 };
 
-void reftable_record_key(struct reftable_record *rec, struct reftable_buf *dest)
+int reftable_record_key(struct reftable_record *rec, struct reftable_buf *dest)
 {
-	reftable_record_vtable(rec)->key(reftable_record_data(rec), dest);
+	return reftable_record_vtable(rec)->key(reftable_record_data(rec), dest);
 }
 
 int reftable_record_encode(struct reftable_record *rec, struct string_view dest,
diff --git a/reftable/record.h b/reftable/record.h
index 271da3bf360..25aa908c859 100644
--- a/reftable/record.h
+++ b/reftable/record.h
@@ -40,7 +40,7 @@ int put_var_int(struct string_view *dest, uint64_t val);
 /* Methods for records. */
 struct reftable_record_vtable {
 	/* encode the key of to a uint8_t reftable_buf. */
-	void (*key)(const void *rec, struct reftable_buf *dest);
+	int (*key)(const void *rec, struct reftable_buf *dest);
 
 	/* The record type of ('r' for ref). */
 	uint8_t type;
@@ -137,7 +137,7 @@ void reftable_record_init(struct reftable_record *rec, uint8_t typ);
 /* see struct record_vtable */
 int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b);
 int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, int hash_size);
-void reftable_record_key(struct reftable_record *rec, struct reftable_buf *dest);
+int reftable_record_key(struct reftable_record *rec, struct reftable_buf *dest);
 int reftable_record_copy_from(struct reftable_record *rec,
 			      struct reftable_record *src, int hash_size);
 uint8_t reftable_record_val_type(struct reftable_record *rec);
diff --git a/reftable/writer.c b/reftable/writer.c
index da6941a78ac..377db709c85 100644
--- a/reftable/writer.c
+++ b/reftable/writer.c
@@ -249,7 +249,10 @@ static int writer_add_record(struct reftable_writer *w,
 	struct reftable_buf key = REFTABLE_BUF_INIT;
 	int err;
 
-	reftable_record_key(rec, &key);
+	err = reftable_record_key(rec, &key);
+	if (err < 0)
+		goto done;
+
 	if (reftable_buf_cmp(&w->last_key, &key) >= 0) {
 		err = REFTABLE_API_ERROR;
 		goto done;
