]>
git.ipfire.org Git - thirdparty/git.git/blob - delta-islands.c
1 #include "git-compat-util.h"
11 #include "tree-walk.h"
14 #include "list-objects.h"
18 #include "pack-bitmap.h"
19 #include "pack-objects.h"
20 #include "delta-islands.h"
21 #include "oid-array.h"
24 KHASH_INIT(str
, const char *, void *, 1, kh_str_hash_func
, kh_str_hash_equal
)
26 static kh_oid_map_t
*island_marks
;
27 static unsigned island_counter
;
28 static unsigned island_counter_core
;
30 struct remote_island
{
32 struct oid_array oids
;
35 struct island_bitmap
{
37 uint32_t bits
[FLEX_ARRAY
];
40 static uint32_t island_bitmap_size
;
43 * Allocate a new bitmap; if "old" is not NULL, the new bitmap will be a copy
44 * of "old". Otherwise, the new bitmap is empty.
46 static struct island_bitmap
*island_bitmap_new(const struct island_bitmap
*old
)
48 size_t size
= sizeof(struct island_bitmap
) + (island_bitmap_size
* 4);
49 struct island_bitmap
*b
= xcalloc(1, size
);
58 static void island_bitmap_or(struct island_bitmap
*a
, const struct island_bitmap
*b
)
62 for (i
= 0; i
< island_bitmap_size
; ++i
)
63 a
->bits
[i
] |= b
->bits
[i
];
66 static int island_bitmap_is_subset(struct island_bitmap
*self
,
67 struct island_bitmap
*super
)
74 for (i
= 0; i
< island_bitmap_size
; ++i
) {
75 if ((self
->bits
[i
] & super
->bits
[i
]) != self
->bits
[i
])
82 #define ISLAND_BITMAP_BLOCK(x) (x / 32)
83 #define ISLAND_BITMAP_MASK(x) (1 << (x % 32))
85 static void island_bitmap_set(struct island_bitmap
*self
, uint32_t i
)
87 self
->bits
[ISLAND_BITMAP_BLOCK(i
)] |= ISLAND_BITMAP_MASK(i
);
90 static int island_bitmap_get(struct island_bitmap
*self
, uint32_t i
)
92 return (self
->bits
[ISLAND_BITMAP_BLOCK(i
)] & ISLAND_BITMAP_MASK(i
)) != 0;
95 int in_same_island(const struct object_id
*trg_oid
, const struct object_id
*src_oid
)
97 khiter_t trg_pos
, src_pos
;
99 /* If we aren't using islands, assume everything goes together. */
104 * If we don't have a bitmap for the target, we can delta it
105 * against anything -- it's not an important object
107 trg_pos
= kh_get_oid_map(island_marks
, *trg_oid
);
108 if (trg_pos
>= kh_end(island_marks
))
112 * if the source (our delta base) doesn't have a bitmap,
113 * we don't want to base any deltas on it!
115 src_pos
= kh_get_oid_map(island_marks
, *src_oid
);
116 if (src_pos
>= kh_end(island_marks
))
119 return island_bitmap_is_subset(kh_value(island_marks
, trg_pos
),
120 kh_value(island_marks
, src_pos
));
123 int island_delta_cmp(const struct object_id
*a
, const struct object_id
*b
)
125 khiter_t a_pos
, b_pos
;
126 struct island_bitmap
*a_bitmap
= NULL
, *b_bitmap
= NULL
;
131 a_pos
= kh_get_oid_map(island_marks
, *a
);
132 if (a_pos
< kh_end(island_marks
))
133 a_bitmap
= kh_value(island_marks
, a_pos
);
135 b_pos
= kh_get_oid_map(island_marks
, *b
);
136 if (b_pos
< kh_end(island_marks
))
137 b_bitmap
= kh_value(island_marks
, b_pos
);
140 if (!b_bitmap
|| !island_bitmap_is_subset(a_bitmap
, b_bitmap
))
144 if (!a_bitmap
|| !island_bitmap_is_subset(b_bitmap
, a_bitmap
))
151 static struct island_bitmap
*create_or_get_island_marks(struct object
*obj
)
156 pos
= kh_put_oid_map(island_marks
, obj
->oid
, &hash_ret
);
158 kh_value(island_marks
, pos
) = island_bitmap_new(NULL
);
160 return kh_value(island_marks
, pos
);
163 static void set_island_marks(struct object
*obj
, struct island_bitmap
*marks
)
165 struct island_bitmap
*b
;
169 pos
= kh_put_oid_map(island_marks
, obj
->oid
, &hash_ret
);
172 * We don't have one yet; make a copy-on-write of the
176 kh_value(island_marks
, pos
) = marks
;
181 * We do have it. Make sure we split any copy-on-write before
184 b
= kh_value(island_marks
, pos
);
185 if (b
->refcount
> 1) {
187 b
= kh_value(island_marks
, pos
) = island_bitmap_new(b
);
189 island_bitmap_or(b
, marks
);
192 static void mark_remote_island_1(struct repository
*r
,
193 struct remote_island
*rl
,
198 for (i
= 0; i
< rl
->oids
.nr
; ++i
) {
199 struct island_bitmap
*marks
;
200 struct object
*obj
= parse_object(r
, &rl
->oids
.oid
[i
]);
205 marks
= create_or_get_island_marks(obj
);
206 island_bitmap_set(marks
, island_counter
);
208 if (is_core_island
&& obj
->type
== OBJ_COMMIT
)
209 obj
->flags
|= NEEDS_BITMAP
;
211 /* If it was a tag, also make sure we hit the underlying object. */
212 while (obj
&& obj
->type
== OBJ_TAG
) {
213 obj
= ((struct tag
*)obj
)->tagged
;
215 parse_object(r
, &obj
->oid
);
216 marks
= create_or_get_island_marks(obj
);
217 island_bitmap_set(marks
, island_counter
);
223 island_counter_core
= island_counter
;
228 struct tree_islands_todo
{
229 struct object_entry
*entry
;
233 static int tree_depth_compare(const void *a
, const void *b
)
235 const struct tree_islands_todo
*todo_a
= a
;
236 const struct tree_islands_todo
*todo_b
= b
;
238 return todo_a
->depth
- todo_b
->depth
;
241 void resolve_tree_islands(struct repository
*r
,
243 struct packing_data
*to_pack
)
245 struct progress
*progress_state
= NULL
;
246 struct tree_islands_todo
*todo
;
254 * We process only trees, as commits and tags have already been handled
255 * (and passed their marks on to root trees, as well. We must make sure
256 * to process them in descending tree-depth order so that marks
257 * propagate down the tree properly, even if a sub-tree is found in
258 * multiple parent trees.
260 ALLOC_ARRAY(todo
, to_pack
->nr_objects
);
261 for (i
= 0; i
< to_pack
->nr_objects
; i
++) {
262 if (oe_type(&to_pack
->objects
[i
]) == OBJ_TREE
) {
263 todo
[nr
].entry
= &to_pack
->objects
[i
];
264 todo
[nr
].depth
= oe_tree_depth(to_pack
, &to_pack
->objects
[i
]);
268 QSORT(todo
, nr
, tree_depth_compare
);
271 progress_state
= start_progress(_("Propagating island marks"), nr
);
273 for (i
= 0; i
< nr
; i
++) {
274 struct object_entry
*ent
= todo
[i
].entry
;
275 struct island_bitmap
*root_marks
;
277 struct tree_desc desc
;
278 struct name_entry entry
;
281 pos
= kh_get_oid_map(island_marks
, ent
->idx
.oid
);
282 if (pos
>= kh_end(island_marks
))
285 root_marks
= kh_value(island_marks
, pos
);
287 tree
= lookup_tree(r
, &ent
->idx
.oid
);
288 if (!tree
|| parse_tree(tree
) < 0)
289 die(_("bad tree object %s"), oid_to_hex(&ent
->idx
.oid
));
291 init_tree_desc(&desc
, tree
->buffer
, tree
->size
);
292 while (tree_entry(&desc
, &entry
)) {
295 if (S_ISGITLINK(entry
.mode
))
298 obj
= lookup_object(r
, &entry
.oid
);
302 set_island_marks(obj
, root_marks
);
305 free_tree_buffer(tree
);
307 display_progress(progress_state
, i
+1);
310 stop_progress(&progress_state
);
314 struct island_load_data
{
315 kh_str_t
*remote_islands
;
320 static const char *core_island_name
;
322 static void free_config_regexes(struct island_load_data
*ild
)
324 for (size_t i
= 0; i
< ild
->nr
; i
++)
325 regfree(&ild
->rx
[i
]);
329 static void free_remote_islands(kh_str_t
*remote_islands
)
331 const char *island_name
;
332 struct remote_island
*rl
;
334 kh_foreach(remote_islands
, island_name
, rl
, {
335 free((void *)island_name
);
336 oid_array_clear(&rl
->oids
);
339 kh_destroy_str(remote_islands
);
342 static int island_config_callback(const char *k
, const char *v
, void *cb
)
344 struct island_load_data
*ild
= cb
;
346 if (!strcmp(k
, "pack.island")) {
347 struct strbuf re
= STRBUF_INIT
;
350 return config_error_nonbool(k
);
352 ALLOC_GROW(ild
->rx
, ild
->nr
+ 1, ild
->alloc
);
355 strbuf_addch(&re
, '^');
356 strbuf_addstr(&re
, v
);
358 if (regcomp(&ild
->rx
[ild
->nr
], re
.buf
, REG_EXTENDED
))
359 die(_("failed to load island regex for '%s': %s"), k
, re
.buf
);
366 if (!strcmp(k
, "pack.islandcore"))
367 return git_config_string(&core_island_name
, k
, v
);
372 static void add_ref_to_island(kh_str_t
*remote_islands
, const char *island_name
,
373 const struct object_id
*oid
)
376 struct remote_island
*rl
= NULL
;
379 khiter_t pos
= kh_put_str(remote_islands
, island_name
, &hash_ret
);
382 kh_key(remote_islands
, pos
) = xstrdup(island_name
);
383 kh_value(remote_islands
, pos
) = xcalloc(1, sizeof(struct remote_island
));
386 rl
= kh_value(remote_islands
, pos
);
387 oid_array_append(&rl
->oids
, oid
);
389 memcpy(&sha_core
, oid
->hash
, sizeof(uint64_t));
390 rl
->hash
+= sha_core
;
393 static int find_island_for_ref(const char *refname
, const struct object_id
*oid
,
394 int flags UNUSED
, void *cb
)
396 struct island_load_data
*ild
= cb
;
399 * We should advertise 'ARRAY_SIZE(matches) - 2' as the max,
400 * so we can diagnose below a config with more capture groups
403 regmatch_t matches
[16];
405 struct strbuf island_name
= STRBUF_INIT
;
407 /* walk backwards to get last-one-wins ordering */
408 for (i
= ild
->nr
- 1; i
>= 0; i
--) {
409 if (!regexec(&ild
->rx
[i
], refname
,
410 ARRAY_SIZE(matches
), matches
, 0))
417 if (matches
[ARRAY_SIZE(matches
) - 1].rm_so
!= -1)
418 warning(_("island regex from config has "
419 "too many capture groups (max=%d)"),
420 (int)ARRAY_SIZE(matches
) - 2);
422 for (m
= 1; m
< ARRAY_SIZE(matches
); m
++) {
423 regmatch_t
*match
= &matches
[m
];
425 if (match
->rm_so
== -1)
429 strbuf_addch(&island_name
, '-');
431 strbuf_add(&island_name
, refname
+ match
->rm_so
, match
->rm_eo
- match
->rm_so
);
434 add_ref_to_island(ild
->remote_islands
, island_name
.buf
, oid
);
435 strbuf_release(&island_name
);
439 static struct remote_island
*get_core_island(kh_str_t
*remote_islands
)
441 if (core_island_name
) {
442 khiter_t pos
= kh_get_str(remote_islands
, core_island_name
);
443 if (pos
< kh_end(remote_islands
))
444 return kh_value(remote_islands
, pos
);
450 static void deduplicate_islands(kh_str_t
*remote_islands
, struct repository
*r
)
452 struct remote_island
*island
, *core
= NULL
, **list
;
453 unsigned int island_count
, dst
, src
, ref
, i
= 0;
455 island_count
= kh_size(remote_islands
);
456 ALLOC_ARRAY(list
, island_count
);
458 kh_foreach_value(remote_islands
, island
, {
462 for (ref
= 0; ref
+ 1 < island_count
; ref
++) {
463 for (src
= ref
+ 1, dst
= src
; src
< island_count
; src
++) {
464 if (list
[ref
]->hash
== list
[src
]->hash
)
468 list
[dst
] = list
[src
];
475 island_bitmap_size
= (island_count
/ 32) + 1;
476 core
= get_core_island(remote_islands
);
478 for (i
= 0; i
< island_count
; ++i
) {
479 mark_remote_island_1(r
, list
[i
], core
&& list
[i
]->hash
== core
->hash
);
485 void load_delta_islands(struct repository
*r
, int progress
)
487 struct island_load_data ild
= { 0 };
489 island_marks
= kh_init_oid_map();
491 git_config(island_config_callback
, &ild
);
492 ild
.remote_islands
= kh_init_str();
493 for_each_ref(find_island_for_ref
, &ild
);
494 free_config_regexes(&ild
);
495 deduplicate_islands(ild
.remote_islands
, r
);
496 free_remote_islands(ild
.remote_islands
);
499 fprintf(stderr
, _("Marked %d islands, done.\n"), island_counter
);
502 void propagate_island_marks(struct commit
*commit
)
504 khiter_t pos
= kh_get_oid_map(island_marks
, commit
->object
.oid
);
506 if (pos
< kh_end(island_marks
)) {
507 struct commit_list
*p
;
508 struct island_bitmap
*root_marks
= kh_value(island_marks
, pos
);
510 parse_commit(commit
);
511 set_island_marks(&get_commit_tree(commit
)->object
, root_marks
);
512 for (p
= commit
->parents
; p
; p
= p
->next
)
513 set_island_marks(&p
->item
->object
, root_marks
);
517 void free_island_marks(void)
519 struct island_bitmap
*bitmap
;
521 kh_foreach_value(island_marks
, bitmap
, {
522 if (!--bitmap
->refcount
)
525 kh_destroy_oid_map(island_marks
);
527 /* detect use-after-free with a an address which is never valid: */
528 island_marks
= (void *)-1;
531 int compute_pack_layers(struct packing_data
*to_pack
)
535 if (!core_island_name
|| !island_marks
)
538 for (i
= 0; i
< to_pack
->nr_objects
; ++i
) {
539 struct object_entry
*entry
= &to_pack
->objects
[i
];
540 khiter_t pos
= kh_get_oid_map(island_marks
, entry
->idx
.oid
);
542 oe_set_layer(to_pack
, entry
, 1);
544 if (pos
< kh_end(island_marks
)) {
545 struct island_bitmap
*bitmap
= kh_value(island_marks
, pos
);
547 if (island_bitmap_get(bitmap
, island_counter_core
))
548 oe_set_layer(to_pack
, entry
, 0);