1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
51
52
53
54
55
56
57
58
59
60
61
62
63
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
91
92
93
94
95
96
97
98
99
100
101
102
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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
#include "cache.h"
#include "object.h"
#include "pack.h"
#include "pack-objects.h"
#include "packfile.h"
#include "config.h"
static uint32_t locate_object_entry_hash(struct packing_data *pdata,
const struct object_id *oid,
int *found)
{
uint32_t i, mask = (pdata->index_size - 1);
i = oidhash(oid) & mask;
while (pdata->index[i] > 0) {
uint32_t pos = pdata->index[i] - 1;
if (oideq(oid, &pdata->objects[pos].idx.oid)) {
*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;
free(pdata->index);
pdata->index = xcalloc(pdata->index_size, sizeof(*pdata->index));
entry = pdata->objects;
for (i = 0; i < pdata->nr_objects; i++) {
int found;
uint32_t ix = locate_object_entry_hash(pdata,
&entry->idx.oid,
&found);
if (found)
BUG("Duplicate object in hash");
pdata->index[ix] = i + 1;
entry++;
}
}
struct object_entry *packlist_find(struct packing_data *pdata,
const struct object_id *oid,
uint32_t *index_pos)
{
uint32_t i;
int found;
if (!pdata->index_size)
return NULL;
i = locate_object_entry_hash(pdata, oid, &found);
if (index_pos)
*index_pos = i;
if (!found)
return NULL;
return &pdata->objects[pdata->index[i] - 1];
}
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;
for (p = get_all_packs(pdata->repo); p; p = p->next, cnt++) {
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)
{
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 repository *r, struct packing_data *pdata)
{
pdata->repo = r;
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);
}
pdata->oe_size_limit = git_env_ulong("GIT_TEST_OE_SIZE",
1U << OE_SIZE_BITS);
pdata->oe_delta_size_limit = git_env_ulong("GIT_TEST_OE_DELTA_SIZE",
1UL << OE_DELTA_SIZE_BITS);
init_recursive_mutex(&pdata->odb_lock);
}
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;
REALLOC_ARRAY(pdata->objects, pdata->nr_alloc);
if (!pdata->in_pack_by_idx)
REALLOC_ARRAY(pdata->in_pack, pdata->nr_alloc);
if (pdata->delta_size)
REALLOC_ARRAY(pdata->delta_size, pdata->nr_alloc);
if (pdata->tree_depth)
REALLOC_ARRAY(pdata->tree_depth, pdata->nr_alloc);
if (pdata->layer)
REALLOC_ARRAY(pdata->layer, pdata->nr_alloc);
}
new_entry = pdata->objects + pdata->nr_objects++;
memset(new_entry, 0, sizeof(*new_entry));
hashcpy(new_entry->idx.oid.hash, sha1);
if (pdata->index_size * 3 <= pdata->nr_objects * 4)
rehash_objects(pdata);
else
pdata->index[index_pos] = pdata->nr_objects;
if (pdata->in_pack)
pdata->in_pack[pdata->nr_objects - 1] = NULL;
if (pdata->tree_depth)
pdata->tree_depth[pdata->nr_objects - 1] = 0;
if (pdata->layer)
pdata->layer[pdata->nr_objects - 1] = 0;
return new_entry;
}
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;
}
|
