10 #include "tree-walk.h"
13 #include "list-objects.h"
17 #include "pack-bitmap.h"
18 #include "pack-objects.h"
19 #include "delta-islands.h"
20 #include "sha1-array.h"
23 KHASH_INIT(str
, const char *, void *, 1, kh_str_hash_func
, kh_str_hash_equal
)
25 static khash_sha1
*island_marks
;
26 static unsigned island_counter
;
27 static unsigned island_counter_core
;
29 static kh_str_t
*remote_islands
;
31 struct remote_island
{
33 struct oid_array oids
;
36 struct island_bitmap
{
38 uint32_t bits
[FLEX_ARRAY
];
41 static uint32_t island_bitmap_size
;
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.
47 static struct island_bitmap
*island_bitmap_new(const struct island_bitmap
*old
)
49 size_t size
= sizeof(struct island_bitmap
) + (island_bitmap_size
* 4);
50 struct island_bitmap
*b
= xcalloc(1, size
);
59 static void island_bitmap_or(struct island_bitmap
*a
, const struct island_bitmap
*b
)
63 for (i
= 0; i
< island_bitmap_size
; ++i
)
64 a
->bits
[i
] |= b
->bits
[i
];
67 static int island_bitmap_is_subset(struct island_bitmap
*self
,
68 struct island_bitmap
*super
)
75 for (i
= 0; i
< island_bitmap_size
; ++i
) {
76 if ((self
->bits
[i
] & super
->bits
[i
]) != self
->bits
[i
])
83 #define ISLAND_BITMAP_BLOCK(x) (x / 32)
84 #define ISLAND_BITMAP_MASK(x) (1 << (x % 32))
86 static void island_bitmap_set(struct island_bitmap
*self
, uint32_t i
)
88 self
->bits
[ISLAND_BITMAP_BLOCK(i
)] |= ISLAND_BITMAP_MASK(i
);
91 static int island_bitmap_get(struct island_bitmap
*self
, uint32_t i
)
93 return (self
->bits
[ISLAND_BITMAP_BLOCK(i
)] & ISLAND_BITMAP_MASK(i
)) != 0;
96 int in_same_island(const struct object_id
*trg_oid
, const struct object_id
*src_oid
)
98 khiter_t trg_pos
, src_pos
;
100 /* If we aren't using islands, assume everything goes together. */
105 * If we don't have a bitmap for the target, we can delta it
106 * against anything -- it's not an important object
108 trg_pos
= kh_get_sha1(island_marks
, trg_oid
->hash
);
109 if (trg_pos
>= kh_end(island_marks
))
113 * if the source (our delta base) doesn't have a bitmap,
114 * we don't want to base any deltas on it!
116 src_pos
= kh_get_sha1(island_marks
, src_oid
->hash
);
117 if (src_pos
>= kh_end(island_marks
))
120 return island_bitmap_is_subset(kh_value(island_marks
, trg_pos
),
121 kh_value(island_marks
, src_pos
));
124 int island_delta_cmp(const struct object_id
*a
, const struct object_id
*b
)
126 khiter_t a_pos
, b_pos
;
127 struct island_bitmap
*a_bitmap
= NULL
, *b_bitmap
= NULL
;
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
);
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
);
141 if (!b_bitmap
|| !island_bitmap_is_subset(a_bitmap
, b_bitmap
))
145 if (!a_bitmap
|| !island_bitmap_is_subset(b_bitmap
, a_bitmap
))
152 static struct island_bitmap
*create_or_get_island_marks(struct object
*obj
)
157 pos
= kh_put_sha1(island_marks
, obj
->oid
.hash
, &hash_ret
);
159 kh_value(island_marks
, pos
) = island_bitmap_new(NULL
);
161 return kh_value(island_marks
, pos
);
164 static void set_island_marks(struct object
*obj
, struct island_bitmap
*marks
)
166 struct island_bitmap
*b
;
170 pos
= kh_put_sha1(island_marks
, obj
->oid
.hash
, &hash_ret
);
173 * We don't have one yet; make a copy-on-write of the
177 kh_value(island_marks
, pos
) = marks
;
182 * We do have it. Make sure we split any copy-on-write before
185 b
= kh_value(island_marks
, pos
);
186 if (b
->refcount
> 1) {
188 b
= kh_value(island_marks
, pos
) = island_bitmap_new(b
);
190 island_bitmap_or(b
, marks
);
193 static void mark_remote_island_1(struct remote_island
*rl
, int is_core_island
)
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
]);
204 marks
= create_or_get_island_marks(obj
);
205 island_bitmap_set(marks
, island_counter
);
207 if (is_core_island
&& obj
->type
== OBJ_COMMIT
)
208 obj
->flags
|= NEEDS_BITMAP
;
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
;
214 parse_object(the_repository
, &obj
->oid
);
215 marks
= create_or_get_island_marks(obj
);
216 island_bitmap_set(marks
, island_counter
);
222 island_counter_core
= island_counter
;
227 static int cmp_tree_depth(const void *va
, const void *vb
)
229 struct object_entry
*a
= *(struct object_entry
**)va
;
230 struct object_entry
*b
= *(struct object_entry
**)vb
;
231 return a
->tree_depth
- b
->tree_depth
;
234 void resolve_tree_islands(int progress
, struct packing_data
*to_pack
)
236 struct progress
*progress_state
= NULL
;
237 struct object_entry
**todo
;
245 * We process only trees, as commits and tags have already been handled
246 * (and passed their marks on to root trees, as well. We must make sure
247 * to process them in descending tree-depth order so that marks
248 * propagate down the tree properly, even if a sub-tree is found in
249 * multiple parent trees.
251 ALLOC_ARRAY(todo
, to_pack
->nr_objects
);
252 for (i
= 0; i
< to_pack
->nr_objects
; i
++) {
253 if (oe_type(&to_pack
->objects
[i
]) == OBJ_TREE
)
254 todo
[nr
++] = &to_pack
->objects
[i
];
256 QSORT(todo
, nr
, cmp_tree_depth
);
259 progress_state
= start_progress(_("Propagating island marks"), nr
);
261 for (i
= 0; i
< nr
; i
++) {
262 struct object_entry
*ent
= todo
[i
];
263 struct island_bitmap
*root_marks
;
265 struct tree_desc desc
;
266 struct name_entry entry
;
269 pos
= kh_get_sha1(island_marks
, ent
->idx
.oid
.hash
);
270 if (pos
>= kh_end(island_marks
))
273 root_marks
= kh_value(island_marks
, pos
);
275 tree
= lookup_tree(the_repository
, &ent
->idx
.oid
);
276 if (!tree
|| parse_tree(tree
) < 0)
277 die(_("bad tree object %s"), oid_to_hex(&ent
->idx
.oid
));
279 init_tree_desc(&desc
, tree
->buffer
, tree
->size
);
280 while (tree_entry(&desc
, &entry
)) {
283 if (S_ISGITLINK(entry
.mode
))
286 obj
= lookup_object(the_repository
, entry
.oid
->hash
);
290 set_island_marks(obj
, root_marks
);
293 free_tree_buffer(tree
);
295 display_progress(progress_state
, i
+1);
298 stop_progress(&progress_state
);
302 static regex_t
*island_regexes
;
303 static unsigned int island_regexes_alloc
, island_regexes_nr
;
304 static const char *core_island_name
;
306 static int island_config_callback(const char *k
, const char *v
, void *cb
)
308 if (!strcmp(k
, "pack.island")) {
309 struct strbuf re
= STRBUF_INIT
;
312 return config_error_nonbool(k
);
314 ALLOC_GROW(island_regexes
, island_regexes_nr
+ 1, island_regexes_alloc
);
317 strbuf_addch(&re
, '^');
318 strbuf_addstr(&re
, v
);
320 if (regcomp(&island_regexes
[island_regexes_nr
], re
.buf
, REG_EXTENDED
))
321 die(_("failed to load island regex for '%s': %s"), k
, re
.buf
);
328 if (!strcmp(k
, "pack.islandcore"))
329 return git_config_string(&core_island_name
, k
, v
);
334 static void add_ref_to_island(const char *island_name
, const struct object_id
*oid
)
337 struct remote_island
*rl
= NULL
;
340 khiter_t pos
= kh_put_str(remote_islands
, island_name
, &hash_ret
);
343 kh_key(remote_islands
, pos
) = xstrdup(island_name
);
344 kh_value(remote_islands
, pos
) = xcalloc(1, sizeof(struct remote_island
));
347 rl
= kh_value(remote_islands
, pos
);
348 oid_array_append(&rl
->oids
, oid
);
350 memcpy(&sha_core
, oid
->hash
, sizeof(uint64_t));
351 rl
->hash
+= sha_core
;
354 static int find_island_for_ref(const char *refname
, const struct object_id
*oid
,
355 int flags
, void *data
)
358 * We should advertise 'ARRAY_SIZE(matches) - 2' as the max,
359 * so we can diagnose below a config with more capture groups
362 regmatch_t matches
[16];
364 struct strbuf island_name
= STRBUF_INIT
;
366 /* walk backwards to get last-one-wins ordering */
367 for (i
= island_regexes_nr
- 1; i
>= 0; i
--) {
368 if (!regexec(&island_regexes
[i
], refname
,
369 ARRAY_SIZE(matches
), matches
, 0))
376 if (matches
[ARRAY_SIZE(matches
) - 1].rm_so
!= -1)
377 warning(_("island regex from config has "
378 "too many capture groups (max=%d)"),
379 (int)ARRAY_SIZE(matches
) - 2);
381 for (m
= 1; m
< ARRAY_SIZE(matches
); m
++) {
382 regmatch_t
*match
= &matches
[m
];
384 if (match
->rm_so
== -1)
388 strbuf_addch(&island_name
, '-');
390 strbuf_add(&island_name
, refname
+ match
->rm_so
, match
->rm_eo
- match
->rm_so
);
393 add_ref_to_island(island_name
.buf
, oid
);
394 strbuf_release(&island_name
);
398 static struct remote_island
*get_core_island(void)
400 if (core_island_name
) {
401 khiter_t pos
= kh_get_str(remote_islands
, core_island_name
);
402 if (pos
< kh_end(remote_islands
))
403 return kh_value(remote_islands
, pos
);
409 static void deduplicate_islands(void)
411 struct remote_island
*island
, *core
= NULL
, **list
;
412 unsigned int island_count
, dst
, src
, ref
, i
= 0;
414 island_count
= kh_size(remote_islands
);
415 ALLOC_ARRAY(list
, island_count
);
417 kh_foreach_value(remote_islands
, island
, {
421 for (ref
= 0; ref
+ 1 < island_count
; ref
++) {
422 for (src
= ref
+ 1, dst
= src
; src
< island_count
; src
++) {
423 if (list
[ref
]->hash
== list
[src
]->hash
)
427 list
[dst
] = list
[src
];
434 island_bitmap_size
= (island_count
/ 32) + 1;
435 core
= get_core_island();
437 for (i
= 0; i
< island_count
; ++i
) {
438 mark_remote_island_1(list
[i
], core
&& list
[i
]->hash
== core
->hash
);
444 void load_delta_islands(void)
446 island_marks
= kh_init_sha1();
447 remote_islands
= kh_init_str();
449 git_config(island_config_callback
, NULL
);
450 for_each_ref(find_island_for_ref
, NULL
);
451 deduplicate_islands();
453 fprintf(stderr
, _("Marked %d islands, done.\n"), island_counter
);
456 void propagate_island_marks(struct commit
*commit
)
458 khiter_t pos
= kh_get_sha1(island_marks
, commit
->object
.oid
.hash
);
460 if (pos
< kh_end(island_marks
)) {
461 struct commit_list
*p
;
462 struct island_bitmap
*root_marks
= kh_value(island_marks
, pos
);
464 parse_commit(commit
);
465 set_island_marks(&get_commit_tree(commit
)->object
, root_marks
);
466 for (p
= commit
->parents
; p
; p
= p
->next
)
467 set_island_marks(&p
->item
->object
, root_marks
);
471 int compute_pack_layers(struct packing_data
*to_pack
)
475 if (!core_island_name
|| !island_marks
)
478 for (i
= 0; i
< to_pack
->nr_objects
; ++i
) {
479 struct object_entry
*entry
= &to_pack
->objects
[i
];
480 khiter_t pos
= kh_get_sha1(island_marks
, entry
->idx
.oid
.hash
);
484 if (pos
< kh_end(island_marks
)) {
485 struct island_bitmap
*bitmap
= kh_value(island_marks
, pos
);
487 if (island_bitmap_get(bitmap
, island_counter_core
))