THIS IS A TEST INSTANCE ONLY! REPOSITORIES CAN BE DELETED AT ANY TIME!

Git Source Code Mirror - This is a publish-only repository and all pull requests are ignored. Please follow Documentation/SubmittingPatches procedure for any of your improvements.
git
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

508 lines
12KB

  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. KHASH_INIT(str, const char *, void *, 1, kh_str_hash_func, kh_str_hash_equal)
  23. static kh_oid_map_t *island_marks;
  24. static unsigned island_counter;
  25. static unsigned island_counter_core;
  26. static kh_str_t *remote_islands;
  27. struct remote_island {
  28. uint64_t hash;
  29. struct oid_array oids;
  30. };
  31. struct island_bitmap {
  32. uint32_t refcount;
  33. uint32_t bits[FLEX_ARRAY];
  34. };
  35. static uint32_t island_bitmap_size;
  36. /*
  37. * Allocate a new bitmap; if "old" is not NULL, the new bitmap will be a copy
  38. * of "old". Otherwise, the new bitmap is empty.
  39. */
  40. static struct island_bitmap *island_bitmap_new(const struct island_bitmap *old)
  41. {
  42. size_t size = sizeof(struct island_bitmap) + (island_bitmap_size * 4);
  43. struct island_bitmap *b = xcalloc(1, size);
  44. if (old)
  45. memcpy(b, old, size);
  46. b->refcount = 1;
  47. return b;
  48. }
  49. static void island_bitmap_or(struct island_bitmap *a, const struct island_bitmap *b)
  50. {
  51. uint32_t i;
  52. for (i = 0; i < island_bitmap_size; ++i)
  53. a->bits[i] |= b->bits[i];
  54. }
  55. static int island_bitmap_is_subset(struct island_bitmap *self,
  56. struct island_bitmap *super)
  57. {
  58. uint32_t i;
  59. if (self == super)
  60. return 1;
  61. for (i = 0; i < island_bitmap_size; ++i) {
  62. if ((self->bits[i] & super->bits[i]) != self->bits[i])
  63. return 0;
  64. }
  65. return 1;
  66. }
  67. #define ISLAND_BITMAP_BLOCK(x) (x / 32)
  68. #define ISLAND_BITMAP_MASK(x) (1 << (x % 32))
  69. static void island_bitmap_set(struct island_bitmap *self, uint32_t i)
  70. {
  71. self->bits[ISLAND_BITMAP_BLOCK(i)] |= ISLAND_BITMAP_MASK(i);
  72. }
  73. static int island_bitmap_get(struct island_bitmap *self, uint32_t i)
  74. {
  75. return (self->bits[ISLAND_BITMAP_BLOCK(i)] & ISLAND_BITMAP_MASK(i)) != 0;
  76. }
  77. int in_same_island(const struct object_id *trg_oid, const struct object_id *src_oid)
  78. {
  79. khiter_t trg_pos, src_pos;
  80. /* If we aren't using islands, assume everything goes together. */
  81. if (!island_marks)
  82. return 1;
  83. /*
  84. * If we don't have a bitmap for the target, we can delta it
  85. * against anything -- it's not an important object
  86. */
  87. trg_pos = kh_get_oid_map(island_marks, *trg_oid);
  88. if (trg_pos >= kh_end(island_marks))
  89. return 1;
  90. /*
  91. * if the source (our delta base) doesn't have a bitmap,
  92. * we don't want to base any deltas on it!
  93. */
  94. src_pos = kh_get_oid_map(island_marks, *src_oid);
  95. if (src_pos >= kh_end(island_marks))
  96. return 0;
  97. return island_bitmap_is_subset(kh_value(island_marks, trg_pos),
  98. kh_value(island_marks, src_pos));
  99. }
  100. int island_delta_cmp(const struct object_id *a, const struct object_id *b)
  101. {
  102. khiter_t a_pos, b_pos;
  103. struct island_bitmap *a_bitmap = NULL, *b_bitmap = NULL;
  104. if (!island_marks)
  105. return 0;
  106. a_pos = kh_get_oid_map(island_marks, *a);
  107. if (a_pos < kh_end(island_marks))
  108. a_bitmap = kh_value(island_marks, a_pos);
  109. b_pos = kh_get_oid_map(island_marks, *b);
  110. if (b_pos < kh_end(island_marks))
  111. b_bitmap = kh_value(island_marks, b_pos);
  112. if (a_bitmap) {
  113. if (!b_bitmap || !island_bitmap_is_subset(a_bitmap, b_bitmap))
  114. return -1;
  115. }
  116. if (b_bitmap) {
  117. if (!a_bitmap || !island_bitmap_is_subset(b_bitmap, a_bitmap))
  118. return 1;
  119. }
  120. return 0;
  121. }
  122. static struct island_bitmap *create_or_get_island_marks(struct object *obj)
  123. {
  124. khiter_t pos;
  125. int hash_ret;
  126. pos = kh_put_oid_map(island_marks, obj->oid, &hash_ret);
  127. if (hash_ret)
  128. kh_value(island_marks, pos) = island_bitmap_new(NULL);
  129. return kh_value(island_marks, pos);
  130. }
  131. static void set_island_marks(struct object *obj, struct island_bitmap *marks)
  132. {
  133. struct island_bitmap *b;
  134. khiter_t pos;
  135. int hash_ret;
  136. pos = kh_put_oid_map(island_marks, obj->oid, &hash_ret);
  137. if (hash_ret) {
  138. /*
  139. * We don't have one yet; make a copy-on-write of the
  140. * parent.
  141. */
  142. marks->refcount++;
  143. kh_value(island_marks, pos) = marks;
  144. return;
  145. }
  146. /*
  147. * We do have it. Make sure we split any copy-on-write before
  148. * updating.
  149. */
  150. b = kh_value(island_marks, pos);
  151. if (b->refcount > 1) {
  152. b->refcount--;
  153. b = kh_value(island_marks, pos) = island_bitmap_new(b);
  154. }
  155. island_bitmap_or(b, marks);
  156. }
  157. static void mark_remote_island_1(struct repository *r,
  158. struct remote_island *rl,
  159. int is_core_island)
  160. {
  161. uint32_t i;
  162. for (i = 0; i < rl->oids.nr; ++i) {
  163. struct island_bitmap *marks;
  164. struct object *obj = parse_object(r, &rl->oids.oid[i]);
  165. if (!obj)
  166. continue;
  167. marks = create_or_get_island_marks(obj);
  168. island_bitmap_set(marks, island_counter);
  169. if (is_core_island && obj->type == OBJ_COMMIT)
  170. obj->flags |= NEEDS_BITMAP;
  171. /* If it was a tag, also make sure we hit the underlying object. */
  172. while (obj && obj->type == OBJ_TAG) {
  173. obj = ((struct tag *)obj)->tagged;
  174. if (obj) {
  175. parse_object(r, &obj->oid);
  176. marks = create_or_get_island_marks(obj);
  177. island_bitmap_set(marks, island_counter);
  178. }
  179. }
  180. }
  181. if (is_core_island)
  182. island_counter_core = island_counter;
  183. island_counter++;
  184. }
  185. struct tree_islands_todo {
  186. struct object_entry *entry;
  187. unsigned int depth;
  188. };
  189. static int tree_depth_compare(const void *a, const void *b)
  190. {
  191. const struct tree_islands_todo *todo_a = a;
  192. const struct tree_islands_todo *todo_b = b;
  193. return todo_a->depth - todo_b->depth;
  194. }
  195. void resolve_tree_islands(struct repository *r,
  196. int progress,
  197. struct packing_data *to_pack)
  198. {
  199. struct progress *progress_state = NULL;
  200. struct tree_islands_todo *todo;
  201. int nr = 0;
  202. int i;
  203. if (!island_marks)
  204. return;
  205. /*
  206. * We process only trees, as commits and tags have already been handled
  207. * (and passed their marks on to root trees, as well. We must make sure
  208. * to process them in descending tree-depth order so that marks
  209. * propagate down the tree properly, even if a sub-tree is found in
  210. * multiple parent trees.
  211. */
  212. ALLOC_ARRAY(todo, to_pack->nr_objects);
  213. for (i = 0; i < to_pack->nr_objects; i++) {
  214. if (oe_type(&to_pack->objects[i]) == OBJ_TREE) {
  215. todo[nr].entry = &to_pack->objects[i];
  216. todo[nr].depth = oe_tree_depth(to_pack, &to_pack->objects[i]);
  217. nr++;
  218. }
  219. }
  220. QSORT(todo, nr, tree_depth_compare);
  221. if (progress)
  222. progress_state = start_progress(_("Propagating island marks"), nr);
  223. for (i = 0; i < nr; i++) {
  224. struct object_entry *ent = todo[i].entry;
  225. struct island_bitmap *root_marks;
  226. struct tree *tree;
  227. struct tree_desc desc;
  228. struct name_entry entry;
  229. khiter_t pos;
  230. pos = kh_get_oid_map(island_marks, ent->idx.oid);
  231. if (pos >= kh_end(island_marks))
  232. continue;
  233. root_marks = kh_value(island_marks, pos);
  234. tree = lookup_tree(r, &ent->idx.oid);
  235. if (!tree || parse_tree(tree) < 0)
  236. die(_("bad tree object %s"), oid_to_hex(&ent->idx.oid));
  237. init_tree_desc(&desc, tree->buffer, tree->size);
  238. while (tree_entry(&desc, &entry)) {
  239. struct object *obj;
  240. if (S_ISGITLINK(entry.mode))
  241. continue;
  242. obj = lookup_object(r, &entry.oid);
  243. if (!obj)
  244. continue;
  245. set_island_marks(obj, root_marks);
  246. }
  247. free_tree_buffer(tree);
  248. display_progress(progress_state, i+1);
  249. }
  250. stop_progress(&progress_state);
  251. free(todo);
  252. }
  253. static regex_t *island_regexes;
  254. static unsigned int island_regexes_alloc, island_regexes_nr;
  255. static const char *core_island_name;
  256. static int island_config_callback(const char *k, const char *v, void *cb)
  257. {
  258. if (!strcmp(k, "pack.island")) {
  259. struct strbuf re = STRBUF_INIT;
  260. if (!v)
  261. return config_error_nonbool(k);
  262. ALLOC_GROW(island_regexes, island_regexes_nr + 1, island_regexes_alloc);
  263. if (*v != '^')
  264. strbuf_addch(&re, '^');
  265. strbuf_addstr(&re, v);
  266. if (regcomp(&island_regexes[island_regexes_nr], re.buf, REG_EXTENDED))
  267. die(_("failed to load island regex for '%s': %s"), k, re.buf);
  268. strbuf_release(&re);
  269. island_regexes_nr++;
  270. return 0;
  271. }
  272. if (!strcmp(k, "pack.islandcore"))
  273. return git_config_string(&core_island_name, k, v);
  274. return 0;
  275. }
  276. static void add_ref_to_island(const char *island_name, const struct object_id *oid)
  277. {
  278. uint64_t sha_core;
  279. struct remote_island *rl = NULL;
  280. int hash_ret;
  281. khiter_t pos = kh_put_str(remote_islands, island_name, &hash_ret);
  282. if (hash_ret) {
  283. kh_key(remote_islands, pos) = xstrdup(island_name);
  284. kh_value(remote_islands, pos) = xcalloc(1, sizeof(struct remote_island));
  285. }
  286. rl = kh_value(remote_islands, pos);
  287. oid_array_append(&rl->oids, oid);
  288. memcpy(&sha_core, oid->hash, sizeof(uint64_t));
  289. rl->hash += sha_core;
  290. }
  291. static int find_island_for_ref(const char *refname, const struct object_id *oid,
  292. int flags, void *data)
  293. {
  294. /*
  295. * We should advertise 'ARRAY_SIZE(matches) - 2' as the max,
  296. * so we can diagnose below a config with more capture groups
  297. * than we support.
  298. */
  299. regmatch_t matches[16];
  300. int i, m;
  301. struct strbuf island_name = STRBUF_INIT;
  302. /* walk backwards to get last-one-wins ordering */
  303. for (i = island_regexes_nr - 1; i >= 0; i--) {
  304. if (!regexec(&island_regexes[i], refname,
  305. ARRAY_SIZE(matches), matches, 0))
  306. break;
  307. }
  308. if (i < 0)
  309. return 0;
  310. if (matches[ARRAY_SIZE(matches) - 1].rm_so != -1)
  311. warning(_("island regex from config has "
  312. "too many capture groups (max=%d)"),
  313. (int)ARRAY_SIZE(matches) - 2);
  314. for (m = 1; m < ARRAY_SIZE(matches); m++) {
  315. regmatch_t *match = &matches[m];
  316. if (match->rm_so == -1)
  317. continue;
  318. if (island_name.len)
  319. strbuf_addch(&island_name, '-');
  320. strbuf_add(&island_name, refname + match->rm_so, match->rm_eo - match->rm_so);
  321. }
  322. add_ref_to_island(island_name.buf, oid);
  323. strbuf_release(&island_name);
  324. return 0;
  325. }
  326. static struct remote_island *get_core_island(void)
  327. {
  328. if (core_island_name) {
  329. khiter_t pos = kh_get_str(remote_islands, core_island_name);
  330. if (pos < kh_end(remote_islands))
  331. return kh_value(remote_islands, pos);
  332. }
  333. return NULL;
  334. }
  335. static void deduplicate_islands(struct repository *r)
  336. {
  337. struct remote_island *island, *core = NULL, **list;
  338. unsigned int island_count, dst, src, ref, i = 0;
  339. island_count = kh_size(remote_islands);
  340. ALLOC_ARRAY(list, island_count);
  341. kh_foreach_value(remote_islands, island, {
  342. list[i++] = island;
  343. });
  344. for (ref = 0; ref + 1 < island_count; ref++) {
  345. for (src = ref + 1, dst = src; src < island_count; src++) {
  346. if (list[ref]->hash == list[src]->hash)
  347. continue;
  348. if (src != dst)
  349. list[dst] = list[src];
  350. dst++;
  351. }
  352. island_count = dst;
  353. }
  354. island_bitmap_size = (island_count / 32) + 1;
  355. core = get_core_island();
  356. for (i = 0; i < island_count; ++i) {
  357. mark_remote_island_1(r, list[i], core && list[i]->hash == core->hash);
  358. }
  359. free(list);
  360. }
  361. void load_delta_islands(struct repository *r, int progress)
  362. {
  363. island_marks = kh_init_oid_map();
  364. remote_islands = kh_init_str();
  365. git_config(island_config_callback, NULL);
  366. for_each_ref(find_island_for_ref, NULL);
  367. deduplicate_islands(r);
  368. if (progress)
  369. fprintf(stderr, _("Marked %d islands, done.\n"), island_counter);
  370. }
  371. void propagate_island_marks(struct commit *commit)
  372. {
  373. khiter_t pos = kh_get_oid_map(island_marks, commit->object.oid);
  374. if (pos < kh_end(island_marks)) {
  375. struct commit_list *p;
  376. struct island_bitmap *root_marks = kh_value(island_marks, pos);
  377. parse_commit(commit);
  378. set_island_marks(&get_commit_tree(commit)->object, root_marks);
  379. for (p = commit->parents; p; p = p->next)
  380. set_island_marks(&p->item->object, root_marks);
  381. }
  382. }
  383. int compute_pack_layers(struct packing_data *to_pack)
  384. {
  385. uint32_t i;
  386. if (!core_island_name || !island_marks)
  387. return 1;
  388. for (i = 0; i < to_pack->nr_objects; ++i) {
  389. struct object_entry *entry = &to_pack->objects[i];
  390. khiter_t pos = kh_get_oid_map(island_marks, entry->idx.oid);
  391. oe_set_layer(to_pack, entry, 1);
  392. if (pos < kh_end(island_marks)) {
  393. struct island_bitmap *bitmap = kh_value(island_marks, pos);
  394. if (island_bitmap_get(bitmap, island_counter_core))
  395. oe_set_layer(to_pack, entry, 0);
  396. }
  397. }
  398. return 2;
  399. }