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 "git/odb.h"
  27 #include "git/zlib.h"
  28 #include "common.h"
  29 #include "fileops.h"
  30 #include "hash.h"
  31 #include <stdio.h>
  32
  33 struct git_odb {
  34         /** Path to the "objects" directory. */
  35         char *objects_dir;
  36
  37         /** Alternate databases to search. */
  38         git_odb **alternates;
  39 };
  40
  41 typedef struct {  /* object header data */
  42         git_otype type;  /* object type */
  43         size_t    size;  /* object size */
  44 } obj_hdr;
  45
  46 static struct {
  47         const char *str;   /* type name string */
  48         int        loose;  /* valid loose object type flag */
  49 } obj_type_table [] = {
  50         { "",          0 },  /* 0 = GIT_OBJ__EXT1     */
  51         { "commit",    1 },  /* 1 = GIT_OBJ_COMMIT    */
  52         { "tree",      1 },  /* 2 = GIT_OBJ_TREE      */
  53         { "blob",      1 },  /* 3 = GIT_OBJ_BLOB      */
  54         { "tag",       1 },  /* 4 = GIT_OBJ_TAG       */
  55         { "",          0 },  /* 5 = GIT_OBJ__EXT2     */
  56         { "OFS_DELTA", 0 },  /* 6 = GIT_OBJ_OFS_DELTA */
  57         { "REF_DELTA", 0 }   /* 7 = GIT_OBJ_REF_DELTA */
  58 };
  59
  60 const char *git_obj_type_to_string(git_otype type)
  61 {
  62         if (type < 0 || type >= ARRAY_SIZE(obj_type_table))
  63                 return "";
  64         return obj_type_table[type].str;
  65 }
  66
  67 git_otype git_obj_string_to_type(const char *str)
  68 {
  69         int i;
  70
  71         if (!str || !*str)
  72                 return GIT_OBJ_BAD;
  73
  74         for (i = 0; i < ARRAY_SIZE(obj_type_table); i++)
  75                 if (!strcmp(str, obj_type_table[i].str))
  76                         return (git_otype) i;
  77
  78         return GIT_OBJ_BAD;
  79 }
  80
  81 int git_obj__loose_object_type(git_otype type)
  82 {
  83         if (type < 0 || type >= ARRAY_SIZE(obj_type_table))
  84                 return 0;
  85         return obj_type_table[type].loose;
  86 }
  87
  88 static int format_object_header(char *hdr, size_t n, git_obj *obj)
  89 {
  90         const char *type_str = git_obj_type_to_string(obj->type);
  91         int len = snprintf(hdr, n, "%s %" PRIuPTR, type_str, obj->len);
  92
  93         assert(len > 0);  /* otherwise snprintf() is broken */
  94         assert(len < n);  /* otherwise the caller is broken! */
  95
  96         if (len < 0 || len >= n)
  97                 return GIT_ERROR;
  98         return len+1;
  99 }
 100
 101 int git_obj_hash(git_oid *id, git_obj *obj)
 102 {
 103         git_buf_vec vec[2];
 104         char hdr[64];
 105         int  hdrlen;
 106
 107         assert(id && obj);
 108
 109         if (!git_obj__loose_object_type(obj->type))
 110                 return GIT_ERROR;
 111
 112         if (!obj->data && obj->len != 0)
 113                 return GIT_ERROR;
 114
 115         if ((hdrlen = format_object_header(hdr, sizeof(hdr), obj)) < 0)
 116                 return GIT_ERROR;
 117
 118         vec[0].data = hdr;
 119         vec[0].len  = hdrlen;
 120         vec[1].data = obj->data;
 121         vec[1].len  = obj->len;
 122
 123         git_hash_vec(id, vec, 2);
 124
 125         return GIT_SUCCESS;
 126 }
 127
 128 static int object_file_name(char *name, size_t n, char *dir, const git_oid *id)
 129 {
 130         size_t len = strlen(dir);
 131
 132         /* check length: 43 = 40 hex sha1 chars + 2 * '/' + '\0' */
 133         if (len+43 > n)
 134                 return len+43;
 135
 136         /* the object dir: eg $GIT_DIR/objects */
 137         strcpy(name, dir);
 138         if (name[len-1] != '/')
 139                 name[len++] = '/';
 140
 141         /* loose object filename: aa/aaa... (41 bytes) */
 142         git_oid_pathfmt(&name[len], id);
 143         name[len+41] = '\0';
 144
 145         return 0;
 146 }
 147
 148 static int is_zlib_compressed_data(unsigned char *data)
 149 {
 150         unsigned int w;
 151
 152         w = ((unsigned int)(data[0]) << 8) + data[1];
 153         return data[0] == 0x78 && !(w %31);
 154 }
 155
 156 static size_t get_binary_object_header(obj_hdr *hdr, gitfo_buf *obj)
 157 {
 158         unsigned char c;
 159         unsigned char *data = obj->data;
 160         size_t shift, size, used = 0;
 161
 162         if (obj->len == 0)
 163                 return 0;
 164
 165         c = data[used++];
 166         hdr->type = (c >> 4) & 7;
 167
 168         size = c & 15;
 169         shift = 4;
 170         while (c & 0x80) {
 171                 if (obj->len <= used)
 172                         return 0;
 173                 if (sizeof(size_t) * 8 <= shift)
 174                         return 0;
 175                 c = data[used++];
 176                 size += (c & 0x7f) << shift;
 177                 shift += 7;
 178         }
 179         hdr->size = size;
 180
 181         return used;
 182 }
 183
 184 static size_t get_object_header(obj_hdr *hdr, unsigned char *data)
 185 {
 186         char c, typename[10];
 187         size_t size, used = 0;
 188
 189         /*
 190          * type name string followed by space.
 191          */
 192         while ((c = data[used]) != ' ') {
 193                 typename[used++] = c;
 194                 if (used >= sizeof(typename))
 195                         return 0;
 196         }
 197         typename[used] = 0;
 198         if (used == 0)
 199                 return 0;
 200         hdr->type = git_obj_string_to_type(typename);
 201         used++;  /* consume the space */
 202
 203         /*
 204          * length follows immediately in decimal (without
 205          * leading zeros).
 206          */
 207         size = data[used++] - '0';
 208         if (size > 9)
 209                 return 0;
 210         if (size) {
 211                 while ((c = data[used]) != '\0') {
 212                         size_t d = c - '0';
 213                         if (d > 9)
 214                                 break;
 215                         used++;
 216                         size = size * 10 + d;
 217                 }
 218         }
 219         hdr->size = size;
 220
 221         /*
 222          * the length must be followed by a zero byte
 223          */
 224         if (data[used++] != '\0')
 225                 return 0;
 226
 227         return used;
 228 }
 229
 230 static void init_stream(z_stream *s, void *out, size_t len)
 231 {
 232         memset(s, 0, sizeof(*s));
 233         s->next_out  = out;
 234         s->avail_out = len;
 235 }
 236
 237 static void set_stream_input(z_stream *s, void *in, size_t len)
 238 {
 239         s->next_in  = in;
 240         s->avail_in = len;
 241 }
 242
 243 static void set_stream_output(z_stream *s, void *out, size_t len)
 244 {
 245         s->next_out  = out;
 246         s->avail_out = len;
 247 }
 248
 249 static int start_inflate(z_stream *s, gitfo_buf *obj, void *out, size_t len)
 250 {
 251         init_stream(s, out, len);
 252         set_stream_input(s, obj->data, obj->len);
 253         inflateInit(s);
 254         return inflate(s, 0);
 255 }
 256
 257 static int finish_inflate(z_stream *s)
 258 {
 259         int status = Z_OK;
 260
 261         while (status == Z_OK)
 262                 status = inflate(s, Z_FINISH);
 263
 264         inflateEnd(s);
 265
 266         if ((status != Z_STREAM_END) || (s->avail_in != 0))
 267                 return GIT_ERROR;
 268
 269         return GIT_SUCCESS;
 270 }
 271
 272 static void *inflate_tail(z_stream *s, void *hb, size_t used, obj_hdr *hdr)
 273 {
 274         unsigned char *buf, *head = hb;
 275         size_t tail;
 276
 277         /*
 278          * allocate a buffer to hold the inflated data and copy the
 279          * initial sequence of inflated data from the tail of the
 280          * head buffer, if any.
 281          */
 282         if ((buf = git__malloc(hdr->size + 1)) == NULL)
 283                 return NULL;
 284         tail = s->total_out - used;
 285         if (used > 0 && tail > 0) {
 286                 if (tail > hdr->size)
 287                         tail = hdr->size;
 288                 memcpy(buf, head + used, tail);
 289         }
 290         used = tail;
 291
 292         /*
 293          * inflate the remainder of the object data, if any
 294          */
 295         if (hdr->size >= used) {
 296                 set_stream_output(s, buf + used, hdr->size - used);
 297                 if (finish_inflate(s)) {
 298                         free(buf);
 299                         return NULL;
 300                 }
 301         }
 302
 303         return buf;
 304 }
 305
 306 static int inflate_buffer(void *in, size_t inlen, void *out, size_t outlen)
 307 {
 308         z_stream zs;
 309         int status = Z_OK;
 310
 311         init_stream(&zs, out, outlen);
 312         set_stream_input(&zs, in, inlen);
 313
 314         inflateInit(&zs);
 315
 316         while (status == Z_OK)
 317                 status = inflate(&zs, Z_FINISH);
 318
 319         inflateEnd(&zs);
 320
 321         if ((status != Z_STREAM_END) || (zs.total_out != outlen))
 322                 return GIT_ERROR;
 323
 324         if (zs.avail_in != 0)
 325                 return GIT_ERROR;
 326
 327         return GIT_SUCCESS;
 328 }
 329
 330 /*
 331  * At one point, there was a loose object format that was intended to
 332  * mimic the format used in pack-files. This was to allow easy copying
 333  * of loose object data into packs. This format is no longer used, but
 334  * we must still read it.
 335  */
 336 static int inflate_packlike_loose_disk_obj(git_obj *out, gitfo_buf *obj)
 337 {
 338         unsigned char *in, *buf;
 339         obj_hdr hdr;
 340         size_t len, used;
 341
 342         /*
 343          * read the object header, which is an (uncompressed)
 344          * binary encoding of the object type and size.
 345          */
 346         if ((used = get_binary_object_header(&hdr, obj)) == 0)
 347                 return GIT_ERROR;
 348
 349         if (!git_obj__loose_object_type(hdr.type))
 350                 return GIT_ERROR;
 351
 352         /*
 353          * allocate a buffer and inflate the data into it
 354          */
 355         buf = git__malloc(hdr.size + 1);
 356         if (!buf)
 357                 return GIT_ERROR;
 358
 359         in  = ((unsigned char *)obj->data) + used;
 360         len = obj->len - used;
 361         if (inflate_buffer(in, len, buf, hdr.size)) {
 362                 free(buf);
 363                 return GIT_ERROR;
 364         }
 365         buf[hdr.size] = '\0';
 366
 367         out->data = buf;
 368         out->len  = hdr.size;
 369         out->type = hdr.type;
 370
 371         return GIT_SUCCESS;
 372 }
 373
 374 static int inflate_disk_obj(git_obj *out, gitfo_buf *obj)
 375 {
 376         unsigned char head[64], *buf;
 377         z_stream zs;
 378         int z_status;
 379         obj_hdr hdr;
 380         size_t used;
 381
 382         /*
 383          * check for a pack-like loose object
 384          */
 385         if (!is_zlib_compressed_data(obj->data))
 386                 return inflate_packlike_loose_disk_obj(out, obj);
 387
 388         /*
 389          * inflate the initial part of the io buffer in order
 390          * to parse the object header (type and size).
 391          */
 392         if ((z_status = start_inflate(&zs, obj, head, sizeof(head))) < Z_OK)
 393                 return GIT_ERROR;
 394
 395         if ((used = get_object_header(&hdr, head)) == 0)
 396                 return GIT_ERROR;
 397
 398         if (!git_obj__loose_object_type(hdr.type))
 399                 return GIT_ERROR;
 400
 401         /*
 402          * allocate a buffer and inflate the object data into it
 403          * (including the initial sequence in the head buffer).
 404          */
 405         if ((buf = inflate_tail(&zs, head, used, &hdr)) == NULL)
 406                 return GIT_ERROR;
 407         buf[hdr.size] = '\0';
 408
 409         out->data = buf;
 410         out->len  = hdr.size;
 411         out->type = hdr.type;
 412
 413         return GIT_SUCCESS;
 414 }
 415
 416 static int open_alternates(git_odb *db)
 417 {
 418         unsigned n = 0;
 419
 420         db->alternates = git__malloc(sizeof(*db->alternates) * (n + 1));
 421         if (!db->alternates)
 422                 return GIT_ERROR;
 423
 424         db->alternates[n] = NULL;
 425         return GIT_SUCCESS;
 426 }
 427
 428 int git_odb_open(git_odb **out, const char *objects_dir)
 429 {
 430         git_odb *db = git__malloc(sizeof(*db));
 431         if (!db)
 432                 return GIT_ERROR;
 433
 434         db->objects_dir = git__strdup(objects_dir);
 435         if (!db->objects_dir) {
 436                 free(db);
 437                 return GIT_ERROR;
 438         }
 439
 440         db->alternates = NULL;
 441
 442         *out = db;
 443         return GIT_SUCCESS;
 444 }
 445
 446 void git_odb_close(git_odb *db)
 447 {
 448         if (!db)
 449                 return;
 450
 451         if (db->alternates) {
 452                 git_odb **alt;
 453                 for (alt = db->alternates; *alt; alt++)
 454                         git_odb_close(*alt);
 455                 free(db->alternates);
 456         }
 457
 458         free(db->objects_dir);
 459         free(db);
 460 }
 461
 462 int git_odb_read(
 463         git_obj *out,
 464         git_odb *db,
 465         const git_oid *id)
 466 {
 467 attempt:
 468         if (!git_odb__read_packed(out, db, id))
 469                 return GIT_SUCCESS;
 470         if (!git_odb__read_loose(out, db, id))
 471                 return GIT_SUCCESS;
 472         if (!db->alternates && !open_alternates(db))
 473                 goto attempt;
 474
 475         out->data = NULL;
 476         return GIT_ENOTFOUND;
 477 }
 478
 479 int git_odb__read_loose(git_obj *out, git_odb *db, const git_oid *id)
 480 {
 481         char file[GIT_PATH_MAX];
 482         gitfo_buf obj = GITFO_BUF_INIT;
 483
 484         assert(out && db && id);
 485
 486         out->data = NULL;
 487         out->len  = 0;
 488         out->type = GIT_OBJ_BAD;
 489
 490         if (object_file_name(file, sizeof(file), db->objects_dir, id))
 491                 return GIT_ENOTFOUND;  /* TODO: error handling */
 492
 493         if (gitfo_read_file(&obj, file))
 494                 return GIT_ENOTFOUND;  /* TODO: error handling */
 495
 496         if (inflate_disk_obj(out, &obj)) {
 497                 gitfo_free_buf(&obj);
 498                 return GIT_ENOTFOUND;  /* TODO: error handling */
 499         }
 500
 501         gitfo_free_buf(&obj);
 502
 503         return GIT_SUCCESS;
 504 }
 505
 506 int git_odb__read_packed(git_obj *out, git_odb *db, const git_oid *id)
 507 {
 508         return GIT_ENOTFOUND;
 509 }
 510