2 Copyright 2020 Google LLC
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
11 #include "blocksource.h"
12 #include "constants.h"
14 #include "reftable-error.h"
18 int header_size(int version
)
29 int footer_size(int version
)
40 static int block_writer_register_restart(struct block_writer
*w
, int n
,
41 int is_restart
, struct strbuf
*key
)
43 int rlen
= w
->restart_len
;
44 if (rlen
>= MAX_RESTARTS
) {
51 if (2 + 3 * rlen
+ n
> w
->block_size
- w
->next
)
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
);
60 w
->restarts
[w
->restart_len
++] = w
->next
;
65 strbuf_reset(&w
->last_key
);
66 strbuf_addbuf(&w
->last_key
, key
);
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
)
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;
86 uint8_t block_writer_type(struct block_writer
*bw
)
88 return bw
->buf
[bw
->header_off
];
91 /* adds the reftable_record to the block. Returns -1 if it does not fit, 0 on
93 int block_writer_add(struct block_writer
*w
, struct reftable_record
*rec
)
95 struct strbuf empty
= STRBUF_INIT
;
97 w
->entries
% w
->restart_interval
== 0 ? empty
: w
->last_key
;
98 struct string_view out
= {
99 .buf
= w
->buf
+ w
->next
,
100 .len
= w
->block_size
- w
->next
,
103 struct string_view start
= out
;
106 struct strbuf key
= STRBUF_INIT
;
109 reftable_record_key(rec
, &key
);
110 n
= reftable_encode_key(&is_restart
, out
, last
, key
,
111 reftable_record_val_type(rec
));
114 string_view_consume(&out
, n
);
116 n
= reftable_record_encode(rec
, out
, w
->hash_size
);
119 string_view_consume(&out
, n
);
121 if (block_writer_register_restart(w
, start
.len
- out
.len
, is_restart
,
125 strbuf_release(&key
);
129 strbuf_release(&key
);
133 int block_writer_finish(struct block_writer
*w
)
136 for (i
= 0; i
< w
->restart_len
; i
++) {
137 put_be24(w
->buf
+ w
->next
, w
->restarts
[i
]);
141 put_be16(w
->buf
+ w
->next
, w
->restart_len
);
143 put_be24(w
->buf
+ 1 + w
->header_off
, w
->next
);
145 if (block_writer_type(w
) == BLOCK_TYPE_LOG
) {
146 int block_header_skip
= 4 + w
->header_off
;
147 uLongf src_len
= w
->next
- block_header_skip
;
148 uLongf dest_cap
= src_len
* 1.001 + 12;
150 uint8_t *compressed
= reftable_malloc(dest_cap
);
152 uLongf out_dest_len
= dest_cap
;
153 int zresult
= compress2(compressed
, &out_dest_len
,
154 w
->buf
+ block_header_skip
,
156 if (zresult
== Z_BUF_ERROR
&& dest_cap
< LONG_MAX
) {
159 reftable_realloc(compressed
, dest_cap
);
164 if (Z_OK
!= zresult
) {
165 reftable_free(compressed
);
166 return REFTABLE_ZLIB_ERROR
;
169 memcpy(w
->buf
+ block_header_skip
, compressed
,
171 w
->next
= out_dest_len
+ block_header_skip
;
172 reftable_free(compressed
);
179 uint8_t block_reader_type(struct block_reader
*r
)
181 return r
->block
.data
[r
->header_off
];
184 int block_reader_init(struct block_reader
*br
, struct reftable_block
*block
,
185 uint32_t header_off
, uint32_t table_block_size
,
188 uint32_t full_block_size
= table_block_size
;
189 uint8_t typ
= block
->data
[header_off
];
190 uint32_t sz
= get_be24(block
->data
+ header_off
+ 1);
192 uint16_t restart_count
= 0;
193 uint32_t restart_start
= 0;
194 uint8_t *restart_bytes
= NULL
;
195 uint8_t *uncompressed
= NULL
;
197 if (!reftable_is_block_type(typ
)) {
198 err
= REFTABLE_FORMAT_ERROR
;
202 if (typ
== BLOCK_TYPE_LOG
) {
203 int block_header_skip
= 4 + header_off
;
204 uLongf dst_len
= sz
- block_header_skip
; /* total size of dest
206 uLongf src_len
= block
->len
- block_header_skip
;
207 /* Log blocks specify the *uncompressed* size in their header.
209 uncompressed
= reftable_malloc(sz
);
211 /* Copy over the block header verbatim. It's not compressed. */
212 memcpy(uncompressed
, block
->data
, block_header_skip
);
216 uncompress2(uncompressed
+ block_header_skip
, &dst_len
,
217 block
->data
+ block_header_skip
, &src_len
)) {
218 err
= REFTABLE_ZLIB_ERROR
;
222 if (dst_len
+ block_header_skip
!= sz
) {
223 err
= REFTABLE_FORMAT_ERROR
;
227 /* We're done with the input data. */
228 reftable_block_done(block
);
229 block
->data
= uncompressed
;
232 block
->source
= malloc_block_source();
233 full_block_size
= src_len
+ block_header_skip
;
234 } else if (full_block_size
== 0) {
235 full_block_size
= sz
;
236 } else if (sz
< full_block_size
&& sz
< block
->len
&&
237 block
->data
[sz
] != 0) {
238 /* If the block is smaller than the full block size, it is
239 padded (data followed by '\0') or the next block is
241 full_block_size
= sz
;
244 restart_count
= get_be16(block
->data
+ sz
- 2);
245 restart_start
= sz
- 2 - 3 * restart_count
;
246 restart_bytes
= block
->data
+ restart_start
;
248 /* transfer ownership. */
253 br
->hash_size
= hash_size
;
254 br
->block_len
= restart_start
;
255 br
->full_block_size
= full_block_size
;
256 br
->header_off
= header_off
;
257 br
->restart_count
= restart_count
;
258 br
->restart_bytes
= restart_bytes
;
261 reftable_free(uncompressed
);
265 static uint32_t block_reader_restart_offset(struct block_reader
*br
, int i
)
267 return get_be24(br
->restart_bytes
+ 3 * i
);
270 void block_reader_start(struct block_reader
*br
, struct block_iter
*it
)
273 strbuf_reset(&it
->last_key
);
274 it
->next_off
= br
->header_off
+ 4;
277 struct restart_find_args
{
280 struct block_reader
*r
;
283 static int restart_key_less(size_t idx
, void *args
)
285 struct restart_find_args
*a
= args
;
286 uint32_t off
= block_reader_restart_offset(a
->r
, idx
);
287 struct string_view in
= {
288 .buf
= a
->r
->block
.data
+ off
,
289 .len
= a
->r
->block_len
- off
,
292 /* the restart key is verbatim in the block, so this could avoid the
293 alloc for decoding the key */
294 struct strbuf rkey
= STRBUF_INIT
;
295 struct strbuf last_key
= STRBUF_INIT
;
296 uint8_t unused_extra
;
297 int n
= reftable_decode_key(&rkey
, &unused_extra
, last_key
, in
);
304 result
= strbuf_cmp(&a
->key
, &rkey
);
305 strbuf_release(&rkey
);
309 void block_iter_copy_from(struct block_iter
*dest
, struct block_iter
*src
)
312 dest
->next_off
= src
->next_off
;
313 strbuf_reset(&dest
->last_key
);
314 strbuf_addbuf(&dest
->last_key
, &src
->last_key
);
317 int block_iter_next(struct block_iter
*it
, struct reftable_record
*rec
)
319 struct string_view in
= {
320 .buf
= it
->br
->block
.data
+ it
->next_off
,
321 .len
= it
->br
->block_len
- it
->next_off
,
323 struct string_view start
= in
;
324 struct strbuf key
= STRBUF_INIT
;
328 if (it
->next_off
>= it
->br
->block_len
)
331 n
= reftable_decode_key(&key
, &extra
, it
->last_key
, in
);
335 string_view_consume(&in
, n
);
336 n
= reftable_record_decode(rec
, key
, extra
, in
, it
->br
->hash_size
);
339 string_view_consume(&in
, n
);
341 strbuf_reset(&it
->last_key
);
342 strbuf_addbuf(&it
->last_key
, &key
);
343 it
->next_off
+= start
.len
- in
.len
;
344 strbuf_release(&key
);
348 int block_reader_first_key(struct block_reader
*br
, struct strbuf
*key
)
350 struct strbuf empty
= STRBUF_INIT
;
351 int off
= br
->header_off
+ 4;
352 struct string_view in
= {
353 .buf
= br
->block
.data
+ off
,
354 .len
= br
->block_len
- off
,
358 int n
= reftable_decode_key(key
, &extra
, empty
, in
);
365 int block_iter_seek(struct block_iter
*it
, struct strbuf
*want
)
367 return block_reader_seek(it
->br
, it
, want
);
370 void block_iter_close(struct block_iter
*it
)
372 strbuf_release(&it
->last_key
);
375 int block_reader_seek(struct block_reader
*br
, struct block_iter
*it
,
378 struct restart_find_args args
= {
382 struct reftable_record rec
= reftable_new_record(block_reader_type(br
));
383 struct strbuf key
= STRBUF_INIT
;
385 struct block_iter next
= {
386 .last_key
= STRBUF_INIT
,
389 int i
= binsearch(br
->restart_count
, &restart_key_less
, &args
);
391 err
= REFTABLE_FORMAT_ERROR
;
398 it
->next_off
= block_reader_restart_offset(br
, i
);
400 it
->next_off
= br
->header_off
+ 4;
403 /* We're looking for the last entry less/equal than the wanted key, so
404 we have to go one entry too far and then back up.
407 block_iter_copy_from(&next
, it
);
408 err
= block_iter_next(&next
, &rec
);
412 reftable_record_key(&rec
, &key
);
413 if (err
> 0 || strbuf_cmp(&key
, want
) >= 0) {
418 block_iter_copy_from(it
, &next
);
422 strbuf_release(&key
);
423 strbuf_release(&next
.last_key
);
424 reftable_record_destroy(&rec
);
429 void block_writer_release(struct block_writer
*bw
)
431 FREE_AND_NULL(bw
->restarts
);
432 strbuf_release(&bw
->last_key
);
433 /* the block is not owned. */
436 void reftable_block_done(struct reftable_block
*blockp
)
438 struct reftable_block_source source
= blockp
->source
;
439 if (blockp
&& source
.ops
)
440 source
.ops
->return_block(source
.arg
, blockp
);
443 blockp
->source
.ops
= NULL
;
444 blockp
->source
.arg
= NULL
;