cache-tree.c: remove the_repository references
[git/git.git] / delta-islands.c
CommitLineData
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
23KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)
24
25static khash_sha1 *island_marks;
26static unsigned island_counter;
27static unsigned island_counter_core;
28
29static kh_str_t *remote_islands;
30
31struct remote_island {
32 uint64_t hash;
33 struct oid_array oids;
34};
35
36struct island_bitmap {
37 uint32_t refcount;
38 uint32_t bits[FLEX_ARRAY];
39};
40
41static 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 */
47static 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
59static 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
67static 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
86static 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
91static 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
96int 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
124int 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
152static 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
164static 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
193static 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
227struct tree_islands_todo {
228 struct object_entry *entry;
229 unsigned int depth;
230};
231
232static 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
240void 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
311static regex_t *island_regexes;
312static unsigned int island_regexes_alloc, island_regexes_nr;
313static const char *core_island_name;
314
315static 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
343static 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
363static 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
407static 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
418static 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
453void 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
465void 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
480int 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}