]>
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 | |
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, |
124 | &key); | |
e581fd72 HWN |
125 | done: |
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; |
218 | goto done; | |
e581fd72 HWN |
219 | } |
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; |
279 | struct block_reader *reader; | |
e581fd72 HWN |
280 | }; |
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; |
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, |
288 | .len = args->reader->block_len - off, | |
e581fd72 | 289 | }; |
d51d8cc3 PS |
290 | uint64_t prefix_len, suffix_len; |
291 | uint8_t extra; | |
292 | int n; | |
77307a61 PS |
293 | |
294 | /* | |
d51d8cc3 PS |
295 | * Records at restart points are stored without prefix compression, so |
296 | * there is no need to fully decode the record key here. This removes | |
297 | * the need for allocating memory. | |
77307a61 | 298 | */ |
d51d8cc3 PS |
299 | n = reftable_decode_keylen(in, &prefix_len, &suffix_len, &extra); |
300 | if (n < 0 || prefix_len) { | |
77307a61 | 301 | args->error = 1; |
e581fd72 HWN |
302 | return -1; |
303 | } | |
304 | ||
d51d8cc3 PS |
305 | string_view_consume(&in, n); |
306 | if (suffix_len > in.len) { | |
307 | args->error = 1; | |
308 | return -1; | |
309 | } | |
310 | ||
311 | n = memcmp(args->needle.buf, in.buf, | |
312 | args->needle.len < suffix_len ? args->needle.len : suffix_len); | |
313 | if (n) | |
314 | return n < 0; | |
315 | return args->needle.len < suffix_len; | |
e581fd72 HWN |
316 | } |
317 | ||
318 | void block_iter_copy_from(struct block_iter *dest, struct block_iter *src) | |
319 | { | |
320 | dest->br = src->br; | |
321 | dest->next_off = src->next_off; | |
322 | strbuf_reset(&dest->last_key); | |
323 | strbuf_addbuf(&dest->last_key, &src->last_key); | |
324 | } | |
325 | ||
326 | int block_iter_next(struct block_iter *it, struct reftable_record *rec) | |
327 | { | |
328 | struct string_view in = { | |
329 | .buf = it->br->block.data + it->next_off, | |
330 | .len = it->br->block_len - it->next_off, | |
331 | }; | |
332 | struct string_view start = in; | |
e581fd72 HWN |
333 | uint8_t extra = 0; |
334 | int n = 0; | |
335 | ||
336 | if (it->next_off >= it->br->block_len) | |
337 | return 1; | |
338 | ||
daf4f43d | 339 | n = reftable_decode_key(&it->last_key, &extra, in); |
e581fd72 HWN |
340 | if (n < 0) |
341 | return -1; | |
daf4f43d | 342 | if (!it->last_key.len) |
45c2fcc2 HWN |
343 | return REFTABLE_FORMAT_ERROR; |
344 | ||
e581fd72 | 345 | string_view_consume(&in, n); |
7b8abc4d PS |
346 | n = reftable_record_decode(rec, it->last_key, extra, in, it->br->hash_size, |
347 | &it->scratch); | |
e581fd72 HWN |
348 | if (n < 0) |
349 | return -1; | |
350 | string_view_consume(&in, n); | |
351 | ||
e581fd72 | 352 | it->next_off += start.len - in.len; |
e581fd72 HWN |
353 | return 0; |
354 | } | |
355 | ||
356 | int block_reader_first_key(struct block_reader *br, struct strbuf *key) | |
357 | { | |
daf4f43d | 358 | int off = br->header_off + 4, n; |
e581fd72 HWN |
359 | struct string_view in = { |
360 | .buf = br->block.data + off, | |
361 | .len = br->block_len - off, | |
362 | }; | |
e581fd72 | 363 | uint8_t extra = 0; |
daf4f43d PS |
364 | |
365 | strbuf_reset(key); | |
366 | ||
367 | n = reftable_decode_key(key, &extra, in); | |
e581fd72 HWN |
368 | if (n < 0) |
369 | return n; | |
45c2fcc2 HWN |
370 | if (!key->len) |
371 | return REFTABLE_FORMAT_ERROR; | |
e581fd72 HWN |
372 | |
373 | return 0; | |
374 | } | |
375 | ||
376 | int block_iter_seek(struct block_iter *it, struct strbuf *want) | |
377 | { | |
378 | return block_reader_seek(it->br, it, want); | |
379 | } | |
380 | ||
381 | void block_iter_close(struct block_iter *it) | |
382 | { | |
383 | strbuf_release(&it->last_key); | |
7b8abc4d | 384 | strbuf_release(&it->scratch); |
e581fd72 HWN |
385 | } |
386 | ||
387 | int block_reader_seek(struct block_reader *br, struct block_iter *it, | |
388 | struct strbuf *want) | |
389 | { | |
77307a61 PS |
390 | struct restart_needle_less_args args = { |
391 | .needle = *want, | |
392 | .reader = br, | |
e581fd72 | 393 | }; |
a8305bc6 | 394 | struct block_iter next = BLOCK_ITER_INIT; |
3ddef475 | 395 | struct reftable_record rec; |
3e7b36d1 PS |
396 | int err = 0; |
397 | size_t i; | |
e581fd72 | 398 | |
77307a61 PS |
399 | /* |
400 | * Perform a binary search over the block's restart points, which | |
401 | * avoids doing a linear scan over the whole block. Like this, we | |
402 | * identify the section of the block that should contain our key. | |
403 | * | |
404 | * Note that we explicitly search for the first restart point _greater_ | |
405 | * than the sought-after record, not _greater or equal_ to it. In case | |
406 | * the sought-after record is located directly at the restart point we | |
407 | * would otherwise start doing the linear search at the preceding | |
408 | * restart point. While that works alright, we would end up scanning | |
409 | * too many record. | |
410 | */ | |
411 | i = binsearch(br->restart_count, &restart_needle_less, &args); | |
f9e88544 PS |
412 | if (args.error) { |
413 | err = REFTABLE_FORMAT_ERROR; | |
414 | goto done; | |
415 | } | |
77307a61 PS |
416 | |
417 | /* | |
418 | * Now there are multiple cases: | |
419 | * | |
420 | * - `i == 0`: The wanted record is smaller than the record found at | |
421 | * the first restart point. As the first restart point is the first | |
422 | * record in the block, our wanted record cannot be located in this | |
423 | * block at all. We still need to position the iterator so that the | |
424 | * next call to `block_iter_next()` will yield an end-of-iterator | |
425 | * signal. | |
426 | * | |
427 | * - `i == restart_count`: The wanted record was not found at any of | |
428 | * the restart points. As there is no restart point at the end of | |
429 | * the section the record may thus be contained in the last block. | |
430 | * | |
431 | * - `i > 0`: The wanted record must be contained in the section | |
432 | * before the found restart point. We thus do a linear search | |
433 | * starting from the preceding restart point. | |
434 | */ | |
3ddef475 PS |
435 | if (i > 0) |
436 | it->next_off = block_reader_restart_offset(br, i - 1); | |
437 | else | |
e581fd72 | 438 | it->next_off = br->header_off + 4; |
3ddef475 PS |
439 | it->br = br; |
440 | ||
441 | reftable_record_init(&rec, block_reader_type(br)); | |
e581fd72 | 442 | |
77307a61 PS |
443 | /* |
444 | * We're looking for the last entry less than the wanted key so that | |
445 | * the next call to `block_reader_next()` would yield the wanted | |
446 | * record. We thus don't want to position our reader at the sought | |
447 | * after record, but one before. To do so, we have to go one entry too | |
448 | * far and then back up. | |
449 | */ | |
e581fd72 HWN |
450 | while (1) { |
451 | block_iter_copy_from(&next, it); | |
452 | err = block_iter_next(&next, &rec); | |
453 | if (err < 0) | |
454 | goto done; | |
77307a61 | 455 | if (err > 0) { |
e581fd72 HWN |
456 | err = 0; |
457 | goto done; | |
458 | } | |
459 | ||
77307a61 PS |
460 | /* |
461 | * Check whether the current key is greater or equal to the | |
462 | * sought-after key. In case it is greater we know that the | |
463 | * record does not exist in the block and can thus abort early. | |
464 | * In case it is equal to the sought-after key we have found | |
465 | * the desired record. | |
466 | */ | |
467 | reftable_record_key(&rec, &it->last_key); | |
468 | if (strbuf_cmp(&it->last_key, want) >= 0) | |
469 | goto done; | |
470 | ||
e581fd72 HWN |
471 | block_iter_copy_from(it, &next); |
472 | } | |
473 | ||
474 | done: | |
c0cadb05 | 475 | block_iter_close(&next); |
66c0daba | 476 | reftable_record_release(&rec); |
e581fd72 HWN |
477 | |
478 | return err; | |
479 | } | |
480 | ||
481 | void block_writer_release(struct block_writer *bw) | |
482 | { | |
483 | FREE_AND_NULL(bw->restarts); | |
484 | strbuf_release(&bw->last_key); | |
485 | /* the block is not owned. */ | |
486 | } | |
487 | ||
488 | void reftable_block_done(struct reftable_block *blockp) | |
489 | { | |
490 | struct reftable_block_source source = blockp->source; | |
491 | if (blockp && source.ops) | |
492 | source.ops->return_block(source.arg, blockp); | |
493 | blockp->data = NULL; | |
494 | blockp->len = 0; | |
495 | blockp->source.ops = NULL; | |
496 | blockp->source.arg = NULL; | |
497 | } |