]>
Commit | Line | Data |
---|---|---|
2834bc27 VM |
1 | #ifndef PACK_OBJECTS_H |
2 | #define PACK_OBJECTS_H | |
3 | ||
43fa44fa | 4 | #include "object-store.h" |
9ac3f0e5 | 5 | #include "thread-utils.h" |
ef3ca954 | 6 | #include "pack.h" |
43fa44fa | 7 | |
9806f5a7 NTND |
8 | #define DEFAULT_DELTA_CACHE_SIZE (256 * 1024 * 1024) |
9 | ||
0c6804ab | 10 | #define OE_DFS_STATE_BITS 2 |
b5c0cbd8 | 11 | #define OE_DEPTH_BITS 12 |
43fa44fa | 12 | #define OE_IN_PACK_BITS 10 |
0cb3c142 | 13 | #define OE_Z_DELTA_BITS 20 |
ac77d0c3 NTND |
14 | /* |
15 | * Note that oe_set_size() becomes expensive when the given size is | |
16 | * above this limit. Don't lower it too much. | |
17 | */ | |
18 | #define OE_SIZE_BITS 31 | |
9ac3f0e5 | 19 | #define OE_DELTA_SIZE_BITS 23 |
0c6804ab NTND |
20 | |
21 | /* | |
22 | * State flags for depth-first search used for analyzing delta cycles. | |
23 | * | |
24 | * The depth is measured in delta-links to the base (so if A is a delta | |
25 | * against B, then A has a depth of 1, and B a depth of 0). | |
26 | */ | |
27 | enum dfs_state { | |
28 | DFS_NONE = 0, | |
29 | DFS_ACTIVE, | |
30 | DFS_DONE, | |
31 | DFS_NUM_STATES | |
32 | }; | |
33 | ||
8d6ccce1 | 34 | /* |
3b13a5f2 NTND |
35 | * The size of struct nearly determines pack-objects's memory |
36 | * consumption. This struct is packed tight for that reason. When you | |
37 | * add or reorder something in this struct, think a bit about this. | |
38 | * | |
8d6ccce1 NTND |
39 | * basic object info |
40 | * ----------------- | |
41 | * idx.oid is filled up before delta searching starts. idx.crc32 is | |
42 | * only valid after the object is written out and will be used for | |
43 | * generating the index. idx.offset will be both gradually set and | |
44 | * used in writing phase (base objects get offset first, then deltas | |
45 | * refer to them) | |
46 | * | |
47 | * "size" is the uncompressed object size. Compressed size of the raw | |
48 | * data for an object in a pack is not stored anywhere but is computed | |
27a7d067 NTND |
49 | * and made available when reverse .idx is made. Note that when a |
50 | * delta is reused, "size" is the uncompressed _delta_ size, not the | |
51 | * canonical one after the delta has been applied. | |
8d6ccce1 NTND |
52 | * |
53 | * "hash" contains a path name hash which is used for sorting the | |
54 | * delta list and also during delta searching. Once prepare_pack() | |
55 | * returns it's no longer needed. | |
56 | * | |
57 | * source pack info | |
58 | * ---------------- | |
59 | * The (in_pack, in_pack_offset) tuple contains the location of the | |
60 | * object in the source pack. in_pack_header_size allows quickly | |
61 | * skipping the header and going straight to the zlib stream. | |
62 | * | |
63 | * "type" and "in_pack_type" both describe object type. in_pack_type | |
64 | * may contain a delta type, while type is always the canonical type. | |
65 | * | |
66 | * deltas | |
67 | * ------ | |
68 | * Delta links (delta, delta_child and delta_sibling) are created to | |
69 | * reflect that delta graph from the source pack then updated or added | |
70 | * during delta searching phase when we find better deltas. | |
71 | * | |
72 | * delta_child and delta_sibling are last needed in | |
73 | * compute_write_order(). "delta" and "delta_size" must remain valid | |
74 | * at object writing phase in case the delta is not cached. | |
75 | * | |
76 | * If a delta is cached in memory and is compressed, delta_data points | |
77 | * to the data and z_delta_size contains the compressed size. If it's | |
78 | * uncompressed [1], z_delta_size must be zero. delta_size is always | |
79 | * the uncompressed size and must be valid even if the delta is not | |
80 | * cached. | |
81 | * | |
82 | * [1] during try_delta phase we don't bother with compressing because | |
83 | * the delta could be quickly replaced with a better one. | |
84 | */ | |
2834bc27 VM |
85 | struct object_entry { |
86 | struct pack_idx_entry idx; | |
2834bc27 | 87 | void *delta_data; /* cached delta (uncompressed) */ |
3b13a5f2 | 88 | off_t in_pack_offset; |
2834bc27 | 89 | uint32_t hash; /* name hint hash */ |
ac77d0c3 NTND |
90 | unsigned size_:OE_SIZE_BITS; |
91 | unsigned size_valid:1; | |
898eba5e NTND |
92 | uint32_t delta_idx; /* delta base object */ |
93 | uint32_t delta_child_idx; /* deltified objects who bases me */ | |
94 | uint32_t delta_sibling_idx; /* other deltified objects who | |
95 | * uses the same base as me | |
96 | */ | |
0aca34e8 NTND |
97 | unsigned delta_size_:OE_DELTA_SIZE_BITS; /* delta data size (uncompressed) */ |
98 | unsigned delta_size_valid:1; | |
9ac3f0e5 | 99 | unsigned char in_pack_header_size; |
3b13a5f2 | 100 | unsigned in_pack_idx:OE_IN_PACK_BITS; /* already in pack */ |
0cb3c142 | 101 | unsigned z_delta_size:OE_Z_DELTA_BITS; |
3b13a5f2 | 102 | unsigned type_valid:1; |
3b13a5f2 | 103 | unsigned no_try_delta:1; |
9ac3f0e5 | 104 | unsigned type_:TYPE_BITS; |
fd9b1bae | 105 | unsigned in_pack_type:TYPE_BITS; /* could be delta */ |
c8d521fa | 106 | |
2834bc27 VM |
107 | unsigned preferred_base:1; /* |
108 | * we do not pack this, but is available | |
109 | * to be used as the base object to delta | |
110 | * objects against. | |
111 | */ | |
2834bc27 VM |
112 | unsigned tagged:1; /* near the very tip of refs */ |
113 | unsigned filled:1; /* assigned write-order */ | |
0c6804ab | 114 | unsigned dfs_state:OE_DFS_STATE_BITS; |
b5c0cbd8 | 115 | unsigned depth:OE_DEPTH_BITS; |
6a1e32d5 | 116 | unsigned ext_base:1; /* delta_idx points outside packlist */ |
4cf2143e JK |
117 | |
118 | /* | |
3b13a5f2 | 119 | * pahole results on 64-bit linux (gcc and clang) |
7dbabbbe | 120 | * |
9ac3f0e5 | 121 | * size: 80, bit_padding: 9 bits |
3b13a5f2 NTND |
122 | * |
123 | * and on 32-bit (gcc) | |
124 | * | |
9ac3f0e5 | 125 | * size: 76, bit_padding: 9 bits |
4cf2143e | 126 | */ |
2834bc27 VM |
127 | }; |
128 | ||
129 | struct packing_data { | |
130 | struct object_entry *objects; | |
131 | uint32_t nr_objects, nr_alloc; | |
132 | ||
133 | int32_t *index; | |
134 | uint32_t index_size; | |
06af3bba NTND |
135 | |
136 | unsigned int *in_pack_pos; | |
9ac3f0e5 | 137 | unsigned long *delta_size; |
43fa44fa NTND |
138 | |
139 | /* | |
140 | * Only one of these can be non-NULL and they have different | |
141 | * sizes. if in_pack_by_idx is allocated, oe_in_pack() returns | |
142 | * the pack of an object using in_pack_idx field. If not, | |
143 | * in_pack[] array is used the same way as in_pack_pos[] | |
144 | */ | |
145 | struct packed_git **in_pack_by_idx; | |
146 | struct packed_git **in_pack; | |
ac77d0c3 | 147 | |
9ac3f0e5 | 148 | pthread_mutex_t lock; |
459307b1 | 149 | pthread_mutex_t read_lock; |
9ac3f0e5 | 150 | |
6a1e32d5 JK |
151 | /* |
152 | * This list contains entries for bases which we know the other side | |
153 | * has (e.g., via reachability bitmaps), but which aren't in our | |
154 | * "objects" list. | |
155 | */ | |
156 | struct object_entry *ext_bases; | |
157 | uint32_t nr_ext, alloc_ext; | |
158 | ||
ac77d0c3 | 159 | uintmax_t oe_size_limit; |
9ac3f0e5 | 160 | uintmax_t oe_delta_size_limit; |
108f5303 CC |
161 | |
162 | /* delta islands */ | |
163 | unsigned int *tree_depth; | |
fe0ac2fb | 164 | unsigned char *layer; |
2834bc27 VM |
165 | }; |
166 | ||
43fa44fa | 167 | void prepare_packing_data(struct packing_data *pdata); |
9ac3f0e5 NTND |
168 | |
169 | static inline void packing_data_lock(struct packing_data *pdata) | |
170 | { | |
9ac3f0e5 | 171 | pthread_mutex_lock(&pdata->lock); |
9ac3f0e5 NTND |
172 | } |
173 | static inline void packing_data_unlock(struct packing_data *pdata) | |
174 | { | |
9ac3f0e5 | 175 | pthread_mutex_unlock(&pdata->lock); |
9ac3f0e5 NTND |
176 | } |
177 | ||
459307b1 PH |
178 | static inline void packing_data_read_lock(struct packing_data *pdata) |
179 | { | |
180 | pthread_mutex_lock(&pdata->read_lock); | |
181 | } | |
182 | static inline void packing_data_read_unlock(struct packing_data *pdata) | |
183 | { | |
184 | pthread_mutex_unlock(&pdata->read_lock); | |
185 | } | |
186 | ||
2834bc27 VM |
187 | struct object_entry *packlist_alloc(struct packing_data *pdata, |
188 | const unsigned char *sha1, | |
189 | uint32_t index_pos); | |
190 | ||
191 | struct object_entry *packlist_find(struct packing_data *pdata, | |
192 | const unsigned char *sha1, | |
193 | uint32_t *index_pos); | |
194 | ||
68fb36eb VM |
195 | static inline uint32_t pack_name_hash(const char *name) |
196 | { | |
197 | uint32_t c, hash = 0; | |
198 | ||
199 | if (!name) | |
200 | return 0; | |
201 | ||
202 | /* | |
203 | * This effectively just creates a sortable number from the | |
204 | * last sixteen non-whitespace characters. Last characters | |
205 | * count "most", so things that end in ".c" sort together. | |
206 | */ | |
207 | while ((c = *name++) != 0) { | |
208 | if (isspace(c)) | |
209 | continue; | |
210 | hash = (hash >> 2) + (c << 24); | |
211 | } | |
212 | return hash; | |
213 | } | |
214 | ||
fd9b1bae NTND |
215 | static inline enum object_type oe_type(const struct object_entry *e) |
216 | { | |
217 | return e->type_valid ? e->type_ : OBJ_BAD; | |
218 | } | |
219 | ||
220 | static inline void oe_set_type(struct object_entry *e, | |
221 | enum object_type type) | |
222 | { | |
223 | if (type >= OBJ_ANY) | |
224 | BUG("OBJ_ANY cannot be set in pack-objects code"); | |
225 | ||
226 | e->type_valid = type >= OBJ_NONE; | |
227 | e->type_ = (unsigned)type; | |
228 | } | |
229 | ||
06af3bba NTND |
230 | static inline unsigned int oe_in_pack_pos(const struct packing_data *pack, |
231 | const struct object_entry *e) | |
232 | { | |
233 | return pack->in_pack_pos[e - pack->objects]; | |
234 | } | |
235 | ||
236 | static inline void oe_set_in_pack_pos(const struct packing_data *pack, | |
237 | const struct object_entry *e, | |
238 | unsigned int pos) | |
239 | { | |
240 | pack->in_pack_pos[e - pack->objects] = pos; | |
241 | } | |
242 | ||
43fa44fa NTND |
243 | static inline struct packed_git *oe_in_pack(const struct packing_data *pack, |
244 | const struct object_entry *e) | |
245 | { | |
246 | if (pack->in_pack_by_idx) | |
247 | return pack->in_pack_by_idx[e->in_pack_idx]; | |
248 | else | |
249 | return pack->in_pack[e - pack->objects]; | |
250 | } | |
251 | ||
252 | void oe_map_new_pack(struct packing_data *pack, | |
253 | struct packed_git *p); | |
254 | static inline void oe_set_in_pack(struct packing_data *pack, | |
255 | struct object_entry *e, | |
256 | struct packed_git *p) | |
257 | { | |
258 | if (!p->index) | |
259 | oe_map_new_pack(pack, p); | |
260 | if (pack->in_pack_by_idx) | |
261 | e->in_pack_idx = p->index; | |
262 | else | |
263 | pack->in_pack[e - pack->objects] = p; | |
264 | } | |
265 | ||
898eba5e NTND |
266 | static inline struct object_entry *oe_delta( |
267 | const struct packing_data *pack, | |
268 | const struct object_entry *e) | |
269 | { | |
6a1e32d5 JK |
270 | if (!e->delta_idx) |
271 | return NULL; | |
272 | if (e->ext_base) | |
273 | return &pack->ext_bases[e->delta_idx - 1]; | |
274 | else | |
898eba5e | 275 | return &pack->objects[e->delta_idx - 1]; |
898eba5e NTND |
276 | } |
277 | ||
278 | static inline void oe_set_delta(struct packing_data *pack, | |
279 | struct object_entry *e, | |
280 | struct object_entry *delta) | |
281 | { | |
282 | if (delta) | |
283 | e->delta_idx = (delta - pack->objects) + 1; | |
284 | else | |
285 | e->delta_idx = 0; | |
286 | } | |
287 | ||
6a1e32d5 JK |
288 | void oe_set_delta_ext(struct packing_data *pack, |
289 | struct object_entry *e, | |
290 | const unsigned char *sha1); | |
291 | ||
898eba5e NTND |
292 | static inline struct object_entry *oe_delta_child( |
293 | const struct packing_data *pack, | |
294 | const struct object_entry *e) | |
295 | { | |
296 | if (e->delta_child_idx) | |
297 | return &pack->objects[e->delta_child_idx - 1]; | |
298 | return NULL; | |
299 | } | |
300 | ||
301 | static inline void oe_set_delta_child(struct packing_data *pack, | |
302 | struct object_entry *e, | |
303 | struct object_entry *delta) | |
304 | { | |
305 | if (delta) | |
306 | e->delta_child_idx = (delta - pack->objects) + 1; | |
307 | else | |
308 | e->delta_child_idx = 0; | |
309 | } | |
310 | ||
311 | static inline struct object_entry *oe_delta_sibling( | |
312 | const struct packing_data *pack, | |
313 | const struct object_entry *e) | |
314 | { | |
315 | if (e->delta_sibling_idx) | |
316 | return &pack->objects[e->delta_sibling_idx - 1]; | |
317 | return NULL; | |
318 | } | |
319 | ||
320 | static inline void oe_set_delta_sibling(struct packing_data *pack, | |
321 | struct object_entry *e, | |
322 | struct object_entry *delta) | |
323 | { | |
324 | if (delta) | |
325 | e->delta_sibling_idx = (delta - pack->objects) + 1; | |
326 | else | |
327 | e->delta_sibling_idx = 0; | |
328 | } | |
329 | ||
ac77d0c3 NTND |
330 | unsigned long oe_get_size_slow(struct packing_data *pack, |
331 | const struct object_entry *e); | |
332 | static inline unsigned long oe_size(struct packing_data *pack, | |
333 | const struct object_entry *e) | |
334 | { | |
335 | if (e->size_valid) | |
336 | return e->size_; | |
337 | ||
338 | return oe_get_size_slow(pack, e); | |
339 | } | |
340 | ||
341 | static inline int oe_size_less_than(struct packing_data *pack, | |
342 | const struct object_entry *lhs, | |
343 | unsigned long rhs) | |
344 | { | |
345 | if (lhs->size_valid) | |
346 | return lhs->size_ < rhs; | |
347 | if (rhs < pack->oe_size_limit) /* rhs < 2^x <= lhs ? */ | |
348 | return 0; | |
349 | return oe_get_size_slow(pack, lhs) < rhs; | |
350 | } | |
351 | ||
352 | static inline int oe_size_greater_than(struct packing_data *pack, | |
353 | const struct object_entry *lhs, | |
354 | unsigned long rhs) | |
355 | { | |
356 | if (lhs->size_valid) | |
357 | return lhs->size_ > rhs; | |
358 | if (rhs < pack->oe_size_limit) /* rhs < 2^x <= lhs ? */ | |
359 | return 1; | |
360 | return oe_get_size_slow(pack, lhs) > rhs; | |
361 | } | |
362 | ||
363 | static inline void oe_set_size(struct packing_data *pack, | |
364 | struct object_entry *e, | |
365 | unsigned long size) | |
366 | { | |
367 | if (size < pack->oe_size_limit) { | |
368 | e->size_ = size; | |
369 | e->size_valid = 1; | |
370 | } else { | |
371 | e->size_valid = 0; | |
372 | if (oe_get_size_slow(pack, e) != size) | |
373 | BUG("'size' is supposed to be the object size!"); | |
374 | } | |
375 | } | |
376 | ||
0aca34e8 NTND |
377 | static inline unsigned long oe_delta_size(struct packing_data *pack, |
378 | const struct object_entry *e) | |
379 | { | |
380 | if (e->delta_size_valid) | |
381 | return e->delta_size_; | |
9ac3f0e5 NTND |
382 | |
383 | /* | |
ce498e09 | 384 | * pack->delta_size[] can't be NULL because oe_set_delta_size() |
9ac3f0e5 NTND |
385 | * must have been called when a new delta is saved with |
386 | * oe_set_delta(). | |
387 | * If oe_delta() returns NULL (i.e. default state, which means | |
388 | * delta_size_valid is also false), then the caller must never | |
389 | * call oe_delta_size(). | |
390 | */ | |
391 | return pack->delta_size[e - pack->objects]; | |
0aca34e8 NTND |
392 | } |
393 | ||
394 | static inline void oe_set_delta_size(struct packing_data *pack, | |
395 | struct object_entry *e, | |
396 | unsigned long size) | |
397 | { | |
9ac3f0e5 NTND |
398 | if (size < pack->oe_delta_size_limit) { |
399 | e->delta_size_ = size; | |
400 | e->delta_size_valid = 1; | |
401 | } else { | |
402 | packing_data_lock(pack); | |
403 | if (!pack->delta_size) | |
404 | ALLOC_ARRAY(pack->delta_size, pack->nr_alloc); | |
405 | packing_data_unlock(pack); | |
406 | ||
407 | pack->delta_size[e - pack->objects] = size; | |
408 | e->delta_size_valid = 0; | |
409 | } | |
0aca34e8 NTND |
410 | } |
411 | ||
108f5303 CC |
412 | static inline unsigned int oe_tree_depth(struct packing_data *pack, |
413 | struct object_entry *e) | |
414 | { | |
415 | if (!pack->tree_depth) | |
416 | return 0; | |
417 | return pack->tree_depth[e - pack->objects]; | |
418 | } | |
419 | ||
420 | static inline void oe_set_tree_depth(struct packing_data *pack, | |
421 | struct object_entry *e, | |
422 | unsigned int tree_depth) | |
423 | { | |
424 | if (!pack->tree_depth) | |
e159b810 | 425 | CALLOC_ARRAY(pack->tree_depth, pack->nr_alloc); |
108f5303 CC |
426 | pack->tree_depth[e - pack->objects] = tree_depth; |
427 | } | |
428 | ||
fe0ac2fb CC |
429 | static inline unsigned char oe_layer(struct packing_data *pack, |
430 | struct object_entry *e) | |
431 | { | |
432 | if (!pack->layer) | |
433 | return 0; | |
434 | return pack->layer[e - pack->objects]; | |
435 | } | |
436 | ||
437 | static inline void oe_set_layer(struct packing_data *pack, | |
438 | struct object_entry *e, | |
439 | unsigned char layer) | |
440 | { | |
441 | if (!pack->layer) | |
e159b810 | 442 | CALLOC_ARRAY(pack->layer, pack->nr_alloc); |
fe0ac2fb CC |
443 | pack->layer[e - pack->objects] = layer; |
444 | } | |
445 | ||
2834bc27 | 446 | #endif |