src/odb_pack.c

/*
 * This file is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License, version 2,
 * as published by the Free Software Foundation.
 *
 * In addition to the permissions in the GNU General Public License,
 * the authors give you unlimited permission to link the compiled
 * version of this file into combinations with other programs,
 * and to distribute those combinations without any restriction
 * coming from the use of this file.  (The General Public License
 * restrictions do apply in other respects; for example, they cover
 * modification of the file, and distribution when not linked into
 * a combined executable.)
 *
 * This file is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; see the file COPYING.  If not, write to
 * the Free Software Foundation, 51 Franklin Street, Fifth Floor,
 * Boston, MA 02110-1301, USA.
 */

#include "common.h"
#include "git2/zlib.h"
#include "git2/repository.h"
#include "fileops.h"
#include "hash.h"
#include "odb.h"
#include "delta-apply.h"

#include "git2/odb_backend.h"

#define DEFAULT_WINDOW_SIZE \
	(sizeof(void*) >= 8 \
		?  1 * 1024 * 1024 * 1024 \
		: 32 * 1024 * 1024)

#define DEFAULT_MAPPED_LIMIT \
	((1024L * 1024L) * (sizeof(void*) >= 8 ? 8192 : 256))

#define PACK_SIGNATURE 0x5041434b	/* "PACK" */
#define PACK_VERSION 2
#define pack_version_ok(v) ((v) == htonl(2) || (v) == htonl(3))
struct pack_header {
	uint32_t hdr_signature;
	uint32_t hdr_version;
	uint32_t hdr_entries;
};

/*
 * The first four bytes of index formats later than version 1 should
 * start with this signature, as all older git binaries would find this
 * value illegal and abort reading the file.
 *
 * This is the case because the number of objects in a packfile
 * cannot exceed 1,431,660,000 as every object would need at least
 * 3 bytes of data and the overall packfile cannot exceed 4 GiB with
 * version 1 of the index file due to the offsets limited to 32 bits.
 * Clearly the signature exceeds this maximum.
 *
 * Very old git binaries will also compare the first 4 bytes to the
 * next 4 bytes in the index and abort with a "non-monotonic index"
 * error if the second 4 byte word is smaller than the first 4
 * byte word.  This would be true in the proposed future index
 * format as idx_signature would be greater than idx_version.
 */
#define PACK_IDX_SIGNATURE 0xff744f63	/* "\377tOc" */

struct pack_idx_header {
	uint32_t idx_signature;
	uint32_t idx_version;
};

struct pack_window {
	struct pack_window *next;
	git_map window_map;
	off_t offset;
	unsigned int last_used;
	unsigned int inuse_cnt;
};

struct pack_file {
	struct pack_window *windows;
	off_t pack_size;

	git_map index_map;

	uint32_t num_objects;
	uint32_t num_bad_objects;
	git_oid *bad_object_sha1; /* array of git_oid */

	int index_version;
	time_t mtime;
	int pack_fd;
	unsigned pack_local:1, pack_keep:1;
	git_oid sha1;

	/* something like ".git/objects/pack/xxxxx.pack" */
	char pack_name[GIT_FLEX_ARRAY]; /* more */
};

struct pack_entry {
	off_t offset;
	git_oid sha1;
	struct pack_file *p;
};

struct pack__dirent {
	struct pack_backend *backend;
	int is_pack_local;
};

struct pack_backend {
	git_odb_backend parent;
	git_vector packs;
	struct pack_file *last_found;

	size_t window_size; /* needs default value */

	size_t mapped_limit; /* needs default value */
	size_t peak_mapped;
	size_t mapped;

	size_t used_ctr;

	unsigned int peak_open_windows;
	unsigned int open_windows;

	unsigned int mmap_calls;
};

/**
 * The wonderful tale of a Packed Object lookup query
 * ===================================================
 *   A riveting and epic story of epicness and ASCII
 *          art, presented by yours truly,
 *               Sir Vicent of Marti
 *
 *
 *	Chapter 1: Once upon a time...
 *	Initialization of the Pack Backend
 *	--------------------------------------------------
 *
 *	# git_odb_backend_pack
 *	| Creates the pack backend structure, initializes the
 *	| callback pointers to our default read() and exist() methods,
 *	| and tries to preload all the known packfiles in the ODB.
 *  |
 *	|-# packfile_load_all
 *	  | Tries to find the `pack` folder, if it exists. ODBs without
 *	  | a pack folder are ignored altogether. If there's a `pack` folder
 *	  | we run a `dirent` callback through every file in the pack folder
 *	  | to find our packfiles. The packfiles are then sorted according
 *	  | to a sorting callback.
 * 	  |
 *	  |-# packfile_load__cb
 *	  | | This callback is called from `dirent` with every single file
 *	  | | inside the pack folder. We find the packs by actually locating
 *	  | | their index (ends in ".idx"). From that index, we verify that
 *	  | | the corresponding packfile exists and is valid, and if so, we
 *    | | add it to the pack list.
 *	  | |
 *	  | |-# packfile_check
 *	  |     Make sure that there's a packfile to back this index, and store
 *	  |     some very basic information regarding the packfile itself,
 *	  |     such as the full path, the size, and the modification time.
 *	  |     We don't actually open the packfile to check for internal consistency.
 *    |
 *    |-# packfile_sort__cb
 *        Sort all the preloaded packs according to some specific criteria:
 *        we prioritize the "newer" packs because it's more likely they
 *        contain the objects we are looking for, and we prioritize local
 *        packs over remote ones.
 *
 *
 *
 *	Chapter 2: To be, or not to be...
 *	A standard packed `exist` query for an OID
 *	--------------------------------------------------
 *
 *  # pack_backend__exists
 *  | Check if the given SHA1 oid exists in any of the packs
 *  | that have been loaded for our ODB.
 *  |
 *  |-# pack_entry_find
 *    | Iterate through all the packs that have been preloaded
 *    | (starting by the pack where the latest object was found)
 *    | to try to find the OID in one of them.
 *    |
 *    |-# pack_entry_find1
 *      | Check the index of an individual pack to see if the SHA1
 *      | OID can be found. If we can find the offset to that SHA1
 *      | inside of the index, that means the object is contained
 *      | inside of the packfile and we can stop searching.
 *      | Before returning, we verify that the packfile behing the
 *      | index we are searching still exists on disk.
 *      |
 *      |-# pack_entry_find_offset
 *      | | Mmap the actual index file to disk if it hasn't been opened
 *      | | yet, and run a binary search through it to find the OID.
 *      | | See <http://book.git-scm.com/7_the_packfile.html> for specifics
 *      | | on the Packfile Index format and how do we find entries in it.
 *      | |
 *      | |-# pack_index_open
 *      |   | Guess the name of the index based on the full path to the
 *      |   | packfile, open it and verify its contents. Only if the index
 *      |   | has not been opened already.
 *      |   |
 *      |   |-# pack_index_check
 *      |       Mmap the index file and do a quick run through the header
 *      |       to guess the index version (right now we support v1 and v2),
 *      |       and to verify that the size of the index makes sense.
 *      |
 *      |-# packfile_open
 *          See `packfile_open` in Chapter 3
 *
 *
 *
 *	Chapter 3: The neverending story...
 *	A standard packed `lookup` query for an OID
 *	--------------------------------------------------
 *	TODO
 *
 */



 
/***********************************************************
 *
 * FORWARD DECLARATIONS
 *
 ***********************************************************/

static void pack_window_free_all(struct pack_backend *backend, struct pack_file *p);
static int pack_window_contains(struct pack_window *win, off_t offset);

static void pack_window_scan_lru(struct pack_file *p, struct pack_file **lru_p,
		struct pack_window **lru_w, struct pack_window **lru_l);

static int pack_window_close_lru( struct pack_backend *backend,
		struct pack_file *current, git_file keep_fd);

static void pack_window_close(struct pack_window **w_cursor);

static unsigned char *pack_window_open( struct pack_backend *backend,
		struct pack_file *p, struct pack_window **w_cursor, off_t offset,
		unsigned int *left);

static int packfile_sort__cb(const void *a_, const void *b_);

static void pack_index_free(struct pack_file *p);

static int pack_index_check(const char *path,  struct pack_file *p);
static int pack_index_open(struct pack_file *p);

static struct pack_file *packfile_alloc(int extra);
static int packfile_open(struct pack_file *p);
static int packfile_check(struct pack_file **pack_out, const char *path, int local);
static int packfile_load__cb(void *_data, char *path);
static int packfile_load_all(struct pack_backend *backend, const char *odb_path, int local);

static off_t nth_packed_object_offset(const struct pack_file *p, uint32_t n);

static int pack_entry_find_offset(off_t *offset_out,
		struct pack_file *p, const git_oid *oid);

static int pack_entry_find1(struct pack_entry *e,
		struct pack_file *p, const git_oid *oid);

static int pack_entry_find(struct pack_entry *e,
		struct pack_backend *backend, const git_oid *oid);

static off_t get_delta_base(struct pack_backend *backend,
		struct pack_file *p, struct pack_window **w_curs,
		off_t *curpos, git_otype type,
		off_t delta_obj_offset);

static unsigned long packfile_unpack_header1(
		size_t *sizep,
		git_otype *type, 
		const unsigned char *buf,
		unsigned long len);

static int packfile_unpack_header(
		size_t *size_p,
		git_otype *type_p,
		struct pack_backend *backend,
		struct pack_file *p,
		struct pack_window **w_curs,
		off_t *curpos);

static int packfile_unpack_compressed(
		git_rawobj *obj,
		struct pack_backend *backend,
		struct pack_file *p,
		struct pack_window **w_curs,
		off_t curpos,
		size_t size,
		git_otype type);

static int packfile_unpack_delta(
		git_rawobj *obj,
		struct pack_backend *backend,
		struct pack_file *p,
		struct pack_window **w_curs,
		off_t curpos,
		size_t delta_size,
		git_otype delta_type,
		off_t obj_offset);

static int packfile_unpack(git_rawobj *obj, struct pack_backend *backend,
		struct pack_file *p, off_t obj_offset);





/***********************************************************
 *
 * PACK WINDOW MANAGEMENT
 *
 ***********************************************************/

void pack_window_free_all(struct pack_backend *backend, struct pack_file *p)
{
	while (p->windows) {
		struct pack_window *w = p->windows;
		assert(w->inuse_cnt == 0);

		backend->mapped -= w->window_map.len;
		backend->open_windows--;

		gitfo_free_map(&w->window_map);

		p->windows = w->next;
		free(w);
	}
}

GIT_INLINE(int) pack_window_contains(struct pack_window *win, off_t offset)
{
	/* We must promise at least 20 bytes (one hash) after the
	 * offset is available from this window, otherwise the offset
	 * is not actually in this window and a different window (which
	 * has that one hash excess) must be used.  This is to support
	 * the object header and delta base parsing routines below.
	 */
	off_t win_off = win->offset;
	return win_off <= offset
		&& (offset + 20) <= (off_t)(win_off + win->window_map.len);
}

static void pack_window_scan_lru(
	struct pack_file *p,
	struct pack_file **lru_p,
	struct pack_window **lru_w,
	struct pack_window **lru_l)
{
	struct pack_window *w, *w_l;

	for (w_l = NULL, w = p->windows; w; w = w->next) {
		if (!w->inuse_cnt) {
			if (!*lru_w || w->last_used < (*lru_w)->last_used) {
				*lru_p = p;
				*lru_w = w;
				*lru_l = w_l;
			}
		}
		w_l = w;
	}
}

static int pack_window_close_lru(
		struct pack_backend *backend,
		struct pack_file *current,
		git_file keep_fd)
{
	struct pack_file *lru_p = NULL;
	struct pack_window *lru_w = NULL, *lru_l = NULL;
	size_t i;

	if (current)
		pack_window_scan_lru(current, &lru_p, &lru_w, &lru_l);

	for (i = 0; i < backend->packs.length; ++i)
		pack_window_scan_lru(git_vector_get(&backend->packs, i), &lru_p, &lru_w, &lru_l);

	if (lru_p) {
		backend->mapped -= lru_w->window_map.len;
		gitfo_free_map(&lru_w->window_map);

		if (lru_l)
			lru_l->next = lru_w->next;
		else {
			lru_p->windows = lru_w->next;
			if (!lru_p->windows && lru_p->pack_fd != keep_fd) {
				gitfo_close(lru_p->pack_fd);
				lru_p->pack_fd = -1;
			}
		}

		free(lru_w);
		backend->open_windows--;
		return GIT_SUCCESS;
	}

	return GIT_ERROR;
}

static void pack_window_close(struct pack_window **w_cursor)
{
	struct pack_window *w = *w_cursor;
	if (w) {
		w->inuse_cnt--;
		*w_cursor = NULL;
	}
}

static unsigned char *pack_window_open(
		struct pack_backend *backend,
		struct pack_file *p,
		struct pack_window **w_cursor,
		off_t offset,
		unsigned int *left)
{
	struct pack_window *win = *w_cursor;

	if (p->pack_fd == -1 && packfile_open(p) < GIT_SUCCESS)
		return NULL;

	/* Since packfiles end in a hash of their content and it's
	 * pointless to ask for an offset into the middle of that
	 * hash, and the pack_window_contains function above wouldn't match
	 * don't allow an offset too close to the end of the file.
	 */
	if (offset > (p->pack_size - 20))
		return NULL;

	if (!win || !pack_window_contains(win, offset)) {

		if (win)
			win->inuse_cnt--;

		for (win = p->windows; win; win = win->next) {
			if (pack_window_contains(win, offset))
				break;
		}

		if (!win) {
			size_t window_align = backend->window_size / 2;
			size_t len;

			win = git__calloc(1, sizeof(*win));
			win->offset = (offset / window_align) * window_align;

			len = (size_t)(p->pack_size - win->offset);
			if (len > backend->window_size)
				len = backend->window_size;

			backend->mapped += len;

			while (backend->mapped_limit < backend->mapped &&
				pack_window_close_lru(backend, p, p->pack_fd) == GIT_SUCCESS) {}

			if (gitfo_map_ro(&win->window_map, p->pack_fd,
					win->offset, len) < GIT_SUCCESS)
				return NULL;

			backend->mmap_calls++;
			backend->open_windows++;

			if (backend->mapped > backend->peak_mapped)
				backend->peak_mapped = backend->mapped;

			if (backend->open_windows > backend->peak_open_windows)
				backend->peak_open_windows = backend->open_windows;

			win->next = p->windows;
			p->windows = win;
		}
	}

	if (win != *w_cursor) {
		win->last_used = backend->used_ctr++;
		win->inuse_cnt++;
		*w_cursor = win;
	}

	offset -= win->offset;
	assert(git__is_sizet(offset));

	if (left)
		*left = win->window_map.len - (size_t)offset;

	return (unsigned char *)win->window_map.data + offset;
}







/***********************************************************
 *
 * PACK INDEX METHODS
 *
 ***********************************************************/

static void pack_index_free(struct pack_file *p)
{
	if (p->index_map.data) {
		gitfo_free_map(&p->index_map);
		p->index_map.data = NULL;
	}
}

static int pack_index_check(const char *path,  struct pack_file *p)
{
	struct pack_idx_header *hdr;
	uint32_t version, nr, i, *index;

	void *idx_map;
	size_t idx_size;

	struct stat st;

	/* TODO: properly open the file without access time */
	git_file fd = gitfo_open(path, O_RDONLY /*| O_NOATIME */);

	int error;

	if (fd < 0)
		return GIT_EOSERR;

	if (gitfo_fstat(fd, &st) < GIT_SUCCESS) {
		gitfo_close(fd);
		return GIT_EOSERR;
	}

	if (!git__is_sizet(st.st_size))
		return GIT_ENOMEM;

	idx_size = (size_t)st.st_size;

	if (idx_size < 4 * 256 + 20 + 20) {
		gitfo_close(fd);
		return GIT_EOBJCORRUPTED;
	}

	error = gitfo_map_ro(&p->index_map, fd, 0, idx_size);
	gitfo_close(fd);

	if (error < GIT_SUCCESS)
		return error;

	hdr = idx_map = p->index_map.data;

	if (hdr->idx_signature == htonl(PACK_IDX_SIGNATURE)) {
		version = ntohl(hdr->idx_version);

		if (version < 2 || version > 2) {
			gitfo_free_map(&p->index_map);
			return GIT_EOBJCORRUPTED; /* unsupported index version */
		}

	} else
		version = 1;

	nr = 0;
	index = idx_map;

	if (version > 1)
		index += 2;  /* skip index header */

	for (i = 0; i < 256; i++) {
		uint32_t n = ntohl(index[i]);
		if (n < nr) {
			gitfo_free_map(&p->index_map);
			return GIT_EOBJCORRUPTED; /* non-monotonic index */
		}
		nr = n;
	}

	if (version == 1) {
		/*
		 * Total size:
		 *  - 256 index entries 4 bytes each
		 *  - 24-byte entries * nr (20-byte sha1 + 4-byte offset)
		 *  - 20-byte SHA1 of the packfile
		 *  - 20-byte SHA1 file checksum
		 */
		if (idx_size != 4*256 + nr * 24 + 20 + 20) {
			gitfo_free_map(&p->index_map);
			return GIT_EOBJCORRUPTED;
		}
	} else if (version == 2) {
		/*
		 * Minimum size:
		 *  - 8 bytes of header
		 *  - 256 index entries 4 bytes each
		 *  - 20-byte sha1 entry * nr
		 *  - 4-byte crc entry * nr
		 *  - 4-byte offset entry * nr
		 *  - 20-byte SHA1 of the packfile
		 *  - 20-byte SHA1 file checksum
		 * And after the 4-byte offset table might be a
		 * variable sized table containing 8-byte entries
		 * for offsets larger than 2^31.
		 */
		unsigned long min_size = 8 + 4*256 + nr*(20 + 4 + 4) + 20 + 20;
		unsigned long max_size = min_size;

		if (nr)
			max_size += (nr - 1)*8;

		if (idx_size < min_size || idx_size > max_size) {
			gitfo_free_map(&p->index_map);
			return GIT_EOBJCORRUPTED;
		}

		/* Make sure that off_t is big enough to access the whole pack...
		 * Is this an issue in libgit2? It shouldn't. */
		if (idx_size != min_size && (sizeof(off_t) <= 4)) {
			gitfo_free_map(&p->index_map);
			return GIT_EOSERR;
		}
	}

	p->index_version = version;
	p->num_objects = nr;
	return GIT_SUCCESS;
}

static int pack_index_open(struct pack_file *p)
{
	char *idx_name;
	int error;

	if (p->index_map.data)
		return GIT_SUCCESS;

	idx_name = git__strdup(p->pack_name);
	strcpy(idx_name + strlen(idx_name) - STRLEN(".pack"), ".idx");

	error = pack_index_check(idx_name, p);
	free(idx_name);

	return error;
}









/***********************************************************
 *
 * PACKFILE METHODS
 *
 ***********************************************************/

static int packfile_sort__cb(const void *a_, const void *b_)
{
	struct pack_file *a = *((struct pack_file **)a_);
	struct pack_file *b = *((struct pack_file **)b_);
	int st;

	/*
	 * Local packs tend to contain objects specific to our
	 * variant of the project than remote ones.  In addition,
	 * remote ones could be on a network mounted filesystem.
	 * Favor local ones for these reasons.
	 */
	st = a->pack_local - b->pack_local;
	if (st)
		return -st;

	/*
	 * Younger packs tend to contain more recent objects,
	 * and more recent objects tend to get accessed more
	 * often.
	 */
	if (a->mtime < b->mtime)
		return 1;
	else if (a->mtime == b->mtime)
		return 0;

	return -1;
}

static struct pack_file *packfile_alloc(int extra)
{
	struct pack_file *p = git__malloc(sizeof(*p) + extra);
	memset(p, 0, sizeof(*p));
	p->pack_fd = -1;
	return p;
}


static void packfile_free(struct pack_backend *backend, struct pack_file *p)
{
	assert(p);

	/* clear_delta_base_cache(); */
	pack_window_free_all(backend, p);

	if (p->pack_fd != -1)
		gitfo_close(p->pack_fd);

	pack_index_free(p);

	free(p->bad_object_sha1);
	free(p);
}

static int packfile_open(struct pack_file *p)
{
	struct stat st;
	struct pack_header hdr;
	git_oid sha1;
	unsigned char *idx_sha1;

	if (!p->index_map.data && pack_index_open(p) < GIT_SUCCESS)
		return GIT_ENOTFOUND;

	/* TODO: open with noatime */
	p->pack_fd = gitfo_open(p->pack_name, O_RDONLY);
	if (p->pack_fd < 0 || gitfo_fstat(p->pack_fd, &st) < GIT_SUCCESS)
		return GIT_EOSERR;

	/* If we created the struct before we had the pack we lack size. */
	if (!p->pack_size) {
		if (!S_ISREG(st.st_mode))
			goto cleanup;
		p->pack_size = (off_t)st.st_size;
	} else if (p->pack_size != st.st_size)
		goto cleanup;

#if 0
	/* We leave these file descriptors open with sliding mmap;
	 * there is no point keeping them open across exec(), though.
	 */
	fd_flag = fcntl(p->pack_fd, F_GETFD, 0);
	if (fd_flag < 0)
		return error("cannot determine file descriptor flags");

	fd_flag |= FD_CLOEXEC;
	if (fcntl(p->pack_fd, F_SETFD, fd_flag) == -1)
		return GIT_EOSERR;
#endif

	/* Verify we recognize this pack file format. */
	if (gitfo_read(p->pack_fd, &hdr, sizeof(hdr)) < GIT_SUCCESS)
		goto cleanup;

	if (hdr.hdr_signature != htonl(PACK_SIGNATURE))
		goto cleanup;

	if (!pack_version_ok(hdr.hdr_version))
		goto cleanup;

	/* Verify the pack matches its index. */
	if (p->num_objects != ntohl(hdr.hdr_entries))
		goto cleanup;

	if (gitfo_lseek(p->pack_fd, p->pack_size - GIT_OID_RAWSZ, SEEK_SET) == -1)
		goto cleanup;

	if (gitfo_read(p->pack_fd, sha1.id, GIT_OID_RAWSZ) < GIT_SUCCESS)
		goto cleanup;

	idx_sha1 = ((unsigned char *)p->index_map.data) + p->index_map.len - 40;

	if (git_oid_cmp(&sha1, (git_oid *)idx_sha1) != 0)
		goto cleanup;

	return GIT_SUCCESS;	

cleanup:
	gitfo_close(p->pack_fd);
	p->pack_fd = -1;
	return GIT_EPACKCORRUPTED;
}

static int packfile_check(struct pack_file **pack_out, const char *path, int local)
{
	struct stat st;
	struct pack_file *p;
	size_t path_len;

	*pack_out = NULL;
	path_len = strlen(path);
	p = packfile_alloc(path_len + 2);

	/*
	 * Make sure a corresponding .pack file exists and that
	 * the index looks sane.
	 */
	path_len -= STRLEN(".idx");
	if (path_len < 1) {
		free(p);
		return GIT_ENOTFOUND;
	}

	memcpy(p->pack_name, path, path_len);

	strcpy(p->pack_name + path_len, ".keep");
	if (gitfo_exists(p->pack_name) == GIT_SUCCESS)
		p->pack_keep = 1;

	strcpy(p->pack_name + path_len, ".pack");
	if (gitfo_stat(p->pack_name, &st) < GIT_SUCCESS || !S_ISREG(st.st_mode)) {
		free(p);
		return GIT_ENOTFOUND;
	}

	/* ok, it looks sane as far as we can check without
	 * actually mapping the pack file.
	 */
	p->pack_size = (off_t)st.st_size;
	p->pack_local = local;
	p->mtime = st.st_mtime;

	/* see if we can parse the sha1 oid in the packfile name */
	if (path_len < 40 ||
		git_oid_mkstr(&p->sha1, path + path_len - GIT_OID_HEXSZ) < GIT_SUCCESS)
		memset(&p->sha1, 0x0, GIT_OID_RAWSZ);

	*pack_out = p;
	return GIT_SUCCESS;
}

static int packfile_load__cb(void *_data, char *path)
{
	struct pack__dirent *data = (struct pack__dirent *)_data;
	struct pack_file *pack;
	int error;

	if (git__suffixcmp(path, ".idx") != 0)
		return GIT_SUCCESS; /* not an index */

	/* FIXME: git.git checks for duplicate packs.
	 * But that makes no fucking sense. Our dirent is not
	 * going to generate dupicate entries */

	error = packfile_check(&pack, path, data->is_pack_local);
	if (error < GIT_SUCCESS)
		return error;

	if (git_vector_insert(&data->backend->packs, pack) < GIT_SUCCESS) {
		free(pack);
		return GIT_ENOMEM;
	}

	return GIT_SUCCESS;
}

static int packfile_load_all(struct pack_backend *backend, const char *odb_path, int local)
{
	int error;
	char path[GIT_PATH_MAX];
	struct pack__dirent data;

	data.backend = backend;
	data.is_pack_local = local;

	git__joinpath(path, odb_path, "pack");
	if (gitfo_isdir(path) < GIT_SUCCESS)
		return GIT_SUCCESS;

	error = gitfo_dirent(path, GIT_PATH_MAX, packfile_load__cb, (void *)&data);
	if (error < GIT_SUCCESS)
		return error;

	git_vector_sort(&backend->packs);
	backend->last_found = git_vector_get(&backend->packs, 0);

	return GIT_SUCCESS;
}








/***********************************************************
 *
 * PACKFILE ENTRY SEARCH INTERNALS
 *
 ***********************************************************/

static off_t nth_packed_object_offset(const struct pack_file *p, uint32_t n)
{
	const unsigned char *index = p->index_map.data;
	index += 4 * 256;
	if (p->index_version == 1) {
		return ntohl(*((uint32_t *)(index + 24 * n)));
	} else {
		uint32_t off;
		index += 8 + p->num_objects * (20 + 4);
		off = ntohl(*((uint32_t *)(index + 4 * n)));
		if (!(off & 0x80000000))
			return off;
		index += p->num_objects * 4 + (off & 0x7fffffff) * 8;
		return (((uint64_t)ntohl(*((uint32_t *)(index + 0)))) << 32) |
				   ntohl(*((uint32_t *)(index + 4)));
	}
}

static int pack_entry_find_offset(
		off_t *offset_out,
		struct pack_file *p,
		const git_oid *oid)
{
	const uint32_t *level1_ofs = p->index_map.data;
	const unsigned char *index = p->index_map.data;
	unsigned hi, lo, stride;

	*offset_out = 0;

	if (index == NULL) {
		int error;

		if ((error = pack_index_open(p)) < GIT_SUCCESS)
			return error;

		assert(p->index_map.data);

		index = p->index_map.data;
		level1_ofs = p->index_map.data;
	}

	if (p->index_version > 1) {
		level1_ofs += 2;
		index += 8;
	}

	index += 4 * 256;
	hi = ntohl(level1_ofs[(int)oid->id[0]]);
	lo = ((oid->id[0] == 0x0) ? 0 : ntohl(level1_ofs[(int)oid->id[0] - 1]));

	if (p->index_version > 1) {
		stride = 20;
	} else {
		stride = 24;
		index += 4;
	}

#ifdef INDEX_DEBUG_LOOKUP
	printf("%02x%02x%02x... lo %u hi %u nr %d\n",
		oid->id[0], oid->id[1], oid->id[2], lo, hi, p->num_objects);
#endif

#ifdef GIT2_INDEX_LOOKUP /* TODO: use the advanced lookup method from git.git */

	int pos = sha1_entry_pos(index, stride, 0, lo, hi, p->num_objects, oid);
	if (pos < 0)
		return GIT_ENOTFOUND;

	*offset_out = nth_packed_object_offset(p, pos);
	return GIT_SUCCESS;

#else /* use an old and boring binary search */

	do {
		unsigned mi = (lo + hi) / 2;
		int cmp = memcmp(index + mi * stride, oid->id, GIT_OID_RAWSZ);

		if (!cmp) {
			*offset_out = nth_packed_object_offset(p, mi);
			return GIT_SUCCESS;
		}

		if (cmp > 0)
			hi = mi;
		else
			lo = mi+1;

	} while (lo < hi);

	return GIT_ENOTFOUND;
#endif
}

static int pack_entry_find1(
		struct pack_entry *e,
		struct pack_file *p,
		const git_oid *oid)
{
	off_t offset;

	assert(p);

	if (p->num_bad_objects) {
		unsigned i;
		for (i = 0; i < p->num_bad_objects; i++)
			if (git_oid_cmp(oid, &p->bad_object_sha1[i]) == 0)
				return GIT_ERROR;
	}

	if (pack_entry_find_offset(&offset, p, oid) < GIT_SUCCESS)
		return GIT_ENOTFOUND;
	
	/* we found an entry in the index;
	 * make sure the packfile backing the index 
	 * still exists on disk */
	if (p->pack_fd == -1 && packfile_open(p) < GIT_SUCCESS)
		return GIT_EOSERR;

	e->offset = offset;
	e->p = p;

	git_oid_cpy(&e->sha1, oid);
	return GIT_SUCCESS;
}

static int pack_entry_find(struct pack_entry *e, struct pack_backend *backend, const git_oid *oid)
{
	size_t i;

	if (backend->last_found &&
		pack_entry_find1(e, backend->last_found, oid) == GIT_SUCCESS)
		return GIT_SUCCESS;

	for (i = 0; i < backend->packs.length; ++i) {
		struct pack_file *p;

		p = git_vector_get(&backend->packs, i);
		if (p == backend->last_found)
			continue;

		if (pack_entry_find1(e, p, oid) == GIT_SUCCESS) {
			backend->last_found = p;
			return GIT_SUCCESS;
		}
	}

	return GIT_ENOTFOUND;
}












/***********************************************************
 *
 * PACKFILE ENTRY UNPACK INTERNALS
 *
 ***********************************************************/

static unsigned long packfile_unpack_header1(
		size_t *sizep,
		git_otype *type, 
		const unsigned char *buf,
		unsigned long len)
{
	unsigned shift;
	unsigned long size, c;
	unsigned long used = 0;

	c = buf[used++];
	*type = (c >> 4) & 7;
	size = c & 15;
	shift = 4;
	while (c & 0x80) {
		if (len <= used || bitsizeof(long) <= shift)
			return 0;

		c = buf[used++];
		size += (c & 0x7f) << shift;
		shift += 7;
	}

	*sizep = (size_t)size;
	return used;
}

static int packfile_unpack_header(
		size_t *size_p,
		git_otype *type_p,
		struct pack_backend *backend,
		struct pack_file *p,
		struct pack_window **w_curs,
		off_t *curpos)
{
	unsigned char *base;
	unsigned int left;
	unsigned long used;

	/* pack_window_open() assures us we have [base, base + 20) available
	 * as a range that we can look at at.  (Its actually the hash
	 * size that is assured.)  With our object header encoding
	 * the maximum deflated object size is 2^137, which is just
	 * insane, so we know won't exceed what we have been given.
	 */
	base = pack_window_open(backend, p, w_curs, *curpos, &left);
	if (base == NULL)
		return GIT_ENOMEM;

	used = packfile_unpack_header1(size_p, type_p, base, left);

	if (used == 0)
		return GIT_EOBJCORRUPTED;

	*curpos += used;
	return GIT_SUCCESS;
}

static int packfile_unpack_compressed(
		git_rawobj *obj,
		struct pack_backend *backend,
		struct pack_file *p,
		struct pack_window **w_curs,
		off_t curpos,
		size_t size,
		git_otype type)
{
	int st;
	z_stream stream;
	unsigned char *buffer, *in;

	buffer = git__malloc(size);

	memset(&stream, 0, sizeof(stream));
	stream.next_out = buffer;
	stream.avail_out = size + 1;

	st = inflateInit(&stream);
	if (st != Z_OK) {
		free(buffer);
		return GIT_EZLIB;
	}

	do {
		in = pack_window_open(backend, p, w_curs, curpos, &stream.avail_in);
		stream.next_in = in;
		st = inflate(&stream, Z_FINISH);

		if (!stream.avail_out)
			break; /* the payload is larger than it should be */

		curpos += stream.next_in - in;
	} while (st == Z_OK || st == Z_BUF_ERROR);

	inflateEnd(&stream);

	if ((st != Z_STREAM_END) || stream.total_out != size) {
		free(buffer);
		return GIT_EZLIB;
	}

	obj->type = type;
	obj->len = size;
	obj->data = buffer;
	return GIT_SUCCESS;
}

static off_t get_delta_base(
		struct pack_backend *backend,
		struct pack_file *p,
		struct pack_window **w_curs,
		off_t *curpos,
		git_otype type,
		off_t delta_obj_offset)
{
	unsigned char *base_info = pack_window_open(backend, p, w_curs, *curpos, NULL);
	off_t base_offset;

	/* pack_window_open() assured us we have [base_info, base_info + 20)
	 * as a range that we can look at without walking off the
	 * end of the mapped window.  Its actually the hash size
	 * that is assured.  An OFS_DELTA longer than the hash size
	 * is stupid, as then a REF_DELTA would be smaller to store.
	 */
	if (type == GIT_OBJ_OFS_DELTA) {
		unsigned used = 0;
		unsigned char c = base_info[used++];
		base_offset = c & 127;
		while (c & 128) {
			base_offset += 1;
			if (!base_offset || MSB(base_offset, 7))
				return 0;  /* overflow */
			c = base_info[used++];
			base_offset = (base_offset << 7) + (c & 127);
		}
		base_offset = delta_obj_offset - base_offset;
		if (base_offset <= 0 || base_offset >= delta_obj_offset)
			return 0;  /* out of bound */
		*curpos += used;
	} else if (type == GIT_OBJ_REF_DELTA) {
		/* The base entry _must_ be in the same pack */
		if (pack_entry_find_offset(&base_offset, p, (git_oid *)base_info) < GIT_SUCCESS)
			return GIT_EPACKCORRUPTED;
		*curpos += 20;
	} else
		return 0;

	return base_offset;
}

static int packfile_unpack_delta(
		git_rawobj *obj,
		struct pack_backend *backend,
		struct pack_file *p,
		struct pack_window **w_curs,
		off_t curpos,
		size_t delta_size,
		git_otype delta_type,
		off_t obj_offset)
{
	off_t base_offset;
	git_rawobj base, delta;
	int error;

	base_offset = get_delta_base(backend, p, w_curs, &curpos, delta_type, obj_offset);
	if (base_offset == 0)
		return GIT_EOBJCORRUPTED;

	pack_window_close(w_curs);
	error = packfile_unpack(&base, backend, p, base_offset);

	/* TODO: git.git tries to load the base from other packfiles
	 * or loose objects */
	if (error < GIT_SUCCESS)
		return error;

	error = packfile_unpack_compressed(&delta, backend, p, w_curs, curpos, delta_size, delta_type);
	if (error < GIT_SUCCESS) {
		git_rawobj_close(&base);
		return error;
	}

	obj->type = base.type;
	error = git__delta_apply(obj,
			base.data, base.len,
			delta.data, delta.len);

	git_rawobj_close(&base);
	git_rawobj_close(&delta);

	/* TODO: we might want to cache this shit. eventually */
	//add_delta_base_cache(p, base_offset, base, base_size, *type);
	return error;
}

static int packfile_unpack(
		git_rawobj *obj,
		struct pack_backend *backend,
		struct pack_file *p,
		off_t obj_offset)
{
	struct pack_window *w_curs = NULL;
	off_t curpos = obj_offset;
	int error;

	size_t size;
	git_otype type;

	/* 
	 * TODO: optionally check the CRC on the packfile
	 */

	obj->data = NULL;
	obj->len = 0;
	obj->type = GIT_OBJ_BAD;

	error = packfile_unpack_header(&size, &type, backend, p, &w_curs, &curpos);
	if (error < GIT_SUCCESS)
		return error;

	switch (type) {
	case GIT_OBJ_OFS_DELTA:
	case GIT_OBJ_REF_DELTA:
		error = packfile_unpack_delta(
				obj, backend, p, &w_curs, curpos,
				size, type, obj_offset);
		break;

	case GIT_OBJ_COMMIT:
	case GIT_OBJ_TREE:
	case GIT_OBJ_BLOB:
	case GIT_OBJ_TAG:
		error = packfile_unpack_compressed(
				obj, backend, p, &w_curs, curpos,
				size, type);
		break;

	default:
		error = GIT_EOBJCORRUPTED;
		break;
	}

	pack_window_close(&w_curs);
	return error;
}





/***********************************************************
 *
 * PACKED BACKEND PUBLIC API
 *
 * Implement the git_odb_backend API calls
 *
 ***********************************************************/

/*
int pack_backend__read_header(git_rawobj *obj, git_odb_backend *backend, const git_oid *oid)
{
	pack_location location;

	assert(obj && backend && oid);

	if (locate_packfile(&location, (struct pack_backend *)backend, oid) < 0)
		return GIT_ENOTFOUND;

	return read_header_packed(obj, &location);
}
*/

int pack_backend__read(git_rawobj *obj, git_odb_backend *backend, const git_oid *oid)
{
	struct pack_entry e;
	int error;

	if ((error = pack_entry_find(&e, (struct pack_backend *)backend, oid)) < GIT_SUCCESS)
		return error;

	return packfile_unpack(obj, (struct pack_backend *)backend, e.p, e.offset);
}

int pack_backend__exists(git_odb_backend *backend, const git_oid *oid)
{
	struct pack_entry e;
	return pack_entry_find(&e, (struct pack_backend *)backend, oid) == GIT_SUCCESS;
}

void pack_backend__free(git_odb_backend *_backend)
{
	struct pack_backend *backend;
	size_t i;

	assert(_backend);

	backend = (struct pack_backend *)_backend;

	for (i = 0; i < backend->packs.length; ++i) {
		struct pack_file *p = git_vector_get(&backend->packs, i);
		packfile_free(backend, p);
	}

	git_vector_free(&backend->packs);
	free(backend);
}

int git_odb_backend_pack(git_odb_backend **backend_out, const char *objects_dir)
{
	int error;
	struct pack_backend *backend;

	backend = git__calloc(1, sizeof(struct pack_backend));
	if (backend == NULL)
		return GIT_ENOMEM;

	if (git_vector_init(&backend->packs, 8, packfile_sort__cb) < GIT_SUCCESS) {
		free(backend);
		return GIT_ENOMEM;
	}

	backend->window_size = DEFAULT_WINDOW_SIZE;
	backend->mapped_limit = DEFAULT_MAPPED_LIMIT;

	error = packfile_load_all(backend, objects_dir, 1);
	if (error < GIT_SUCCESS) {
		pack_backend__free((git_odb_backend *)backend);
		return error;
	}

	backend->parent.read = &pack_backend__read;
	backend->parent.read_header = NULL;
	backend->parent.write = NULL;
	backend->parent.exists = &pack_backend__exists;
	backend->parent.free = &pack_backend__free;

	*backend_out = (git_odb_backend *)backend;
	return GIT_SUCCESS;
}