reftable/record.c

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