pack-objects.c 4.81 KB
Newer Older
1 2 3 4
#include "cache.h"
#include "object.h"
#include "pack.h"
#include "pack-objects.h"
5 6
#include "packfile.h"
#include "config.h"
7 8 9 10 11

static uint32_t locate_object_entry_hash(struct packing_data *pdata,
					 const unsigned char *sha1,
					 int *found)
{
12
	uint32_t i, mask = (pdata->index_size - 1);
13

14
	i = sha1hash(sha1) & mask;
15 16 17 18

	while (pdata->index[i] > 0) {
		uint32_t pos = pdata->index[i] - 1;

19
		if (hasheq(sha1, pdata->objects[pos].idx.oid.hash)) {
20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50
			*found = 1;
			return i;
		}

		i = (i + 1) & mask;
	}

	*found = 0;
	return i;
}

static inline uint32_t closest_pow2(uint32_t v)
{
	v = v - 1;
	v |= v >> 1;
	v |= v >> 2;
	v |= v >> 4;
	v |= v >> 8;
	v |= v >> 16;
	return v + 1;
}

static void rehash_objects(struct packing_data *pdata)
{
	uint32_t i;
	struct object_entry *entry;

	pdata->index_size = closest_pow2(pdata->nr_objects * 3);
	if (pdata->index_size < 1024)
		pdata->index_size = 1024;

51 52
	free(pdata->index);
	pdata->index = xcalloc(pdata->index_size, sizeof(*pdata->index));
53 54 55 56 57

	entry = pdata->objects;

	for (i = 0; i < pdata->nr_objects; i++) {
		int found;
58 59 60
		uint32_t ix = locate_object_entry_hash(pdata,
						       entry->idx.oid.hash,
						       &found);
61 62

		if (found)
63
			BUG("Duplicate object in hash");
64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90

		pdata->index[ix] = i + 1;
		entry++;
	}
}

struct object_entry *packlist_find(struct packing_data *pdata,
				   const unsigned char *sha1,
				   uint32_t *index_pos)
{
	uint32_t i;
	int found;

	if (!pdata->index_size)
		return NULL;

	i = locate_object_entry_hash(pdata, sha1, &found);

	if (index_pos)
		*index_pos = i;

	if (!found)
		return NULL;

	return &pdata->objects[pdata->index[i] - 1];
}

91 92 93 94 95 96 97 98 99 100 101
static void prepare_in_pack_by_idx(struct packing_data *pdata)
{
	struct packed_git **mapping, *p;
	int cnt = 0, nr = 1U << OE_IN_PACK_BITS;

	ALLOC_ARRAY(mapping, nr);
	/*
	 * oe_in_pack() on an all-zero'd object_entry
	 * (i.e. in_pack_idx also zero) should return NULL.
	 */
	mapping[cnt++] = NULL;
102
	for (p = get_all_packs(the_repository); p; p = p->next, cnt++) {
103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145
		if (cnt == nr) {
			free(mapping);
			return;
		}
		p->index = cnt;
		mapping[cnt] = p;
	}
	pdata->in_pack_by_idx = mapping;
}

/*
 * A new pack appears after prepare_in_pack_by_idx() has been
 * run. This is likely a race.
 *
 * We could map this new pack to in_pack_by_idx[] array, but then we
 * have to deal with full array anyway. And since it's hard to test
 * this fall back code, just stay simple and fall back to using
 * in_pack[] array.
 */
void oe_map_new_pack(struct packing_data *pack,
		     struct packed_git *p)
{
	uint32_t i;

	REALLOC_ARRAY(pack->in_pack, pack->nr_alloc);

	for (i = 0; i < pack->nr_objects; i++)
		pack->in_pack[i] = oe_in_pack(pack, pack->objects + i);

	FREE_AND_NULL(pack->in_pack_by_idx);
}

/* assume pdata is already zero'd by caller */
void prepare_packing_data(struct packing_data *pdata)
{
	if (git_env_bool("GIT_TEST_FULL_IN_PACK_ARRAY", 0)) {
		/*
		 * do not initialize in_pack_by_idx[] to force the
		 * slow path in oe_in_pack()
		 */
	} else {
		prepare_in_pack_by_idx(pdata);
	}
146 147 148

	pdata->oe_size_limit = git_env_ulong("GIT_TEST_OE_SIZE",
					     1U << OE_SIZE_BITS);
149 150
	pdata->oe_delta_size_limit = git_env_ulong("GIT_TEST_OE_DELTA_SIZE",
						   1UL << OE_DELTA_SIZE_BITS);
151
	init_recursive_mutex(&pdata->odb_lock);
152 153
}

154 155 156 157 158 159 160 161
struct object_entry *packlist_alloc(struct packing_data *pdata,
				    const unsigned char *sha1,
				    uint32_t index_pos)
{
	struct object_entry *new_entry;

	if (pdata->nr_objects >= pdata->nr_alloc) {
		pdata->nr_alloc = (pdata->nr_alloc  + 1024) * 3 / 2;
162
		REALLOC_ARRAY(pdata->objects, pdata->nr_alloc);
163 164 165

		if (!pdata->in_pack_by_idx)
			REALLOC_ARRAY(pdata->in_pack, pdata->nr_alloc);
166 167
		if (pdata->delta_size)
			REALLOC_ARRAY(pdata->delta_size, pdata->nr_alloc);
168 169 170

		if (pdata->tree_depth)
			REALLOC_ARRAY(pdata->tree_depth, pdata->nr_alloc);
171 172 173

		if (pdata->layer)
			REALLOC_ARRAY(pdata->layer, pdata->nr_alloc);
174 175 176 177 178
	}

	new_entry = pdata->objects + pdata->nr_objects++;

	memset(new_entry, 0, sizeof(*new_entry));
179
	hashcpy(new_entry->idx.oid.hash, sha1);
180 181 182 183 184 185

	if (pdata->index_size * 3 <= pdata->nr_objects * 4)
		rehash_objects(pdata);
	else
		pdata->index[index_pos] = pdata->nr_objects;

186 187 188
	if (pdata->in_pack)
		pdata->in_pack[pdata->nr_objects - 1] = NULL;

189 190 191
	if (pdata->tree_depth)
		pdata->tree_depth[pdata->nr_objects - 1] = 0;

192 193 194
	if (pdata->layer)
		pdata->layer[pdata->nr_objects - 1] = 0;

195 196
	return new_entry;
}
197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215

void oe_set_delta_ext(struct packing_data *pdata,
		      struct object_entry *delta,
		      const unsigned char *sha1)
{
	struct object_entry *base;

	ALLOC_GROW(pdata->ext_bases, pdata->nr_ext + 1, pdata->alloc_ext);
	base = &pdata->ext_bases[pdata->nr_ext++];
	memset(base, 0, sizeof(*base));
	hashcpy(base->idx.oid.hash, sha1);

	/* These flags mark that we are not part of the actual pack output. */
	base->preferred_base = 1;
	base->filled = 1;

	delta->ext_base = 1;
	delta->delta_idx = base - pdata->ext_bases + 1;
}