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