git

1
#include "git-compat-util.h"
2
#include "object.h"
3
#include "pack.h"
4
#include "pack-objects.h"
5
#include "packfile.h"
6
#include "parse.h"
7

8
static uint32_t locate_object_entry_hash(struct packing_data *pdata,
9
					 const struct object_id *oid,
10
					 int *found)
11
{
12
	uint32_t i, mask = (pdata->index_size - 1);
13

14
	i = oidhash(oid) & mask;
15

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

19
		if (oideq(oid, &pdata->objects[pos].idx.oid)) {
20
			*found = 1;
21
			return i;
22
		}
23

24
		i = (i + 1) & mask;
25
	}
26

27
	*found = 0;
28
	return i;
29
}
30

31
static inline uint32_t closest_pow2(uint32_t v)
32
{
33
	v = v - 1;
34
	v |= v >> 1;
35
	v |= v >> 2;
36
	v |= v >> 4;
37
	v |= v >> 8;
38
	v |= v >> 16;
39
	return v + 1;
40
}
41

42
static void rehash_objects(struct packing_data *pdata)
43
{
44
	uint32_t i;
45
	struct object_entry *entry;
46

47
	pdata->index_size = closest_pow2(pdata->nr_objects * 3);
48
	if (pdata->index_size < 1024)
49
		pdata->index_size = 1024;
50

51
	free(pdata->index);
52
	CALLOC_ARRAY(pdata->index, pdata->index_size);
53

54
	entry = pdata->objects;
55

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

62
		if (found)
63
			BUG("Duplicate object in hash");
64

65
		pdata->index[ix] = i + 1;
66
		entry++;
67
	}
68
}
69

70
struct object_entry *packlist_find(struct packing_data *pdata,
71
				   const struct object_id *oid)
72
{
73
	uint32_t i;
74
	int found;
75

76
	if (!pdata->index_size)
77
		return NULL;
78

79
	i = locate_object_entry_hash(pdata, oid, &found);
80

81
	if (!found)
82
		return NULL;
83

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

87
static void prepare_in_pack_by_idx(struct packing_data *pdata)
88
{
89
	struct packed_git **mapping, *p;
90
	int cnt = 0, nr = 1U << OE_IN_PACK_BITS;
91

92
	ALLOC_ARRAY(mapping, nr);
93
	/*
94
	 * oe_in_pack() on an all-zero'd object_entry
95
	 * (i.e. in_pack_idx also zero) should return NULL.
96
	 */
97
	mapping[cnt++] = NULL;
98
	for (p = get_all_packs(pdata->repo); p; p = p->next, cnt++) {
99
		if (cnt == nr) {
100
			free(mapping);
101
			return;
102
		}
103
		p->index = cnt;
104
		mapping[cnt] = p;
105
	}
106
	pdata->in_pack_by_idx = mapping;
107
}
108

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

122
	if (pack->in_pack)
123
		BUG("packing_data has already been converted to pack array");
124

125
	ALLOC_ARRAY(pack->in_pack, pack->nr_alloc);
126

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

130
	FREE_AND_NULL(pack->in_pack_by_idx);
131
}
132

133
/* assume pdata is already zero'd by caller */
134
void prepare_packing_data(struct repository *r, struct packing_data *pdata)
135
{
136
	pdata->repo = r;
137

138
	if (git_env_bool("GIT_TEST_FULL_IN_PACK_ARRAY", 0)) {
139
		/*
140
		 * do not initialize in_pack_by_idx[] to force the
141
		 * slow path in oe_in_pack()
142
		 */
143
	} else {
144
		prepare_in_pack_by_idx(pdata);
145
	}
146

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

154
void clear_packing_data(struct packing_data *pdata)
155
{
156
	if (!pdata)
157
		return;
158

159
	free(pdata->cruft_mtime);
160
	free(pdata->in_pack);
161
	free(pdata->in_pack_by_idx);
162
	free(pdata->in_pack_pos);
163
	free(pdata->index);
164
	free(pdata->layer);
165
	free(pdata->objects);
166
	free(pdata->tree_depth);
167
}
168

169
struct object_entry *packlist_alloc(struct packing_data *pdata,
170
				    const struct object_id *oid)
171
{
172
	struct object_entry *new_entry;
173

174
	if (pdata->nr_objects >= pdata->nr_alloc) {
175
		pdata->nr_alloc = (pdata->nr_alloc  + 1024) * 3 / 2;
176
		REALLOC_ARRAY(pdata->objects, pdata->nr_alloc);
177

178
		if (!pdata->in_pack_by_idx)
179
			REALLOC_ARRAY(pdata->in_pack, pdata->nr_alloc);
180
		if (pdata->delta_size)
181
			REALLOC_ARRAY(pdata->delta_size, pdata->nr_alloc);
182

183
		if (pdata->tree_depth)
184
			REALLOC_ARRAY(pdata->tree_depth, pdata->nr_alloc);
185

186
		if (pdata->layer)
187
			REALLOC_ARRAY(pdata->layer, pdata->nr_alloc);
188

189
		if (pdata->cruft_mtime)
190
			REALLOC_ARRAY(pdata->cruft_mtime, pdata->nr_alloc);
191
	}
192

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

195
	memset(new_entry, 0, sizeof(*new_entry));
196
	oidcpy(&new_entry->idx.oid, oid);
197

198
	if (pdata->index_size * 3 <= pdata->nr_objects * 4)
199
		rehash_objects(pdata);
200
	else {
201
		int found;
202
		uint32_t pos = locate_object_entry_hash(pdata,
203
							&new_entry->idx.oid,
204
							&found);
205
		if (found)
206
			BUG("duplicate object inserted into hash");
207
		pdata->index[pos] = pdata->nr_objects;
208
	}
209

210
	if (pdata->in_pack)
211
		pdata->in_pack[pdata->nr_objects - 1] = NULL;
212

213
	if (pdata->tree_depth)
214
		pdata->tree_depth[pdata->nr_objects - 1] = 0;
215

216
	if (pdata->layer)
217
		pdata->layer[pdata->nr_objects - 1] = 0;
218

219
	if (pdata->cruft_mtime)
220
		pdata->cruft_mtime[pdata->nr_objects - 1] = 0;
221

222
	return new_entry;
223
}
224

225
void oe_set_delta_ext(struct packing_data *pdata,
226
		      struct object_entry *delta,
227
		      const struct object_id *oid)
228
{
229
	struct object_entry *base;
230

231
	ALLOC_GROW(pdata->ext_bases, pdata->nr_ext + 1, pdata->alloc_ext);
232
	base = &pdata->ext_bases[pdata->nr_ext++];
233
	memset(base, 0, sizeof(*base));
234
	oidcpy(&base->idx.oid, oid);
235

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

240
	delta->ext_base = 1;
241
	delta->delta_idx = base - pdata->ext_bases + 1;
242
}
243