git

1
#define USE_THE_REPOSITORY_VARIABLE
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

22
KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)
23

24
static kh_oid_map_t *island_marks;
25
static unsigned island_counter;
26
static unsigned island_counter_core;
27

28
struct remote_island {
29
	uint64_t hash;
30
	struct oid_array oids;
31
};
32

33
struct island_bitmap {
34
	uint32_t refcount;
35
	uint32_t bits[FLEX_ARRAY];
36
};
37

38
static 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
 */
44
static 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

56
static 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

64
static 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

83
static 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

88
static 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

93
int 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

121
int 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

149
static 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

161
static 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

190
static 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

226
struct tree_islands_todo {
227
	struct object_entry *entry;
228
	unsigned int depth;
229
};
230

231
static 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

239
void 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(_("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

312
struct island_load_data {
313
	kh_str_t *remote_islands;
314
	regex_t *rx;
315
	size_t nr;
316
	size_t alloc;
317
};
318
static char *core_island_name;
319

320
static 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

327
static 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

340
static 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

372
static 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

393
static 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

439
static 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

450
static 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

485
void 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
	git_config(island_config_callback, &ild);
492
	ild.remote_islands = kh_init_str();
493
	refs_for_each_ref(get_main_ref_store(the_repository),
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

503
void propagate_island_marks(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(the_repository, commit);
512
		set_island_marks(&repo_get_commit_tree(the_repository, 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

519
void 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

535
int 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
}
558