src/odb.c

   1 /*
   2  * Copyright (C) the libgit2 contributors. All rights reserved.
   3  *
   4  * This file is part of libgit2, distributed under the GNU GPL v2 with
   5  * a Linking Exception. For full terms see the included COPYING file.
   6  */
   7
   8 #include "common.h"
   9 #include <zlib.h>
  10 #include "git2/object.h"
  11 #include "git2/sys/odb_backend.h"
  12 #include "fileops.h"
  13 #include "hash.h"
  14 #include "odb.h"
  15 #include "delta-apply.h"
  16 #include "filter.h"
  17 #include "repository.h"
  18
  19 #include "git2/odb_backend.h"
  20 #include "git2/oid.h"
  21 #include "git2/oidarray.h"
  22
  23 #define GIT_ALTERNATES_FILE "info/alternates"
  24
  25 /*
  26  * We work under the assumption that most objects for long-running
  27  * operations will be packed
  28  */
  29 #define GIT_LOOSE_PRIORITY 1
  30 #define GIT_PACKED_PRIORITY 2
  31
  32 #define GIT_ALTERNATES_MAX_DEPTH 5
  33
  34 typedef struct
  35 {
  36         git_odb_backend *backend;
  37         int priority;
  38         bool is_alternate;
  39         ino_t disk_inode;
  40 } backend_internal;
  41
  42 static git_cache *odb_cache(git_odb *odb)
  43 {
  44         if (odb->rc.owner != NULL) {
  45                 git_repository *owner = odb->rc.owner;
  46                 return &owner->objects;
  47         }
  48
  49         return &odb->own_cache;
  50 }
  51
  52 static int load_alternates(git_odb *odb, const char *objects_dir, int alternate_depth);
  53
  54 int git_odb__format_object_header(char *hdr, size_t n, git_off_t obj_len, git_otype obj_type)
  55 {
  56         const char *type_str = git_object_type2string(obj_type);
  57         int len = p_snprintf(hdr, n, "%s %lld", type_str, (long long)obj_len);
  58         assert(len > 0 && len <= (int)n);
  59         return len+1;
  60 }
  61
  62 int git_odb__hashobj(git_oid *id, git_rawobj *obj)
  63 {
  64         git_buf_vec vec[2];
  65         char header[64];
  66         int hdrlen;
  67
  68         assert(id && obj);
  69
  70         if (!git_object_typeisloose(obj->type))
  71                 return -1;
  72
  73         if (!obj->data && obj->len != 0)
  74                 return -1;
  75
  76         hdrlen = git_odb__format_object_header(header, sizeof(header), obj->len, obj->type);
  77
  78         vec[0].data = header;
  79         vec[0].len = hdrlen;
  80         vec[1].data = obj->data;
  81         vec[1].len = obj->len;
  82
  83         git_hash_vec(id, vec, 2);
  84
  85         return 0;
  86 }
  87
  88
  89 static git_odb_object *odb_object__alloc(const git_oid *oid, git_rawobj *source)
  90 {
  91         git_odb_object *object = git__calloc(1, sizeof(git_odb_object));
  92
  93         if (object != NULL) {
  94                 git_oid_cpy(&object->cached.oid, oid);
  95                 object->cached.type = source->type;
  96                 object->cached.size = source->len;
  97                 object->buffer      = source->data;
  98         }
  99
 100         return object;
 101 }
 102
 103 void git_odb_object__free(void *object)
 104 {
 105         if (object != NULL) {
 106                 git__free(((git_odb_object *)object)->buffer);
 107                 git__free(object);
 108         }
 109 }
 110
 111 const git_oid *git_odb_object_id(git_odb_object *object)
 112 {
 113         return &object->cached.oid;
 114 }
 115
 116 const void *git_odb_object_data(git_odb_object *object)
 117 {
 118         return object->buffer;
 119 }
 120
 121 size_t git_odb_object_size(git_odb_object *object)
 122 {
 123         return object->cached.size;
 124 }
 125
 126 git_otype git_odb_object_type(git_odb_object *object)
 127 {
 128         return object->cached.type;
 129 }
 130
 131 int git_odb_object_dup(git_odb_object **dest, git_odb_object *source)
 132 {
 133         git_cached_obj_incref(source);
 134         *dest = source;
 135         return 0;
 136 }
 137
 138 void git_odb_object_free(git_odb_object *object)
 139 {
 140         if (object == NULL)
 141                 return;
 142
 143         git_cached_obj_decref(object);
 144 }
 145
 146 int git_odb__hashfd(git_oid *out, git_file fd, size_t size, git_otype type)
 147 {
 148         int hdr_len;
 149         char hdr[64], buffer[FILEIO_BUFSIZE];
 150         git_hash_ctx ctx;
 151         ssize_t read_len = 0;
 152         int error = 0;
 153
 154         if (!git_object_typeisloose(type)) {
 155                 giterr_set(GITERR_INVALID, "Invalid object type for hash");
 156                 return -1;
 157         }
 158
 159         if ((error = git_hash_ctx_init(&ctx)) < 0)
 160                 return -1;
 161
 162         hdr_len = git_odb__format_object_header(hdr, sizeof(hdr), size, type);
 163
 164         if ((error = git_hash_update(&ctx, hdr, hdr_len)) < 0)
 165                 goto done;
 166
 167         while (size > 0 && (read_len = p_read(fd, buffer, sizeof(buffer))) > 0) {
 168                 if ((error = git_hash_update(&ctx, buffer, read_len)) < 0)
 169                         goto done;
 170
 171                 size -= read_len;
 172         }
 173
 174         /* If p_read returned an error code, the read obviously failed.
 175          * If size is not zero, the file was truncated after we originally
 176          * stat'd it, so we consider this a read failure too */
 177         if (read_len < 0 || size > 0) {
 178                 giterr_set(GITERR_OS, "Error reading file for hashing");
 179                 error = -1;
 180
 181                 goto done;
 182         }
 183
 184         error = git_hash_final(out, &ctx);
 185
 186 done:
 187         git_hash_ctx_cleanup(&ctx);
 188         return error;
 189 }
 190
 191 int git_odb__hashfd_filtered(
 192         git_oid *out, git_file fd, size_t size, git_otype type, git_filter_list *fl)
 193 {
 194         int error;
 195         git_buf raw = GIT_BUF_INIT;
 196
 197         if (!fl)
 198                 return git_odb__hashfd(out, fd, size, type);
 199
 200         /* size of data is used in header, so we have to read the whole file
 201          * into memory to apply filters before beginning to calculate the hash
 202          */
 203
 204         if (!(error = git_futils_readbuffer_fd(&raw, fd, size))) {
 205                 git_buf post = GIT_BUF_INIT;
 206
 207                 error = git_filter_list_apply_to_data(&post, fl, &raw);
 208
 209                 git_buf_free(&raw);
 210
 211                 if (!error)
 212                         error = git_odb_hash(out, post.ptr, post.size, type);
 213
 214                 git_buf_free(&post);
 215         }
 216
 217         return error;
 218 }
 219
 220 int git_odb__hashlink(git_oid *out, const char *path)
 221 {
 222         struct stat st;
 223         int size;
 224         int result;
 225
 226         if (git_path_lstat(path, &st) < 0)
 227                 return -1;
 228
 229         if (!git__is_int(st.st_size) || (int)st.st_size < 0) {
 230                 giterr_set(GITERR_FILESYSTEM, "File size overflow for 32-bit systems");
 231                 return -1;
 232         }
 233
 234         size = (int)st.st_size;
 235
 236         if (S_ISLNK(st.st_mode)) {
 237                 char *link_data;
 238                 int read_len;
 239                 size_t alloc_size;
 240
 241                 GITERR_CHECK_ALLOC_ADD(&alloc_size, size, 1);
 242                 link_data = git__malloc(alloc_size);
 243                 GITERR_CHECK_ALLOC(link_data);
 244
 245                 read_len = p_readlink(path, link_data, size);
 246                 link_data[size] = '\0';
 247                 if (read_len != size) {
 248                         giterr_set(GITERR_OS, "Failed to read symlink data for '%s'", path);
 249                         git__free(link_data);
 250                         return -1;
 251                 }
 252
 253                 result = git_odb_hash(out, link_data, size, GIT_OBJ_BLOB);
 254                 git__free(link_data);
 255         } else {
 256                 int fd = git_futils_open_ro(path);
 257                 if (fd < 0)
 258                         return -1;
 259                 result = git_odb__hashfd(out, fd, size, GIT_OBJ_BLOB);
 260                 p_close(fd);
 261         }
 262
 263         return result;
 264 }
 265
 266 int git_odb_hashfile(git_oid *out, const char *path, git_otype type)
 267 {
 268         git_off_t size;
 269         int result, fd = git_futils_open_ro(path);
 270         if (fd < 0)
 271                 return fd;
 272
 273         if ((size = git_futils_filesize(fd)) < 0 || !git__is_sizet(size)) {
 274                 giterr_set(GITERR_OS, "File size overflow for 32-bit systems");
 275                 p_close(fd);
 276                 return -1;
 277         }
 278
 279         result = git_odb__hashfd(out, fd, (size_t)size, type);
 280         p_close(fd);
 281         return result;
 282 }
 283
 284 int git_odb_hash(git_oid *id, const void *data, size_t len, git_otype type)
 285 {
 286         git_rawobj raw;
 287
 288         assert(id);
 289
 290         raw.data = (void *)data;
 291         raw.len = len;
 292         raw.type = type;
 293
 294         return git_odb__hashobj(id, &raw);
 295 }
 296
 297 /**
 298  * FAKE WSTREAM
 299  */
 300
 301 typedef struct {
 302         git_odb_stream stream;
 303         char *buffer;
 304         size_t size, written;
 305         git_otype type;
 306 } fake_wstream;
 307
 308 static int fake_wstream__fwrite(git_odb_stream *_stream, const git_oid *oid)
 309 {
 310         fake_wstream *stream = (fake_wstream *)_stream;
 311         return _stream->backend->write(_stream->backend, oid, stream->buffer, stream->size, stream->type);
 312 }
 313
 314 static int fake_wstream__write(git_odb_stream *_stream, const char *data, size_t len)
 315 {
 316         fake_wstream *stream = (fake_wstream *)_stream;
 317
 318         if (stream->written + len > stream->size)
 319                 return -1;
 320
 321         memcpy(stream->buffer + stream->written, data, len);
 322         stream->written += len;
 323         return 0;
 324 }
 325
 326 static void fake_wstream__free(git_odb_stream *_stream)
 327 {
 328         fake_wstream *stream = (fake_wstream *)_stream;
 329
 330         git__free(stream->buffer);
 331         git__free(stream);
 332 }
 333
 334 static int init_fake_wstream(git_odb_stream **stream_p, git_odb_backend *backend, git_off_t size, git_otype type)
 335 {
 336         fake_wstream *stream;
 337
 338         if (!git__is_ssizet(size)) {
 339                 giterr_set(GITERR_ODB, "object size too large to keep in memory");
 340                 return -1;
 341         }
 342
 343         stream = git__calloc(1, sizeof(fake_wstream));
 344         GITERR_CHECK_ALLOC(stream);
 345
 346         stream->size = size;
 347         stream->type = type;
 348         stream->buffer = git__malloc(size);
 349         if (stream->buffer == NULL) {
 350                 git__free(stream);
 351                 return -1;
 352         }
 353
 354         stream->stream.backend = backend;
 355         stream->stream.read = NULL; /* read only */
 356         stream->stream.write = &fake_wstream__write;
 357         stream->stream.finalize_write = &fake_wstream__fwrite;
 358         stream->stream.free = &fake_wstream__free;
 359         stream->stream.mode = GIT_STREAM_WRONLY;
 360
 361         *stream_p = (git_odb_stream *)stream;
 362         return 0;
 363 }
 364
 365 /***********************************************************
 366  *
 367  * OBJECT DATABASE PUBLIC API
 368  *
 369  * Public calls for the ODB functionality
 370  *
 371  ***********************************************************/
 372
 373 static int backend_sort_cmp(const void *a, const void *b)
 374 {
 375         const backend_internal *backend_a = (const backend_internal *)(a);
 376         const backend_internal *backend_b = (const backend_internal *)(b);
 377
 378         if (backend_b->priority == backend_a->priority) {
 379                 if (backend_a->is_alternate)
 380                         return -1;
 381                 if (backend_b->is_alternate)
 382                         return 1;
 383                 return 0;
 384         }
 385         return (backend_b->priority - backend_a->priority);
 386 }
 387
 388 int git_odb_new(git_odb **out)
 389 {
 390         git_odb *db = git__calloc(1, sizeof(*db));
 391         GITERR_CHECK_ALLOC(db);
 392
 393         if (git_cache_init(&db->own_cache) < 0 ||
 394                 git_vector_init(&db->backends, 4, backend_sort_cmp) < 0) {
 395                 git__free(db);
 396                 return -1;
 397         }
 398
 399         *out = db;
 400         GIT_REFCOUNT_INC(db);
 401         return 0;
 402 }
 403
 404 static int add_backend_internal(
 405         git_odb *odb, git_odb_backend *backend,
 406         int priority, bool is_alternate, ino_t disk_inode)
 407 {
 408         backend_internal *internal;
 409
 410         assert(odb && backend);
 411
 412         GITERR_CHECK_VERSION(backend, GIT_ODB_BACKEND_VERSION, "git_odb_backend");
 413
 414         /* Check if the backend is already owned by another ODB */
 415         assert(!backend->odb || backend->odb == odb);
 416
 417         internal = git__malloc(sizeof(backend_internal));
 418         GITERR_CHECK_ALLOC(internal);
 419
 420         internal->backend = backend;
 421         internal->priority = priority;
 422         internal->is_alternate = is_alternate;
 423         internal->disk_inode = disk_inode;
 424
 425         if (git_vector_insert(&odb->backends, internal) < 0) {
 426                 git__free(internal);
 427                 return -1;
 428         }
 429
 430         git_vector_sort(&odb->backends);
 431         internal->backend->odb = odb;
 432         return 0;
 433 }
 434
 435 int git_odb_add_backend(git_odb *odb, git_odb_backend *backend, int priority)
 436 {
 437         return add_backend_internal(odb, backend, priority, false, 0);
 438 }
 439
 440 int git_odb_add_alternate(git_odb *odb, git_odb_backend *backend, int priority)
 441 {
 442         return add_backend_internal(odb, backend, priority, true, 0);
 443 }
 444
 445 size_t git_odb_num_backends(git_odb *odb)
 446 {
 447         assert(odb);
 448         return odb->backends.length;
 449 }
 450
 451 static int git_odb__error_unsupported_in_backend(const char *action)
 452 {
 453         giterr_set(GITERR_ODB,
 454                 "Cannot %s - unsupported in the loaded odb backends", action);
 455         return -1;
 456 }
 457
 458
 459 int git_odb_get_backend(git_odb_backend **out, git_odb *odb, size_t pos)
 460 {
 461         backend_internal *internal;
 462
 463         assert(out && odb);
 464         internal = git_vector_get(&odb->backends, pos);
 465
 466         if (internal && internal->backend) {
 467                 *out = internal->backend;
 468                 return 0;
 469         }
 470
 471         giterr_set(GITERR_ODB, "No ODB backend loaded at index %" PRIuZ, pos);
 472         return GIT_ENOTFOUND;
 473 }
 474
 475 static int add_default_backends(
 476         git_odb *db, const char *objects_dir,
 477         bool as_alternates, int alternate_depth)
 478 {
 479         size_t i;
 480         struct stat st;
 481         ino_t inode;
 482         git_odb_backend *loose, *packed;
 483
 484         /* TODO: inodes are not really relevant on Win32, so we need to find
 485          * a cross-platform workaround for this */
 486 #ifdef GIT_WIN32
 487         GIT_UNUSED(i);
 488         GIT_UNUSED(st);
 489
 490         inode = 0;
 491 #else
 492         if (p_stat(objects_dir, &st) < 0) {
 493                 if (as_alternates)
 494                         return 0;
 495
 496                 giterr_set(GITERR_ODB, "Failed to load object database in '%s'", objects_dir);
 497                 return -1;
 498         }
 499
 500         inode = st.st_ino;
 501
 502         for (i = 0; i < db->backends.length; ++i) {
 503                 backend_internal *backend = git_vector_get(&db->backends, i);
 504                 if (backend->disk_inode == inode)
 505                         return 0;
 506         }
 507 #endif
 508
 509         /* add the loose object backend */
 510         if (git_odb_backend_loose(&loose, objects_dir, -1, 0, 0, 0) < 0 ||
 511                 add_backend_internal(db, loose, GIT_LOOSE_PRIORITY, as_alternates, inode) < 0)
 512                 return -1;
 513
 514         /* add the packed file backend */
 515         if (git_odb_backend_pack(&packed, objects_dir) < 0 ||
 516                 add_backend_internal(db, packed, GIT_PACKED_PRIORITY, as_alternates, inode) < 0)
 517                 return -1;
 518
 519         return load_alternates(db, objects_dir, alternate_depth);
 520 }
 521
 522 static int load_alternates(git_odb *odb, const char *objects_dir, int alternate_depth)
 523 {
 524         git_buf alternates_path = GIT_BUF_INIT;
 525         git_buf alternates_buf = GIT_BUF_INIT;
 526         char *buffer;
 527         const char *alternate;
 528         int result = 0;
 529
 530         /* Git reports an error, we just ignore anything deeper */
 531         if (alternate_depth > GIT_ALTERNATES_MAX_DEPTH)
 532                 return 0;
 533
 534         if (git_buf_joinpath(&alternates_path, objects_dir, GIT_ALTERNATES_FILE) < 0)
 535                 return -1;
 536
 537         if (git_path_exists(alternates_path.ptr) == false) {
 538                 git_buf_free(&alternates_path);
 539                 return 0;
 540         }
 541
 542         if (git_futils_readbuffer(&alternates_buf, alternates_path.ptr) < 0) {
 543                 git_buf_free(&alternates_path);
 544                 return -1;
 545         }
 546
 547         buffer = (char *)alternates_buf.ptr;
 548
 549         /* add each alternate as a new backend; one alternate per line */
 550         while ((alternate = git__strtok(&buffer, "\r\n")) != NULL) {
 551                 if (*alternate == '\0' || *alternate == '#')
 552                         continue;
 553
 554                 /*
 555                  * Relative path: build based on the current `objects`
 556                  * folder. However, relative paths are only allowed in
 557                  * the current repository.
 558                  */
 559                 if (*alternate == '.' && !alternate_depth) {
 560                         if ((result = git_buf_joinpath(&alternates_path, objects_dir, alternate)) < 0)
 561                                 break;
 562                         alternate = git_buf_cstr(&alternates_path);
 563                 }
 564
 565                 if ((result = add_default_backends(odb, alternate, true, alternate_depth + 1)) < 0)
 566                         break;
 567         }
 568
 569         git_buf_free(&alternates_path);
 570         git_buf_free(&alternates_buf);
 571
 572         return result;
 573 }
 574
 575 int git_odb_add_disk_alternate(git_odb *odb, const char *path)
 576 {
 577         return add_default_backends(odb, path, true, 0);
 578 }
 579
 580 int git_odb_open(git_odb **out, const char *objects_dir)
 581 {
 582         git_odb *db;
 583
 584         assert(out && objects_dir);
 585
 586         *out = NULL;
 587
 588         if (git_odb_new(&db) < 0)
 589                 return -1;
 590
 591         if (add_default_backends(db, objects_dir, 0, 0) < 0) {
 592                 git_odb_free(db);
 593                 return -1;
 594         }
 595
 596         *out = db;
 597         return 0;
 598 }
 599
 600 static void odb_free(git_odb *db)
 601 {
 602         size_t i;
 603
 604         for (i = 0; i < db->backends.length; ++i) {
 605                 backend_internal *internal = git_vector_get(&db->backends, i);
 606                 git_odb_backend *backend = internal->backend;
 607
 608                 backend->free(backend);
 609
 610                 git__free(internal);
 611         }
 612
 613         git_vector_free(&db->backends);
 614         git_cache_free(&db->own_cache);
 615
 616         git__memzero(db, sizeof(*db));
 617         git__free(db);
 618 }
 619
 620 void git_odb_free(git_odb *db)
 621 {
 622         if (db == NULL)
 623                 return;
 624
 625         GIT_REFCOUNT_DEC(db, odb_free);
 626 }
 627
 628 static int odb_exists_1(git_odb *db, const git_oid *id, bool only_refreshed)
 629 {
 630         size_t i;
 631         bool found = false;
 632
 633         for (i = 0; i < db->backends.length && !found; ++i) {
 634                 backend_internal *internal = git_vector_get(&db->backends, i);
 635                 git_odb_backend *b = internal->backend;
 636
 637                 if (only_refreshed && !b->refresh)
 638                         continue;
 639
 640                 if (b->exists != NULL)
 641                         found = (bool)b->exists(b, id);
 642         }
 643
 644         return (int)found;
 645 }
 646
 647 int git_odb_exists(git_odb *db, const git_oid *id)
 648 {
 649         git_odb_object *object;
 650
 651         assert(db && id);
 652
 653         if ((object = git_cache_get_raw(odb_cache(db), id)) != NULL) {
 654                 git_odb_object_free(object);
 655                 return 1;
 656         }
 657
 658         if (odb_exists_1(db, id, false))
 659                 return 1;
 660
 661         if (!git_odb_refresh(db))
 662                 return odb_exists_1(db, id, true);
 663
 664         /* Failed to refresh, hence not found */
 665         return 0;
 666 }
 667
 668 static int odb_exists_prefix_1(git_oid *out, git_odb *db,
 669         const git_oid *key, size_t len, bool only_refreshed)
 670 {
 671         size_t i;
 672         int error = GIT_ENOTFOUND, num_found = 0;
 673         git_oid last_found = {{0}}, found;
 674
 675         for (i = 0; i < db->backends.length; ++i) {
 676                 backend_internal *internal = git_vector_get(&db->backends, i);
 677                 git_odb_backend *b = internal->backend;
 678
 679                 if (only_refreshed && !b->refresh)
 680                         continue;
 681
 682                 if (!b->exists_prefix)
 683                         continue;
 684
 685                 error = b->exists_prefix(&found, b, key, len);
 686                 if (error == GIT_ENOTFOUND || error == GIT_PASSTHROUGH)
 687                         continue;
 688                 if (error)
 689                         return error;
 690
 691                 /* make sure found item doesn't introduce ambiguity */
 692                 if (num_found) {
 693                         if (git_oid__cmp(&last_found, &found))
 694                                 return git_odb__error_ambiguous("multiple matches for prefix");
 695                 } else {
 696                         git_oid_cpy(&last_found, &found);
 697                         num_found++;
 698                 }
 699         }
 700
 701         if (!num_found)
 702                 return GIT_ENOTFOUND;
 703
 704         if (out)
 705                 git_oid_cpy(out, &last_found);
 706
 707         return 0;
 708 }
 709
 710 int git_odb_exists_prefix(
 711         git_oid *out, git_odb *db, const git_oid *short_id, size_t len)
 712 {
 713         int error;
 714         git_oid key = {{0}};
 715
 716         assert(db && short_id);
 717
 718         if (len < GIT_OID_MINPREFIXLEN)
 719                 return git_odb__error_ambiguous("prefix length too short");
 720
 721         if (len >= GIT_OID_HEXSZ) {
 722                 if (git_odb_exists(db, short_id)) {
 723                         if (out)
 724                                 git_oid_cpy(out, short_id);
 725                         return 0;
 726                 } else {
 727                         return git_odb__error_notfound(
 728                                 "no match for id prefix", short_id, len);
 729                 }
 730         }
 731
 732         git_oid__cpy_prefix(&key, short_id, len);
 733
 734         error = odb_exists_prefix_1(out, db, &key, len, false);
 735
 736         if (error == GIT_ENOTFOUND && !git_odb_refresh(db))
 737                 error = odb_exists_prefix_1(out, db, &key, len, true);
 738
 739         if (error == GIT_ENOTFOUND)
 740                 return git_odb__error_notfound("no match for id prefix", &key, len);
 741
 742         return error;
 743 }
 744
 745 int git_odb_expand_ids(
 746         git_odb *db,
 747         git_oid *ids,
 748         size_t *id_lengths,
 749         git_otype *types,
 750         size_t cnt)
 751 {
 752         size_t len, i;
 753         int error;
 754
 755         assert(db && ids && id_lengths);
 756
 757         for (i = 0; i < cnt; i++) {
 758                 git_oid *actual_id = NULL, tmp;
 759                 git_otype actual_type = 0;
 760
 761                 /* if we were given a full object ID, simply look it up */
 762                 if (id_lengths[i] >= GIT_OID_HEXSZ) {
 763                         error = git_odb_read_header(&len, &actual_type, db, &ids[i]);
 764                 }
 765
 766                 /* otherwise, resolve the short id to full, then (optionally)
 767                  * read the header.
 768                  */
 769                 else if (id_lengths[i] >= GIT_OID_MINPREFIXLEN) {
 770                 error = odb_exists_prefix_1(&tmp,
 771                                 db, &ids[i], id_lengths[i], false);
 772
 773                         if (!error) {
 774                                 actual_id = &tmp;
 775
 776                                 if (types)
 777                                         error = git_odb_read_header(&len, &actual_type, db, &tmp);
 778                                 else
 779                                         actual_type = GIT_OBJ_ANY;
 780                         }
 781                 }
 782
 783                 if (error < 0 && error != GIT_ENOTFOUND && error != GIT_EAMBIGUOUS)
 784                         break;
 785
 786                 error = 0;
 787
 788                 if (types && types[i] != GIT_OBJ_ANY && types[i] != actual_type)
 789                         actual_type = 0;
 790
 791                 if (!actual_type) {
 792                         memset(&ids[i], 0, sizeof(git_oid));
 793                         id_lengths[i] = 0;
 794
 795                         if (types)
 796                                 types[i] = 0;
 797                 } else {
 798                         if (actual_id)
 799                                 git_oid_cpy(&ids[i], actual_id);
 800
 801                         id_lengths[i] = GIT_OID_HEXSZ;
 802
 803                         if (types)
 804                                 types[i] = actual_type;
 805                 }
 806         }
 807
 808         if (!error)
 809                 giterr_clear();
 810
 811         return error;
 812 }
 813
 814 int git_odb_read_header(size_t *len_p, git_otype *type_p, git_odb *db, const git_oid *id)
 815 {
 816         int error;
 817         git_odb_object *object;
 818
 819         error = git_odb__read_header_or_object(&object, len_p, type_p, db, id);
 820
 821         if (object)
 822                 git_odb_object_free(object);
 823
 824         return error;
 825 }
 826
 827 int git_odb__read_header_or_object(
 828         git_odb_object **out, size_t *len_p, git_otype *type_p,
 829         git_odb *db, const git_oid *id)
 830 {
 831         size_t i;
 832         int error = GIT_ENOTFOUND;
 833         git_odb_object *object;
 834
 835         assert(db && id && out && len_p && type_p);
 836
 837         if ((object = git_cache_get_raw(odb_cache(db), id)) != NULL) {
 838                 *len_p = object->cached.size;
 839                 *type_p = object->cached.type;
 840                 *out = object;
 841                 return 0;
 842         }
 843
 844         *out = NULL;
 845
 846         for (i = 0; i < db->backends.length && error < 0; ++i) {
 847                 backend_internal *internal = git_vector_get(&db->backends, i);
 848                 git_odb_backend *b = internal->backend;
 849
 850                 if (b->read_header != NULL)
 851                         error = b->read_header(len_p, type_p, b, id);
 852         }
 853
 854         if (!error || error == GIT_PASSTHROUGH)
 855                 return 0;
 856
 857         /*
 858          * no backend could read only the header.
 859          * try reading the whole object and freeing the contents
 860          */
 861         if ((error = git_odb_read(&object, db, id)) < 0)
 862                 return error; /* error already set - pass along */
 863
 864         *len_p = object->cached.size;
 865         *type_p = object->cached.type;
 866         *out = object;
 867
 868         return 0;
 869 }
 870
 871 static git_oid empty_blob = {{ 0xe6, 0x9d, 0xe2, 0x9b, 0xb2, 0xd1, 0xd6, 0x43, 0x4b, 0x8b,
 872                                0x29, 0xae, 0x77, 0x5a, 0xd8, 0xc2, 0xe4, 0x8c, 0x53, 0x91 }};
 873 static git_oid empty_tree = {{ 0x4b, 0x82, 0x5d, 0xc6, 0x42, 0xcb, 0x6e, 0xb9, 0xa0, 0x60,
 874                                0xe5, 0x4b, 0xf8, 0xd6, 0x92, 0x88, 0xfb, 0xee, 0x49, 0x04 }};
 875
 876 static int hardcoded_objects(git_rawobj *raw, const git_oid *id)
 877 {
 878         if (!git_oid_cmp(id, &empty_blob)) {
 879                 raw->type = GIT_OBJ_BLOB;
 880                 raw->len = 0;
 881                 raw->data = git__calloc(1, sizeof(uint8_t));
 882                 return 0;
 883         } else if (!git_oid_cmp(id, &empty_tree)) {
 884                 raw->type = GIT_OBJ_TREE;
 885                 raw->len = 0;
 886                 raw->data = git__calloc(1, sizeof(uint8_t));
 887                 return 0;
 888         } else {
 889                 return GIT_ENOTFOUND;
 890         }
 891 }
 892
 893 static int odb_read_1(git_odb_object **out, git_odb *db, const git_oid *id,
 894                 bool only_refreshed)
 895 {
 896         size_t i;
 897         git_rawobj raw;
 898         git_odb_object *object;
 899         bool found = false;
 900
 901         if (!hardcoded_objects(&raw, id))
 902                 found = true;
 903
 904         for (i = 0; i < db->backends.length && !found; ++i) {
 905                 backend_internal *internal = git_vector_get(&db->backends, i);
 906                 git_odb_backend *b = internal->backend;
 907
 908                 if (only_refreshed && !b->refresh)
 909                         continue;
 910
 911                 if (b->read != NULL) {
 912                         int error = b->read(&raw.data, &raw.len, &raw.type, b, id);
 913                         if (error == GIT_PASSTHROUGH || error == GIT_ENOTFOUND)
 914                                 continue;
 915
 916                         if (error < 0)
 917                                 return error;
 918
 919                         found = true;
 920                 }
 921         }
 922
 923         if (!found)
 924                 return GIT_ENOTFOUND;
 925
 926         giterr_clear();
 927         if ((object = odb_object__alloc(id, &raw)) == NULL)
 928                 return -1;
 929
 930         *out = git_cache_store_raw(odb_cache(db), object);
 931         return 0;
 932 }
 933
 934 int git_odb_read(git_odb_object **out, git_odb *db, const git_oid *id)
 935 {
 936         int error;
 937
 938         assert(out && db && id);
 939
 940         *out = git_cache_get_raw(odb_cache(db), id);
 941         if (*out != NULL)
 942                 return 0;
 943
 944         error = odb_read_1(out, db, id, false);
 945
 946         if (error == GIT_ENOTFOUND && !git_odb_refresh(db))
 947                 error = odb_read_1(out, db, id, true);
 948
 949         if (error == GIT_ENOTFOUND)
 950                 return git_odb__error_notfound("no match for id", id, GIT_OID_HEXSZ);
 951
 952         return error;
 953 }
 954
 955 static int read_prefix_1(git_odb_object **out, git_odb *db,
 956                 const git_oid *key, size_t len, bool only_refreshed)
 957 {
 958         size_t i;
 959         int error = GIT_ENOTFOUND;
 960         git_oid found_full_oid = {{0}};
 961         git_rawobj raw;
 962         void *data = NULL;
 963         bool found = false;
 964         git_odb_object *object;
 965
 966         for (i = 0; i < db->backends.length; ++i) {
 967                 backend_internal *internal = git_vector_get(&db->backends, i);
 968                 git_odb_backend *b = internal->backend;
 969
 970                 if (only_refreshed && !b->refresh)
 971                         continue;
 972
 973                 if (b->read_prefix != NULL) {
 974                         git_oid full_oid;
 975                         error = b->read_prefix(&full_oid, &raw.data, &raw.len, &raw.type, b, key, len);
 976                         if (error == GIT_ENOTFOUND || error == GIT_PASSTHROUGH)
 977                                 continue;
 978
 979                         if (error)
 980                                 return error;
 981
 982                         git__free(data);
 983                         data = raw.data;
 984
 985                         if (found && git_oid__cmp(&full_oid, &found_full_oid)) {
 986                                 git__free(raw.data);
 987                                 return git_odb__error_ambiguous("multiple matches for prefix");
 988                         }
 989
 990                         found_full_oid = full_oid;
 991                         found = true;
 992                 }
 993         }
 994
 995         if (!found)
 996                 return GIT_ENOTFOUND;
 997
 998         if ((object = odb_object__alloc(&found_full_oid, &raw)) == NULL)
 999                 return -1;
1000
1001         *out = git_cache_store_raw(odb_cache(db), object);
1002         return 0;
1003 }
1004
1005 int git_odb_read_prefix(
1006         git_odb_object **out, git_odb *db, const git_oid *short_id, size_t len)
1007 {
1008         git_oid key = {{0}};
1009         int error;
1010
1011         assert(out && db);
1012
1013         if (len < GIT_OID_MINPREFIXLEN)
1014                 return git_odb__error_ambiguous("prefix length too short");
1015
1016         if (len > GIT_OID_HEXSZ)
1017                 len = GIT_OID_HEXSZ;
1018
1019         if (len == GIT_OID_HEXSZ) {
1020                 *out = git_cache_get_raw(odb_cache(db), short_id);
1021                 if (*out != NULL)
1022                         return 0;
1023         }
1024
1025         git_oid__cpy_prefix(&key, short_id, len);
1026
1027         error = read_prefix_1(out, db, &key, len, false);
1028
1029         if (error == GIT_ENOTFOUND && !git_odb_refresh(db))
1030                 error = read_prefix_1(out, db, &key, len, true);
1031
1032         if (error == GIT_ENOTFOUND)
1033                 return git_odb__error_notfound("no match for prefix", &key, len);
1034
1035         return error;
1036 }
1037
1038 int git_odb_foreach(git_odb *db, git_odb_foreach_cb cb, void *payload)
1039 {
1040         unsigned int i;
1041         backend_internal *internal;
1042
1043         git_vector_foreach(&db->backends, i, internal) {
1044                 git_odb_backend *b = internal->backend;
1045                 int error = b->foreach(b, cb, payload);
1046                 if (error < 0)
1047                         return error;
1048         }
1049
1050         return 0;
1051 }
1052
1053 int git_odb_write(
1054         git_oid *oid, git_odb *db, const void *data, size_t len, git_otype type)
1055 {
1056         size_t i;
1057         int error = GIT_ERROR;
1058         git_odb_stream *stream;
1059
1060         assert(oid && db);
1061
1062         git_odb_hash(oid, data, len, type);
1063         if (git_odb_exists(db, oid))
1064                 return 0;
1065
1066         for (i = 0; i < db->backends.length && error < 0; ++i) {
1067                 backend_internal *internal = git_vector_get(&db->backends, i);
1068                 git_odb_backend *b = internal->backend;
1069
1070                 /* we don't write in alternates! */
1071                 if (internal->is_alternate)
1072                         continue;
1073
1074                 if (b->write != NULL)
1075                         error = b->write(b, oid, data, len, type);
1076         }
1077
1078         if (!error || error == GIT_PASSTHROUGH)
1079                 return 0;
1080
1081         /* if no backends were able to write the object directly, we try a
1082          * streaming write to the backends; just write the whole object into the
1083          * stream in one push
1084          */
1085         if ((error = git_odb_open_wstream(&stream, db, len, type)) != 0)
1086                 return error;
1087
1088         stream->write(stream, data, len);
1089         error = stream->finalize_write(stream, oid);
1090         git_odb_stream_free(stream);
1091
1092         return error;
1093 }
1094
1095 static void hash_header(git_hash_ctx *ctx, git_off_t size, git_otype type)
1096 {
1097         char header[64];
1098         int hdrlen;
1099
1100         hdrlen = git_odb__format_object_header(header, sizeof(header), size, type);
1101         git_hash_update(ctx, header, hdrlen);
1102 }
1103
1104 int git_odb_open_wstream(
1105         git_odb_stream **stream, git_odb *db, git_off_t size, git_otype type)
1106 {
1107         size_t i, writes = 0;
1108         int error = GIT_ERROR;
1109         git_hash_ctx *ctx = NULL;
1110
1111         assert(stream && db);
1112
1113         for (i = 0; i < db->backends.length && error < 0; ++i) {
1114                 backend_internal *internal = git_vector_get(&db->backends, i);
1115                 git_odb_backend *b = internal->backend;
1116
1117                 /* we don't write in alternates! */
1118                 if (internal->is_alternate)
1119                         continue;
1120
1121                 if (b->writestream != NULL) {
1122                         ++writes;
1123                         error = b->writestream(stream, b, size, type);
1124                 } else if (b->write != NULL) {
1125                         ++writes;
1126                         error = init_fake_wstream(stream, b, size, type);
1127                 }
1128         }
1129
1130         if (error < 0) {
1131                 if (error == GIT_PASSTHROUGH)
1132                         error = 0;
1133                 else if (!writes)
1134                         error = git_odb__error_unsupported_in_backend("write object");
1135
1136                 goto done;
1137         }
1138
1139         ctx = git__malloc(sizeof(git_hash_ctx));
1140         GITERR_CHECK_ALLOC(ctx);
1141
1142         if ((error = git_hash_ctx_init(ctx)) < 0)
1143                 goto done;
1144
1145         hash_header(ctx, size, type);
1146         (*stream)->hash_ctx = ctx;
1147
1148         (*stream)->declared_size = size;
1149         (*stream)->received_bytes = 0;
1150
1151 done:
1152         return error;
1153 }
1154
1155 static int git_odb_stream__invalid_length(
1156         const git_odb_stream *stream,
1157         const char *action)
1158 {
1159         giterr_set(GITERR_ODB,
1160                 "Cannot %s - "
1161                 "Invalid length. %"PRIuZ" was expected. The "
1162                 "total size of the received chunks amounts to %"PRIuZ".",
1163                 action, stream->declared_size, stream->received_bytes);
1164
1165         return -1;
1166 }
1167
1168 int git_odb_stream_write(git_odb_stream *stream, const char *buffer, size_t len)
1169 {
1170         git_hash_update(stream->hash_ctx, buffer, len);
1171
1172         stream->received_bytes += len;
1173
1174         if (stream->received_bytes > stream->declared_size)
1175                 return git_odb_stream__invalid_length(stream,
1176                         "stream_write()");
1177
1178         return stream->write(stream, buffer, len);
1179 }
1180
1181 int git_odb_stream_finalize_write(git_oid *out, git_odb_stream *stream)
1182 {
1183         if (stream->received_bytes != stream->declared_size)
1184                 return git_odb_stream__invalid_length(stream,
1185                         "stream_finalize_write()");
1186
1187         git_hash_final(out, stream->hash_ctx);
1188
1189         if (git_odb_exists(stream->backend->odb, out))
1190                 return 0;
1191
1192         return stream->finalize_write(stream, out);
1193 }
1194
1195 int git_odb_stream_read(git_odb_stream *stream, char *buffer, size_t len)
1196 {
1197         return stream->read(stream, buffer, len);
1198 }
1199
1200 void git_odb_stream_free(git_odb_stream *stream)
1201 {
1202         if (stream == NULL)
1203                 return;
1204
1205         git_hash_ctx_cleanup(stream->hash_ctx);
1206         git__free(stream->hash_ctx);
1207         stream->free(stream);
1208 }
1209
1210 int git_odb_open_rstream(git_odb_stream **stream, git_odb *db, const git_oid *oid)
1211 {
1212         size_t i, reads = 0;
1213         int error = GIT_ERROR;
1214
1215         assert(stream && db);
1216
1217         for (i = 0; i < db->backends.length && error < 0; ++i) {
1218                 backend_internal *internal = git_vector_get(&db->backends, i);
1219                 git_odb_backend *b = internal->backend;
1220
1221                 if (b->readstream != NULL) {
1222                         ++reads;
1223                         error = b->readstream(stream, b, oid);
1224                 }
1225         }
1226
1227         if (error == GIT_PASSTHROUGH)
1228                 error = 0;
1229         if (error < 0 && !reads)
1230                 error = git_odb__error_unsupported_in_backend("read object streamed");
1231
1232         return error;
1233 }
1234
1235 int git_odb_write_pack(struct git_odb_writepack **out, git_odb *db, git_transfer_progress_cb progress_cb, void *progress_payload)
1236 {
1237         size_t i, writes = 0;
1238         int error = GIT_ERROR;
1239
1240         assert(out && db);
1241
1242         for (i = 0; i < db->backends.length && error < 0; ++i) {
1243                 backend_internal *internal = git_vector_get(&db->backends, i);
1244                 git_odb_backend *b = internal->backend;
1245
1246                 /* we don't write in alternates! */
1247                 if (internal->is_alternate)
1248                         continue;
1249
1250                 if (b->writepack != NULL) {
1251                         ++writes;
1252                         error = b->writepack(out, b, db, progress_cb, progress_payload);
1253                 }
1254         }
1255
1256         if (error == GIT_PASSTHROUGH)
1257                 error = 0;
1258         if (error < 0 && !writes)
1259                 error = git_odb__error_unsupported_in_backend("write pack");
1260
1261         return error;
1262 }
1263
1264 void *git_odb_backend_malloc(git_odb_backend *backend, size_t len)
1265 {
1266         GIT_UNUSED(backend);
1267         return git__malloc(len);
1268 }
1269
1270 int git_odb_refresh(struct git_odb *db)
1271 {
1272         size_t i;
1273         assert(db);
1274
1275         for (i = 0; i < db->backends.length; ++i) {
1276                 backend_internal *internal = git_vector_get(&db->backends, i);
1277                 git_odb_backend *b = internal->backend;
1278
1279                 if (b->refresh != NULL) {
1280                         int error = b->refresh(b);
1281                         if (error < 0)
1282                                 return error;
1283                 }
1284         }
1285
1286         return 0;
1287 }
1288
1289 int git_odb__error_notfound(
1290         const char *message, const git_oid *oid, size_t oid_len)
1291 {
1292         if (oid != NULL) {
1293                 char oid_str[GIT_OID_HEXSZ + 1];
1294                 git_oid_tostr(oid_str, oid_len, oid);
1295                 giterr_set(GITERR_ODB, "Object not found - %s (%.*s)",
1296                         message, oid_len, oid_str);
1297         } else
1298                 giterr_set(GITERR_ODB, "Object not found - %s", message);
1299
1300         return GIT_ENOTFOUND;
1301 }
1302
1303 int git_odb__error_ambiguous(const char *message)
1304 {
1305         giterr_set(GITERR_ODB, "Ambiguous SHA1 prefix - %s", message);
1306         return GIT_EAMBIGUOUS;
1307 }
1308
1309 int git_odb_init_backend(git_odb_backend *backend, unsigned int version)
1310 {
1311         GIT_INIT_STRUCTURE_FROM_TEMPLATE(
1312                 backend, version, git_odb_backend, GIT_ODB_BACKEND_INIT);
1313         return 0;
1314 }