]>
Commit | Line | Data |
---|---|---|
c8d521fa JK |
1 | #include "cache.h" |
2 | #include "attr.h" | |
3 | #include "object.h" | |
4 | #include "blob.h" | |
5 | #include "commit.h" | |
6 | #include "tag.h" | |
7 | #include "tree.h" | |
8 | #include "delta.h" | |
9 | #include "pack.h" | |
10 | #include "tree-walk.h" | |
11 | #include "diff.h" | |
12 | #include "revision.h" | |
13 | #include "list-objects.h" | |
14 | #include "progress.h" | |
15 | #include "refs.h" | |
16 | #include "khash.h" | |
17 | #include "pack-bitmap.h" | |
18 | #include "pack-objects.h" | |
19 | #include "delta-islands.h" | |
20 | #include "sha1-array.h" | |
21 | #include "config.h" | |
22 | ||
23 | KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal) | |
24 | ||
25 | static khash_sha1 *island_marks; | |
26 | static unsigned island_counter; | |
27 | static unsigned island_counter_core; | |
28 | ||
29 | static kh_str_t *remote_islands; | |
30 | ||
31 | struct remote_island { | |
32 | uint64_t hash; | |
33 | struct oid_array oids; | |
34 | }; | |
35 | ||
36 | struct island_bitmap { | |
37 | uint32_t refcount; | |
38 | uint32_t bits[FLEX_ARRAY]; | |
39 | }; | |
40 | ||
41 | static uint32_t island_bitmap_size; | |
42 | ||
43 | /* | |
44 | * Allocate a new bitmap; if "old" is not NULL, the new bitmap will be a copy | |
45 | * of "old". Otherwise, the new bitmap is empty. | |
46 | */ | |
47 | static struct island_bitmap *island_bitmap_new(const struct island_bitmap *old) | |
48 | { | |
49 | size_t size = sizeof(struct island_bitmap) + (island_bitmap_size * 4); | |
50 | struct island_bitmap *b = xcalloc(1, size); | |
51 | ||
52 | if (old) | |
53 | memcpy(b, old, size); | |
54 | ||
55 | b->refcount = 1; | |
56 | return b; | |
57 | } | |
58 | ||
59 | static void island_bitmap_or(struct island_bitmap *a, const struct island_bitmap *b) | |
60 | { | |
61 | uint32_t i; | |
62 | ||
63 | for (i = 0; i < island_bitmap_size; ++i) | |
64 | a->bits[i] |= b->bits[i]; | |
65 | } | |
66 | ||
67 | static int island_bitmap_is_subset(struct island_bitmap *self, | |
68 | struct island_bitmap *super) | |
69 | { | |
70 | uint32_t i; | |
71 | ||
72 | if (self == super) | |
73 | return 1; | |
74 | ||
75 | for (i = 0; i < island_bitmap_size; ++i) { | |
76 | if ((self->bits[i] & super->bits[i]) != self->bits[i]) | |
77 | return 0; | |
78 | } | |
79 | ||
80 | return 1; | |
81 | } | |
82 | ||
83 | #define ISLAND_BITMAP_BLOCK(x) (x / 32) | |
84 | #define ISLAND_BITMAP_MASK(x) (1 << (x % 32)) | |
85 | ||
86 | static void island_bitmap_set(struct island_bitmap *self, uint32_t i) | |
87 | { | |
88 | self->bits[ISLAND_BITMAP_BLOCK(i)] |= ISLAND_BITMAP_MASK(i); | |
89 | } | |
90 | ||
91 | static int island_bitmap_get(struct island_bitmap *self, uint32_t i) | |
92 | { | |
93 | return (self->bits[ISLAND_BITMAP_BLOCK(i)] & ISLAND_BITMAP_MASK(i)) != 0; | |
94 | } | |
95 | ||
96 | int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid) | |
97 | { | |
98 | khiter_t trg_pos, src_pos; | |
99 | ||
100 | /* If we aren't using islands, assume everything goes together. */ | |
101 | if (!island_marks) | |
102 | return 1; | |
103 | ||
104 | /* | |
105 | * If we don't have a bitmap for the target, we can delta it | |
106 | * against anything -- it's not an important object | |
107 | */ | |
108 | trg_pos = kh_get_sha1(island_marks, trg_oid->hash); | |
109 | if (trg_pos >= kh_end(island_marks)) | |
110 | return 1; | |
111 | ||
112 | /* | |
113 | * if the source (our delta base) doesn't have a bitmap, | |
114 | * we don't want to base any deltas on it! | |
115 | */ | |
116 | src_pos = kh_get_sha1(island_marks, src_oid->hash); | |
117 | if (src_pos >= kh_end(island_marks)) | |
118 | return 0; | |
119 | ||
120 | return island_bitmap_is_subset(kh_value(island_marks, trg_pos), | |
121 | kh_value(island_marks, src_pos)); | |
122 | } | |
123 | ||
124 | int island_delta_cmp(const struct object_id *a, const struct object_id *b) | |
125 | { | |
126 | khiter_t a_pos, b_pos; | |
127 | struct island_bitmap *a_bitmap = NULL, *b_bitmap = NULL; | |
128 | ||
129 | if (!island_marks) | |
130 | return 0; | |
131 | ||
132 | a_pos = kh_get_sha1(island_marks, a->hash); | |
133 | if (a_pos < kh_end(island_marks)) | |
134 | a_bitmap = kh_value(island_marks, a_pos); | |
135 | ||
136 | b_pos = kh_get_sha1(island_marks, b->hash); | |
137 | if (b_pos < kh_end(island_marks)) | |
138 | b_bitmap = kh_value(island_marks, b_pos); | |
139 | ||
140 | if (a_bitmap) { | |
141 | if (!b_bitmap || !island_bitmap_is_subset(a_bitmap, b_bitmap)) | |
142 | return -1; | |
143 | } | |
144 | if (b_bitmap) { | |
145 | if (!a_bitmap || !island_bitmap_is_subset(b_bitmap, a_bitmap)) | |
146 | return 1; | |
147 | } | |
148 | ||
149 | return 0; | |
150 | } | |
151 | ||
152 | static struct island_bitmap *create_or_get_island_marks(struct object *obj) | |
153 | { | |
154 | khiter_t pos; | |
155 | int hash_ret; | |
156 | ||
157 | pos = kh_put_sha1(island_marks, obj->oid.hash, &hash_ret); | |
158 | if (hash_ret) | |
159 | kh_value(island_marks, pos) = island_bitmap_new(NULL); | |
160 | ||
161 | return kh_value(island_marks, pos); | |
162 | } | |
163 | ||
164 | static void set_island_marks(struct object *obj, struct island_bitmap *marks) | |
165 | { | |
166 | struct island_bitmap *b; | |
167 | khiter_t pos; | |
168 | int hash_ret; | |
169 | ||
170 | pos = kh_put_sha1(island_marks, obj->oid.hash, &hash_ret); | |
171 | if (hash_ret) { | |
172 | /* | |
173 | * We don't have one yet; make a copy-on-write of the | |
174 | * parent. | |
175 | */ | |
176 | marks->refcount++; | |
177 | kh_value(island_marks, pos) = marks; | |
178 | return; | |
179 | } | |
180 | ||
181 | /* | |
182 | * We do have it. Make sure we split any copy-on-write before | |
183 | * updating. | |
184 | */ | |
185 | b = kh_value(island_marks, pos); | |
186 | if (b->refcount > 1) { | |
187 | b->refcount--; | |
188 | b = kh_value(island_marks, pos) = island_bitmap_new(b); | |
189 | } | |
190 | island_bitmap_or(b, marks); | |
191 | } | |
192 | ||
193 | static void mark_remote_island_1(struct remote_island *rl, int is_core_island) | |
194 | { | |
195 | uint32_t i; | |
196 | ||
197 | for (i = 0; i < rl->oids.nr; ++i) { | |
198 | struct island_bitmap *marks; | |
199 | struct object *obj = parse_object(the_repository, &rl->oids.oid[i]); | |
200 | ||
201 | if (!obj) | |
202 | continue; | |
203 | ||
204 | marks = create_or_get_island_marks(obj); | |
205 | island_bitmap_set(marks, island_counter); | |
206 | ||
207 | if (is_core_island && obj->type == OBJ_COMMIT) | |
208 | obj->flags |= NEEDS_BITMAP; | |
209 | ||
210 | /* If it was a tag, also make sure we hit the underlying object. */ | |
211 | while (obj && obj->type == OBJ_TAG) { | |
212 | obj = ((struct tag *)obj)->tagged; | |
213 | if (obj) { | |
214 | parse_object(the_repository, &obj->oid); | |
215 | marks = create_or_get_island_marks(obj); | |
216 | island_bitmap_set(marks, island_counter); | |
217 | } | |
218 | } | |
219 | } | |
220 | ||
221 | if (is_core_island) | |
222 | island_counter_core = island_counter; | |
223 | ||
224 | island_counter++; | |
225 | } | |
226 | ||
108f5303 CC |
227 | struct tree_islands_todo { |
228 | struct object_entry *entry; | |
229 | unsigned int depth; | |
230 | }; | |
231 | ||
232 | static int tree_depth_compare(const void *a, const void *b) | |
c8d521fa | 233 | { |
108f5303 CC |
234 | const struct tree_islands_todo *todo_a = a; |
235 | const struct tree_islands_todo *todo_b = b; | |
236 | ||
237 | return todo_a->depth - todo_b->depth; | |
c8d521fa JK |
238 | } |
239 | ||
240 | void resolve_tree_islands(int progress, struct packing_data *to_pack) | |
241 | { | |
242 | struct progress *progress_state = NULL; | |
108f5303 | 243 | struct tree_islands_todo *todo; |
c8d521fa JK |
244 | int nr = 0; |
245 | int i; | |
246 | ||
247 | if (!island_marks) | |
248 | return; | |
249 | ||
250 | /* | |
251 | * We process only trees, as commits and tags have already been handled | |
252 | * (and passed their marks on to root trees, as well. We must make sure | |
253 | * to process them in descending tree-depth order so that marks | |
254 | * propagate down the tree properly, even if a sub-tree is found in | |
255 | * multiple parent trees. | |
256 | */ | |
257 | ALLOC_ARRAY(todo, to_pack->nr_objects); | |
258 | for (i = 0; i < to_pack->nr_objects; i++) { | |
108f5303 CC |
259 | if (oe_type(&to_pack->objects[i]) == OBJ_TREE) { |
260 | todo[nr].entry = &to_pack->objects[i]; | |
261 | todo[nr].depth = oe_tree_depth(to_pack, &to_pack->objects[i]); | |
262 | nr++; | |
263 | } | |
c8d521fa | 264 | } |
108f5303 | 265 | QSORT(todo, nr, tree_depth_compare); |
c8d521fa JK |
266 | |
267 | if (progress) | |
268 | progress_state = start_progress(_("Propagating island marks"), nr); | |
269 | ||
270 | for (i = 0; i < nr; i++) { | |
108f5303 | 271 | struct object_entry *ent = todo[i].entry; |
c8d521fa JK |
272 | struct island_bitmap *root_marks; |
273 | struct tree *tree; | |
274 | struct tree_desc desc; | |
275 | struct name_entry entry; | |
276 | khiter_t pos; | |
277 | ||
278 | pos = kh_get_sha1(island_marks, ent->idx.oid.hash); | |
279 | if (pos >= kh_end(island_marks)) | |
280 | continue; | |
281 | ||
282 | root_marks = kh_value(island_marks, pos); | |
283 | ||
284 | tree = lookup_tree(the_repository, &ent->idx.oid); | |
285 | if (!tree || parse_tree(tree) < 0) | |
286 | die(_("bad tree object %s"), oid_to_hex(&ent->idx.oid)); | |
287 | ||
288 | init_tree_desc(&desc, tree->buffer, tree->size); | |
289 | while (tree_entry(&desc, &entry)) { | |
290 | struct object *obj; | |
291 | ||
292 | if (S_ISGITLINK(entry.mode)) | |
293 | continue; | |
294 | ||
295 | obj = lookup_object(the_repository, entry.oid->hash); | |
296 | if (!obj) | |
297 | continue; | |
298 | ||
299 | set_island_marks(obj, root_marks); | |
300 | } | |
301 | ||
302 | free_tree_buffer(tree); | |
303 | ||
304 | display_progress(progress_state, i+1); | |
305 | } | |
306 | ||
307 | stop_progress(&progress_state); | |
308 | free(todo); | |
309 | } | |
310 | ||
311 | static regex_t *island_regexes; | |
312 | static unsigned int island_regexes_alloc, island_regexes_nr; | |
313 | static const char *core_island_name; | |
314 | ||
315 | static int island_config_callback(const char *k, const char *v, void *cb) | |
316 | { | |
317 | if (!strcmp(k, "pack.island")) { | |
318 | struct strbuf re = STRBUF_INIT; | |
319 | ||
320 | if (!v) | |
321 | return config_error_nonbool(k); | |
322 | ||
323 | ALLOC_GROW(island_regexes, island_regexes_nr + 1, island_regexes_alloc); | |
324 | ||
325 | if (*v != '^') | |
326 | strbuf_addch(&re, '^'); | |
327 | strbuf_addstr(&re, v); | |
328 | ||
329 | if (regcomp(&island_regexes[island_regexes_nr], re.buf, REG_EXTENDED)) | |
330 | die(_("failed to load island regex for '%s': %s"), k, re.buf); | |
331 | ||
332 | strbuf_release(&re); | |
333 | island_regexes_nr++; | |
334 | return 0; | |
335 | } | |
336 | ||
337 | if (!strcmp(k, "pack.islandcore")) | |
338 | return git_config_string(&core_island_name, k, v); | |
339 | ||
340 | return 0; | |
341 | } | |
342 | ||
343 | static void add_ref_to_island(const char *island_name, const struct object_id *oid) | |
344 | { | |
345 | uint64_t sha_core; | |
346 | struct remote_island *rl = NULL; | |
347 | ||
348 | int hash_ret; | |
349 | khiter_t pos = kh_put_str(remote_islands, island_name, &hash_ret); | |
350 | ||
351 | if (hash_ret) { | |
352 | kh_key(remote_islands, pos) = xstrdup(island_name); | |
353 | kh_value(remote_islands, pos) = xcalloc(1, sizeof(struct remote_island)); | |
354 | } | |
355 | ||
356 | rl = kh_value(remote_islands, pos); | |
357 | oid_array_append(&rl->oids, oid); | |
358 | ||
359 | memcpy(&sha_core, oid->hash, sizeof(uint64_t)); | |
360 | rl->hash += sha_core; | |
361 | } | |
362 | ||
363 | static int find_island_for_ref(const char *refname, const struct object_id *oid, | |
364 | int flags, void *data) | |
365 | { | |
366 | /* | |
367 | * We should advertise 'ARRAY_SIZE(matches) - 2' as the max, | |
368 | * so we can diagnose below a config with more capture groups | |
369 | * than we support. | |
370 | */ | |
371 | regmatch_t matches[16]; | |
372 | int i, m; | |
373 | struct strbuf island_name = STRBUF_INIT; | |
374 | ||
375 | /* walk backwards to get last-one-wins ordering */ | |
376 | for (i = island_regexes_nr - 1; i >= 0; i--) { | |
377 | if (!regexec(&island_regexes[i], refname, | |
378 | ARRAY_SIZE(matches), matches, 0)) | |
379 | break; | |
380 | } | |
381 | ||
382 | if (i < 0) | |
383 | return 0; | |
384 | ||
385 | if (matches[ARRAY_SIZE(matches) - 1].rm_so != -1) | |
386 | warning(_("island regex from config has " | |
387 | "too many capture groups (max=%d)"), | |
388 | (int)ARRAY_SIZE(matches) - 2); | |
389 | ||
390 | for (m = 1; m < ARRAY_SIZE(matches); m++) { | |
391 | regmatch_t *match = &matches[m]; | |
392 | ||
393 | if (match->rm_so == -1) | |
394 | continue; | |
395 | ||
396 | if (island_name.len) | |
397 | strbuf_addch(&island_name, '-'); | |
398 | ||
399 | strbuf_add(&island_name, refname + match->rm_so, match->rm_eo - match->rm_so); | |
400 | } | |
401 | ||
402 | add_ref_to_island(island_name.buf, oid); | |
403 | strbuf_release(&island_name); | |
404 | return 0; | |
405 | } | |
406 | ||
407 | static struct remote_island *get_core_island(void) | |
408 | { | |
409 | if (core_island_name) { | |
410 | khiter_t pos = kh_get_str(remote_islands, core_island_name); | |
411 | if (pos < kh_end(remote_islands)) | |
412 | return kh_value(remote_islands, pos); | |
413 | } | |
414 | ||
415 | return NULL; | |
416 | } | |
417 | ||
418 | static void deduplicate_islands(void) | |
419 | { | |
420 | struct remote_island *island, *core = NULL, **list; | |
421 | unsigned int island_count, dst, src, ref, i = 0; | |
422 | ||
423 | island_count = kh_size(remote_islands); | |
424 | ALLOC_ARRAY(list, island_count); | |
425 | ||
426 | kh_foreach_value(remote_islands, island, { | |
427 | list[i++] = island; | |
428 | }); | |
429 | ||
430 | for (ref = 0; ref + 1 < island_count; ref++) { | |
431 | for (src = ref + 1, dst = src; src < island_count; src++) { | |
432 | if (list[ref]->hash == list[src]->hash) | |
433 | continue; | |
434 | ||
435 | if (src != dst) | |
436 | list[dst] = list[src]; | |
437 | ||
438 | dst++; | |
439 | } | |
440 | island_count = dst; | |
441 | } | |
442 | ||
443 | island_bitmap_size = (island_count / 32) + 1; | |
444 | core = get_core_island(); | |
445 | ||
446 | for (i = 0; i < island_count; ++i) { | |
447 | mark_remote_island_1(list[i], core && list[i]->hash == core->hash); | |
448 | } | |
449 | ||
450 | free(list); | |
451 | } | |
452 | ||
453 | void load_delta_islands(void) | |
454 | { | |
455 | island_marks = kh_init_sha1(); | |
456 | remote_islands = kh_init_str(); | |
457 | ||
458 | git_config(island_config_callback, NULL); | |
459 | for_each_ref(find_island_for_ref, NULL); | |
460 | deduplicate_islands(); | |
461 | ||
462 | fprintf(stderr, _("Marked %d islands, done.\n"), island_counter); | |
463 | } | |
464 | ||
465 | void propagate_island_marks(struct commit *commit) | |
466 | { | |
467 | khiter_t pos = kh_get_sha1(island_marks, commit->object.oid.hash); | |
468 | ||
469 | if (pos < kh_end(island_marks)) { | |
470 | struct commit_list *p; | |
471 | struct island_bitmap *root_marks = kh_value(island_marks, pos); | |
472 | ||
473 | parse_commit(commit); | |
474 | set_island_marks(&get_commit_tree(commit)->object, root_marks); | |
475 | for (p = commit->parents; p; p = p->next) | |
476 | set_island_marks(&p->item->object, root_marks); | |
477 | } | |
478 | } | |
479 | ||
480 | int compute_pack_layers(struct packing_data *to_pack) | |
481 | { | |
482 | uint32_t i; | |
483 | ||
484 | if (!core_island_name || !island_marks) | |
485 | return 1; | |
486 | ||
487 | for (i = 0; i < to_pack->nr_objects; ++i) { | |
488 | struct object_entry *entry = &to_pack->objects[i]; | |
489 | khiter_t pos = kh_get_sha1(island_marks, entry->idx.oid.hash); | |
490 | ||
fe0ac2fb | 491 | oe_set_layer(to_pack, entry, 1); |
c8d521fa JK |
492 | |
493 | if (pos < kh_end(island_marks)) { | |
494 | struct island_bitmap *bitmap = kh_value(island_marks, pos); | |
495 | ||
496 | if (island_bitmap_get(bitmap, island_counter_core)) | |
fe0ac2fb | 497 | oe_set_layer(to_pack, entry, 0); |
c8d521fa JK |
498 | } |
499 | } | |
500 | ||
501 | return 2; | |
502 | } |