src/odb.c

   1 /*
   2  * This file is free software; you can redistribute it and/or modify
   3  * it under the terms of the GNU General Public License, version 2,
   4  * as published by the Free Software Foundation.
   5  *
   6  * In addition to the permissions in the GNU General Public License,
   7  * the authors give you unlimited permission to link the compiled
   8  * version of this file into combinations with other programs,
   9  * and to distribute those combinations without any restriction
  10  * coming from the use of this file.  (The General Public License
  11  * restrictions do apply in other respects; for example, they cover
  12  * modification of the file, and distribution when not linked into
  13  * a combined executable.)
  14  *
  15  * This file is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of
  17  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  18  * General Public License for more details.
  19  *
  20  * You should have received a copy of the GNU General Public License
  21  * along with this program; see the file COPYING.  If not, write to
  22  * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
  23  * Boston, MA 02110-1301, USA.
  24  */
  25
  26 #include "common.h"
  27 #include "git/odb.h"
  28 #include "git/zlib.h"
  29 #include "fileops.h"
  30 #include "hash.h"
  31 #include "odb.h"
  32
  33 #define GIT_PACK_NAME_MAX (5 + 40 + 1)
  34 struct git_pack {
  35         git_odb *db;
  36         git_lck lock;
  37
  38         /** Functions to access idx_map. */
  39         int (*idx_search)(
  40                 off_t *,
  41                 struct git_pack *,
  42                 const git_oid *);
  43
  44         /** The .idx file, mapped into memory. */
  45         git_file idx_fd;
  46         git_map idx_map;
  47         uint32_t *im_fanout;
  48         unsigned char *im_oid;
  49         uint32_t *im_crc;
  50         uint32_t *im_offset32;
  51         uint32_t *im_offset64;
  52
  53         /** Number of objects in this pack. */
  54         uint32_t obj_cnt;
  55
  56         /** Number of git_packlist we appear in. */
  57         unsigned int refcnt;
  58
  59         /** Number of active users of the idx_map data. */
  60         unsigned int idxcnt;
  61         unsigned
  62                 invalid:1 /* the pack is unable to be read by libgit2 */
  63                 ;
  64
  65         /** Name of the pack file(s), without extension ("pack-abc"). */
  66         char pack_name[GIT_PACK_NAME_MAX];
  67 };
  68 typedef struct git_pack git_pack;
  69
  70 typedef struct {
  71         size_t n_packs;
  72         unsigned int refcnt;
  73         git_pack *packs[GIT_FLEX_ARRAY];
  74 } git_packlist;
  75
  76 struct git_odb {
  77         git_lck lock;
  78
  79         /** Path to the "objects" directory. */
  80         char *objects_dir;
  81
  82         /** Known pack files from ${objects_dir}/packs. */
  83         git_packlist *packlist;
  84
  85         /** Alternate databases to search. */
  86         git_odb **alternates;
  87         size_t n_alternates;
  88
  89         /** loose object zlib compression level. */
  90         int object_zlib_level;
  91         /** loose object file fsync flag. */
  92         int fsync_object_files;
  93 };
  94
  95 typedef struct {  /* object header data */
  96         git_otype type;  /* object type */
  97         size_t    size;  /* object size */
  98 } obj_hdr;
  99
 100 static struct {
 101         const char *str;   /* type name string */
 102         int        loose;  /* valid loose object type flag */
 103 } obj_type_table [] = {
 104         { "",          0 },  /* 0 = GIT_OBJ__EXT1     */
 105         { "commit",    1 },  /* 1 = GIT_OBJ_COMMIT    */
 106         { "tree",      1 },  /* 2 = GIT_OBJ_TREE      */
 107         { "blob",      1 },  /* 3 = GIT_OBJ_BLOB      */
 108         { "tag",       1 },  /* 4 = GIT_OBJ_TAG       */
 109         { "",          0 },  /* 5 = GIT_OBJ__EXT2     */
 110         { "OFS_DELTA", 0 },  /* 6 = GIT_OBJ_OFS_DELTA */
 111         { "REF_DELTA", 0 }   /* 7 = GIT_OBJ_REF_DELTA */
 112 };
 113
 114 GIT_INLINE(uint32_t) decode32(void *b)
 115 {
 116         return ntohl(*((uint32_t*)b));
 117 }
 118
 119 GIT_INLINE(uint64_t) decode64(void *b)
 120 {
 121         uint32_t *p = b;
 122         return (((uint64_t)ntohl(p[0])) << 32) | ntohl(p[1]);
 123 }
 124
 125 const char *git_obj_type_to_string(git_otype type)
 126 {
 127         if (type < 0 || type >= ARRAY_SIZE(obj_type_table))
 128                 return "";
 129         return obj_type_table[type].str;
 130 }
 131
 132 git_otype git_obj_string_to_type(const char *str)
 133 {
 134         int i;
 135
 136         if (!str || !*str)
 137                 return GIT_OBJ_BAD;
 138
 139         for (i = 0; i < ARRAY_SIZE(obj_type_table); i++)
 140                 if (!strcmp(str, obj_type_table[i].str))
 141                         return (git_otype) i;
 142
 143         return GIT_OBJ_BAD;
 144 }
 145
 146 int git_obj__loose_object_type(git_otype type)
 147 {
 148         if (type < 0 || type >= ARRAY_SIZE(obj_type_table))
 149                 return 0;
 150         return obj_type_table[type].loose;
 151 }
 152
 153 static int format_object_header(char *hdr, size_t n, git_obj *obj)
 154 {
 155         const char *type_str = git_obj_type_to_string(obj->type);
 156         int len = snprintf(hdr, n, "%s %"PRIuZ, type_str, obj->len);
 157
 158         assert(len > 0);  /* otherwise snprintf() is broken */
 159         assert(len < n);  /* otherwise the caller is broken! */
 160
 161         if (len < 0 || len >= n)
 162                 return GIT_ERROR;
 163         return len+1;
 164 }
 165
 166 static int hash_obj(git_oid *id, char *hdr, size_t n, int *len, git_obj *obj)
 167 {
 168         git_buf_vec vec[2];
 169         int  hdrlen;
 170
 171         assert(id && hdr && len && obj);
 172
 173         if (!git_obj__loose_object_type(obj->type))
 174                 return GIT_ERROR;
 175
 176         if (!obj->data && obj->len != 0)
 177                 return GIT_ERROR;
 178
 179         if ((hdrlen = format_object_header(hdr, n, obj)) < 0)
 180                 return GIT_ERROR;
 181
 182         *len = hdrlen;
 183
 184         vec[0].data = hdr;
 185         vec[0].len  = hdrlen;
 186         vec[1].data = obj->data;
 187         vec[1].len  = obj->len;
 188
 189         git_hash_vec(id, vec, 2);
 190
 191         return GIT_SUCCESS;
 192 }
 193
 194 int git_obj_hash(git_oid *id, git_obj *obj)
 195 {
 196         char hdr[64];
 197         int  hdrlen;
 198
 199         assert(id && obj);
 200
 201         return hash_obj(id, hdr, sizeof(hdr), &hdrlen, obj);
 202 }
 203
 204 static size_t object_file_name(char *name, size_t n, char *dir, const git_oid *id)
 205 {
 206         size_t len = strlen(dir);
 207
 208         /* check length: 43 = 40 hex sha1 chars + 2 * '/' + '\0' */
 209         if (len+43 > n)
 210                 return len+43;
 211
 212         /* the object dir: eg $GIT_DIR/objects */
 213         strcpy(name, dir);
 214         if (name[len-1] != '/')
 215                 name[len++] = '/';
 216
 217         /* loose object filename: aa/aaa... (41 bytes) */
 218         git_oid_pathfmt(&name[len], id);
 219         name[len+41] = '\0';
 220
 221         return 0;
 222 }
 223
 224 static int is_zlib_compressed_data(unsigned char *data)
 225 {
 226         unsigned int w;
 227
 228         w = ((unsigned int)(data[0]) << 8) + data[1];
 229         return data[0] == 0x78 && !(w %31);
 230 }
 231
 232 static size_t get_binary_object_header(obj_hdr *hdr, gitfo_buf *obj)
 233 {
 234         unsigned char c;
 235         unsigned char *data = obj->data;
 236         size_t shift, size, used = 0;
 237
 238         if (obj->len == 0)
 239                 return 0;
 240
 241         c = data[used++];
 242         hdr->type = (c >> 4) & 7;
 243
 244         size = c & 15;
 245         shift = 4;
 246         while (c & 0x80) {
 247                 if (obj->len <= used)
 248                         return 0;
 249                 if (sizeof(size_t) * 8 <= shift)
 250                         return 0;
 251                 c = data[used++];
 252                 size += (c & 0x7f) << shift;
 253                 shift += 7;
 254         }
 255         hdr->size = size;
 256
 257         return used;
 258 }
 259
 260 static size_t get_object_header(obj_hdr *hdr, unsigned char *data)
 261 {
 262         char c, typename[10];
 263         size_t size, used = 0;
 264
 265         /*
 266          * type name string followed by space.
 267          */
 268         while ((c = data[used]) != ' ') {
 269                 typename[used++] = c;
 270                 if (used >= sizeof(typename))
 271                         return 0;
 272         }
 273         typename[used] = 0;
 274         if (used == 0)
 275                 return 0;
 276         hdr->type = git_obj_string_to_type(typename);
 277         used++;  /* consume the space */
 278
 279         /*
 280          * length follows immediately in decimal (without
 281          * leading zeros).
 282          */
 283         size = data[used++] - '0';
 284         if (size > 9)
 285                 return 0;
 286         if (size) {
 287                 while ((c = data[used]) != '\0') {
 288                         size_t d = c - '0';
 289                         if (d > 9)
 290                                 break;
 291                         used++;
 292                         size = size * 10 + d;
 293                 }
 294         }
 295         hdr->size = size;
 296
 297         /*
 298          * the length must be followed by a zero byte
 299          */
 300         if (data[used++] != '\0')
 301                 return 0;
 302
 303         return used;
 304 }
 305
 306 static void init_stream(z_stream *s, void *out, size_t len)
 307 {
 308         memset(s, 0, sizeof(*s));
 309         s->next_out  = out;
 310         s->avail_out = len;
 311 }
 312
 313 static void set_stream_input(z_stream *s, void *in, size_t len)
 314 {
 315         s->next_in  = in;
 316         s->avail_in = len;
 317 }
 318
 319 static void set_stream_output(z_stream *s, void *out, size_t len)
 320 {
 321         s->next_out  = out;
 322         s->avail_out = len;
 323 }
 324
 325 static int start_inflate(z_stream *s, gitfo_buf *obj, void *out, size_t len)
 326 {
 327         int status;
 328
 329         init_stream(s, out, len);
 330         set_stream_input(s, obj->data, obj->len);
 331
 332         if ((status = inflateInit(s)) < Z_OK)
 333                 return status;
 334
 335         return inflate(s, 0);
 336 }
 337
 338 static int finish_inflate(z_stream *s)
 339 {
 340         int status = Z_OK;
 341
 342         while (status == Z_OK)
 343                 status = inflate(s, Z_FINISH);
 344
 345         inflateEnd(s);
 346
 347         if ((status != Z_STREAM_END) || (s->avail_in != 0))
 348                 return GIT_ERROR;
 349
 350         return GIT_SUCCESS;
 351 }
 352
 353 static void *inflate_tail(z_stream *s, void *hb, size_t used, obj_hdr *hdr)
 354 {
 355         unsigned char *buf, *head = hb;
 356         size_t tail;
 357
 358         /*
 359          * allocate a buffer to hold the inflated data and copy the
 360          * initial sequence of inflated data from the tail of the
 361          * head buffer, if any.
 362          */
 363         if ((buf = git__malloc(hdr->size + 1)) == NULL) {
 364                 inflateEnd(s);
 365                 return NULL;
 366         }
 367         tail = s->total_out - used;
 368         if (used > 0 && tail > 0) {
 369                 if (tail > hdr->size)
 370                         tail = hdr->size;
 371                 memcpy(buf, head + used, tail);
 372         }
 373         used = tail;
 374
 375         /*
 376          * inflate the remainder of the object data, if any
 377          */
 378         if (hdr->size < used)
 379                 inflateEnd(s);
 380         else {
 381                 set_stream_output(s, buf + used, hdr->size - used);
 382                 if (finish_inflate(s)) {
 383                         free(buf);
 384                         return NULL;
 385                 }
 386         }
 387
 388         return buf;
 389 }
 390
 391 static int inflate_buffer(void *in, size_t inlen, void *out, size_t outlen)
 392 {
 393         z_stream zs;
 394         int status = Z_OK;
 395
 396         init_stream(&zs, out, outlen);
 397         set_stream_input(&zs, in, inlen);
 398
 399         if (inflateInit(&zs) < Z_OK)
 400                 return GIT_ERROR;
 401
 402         while (status == Z_OK)
 403                 status = inflate(&zs, Z_FINISH);
 404
 405         inflateEnd(&zs);
 406
 407         if ((status != Z_STREAM_END) || (zs.avail_in != 0))
 408                 return GIT_ERROR;
 409
 410         if (zs.total_out != outlen)
 411                 return GIT_ERROR;
 412
 413         return GIT_SUCCESS;
 414 }
 415
 416 /*
 417  * At one point, there was a loose object format that was intended to
 418  * mimic the format used in pack-files. This was to allow easy copying
 419  * of loose object data into packs. This format is no longer used, but
 420  * we must still read it.
 421  */
 422 static int inflate_packlike_loose_disk_obj(git_obj *out, gitfo_buf *obj)
 423 {
 424         unsigned char *in, *buf;
 425         obj_hdr hdr;
 426         size_t len, used;
 427
 428         /*
 429          * read the object header, which is an (uncompressed)
 430          * binary encoding of the object type and size.
 431          */
 432         if ((used = get_binary_object_header(&hdr, obj)) == 0)
 433                 return GIT_ERROR;
 434
 435         if (!git_obj__loose_object_type(hdr.type))
 436                 return GIT_ERROR;
 437
 438         /*
 439          * allocate a buffer and inflate the data into it
 440          */
 441         buf = git__malloc(hdr.size + 1);
 442         if (!buf)
 443                 return GIT_ERROR;
 444
 445         in  = ((unsigned char *)obj->data) + used;
 446         len = obj->len - used;
 447         if (inflate_buffer(in, len, buf, hdr.size)) {
 448                 free(buf);
 449                 return GIT_ERROR;
 450         }
 451         buf[hdr.size] = '\0';
 452
 453         out->data = buf;
 454         out->len  = hdr.size;
 455         out->type = hdr.type;
 456
 457         return GIT_SUCCESS;
 458 }
 459
 460 static int inflate_disk_obj(git_obj *out, gitfo_buf *obj)
 461 {
 462         unsigned char head[64], *buf;
 463         z_stream zs;
 464         int z_status;
 465         obj_hdr hdr;
 466         size_t used;
 467
 468         /*
 469          * check for a pack-like loose object
 470          */
 471         if (!is_zlib_compressed_data(obj->data))
 472                 return inflate_packlike_loose_disk_obj(out, obj);
 473
 474         /*
 475          * inflate the initial part of the io buffer in order
 476          * to parse the object header (type and size).
 477          */
 478         if ((z_status = start_inflate(&zs, obj, head, sizeof(head))) < Z_OK)
 479                 return GIT_ERROR;
 480
 481         if ((used = get_object_header(&hdr, head)) == 0)
 482                 return GIT_ERROR;
 483
 484         if (!git_obj__loose_object_type(hdr.type))
 485                 return GIT_ERROR;
 486
 487         /*
 488          * allocate a buffer and inflate the object data into it
 489          * (including the initial sequence in the head buffer).
 490          */
 491         if ((buf = inflate_tail(&zs, head, used, &hdr)) == NULL)
 492                 return GIT_ERROR;
 493         buf[hdr.size] = '\0';
 494
 495         out->data = buf;
 496         out->len  = hdr.size;
 497         out->type = hdr.type;
 498
 499         return GIT_SUCCESS;
 500 }
 501
 502 static int make_temp_file(git_file *fd, char *tmp, size_t n, char *file)
 503 {
 504         char *template = "/tmp_obj_XXXXXX";
 505         size_t tmplen = strlen(template);
 506         size_t dirlen;
 507
 508         if ((dirlen = git__dirname(tmp, n, file)) < 0)
 509                 return GIT_ERROR;
 510
 511         if ((dirlen + tmplen) >= n)
 512                 return GIT_ERROR;
 513
 514         strcpy(tmp + dirlen, (dirlen) ? template : template + 1);
 515
 516         *fd = gitfo_mkstemp(tmp);
 517         if (*fd < 0 && dirlen) {
 518                 /* create directory if it doesn't exist */
 519                 tmp[dirlen] = '\0';
 520                 if ((gitfo_exists(tmp) < 0) && gitfo_mkdir(tmp, 0755))
 521                         return GIT_ERROR;
 522                 /* try again */
 523                 strcpy(tmp + dirlen, template);
 524                 *fd = gitfo_mkstemp(tmp);
 525         }
 526         if (*fd < 0)
 527                 return GIT_ERROR;
 528
 529         return GIT_SUCCESS;
 530 }
 531
 532 static int deflate_buf(z_stream *s, void *in, size_t len, int flush)
 533 {
 534         int status = Z_OK;
 535
 536         set_stream_input(s, in, len);
 537         while (status == Z_OK) {
 538                 status = deflate(s, flush);
 539                 if (s->avail_in == 0)
 540                         break;
 541         }
 542         return status;
 543 }
 544
 545 static int deflate_obj(gitfo_buf *buf, char *hdr, int hdrlen, git_obj *obj, int level)
 546 {
 547         z_stream zs;
 548         int status;
 549         size_t size;
 550
 551         assert(buf && !buf->data && hdr && obj);
 552         assert(level == Z_DEFAULT_COMPRESSION || (level >= 0 && level <= 9));
 553
 554         buf->data = NULL;
 555         buf->len  = 0;
 556         init_stream(&zs, NULL, 0);
 557
 558         if (deflateInit(&zs, level) < Z_OK)
 559                 return GIT_ERROR;
 560
 561         size = deflateBound(&zs, hdrlen + obj->len);
 562
 563         if ((buf->data = git__malloc(size)) == NULL) {
 564                 deflateEnd(&zs);
 565                 return GIT_ERROR;
 566         }
 567
 568         set_stream_output(&zs, buf->data, size);
 569
 570         /* compress the header */
 571         status = deflate_buf(&zs, hdr, hdrlen, Z_NO_FLUSH);
 572
 573         /* if header compressed OK, compress the object */
 574         if (status == Z_OK)
 575                 status = deflate_buf(&zs, obj->data, obj->len, Z_FINISH);
 576
 577         if (status != Z_STREAM_END) {
 578                 deflateEnd(&zs);
 579                 free(buf->data);
 580                 buf->data = NULL;
 581                 return GIT_ERROR;
 582         }
 583
 584         buf->len = zs.total_out;
 585         deflateEnd(&zs);
 586
 587         return GIT_SUCCESS;
 588 }
 589
 590 static int write_obj(gitfo_buf *buf, git_oid *id, git_odb *db)
 591 {
 592         char file[GIT_PATH_MAX];
 593         char temp[GIT_PATH_MAX];
 594         git_file fd;
 595
 596         if (object_file_name(file, sizeof(file), db->objects_dir, id))
 597                 return GIT_ERROR;
 598
 599         if (make_temp_file(&fd, temp, sizeof(temp), file) < 0)
 600                 return GIT_ERROR;
 601
 602         if (gitfo_write(fd, buf->data, buf->len) < 0) {
 603                 gitfo_close(fd);
 604                 gitfo_unlink(temp);
 605                 return GIT_ERROR;
 606         }
 607
 608         if (db->fsync_object_files)
 609                 gitfo_fsync(fd);
 610         gitfo_close(fd);
 611         gitfo_chmod(temp, 0444);
 612
 613         if (gitfo_move_file(temp, file) < 0) {
 614                 gitfo_unlink(temp);
 615                 return GIT_ERROR;
 616         }
 617
 618         return GIT_SUCCESS;
 619 }
 620
 621 static int open_alternates(git_odb *db)
 622 {
 623         unsigned n = 0;
 624
 625         gitlck_lock(&db->lock);
 626         if (db->alternates) {
 627                 gitlck_unlock(&db->lock);
 628                 return 1;
 629         }
 630
 631         db->alternates = git__malloc(sizeof(*db->alternates) * (n + 1));
 632         if (!db->alternates) {
 633                 gitlck_unlock(&db->lock);
 634                 return -1;
 635         }
 636
 637         db->alternates[n] = NULL;
 638         db->n_alternates = n;
 639         gitlck_unlock(&db->lock);
 640         return 0;
 641 }
 642
 643 static int pack_openidx_map(git_pack *p)
 644 {
 645         char pb[GIT_PATH_MAX];
 646         off_t len;
 647
 648         if (git__fmt(pb, sizeof(pb), "%s/pack/%s.idx",
 649                         p->db->objects_dir,
 650                         p->pack_name) < 0)
 651                 return GIT_ERROR;
 652
 653         if ((p->idx_fd = gitfo_open(pb, O_RDONLY)) < 0)
 654                 return GIT_ERROR;
 655
 656         if ((len = gitfo_size(p->idx_fd)) < 0
 657                 || !git__is_sizet(len)
 658                 || gitfo_map_ro(&p->idx_map, p->idx_fd, 0, (size_t)len)) {
 659                 gitfo_close(p->idx_fd);
 660                 return GIT_ERROR;
 661         }
 662
 663         return GIT_SUCCESS;
 664 }
 665
 666 static int idxv1_search(off_t *out, git_pack *p, const git_oid *id)
 667 {
 668         unsigned char *data = p->im_oid;
 669         size_t lo = id->id[0] ? p->im_fanout[id->id[0] - 1] : 0;
 670         size_t hi = p->im_fanout[id->id[0]];
 671
 672         do {
 673                 size_t mid = (lo + hi) >> 1;
 674                 size_t pos = 24 * mid;
 675                 int cmp = memcmp(id->id, data + pos + 4, 20);
 676                 if (cmp < 0)
 677                         hi = mid;
 678                 else if (!cmp) {
 679                         *out = decode32(data + pos);
 680                         return GIT_SUCCESS;
 681                 } else
 682                         lo = mid + 1;
 683         } while (lo < hi);
 684         return GIT_ENOTFOUND;
 685 }
 686
 687 static int pack_openidx_v1(git_pack *p)
 688 {
 689         uint32_t *src_fanout = p->idx_map.data;
 690         uint32_t *im_fanout;
 691         size_t expsz;
 692         int j;
 693
 694         if ((im_fanout = git__malloc(sizeof(*im_fanout) * 256)) == NULL)
 695                 return GIT_ERROR;
 696
 697         im_fanout[0] = decode32(&src_fanout[0]);
 698         for (j = 1; j < 256; j++) {
 699                 im_fanout[j] = decode32(&src_fanout[j]);
 700                 if (im_fanout[j] < im_fanout[j - 1]) {
 701                         free(im_fanout);
 702                         return GIT_ERROR;
 703                 }
 704         }
 705         p->obj_cnt = im_fanout[255];
 706
 707         expsz = 4 * 256 + 24 * p->obj_cnt + 2 * 20;
 708         if (expsz != p->idx_map.len) {
 709                 free(im_fanout);
 710                 return GIT_ERROR;
 711         }
 712
 713         p->idx_search = idxv1_search;
 714         p->im_fanout = im_fanout;
 715         p->im_oid = (unsigned char*)(src_fanout + 256);
 716         return GIT_SUCCESS;
 717 }
 718
 719 static int idxv2_search(off_t *out, git_pack *p, const git_oid *id)
 720 {
 721         unsigned char *data = p->im_oid;
 722         size_t lo = id->id[0] ? p->im_fanout[id->id[0] - 1] : 0;
 723         size_t hi = p->im_fanout[id->id[0]];
 724
 725         do {
 726                 size_t mid = (lo + hi) >> 1;
 727                 size_t pos = 20 * mid;
 728                 int cmp = memcmp(id->id, data + pos, 20);
 729                 if (cmp < 0)
 730                         hi = mid;
 731                 else if (!cmp) {
 732                         uint32_t o32 = decode32(p->im_offset32 + mid);
 733                         if (o32 & 0x80000000)
 734                                 *out = decode64(p->im_offset64 + 2*(o32 & ~0x80000000));
 735                         else
 736                                 *out = o32;
 737                         return GIT_SUCCESS;
 738                 } else
 739                         lo = mid + 1;
 740         } while (lo < hi);
 741         return GIT_ENOTFOUND;
 742 }
 743
 744 static int pack_openidx_v2(git_pack *p)
 745 {
 746         unsigned char *data = p->idx_map.data;
 747         uint32_t *src_fanout = (uint32_t*)(data + 8);
 748         uint32_t *im_fanout;
 749         int j;
 750
 751         if ((im_fanout = git__malloc(sizeof(*im_fanout) * 256)) == NULL)
 752                 return GIT_ERROR;
 753
 754         im_fanout[0] = decode32(&src_fanout[0]);
 755         for (j = 1; j < 256; j++) {
 756                 im_fanout[j] = decode32(&src_fanout[j]);
 757                 if (im_fanout[j] < im_fanout[j - 1]) {
 758                         free(im_fanout);
 759                         return GIT_ERROR;
 760                 }
 761         }
 762         p->obj_cnt = im_fanout[255];
 763
 764         p->idx_search = idxv2_search;
 765         p->im_fanout = im_fanout;
 766         p->im_oid = (unsigned char*)(src_fanout + 256);
 767         p->im_crc = (uint32_t*)(p->im_oid + 20 * p->obj_cnt);
 768         p->im_offset32 = p->im_crc + p->obj_cnt;
 769         p->im_offset64 = p->im_offset32 + p->obj_cnt;
 770         return GIT_SUCCESS;
 771 }
 772
 773 static int pack_openidx(git_pack *p)
 774 {
 775         gitlck_lock(&p->lock);
 776         if (p->invalid)
 777                 goto unlock_fail;
 778         if (++p->idxcnt == 1 && !p->idx_search) {
 779                 uint32_t *data;
 780
 781                 if (pack_openidx_map(p))
 782                         goto invalid_fail;
 783                 data = p->idx_map.data;
 784
 785                 if (decode32(&data[0]) == PACK_TOC) {
 786                         switch (decode32(&data[1])) {
 787                         case 2:
 788                                 if (pack_openidx_v2(p))
 789                                         goto unmap_fail;
 790                                 break;
 791                         default:
 792                                 goto unmap_fail;
 793                         }
 794                 } else if (pack_openidx_v1(p))
 795                         goto unmap_fail;
 796         }
 797         gitlck_unlock(&p->lock);
 798         return GIT_SUCCESS;
 799
 800 unmap_fail:
 801         gitfo_free_map(&p->idx_map);
 802
 803 invalid_fail:
 804         p->invalid = 1;
 805         p->idxcnt--;
 806
 807 unlock_fail:
 808         gitlck_unlock(&p->lock);
 809         return GIT_ERROR;
 810 }
 811
 812 static void pack_decidx(git_pack *p)
 813 {
 814         gitlck_lock(&p->lock);
 815         p->idxcnt--;
 816         gitlck_unlock(&p->lock);
 817 }
 818
 819 static void pack_dec(git_pack *p)
 820 {
 821         int need_free;
 822
 823         gitlck_lock(&p->lock);
 824         need_free = !--p->refcnt;
 825         gitlck_unlock(&p->lock);
 826
 827         if (need_free) {
 828                 if (p->idx_search) {
 829                         gitfo_free_map(&p->idx_map);
 830                         gitfo_close(p->idx_fd);
 831                         free(p->im_fanout);
 832                 }
 833
 834                 gitlck_free(&p->lock);
 835                 free(p);
 836         }
 837 }
 838
 839 static void packlist_dec(git_odb *db, git_packlist *pl)
 840 {
 841         int need_free;
 842
 843         gitlck_lock(&db->lock);
 844         need_free = !--pl->refcnt;
 845         gitlck_unlock(&db->lock);
 846
 847         if (need_free) {
 848                 size_t j;
 849                 for (j = 0; j < pl->n_packs; j++)
 850                         pack_dec(pl->packs[j]);
 851                 free(pl);
 852         }
 853 }
 854
 855 static git_pack *alloc_pack(const char *pack_name)
 856 {
 857         git_pack *p = git__calloc(1, sizeof(*p));
 858         if (!p)
 859                 return NULL;
 860
 861         gitlck_init(&p->lock);
 862         strcpy(p->pack_name, pack_name);
 863         p->refcnt = 1;
 864         return p;
 865 }
 866
 867 struct scanned_pack {
 868         struct scanned_pack *next;
 869         git_pack *pack;
 870 };
 871
 872 static int scan_one_pack(void *state, char *name)
 873 {
 874         struct scanned_pack **ret = state, *r;
 875         char *s = strrchr(name, '/'), *d;
 876
 877         if (git__prefixcmp(s + 1, "pack-")
 878          || git__suffixcmp(s, ".pack")
 879          || strlen(s + 1) != GIT_PACK_NAME_MAX + 4)
 880                 return 0;
 881
 882         d = strrchr(s + 1, '.');
 883         strcpy(d + 1, "idx");    /* "pack-abc.pack" -> "pack-abc.idx" */
 884         if (gitfo_exists(name))
 885                 return 0;
 886
 887         if ((r = git__malloc(sizeof(*r))) == NULL)
 888                 return GIT_ERROR;
 889
 890         *d = '\0';               /* "pack-abc.pack" -_> "pack-abc" */
 891         if ((r->pack = alloc_pack(s + 1)) == NULL) {
 892                 free(r);
 893                 return GIT_ERROR;
 894         }
 895
 896         r->next = *ret;
 897         *ret = r;
 898         return 0;
 899 }
 900
 901 static git_packlist* scan_packs(git_odb *db)
 902 {
 903         char pb[GIT_PATH_MAX];
 904         struct scanned_pack *state = NULL, *c;
 905         size_t cnt;
 906         git_packlist *new_list;
 907
 908         if (git__fmt(pb, sizeof(pb), "%s/pack", db->objects_dir) < 0)
 909                 return NULL;
 910         gitfo_dirent(pb, sizeof(pb), scan_one_pack, &state);
 911
 912         /* TODO - merge old entries into the new array */
 913         for (cnt = 0, c = state; c; c = c->next)
 914                 cnt++;
 915         new_list = git__malloc(sizeof(*new_list)
 916                 + (sizeof(new_list->packs[0]) * cnt));
 917         if (!new_list)
 918                 goto fail;
 919
 920         for (cnt = 0, c = state; c; ) {
 921                 struct scanned_pack *n = c->next;
 922                 c->pack->db = db;
 923                 new_list->packs[cnt++] = c->pack;
 924                 free(c);
 925                 c = n;
 926         }
 927         new_list->n_packs = cnt;
 928         new_list->refcnt = 2;
 929         db->packlist = new_list;
 930         return new_list;
 931
 932 fail:
 933         while (state) {
 934                 struct scanned_pack *n = state->next;
 935                 pack_dec(state->pack);
 936                 free(state);
 937                 state = n;
 938         }
 939         return NULL;
 940 }
 941
 942 static git_packlist *packlist_get(git_odb *db)
 943 {
 944         git_packlist *pl;
 945
 946         gitlck_lock(&db->lock);
 947         if ((pl = db->packlist) != NULL)
 948                 pl->refcnt++;
 949         else
 950                 pl = scan_packs(db);
 951         gitlck_unlock(&db->lock);
 952         return pl;
 953 }
 954
 955 static int search_packs(git_pack **p, off_t *offset, git_odb *db, const git_oid *id)
 956 {
 957         git_packlist *pl = packlist_get(db);
 958         size_t j;
 959
 960         if (!pl)
 961                 return GIT_ENOTFOUND;
 962
 963         for (j = 0; j < pl->n_packs; j++) {
 964
 965                 git_pack *pack = pl->packs[j];
 966                 off_t pos;
 967                 int res;
 968
 969                 if (pack_openidx(pack))
 970                         continue;
 971                 res = pack->idx_search(&pos, pack, id);
 972                 pack_decidx(pack);
 973
 974                 if (!res) {
 975                         packlist_dec(db,pl);
 976                         if (p)
 977                                 *p = pack;
 978                         if (offset)
 979                                 *offset = pos;
 980                         return GIT_SUCCESS;
 981                 }
 982
 983         }
 984
 985         packlist_dec(db,pl);
 986         return GIT_ENOTFOUND;
 987 }
 988
 989 static int exists_packed(git_odb *db, const git_oid *id)
 990 {
 991         return !search_packs(NULL, NULL, db, id);
 992 }
 993
 994 static int exists_loose(git_odb *db, const git_oid *id)
 995 {
 996         char file[GIT_PATH_MAX];
 997
 998         if (object_file_name(file, sizeof(file), db->objects_dir, id))
 999                 return 0;
1000
1001         if (gitfo_exists(file) < 0)
1002                 return 0;
1003
1004         return 1;
1005 }
1006
1007 int git_odb_exists(git_odb *db, const git_oid *id)
1008 {
1009         /* TODO: extend to search alternate db's */
1010         if (exists_packed(db, id))
1011                 return 1;
1012         return exists_loose(db, id);
1013 }
1014
1015 int git_odb_open(git_odb **out, const char *objects_dir)
1016 {
1017         git_odb *db = git__calloc(1, sizeof(*db));
1018         if (!db)
1019                 return GIT_ERROR;
1020
1021         db->objects_dir = git__strdup(objects_dir);
1022         if (!db->objects_dir) {
1023                 free(db);
1024                 return GIT_ERROR;
1025         }
1026
1027         gitlck_init(&db->lock);
1028
1029         db->object_zlib_level = Z_BEST_SPEED;
1030         db->fsync_object_files = 0;
1031
1032         *out = db;
1033         return GIT_SUCCESS;
1034 }
1035
1036 void git_odb_close(git_odb *db)
1037 {
1038         git_packlist *pl;
1039
1040         if (!db)
1041                 return;
1042
1043         gitlck_lock(&db->lock);
1044
1045         pl = db->packlist;
1046         db->packlist = NULL;
1047
1048         if (db->alternates) {
1049                 git_odb **alt;
1050                 for (alt = db->alternates; *alt; alt++)
1051                         git_odb_close(*alt);
1052                 free(db->alternates);
1053         }
1054
1055         free(db->objects_dir);
1056
1057         gitlck_unlock(&db->lock);
1058         if (pl)
1059                 packlist_dec(db, pl);
1060         gitlck_free(&db->lock);
1061         free(db);
1062 }
1063
1064 int git_odb_read(
1065         git_obj *out,
1066         git_odb *db,
1067         const git_oid *id)
1068 {
1069 attempt:
1070         if (!git_odb__read_packed(out, db, id))
1071                 return GIT_SUCCESS;
1072         if (!git_odb__read_loose(out, db, id))
1073                 return GIT_SUCCESS;
1074         if (!open_alternates(db))
1075                 goto attempt;
1076
1077         out->data = NULL;
1078         return GIT_ENOTFOUND;
1079 }
1080
1081 int git_odb__read_loose(git_obj *out, git_odb *db, const git_oid *id)
1082 {
1083         char file[GIT_PATH_MAX];
1084         gitfo_buf obj = GITFO_BUF_INIT;
1085
1086         assert(out && db && id);
1087
1088         out->data = NULL;
1089         out->len  = 0;
1090         out->type = GIT_OBJ_BAD;
1091
1092         if (object_file_name(file, sizeof(file), db->objects_dir, id))
1093                 return GIT_ENOTFOUND;  /* TODO: error handling */
1094
1095         if (gitfo_read_file(&obj, file))
1096                 return GIT_ENOTFOUND;  /* TODO: error handling */
1097
1098         if (inflate_disk_obj(out, &obj)) {
1099                 gitfo_free_buf(&obj);
1100                 return GIT_ENOTFOUND;  /* TODO: error handling */
1101         }
1102
1103         gitfo_free_buf(&obj);
1104
1105         return GIT_SUCCESS;
1106 }
1107
1108 static int read_packed(git_obj *out, git_pack *p, const git_oid *id)
1109 {
1110         off_t pos;
1111         int res;
1112
1113         if (pack_openidx(p))
1114                 return GIT_ERROR;
1115         res = p->idx_search(&pos, p, id);
1116         pack_decidx(p);
1117
1118         if (!res) {
1119                 /* TODO unpack object at pos */
1120                 res = GIT_ERROR;
1121         }
1122
1123         return res;
1124 }
1125
1126 int git_odb__read_packed(git_obj *out, git_odb *db, const git_oid *id)
1127 {
1128         git_packlist *pl = packlist_get(db);
1129         size_t j;
1130
1131         if (!pl)
1132                 return GIT_ENOTFOUND;
1133
1134         for (j = 0; j < pl->n_packs; j++) {
1135                 if (!read_packed(out, pl->packs[j], id)) {
1136                         packlist_dec(db, pl);
1137                         return GIT_SUCCESS;
1138                 }
1139         }
1140
1141         packlist_dec(db, pl);
1142         return GIT_ENOTFOUND;
1143 }
1144
1145 int git_odb_write(git_oid *id, git_odb *db, git_obj *obj)
1146 {
1147         char hdr[64];
1148         int  hdrlen;
1149         gitfo_buf buf = GITFO_BUF_INIT;
1150
1151         assert(id && db && obj);
1152
1153         if (hash_obj(id, hdr, sizeof(hdr), &hdrlen, obj) < 0)
1154                 return GIT_ERROR;
1155
1156         if (git_odb_exists(db, id))
1157                 return GIT_SUCCESS;
1158
1159         if (deflate_obj(&buf, hdr, hdrlen, obj, db->object_zlib_level) < 0)
1160                 return GIT_ERROR;
1161
1162         if (write_obj(&buf, id, db) < 0) {
1163                 gitfo_free_buf(&buf);
1164                 return GIT_ERROR;
1165         }
1166
1167         gitfo_free_buf(&buf);
1168
1169         return GIT_SUCCESS;
1170 }
1171