freshlybakedca.ke
Git fork
a.starrysky.fyi
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/* record.c - methods for different types of records. */
10
11#include "record.h"
12
13#include "system.h"
14#include "constants.h"
15#include "reftable-error.h"
16#include "basics.h"
17
18static struct reftable_record_vtable *
19reftable_record_vtable(struct reftable_record *rec);
20static void *reftable_record_data(struct reftable_record *rec);
21
22int get_var_int(uint64_t *dest, struct string_view *in)
23{
24 const unsigned char *buf = in->buf;
25 unsigned char c;
26 uint64_t val;
27
28 if (!in->len)
29 return -1;
30 c = *buf++;
31 val = c & 0x7f;
32
33 while (c & 0x80) {
34 /*
35 * We use a micro-optimization here: whenever we see that the
36 * 0x80 bit is set, we know that the remainder of the value
37 * cannot be 0. The zero-values thus doesn't need to be encoded
38 * at all, which is why we subtract 1 when encoding and add 1
39 * when decoding.
40 *
41 * This allows us to save a byte in some edge cases.
42 */
43 val += 1;
44 if (!val || (val & (uint64_t)(~0ULL << (64 - 7))))
45 return -1; /* overflow */
46 if (buf >= in->buf + in->len)
47 return -1;
48 c = *buf++;
49 val = (val << 7) + (c & 0x7f);
50 }
51
52 *dest = val;
53 return buf - in->buf;
54}
55
56int put_var_int(struct string_view *dest, uint64_t value)
57{
58 unsigned char varint[10];
59 unsigned pos = sizeof(varint) - 1;
60 varint[pos] = value & 0x7f;
61 while (value >>= 7)
62 varint[--pos] = 0x80 | (--value & 0x7f);
63 if (dest->len < sizeof(varint) - pos)
64 return REFTABLE_ENTRY_TOO_BIG_ERROR;
65 memcpy(dest->buf, varint + pos, sizeof(varint) - pos);
66 return sizeof(varint) - pos;
67}
68
69int reftable_is_block_type(uint8_t typ)
70{
71 switch (typ) {
72 case REFTABLE_BLOCK_TYPE_REF:
73 case REFTABLE_BLOCK_TYPE_LOG:
74 case REFTABLE_BLOCK_TYPE_OBJ:
75 case REFTABLE_BLOCK_TYPE_INDEX:
76 return 1;
77 }
78 return 0;
79}
80
81const unsigned char *reftable_ref_record_val1(const struct reftable_ref_record *rec)
82{
83 // Implemented in reftable_record.rs
84 switch (rec->value_type) {
85 case REFTABLE_REF_VAL1:
86 return rec->value.val1;
87 case REFTABLE_REF_VAL2:
88 return rec->value.val2.value;
89 default:
90 return NULL;
91 }
92}
93
94const unsigned char *reftable_ref_record_val2(const struct reftable_ref_record *rec)
95{
96 // Implemented in reftable_record.rs
97 switch (rec->value_type) {
98 case REFTABLE_REF_VAL2:
99 return rec->value.val2.target_value;
100 default:
101 return NULL;
102 }
103}
104
105static int decode_string(struct reftable_buf *dest, struct string_view in)
106{
107 int start_len = in.len;
108 uint64_t tsize = 0;
109 int n, err;
110
111 n = get_var_int(&tsize, &in);
112 if (n <= 0)
113 return -1;
114 string_view_consume(&in, n);
115 if (in.len < tsize)
116 return -1;
117
118 reftable_buf_reset(dest);
119 err = reftable_buf_add(dest, in.buf, tsize);
120 if (err < 0)
121 return err;
122
123 string_view_consume(&in, tsize);
124
125 return start_len - in.len;
126}
127
128static int encode_string(const char *str, struct string_view s)
129{
130 struct string_view start = s;
131 size_t l = strlen(str);
132 int n = put_var_int(&s, l);
133 if (n < 0)
134 return n;
135 string_view_consume(&s, n);
136 if (s.len < l)
137 return REFTABLE_ENTRY_TOO_BIG_ERROR;
138 memcpy(s.buf, str, l);
139 string_view_consume(&s, l);
140
141 return start.len - s.len;
142}
143
144int reftable_encode_key(int *restart, struct string_view dest,
145 struct reftable_buf prev_key, struct reftable_buf key,
146 uint8_t extra)
147{
148 struct string_view start = dest;
149 size_t prefix_len = common_prefix_size(&prev_key, &key);
150 uint64_t suffix_len = key.len - prefix_len;
151 int n = put_var_int(&dest, prefix_len);
152 if (n < 0)
153 return n;
154 string_view_consume(&dest, n);
155
156 *restart = (prefix_len == 0);
157
158 n = put_var_int(&dest, suffix_len << 3 | (uint64_t)extra);
159 if (n < 0)
160 return n;
161 string_view_consume(&dest, n);
162
163 if (dest.len < suffix_len)
164 return REFTABLE_ENTRY_TOO_BIG_ERROR;
165 memcpy(dest.buf, key.buf + prefix_len, suffix_len);
166 string_view_consume(&dest, suffix_len);
167
168 return start.len - dest.len;
169}
170
171int reftable_decode_keylen(struct string_view in,
172 uint64_t *prefix_len,
173 uint64_t *suffix_len,
174 uint8_t *extra)
175{
176 size_t start_len = in.len;
177 int n;
178
179 n = get_var_int(prefix_len, &in);
180 if (n < 0)
181 return -1;
182 string_view_consume(&in, n);
183
184 n = get_var_int(suffix_len, &in);
185 if (n <= 0)
186 return -1;
187 string_view_consume(&in, n);
188
189 *extra = (uint8_t)(*suffix_len & 0x7);
190 *suffix_len >>= 3;
191
192 return start_len - in.len;
193}
194
195int reftable_decode_key(struct reftable_buf *last_key, uint8_t *extra,
196 struct string_view in)
197{
198 int start_len = in.len;
199 uint64_t prefix_len = 0;
200 uint64_t suffix_len = 0;
201 int err, n;
202
203 n = reftable_decode_keylen(in, &prefix_len, &suffix_len, extra);
204 if (n < 0)
205 return -1;
206 string_view_consume(&in, n);
207
208 if (in.len < suffix_len ||
209 prefix_len > last_key->len)
210 return -1;
211
212 err = reftable_buf_setlen(last_key, prefix_len);
213 if (err < 0)
214 return err;
215
216 err = reftable_buf_add(last_key, in.buf, suffix_len);
217 if (err < 0)
218 return err;
219
220 string_view_consume(&in, suffix_len);
221
222 return start_len - in.len;
223}
224
225static int reftable_ref_record_key(const void *r, struct reftable_buf *dest)
226{
227 const struct reftable_ref_record *rec =
228 (const struct reftable_ref_record *)r;
229 reftable_buf_reset(dest);
230 return reftable_buf_addstr(dest, rec->refname);
231}
232
233static int reftable_ref_record_copy_from(void *rec, const void *src_rec,
234 uint32_t hash_size)
235{
236 struct reftable_ref_record *ref = rec;
237 const struct reftable_ref_record *src = src_rec;
238 char *refname = NULL;
239 size_t refname_cap = 0;
240 int err;
241
242 REFTABLE_SWAP(refname, ref->refname);
243 REFTABLE_SWAP(refname_cap, ref->refname_cap);
244 reftable_ref_record_release(ref);
245 REFTABLE_SWAP(ref->refname, refname);
246 REFTABLE_SWAP(ref->refname_cap, refname_cap);
247
248 if (src->refname) {
249 size_t refname_len = strlen(src->refname);
250
251 REFTABLE_ALLOC_GROW_OR_NULL(ref->refname, refname_len + 1,
252 ref->refname_cap);
253 if (!ref->refname) {
254 err = REFTABLE_OUT_OF_MEMORY_ERROR;
255 goto out;
256 }
257
258 memcpy(ref->refname, src->refname, refname_len);
259 ref->refname[refname_len] = 0;
260 }
261
262 ref->update_index = src->update_index;
263 ref->value_type = src->value_type;
264 switch (src->value_type) {
265 case REFTABLE_REF_DELETION:
266 break;
267 case REFTABLE_REF_VAL1:
268 memcpy(ref->value.val1, src->value.val1, hash_size);
269 break;
270 case REFTABLE_REF_VAL2:
271 memcpy(ref->value.val2.value, src->value.val2.value, hash_size);
272 memcpy(ref->value.val2.target_value,
273 src->value.val2.target_value, hash_size);
274 break;
275 case REFTABLE_REF_SYMREF:
276 ref->value.symref = reftable_strdup(src->value.symref);
277 if (!ref->value.symref) {
278 err = REFTABLE_OUT_OF_MEMORY_ERROR;
279 goto out;
280 }
281 break;
282 }
283
284 err = 0;
285out:
286 return err;
287}
288
289static void reftable_ref_record_release_void(void *rec)
290{
291 reftable_ref_record_release(rec);
292}
293
294void reftable_ref_record_release(struct reftable_ref_record *ref)
295{
296 switch (ref->value_type) {
297 case REFTABLE_REF_SYMREF:
298 reftable_free(ref->value.symref);
299 break;
300 case REFTABLE_REF_VAL2:
301 break;
302 case REFTABLE_REF_VAL1:
303 break;
304 case REFTABLE_REF_DELETION:
305 break;
306 default:
307 abort();
308 }
309
310 reftable_free(ref->refname);
311 memset(ref, 0, sizeof(struct reftable_ref_record));
312}
313
314static uint8_t reftable_ref_record_val_type(const void *rec)
315{
316 const struct reftable_ref_record *r =
317 (const struct reftable_ref_record *)rec;
318 return r->value_type;
319}
320
321static int reftable_ref_record_encode(const void *rec, struct string_view s,
322 uint32_t hash_size)
323{
324 const struct reftable_ref_record *r =
325 (const struct reftable_ref_record *)rec;
326 struct string_view start = s;
327 int n = put_var_int(&s, r->update_index);
328 if (n < 0)
329 return n;
330 string_view_consume(&s, n);
331
332 switch (r->value_type) {
333 case REFTABLE_REF_SYMREF:
334 n = encode_string(r->value.symref, s);
335 if (n < 0)
336 return n;
337 string_view_consume(&s, n);
338 break;
339 case REFTABLE_REF_VAL2:
340 if (s.len < 2 * hash_size)
341 return REFTABLE_ENTRY_TOO_BIG_ERROR;
342 memcpy(s.buf, r->value.val2.value, hash_size);
343 string_view_consume(&s, hash_size);
344 memcpy(s.buf, r->value.val2.target_value, hash_size);
345 string_view_consume(&s, hash_size);
346 break;
347 case REFTABLE_REF_VAL1:
348 if (s.len < hash_size)
349 return REFTABLE_ENTRY_TOO_BIG_ERROR;
350 memcpy(s.buf, r->value.val1, hash_size);
351 string_view_consume(&s, hash_size);
352 break;
353 case REFTABLE_REF_DELETION:
354 break;
355 default:
356 abort();
357 }
358
359 return start.len - s.len;
360}
361
362static int reftable_ref_record_decode(void *rec, struct reftable_buf key,
363 uint8_t val_type, struct string_view in,
364 uint32_t hash_size, struct reftable_buf *scratch)
365{
366 struct reftable_ref_record *r = rec;
367 struct string_view start = in;
368 uint64_t update_index = 0;
369 const char *refname = NULL;
370 size_t refname_cap = 0;
371 int n, err;
372
373 n = get_var_int(&update_index, &in);
374 if (n < 0)
375 return n;
376 string_view_consume(&in, n);
377
378 REFTABLE_SWAP(refname, r->refname);
379 REFTABLE_SWAP(refname_cap, r->refname_cap);
380 reftable_ref_record_release(r);
381 REFTABLE_SWAP(r->refname, refname);
382 REFTABLE_SWAP(r->refname_cap, refname_cap);
383
384 REFTABLE_ALLOC_GROW_OR_NULL(r->refname, key.len + 1, r->refname_cap);
385 if (!r->refname) {
386 err = REFTABLE_OUT_OF_MEMORY_ERROR;
387 goto done;
388 }
389 memcpy(r->refname, key.buf, key.len);
390 r->refname[key.len] = 0;
391
392 r->update_index = update_index;
393 r->value_type = val_type;
394 switch (val_type) {
395 case REFTABLE_REF_VAL1:
396 if (in.len < hash_size) {
397 err = REFTABLE_FORMAT_ERROR;
398 goto done;
399 }
400
401 memcpy(r->value.val1, in.buf, hash_size);
402 string_view_consume(&in, hash_size);
403 break;
404
405 case REFTABLE_REF_VAL2:
406 if (in.len < 2 * hash_size) {
407 err = REFTABLE_FORMAT_ERROR;
408 goto done;
409 }
410
411 memcpy(r->value.val2.value, in.buf, hash_size);
412 string_view_consume(&in, hash_size);
413
414 memcpy(r->value.val2.target_value, in.buf, hash_size);
415 string_view_consume(&in, hash_size);
416 break;
417
418 case REFTABLE_REF_SYMREF: {
419 int n = decode_string(scratch, in);
420 if (n < 0) {
421 err = REFTABLE_FORMAT_ERROR;
422 goto done;
423 }
424 string_view_consume(&in, n);
425 r->value.symref = reftable_buf_detach(scratch);
426 } break;
427
428 case REFTABLE_REF_DELETION:
429 break;
430 default:
431 abort();
432 break;
433 }
434
435 return start.len - in.len;
436
437done:
438 return err;
439}
440
441static int reftable_ref_record_is_deletion_void(const void *p)
442{
443 return reftable_ref_record_is_deletion(
444 (const struct reftable_ref_record *)p);
445}
446
447static int reftable_ref_record_equal_void(const void *a,
448 const void *b, uint32_t hash_size)
449{
450 struct reftable_ref_record *ra = (struct reftable_ref_record *) a;
451 struct reftable_ref_record *rb = (struct reftable_ref_record *) b;
452 return reftable_ref_record_equal(ra, rb, hash_size);
453}
454
455static int reftable_ref_record_cmp_void(const void *_a, const void *_b)
456{
457 const struct reftable_ref_record *a = _a;
458 const struct reftable_ref_record *b = _b;
459 return strcmp(a->refname, b->refname);
460}
461
462static struct reftable_record_vtable reftable_ref_record_vtable = {
463 .key = &reftable_ref_record_key,
464 .type = REFTABLE_BLOCK_TYPE_REF,
465 .copy_from = &reftable_ref_record_copy_from,
466 .val_type = &reftable_ref_record_val_type,
467 .encode = &reftable_ref_record_encode,
468 .decode = &reftable_ref_record_decode,
469 .release = &reftable_ref_record_release_void,
470 .is_deletion = &reftable_ref_record_is_deletion_void,
471 .equal = &reftable_ref_record_equal_void,
472 .cmp = &reftable_ref_record_cmp_void,
473};
474
475static int reftable_obj_record_key(const void *r, struct reftable_buf *dest)
476{
477 const struct reftable_obj_record *rec =
478 (const struct reftable_obj_record *)r;
479 reftable_buf_reset(dest);
480 return reftable_buf_add(dest, rec->hash_prefix, rec->hash_prefix_len);
481}
482
483static void reftable_obj_record_release(void *rec)
484{
485 struct reftable_obj_record *obj = rec;
486 REFTABLE_FREE_AND_NULL(obj->hash_prefix);
487 REFTABLE_FREE_AND_NULL(obj->offsets);
488 memset(obj, 0, sizeof(struct reftable_obj_record));
489}
490
491static int reftable_obj_record_copy_from(void *rec, const void *src_rec,
492 uint32_t hash_size REFTABLE_UNUSED)
493{
494 struct reftable_obj_record *obj = rec;
495 const struct reftable_obj_record *src = src_rec;
496
497 reftable_obj_record_release(obj);
498
499 REFTABLE_ALLOC_ARRAY(obj->hash_prefix, src->hash_prefix_len);
500 if (!obj->hash_prefix)
501 return REFTABLE_OUT_OF_MEMORY_ERROR;
502 obj->hash_prefix_len = src->hash_prefix_len;
503 if (src->hash_prefix_len)
504 memcpy(obj->hash_prefix, src->hash_prefix, obj->hash_prefix_len);
505
506 if (src->offset_len) {
507 if (sizeof(*src->offsets) > SIZE_MAX / src->offset_len)
508 return REFTABLE_OUT_OF_MEMORY_ERROR;
509
510 REFTABLE_ALLOC_ARRAY(obj->offsets, src->offset_len);
511 if (!obj->offsets)
512 return REFTABLE_OUT_OF_MEMORY_ERROR;
513
514 memcpy(obj->offsets, src->offsets, sizeof(*src->offsets) * src->offset_len);
515 obj->offset_len = src->offset_len;
516 }
517
518 return 0;
519}
520
521static uint8_t reftable_obj_record_val_type(const void *rec)
522{
523 const struct reftable_obj_record *r = rec;
524 if (r->offset_len > 0 && r->offset_len < 8)
525 return r->offset_len;
526 return 0;
527}
528
529static int reftable_obj_record_encode(const void *rec, struct string_view s,
530 uint32_t hash_size REFTABLE_UNUSED)
531{
532 const struct reftable_obj_record *r = rec;
533 struct string_view start = s;
534 int i = 0;
535 int n = 0;
536 uint64_t last = 0;
537 if (r->offset_len == 0 || r->offset_len >= 8) {
538 n = put_var_int(&s, r->offset_len);
539 if (n < 0)
540 return n;
541 string_view_consume(&s, n);
542 }
543 if (r->offset_len == 0)
544 return start.len - s.len;
545 n = put_var_int(&s, r->offsets[0]);
546 if (n < 0)
547 return n;
548 string_view_consume(&s, n);
549
550 last = r->offsets[0];
551 for (i = 1; i < r->offset_len; i++) {
552 int n = put_var_int(&s, r->offsets[i] - last);
553 if (n < 0)
554 return n;
555 string_view_consume(&s, n);
556 last = r->offsets[i];
557 }
558 return start.len - s.len;
559}
560
561static int reftable_obj_record_decode(void *rec, struct reftable_buf key,
562 uint8_t val_type, struct string_view in,
563 uint32_t hash_size REFTABLE_UNUSED,
564 struct reftable_buf *scratch REFTABLE_UNUSED)
565{
566 struct string_view start = in;
567 struct reftable_obj_record *r = rec;
568 uint64_t count = val_type;
569 int n = 0;
570 uint64_t last;
571
572 reftable_obj_record_release(r);
573
574 REFTABLE_ALLOC_ARRAY(r->hash_prefix, key.len);
575 if (!r->hash_prefix)
576 return REFTABLE_OUT_OF_MEMORY_ERROR;
577 memcpy(r->hash_prefix, key.buf, key.len);
578 r->hash_prefix_len = key.len;
579
580 if (val_type == 0) {
581 n = get_var_int(&count, &in);
582 if (n < 0) {
583 return n;
584 }
585
586 string_view_consume(&in, n);
587 }
588
589 r->offsets = NULL;
590 r->offset_len = 0;
591 if (count == 0)
592 return start.len - in.len;
593
594 REFTABLE_ALLOC_ARRAY(r->offsets, count);
595 if (!r->offsets)
596 return REFTABLE_OUT_OF_MEMORY_ERROR;
597 r->offset_len = count;
598
599 n = get_var_int(&r->offsets[0], &in);
600 if (n < 0)
601 return n;
602 string_view_consume(&in, n);
603
604 last = r->offsets[0];
605 for (uint64_t j = 1; j < count; j++) {
606 uint64_t delta = 0;
607 int n = get_var_int(&delta, &in);
608 if (n < 0) {
609 return n;
610 }
611 string_view_consume(&in, n);
612
613 last = r->offsets[j] = (delta + last);
614 }
615 return start.len - in.len;
616}
617
618static int not_a_deletion(const void *p REFTABLE_UNUSED)
619{
620 return 0;
621}
622
623static int reftable_obj_record_equal_void(const void *a, const void *b,
624 uint32_t hash_size REFTABLE_UNUSED)
625{
626 struct reftable_obj_record *ra = (struct reftable_obj_record *) a;
627 struct reftable_obj_record *rb = (struct reftable_obj_record *) b;
628
629 if (ra->hash_prefix_len != rb->hash_prefix_len
630 || ra->offset_len != rb->offset_len)
631 return 0;
632
633 if (ra->hash_prefix_len &&
634 memcmp(ra->hash_prefix, rb->hash_prefix, ra->hash_prefix_len))
635 return 0;
636 if (ra->offset_len &&
637 memcmp(ra->offsets, rb->offsets, ra->offset_len * sizeof(uint64_t)))
638 return 0;
639
640 return 1;
641}
642
643static int reftable_obj_record_cmp_void(const void *_a, const void *_b)
644{
645 const struct reftable_obj_record *a = _a;
646 const struct reftable_obj_record *b = _b;
647 int cmp;
648
649 cmp = memcmp(a->hash_prefix, b->hash_prefix,
650 a->hash_prefix_len > b->hash_prefix_len ?
651 a->hash_prefix_len : b->hash_prefix_len);
652 if (cmp)
653 return cmp;
654
655 /*
656 * When the prefix is the same then the object record that is longer is
657 * considered to be bigger.
658 */
659 return a->hash_prefix_len - b->hash_prefix_len;
660}
661
662static struct reftable_record_vtable reftable_obj_record_vtable = {
663 .key = &reftable_obj_record_key,
664 .type = REFTABLE_BLOCK_TYPE_OBJ,
665 .copy_from = &reftable_obj_record_copy_from,
666 .val_type = &reftable_obj_record_val_type,
667 .encode = &reftable_obj_record_encode,
668 .decode = &reftable_obj_record_decode,
669 .release = &reftable_obj_record_release,
670 .is_deletion = ¬_a_deletion,
671 .equal = &reftable_obj_record_equal_void,
672 .cmp = &reftable_obj_record_cmp_void,
673};
674
675static int reftable_log_record_key(const void *r, struct reftable_buf *dest)
676{
677 const struct reftable_log_record *rec =
678 (const struct reftable_log_record *)r;
679 int len = strlen(rec->refname), err;
680 uint8_t i64[8];
681 uint64_t ts = 0;
682
683 reftable_buf_reset(dest);
684 err = reftable_buf_add(dest, (uint8_t *)rec->refname, len + 1);
685 if (err < 0)
686 return err;
687
688 ts = (~ts) - rec->update_index;
689 reftable_put_be64(&i64[0], ts);
690
691 err = reftable_buf_add(dest, i64, sizeof(i64));
692 if (err < 0)
693 return err;
694
695 return 0;
696}
697
698static int reftable_log_record_copy_from(void *rec, const void *src_rec,
699 uint32_t hash_size)
700{
701 struct reftable_log_record *dst = rec;
702 const struct reftable_log_record *src =
703 (const struct reftable_log_record *)src_rec;
704 int ret;
705
706 reftable_log_record_release(dst);
707 *dst = *src;
708
709 if (dst->refname) {
710 dst->refname = reftable_strdup(dst->refname);
711 if (!dst->refname) {
712 ret = REFTABLE_OUT_OF_MEMORY_ERROR;
713 goto out;
714 }
715 }
716
717 switch (dst->value_type) {
718 case REFTABLE_LOG_DELETION:
719 break;
720 case REFTABLE_LOG_UPDATE:
721 if (dst->value.update.email)
722 dst->value.update.email =
723 reftable_strdup(dst->value.update.email);
724 if (dst->value.update.name)
725 dst->value.update.name =
726 reftable_strdup(dst->value.update.name);
727 if (dst->value.update.message)
728 dst->value.update.message =
729 reftable_strdup(dst->value.update.message);
730
731 if (!dst->value.update.email ||
732 !dst->value.update.name ||
733 !dst->value.update.message) {
734 ret = REFTABLE_OUT_OF_MEMORY_ERROR;
735 goto out;
736 }
737
738 memcpy(dst->value.update.new_hash,
739 src->value.update.new_hash, hash_size);
740 memcpy(dst->value.update.old_hash,
741 src->value.update.old_hash, hash_size);
742 break;
743 }
744
745 ret = 0;
746out:
747 return ret;
748}
749
750static void reftable_log_record_release_void(void *rec)
751{
752 struct reftable_log_record *r = rec;
753 reftable_log_record_release(r);
754}
755
756void reftable_log_record_release(struct reftable_log_record *r)
757{
758 reftable_free(r->refname);
759 switch (r->value_type) {
760 case REFTABLE_LOG_DELETION:
761 break;
762 case REFTABLE_LOG_UPDATE:
763 reftable_free(r->value.update.name);
764 reftable_free(r->value.update.email);
765 reftable_free(r->value.update.message);
766 break;
767 }
768 memset(r, 0, sizeof(struct reftable_log_record));
769}
770
771static uint8_t reftable_log_record_val_type(const void *rec)
772{
773 const struct reftable_log_record *log =
774 (const struct reftable_log_record *)rec;
775
776 return reftable_log_record_is_deletion(log) ? 0 : 1;
777}
778
779static int reftable_log_record_encode(const void *rec, struct string_view s,
780 uint32_t hash_size)
781{
782 const struct reftable_log_record *r = rec;
783 struct string_view start = s;
784 int n = 0;
785 if (reftable_log_record_is_deletion(r))
786 return 0;
787
788 if (s.len < 2 * hash_size)
789 return REFTABLE_ENTRY_TOO_BIG_ERROR;
790
791 memcpy(s.buf, r->value.update.old_hash, hash_size);
792 memcpy(s.buf + hash_size, r->value.update.new_hash, hash_size);
793 string_view_consume(&s, 2 * hash_size);
794
795 n = encode_string(r->value.update.name ? r->value.update.name : "", s);
796 if (n < 0)
797 return n;
798 string_view_consume(&s, n);
799
800 n = encode_string(r->value.update.email ? r->value.update.email : "",
801 s);
802 if (n < 0)
803 return n;
804 string_view_consume(&s, n);
805
806 n = put_var_int(&s, r->value.update.time);
807 if (n < 0)
808 return n;
809 string_view_consume(&s, n);
810
811 if (s.len < 2)
812 return REFTABLE_ENTRY_TOO_BIG_ERROR;
813
814 reftable_put_be16(s.buf, r->value.update.tz_offset);
815 string_view_consume(&s, 2);
816
817 n = encode_string(
818 r->value.update.message ? r->value.update.message : "", s);
819 if (n < 0)
820 return n;
821 string_view_consume(&s, n);
822
823 return start.len - s.len;
824}
825
826static int reftable_log_record_decode(void *rec, struct reftable_buf key,
827 uint8_t val_type, struct string_view in,
828 uint32_t hash_size, struct reftable_buf *scratch)
829{
830 struct string_view start = in;
831 struct reftable_log_record *r = rec;
832 uint64_t max = 0;
833 uint64_t ts = 0;
834 int err, n;
835
836 if (key.len <= 9 || key.buf[key.len - 9] != 0)
837 return REFTABLE_FORMAT_ERROR;
838
839 REFTABLE_ALLOC_GROW_OR_NULL(r->refname, key.len - 8, r->refname_cap);
840 if (!r->refname) {
841 err = REFTABLE_OUT_OF_MEMORY_ERROR;
842 goto done;
843 }
844
845 memcpy(r->refname, key.buf, key.len - 8);
846 ts = reftable_get_be64((unsigned char *)key.buf + key.len - 8);
847
848 r->update_index = (~max) - ts;
849
850 if (val_type != r->value_type) {
851 switch (r->value_type) {
852 case REFTABLE_LOG_UPDATE:
853 REFTABLE_FREE_AND_NULL(r->value.update.message);
854 r->value.update.message_cap = 0;
855 REFTABLE_FREE_AND_NULL(r->value.update.email);
856 REFTABLE_FREE_AND_NULL(r->value.update.name);
857 break;
858 case REFTABLE_LOG_DELETION:
859 break;
860 }
861 }
862
863 r->value_type = val_type;
864 if (val_type == REFTABLE_LOG_DELETION)
865 return 0;
866
867 if (in.len < 2 * hash_size) {
868 err = REFTABLE_FORMAT_ERROR;
869 goto done;
870 }
871
872 memcpy(r->value.update.old_hash, in.buf, hash_size);
873 memcpy(r->value.update.new_hash, in.buf + hash_size, hash_size);
874
875 string_view_consume(&in, 2 * hash_size);
876
877 n = decode_string(scratch, in);
878 if (n < 0) {
879 err = REFTABLE_FORMAT_ERROR;
880 goto done;
881 }
882 string_view_consume(&in, n);
883
884 /*
885 * In almost all cases we can expect the reflog name to not change for
886 * reflog entries as they are tied to the local identity, not to the
887 * target commits. As an optimization for this common case we can thus
888 * skip copying over the name in case it's accurate already.
889 */
890 if (!r->value.update.name ||
891 strcmp(r->value.update.name, scratch->buf)) {
892 char *name = reftable_realloc(r->value.update.name, scratch->len + 1);
893 if (!name) {
894 err = REFTABLE_OUT_OF_MEMORY_ERROR;
895 goto done;
896 }
897
898 r->value.update.name = name;
899 memcpy(r->value.update.name, scratch->buf, scratch->len);
900 r->value.update.name[scratch->len] = 0;
901 }
902
903 n = decode_string(scratch, in);
904 if (n < 0) {
905 err = REFTABLE_FORMAT_ERROR;
906 goto done;
907 }
908 string_view_consume(&in, n);
909
910 /* Same as above, but for the reflog email. */
911 if (!r->value.update.email ||
912 strcmp(r->value.update.email, scratch->buf)) {
913 char *email = reftable_realloc(r->value.update.email, scratch->len + 1);
914 if (!email) {
915 err = REFTABLE_OUT_OF_MEMORY_ERROR;
916 goto done;
917 }
918
919 r->value.update.email = email;
920 memcpy(r->value.update.email, scratch->buf, scratch->len);
921 r->value.update.email[scratch->len] = 0;
922 }
923
924 ts = 0;
925 n = get_var_int(&ts, &in);
926 if (n < 0) {
927 err = REFTABLE_FORMAT_ERROR;
928 goto done;
929 }
930 string_view_consume(&in, n);
931 r->value.update.time = ts;
932 if (in.len < 2) {
933 err = REFTABLE_FORMAT_ERROR;
934 goto done;
935 }
936
937 r->value.update.tz_offset = reftable_get_be16(in.buf);
938 string_view_consume(&in, 2);
939
940 n = decode_string(scratch, in);
941 if (n < 0) {
942 err = REFTABLE_FORMAT_ERROR;
943 goto done;
944 }
945 string_view_consume(&in, n);
946
947 REFTABLE_ALLOC_GROW_OR_NULL(r->value.update.message, scratch->len + 1,
948 r->value.update.message_cap);
949 if (!r->value.update.message) {
950 err = REFTABLE_OUT_OF_MEMORY_ERROR;
951 goto done;
952 }
953
954 memcpy(r->value.update.message, scratch->buf, scratch->len);
955 r->value.update.message[scratch->len] = 0;
956
957 return start.len - in.len;
958
959done:
960 return err;
961}
962
963static int null_streq(const char *a, const char *b)
964{
965 const char *empty = "";
966 if (!a)
967 a = empty;
968
969 if (!b)
970 b = empty;
971
972 return 0 == strcmp(a, b);
973}
974
975static int reftable_log_record_equal_void(const void *a,
976 const void *b, uint32_t hash_size)
977{
978 return reftable_log_record_equal((struct reftable_log_record *) a,
979 (struct reftable_log_record *) b,
980 hash_size);
981}
982
983static int reftable_log_record_cmp_void(const void *_a, const void *_b)
984{
985 const struct reftable_log_record *a = _a;
986 const struct reftable_log_record *b = _b;
987 int cmp = strcmp(a->refname, b->refname);
988 if (cmp)
989 return cmp;
990
991 /*
992 * Note that the comparison here is reversed. This is because the
993 * update index is reversed when comparing keys. For reference, see how
994 * we handle this in reftable_log_record_key()`.
995 */
996 return b->update_index - a->update_index;
997}
998
999int reftable_log_record_equal(const struct reftable_log_record *a,
1000 const struct reftable_log_record *b, uint32_t hash_size)
1001{
1002 // Implemented in reftable_record.rs
1003 if (!(null_streq(a->refname, b->refname) &&
1004 a->update_index == b->update_index &&
1005 a->value_type == b->value_type))
1006 return 0;
1007
1008 switch (a->value_type) {
1009 case REFTABLE_LOG_DELETION:
1010 return 1;
1011 case REFTABLE_LOG_UPDATE:
1012 return null_streq(a->value.update.name, b->value.update.name) &&
1013 a->value.update.time == b->value.update.time &&
1014 a->value.update.tz_offset == b->value.update.tz_offset &&
1015 null_streq(a->value.update.email,
1016 b->value.update.email) &&
1017 null_streq(a->value.update.message,
1018 b->value.update.message) &&
1019 !memcmp(a->value.update.old_hash,
1020 b->value.update.old_hash, hash_size) &&
1021 !memcmp(a->value.update.new_hash,
1022 b->value.update.new_hash, hash_size);
1023 }
1024
1025 abort();
1026}
1027
1028static int reftable_log_record_is_deletion_void(const void *p)
1029{
1030 return reftable_log_record_is_deletion(
1031 (const struct reftable_log_record *)p);
1032}
1033
1034static struct reftable_record_vtable reftable_log_record_vtable = {
1035 .key = &reftable_log_record_key,
1036 .type = REFTABLE_BLOCK_TYPE_LOG,
1037 .copy_from = &reftable_log_record_copy_from,
1038 .val_type = &reftable_log_record_val_type,
1039 .encode = &reftable_log_record_encode,
1040 .decode = &reftable_log_record_decode,
1041 .release = &reftable_log_record_release_void,
1042 .is_deletion = &reftable_log_record_is_deletion_void,
1043 .equal = &reftable_log_record_equal_void,
1044 .cmp = &reftable_log_record_cmp_void,
1045};
1046
1047static int reftable_index_record_key(const void *r, struct reftable_buf *dest)
1048{
1049 const struct reftable_index_record *rec = r;
1050 reftable_buf_reset(dest);
1051 return reftable_buf_add(dest, rec->last_key.buf, rec->last_key.len);
1052}
1053
1054static int reftable_index_record_copy_from(void *rec, const void *src_rec,
1055 uint32_t hash_size REFTABLE_UNUSED)
1056{
1057 struct reftable_index_record *dst = rec;
1058 const struct reftable_index_record *src = src_rec;
1059 int err;
1060
1061 reftable_buf_reset(&dst->last_key);
1062 err = reftable_buf_add(&dst->last_key, src->last_key.buf, src->last_key.len);
1063 if (err < 0)
1064 return err;
1065 dst->offset = src->offset;
1066
1067 return 0;
1068}
1069
1070static void reftable_index_record_release(void *rec)
1071{
1072 struct reftable_index_record *idx = rec;
1073 reftable_buf_release(&idx->last_key);
1074}
1075
1076static uint8_t reftable_index_record_val_type(const void *rec REFTABLE_UNUSED)
1077{
1078 return 0;
1079}
1080
1081static int reftable_index_record_encode(const void *rec, struct string_view out,
1082 uint32_t hash_size REFTABLE_UNUSED)
1083{
1084 const struct reftable_index_record *r =
1085 (const struct reftable_index_record *)rec;
1086 struct string_view start = out;
1087
1088 int n = put_var_int(&out, r->offset);
1089 if (n < 0)
1090 return n;
1091
1092 string_view_consume(&out, n);
1093
1094 return start.len - out.len;
1095}
1096
1097static int reftable_index_record_decode(void *rec, struct reftable_buf key,
1098 uint8_t val_type REFTABLE_UNUSED,
1099 struct string_view in,
1100 uint32_t hash_size REFTABLE_UNUSED,
1101 struct reftable_buf *scratch REFTABLE_UNUSED)
1102{
1103 struct string_view start = in;
1104 struct reftable_index_record *r = rec;
1105 int err, n = 0;
1106
1107 reftable_buf_reset(&r->last_key);
1108 err = reftable_buf_add(&r->last_key, key.buf, key.len);
1109 if (err < 0)
1110 return err;
1111
1112 n = get_var_int(&r->offset, &in);
1113 if (n < 0)
1114 return n;
1115
1116 string_view_consume(&in, n);
1117 return start.len - in.len;
1118}
1119
1120static int reftable_index_record_equal(const void *a, const void *b,
1121 uint32_t hash_size REFTABLE_UNUSED)
1122{
1123 struct reftable_index_record *ia = (struct reftable_index_record *) a;
1124 struct reftable_index_record *ib = (struct reftable_index_record *) b;
1125
1126 return ia->offset == ib->offset && !reftable_buf_cmp(&ia->last_key, &ib->last_key);
1127}
1128
1129static int reftable_index_record_cmp(const void *_a, const void *_b)
1130{
1131 const struct reftable_index_record *a = _a;
1132 const struct reftable_index_record *b = _b;
1133 return reftable_buf_cmp(&a->last_key, &b->last_key);
1134}
1135
1136static struct reftable_record_vtable reftable_index_record_vtable = {
1137 .key = &reftable_index_record_key,
1138 .type = REFTABLE_BLOCK_TYPE_INDEX,
1139 .copy_from = &reftable_index_record_copy_from,
1140 .val_type = &reftable_index_record_val_type,
1141 .encode = &reftable_index_record_encode,
1142 .decode = &reftable_index_record_decode,
1143 .release = &reftable_index_record_release,
1144 .is_deletion = ¬_a_deletion,
1145 .equal = &reftable_index_record_equal,
1146 .cmp = &reftable_index_record_cmp,
1147};
1148
1149int reftable_record_key(struct reftable_record *rec, struct reftable_buf *dest)
1150{
1151 return reftable_record_vtable(rec)->key(reftable_record_data(rec), dest);
1152}
1153
1154int reftable_record_encode(struct reftable_record *rec, struct string_view dest,
1155 uint32_t hash_size)
1156{
1157 return reftable_record_vtable(rec)->encode(reftable_record_data(rec),
1158 dest, hash_size);
1159}
1160
1161int reftable_record_copy_from(struct reftable_record *rec,
1162 struct reftable_record *src, uint32_t hash_size)
1163{
1164 assert(src->type == rec->type);
1165
1166 return reftable_record_vtable(rec)->copy_from(reftable_record_data(rec),
1167 reftable_record_data(src),
1168 hash_size);
1169}
1170
1171uint8_t reftable_record_val_type(struct reftable_record *rec)
1172{
1173 return reftable_record_vtable(rec)->val_type(reftable_record_data(rec));
1174}
1175
1176int reftable_record_decode(struct reftable_record *rec, struct reftable_buf key,
1177 uint8_t extra, struct string_view src, uint32_t hash_size,
1178 struct reftable_buf *scratch)
1179{
1180 return reftable_record_vtable(rec)->decode(reftable_record_data(rec),
1181 key, extra, src, hash_size,
1182 scratch);
1183}
1184
1185void reftable_record_release(struct reftable_record *rec)
1186{
1187 reftable_record_vtable(rec)->release(reftable_record_data(rec));
1188}
1189
1190int reftable_record_is_deletion(struct reftable_record *rec)
1191{
1192 return reftable_record_vtable(rec)->is_deletion(
1193 reftable_record_data(rec));
1194}
1195
1196int reftable_record_cmp(struct reftable_record *a, struct reftable_record *b,
1197 int *cmp)
1198{
1199 if (a->type != b->type)
1200 return -1;
1201 *cmp = reftable_record_vtable(a)->cmp(reftable_record_data(a),
1202 reftable_record_data(b));
1203 return 0;
1204}
1205
1206int reftable_record_equal(struct reftable_record *a, struct reftable_record *b, uint32_t hash_size)
1207{
1208 if (a->type != b->type)
1209 return 0;
1210 return reftable_record_vtable(a)->equal(
1211 reftable_record_data(a), reftable_record_data(b), hash_size);
1212}
1213
1214static int hash_equal(const unsigned char *a, const unsigned char *b, uint32_t hash_size)
1215{
1216 // Implemented in reftable_basics.rs
1217 if (a && b)
1218 return !memcmp(a, b, hash_size);
1219
1220 return a == b;
1221}
1222
1223int reftable_ref_record_equal(const struct reftable_ref_record *a,
1224 const struct reftable_ref_record *b, uint32_t hash_size)
1225{
1226 // Implemented in reftable_record.rs
1227 if (!null_streq(a->refname, b->refname))
1228 return 0;
1229
1230 if (a->update_index != b->update_index ||
1231 a->value_type != b->value_type)
1232 return 0;
1233
1234 switch (a->value_type) {
1235 case REFTABLE_REF_SYMREF:
1236 return !strcmp(a->value.symref, b->value.symref);
1237 case REFTABLE_REF_VAL2:
1238 return hash_equal(a->value.val2.value, b->value.val2.value,
1239 hash_size) &&
1240 hash_equal(a->value.val2.target_value,
1241 b->value.val2.target_value, hash_size);
1242 case REFTABLE_REF_VAL1:
1243 return hash_equal(a->value.val1, b->value.val1, hash_size);
1244 case REFTABLE_REF_DELETION:
1245 return 1;
1246 default:
1247 abort();
1248 }
1249}
1250
1251int reftable_ref_record_compare_name(const void *a, const void *b)
1252{
1253 return strcmp(((struct reftable_ref_record *)a)->refname,
1254 ((struct reftable_ref_record *)b)->refname);
1255}
1256
1257int reftable_ref_record_is_deletion(const struct reftable_ref_record *ref)
1258{
1259 return ref->value_type == REFTABLE_REF_DELETION;
1260}
1261
1262int reftable_log_record_compare_key(const void *a, const void *b)
1263{
1264 const struct reftable_log_record *la = a;
1265 const struct reftable_log_record *lb = b;
1266
1267 int cmp = strcmp(la->refname, lb->refname);
1268 if (cmp)
1269 return cmp;
1270 if (la->update_index > lb->update_index)
1271 return -1;
1272 return (la->update_index < lb->update_index) ? 1 : 0;
1273}
1274
1275int reftable_log_record_is_deletion(const struct reftable_log_record *log)
1276{
1277 // Implemented in reftable_record.rs
1278 return (log->value_type == REFTABLE_LOG_DELETION);
1279}
1280
1281static void *reftable_record_data(struct reftable_record *rec)
1282{
1283 switch (rec->type) {
1284 case REFTABLE_BLOCK_TYPE_REF:
1285 return &rec->u.ref;
1286 case REFTABLE_BLOCK_TYPE_LOG:
1287 return &rec->u.log;
1288 case REFTABLE_BLOCK_TYPE_INDEX:
1289 return &rec->u.idx;
1290 case REFTABLE_BLOCK_TYPE_OBJ:
1291 return &rec->u.obj;
1292 }
1293 abort();
1294}
1295
1296static struct reftable_record_vtable *
1297reftable_record_vtable(struct reftable_record *rec)
1298{
1299 switch (rec->type) {
1300 case REFTABLE_BLOCK_TYPE_REF:
1301 return &reftable_ref_record_vtable;
1302 case REFTABLE_BLOCK_TYPE_LOG:
1303 return &reftable_log_record_vtable;
1304 case REFTABLE_BLOCK_TYPE_INDEX:
1305 return &reftable_index_record_vtable;
1306 case REFTABLE_BLOCK_TYPE_OBJ:
1307 return &reftable_obj_record_vtable;
1308 }
1309 abort();
1310}
1311
1312int reftable_record_init(struct reftable_record *rec, uint8_t typ)
1313{
1314 memset(rec, 0, sizeof(*rec));
1315 rec->type = typ;
1316
1317 switch (typ) {
1318 case REFTABLE_BLOCK_TYPE_REF:
1319 case REFTABLE_BLOCK_TYPE_LOG:
1320 case REFTABLE_BLOCK_TYPE_OBJ:
1321 return 0;
1322 case REFTABLE_BLOCK_TYPE_INDEX:
1323 reftable_buf_init(&rec->u.idx.last_key);
1324 return 0;
1325 default:
1326 return REFTABLE_API_ERROR;
1327 }
1328}