Blame src/pack-objects.c

Packit Service 20376f
/*
Packit Service 20376f
 * Copyright (C) the libgit2 contributors. All rights reserved.
Packit Service 20376f
 *
Packit Service 20376f
 * This file is part of libgit2, distributed under the GNU GPL v2 with
Packit Service 20376f
 * a Linking Exception. For full terms see the included COPYING file.
Packit Service 20376f
 */
Packit Service 20376f
Packit Service 20376f
#include "pack-objects.h"
Packit Service 20376f
Packit Service 20376f
#include "zstream.h"
Packit Service 20376f
#include "delta.h"
Packit Service 20376f
#include "iterator.h"
Packit Service 20376f
#include "netops.h"
Packit Service 20376f
#include "pack.h"
Packit Service 20376f
#include "thread-utils.h"
Packit Service 20376f
#include "tree.h"
Packit Service 20376f
#include "util.h"
Packit Service 20376f
#include "revwalk.h"
Packit Service 20376f
#include "commit_list.h"
Packit Service 20376f
Packit Service 20376f
#include "git2/pack.h"
Packit Service 20376f
#include "git2/commit.h"
Packit Service 20376f
#include "git2/tag.h"
Packit Service 20376f
#include "git2/indexer.h"
Packit Service 20376f
#include "git2/config.h"
Packit Service 20376f
Packit Service 20376f
struct unpacked {
Packit Service 20376f
	git_pobject *object;
Packit Service 20376f
	void *data;
Packit Service 20376f
	struct git_delta_index *index;
Packit Service 20376f
	size_t depth;
Packit Service 20376f
};
Packit Service 20376f
Packit Service 20376f
struct tree_walk_context {
Packit Service 20376f
	git_packbuilder *pb;
Packit Service 20376f
	git_buf buf;
Packit Service 20376f
};
Packit Service 20376f
Packit Service 20376f
struct pack_write_context {
Packit Service 20376f
	git_indexer *indexer;
Packit Service 20376f
	git_transfer_progress *stats;
Packit Service 20376f
};
Packit Service 20376f
Packit Service 20376f
#ifdef GIT_THREADS
Packit Service 20376f
Packit Service 20376f
#define GIT_PACKBUILDER__MUTEX_OP(pb, mtx, op) do { \
Packit Service 20376f
		int result = git_mutex_##op(&(pb)->mtx); \
Packit Service 20376f
		assert(!result); \
Packit Service 20376f
		GIT_UNUSED(result); \
Packit Service 20376f
	} while (0)
Packit Service 20376f
Packit Service 20376f
#else
Packit Service 20376f
Packit Service 20376f
#define GIT_PACKBUILDER__MUTEX_OP(pb,mtx,op) GIT_UNUSED(pb)
Packit Service 20376f
Packit Service 20376f
#endif /* GIT_THREADS */
Packit Service 20376f
Packit Service 20376f
#define git_packbuilder__cache_lock(pb) GIT_PACKBUILDER__MUTEX_OP(pb, cache_mutex, lock)
Packit Service 20376f
#define git_packbuilder__cache_unlock(pb) GIT_PACKBUILDER__MUTEX_OP(pb, cache_mutex, unlock)
Packit Service 20376f
#define git_packbuilder__progress_lock(pb) GIT_PACKBUILDER__MUTEX_OP(pb, progress_mutex, lock)
Packit Service 20376f
#define git_packbuilder__progress_unlock(pb) GIT_PACKBUILDER__MUTEX_OP(pb, progress_mutex, unlock)
Packit Service 20376f
Packit Service 20376f
/* The minimal interval between progress updates (in seconds). */
Packit Service 20376f
#define MIN_PROGRESS_UPDATE_INTERVAL 0.5
Packit Service 20376f
Packit Service 20376f
/* Size of the buffer to feed to zlib */
Packit Service 20376f
#define COMPRESS_BUFLEN (1024 * 1024)
Packit Service 20376f
Packit Service 20376f
static unsigned name_hash(const char *name)
Packit Service 20376f
{
Packit Service 20376f
	unsigned c, hash = 0;
Packit Service 20376f
Packit Service 20376f
	if (!name)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * This effectively just creates a sortable number from the
Packit Service 20376f
	 * last sixteen non-whitespace characters. Last characters
Packit Service 20376f
	 * count "most", so things that end in ".c" sort together.
Packit Service 20376f
	 */
Packit Service 20376f
	while ((c = *name++) != 0) {
Packit Service 20376f
		if (git__isspace(c))
Packit Service 20376f
			continue;
Packit Service 20376f
		hash = (hash >> 2) + (c << 24);
Packit Service 20376f
	}
Packit Service 20376f
	return hash;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int packbuilder_config(git_packbuilder *pb)
Packit Service 20376f
{
Packit Service 20376f
	git_config *config;
Packit Service 20376f
	int ret = 0;
Packit Service 20376f
	int64_t val;
Packit Service 20376f
Packit Service 20376f
	if ((ret = git_repository_config_snapshot(&config, pb->repo)) < 0)
Packit Service 20376f
		return ret;
Packit Service 20376f
Packit Service 20376f
#define config_get(KEY,DST,DFLT) do { \
Packit Service 20376f
	ret = git_config_get_int64(&val, config, KEY); \
Packit Service 20376f
	if (!ret) { \
Packit Service 20376f
		if (!git__is_sizet(val)) { \
Packit Service 20376f
			giterr_set(GITERR_CONFIG, \
Packit Service 20376f
				"configuration value '%s' is too large", KEY); \
Packit Service 20376f
			ret = -1; \
Packit Service 20376f
			goto out; \
Packit Service 20376f
		} \
Packit Service 20376f
		(DST) = (size_t)val; \
Packit Service 20376f
	} else if (ret == GIT_ENOTFOUND) { \
Packit Service 20376f
	    (DST) = (DFLT); \
Packit Service 20376f
	    ret = 0; \
Packit Service 20376f
	} else if (ret < 0) goto out; } while (0)
Packit Service 20376f
Packit Service 20376f
	config_get("pack.deltaCacheSize", pb->max_delta_cache_size,
Packit Service 20376f
		   GIT_PACK_DELTA_CACHE_SIZE);
Packit Service 20376f
	config_get("pack.deltaCacheLimit", pb->cache_max_small_delta_size,
Packit Service 20376f
		   GIT_PACK_DELTA_CACHE_LIMIT);
Packit Service 20376f
	config_get("pack.deltaCacheSize", pb->big_file_threshold,
Packit Service 20376f
		   GIT_PACK_BIG_FILE_THRESHOLD);
Packit Service 20376f
	config_get("pack.windowMemory", pb->window_memory_limit, 0);
Packit Service 20376f
Packit Service 20376f
#undef config_get
Packit Service 20376f
Packit Service 20376f
out:
Packit Service 20376f
	git_config_free(config);
Packit Service 20376f
Packit Service 20376f
	return ret;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_packbuilder_new(git_packbuilder **out, git_repository *repo)
Packit Service 20376f
{
Packit Service 20376f
	git_packbuilder *pb;
Packit Service 20376f
Packit Service 20376f
	*out = NULL;
Packit Service 20376f
Packit Service 20376f
	pb = git__calloc(1, sizeof(*pb));
Packit Service 20376f
	GITERR_CHECK_ALLOC(pb);
Packit Service 20376f
Packit Service 20376f
	pb->object_ix = git_oidmap_alloc();
Packit Service 20376f
	if (!pb->object_ix)
Packit Service 20376f
		goto on_error;
Packit Service 20376f
Packit Service 20376f
	pb->walk_objects = git_oidmap_alloc();
Packit Service 20376f
	if (!pb->walk_objects)
Packit Service 20376f
		goto on_error;
Packit Service 20376f
Packit Service 20376f
	git_pool_init(&pb->object_pool, sizeof(git_walk_object));
Packit Service 20376f
Packit Service 20376f
	pb->repo = repo;
Packit Service 20376f
	pb->nr_threads = 1; /* do not spawn any thread by default */
Packit Service 20376f
Packit Service 20376f
	if (git_hash_ctx_init(&pb->ctx) < 0 ||
Packit Service 20376f
		git_zstream_init(&pb->zstream, GIT_ZSTREAM_DEFLATE) < 0 ||
Packit Service 20376f
		git_repository_odb(&pb->odb, repo) < 0 ||
Packit Service 20376f
		packbuilder_config(pb) < 0)
Packit Service 20376f
		goto on_error;
Packit Service 20376f
Packit Service 20376f
#ifdef GIT_THREADS
Packit Service 20376f
Packit Service 20376f
	if (git_mutex_init(&pb->cache_mutex) ||
Packit Service 20376f
		git_mutex_init(&pb->progress_mutex) ||
Packit Service 20376f
		git_cond_init(&pb->progress_cond))
Packit Service 20376f
	{
Packit Service 20376f
		giterr_set(GITERR_OS, "failed to initialize packbuilder mutex");
Packit Service 20376f
		goto on_error;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
#endif
Packit Service 20376f
Packit Service 20376f
	*out = pb;
Packit Service 20376f
	return 0;
Packit Service 20376f
Packit Service 20376f
on_error:
Packit Service 20376f
	git_packbuilder_free(pb);
Packit Service 20376f
	return -1;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
unsigned int git_packbuilder_set_threads(git_packbuilder *pb, unsigned int n)
Packit Service 20376f
{
Packit Service 20376f
	assert(pb);
Packit Service 20376f
Packit Service 20376f
#ifdef GIT_THREADS
Packit Service 20376f
	pb->nr_threads = n;
Packit Service 20376f
#else
Packit Service 20376f
	GIT_UNUSED(n);
Packit Service 20376f
	assert(1 == pb->nr_threads);
Packit Service 20376f
#endif
Packit Service 20376f
Packit Service 20376f
	return pb->nr_threads;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static void rehash(git_packbuilder *pb)
Packit Service 20376f
{
Packit Service 20376f
	git_pobject *po;
Packit Service 20376f
	khiter_t pos;
Packit Service 20376f
	size_t i;
Packit Service 20376f
	int ret;
Packit Service 20376f
Packit Service 20376f
	git_oidmap_clear(pb->object_ix);
Packit Service 20376f
	for (i = 0, po = pb->object_list; i < pb->nr_objects; i++, po++) {
Packit Service 20376f
		pos = git_oidmap_put(pb->object_ix, &po->id, &ret;;
Packit Service 20376f
		git_oidmap_set_value_at(pb->object_ix, pos, po);
Packit Service 20376f
	}
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_packbuilder_insert(git_packbuilder *pb, const git_oid *oid,
Packit Service 20376f
			   const char *name)
Packit Service 20376f
{
Packit Service 20376f
	git_pobject *po;
Packit Service 20376f
	khiter_t pos;
Packit Service 20376f
	size_t newsize;
Packit Service 20376f
	int ret;
Packit Service 20376f
Packit Service 20376f
	assert(pb && oid);
Packit Service 20376f
Packit Service 20376f
	/* If the object already exists in the hash table, then we don't
Packit Service 20376f
	 * have any work to do */
Packit Service 20376f
	if (git_oidmap_exists(pb->object_ix, oid))
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	if (pb->nr_objects >= pb->nr_alloc) {
Packit Service 20376f
		GITERR_CHECK_ALLOC_ADD(&newsize, pb->nr_alloc, 1024);
Packit Service 20376f
		GITERR_CHECK_ALLOC_MULTIPLY(&newsize, newsize, 3 / 2);
Packit Service 20376f
Packit Service 20376f
		if (!git__is_uint32(newsize)) {
Packit Service 20376f
			giterr_set(GITERR_NOMEMORY, "packfile too large to fit in memory.");
Packit Service 20376f
			return -1;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		pb->nr_alloc = newsize;
Packit Service 20376f
Packit Service 20376f
		pb->object_list = git__reallocarray(pb->object_list,
Packit Service 20376f
			pb->nr_alloc, sizeof(*po));
Packit Service 20376f
		GITERR_CHECK_ALLOC(pb->object_list);
Packit Service 20376f
		rehash(pb);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	po = pb->object_list + pb->nr_objects;
Packit Service 20376f
	memset(po, 0x0, sizeof(*po));
Packit Service 20376f
Packit Service 20376f
	if ((ret = git_odb_read_header(&po->size, &po->type, pb->odb, oid)) < 0)
Packit Service 20376f
		return ret;
Packit Service 20376f
Packit Service 20376f
	pb->nr_objects++;
Packit Service 20376f
	git_oid_cpy(&po->id, oid);
Packit Service 20376f
	po->hash = name_hash(name);
Packit Service 20376f
Packit Service 20376f
	pos = git_oidmap_put(pb->object_ix, &po->id, &ret;;
Packit Service 20376f
	if (ret < 0) {
Packit Service 20376f
		giterr_set_oom();
Packit Service 20376f
		return ret;
Packit Service 20376f
	}
Packit Service 20376f
	assert(ret != 0);
Packit Service 20376f
	git_oidmap_set_value_at(pb->object_ix, pos, po);
Packit Service 20376f
Packit Service 20376f
	pb->done = false;
Packit Service 20376f
Packit Service 20376f
	if (pb->progress_cb) {
Packit Service 20376f
		double current_time = git__timer();
Packit Service 20376f
		double elapsed = current_time - pb->last_progress_report_time;
Packit Service 20376f
Packit Service 20376f
		if (elapsed >= MIN_PROGRESS_UPDATE_INTERVAL) {
Packit Service 20376f
			pb->last_progress_report_time = current_time;
Packit Service 20376f
Packit Service 20376f
			ret = pb->progress_cb(
Packit Service 20376f
				GIT_PACKBUILDER_ADDING_OBJECTS,
Packit Service 20376f
				pb->nr_objects, 0, pb->progress_cb_payload);
Packit Service 20376f
Packit Service 20376f
			if (ret)
Packit Service 20376f
				return giterr_set_after_callback(ret);
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int get_delta(void **out, git_odb *odb, git_pobject *po)
Packit Service 20376f
{
Packit Service 20376f
	git_odb_object *src = NULL, *trg = NULL;
Packit Service 20376f
	size_t delta_size;
Packit Service 20376f
	void *delta_buf;
Packit Service 20376f
	int error;
Packit Service 20376f
Packit Service 20376f
	*out = NULL;
Packit Service 20376f
Packit Service 20376f
	if (git_odb_read(&src, odb, &po->delta->id) < 0 ||
Packit Service 20376f
	    git_odb_read(&trg, odb, &po->id) < 0)
Packit Service 20376f
		goto on_error;
Packit Service 20376f
Packit Service 20376f
	error = git_delta(&delta_buf, &delta_size,
Packit Service 20376f
		git_odb_object_data(src), git_odb_object_size(src),
Packit Service 20376f
		git_odb_object_data(trg), git_odb_object_size(trg),
Packit Service 20376f
		0);
Packit Service 20376f
Packit Service 20376f
	if (error < 0 && error != GIT_EBUFS)
Packit Service 20376f
		goto on_error;
Packit Service 20376f
Packit Service 20376f
	if (error == GIT_EBUFS || delta_size != po->delta_size) {
Packit Service 20376f
		giterr_set(GITERR_INVALID, "delta size changed");
Packit Service 20376f
		goto on_error;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	*out = delta_buf;
Packit Service 20376f
Packit Service 20376f
	git_odb_object_free(src);
Packit Service 20376f
	git_odb_object_free(trg);
Packit Service 20376f
	return 0;
Packit Service 20376f
Packit Service 20376f
on_error:
Packit Service 20376f
	git_odb_object_free(src);
Packit Service 20376f
	git_odb_object_free(trg);
Packit Service 20376f
	return -1;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int write_object(
Packit Service 20376f
	git_packbuilder *pb,
Packit Service 20376f
	git_pobject *po,
Packit Service 20376f
	int (*write_cb)(void *buf, size_t size, void *cb_data),
Packit Service 20376f
	void *cb_data)
Packit Service 20376f
{
Packit Service 20376f
	git_odb_object *obj = NULL;
Packit Service 20376f
	git_otype type;
Packit Service 20376f
	unsigned char hdr[10], *zbuf = NULL;
Packit Service 20376f
	void *data = NULL;
Packit Service 20376f
	size_t hdr_len, zbuf_len = COMPRESS_BUFLEN, data_len;
Packit Service 20376f
	int error;
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * If we have a delta base, let's use the delta to save space.
Packit Service 20376f
	 * Otherwise load the whole object. 'data' ends up pointing to
Packit Service 20376f
	 * whatever data we want to put into the packfile.
Packit Service 20376f
	 */
Packit Service 20376f
	if (po->delta) {
Packit Service 20376f
		if (po->delta_data)
Packit Service 20376f
			data = po->delta_data;
Packit Service 20376f
		else if ((error = get_delta(&data, pb->odb, po)) < 0)
Packit Service 20376f
				goto done;
Packit Service 20376f
Packit Service 20376f
		data_len = po->delta_size;
Packit Service 20376f
		type = GIT_OBJ_REF_DELTA;
Packit Service 20376f
	} else {
Packit Service 20376f
		if ((error = git_odb_read(&obj, pb->odb, &po->id)) < 0)
Packit Service 20376f
			goto done;
Packit Service 20376f
Packit Service 20376f
		data = (void *)git_odb_object_data(obj);
Packit Service 20376f
		data_len = git_odb_object_size(obj);
Packit Service 20376f
		type = git_odb_object_type(obj);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* Write header */
Packit Service 20376f
	hdr_len = git_packfile__object_header(hdr, data_len, type);
Packit Service 20376f
Packit Service 20376f
	if ((error = write_cb(hdr, hdr_len, cb_data)) < 0 ||
Packit Service 20376f
		(error = git_hash_update(&pb->ctx, hdr, hdr_len)) < 0)
Packit Service 20376f
		goto done;
Packit Service 20376f
Packit Service 20376f
	if (type == GIT_OBJ_REF_DELTA) {
Packit Service 20376f
		if ((error = write_cb(po->delta->id.id, GIT_OID_RAWSZ, cb_data)) < 0 ||
Packit Service 20376f
			(error = git_hash_update(&pb->ctx, po->delta->id.id, GIT_OID_RAWSZ)) < 0)
Packit Service 20376f
			goto done;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* Write data */
Packit Service 20376f
	if (po->z_delta_size) {
Packit Service 20376f
		data_len = po->z_delta_size;
Packit Service 20376f
Packit Service 20376f
		if ((error = write_cb(data, data_len, cb_data)) < 0 ||
Packit Service 20376f
			(error = git_hash_update(&pb->ctx, data, data_len)) < 0)
Packit Service 20376f
			goto done;
Packit Service 20376f
	} else {
Packit Service 20376f
		zbuf = git__malloc(zbuf_len);
Packit Service 20376f
		GITERR_CHECK_ALLOC(zbuf);
Packit Service 20376f
Packit Service 20376f
		git_zstream_reset(&pb->zstream);
Packit Service 20376f
		git_zstream_set_input(&pb->zstream, data, data_len);
Packit Service 20376f
Packit Service 20376f
		while (!git_zstream_done(&pb->zstream)) {
Packit Service 20376f
			if ((error = git_zstream_get_output(zbuf, &zbuf_len, &pb->zstream)) < 0 ||
Packit Service 20376f
				(error = write_cb(zbuf, zbuf_len, cb_data)) < 0 ||
Packit Service 20376f
				(error = git_hash_update(&pb->ctx, zbuf, zbuf_len)) < 0)
Packit Service 20376f
				goto done;
Packit Service 20376f
Packit Service 20376f
			zbuf_len = COMPRESS_BUFLEN; /* reuse buffer */
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * If po->delta is true, data is a delta and it is our
Packit Service 20376f
	 * responsibility to free it (otherwise it's a git_object's
Packit Service 20376f
	 * data). We set po->delta_data to NULL in case we got the
Packit Service 20376f
	 * data from there instead of get_delta(). If we didn't,
Packit Service 20376f
	 * there's no harm.
Packit Service 20376f
	 */
Packit Service 20376f
	if (po->delta) {
Packit Service 20376f
		git__free(data);
Packit Service 20376f
		po->delta_data = NULL;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	pb->nr_written++;
Packit Service 20376f
Packit Service 20376f
done:
Packit Service 20376f
	git__free(zbuf);
Packit Service 20376f
	git_odb_object_free(obj);
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
enum write_one_status {
Packit Service 20376f
	WRITE_ONE_SKIP = -1, /* already written */
Packit Service 20376f
	WRITE_ONE_BREAK = 0, /* writing this will bust the limit; not written */
Packit Service 20376f
	WRITE_ONE_WRITTEN = 1, /* normal */
Packit Service 20376f
	WRITE_ONE_RECURSIVE = 2 /* already scheduled to be written */
Packit Service 20376f
};
Packit Service 20376f
Packit Service 20376f
static int write_one(
Packit Service 20376f
	enum write_one_status *status,
Packit Service 20376f
	git_packbuilder *pb,
Packit Service 20376f
	git_pobject *po,
Packit Service 20376f
	int (*write_cb)(void *buf, size_t size, void *cb_data),
Packit Service 20376f
	void *cb_data)
Packit Service 20376f
{
Packit Service 20376f
	int error;
Packit Service 20376f
Packit Service 20376f
	if (po->recursing) {
Packit Service 20376f
		*status = WRITE_ONE_RECURSIVE;
Packit Service 20376f
		return 0;
Packit Service 20376f
	} else if (po->written) {
Packit Service 20376f
		*status = WRITE_ONE_SKIP;
Packit Service 20376f
		return 0;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (po->delta) {
Packit Service 20376f
		po->recursing = 1;
Packit Service 20376f
Packit Service 20376f
		if ((error = write_one(status, pb, po->delta, write_cb, cb_data)) < 0)
Packit Service 20376f
			return error;
Packit Service 20376f
Packit Service 20376f
		/* we cannot depend on this one */
Packit Service 20376f
		if (*status == WRITE_ONE_RECURSIVE)
Packit Service 20376f
			po->delta = NULL;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	*status = WRITE_ONE_WRITTEN;
Packit Service 20376f
	po->written = 1;
Packit Service 20376f
	po->recursing = 0;
Packit Service 20376f
Packit Service 20376f
	return write_object(pb, po, write_cb, cb_data);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
GIT_INLINE(void) add_to_write_order(git_pobject **wo, size_t *endp,
Packit Service 20376f
	git_pobject *po)
Packit Service 20376f
{
Packit Service 20376f
	if (po->filled)
Packit Service 20376f
		return;
Packit Service 20376f
	wo[(*endp)++] = po;
Packit Service 20376f
	po->filled = 1;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static void add_descendants_to_write_order(git_pobject **wo, size_t *endp,
Packit Service 20376f
	git_pobject *po)
Packit Service 20376f
{
Packit Service 20376f
	int add_to_order = 1;
Packit Service 20376f
	while (po) {
Packit Service 20376f
		if (add_to_order) {
Packit Service 20376f
			git_pobject *s;
Packit Service 20376f
			/* add this node... */
Packit Service 20376f
			add_to_write_order(wo, endp, po);
Packit Service 20376f
			/* all its siblings... */
Packit Service 20376f
			for (s = po->delta_sibling; s; s = s->delta_sibling) {
Packit Service 20376f
				add_to_write_order(wo, endp, s);
Packit Service 20376f
			}
Packit Service 20376f
		}
Packit Service 20376f
		/* drop down a level to add left subtree nodes if possible */
Packit Service 20376f
		if (po->delta_child) {
Packit Service 20376f
			add_to_order = 1;
Packit Service 20376f
			po = po->delta_child;
Packit Service 20376f
		} else {
Packit Service 20376f
			add_to_order = 0;
Packit Service 20376f
			/* our sibling might have some children, it is next */
Packit Service 20376f
			if (po->delta_sibling) {
Packit Service 20376f
				po = po->delta_sibling;
Packit Service 20376f
				continue;
Packit Service 20376f
			}
Packit Service 20376f
			/* go back to our parent node */
Packit Service 20376f
			po = po->delta;
Packit Service 20376f
			while (po && !po->delta_sibling) {
Packit Service 20376f
				/* we're on the right side of a subtree, keep
Packit Service 20376f
				 * going up until we can go right again */
Packit Service 20376f
				po = po->delta;
Packit Service 20376f
			}
Packit Service 20376f
			if (!po) {
Packit Service 20376f
				/* done- we hit our original root node */
Packit Service 20376f
				return;
Packit Service 20376f
			}
Packit Service 20376f
			/* pass it off to sibling at this level */
Packit Service 20376f
			po = po->delta_sibling;
Packit Service 20376f
		}
Packit Service 20376f
	};
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static void add_family_to_write_order(git_pobject **wo, size_t *endp,
Packit Service 20376f
	git_pobject *po)
Packit Service 20376f
{
Packit Service 20376f
	git_pobject *root;
Packit Service 20376f
Packit Service 20376f
	for (root = po; root->delta; root = root->delta)
Packit Service 20376f
		; /* nothing */
Packit Service 20376f
	add_descendants_to_write_order(wo, endp, root);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int cb_tag_foreach(const char *name, git_oid *oid, void *data)
Packit Service 20376f
{
Packit Service 20376f
	git_packbuilder *pb = data;
Packit Service 20376f
	git_pobject *po;
Packit Service 20376f
	khiter_t pos;
Packit Service 20376f
Packit Service 20376f
	GIT_UNUSED(name);
Packit Service 20376f
Packit Service 20376f
	pos = git_oidmap_lookup_index(pb->object_ix, oid);
Packit Service 20376f
	if (!git_oidmap_valid_index(pb->object_ix, pos))
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	po = git_oidmap_value_at(pb->object_ix, pos);
Packit Service 20376f
	po->tagged = 1;
Packit Service 20376f
Packit Service 20376f
	/* TODO: peel objects */
Packit Service 20376f
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static git_pobject **compute_write_order(git_packbuilder *pb)
Packit Service 20376f
{
Packit Service 20376f
	size_t i, wo_end, last_untagged;
Packit Service 20376f
	git_pobject **wo;
Packit Service 20376f
Packit Service 20376f
	if ((wo = git__mallocarray(pb->nr_objects, sizeof(*wo))) == NULL)
Packit Service 20376f
		return NULL;
Packit Service 20376f
Packit Service 20376f
	for (i = 0; i < pb->nr_objects; i++) {
Packit Service 20376f
		git_pobject *po = pb->object_list + i;
Packit Service 20376f
		po->tagged = 0;
Packit Service 20376f
		po->filled = 0;
Packit Service 20376f
		po->delta_child = NULL;
Packit Service 20376f
		po->delta_sibling = NULL;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * Fully connect delta_child/delta_sibling network.
Packit Service 20376f
	 * Make sure delta_sibling is sorted in the original
Packit Service 20376f
	 * recency order.
Packit Service 20376f
	 */
Packit Service 20376f
	for (i = pb->nr_objects; i > 0;) {
Packit Service 20376f
		git_pobject *po = &pb->object_list[--i];
Packit Service 20376f
		if (!po->delta)
Packit Service 20376f
			continue;
Packit Service 20376f
		/* Mark me as the first child */
Packit Service 20376f
		po->delta_sibling = po->delta->delta_child;
Packit Service 20376f
		po->delta->delta_child = po;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * Mark objects that are at the tip of tags.
Packit Service 20376f
	 */
Packit Service 20376f
	if (git_tag_foreach(pb->repo, &cb_tag_foreach, pb) < 0) {
Packit Service 20376f
		git__free(wo);
Packit Service 20376f
		return NULL;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * Give the objects in the original recency order until
Packit Service 20376f
	 * we see a tagged tip.
Packit Service 20376f
	 */
Packit Service 20376f
	for (i = wo_end = 0; i < pb->nr_objects; i++) {
Packit Service 20376f
		git_pobject *po = pb->object_list + i;
Packit Service 20376f
		if (po->tagged)
Packit Service 20376f
			break;
Packit Service 20376f
		add_to_write_order(wo, &wo_end, po);
Packit Service 20376f
	}
Packit Service 20376f
	last_untagged = i;
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * Then fill all the tagged tips.
Packit Service 20376f
	 */
Packit Service 20376f
	for (; i < pb->nr_objects; i++) {
Packit Service 20376f
		git_pobject *po = pb->object_list + i;
Packit Service 20376f
		if (po->tagged)
Packit Service 20376f
			add_to_write_order(wo, &wo_end, po);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * And then all remaining commits and tags.
Packit Service 20376f
	 */
Packit Service 20376f
	for (i = last_untagged; i < pb->nr_objects; i++) {
Packit Service 20376f
		git_pobject *po = pb->object_list + i;
Packit Service 20376f
		if (po->type != GIT_OBJ_COMMIT &&
Packit Service 20376f
		    po->type != GIT_OBJ_TAG)
Packit Service 20376f
			continue;
Packit Service 20376f
		add_to_write_order(wo, &wo_end, po);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * And then all the trees.
Packit Service 20376f
	 */
Packit Service 20376f
	for (i = last_untagged; i < pb->nr_objects; i++) {
Packit Service 20376f
		git_pobject *po = pb->object_list + i;
Packit Service 20376f
		if (po->type != GIT_OBJ_TREE)
Packit Service 20376f
			continue;
Packit Service 20376f
		add_to_write_order(wo, &wo_end, po);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * Finally all the rest in really tight order
Packit Service 20376f
	 */
Packit Service 20376f
	for (i = last_untagged; i < pb->nr_objects; i++) {
Packit Service 20376f
		git_pobject *po = pb->object_list + i;
Packit Service 20376f
		if (!po->filled)
Packit Service 20376f
			add_family_to_write_order(wo, &wo_end, po);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (wo_end != pb->nr_objects) {
Packit Service 20376f
		git__free(wo);
Packit Service 20376f
		giterr_set(GITERR_INVALID, "invalid write order");
Packit Service 20376f
		return NULL;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	return wo;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int write_pack(git_packbuilder *pb,
Packit Service 20376f
	int (*write_cb)(void *buf, size_t size, void *cb_data),
Packit Service 20376f
	void *cb_data)
Packit Service 20376f
{
Packit Service 20376f
	git_pobject **write_order;
Packit Service 20376f
	git_pobject *po;
Packit Service 20376f
	enum write_one_status status;
Packit Service 20376f
	struct git_pack_header ph;
Packit Service 20376f
	git_oid entry_oid;
Packit Service 20376f
	size_t i = 0;
Packit Service 20376f
	int error = 0;
Packit Service 20376f
Packit Service 20376f
	write_order = compute_write_order(pb);
Packit Service 20376f
	if (write_order == NULL)
Packit Service 20376f
		return -1;
Packit Service 20376f
Packit Service 20376f
	if (!git__is_uint32(pb->nr_objects)) {
Packit Service 20376f
		giterr_set(GITERR_INVALID, "too many objects");
Packit Service 20376f
		return -1;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* Write pack header */
Packit Service 20376f
	ph.hdr_signature = htonl(PACK_SIGNATURE);
Packit Service 20376f
	ph.hdr_version = htonl(PACK_VERSION);
Packit Service 20376f
	ph.hdr_entries = htonl(pb->nr_objects);
Packit Service 20376f
Packit Service 20376f
	if ((error = write_cb(&ph, sizeof(ph), cb_data)) < 0 ||
Packit Service 20376f
		(error = git_hash_update(&pb->ctx, &ph, sizeof(ph))) < 0)
Packit Service 20376f
		goto done;
Packit Service 20376f
Packit Service 20376f
	pb->nr_remaining = pb->nr_objects;
Packit Service 20376f
	do {
Packit Service 20376f
		pb->nr_written = 0;
Packit Service 20376f
		for ( ; i < pb->nr_objects; ++i) {
Packit Service 20376f
			po = write_order[i];
Packit Service 20376f
Packit Service 20376f
			if ((error = write_one(&status, pb, po, write_cb, cb_data)) < 0)
Packit Service 20376f
				goto done;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		pb->nr_remaining -= pb->nr_written;
Packit Service 20376f
	} while (pb->nr_remaining && i < pb->nr_objects);
Packit Service 20376f
Packit Service 20376f
	if ((error = git_hash_final(&entry_oid, &pb->ctx)) < 0)
Packit Service 20376f
		goto done;
Packit Service 20376f
Packit Service 20376f
	error = write_cb(entry_oid.id, GIT_OID_RAWSZ, cb_data);
Packit Service 20376f
Packit Service 20376f
done:
Packit Service 20376f
	/* if callback cancelled writing, we must still free delta_data */
Packit Service 20376f
	for ( ; i < pb->nr_objects; ++i) {
Packit Service 20376f
		po = write_order[i];
Packit Service 20376f
		if (po->delta_data) {
Packit Service 20376f
			git__free(po->delta_data);
Packit Service 20376f
			po->delta_data = NULL;
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	git__free(write_order);
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int write_pack_buf(void *buf, size_t size, void *data)
Packit Service 20376f
{
Packit Service 20376f
	git_buf *b = (git_buf *)data;
Packit Service 20376f
	return git_buf_put(b, buf, size);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int type_size_sort(const void *_a, const void *_b)
Packit Service 20376f
{
Packit Service 20376f
	const git_pobject *a = (git_pobject *)_a;
Packit Service 20376f
	const git_pobject *b = (git_pobject *)_b;
Packit Service 20376f
Packit Service 20376f
	if (a->type > b->type)
Packit Service 20376f
		return -1;
Packit Service 20376f
	if (a->type < b->type)
Packit Service 20376f
		return 1;
Packit Service 20376f
	if (a->hash > b->hash)
Packit Service 20376f
		return -1;
Packit Service 20376f
	if (a->hash < b->hash)
Packit Service 20376f
		return 1;
Packit Service 20376f
	/*
Packit Service 20376f
	 * TODO
Packit Service 20376f
	 *
Packit Service 20376f
	if (a->preferred_base > b->preferred_base)
Packit Service 20376f
		return -1;
Packit Service 20376f
	if (a->preferred_base < b->preferred_base)
Packit Service 20376f
		return 1;
Packit Service 20376f
	*/
Packit Service 20376f
	if (a->size > b->size)
Packit Service 20376f
		return -1;
Packit Service 20376f
	if (a->size < b->size)
Packit Service 20376f
		return 1;
Packit Service 20376f
	return a < b ? -1 : (a > b); /* newest first */
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int delta_cacheable(
Packit Service 20376f
	git_packbuilder *pb,
Packit Service 20376f
	size_t src_size,
Packit Service 20376f
	size_t trg_size,
Packit Service 20376f
	size_t delta_size)
Packit Service 20376f
{
Packit Service 20376f
	size_t new_size;
Packit Service 20376f
Packit Service 20376f
	if (git__add_sizet_overflow(&new_size, pb->delta_cache_size, delta_size))
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	if (pb->max_delta_cache_size && new_size > pb->max_delta_cache_size)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	if (delta_size < pb->cache_max_small_delta_size)
Packit Service 20376f
		return 1;
Packit Service 20376f
Packit Service 20376f
	/* cache delta, if objects are large enough compared to delta size */
Packit Service 20376f
	if ((src_size >> 20) + (trg_size >> 21) > (delta_size >> 10))
Packit Service 20376f
		return 1;
Packit Service 20376f
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int try_delta(git_packbuilder *pb, struct unpacked *trg,
Packit Service 20376f
		     struct unpacked *src, size_t max_depth,
Packit Service 20376f
			 size_t *mem_usage, int *ret)
Packit Service 20376f
{
Packit Service 20376f
	git_pobject *trg_object = trg->object;
Packit Service 20376f
	git_pobject *src_object = src->object;
Packit Service 20376f
	git_odb_object *obj;
Packit Service 20376f
	size_t trg_size, src_size, delta_size, sizediff, max_size, sz;
Packit Service 20376f
	size_t ref_depth;
Packit Service 20376f
	void *delta_buf;
Packit Service 20376f
Packit Service 20376f
	/* Don't bother doing diffs between different types */
Packit Service 20376f
	if (trg_object->type != src_object->type) {
Packit Service 20376f
		*ret = -1;
Packit Service 20376f
		return 0;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	*ret = 0;
Packit Service 20376f
Packit Service 20376f
	/* TODO: support reuse-delta */
Packit Service 20376f
Packit Service 20376f
	/* Let's not bust the allowed depth. */
Packit Service 20376f
	if (src->depth >= max_depth)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	/* Now some size filtering heuristics. */
Packit Service 20376f
	trg_size = trg_object->size;
Packit Service 20376f
	if (!trg_object->delta) {
Packit Service 20376f
		max_size = trg_size/2 - 20;
Packit Service 20376f
		ref_depth = 1;
Packit Service 20376f
	} else {
Packit Service 20376f
		max_size = trg_object->delta_size;
Packit Service 20376f
		ref_depth = trg->depth;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	max_size = (uint64_t)max_size * (max_depth - src->depth) /
Packit Service 20376f
					(max_depth - ref_depth + 1);
Packit Service 20376f
	if (max_size == 0)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	src_size = src_object->size;
Packit Service 20376f
	sizediff = src_size < trg_size ? trg_size - src_size : 0;
Packit Service 20376f
	if (sizediff >= max_size)
Packit Service 20376f
		return 0;
Packit Service 20376f
	if (trg_size < src_size / 32)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	/* Load data if not already done */
Packit Service 20376f
	if (!trg->data) {
Packit Service 20376f
		if (git_odb_read(&obj, pb->odb, &trg_object->id) < 0)
Packit Service 20376f
			return -1;
Packit Service 20376f
Packit Service 20376f
		sz = git_odb_object_size(obj);
Packit Service 20376f
		trg->data = git__malloc(sz);
Packit Service 20376f
		GITERR_CHECK_ALLOC(trg->data);
Packit Service 20376f
		memcpy(trg->data, git_odb_object_data(obj), sz);
Packit Service 20376f
Packit Service 20376f
		git_odb_object_free(obj);
Packit Service 20376f
Packit Service 20376f
		if (sz != trg_size) {
Packit Service 20376f
			giterr_set(GITERR_INVALID,
Packit Service 20376f
				   "inconsistent target object length");
Packit Service 20376f
			return -1;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		*mem_usage += sz;
Packit Service 20376f
	}
Packit Service 20376f
	if (!src->data) {
Packit Service 20376f
		size_t obj_sz;
Packit Service 20376f
Packit Service 20376f
		if (git_odb_read(&obj, pb->odb, &src_object->id) < 0 ||
Packit Service 20376f
			!git__is_ulong(obj_sz = git_odb_object_size(obj)))
Packit Service 20376f
			return -1;
Packit Service 20376f
Packit Service 20376f
		sz = obj_sz;
Packit Service 20376f
		src->data = git__malloc(sz);
Packit Service 20376f
		GITERR_CHECK_ALLOC(src->data);
Packit Service 20376f
		memcpy(src->data, git_odb_object_data(obj), sz);
Packit Service 20376f
Packit Service 20376f
		git_odb_object_free(obj);
Packit Service 20376f
Packit Service 20376f
		if (sz != src_size) {
Packit Service 20376f
			giterr_set(GITERR_INVALID,
Packit Service 20376f
				   "inconsistent source object length");
Packit Service 20376f
			return -1;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		*mem_usage += sz;
Packit Service 20376f
	}
Packit Service 20376f
	if (!src->index) {
Packit Service 20376f
		if (git_delta_index_init(&src->index, src->data, src_size) < 0)
Packit Service 20376f
			return 0; /* suboptimal pack - out of memory */
Packit Service 20376f
Packit Service 20376f
		*mem_usage += git_delta_index_size(src->index);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (git_delta_create_from_index(&delta_buf, &delta_size, src->index, trg->data, trg_size,
Packit Service 20376f
		max_size) < 0)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	if (trg_object->delta) {
Packit Service 20376f
		/* Prefer only shallower same-sized deltas. */
Packit Service 20376f
		if (delta_size == trg_object->delta_size &&
Packit Service 20376f
		    src->depth + 1 >= trg->depth) {
Packit Service 20376f
			git__free(delta_buf);
Packit Service 20376f
			return 0;
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	git_packbuilder__cache_lock(pb);
Packit Service 20376f
	if (trg_object->delta_data) {
Packit Service 20376f
		git__free(trg_object->delta_data);
Packit Service 20376f
		assert(pb->delta_cache_size >= trg_object->delta_size);
Packit Service 20376f
		pb->delta_cache_size -= trg_object->delta_size;
Packit Service 20376f
		trg_object->delta_data = NULL;
Packit Service 20376f
	}
Packit Service 20376f
	if (delta_cacheable(pb, src_size, trg_size, delta_size)) {
Packit Service 20376f
		bool overflow = git__add_sizet_overflow(
Packit Service 20376f
			&pb->delta_cache_size, pb->delta_cache_size, delta_size);
Packit Service 20376f
Packit Service 20376f
		git_packbuilder__cache_unlock(pb);
Packit Service 20376f
Packit Service 20376f
		if (overflow) {
Packit Service 20376f
			git__free(delta_buf);
Packit Service 20376f
			return -1;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		trg_object->delta_data = git__realloc(delta_buf, delta_size);
Packit Service 20376f
		GITERR_CHECK_ALLOC(trg_object->delta_data);
Packit Service 20376f
	} else {
Packit Service 20376f
		/* create delta when writing the pack */
Packit Service 20376f
		git_packbuilder__cache_unlock(pb);
Packit Service 20376f
		git__free(delta_buf);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	trg_object->delta = src_object;
Packit Service 20376f
	trg_object->delta_size = delta_size;
Packit Service 20376f
	trg->depth = src->depth + 1;
Packit Service 20376f
Packit Service 20376f
	*ret = 1;
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static size_t check_delta_limit(git_pobject *me, size_t n)
Packit Service 20376f
{
Packit Service 20376f
	git_pobject *child = me->delta_child;
Packit Service 20376f
	size_t m = n;
Packit Service 20376f
Packit Service 20376f
	while (child) {
Packit Service 20376f
		size_t c = check_delta_limit(child, n + 1);
Packit Service 20376f
		if (m < c)
Packit Service 20376f
			m = c;
Packit Service 20376f
		child = child->delta_sibling;
Packit Service 20376f
	}
Packit Service 20376f
	return m;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static size_t free_unpacked(struct unpacked *n)
Packit Service 20376f
{
Packit Service 20376f
	size_t freed_mem = 0;
Packit Service 20376f
Packit Service 20376f
	if (n->index) {
Packit Service 20376f
		freed_mem += git_delta_index_size(n->index);
Packit Service 20376f
		git_delta_index_free(n->index);
Packit Service 20376f
	}
Packit Service 20376f
	n->index = NULL;
Packit Service 20376f
Packit Service 20376f
	if (n->data) {
Packit Service 20376f
		freed_mem += n->object->size;
Packit Service 20376f
		git__free(n->data);
Packit Service 20376f
		n->data = NULL;
Packit Service 20376f
	}
Packit Service 20376f
	n->object = NULL;
Packit Service 20376f
	n->depth = 0;
Packit Service 20376f
	return freed_mem;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int report_delta_progress(
Packit Service 20376f
	git_packbuilder *pb, uint32_t count, bool force)
Packit Service 20376f
{
Packit Service 20376f
	int ret;
Packit Service 20376f
Packit Service 20376f
	if (pb->progress_cb) {
Packit Service 20376f
		double current_time = git__timer();
Packit Service 20376f
		double elapsed = current_time - pb->last_progress_report_time;
Packit Service 20376f
Packit Service 20376f
		if (force || elapsed >= MIN_PROGRESS_UPDATE_INTERVAL) {
Packit Service 20376f
			pb->last_progress_report_time = current_time;
Packit Service 20376f
Packit Service 20376f
			ret = pb->progress_cb(
Packit Service 20376f
				GIT_PACKBUILDER_DELTAFICATION,
Packit Service 20376f
				count, pb->nr_objects, pb->progress_cb_payload);
Packit Service 20376f
Packit Service 20376f
			if (ret)
Packit Service 20376f
				return giterr_set_after_callback(ret);
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int find_deltas(git_packbuilder *pb, git_pobject **list,
Packit Service 20376f
	size_t *list_size, size_t window, size_t depth)
Packit Service 20376f
{
Packit Service 20376f
	git_pobject *po;
Packit Service 20376f
	git_buf zbuf = GIT_BUF_INIT;
Packit Service 20376f
	struct unpacked *array;
Packit Service 20376f
	size_t idx = 0, count = 0;
Packit Service 20376f
	size_t mem_usage = 0;
Packit Service 20376f
	size_t i;
Packit Service 20376f
	int error = -1;
Packit Service 20376f
Packit Service 20376f
	array = git__calloc(window, sizeof(struct unpacked));
Packit Service 20376f
	GITERR_CHECK_ALLOC(array);
Packit Service 20376f
Packit Service 20376f
	for (;;) {
Packit Service 20376f
		struct unpacked *n = array + idx;
Packit Service 20376f
		size_t max_depth, j, best_base = SIZE_MAX;
Packit Service 20376f
Packit Service 20376f
		git_packbuilder__progress_lock(pb);
Packit Service 20376f
		if (!*list_size) {
Packit Service 20376f
			git_packbuilder__progress_unlock(pb);
Packit Service 20376f
			break;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		pb->nr_deltified += 1;
Packit Service 20376f
		report_delta_progress(pb, pb->nr_deltified, false);
Packit Service 20376f
Packit Service 20376f
		po = *list++;
Packit Service 20376f
		(*list_size)--;
Packit Service 20376f
		git_packbuilder__progress_unlock(pb);
Packit Service 20376f
Packit Service 20376f
		mem_usage -= free_unpacked(n);
Packit Service 20376f
		n->object = po;
Packit Service 20376f
Packit Service 20376f
		while (pb->window_memory_limit &&
Packit Service 20376f
		       mem_usage > pb->window_memory_limit &&
Packit Service 20376f
		       count > 1) {
Packit Service 20376f
			size_t tail = (idx + window - count) % window;
Packit Service 20376f
			mem_usage -= free_unpacked(array + tail);
Packit Service 20376f
			count--;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		/*
Packit Service 20376f
		 * If the current object is at pack edge, take the depth the
Packit Service 20376f
		 * objects that depend on the current object into account
Packit Service 20376f
		 * otherwise they would become too deep.
Packit Service 20376f
		 */
Packit Service 20376f
		max_depth = depth;
Packit Service 20376f
		if (po->delta_child) {
Packit Service 20376f
			size_t delta_limit = check_delta_limit(po, 0);
Packit Service 20376f
Packit Service 20376f
			if (delta_limit > max_depth)
Packit Service 20376f
				goto next;
Packit Service 20376f
Packit Service 20376f
			max_depth -= delta_limit;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		j = window;
Packit Service 20376f
		while (--j > 0) {
Packit Service 20376f
			int ret;
Packit Service 20376f
			size_t other_idx = idx + j;
Packit Service 20376f
			struct unpacked *m;
Packit Service 20376f
Packit Service 20376f
			if (other_idx >= window)
Packit Service 20376f
				other_idx -= window;
Packit Service 20376f
Packit Service 20376f
			m = array + other_idx;
Packit Service 20376f
			if (!m->object)
Packit Service 20376f
				break;
Packit Service 20376f
Packit Service 20376f
			if (try_delta(pb, n, m, max_depth, &mem_usage, &ret) < 0)
Packit Service 20376f
				goto on_error;
Packit Service 20376f
			if (ret < 0)
Packit Service 20376f
				break;
Packit Service 20376f
			else if (ret > 0)
Packit Service 20376f
				best_base = other_idx;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		/*
Packit Service 20376f
		 * If we decided to cache the delta data, then it is best
Packit Service 20376f
		 * to compress it right away.  First because we have to do
Packit Service 20376f
		 * it anyway, and doing it here while we're threaded will
Packit Service 20376f
		 * save a lot of time in the non threaded write phase,
Packit Service 20376f
		 * as well as allow for caching more deltas within
Packit Service 20376f
		 * the same cache size limit.
Packit Service 20376f
		 * ...
Packit Service 20376f
		 * But only if not writing to stdout, since in that case
Packit Service 20376f
		 * the network is most likely throttling writes anyway,
Packit Service 20376f
		 * and therefore it is best to go to the write phase ASAP
Packit Service 20376f
		 * instead, as we can afford spending more time compressing
Packit Service 20376f
		 * between writes at that moment.
Packit Service 20376f
		 */
Packit Service 20376f
		if (po->delta_data) {
Packit Service 20376f
			if (git_zstream_deflatebuf(&zbuf, po->delta_data, po->delta_size) < 0)
Packit Service 20376f
				goto on_error;
Packit Service 20376f
Packit Service 20376f
			git__free(po->delta_data);
Packit Service 20376f
			po->delta_data = git__malloc(zbuf.size);
Packit Service 20376f
			GITERR_CHECK_ALLOC(po->delta_data);
Packit Service 20376f
Packit Service 20376f
			memcpy(po->delta_data, zbuf.ptr, zbuf.size);
Packit Service 20376f
			po->z_delta_size = zbuf.size;
Packit Service 20376f
			git_buf_clear(&zbuf);
Packit Service 20376f
Packit Service 20376f
			git_packbuilder__cache_lock(pb);
Packit Service 20376f
			pb->delta_cache_size -= po->delta_size;
Packit Service 20376f
			pb->delta_cache_size += po->z_delta_size;
Packit Service 20376f
			git_packbuilder__cache_unlock(pb);
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		/*
Packit Service 20376f
		 * If we made n a delta, and if n is already at max
Packit Service 20376f
		 * depth, leaving it in the window is pointless.  we
Packit Service 20376f
		 * should evict it first.
Packit Service 20376f
		 */
Packit Service 20376f
		if (po->delta && max_depth <= n->depth)
Packit Service 20376f
			continue;
Packit Service 20376f
Packit Service 20376f
		/*
Packit Service 20376f
		 * Move the best delta base up in the window, after the
Packit Service 20376f
		 * currently deltified object, to keep it longer.  It will
Packit Service 20376f
		 * be the first base object to be attempted next.
Packit Service 20376f
		 */
Packit Service 20376f
		if (po->delta) {
Packit Service 20376f
			struct unpacked swap = array[best_base];
Packit Service 20376f
			size_t dist = (window + idx - best_base) % window;
Packit Service 20376f
			size_t dst = best_base;
Packit Service 20376f
			while (dist--) {
Packit Service 20376f
				size_t src = (dst + 1) % window;
Packit Service 20376f
				array[dst] = array[src];
Packit Service 20376f
				dst = src;
Packit Service 20376f
			}
Packit Service 20376f
			array[dst] = swap;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		next:
Packit Service 20376f
		idx++;
Packit Service 20376f
		if (count + 1 < window)
Packit Service 20376f
			count++;
Packit Service 20376f
		if (idx >= window)
Packit Service 20376f
			idx = 0;
Packit Service 20376f
	}
Packit Service 20376f
	error = 0;
Packit Service 20376f
Packit Service 20376f
on_error:
Packit Service 20376f
	for (i = 0; i < window; ++i) {
Packit Service 20376f
		git__free(array[i].index);
Packit Service 20376f
		git__free(array[i].data);
Packit Service 20376f
	}
Packit Service 20376f
	git__free(array);
Packit Service 20376f
	git_buf_free(&zbuf);
Packit Service 20376f
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
#ifdef GIT_THREADS
Packit Service 20376f
Packit Service 20376f
struct thread_params {
Packit Service 20376f
	git_thread thread;
Packit Service 20376f
	git_packbuilder *pb;
Packit Service 20376f
Packit Service 20376f
	git_pobject **list;
Packit Service 20376f
Packit Service 20376f
	git_cond cond;
Packit Service 20376f
	git_mutex mutex;
Packit Service 20376f
Packit Service 20376f
	size_t list_size;
Packit Service 20376f
	size_t remaining;
Packit Service 20376f
Packit Service 20376f
	size_t window;
Packit Service 20376f
	size_t depth;
Packit Service 20376f
	size_t working;
Packit Service 20376f
	size_t data_ready;
Packit Service 20376f
};
Packit Service 20376f
Packit Service 20376f
static void *threaded_find_deltas(void *arg)
Packit Service 20376f
{
Packit Service 20376f
	struct thread_params *me = arg;
Packit Service 20376f
Packit Service 20376f
	while (me->remaining) {
Packit Service 20376f
		if (find_deltas(me->pb, me->list, &me->remaining,
Packit Service 20376f
				me->window, me->depth) < 0) {
Packit Service 20376f
			; /* TODO */
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		git_packbuilder__progress_lock(me->pb);
Packit Service 20376f
		me->working = 0;
Packit Service 20376f
		git_cond_signal(&me->pb->progress_cond);
Packit Service 20376f
		git_packbuilder__progress_unlock(me->pb);
Packit Service 20376f
Packit Service 20376f
		if (git_mutex_lock(&me->mutex)) {
Packit Service 20376f
			giterr_set(GITERR_THREAD, "unable to lock packfile condition mutex");
Packit Service 20376f
			return NULL;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		while (!me->data_ready)
Packit Service 20376f
			git_cond_wait(&me->cond, &me->mutex);
Packit Service 20376f
Packit Service 20376f
		/*
Packit Service 20376f
		 * We must not set ->data_ready before we wait on the
Packit Service 20376f
		 * condition because the main thread may have set it to 1
Packit Service 20376f
		 * before we get here. In order to be sure that new
Packit Service 20376f
		 * work is available if we see 1 in ->data_ready, it
Packit Service 20376f
		 * was initialized to 0 before this thread was spawned
Packit Service 20376f
		 * and we reset it to 0 right away.
Packit Service 20376f
		 */
Packit Service 20376f
		me->data_ready = 0;
Packit Service 20376f
		git_mutex_unlock(&me->mutex);
Packit Service 20376f
	}
Packit Service 20376f
	/* leave ->working 1 so that this doesn't get more work assigned */
Packit Service 20376f
	return NULL;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int ll_find_deltas(git_packbuilder *pb, git_pobject **list,
Packit Service 20376f
			  size_t list_size, size_t window, size_t depth)
Packit Service 20376f
{
Packit Service 20376f
	struct thread_params *p;
Packit Service 20376f
	size_t i;
Packit Service 20376f
	int ret, active_threads = 0;
Packit Service 20376f
Packit Service 20376f
	if (!pb->nr_threads)
Packit Service 20376f
		pb->nr_threads = git_online_cpus();
Packit Service 20376f
Packit Service 20376f
	if (pb->nr_threads <= 1) {
Packit Service 20376f
		find_deltas(pb, list, &list_size, window, depth);
Packit Service 20376f
		return 0;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	p = git__mallocarray(pb->nr_threads, sizeof(*p));
Packit Service 20376f
	GITERR_CHECK_ALLOC(p);
Packit Service 20376f
Packit Service 20376f
	/* Partition the work among the threads */
Packit Service 20376f
	for (i = 0; i < pb->nr_threads; ++i) {
Packit Service 20376f
		size_t sub_size = list_size / (pb->nr_threads - i);
Packit Service 20376f
Packit Service 20376f
		/* don't use too small segments or no deltas will be found */
Packit Service 20376f
		if (sub_size < 2*window && i+1 < pb->nr_threads)
Packit Service 20376f
			sub_size = 0;
Packit Service 20376f
Packit Service 20376f
		p[i].pb = pb;
Packit Service 20376f
		p[i].window = window;
Packit Service 20376f
		p[i].depth = depth;
Packit Service 20376f
		p[i].working = 1;
Packit Service 20376f
		p[i].data_ready = 0;
Packit Service 20376f
Packit Service 20376f
		/* try to split chunks on "path" boundaries */
Packit Service 20376f
		while (sub_size && sub_size < list_size &&
Packit Service 20376f
		       list[sub_size]->hash &&
Packit Service 20376f
		       list[sub_size]->hash == list[sub_size-1]->hash)
Packit Service 20376f
			sub_size++;
Packit Service 20376f
Packit Service 20376f
		p[i].list = list;
Packit Service 20376f
		p[i].list_size = sub_size;
Packit Service 20376f
		p[i].remaining = sub_size;
Packit Service 20376f
Packit Service 20376f
		list += sub_size;
Packit Service 20376f
		list_size -= sub_size;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/* Start work threads */
Packit Service 20376f
	for (i = 0; i < pb->nr_threads; ++i) {
Packit Service 20376f
		if (!p[i].list_size)
Packit Service 20376f
			continue;
Packit Service 20376f
Packit Service 20376f
		git_mutex_init(&p[i].mutex);
Packit Service 20376f
		git_cond_init(&p[i].cond);
Packit Service 20376f
Packit Service 20376f
		ret = git_thread_create(&p[i].thread,
Packit Service 20376f
					threaded_find_deltas, &p[i]);
Packit Service 20376f
		if (ret) {
Packit Service 20376f
			giterr_set(GITERR_THREAD, "unable to create thread");
Packit Service 20376f
			return -1;
Packit Service 20376f
		}
Packit Service 20376f
		active_threads++;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * Now let's wait for work completion.  Each time a thread is done
Packit Service 20376f
	 * with its work, we steal half of the remaining work from the
Packit Service 20376f
	 * thread with the largest number of unprocessed objects and give
Packit Service 20376f
	 * it to that newly idle thread.  This ensure good load balancing
Packit Service 20376f
	 * until the remaining object list segments are simply too short
Packit Service 20376f
	 * to be worth splitting anymore.
Packit Service 20376f
	 */
Packit Service 20376f
	while (active_threads) {
Packit Service 20376f
		struct thread_params *target = NULL;
Packit Service 20376f
		struct thread_params *victim = NULL;
Packit Service 20376f
		size_t sub_size = 0;
Packit Service 20376f
Packit Service 20376f
		/* Start by locating a thread that has transitioned its
Packit Service 20376f
		 * 'working' flag from 1 -> 0. This indicates that it is
Packit Service 20376f
		 * ready to receive more work using our work-stealing
Packit Service 20376f
		 * algorithm. */
Packit Service 20376f
		git_packbuilder__progress_lock(pb);
Packit Service 20376f
		for (;;) {
Packit Service 20376f
			for (i = 0; !target && i < pb->nr_threads; i++)
Packit Service 20376f
				if (!p[i].working)
Packit Service 20376f
					target = &p[i];
Packit Service 20376f
			if (target)
Packit Service 20376f
				break;
Packit Service 20376f
			git_cond_wait(&pb->progress_cond, &pb->progress_mutex);
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		/* At this point we hold the progress lock and have located
Packit Service 20376f
		 * a thread to receive more work. We still need to locate a
Packit Service 20376f
		 * thread from which to steal work (the victim). */
Packit Service 20376f
		for (i = 0; i < pb->nr_threads; i++)
Packit Service 20376f
			if (p[i].remaining > 2*window &&
Packit Service 20376f
			    (!victim || victim->remaining < p[i].remaining))
Packit Service 20376f
				victim = &p[i];
Packit Service 20376f
Packit Service 20376f
		if (victim) {
Packit Service 20376f
			sub_size = victim->remaining / 2;
Packit Service 20376f
			list = victim->list + victim->list_size - sub_size;
Packit Service 20376f
			while (sub_size && list[0]->hash &&
Packit Service 20376f
			       list[0]->hash == list[-1]->hash) {
Packit Service 20376f
				list++;
Packit Service 20376f
				sub_size--;
Packit Service 20376f
			}
Packit Service 20376f
			if (!sub_size) {
Packit Service 20376f
				/*
Packit Service 20376f
				 * It is possible for some "paths" to have
Packit Service 20376f
				 * so many objects that no hash boundary
Packit Service 20376f
				 * might be found.  Let's just steal the
Packit Service 20376f
				 * exact half in that case.
Packit Service 20376f
				 */
Packit Service 20376f
				sub_size = victim->remaining / 2;
Packit Service 20376f
				list -= sub_size;
Packit Service 20376f
			}
Packit Service 20376f
			target->list = list;
Packit Service 20376f
			victim->list_size -= sub_size;
Packit Service 20376f
			victim->remaining -= sub_size;
Packit Service 20376f
		}
Packit Service 20376f
		target->list_size = sub_size;
Packit Service 20376f
		target->remaining = sub_size;
Packit Service 20376f
		target->working = 1;
Packit Service 20376f
		git_packbuilder__progress_unlock(pb);
Packit Service 20376f
Packit Service 20376f
		if (git_mutex_lock(&target->mutex)) {
Packit Service 20376f
			giterr_set(GITERR_THREAD, "unable to lock packfile condition mutex");
Packit Service 20376f
			git__free(p);
Packit Service 20376f
			return -1;
Packit Service 20376f
		}
Packit Service 20376f
Packit Service 20376f
		target->data_ready = 1;
Packit Service 20376f
		git_cond_signal(&target->cond);
Packit Service 20376f
		git_mutex_unlock(&target->mutex);
Packit Service 20376f
Packit Service 20376f
		if (!sub_size) {
Packit Service 20376f
			git_thread_join(&target->thread, NULL);
Packit Service 20376f
			git_cond_free(&target->cond);
Packit Service 20376f
			git_mutex_free(&target->mutex);
Packit Service 20376f
			active_threads--;
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	git__free(p);
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
#else
Packit Service 20376f
#define ll_find_deltas(pb, l, ls, w, d) find_deltas(pb, l, &ls, w, d)
Packit Service 20376f
#endif
Packit Service 20376f
Packit Service 20376f
static int prepare_pack(git_packbuilder *pb)
Packit Service 20376f
{
Packit Service 20376f
	git_pobject **delta_list;
Packit Service 20376f
	size_t i, n = 0;
Packit Service 20376f
Packit Service 20376f
	if (pb->nr_objects == 0 || pb->done)
Packit Service 20376f
		return 0; /* nothing to do */
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * Although we do not report progress during deltafication, we
Packit Service 20376f
	 * at least report that we are in the deltafication stage
Packit Service 20376f
	 */
Packit Service 20376f
	if (pb->progress_cb)
Packit Service 20376f
			pb->progress_cb(GIT_PACKBUILDER_DELTAFICATION, 0, pb->nr_objects, pb->progress_cb_payload);
Packit Service 20376f
Packit Service 20376f
	delta_list = git__mallocarray(pb->nr_objects, sizeof(*delta_list));
Packit Service 20376f
	GITERR_CHECK_ALLOC(delta_list);
Packit Service 20376f
Packit Service 20376f
	for (i = 0; i < pb->nr_objects; ++i) {
Packit Service 20376f
		git_pobject *po = pb->object_list + i;
Packit Service 20376f
Packit Service 20376f
		/* Make sure the item is within our size limits */
Packit Service 20376f
		if (po->size < 50 || po->size > pb->big_file_threshold)
Packit Service 20376f
			continue;
Packit Service 20376f
Packit Service 20376f
		delta_list[n++] = po;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (n > 1) {
Packit Service 20376f
		git__tsort((void **)delta_list, n, type_size_sort);
Packit Service 20376f
		if (ll_find_deltas(pb, delta_list, n,
Packit Service 20376f
				   GIT_PACK_WINDOW + 1,
Packit Service 20376f
				   GIT_PACK_DEPTH) < 0) {
Packit Service 20376f
			git__free(delta_list);
Packit Service 20376f
			return -1;
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	report_delta_progress(pb, pb->nr_objects, true);
Packit Service 20376f
Packit Service 20376f
	pb->done = true;
Packit Service 20376f
	git__free(delta_list);
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
#define PREPARE_PACK if (prepare_pack(pb) < 0) { return -1; }
Packit Service 20376f
Packit Service 20376f
int git_packbuilder_foreach(git_packbuilder *pb, int (*cb)(void *buf, size_t size, void *payload), void *payload)
Packit Service 20376f
{
Packit Service 20376f
	PREPARE_PACK;
Packit Service 20376f
	return write_pack(pb, cb, payload);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_packbuilder_write_buf(git_buf *buf, git_packbuilder *pb)
Packit Service 20376f
{
Packit Service 20376f
	PREPARE_PACK;
Packit Service 20376f
	git_buf_sanitize(buf);
Packit Service 20376f
	return write_pack(pb, &write_pack_buf, buf);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int write_cb(void *buf, size_t len, void *payload)
Packit Service 20376f
{
Packit Service 20376f
	struct pack_write_context *ctx = payload;
Packit Service 20376f
	return git_indexer_append(ctx->indexer, buf, len, ctx->stats);
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_packbuilder_write(
Packit Service 20376f
	git_packbuilder *pb,
Packit Service 20376f
	const char *path,
Packit Service 20376f
	unsigned int mode,
Packit Service 20376f
	git_transfer_progress_cb progress_cb,
Packit Service 20376f
	void *progress_cb_payload)
Packit Service 20376f
{
Packit Service 20376f
	git_indexer *indexer;
Packit Service 20376f
	git_transfer_progress stats;
Packit Service 20376f
	struct pack_write_context ctx;
Packit Service 20376f
	int t;
Packit Service 20376f
Packit Service 20376f
	PREPARE_PACK;
Packit Service 20376f
Packit Service 20376f
	if (git_indexer_new(
Packit Service 20376f
		&indexer, path, mode, pb->odb, progress_cb, progress_cb_payload) < 0)
Packit Service 20376f
		return -1;
Packit Service 20376f
Packit Service 20376f
	if (!git_repository__cvar(&t, pb->repo, GIT_CVAR_FSYNCOBJECTFILES) && t)
Packit Service 20376f
		git_indexer__set_fsync(indexer, 1);
Packit Service 20376f
Packit Service 20376f
	ctx.indexer = indexer;
Packit Service 20376f
	ctx.stats = &stat;;
Packit Service 20376f
Packit Service 20376f
	if (git_packbuilder_foreach(pb, write_cb, &ctx) < 0 ||
Packit Service 20376f
		git_indexer_commit(indexer, &stats) < 0) {
Packit Service 20376f
		git_indexer_free(indexer);
Packit Service 20376f
		return -1;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	git_oid_cpy(&pb->pack_oid, git_indexer_hash(indexer));
Packit Service 20376f
Packit Service 20376f
	git_indexer_free(indexer);
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
#undef PREPARE_PACK
Packit Service 20376f
Packit Service 20376f
const git_oid *git_packbuilder_hash(git_packbuilder *pb)
Packit Service 20376f
{
Packit Service 20376f
	return &pb->pack_oid;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
Packit Service 20376f
static int cb_tree_walk(
Packit Service 20376f
	const char *root, const git_tree_entry *entry, void *payload)
Packit Service 20376f
{
Packit Service 20376f
	int error;
Packit Service 20376f
	struct tree_walk_context *ctx = payload;
Packit Service 20376f
Packit Service 20376f
	/* A commit inside a tree represents a submodule commit and should be skipped. */
Packit Service 20376f
	if (git_tree_entry_type(entry) == GIT_OBJ_COMMIT)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	if (!(error = git_buf_sets(&ctx->buf, root)) &&
Packit Service 20376f
		!(error = git_buf_puts(&ctx->buf, git_tree_entry_name(entry))))
Packit Service 20376f
		error = git_packbuilder_insert(
Packit Service 20376f
			ctx->pb, git_tree_entry_id(entry), git_buf_cstr(&ctx->buf));
Packit Service 20376f
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_packbuilder_insert_commit(git_packbuilder *pb, const git_oid *oid)
Packit Service 20376f
{
Packit Service 20376f
	git_commit *commit;
Packit Service 20376f
Packit Service 20376f
	if (git_commit_lookup(&commit, pb->repo, oid) < 0 ||
Packit Service 20376f
		git_packbuilder_insert(pb, oid, NULL) < 0)
Packit Service 20376f
		return -1;
Packit Service 20376f
Packit Service 20376f
	if (git_packbuilder_insert_tree(pb, git_commit_tree_id(commit)) < 0)
Packit Service 20376f
		return -1;
Packit Service 20376f
Packit Service 20376f
	git_commit_free(commit);
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_packbuilder_insert_tree(git_packbuilder *pb, const git_oid *oid)
Packit Service 20376f
{
Packit Service 20376f
	int error;
Packit Service 20376f
	git_tree *tree = NULL;
Packit Service 20376f
	struct tree_walk_context context = { pb, GIT_BUF_INIT };
Packit Service 20376f
Packit Service 20376f
	if (!(error = git_tree_lookup(&tree, pb->repo, oid)) &&
Packit Service 20376f
	    !(error = git_packbuilder_insert(pb, oid, NULL)))
Packit Service 20376f
		error = git_tree_walk(tree, GIT_TREEWALK_PRE, cb_tree_walk, &context);
Packit Service 20376f
Packit Service 20376f
	git_tree_free(tree);
Packit Service 20376f
	git_buf_free(&context.buf);
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_packbuilder_insert_recur(git_packbuilder *pb, const git_oid *id, const char *name)
Packit Service 20376f
{
Packit Service 20376f
	git_object *obj;
Packit Service 20376f
	int error;
Packit Service 20376f
Packit Service 20376f
	assert(pb && id);
Packit Service 20376f
Packit Service 20376f
	if ((error = git_object_lookup(&obj, pb->repo, id, GIT_OBJ_ANY)) < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	switch (git_object_type(obj)) {
Packit Service 20376f
	case GIT_OBJ_BLOB:
Packit Service 20376f
		error = git_packbuilder_insert(pb, id, name);
Packit Service 20376f
		break;
Packit Service 20376f
	case GIT_OBJ_TREE:
Packit Service 20376f
		error = git_packbuilder_insert_tree(pb, id);
Packit Service 20376f
		break;
Packit Service 20376f
	case GIT_OBJ_COMMIT:
Packit Service 20376f
		error = git_packbuilder_insert_commit(pb, id);
Packit Service 20376f
		break;
Packit Service 20376f
	case GIT_OBJ_TAG:
Packit Service 20376f
		if ((error = git_packbuilder_insert(pb, id, name)) < 0)
Packit Service 20376f
			goto cleanup;
Packit Service 20376f
		error = git_packbuilder_insert_recur(pb, git_tag_target_id((git_tag *) obj), NULL);
Packit Service 20376f
		break;
Packit Service 20376f
Packit Service 20376f
	default:
Packit Service 20376f
		giterr_set(GITERR_INVALID, "unknown object type");
Packit Service 20376f
		error = -1;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
cleanup:
Packit Service 20376f
	git_object_free(obj);
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
size_t git_packbuilder_object_count(git_packbuilder *pb)
Packit Service 20376f
{
Packit Service 20376f
	return pb->nr_objects;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
size_t git_packbuilder_written(git_packbuilder *pb)
Packit Service 20376f
{
Packit Service 20376f
	return pb->nr_written;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int lookup_walk_object(git_walk_object **out, git_packbuilder *pb, const git_oid *id)
Packit Service 20376f
{
Packit Service 20376f
	git_walk_object *obj;
Packit Service 20376f
Packit Service 20376f
	obj = git_pool_mallocz(&pb->object_pool, 1);
Packit Service 20376f
	if (!obj) {
Packit Service 20376f
		giterr_set_oom();
Packit Service 20376f
		return -1;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	git_oid_cpy(&obj->id, id);
Packit Service 20376f
Packit Service 20376f
	*out = obj;
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int retrieve_object(git_walk_object **out, git_packbuilder *pb, const git_oid *id)
Packit Service 20376f
{
Packit Service 20376f
	int error;
Packit Service 20376f
	khiter_t pos;
Packit Service 20376f
	git_walk_object *obj;
Packit Service 20376f
Packit Service 20376f
	pos = git_oidmap_lookup_index(pb->walk_objects, id);
Packit Service 20376f
	if (git_oidmap_valid_index(pb->walk_objects, pos)) {
Packit Service 20376f
		obj = git_oidmap_value_at(pb->walk_objects, pos);
Packit Service 20376f
	} else {
Packit Service 20376f
		if ((error = lookup_walk_object(&obj, pb, id)) < 0)
Packit Service 20376f
			return error;
Packit Service 20376f
Packit Service 20376f
		git_oidmap_insert(pb->walk_objects, &obj->id, obj, &error);
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	*out = obj;
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int mark_blob_uninteresting(git_packbuilder *pb, const git_oid *id)
Packit Service 20376f
{
Packit Service 20376f
	int error;
Packit Service 20376f
	git_walk_object *obj;
Packit Service 20376f
Packit Service 20376f
	if ((error = retrieve_object(&obj, pb, id)) < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	obj->uninteresting = 1;
Packit Service 20376f
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
static int mark_tree_uninteresting(git_packbuilder *pb, const git_oid *id)
Packit Service 20376f
{
Packit Service 20376f
	git_walk_object *obj;
Packit Service 20376f
	git_tree *tree;
Packit Service 20376f
	int error;
Packit Service 20376f
	size_t i;
Packit Service 20376f
Packit Service 20376f
	if ((error = retrieve_object(&obj, pb, id)) < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	if (obj->uninteresting)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	obj->uninteresting = 1;
Packit Service 20376f
Packit Service 20376f
	if ((error = git_tree_lookup(&tree, pb->repo, id)) < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	for (i = 0; i < git_tree_entrycount(tree); i++) {
Packit Service 20376f
		const git_tree_entry *entry = git_tree_entry_byindex(tree, i);
Packit Service 20376f
		const git_oid *entry_id = git_tree_entry_id(entry);
Packit Service 20376f
		switch (git_tree_entry_type(entry)) {
Packit Service 20376f
		case GIT_OBJ_TREE:
Packit Service 20376f
			if ((error = mark_tree_uninteresting(pb, entry_id)) < 0)
Packit Service 20376f
				goto cleanup;
Packit Service 20376f
			break;
Packit Service 20376f
		case GIT_OBJ_BLOB:
Packit Service 20376f
			if ((error = mark_blob_uninteresting(pb, entry_id)) < 0)
Packit Service 20376f
				goto cleanup;
Packit Service 20376f
			break;
Packit Service 20376f
		default:
Packit Service 20376f
			/* it's a submodule or something unknown, we don't want it */
Packit Service 20376f
			;
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
cleanup:
Packit Service 20376f
	git_tree_free(tree);
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
/*
Packit Service 20376f
 * Mark the edges of the graph uninteresting. Since we start from a
Packit Service 20376f
 * git_revwalk, the commits are already uninteresting, but we need to
Packit Service 20376f
 * mark the trees and blobs.
Packit Service 20376f
 */
Packit Service 20376f
static int mark_edges_uninteresting(git_packbuilder *pb, git_commit_list *commits)
Packit Service 20376f
{
Packit Service 20376f
	int error;
Packit Service 20376f
	git_commit_list *list;
Packit Service 20376f
	git_commit *commit;
Packit Service 20376f
Packit Service 20376f
	for (list = commits; list; list = list->next) {
Packit Service 20376f
		if (!list->item->uninteresting)
Packit Service 20376f
			continue;
Packit Service 20376f
Packit Service 20376f
		if ((error = git_commit_lookup(&commit, pb->repo, &list->item->oid)) < 0)
Packit Service 20376f
			return error;
Packit Service 20376f
Packit Service 20376f
		error = mark_tree_uninteresting(pb, git_commit_tree_id(commit));
Packit Service 20376f
		git_commit_free(commit);
Packit Service 20376f
Packit Service 20376f
		if (error < 0)
Packit Service 20376f
			return error;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int insert_tree(git_packbuilder *pb, git_tree *tree)
Packit Service 20376f
{
Packit Service 20376f
	size_t i;
Packit Service 20376f
	int error;
Packit Service 20376f
	git_tree *subtree;
Packit Service 20376f
	git_walk_object *obj;
Packit Service 20376f
	const char *name;
Packit Service 20376f
Packit Service 20376f
	if ((error = retrieve_object(&obj, pb, git_tree_id(tree))) < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	if (obj->seen)
Packit Service 20376f
		return 0;
Packit Service 20376f
Packit Service 20376f
	obj->seen = 1;
Packit Service 20376f
Packit Service 20376f
	if ((error = git_packbuilder_insert(pb, &obj->id, NULL)))
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	for (i = 0; i < git_tree_entrycount(tree); i++) {
Packit Service 20376f
		const git_tree_entry *entry = git_tree_entry_byindex(tree, i);
Packit Service 20376f
		const git_oid *entry_id = git_tree_entry_id(entry);
Packit Service 20376f
		switch (git_tree_entry_type(entry)) {
Packit Service 20376f
		case GIT_OBJ_TREE:
Packit Service 20376f
			if ((error = git_tree_lookup(&subtree, pb->repo, entry_id)) < 0)
Packit Service 20376f
				return error;
Packit Service 20376f
Packit Service 20376f
			error = insert_tree(pb, subtree);
Packit Service 20376f
			git_tree_free(subtree);
Packit Service 20376f
Packit Service 20376f
			if (error < 0)
Packit Service 20376f
				return error;
Packit Service 20376f
Packit Service 20376f
			break;
Packit Service 20376f
		case GIT_OBJ_BLOB:
Packit Service 20376f
			name = git_tree_entry_name(entry);
Packit Service 20376f
			if ((error = git_packbuilder_insert(pb, entry_id, name)) < 0)
Packit Service 20376f
				return error;
Packit Service 20376f
			break;
Packit Service 20376f
		default:
Packit Service 20376f
			/* it's a submodule or something unknown, we don't want it */
Packit Service 20376f
			;
Packit Service 20376f
		}
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int insert_commit(git_packbuilder *pb, git_walk_object *obj)
Packit Service 20376f
{
Packit Service 20376f
	int error;
Packit Service 20376f
	git_commit *commit = NULL;
Packit Service 20376f
	git_tree *tree = NULL;
Packit Service 20376f
Packit Service 20376f
	obj->seen = 1;
Packit Service 20376f
Packit Service 20376f
	if ((error = git_packbuilder_insert(pb, &obj->id, NULL)) < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	if ((error = git_commit_lookup(&commit, pb->repo, &obj->id)) < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	if ((error = git_tree_lookup(&tree, pb->repo, git_commit_tree_id(commit))) < 0)
Packit Service 20376f
		goto cleanup;
Packit Service 20376f
Packit Service 20376f
	if ((error = insert_tree(pb, tree)) < 0)
Packit Service 20376f
		goto cleanup;
Packit Service 20376f
Packit Service 20376f
cleanup:
Packit Service 20376f
	git_commit_free(commit);
Packit Service 20376f
	git_tree_free(tree);
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_packbuilder_insert_walk(git_packbuilder *pb, git_revwalk *walk)
Packit Service 20376f
{
Packit Service 20376f
	int error;
Packit Service 20376f
	git_oid id;
Packit Service 20376f
	git_walk_object *obj;
Packit Service 20376f
Packit Service 20376f
	assert(pb && walk);
Packit Service 20376f
Packit Service 20376f
	if ((error = mark_edges_uninteresting(pb, walk->user_input)) < 0)
Packit Service 20376f
		return error;
Packit Service 20376f
Packit Service 20376f
	/*
Packit Service 20376f
	 * TODO: git marks the parents of the edges
Packit Service 20376f
	 * uninteresting. This may provide a speed advantage, but does
Packit Service 20376f
	 * seem to assume the remote does not have a single-commit
Packit Service 20376f
	 * history on the other end.
Packit Service 20376f
	 */
Packit Service 20376f
Packit Service 20376f
	/* walk down each tree up to the blobs and insert them, stopping when uninteresting */
Packit Service 20376f
	while ((error = git_revwalk_next(&id, walk)) == 0) {
Packit Service 20376f
		if ((error = retrieve_object(&obj, pb, &id)) < 0)
Packit Service 20376f
			return error;
Packit Service 20376f
Packit Service 20376f
		if (obj->seen || obj->uninteresting)
Packit Service 20376f
			continue;
Packit Service 20376f
Packit Service 20376f
		if ((error = insert_commit(pb, obj)) < 0)
Packit Service 20376f
			return error;
Packit Service 20376f
	}
Packit Service 20376f
Packit Service 20376f
	if (error == GIT_ITEROVER)
Packit Service 20376f
		error = 0;
Packit Service 20376f
Packit Service 20376f
	return error;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
int git_packbuilder_set_callbacks(git_packbuilder *pb, git_packbuilder_progress progress_cb, void *progress_cb_payload)
Packit Service 20376f
{
Packit Service 20376f
	if (!pb)
Packit Service 20376f
		return -1;
Packit Service 20376f
Packit Service 20376f
	pb->progress_cb = progress_cb;
Packit Service 20376f
	pb->progress_cb_payload = progress_cb_payload;
Packit Service 20376f
Packit Service 20376f
	return 0;
Packit Service 20376f
}
Packit Service 20376f
Packit Service 20376f
void git_packbuilder_free(git_packbuilder *pb)
Packit Service 20376f
{
Packit Service 20376f
	if (pb == NULL)
Packit Service 20376f
		return;
Packit Service 20376f
Packit Service 20376f
#ifdef GIT_THREADS
Packit Service 20376f
Packit Service 20376f
	git_mutex_free(&pb->cache_mutex);
Packit Service 20376f
	git_mutex_free(&pb->progress_mutex);
Packit Service 20376f
	git_cond_free(&pb->progress_cond);
Packit Service 20376f
Packit Service 20376f
#endif
Packit Service 20376f
Packit Service 20376f
	if (pb->odb)
Packit Service 20376f
		git_odb_free(pb->odb);
Packit Service 20376f
Packit Service 20376f
	if (pb->object_ix)
Packit Service 20376f
		git_oidmap_free(pb->object_ix);
Packit Service 20376f
Packit Service 20376f
	if (pb->object_list)
Packit Service 20376f
		git__free(pb->object_list);
Packit Service 20376f
Packit Service 20376f
	git_oidmap_free(pb->walk_objects);
Packit Service 20376f
	git_pool_clear(&pb->object_pool);
Packit Service 20376f
Packit Service 20376f
	git_hash_ctx_cleanup(&pb->ctx);
Packit Service 20376f
	git_zstream_free(&pb->zstream);
Packit Service 20376f
Packit Service 20376f
	git__free(pb);
Packit Service 20376f
}