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