| 1 | #define DISABLE_SIGN_COMPARE_WARNINGS |
| 2 | |
| 3 | #include "git-compat-util.h" |
| 4 | #include "repack.h" |
| 5 | #include "repository.h" |
| 6 | #include "hex.h" |
| 7 | #include "midx.h" |
| 8 | #include "packfile.h" |
| 9 | |
| 10 | static uint32_t pack_geometry_weight(struct packed_git *p) |
| 11 | { |
| 12 | if (open_pack_index(p)) |
| 13 | die(_("cannot open index for %s"), p->pack_name); |
| 14 | return p->num_objects; |
| 15 | } |
| 16 | |
| 17 | static int pack_geometry_cmp(const void *va, const void *vb) |
| 18 | { |
| 19 | uint32_t aw = pack_geometry_weight(*(struct packed_git **)va), |
| 20 | bw = pack_geometry_weight(*(struct packed_git **)vb); |
| 21 | |
| 22 | if (aw < bw) |
| 23 | return -1; |
| 24 | if (aw > bw) |
| 25 | return 1; |
| 26 | return 0; |
| 27 | } |
| 28 | |
| 29 | void pack_geometry_init(struct pack_geometry *geometry, |
| 30 | struct existing_packs *existing, |
| 31 | const struct pack_objects_args *args) |
| 32 | { |
| 33 | struct packed_git *p; |
| 34 | struct strbuf buf = STRBUF_INIT; |
| 35 | struct odb_source_files *files = odb_source_files_downcast(existing->source); |
| 36 | struct multi_pack_index *m = get_multi_pack_index(files->packed); |
| 37 | |
| 38 | repo_for_each_pack(existing->repo, p) { |
| 39 | if (geometry->midx_layer_threshold_set && m && |
| 40 | p->multi_pack_index) { |
| 41 | /* |
| 42 | * When writing MIDX layers incrementally, |
| 43 | * ignore packs unless they are in the most |
| 44 | * recent MIDX layer *and* there are at least |
| 45 | * 'midx_layer_threshold' packs in that layer. |
| 46 | * |
| 47 | * Otherwise 'p' is either in an older layer, or |
| 48 | * the youngest layer does not have enough packs |
| 49 | * to consider its packs as candidates for |
| 50 | * repacking. In either of those cases we want |
| 51 | * to ignore the pack. |
| 52 | */ |
| 53 | if (m->num_packs < geometry->midx_layer_threshold || |
| 54 | !midx_layer_contains_pack(m, pack_basename(p))) |
| 55 | continue; |
| 56 | } |
| 57 | |
| 58 | if (args->local && !p->pack_local) |
| 59 | /* |
| 60 | * When asked to only repack local packfiles we skip |
| 61 | * over any packfiles that are borrowed from alternate |
| 62 | * object directories. |
| 63 | */ |
| 64 | continue; |
| 65 | |
| 66 | if (!args->pack_kept_objects) { |
| 67 | /* |
| 68 | * Any pack that has its pack_keep bit set will |
| 69 | * appear in existing->kept_packs below, but |
| 70 | * this saves us from doing a more expensive |
| 71 | * check. |
| 72 | */ |
| 73 | if (p->pack_keep) |
| 74 | continue; |
| 75 | |
| 76 | /* |
| 77 | * The pack may be kept via the --keep-pack |
| 78 | * option; check 'existing->kept_packs' to |
| 79 | * determine whether to ignore it. |
| 80 | */ |
| 81 | strbuf_reset(&buf); |
| 82 | strbuf_addstr(&buf, pack_basename(p)); |
| 83 | strbuf_strip_suffix(&buf, ".pack"); |
| 84 | |
| 85 | if (string_list_has_string(&existing->kept_packs, buf.buf)) |
| 86 | continue; |
| 87 | } |
| 88 | if (p->is_cruft) |
| 89 | continue; |
| 90 | |
| 91 | if (p->pack_promisor) { |
| 92 | ALLOC_GROW(geometry->promisor_pack, |
| 93 | geometry->promisor_pack_nr + 1, |
| 94 | geometry->promisor_pack_alloc); |
| 95 | |
| 96 | geometry->promisor_pack[geometry->promisor_pack_nr] = p; |
| 97 | geometry->promisor_pack_nr++; |
| 98 | } else { |
| 99 | ALLOC_GROW(geometry->pack, |
| 100 | geometry->pack_nr + 1, |
| 101 | geometry->pack_alloc); |
| 102 | |
| 103 | geometry->pack[geometry->pack_nr] = p; |
| 104 | geometry->pack_nr++; |
| 105 | } |
| 106 | } |
| 107 | |
| 108 | QSORT(geometry->pack, geometry->pack_nr, pack_geometry_cmp); |
| 109 | QSORT(geometry->promisor_pack, geometry->promisor_pack_nr, pack_geometry_cmp); |
| 110 | strbuf_release(&buf); |
| 111 | } |
| 112 | |
| 113 | static uint32_t compute_pack_geometry_split(struct packed_git **pack, size_t pack_nr, |
| 114 | int split_factor) |
| 115 | { |
| 116 | uint32_t i; |
| 117 | uint32_t split; |
| 118 | off_t total_size = 0; |
| 119 | |
| 120 | if (!pack_nr) |
| 121 | return 0; |
| 122 | |
| 123 | /* |
| 124 | * First, count the number of packs (in descending order of size) which |
| 125 | * already form a geometric progression. |
| 126 | */ |
| 127 | for (i = pack_nr - 1; i > 0; i--) { |
| 128 | struct packed_git *ours = pack[i]; |
| 129 | struct packed_git *prev = pack[i - 1]; |
| 130 | |
| 131 | if (unsigned_mult_overflows(split_factor, |
| 132 | pack_geometry_weight(prev))) |
| 133 | die(_("pack %s too large to consider in geometric " |
| 134 | "progression"), |
| 135 | prev->pack_name); |
| 136 | |
| 137 | if (pack_geometry_weight(ours) < |
| 138 | split_factor * pack_geometry_weight(prev)) |
| 139 | break; |
| 140 | } |
| 141 | |
| 142 | split = i; |
| 143 | |
| 144 | if (split) { |
| 145 | /* |
| 146 | * Move the split one to the right, since the top element in the |
| 147 | * last-compared pair can't be in the progression. Only do this |
| 148 | * when we split in the middle of the array (otherwise if we got |
| 149 | * to the end, then the split is in the right place). |
| 150 | */ |
| 151 | split++; |
| 152 | } |
| 153 | |
| 154 | /* |
| 155 | * Then, anything to the left of 'split' must be in a new pack. But, |
| 156 | * creating that new pack may cause packs in the heavy half to no longer |
| 157 | * form a geometric progression. |
| 158 | * |
| 159 | * Compute an expected size of the new pack, and then determine how many |
| 160 | * packs in the heavy half need to be joined into it (if any) to restore |
| 161 | * the geometric progression. |
| 162 | */ |
| 163 | for (i = 0; i < split; i++) { |
| 164 | struct packed_git *p = pack[i]; |
| 165 | |
| 166 | if (unsigned_add_overflows(total_size, pack_geometry_weight(p))) |
| 167 | die(_("pack %s too large to roll up"), p->pack_name); |
| 168 | total_size += pack_geometry_weight(p); |
| 169 | } |
| 170 | for (i = split; i < pack_nr; i++) { |
| 171 | struct packed_git *ours = pack[i]; |
| 172 | |
| 173 | if (unsigned_mult_overflows(split_factor, total_size)) |
| 174 | die(_("pack %s too large to roll up"), ours->pack_name); |
| 175 | |
| 176 | if (pack_geometry_weight(ours) < split_factor * total_size) { |
| 177 | if (unsigned_add_overflows(total_size, |
| 178 | pack_geometry_weight(ours))) |
| 179 | die(_("pack %s too large to roll up"), |
| 180 | ours->pack_name); |
| 181 | |
| 182 | split++; |
| 183 | total_size += pack_geometry_weight(ours); |
| 184 | } else |
| 185 | break; |
| 186 | } |
| 187 | |
| 188 | return split; |
| 189 | } |
| 190 | |
| 191 | void pack_geometry_split(struct pack_geometry *geometry) |
| 192 | { |
| 193 | geometry->split = compute_pack_geometry_split(geometry->pack, geometry->pack_nr, |
| 194 | geometry->split_factor); |
| 195 | geometry->promisor_split = compute_pack_geometry_split(geometry->promisor_pack, |
| 196 | geometry->promisor_pack_nr, |
| 197 | geometry->split_factor); |
| 198 | for (uint32_t i = 0; i < geometry->split; i++) { |
| 199 | struct packed_git *p = geometry->pack[i]; |
| 200 | /* |
| 201 | * During incremental MIDX/bitmap repacking, any packs |
| 202 | * included in the rollup are either (a) not MIDX'd, or |
| 203 | * (b) contained in the tip layer iff it has at least |
| 204 | * the threshold number of packs. |
| 205 | * |
| 206 | * In the latter case, we can safely conclude that the |
| 207 | * tip of the MIDX chain will be rewritten. |
| 208 | */ |
| 209 | if (p->multi_pack_index) |
| 210 | geometry->midx_tip_rewritten = true; |
| 211 | } |
| 212 | } |
| 213 | |
| 214 | struct packed_git *pack_geometry_preferred_pack(struct pack_geometry *geometry) |
| 215 | { |
| 216 | uint32_t i; |
| 217 | |
| 218 | if (!geometry) { |
| 219 | /* |
| 220 | * No geometry means either an all-into-one repack (in which |
| 221 | * case there is only one pack left and it is the largest) or an |
| 222 | * incremental one. |
| 223 | * |
| 224 | * If repacking incrementally, then we could check the size of |
| 225 | * all packs to determine which should be preferred, but leave |
| 226 | * this for later. |
| 227 | */ |
| 228 | return NULL; |
| 229 | } |
| 230 | if (geometry->split == geometry->pack_nr) |
| 231 | return NULL; |
| 232 | |
| 233 | /* |
| 234 | * The preferred pack is the largest pack above the split line. In |
| 235 | * other words, it is the largest pack that does not get rolled up in |
| 236 | * the geometric repack. |
| 237 | */ |
| 238 | for (i = geometry->pack_nr; i > geometry->split; i--) |
| 239 | /* |
| 240 | * A pack that is not local would never be included in a |
| 241 | * multi-pack index. We thus skip over any non-local packs. |
| 242 | */ |
| 243 | if (geometry->pack[i - 1]->pack_local) |
| 244 | return geometry->pack[i - 1]; |
| 245 | |
| 246 | return NULL; |
| 247 | } |
| 248 | |
| 249 | static void remove_redundant_packs(struct packed_git **pack, |
| 250 | uint32_t pack_nr, |
| 251 | struct string_list *names, |
| 252 | struct existing_packs *existing, |
| 253 | const char *packdir, |
| 254 | bool wrote_incremental_midx) |
| 255 | { |
| 256 | const struct git_hash_algo *algop = existing->repo->hash_algo; |
| 257 | struct strbuf buf = STRBUF_INIT; |
| 258 | uint32_t i; |
| 259 | |
| 260 | for (i = 0; i < pack_nr; i++) { |
| 261 | struct packed_git *p = pack[i]; |
| 262 | if (string_list_has_string(names, hash_to_hex_algop(p->hash, |
| 263 | algop))) |
| 264 | continue; |
| 265 | |
| 266 | strbuf_reset(&buf); |
| 267 | strbuf_addstr(&buf, pack_basename(p)); |
| 268 | strbuf_strip_suffix(&buf, ".pack"); |
| 269 | |
| 270 | if ((p->pack_keep) || |
| 271 | (string_list_has_string(&existing->kept_packs, buf.buf))) |
| 272 | continue; |
| 273 | |
| 274 | repack_remove_redundant_pack(existing->repo, packdir, buf.buf, |
| 275 | wrote_incremental_midx); |
| 276 | } |
| 277 | |
| 278 | strbuf_release(&buf); |
| 279 | } |
| 280 | |
| 281 | void pack_geometry_remove_redundant(struct pack_geometry *geometry, |
| 282 | struct string_list *names, |
| 283 | struct existing_packs *existing, |
| 284 | const char *packdir, |
| 285 | bool wrote_incremental_midx) |
| 286 | { |
| 287 | remove_redundant_packs(geometry->pack, geometry->split, |
| 288 | names, existing, packdir, wrote_incremental_midx); |
| 289 | remove_redundant_packs(geometry->promisor_pack, geometry->promisor_split, |
| 290 | names, existing, packdir, wrote_incremental_midx); |
| 291 | } |
| 292 | |
| 293 | void pack_geometry_release(struct pack_geometry *geometry) |
| 294 | { |
| 295 | if (!geometry) |
| 296 | return; |
| 297 | |
| 298 | free(geometry->pack); |
| 299 | free(geometry->promisor_pack); |
| 300 | } |