| 1 | /* |
| 2 | * Precomputed diff hunks, keyed by diff input. |
| 3 | * |
| 4 | * A single store at .git/objects/info/diff-hunks maps an (old blob, |
| 5 | * new blob, xdl_opts) key to the hunk coordinates of diffing the pair. |
| 6 | * The key determines the diff result (only trim-stable pairs are |
| 7 | * recorded; see diff-hunks.h), so an entry is valid in any context it |
| 8 | * recurs in, independent of path. Reading is on by default |
| 9 | * (core.diffHunks); writing is off by default and enabled per run or |
| 10 | * by configuration (see diff_hunks_write_enabled), so an ordinary |
| 11 | * command populates the store only during a warming run the |
| 12 | * repository owner opts into. |
| 13 | * |
| 14 | * File layout: |
| 15 | * Header: "DHPF"(4) + version(1) + hash_version(1) |
| 16 | * + num_chunks(1) + reserved(1) |
| 17 | * Table of contents (chunk-format) |
| 18 | * DHIX chunk: sorted entries, each |
| 19 | * old_blob_oid, new_blob_oid, xdl_opts(4), hdat_offset(4) |
| 20 | * DHDT chunk: per entry, num_hunks(4) followed by that many 16-byte hunks |
| 21 | * Trailing hash checksum |
| 22 | */ |
| 23 | #include "git-compat-util.h" |
| 24 | #include "chunk-format.h" |
| 25 | #include "config.h" |
| 26 | #include "csum-file.h" |
| 27 | #include "diff-hunks.h" |
| 28 | #include "diff-provider-internal.h" |
| 29 | #include "diff.h" |
| 30 | #include "gettext.h" |
| 31 | #include "hash.h" |
| 32 | #include "hashmap.h" |
| 33 | #include "lockfile.h" |
| 34 | #include "odb.h" |
| 35 | #include "path.h" |
| 36 | #include "repo-settings.h" |
| 37 | #include "repository.h" |
| 38 | #include "strbuf.h" |
| 39 | #include "wrapper.h" |
| 40 | |
| 41 | #define DIFF_HUNKS_SIGNATURE 0x44485046 /* "DHPF" */ |
| 42 | /* |
| 43 | * Bump when the on-disk format changes, or when xdiff's emitted hunk |
| 44 | * coordinates change for a fixed (blobs, xdl_opts) key: an old store |
| 45 | * would otherwise serve stale hunks and change command output. |
| 46 | */ |
| 47 | #define DIFF_HUNKS_VERSION 1 |
| 48 | #define DIFF_HUNKS_HEADER_SIZE 8 |
| 49 | |
| 50 | #define DIFF_HUNKS_CHUNKID_INDEX 0x44484958 /* "DHIX" */ |
| 51 | #define DIFF_HUNKS_CHUNKID_DATA 0x44484454 /* "DHDT" */ |
| 52 | |
| 53 | /* |
| 54 | * Each hunk is 16 bytes on disk: |
| 55 | * old_start(4) old_count(4) new_start(4) new_count(4) |
| 56 | */ |
| 57 | #define DIFF_HUNKS_HUNK_SIZE (4 * sizeof(uint32_t)) |
| 58 | |
| 59 | /* |
| 60 | * Result of a store lookup: num_hunks records encoded in the store's mmap, |
| 61 | * valid until the store is freed. Read them with nth_precomputed_hunk(). |
| 62 | */ |
| 63 | struct precomputed_entry { |
| 64 | uint32_t num_hunks; |
| 65 | const unsigned char *hunk_data; |
| 66 | }; |
| 67 | |
| 68 | /* Decode a single hunk from the raw on-disk format. */ |
| 69 | static inline void decode_precomputed_hunk(const unsigned char *data, |
| 70 | struct precomputed_hunk *h) |
| 71 | { |
| 72 | h->old_start = get_be32(data); |
| 73 | h->old_count = get_be32(data + 4); |
| 74 | h->new_start = get_be32(data + 8); |
| 75 | h->new_count = get_be32(data + 12); |
| 76 | } |
| 77 | |
| 78 | /* Decode the nth hunk of a lookup result into *h. */ |
| 79 | static inline void nth_precomputed_hunk(const struct precomputed_entry *e, |
| 80 | uint32_t n, struct precomputed_hunk *h) |
| 81 | { |
| 82 | decode_precomputed_hunk(e->hunk_data + (size_t)n * DIFF_HUNKS_HUNK_SIZE, h); |
| 83 | } |
| 84 | |
| 85 | /* Byte length of the (old_oid, new_oid, xdl_opts) lookup key. */ |
| 86 | static size_t store_index_key_size(const struct git_hash_algo *algo) |
| 87 | { |
| 88 | return 2 * algo->rawsz + sizeof(uint32_t); |
| 89 | } |
| 90 | |
| 91 | /* Index entry: the lookup key followed by the 4-byte offset into DHDT. */ |
| 92 | static size_t store_index_entry_size(const struct git_hash_algo *algo) |
| 93 | { |
| 94 | return store_index_key_size(algo) + sizeof(uint32_t); |
| 95 | } |
| 96 | |
| 97 | /* |
| 98 | * The smallest a valid store file can be: the header, a table of contents |
| 99 | * with one entry per chunk plus a terminating entry, and the trailing |
| 100 | * checksum. |
| 101 | */ |
| 102 | static size_t store_min_size(const struct git_hash_algo *algo, |
| 103 | uint8_t num_chunks) |
| 104 | { |
| 105 | size_t toc_size = (num_chunks + 1) * CHUNK_TOC_ENTRY_SIZE; |
| 106 | |
| 107 | return DIFF_HUNKS_HEADER_SIZE + toc_size + algo->rawsz; |
| 108 | } |
| 109 | |
| 110 | /* |
| 111 | * Decode an index entry's key into pointers to the two oids and the |
| 112 | * xdl_opts value (on-disk: old_oid, new_oid, then xdl_opts as a |
| 113 | * big-endian uint32). |
| 114 | */ |
| 115 | static void decode_store_index_key(const unsigned char *entry, unsigned int rawsz, |
| 116 | const unsigned char **old_hash, |
| 117 | const unsigned char **new_hash, |
| 118 | uint32_t *xdl_opts) |
| 119 | { |
| 120 | *old_hash = entry; |
| 121 | *new_hash = entry + rawsz; |
| 122 | *xdl_opts = get_be32(entry + 2 * rawsz); |
| 123 | } |
| 124 | |
| 125 | /* The DHDT offset stored in an index entry, in the field after its key. */ |
| 126 | static uint32_t index_entry_hdat_offset(const unsigned char *entry, size_t keysz) |
| 127 | { |
| 128 | return get_be32(entry + keysz); |
| 129 | } |
| 130 | |
| 131 | static char *diff_hunks_store_path(struct repository *r) |
| 132 | { |
| 133 | return xstrfmt("%s/info/diff-hunks", repo_get_object_directory(r)); |
| 134 | } |
| 135 | |
| 136 | struct diff_hunks_store { |
| 137 | const unsigned char *data; |
| 138 | size_t data_len; |
| 139 | const struct git_hash_algo *hash_algo; |
| 140 | const unsigned char *index; |
| 141 | uint32_t num_entries; |
| 142 | const unsigned char *hdat; |
| 143 | size_t hdat_size; |
| 144 | |
| 145 | /* Consultation counters; see diff_hunks_read_stats(). */ |
| 146 | unsigned long read_hits; |
| 147 | unsigned long read_misses; |
| 148 | }; |
| 149 | |
| 150 | static void free_store(struct diff_hunks_store *s) |
| 151 | { |
| 152 | if (!s) |
| 153 | return; |
| 154 | if (s->data) |
| 155 | munmap((void *)s->data, s->data_len); |
| 156 | free(s); |
| 157 | } |
| 158 | |
| 159 | /* |
| 160 | * Open, mmap, and parse the store at fname. Returns the parsed store |
| 161 | * or NULL on any error. The diff output is unaffected either way; |
| 162 | * corruption is reported by verify, not treated as fatal here. |
| 163 | */ |
| 164 | static struct diff_hunks_store *load_store_at( |
| 165 | const struct git_hash_algo *repo_algo, const char *fname) |
| 166 | { |
| 167 | struct diff_hunks_store *s; |
| 168 | struct chunkfile *cf; |
| 169 | int fd; |
| 170 | struct stat st; |
| 171 | void *data; |
| 172 | const unsigned char *p; |
| 173 | uint8_t num_chunks; |
| 174 | size_t index_size, entry_size, data_len; |
| 175 | |
| 176 | fd = git_open(fname); |
| 177 | if (fd < 0) |
| 178 | return NULL; |
| 179 | if (fstat(fd, &st) || st.st_size < DIFF_HUNKS_HEADER_SIZE) { |
| 180 | close(fd); |
| 181 | return NULL; |
| 182 | } |
| 183 | data_len = xsize_t(st.st_size); |
| 184 | data = xmmap(NULL, data_len, PROT_READ, MAP_PRIVATE, fd, 0); |
| 185 | close(fd); |
| 186 | p = data; |
| 187 | |
| 188 | num_chunks = p[6]; |
| 189 | |
| 190 | /* |
| 191 | * Reject a file that is not a readable store: wrong signature, |
| 192 | * version, or object hash, or too small to hold the table of |
| 193 | * contents that read_table_of_contents() walks (it dereferences |
| 194 | * each entry before range-checking its offset). |
| 195 | */ |
| 196 | if (get_be32(p) != DIFF_HUNKS_SIGNATURE || |
| 197 | p[4] != DIFF_HUNKS_VERSION || |
| 198 | p[5] != oid_version(repo_algo) || |
| 199 | data_len < store_min_size(repo_algo, num_chunks)) { |
| 200 | munmap(data, data_len); |
| 201 | return NULL; |
| 202 | } |
| 203 | |
| 204 | /* |
| 205 | * The trailing checksum is not verified here: the writer fsyncs |
| 206 | * and commits atomically, so a committed file is intact, and |
| 207 | * every record is bounds-checked at read (see precomputed_entry_at). |
| 208 | * The checksum is checked separately, by diff_hunks_verify(). |
| 209 | */ |
| 210 | |
| 211 | CALLOC_ARRAY(s, 1); |
| 212 | s->data = data; |
| 213 | s->data_len = data_len; |
| 214 | s->hash_algo = repo_algo; |
| 215 | |
| 216 | cf = init_chunkfile(NULL); |
| 217 | if (read_table_of_contents_quiet(cf, p, data_len, |
| 218 | DIFF_HUNKS_HEADER_SIZE, num_chunks, 1, |
| 219 | repo_algo) || |
| 220 | pair_chunk(cf, DIFF_HUNKS_CHUNKID_INDEX, &s->index, &index_size) || |
| 221 | pair_chunk(cf, DIFF_HUNKS_CHUNKID_DATA, &s->hdat, &s->hdat_size)) { |
| 222 | free_chunkfile(cf); |
| 223 | goto corrupt; |
| 224 | } |
| 225 | free_chunkfile(cf); |
| 226 | |
| 227 | entry_size = store_index_entry_size(s->hash_algo); |
| 228 | if (index_size % entry_size) |
| 229 | goto corrupt; |
| 230 | s->num_entries = index_size / entry_size; |
| 231 | return s; |
| 232 | |
| 233 | corrupt: |
| 234 | free_store(s); |
| 235 | return NULL; |
| 236 | } |
| 237 | |
| 238 | static struct diff_hunks_store *diff_hunks_store_load(struct repository *r) |
| 239 | { |
| 240 | struct diff_hunks_store *s; |
| 241 | char *fname; |
| 242 | |
| 243 | prepare_repo_settings(r); |
| 244 | if (!r->settings.core_diff_hunks) |
| 245 | return NULL; |
| 246 | |
| 247 | fname = diff_hunks_store_path(r); |
| 248 | s = load_store_at(r->hash_algo, fname); |
| 249 | free(fname); |
| 250 | return s; |
| 251 | } |
| 252 | |
| 253 | struct diff_hunks_store *repo_diff_hunks_store(struct repository *r) |
| 254 | { |
| 255 | if (!r->objects) |
| 256 | return NULL; |
| 257 | if (r->objects->diff_hunks_store_attempted) |
| 258 | return r->objects->diff_hunks_store; |
| 259 | r->objects->diff_hunks_store_attempted = 1; |
| 260 | r->objects->diff_hunks_store = diff_hunks_store_load(r); |
| 261 | return r->objects->diff_hunks_store; |
| 262 | } |
| 263 | |
| 264 | void diff_hunks_read_stats(struct repository *r, |
| 265 | unsigned long *hits, unsigned long *misses) |
| 266 | { |
| 267 | struct diff_hunks_store *s = repo_diff_hunks_store(r); |
| 268 | |
| 269 | *hits = s ? s->read_hits : 0; |
| 270 | *misses = s ? s->read_misses : 0; |
| 271 | } |
| 272 | |
| 273 | void close_diff_hunks_store(struct object_database *o) |
| 274 | { |
| 275 | if (!o->diff_hunks_store) |
| 276 | return; |
| 277 | free_store(o->diff_hunks_store); |
| 278 | o->diff_hunks_store = NULL; |
| 279 | } |
| 280 | |
| 281 | /* |
| 282 | * Fill *out with the hunk record at offset in the data chunk, and return |
| 283 | * 1 if the record is in bounds, 0 otherwise. The read path does not |
| 284 | * re-verify the checksum, and a valid checksum would not bound the count |
| 285 | * anyway, so a read must call this and use *out only when it returns |
| 286 | * non-zero. |
| 287 | * |
| 288 | * A record is a be32 hunk count followed by that many DIFF_HUNKS_HUNK_SIZE |
| 289 | * hunks. "remaining" tracks the bytes from offset to the end of the data |
| 290 | * chunk: it must hold the count, and after the count is consumed it must |
| 291 | * hold every hunk. The bounds are written as subtraction and division |
| 292 | * (never addition or multiplication) so a crafted offset or count cannot |
| 293 | * overflow them. |
| 294 | */ |
| 295 | static int precomputed_entry_at(const struct diff_hunks_store *s, |
| 296 | uint32_t offset, struct precomputed_entry *out) |
| 297 | { |
| 298 | size_t remaining; |
| 299 | uint32_t num_hunks; |
| 300 | |
| 301 | if (offset >= s->hdat_size) |
| 302 | return 0; |
| 303 | remaining = s->hdat_size - offset; |
| 304 | if (remaining < sizeof(uint32_t)) |
| 305 | return 0; |
| 306 | |
| 307 | num_hunks = get_be32(s->hdat + offset); |
| 308 | remaining -= sizeof(uint32_t); |
| 309 | if (num_hunks > remaining / DIFF_HUNKS_HUNK_SIZE) |
| 310 | return 0; |
| 311 | |
| 312 | out->num_hunks = num_hunks; |
| 313 | out->hunk_data = s->hdat + offset + sizeof(uint32_t); |
| 314 | return 1; |
| 315 | } |
| 316 | |
| 317 | struct lookup_key { |
| 318 | const struct object_id *old_oid; |
| 319 | const struct object_id *new_oid; |
| 320 | int xdl_opts; |
| 321 | unsigned int rawsz; |
| 322 | }; |
| 323 | |
| 324 | /* |
| 325 | * The store's total order over (old_oid, new_oid, xdl_opts), defined |
| 326 | * once so the write-side sort (writer_entry_cmp) and the read-side |
| 327 | * search (store_bsearch_cmp) order the keys identically. |
| 328 | */ |
| 329 | static int cmp_store_index_key(const unsigned char *old_a, const unsigned char *new_a, |
| 330 | uint32_t opts_a, |
| 331 | const unsigned char *old_b, const unsigned char *new_b, |
| 332 | uint32_t opts_b, unsigned int rawsz) |
| 333 | { |
| 334 | int cmp = memcmp(old_a, old_b, rawsz); |
| 335 | if (!cmp) |
| 336 | cmp = memcmp(new_a, new_b, rawsz); |
| 337 | if (!cmp) |
| 338 | cmp = (opts_a > opts_b) - (opts_a < opts_b); |
| 339 | return cmp; |
| 340 | } |
| 341 | |
| 342 | static int store_bsearch_cmp(const void *key, const void *entry_ptr) |
| 343 | { |
| 344 | const struct lookup_key *k = key; |
| 345 | const unsigned char *old_hash, *new_hash; |
| 346 | uint32_t xdl_opts; |
| 347 | |
| 348 | decode_store_index_key(entry_ptr, k->rawsz, &old_hash, &new_hash, |
| 349 | &xdl_opts); |
| 350 | return cmp_store_index_key(k->old_oid->hash, k->new_oid->hash, |
| 351 | (uint32_t)k->xdl_opts, |
| 352 | old_hash, new_hash, xdl_opts, k->rawsz); |
| 353 | } |
| 354 | |
| 355 | static int store_get_one(struct diff_hunks_store *s, const struct lookup_key *key, |
| 356 | struct precomputed_entry *out) |
| 357 | { |
| 358 | size_t entry_size = store_index_entry_size(s->hash_algo); |
| 359 | const unsigned char *found; |
| 360 | |
| 361 | found = bsearch(key, s->index, s->num_entries, entry_size, |
| 362 | store_bsearch_cmp); |
| 363 | if (!found) |
| 364 | return 0; |
| 365 | return precomputed_entry_at(s, |
| 366 | index_entry_hdat_offset(found, store_index_key_size(s->hash_algo)), |
| 367 | out); |
| 368 | } |
| 369 | |
| 370 | static int diff_hunks_store_get(struct diff_hunks_store *s, |
| 371 | const struct object_id *old_oid, |
| 372 | const struct object_id *new_oid, |
| 373 | int xdl_opts, |
| 374 | struct precomputed_entry *out) |
| 375 | { |
| 376 | struct lookup_key key; |
| 377 | |
| 378 | if (!s) |
| 379 | return 0; |
| 380 | /* The null OID names no blob and cannot key an entry. */ |
| 381 | if (is_null_oid(old_oid) || is_null_oid(new_oid)) |
| 382 | return 0; |
| 383 | |
| 384 | key.old_oid = old_oid; |
| 385 | key.new_oid = new_oid; |
| 386 | key.xdl_opts = xdl_opts; |
| 387 | key.rawsz = s->hash_algo->rawsz; |
| 388 | |
| 389 | return store_get_one(s, &key, out); |
| 390 | } |
| 391 | |
| 392 | /* |
| 393 | * A recorded hunk sequence must satisfy the provider interface's |
| 394 | * shared check (diff_provider_check_hunk()) before it may be replayed: |
| 395 | * coordinates decode from be32 into long, which is 32-bit on some |
| 396 | * platforms, so a crafted value can decode negative or out of order. |
| 397 | * An entry that fails reads as a miss, so the caller recomputes. |
| 398 | */ |
| 399 | static int replayable_hunks(const struct precomputed_entry *e) |
| 400 | { |
| 401 | struct diff_provider_hunks_check c = { 0 }; |
| 402 | uint32_t i; |
| 403 | |
| 404 | /* |
| 405 | * Replaying a record with no hunks would assert the blob pair |
| 406 | * equivalent, a claim the store must never make (the writer |
| 407 | * refuses to record one), so such a record is invalid. |
| 408 | */ |
| 409 | if (!e->num_hunks) |
| 410 | return 0; |
| 411 | for (i = 0; i < e->num_hunks; i++) { |
| 412 | struct precomputed_hunk h; |
| 413 | nth_precomputed_hunk(e, i, &h); |
| 414 | if (diff_provider_check_hunk(&c, h.old_start, h.old_count, |
| 415 | h.new_start, h.new_count)) |
| 416 | return 0; |
| 417 | } |
| 418 | return 1; |
| 419 | } |
| 420 | |
| 421 | int diff_hunks_replay(struct diff_hunks_store *s, |
| 422 | const struct object_id *old_oid, |
| 423 | const struct object_id *new_oid, |
| 424 | int xdl_opts, |
| 425 | xdl_emit_hunk_consume_func_t hunk_func, void *cb_data) |
| 426 | { |
| 427 | struct precomputed_entry e; |
| 428 | uint32_t i; |
| 429 | |
| 430 | if (!s) |
| 431 | return 0; |
| 432 | if (!diff_hunks_store_get(s, old_oid, new_oid, xdl_opts, &e) || |
| 433 | !replayable_hunks(&e)) { |
| 434 | s->read_misses++; |
| 435 | return 0; |
| 436 | } |
| 437 | for (i = 0; i < e.num_hunks; i++) { |
| 438 | struct precomputed_hunk h; |
| 439 | nth_precomputed_hunk(&e, i, &h); |
| 440 | hunk_func(h.old_start, h.old_count, |
| 441 | h.new_start, h.new_count, cb_data); |
| 442 | } |
| 443 | s->read_hits++; |
| 444 | return 1; |
| 445 | } |
| 446 | |
| 447 | /* |
| 448 | * The store's consult implementation. The store is not |
| 449 | * authoritative, so it serves a recorded pair or passes; what the |
| 450 | * recording key cannot express, it excludes here with the |
| 451 | * stop-no-record disposition. None of those legs reaches |
| 452 | * diff_hunks_replay(), so none of them counts as a miss. |
| 453 | */ |
| 454 | static enum diff_provider_disposition |
| 455 | diff_hunks_store_consult(struct diff_provider *provider UNUSED, |
| 456 | const struct diff_provider_request *req, |
| 457 | diff_provider_fill_fn fill UNUSED, |
| 458 | void *fill_data UNUSED, |
| 459 | xdl_emit_hunk_consume_func_t hunk_cb, void *cb_data) |
| 460 | { |
| 461 | /* |
| 462 | * xpparam_t is the consult's parameter input. Its flags are |
| 463 | * the store key's xdl_opts; ignore_regex (-I) and anchors |
| 464 | * (--anchored) shape the diff outside the key, so such a |
| 465 | * request is neither served nor recorded. |
| 466 | * |
| 467 | * Adding an xpparam_t field fires this assert (its size no |
| 468 | * longer matches the reference struct). To clear it: (1) add |
| 469 | * the field to the reference struct below; then (2) decide how |
| 470 | * it affects the key: make it part of the key, or exclude |
| 471 | * diffs that use it here with the disposition below. The |
| 472 | * assert only tracks size: a same-size reorder or a changed |
| 473 | * field meaning slips past, so re-read the fields when it |
| 474 | * fires. |
| 475 | */ |
| 476 | (void)BUILD_ASSERT_OR_ZERO(sizeof(xpparam_t) == sizeof(struct { |
| 477 | unsigned long flags; |
| 478 | regex_t **ignore_regex; |
| 479 | size_t ignore_regex_nr; |
| 480 | char **anchors; |
| 481 | size_t anchors_nr; |
| 482 | })); |
| 483 | if (req->xpp->ignore_regex_nr || req->xpp->anchors_nr) |
| 484 | return DIFF_PROVIDER_DISP_STOP_NO_RECORD; |
| 485 | /* |
| 486 | * Break detection (-B) rescores the pair outside xpparam_t, so |
| 487 | * it is outside the key for the same reason. |
| 488 | */ |
| 489 | if (req->diffopt && req->diffopt->break_opt != -1) |
| 490 | return DIFF_PROVIDER_DISP_STOP_NO_RECORD; |
| 491 | |
| 492 | if (!req->old_oid || !req->new_oid) |
| 493 | return DIFF_PROVIDER_DISP_PASS; |
| 494 | if (diff_hunks_replay(repo_diff_hunks_store(req->repo), |
| 495 | req->old_oid, req->new_oid, |
| 496 | req->xpp->flags, hunk_cb, cb_data)) |
| 497 | return DIFF_PROVIDER_DISP_ANSWERED; |
| 498 | return DIFF_PROVIDER_DISP_PASS; |
| 499 | } |
| 500 | |
| 501 | /* |
| 502 | * The provider borrows the repository's store through |
| 503 | * repo_diff_hunks_store() per request; the object database owns the |
| 504 | * file and tears it down, so there is nothing to release here. |
| 505 | */ |
| 506 | struct diff_provider *diff_hunks_store_provider_new(void) |
| 507 | { |
| 508 | struct diff_provider *p = xcalloc(1, sizeof(*p)); |
| 509 | |
| 510 | p->consult = diff_hunks_store_consult; |
| 511 | return p; |
| 512 | } |
| 513 | |
| 514 | /* Validate one store file. Returns 0 if valid or absent, -1 on any error. */ |
| 515 | static int verify_store_at(struct repository *r, const char *fname) |
| 516 | { |
| 517 | struct diff_hunks_store *s; |
| 518 | size_t entry_size; |
| 519 | uint32_t i; |
| 520 | int fd; |
| 521 | int ret = 0; |
| 522 | |
| 523 | /* |
| 524 | * A file that cannot be opened is not evidence of corruption: |
| 525 | * report the open error, and reserve the corruption diagnostics |
| 526 | * below for a file that was read and failed to parse. |
| 527 | */ |
| 528 | fd = git_open(fname); |
| 529 | if (fd < 0) { |
| 530 | if (errno == ENOENT) |
| 531 | return 0; /* absent is valid */ |
| 532 | return error_errno(_("unable to open diff-hunks store %s"), |
| 533 | fname); |
| 534 | } |
| 535 | close(fd); |
| 536 | s = load_store_at(r->hash_algo, fname); |
| 537 | if (!s) |
| 538 | return error(_("diff-hunks store failed to load (corrupt " |
| 539 | "header or hash mismatch): %s"), fname); |
| 540 | if (!hashfile_checksum_valid(r->hash_algo, s->data, s->data_len)) { |
| 541 | error(_("diff-hunks store has incorrect checksum and is " |
| 542 | "likely corrupt: %s"), fname); |
| 543 | free_store(s); |
| 544 | return -1; |
| 545 | } |
| 546 | |
| 547 | entry_size = store_index_entry_size(s->hash_algo); |
| 548 | for (i = 0; i < s->num_entries; i++) { |
| 549 | const unsigned char *ep = s->index + st_mult(entry_size, i); |
| 550 | size_t keysz = store_index_key_size(s->hash_algo); |
| 551 | uint32_t offset = index_entry_hdat_offset(ep, keysz); |
| 552 | struct precomputed_entry pe; |
| 553 | |
| 554 | /* |
| 555 | * Keyed by (old_oid, new_oid, xdl_opts), increasing. memcmp |
| 556 | * matches cmp_store_index_key's integer comparison of |
| 557 | * xdl_opts because it is non-negative, so its big-endian |
| 558 | * bytes order the same as its value. |
| 559 | */ |
| 560 | if (i > 0 && memcmp(ep - entry_size, ep, keysz) >= 0) { |
| 561 | error(_("diff-hunks entry %u not in sorted order"), i); |
| 562 | ret = -1; |
| 563 | } |
| 564 | if (!precomputed_entry_at(s, offset, &pe)) { |
| 565 | error(_("diff-hunks entry %u has out-of-bounds hunk " |
| 566 | "data"), i); |
| 567 | ret = -1; |
| 568 | } else if (!replayable_hunks(&pe)) { |
| 569 | error(_("diff-hunks entry %u holds an invalid hunk " |
| 570 | "sequence"), i); |
| 571 | ret = -1; |
| 572 | } |
| 573 | } |
| 574 | |
| 575 | free_store(s); |
| 576 | return ret; |
| 577 | } |
| 578 | |
| 579 | int diff_hunks_verify(struct repository *r) |
| 580 | { |
| 581 | char *fname = diff_hunks_store_path(r); |
| 582 | int ret = 0; |
| 583 | |
| 584 | if (verify_store_at(r, fname)) |
| 585 | ret = -1; |
| 586 | free(fname); |
| 587 | return ret; |
| 588 | } |
| 589 | |
| 590 | int diff_hunks_clear(struct repository *r) |
| 591 | { |
| 592 | char *fname = diff_hunks_store_path(r); |
| 593 | int ret = 0; |
| 594 | |
| 595 | if (unlink(fname) && errno != ENOENT) |
| 596 | ret = error_errno(_("unable to remove %s"), fname); |
| 597 | free(fname); |
| 598 | return ret; |
| 599 | } |
| 600 | |
| 601 | struct writer_entry { |
| 602 | struct object_id old_oid; |
| 603 | struct object_id new_oid; |
| 604 | int xdl_opts; |
| 605 | uint32_t hdat_offset; |
| 606 | }; |
| 607 | |
| 608 | struct diff_hunks_writer { |
| 609 | struct repository *r; |
| 610 | struct writer_entry *entries; |
| 611 | size_t nr, alloc; |
| 612 | size_t seed_nr; /* nr after seeding; finish skips a no-op flush */ |
| 613 | unsigned force_flush : 1; /* seed pruned: rewrite even a no-op warm */ |
| 614 | struct strbuf hdat; |
| 615 | struct hashmap dedup; /* hunk block content -> offset in hdat */ |
| 616 | }; |
| 617 | |
| 618 | /* A record of one distinct hunk block already present in hdat. */ |
| 619 | struct dedup_entry { |
| 620 | struct hashmap_entry ent; |
| 621 | uint32_t offset; |
| 622 | uint32_t len; |
| 623 | }; |
| 624 | |
| 625 | static int dedup_cmp(const void *cmp_data, |
| 626 | const struct hashmap_entry *a, |
| 627 | const struct hashmap_entry *b, |
| 628 | const void *keydata UNUSED) |
| 629 | { |
| 630 | const struct diff_hunks_writer *writer = cmp_data; |
| 631 | const struct dedup_entry *ea = container_of(a, const struct dedup_entry, ent); |
| 632 | const struct dedup_entry *eb = container_of(b, const struct dedup_entry, ent); |
| 633 | |
| 634 | if (ea->len != eb->len) |
| 635 | return 1; |
| 636 | return memcmp(writer->hdat.buf + ea->offset, |
| 637 | writer->hdat.buf + eb->offset, ea->len); |
| 638 | } |
| 639 | |
| 640 | static struct diff_hunks_writer *diff_hunks_writer_new(struct repository *r) |
| 641 | { |
| 642 | struct diff_hunks_writer *w; |
| 643 | |
| 644 | CALLOC_ARRAY(w, 1); |
| 645 | w->r = r; |
| 646 | strbuf_init(&w->hdat, 0); |
| 647 | hashmap_init(&w->dedup, dedup_cmp, w, 0); |
| 648 | return w; |
| 649 | } |
| 650 | |
| 651 | static void strbuf_put_be32(struct strbuf *sb, uint32_t val) |
| 652 | { |
| 653 | unsigned char buf[4]; |
| 654 | put_be32(buf, val); |
| 655 | strbuf_add(sb, buf, 4); |
| 656 | } |
| 657 | |
| 658 | /* |
| 659 | * The hunk block just appended at `start` is deduplicated: if an |
| 660 | * identical block is already in hdat, this copy is dropped and the |
| 661 | * earlier offset returned; otherwise it is kept and remembered. |
| 662 | * Distinct keys that diff to the same hunks then share one block. |
| 663 | */ |
| 664 | static uint32_t intern_block(struct diff_hunks_writer *w, size_t start) |
| 665 | { |
| 666 | size_t len = w->hdat.len - start; |
| 667 | struct dedup_entry key, *found, *added; |
| 668 | |
| 669 | hashmap_entry_init(&key.ent, memhash(w->hdat.buf + start, len)); |
| 670 | key.offset = (uint32_t)start; |
| 671 | key.len = (uint32_t)len; |
| 672 | |
| 673 | found = hashmap_get_entry(&w->dedup, &key, ent, NULL); |
| 674 | if (found) { |
| 675 | strbuf_setlen(&w->hdat, start); |
| 676 | return found->offset; |
| 677 | } |
| 678 | |
| 679 | added = xmalloc(sizeof(*added)); |
| 680 | hashmap_entry_init(&added->ent, key.ent.hash); |
| 681 | added->offset = key.offset; |
| 682 | added->len = key.len; |
| 683 | hashmap_add(&w->dedup, &added->ent); |
| 684 | return key.offset; |
| 685 | } |
| 686 | |
| 687 | int diff_hunks_writer_add(struct diff_hunks_writer *w, |
| 688 | const struct object_id *old_oid, |
| 689 | const struct object_id *new_oid, |
| 690 | int xdl_opts, |
| 691 | const struct precomputed_hunk *hunks, |
| 692 | size_t nr_hunks) |
| 693 | { |
| 694 | struct writer_entry *e; |
| 695 | size_t i, block_start; |
| 696 | |
| 697 | if (!w) |
| 698 | return 0; |
| 699 | /* |
| 700 | * The block appended for this entry is sizeof(uint32_t) + |
| 701 | * nr_hunks * DIFF_HUNKS_HUNK_SIZE bytes. Bound nr_hunks so that |
| 702 | * length fits the uint32_t the dedup index records (and so the |
| 703 | * count itself fits the uint32_t written to the store). |
| 704 | */ |
| 705 | if (!nr_hunks || |
| 706 | nr_hunks > (UINT32_MAX - sizeof(uint32_t)) / DIFF_HUNKS_HUNK_SIZE || |
| 707 | is_null_oid(old_oid) || is_null_oid(new_oid)) |
| 708 | return 0; |
| 709 | if (w->hdat.len > UINT32_MAX) |
| 710 | return 0; |
| 711 | /* |
| 712 | * Coordinates are stored as 32-bit values; a result that cannot |
| 713 | * round-trip is dropped rather than silently truncated. |
| 714 | */ |
| 715 | for (i = 0; i < nr_hunks; i++) |
| 716 | if ((uintmax_t)hunks[i].old_start > (uintmax_t)INT32_MAX || |
| 717 | (uintmax_t)hunks[i].old_count > (uintmax_t)INT32_MAX || |
| 718 | (uintmax_t)hunks[i].new_start > (uintmax_t)INT32_MAX || |
| 719 | (uintmax_t)hunks[i].new_count > (uintmax_t)INT32_MAX) |
| 720 | return 0; |
| 721 | |
| 722 | ALLOC_GROW(w->entries, w->nr + 1, w->alloc); |
| 723 | e = &w->entries[w->nr++]; |
| 724 | oidcpy(&e->old_oid, old_oid); |
| 725 | oidcpy(&e->new_oid, new_oid); |
| 726 | e->xdl_opts = xdl_opts; |
| 727 | |
| 728 | block_start = w->hdat.len; |
| 729 | strbuf_put_be32(&w->hdat, (uint32_t)nr_hunks); |
| 730 | for (i = 0; i < nr_hunks; i++) { |
| 731 | strbuf_put_be32(&w->hdat, hunks[i].old_start); |
| 732 | strbuf_put_be32(&w->hdat, hunks[i].old_count); |
| 733 | strbuf_put_be32(&w->hdat, hunks[i].new_start); |
| 734 | strbuf_put_be32(&w->hdat, hunks[i].new_count); |
| 735 | } |
| 736 | e->hdat_offset = intern_block(w, block_start); |
| 737 | return 1; |
| 738 | } |
| 739 | |
| 740 | void diff_hunks_writer_record_stable(struct diff_hunks_writer *w, |
| 741 | const struct object_id *old_oid, |
| 742 | const struct object_id *new_oid, |
| 743 | int xdl_opts, |
| 744 | const struct precomputed_hunk *trimmed, |
| 745 | size_t nr_trimmed, |
| 746 | const struct precomputed_hunk *full, |
| 747 | size_t nr_full) |
| 748 | { |
| 749 | size_t i; |
| 750 | |
| 751 | if (!w) |
| 752 | return; |
| 753 | /* |
| 754 | * Record only a trim-stable pair, one whose trimmed and |
| 755 | * untrimmed diffs are identical, so the single entry answers |
| 756 | * any consumer at any context (see the top of this file). A |
| 757 | * pair where the two diffs differ is never recorded and every |
| 758 | * consumer computes it. |
| 759 | */ |
| 760 | if (nr_trimmed != nr_full) |
| 761 | return; |
| 762 | for (i = 0; i < nr_trimmed; i++) |
| 763 | if (trimmed[i].old_start != full[i].old_start || |
| 764 | trimmed[i].old_count != full[i].old_count || |
| 765 | trimmed[i].new_start != full[i].new_start || |
| 766 | trimmed[i].new_count != full[i].new_count) |
| 767 | return; |
| 768 | diff_hunks_writer_add(w, old_oid, new_oid, xdl_opts, |
| 769 | trimmed, nr_trimmed); |
| 770 | } |
| 771 | |
| 772 | /* |
| 773 | * Seed the writer with fname's entries so a rewrite preserves them, |
| 774 | * setting *pruned when the rewrite will not carry the whole file |
| 775 | * forward: the file failed its checksum and was discarded outright, or |
| 776 | * individual entries were dropped because they failed the replayable |
| 777 | * check or the writer refused them (a key naming no blob). A |
| 778 | * rewrite re-checksums, so corruption must not be carried forward: |
| 779 | * that would launder it into a checksum-valid file that verify can no |
| 780 | * longer catch. This path already reads the whole file, so verify the |
| 781 | * checksum here (the reader keeps trusting committed files, without |
| 782 | * re-checksumming); an invalid |
| 783 | * entry reads as a miss anyway, so dropping it heals the store rather |
| 784 | * than losing anything a reader could use. |
| 785 | */ |
| 786 | static void diff_hunks_writer_seed(struct diff_hunks_writer *w, |
| 787 | const char *fname, int *pruned) |
| 788 | { |
| 789 | struct diff_hunks_store *s = load_store_at(w->r->hash_algo, fname); |
| 790 | unsigned int rawsz; |
| 791 | size_t entry_size, keysz; |
| 792 | struct precomputed_hunk *hunks = NULL; |
| 793 | size_t hunks_alloc = 0; |
| 794 | uint32_t i, dropped = 0; |
| 795 | |
| 796 | if (!s) |
| 797 | return; |
| 798 | if (!hashfile_checksum_valid(w->r->hash_algo, s->data, s->data_len)) { |
| 799 | warning(_("diff-hunks store %s failed its checksum; " |
| 800 | "discarding it"), fname); |
| 801 | free_store(s); |
| 802 | *pruned = 1; |
| 803 | return; |
| 804 | } |
| 805 | rawsz = s->hash_algo->rawsz; |
| 806 | entry_size = store_index_entry_size(s->hash_algo); |
| 807 | keysz = store_index_key_size(s->hash_algo); |
| 808 | |
| 809 | for (i = 0; i < s->num_entries; i++) { |
| 810 | const unsigned char *ep = s->index + st_mult(entry_size, i); |
| 811 | const unsigned char *old_hash, *new_hash; |
| 812 | struct object_id old_oid, new_oid; |
| 813 | uint32_t xdl_opts, j; |
| 814 | struct precomputed_entry pe; |
| 815 | |
| 816 | decode_store_index_key(ep, rawsz, &old_hash, &new_hash, |
| 817 | &xdl_opts); |
| 818 | oidread(&old_oid, old_hash, s->hash_algo); |
| 819 | oidread(&new_oid, new_hash, s->hash_algo); |
| 820 | if (!precomputed_entry_at(s, index_entry_hdat_offset(ep, keysz), &pe) || |
| 821 | !replayable_hunks(&pe)) { |
| 822 | dropped++; |
| 823 | continue; |
| 824 | } |
| 825 | ALLOC_GROW(hunks, pe.num_hunks, hunks_alloc); |
| 826 | for (j = 0; j < pe.num_hunks; j++) |
| 827 | nth_precomputed_hunk(&pe, j, &hunks[j]); |
| 828 | if (!diff_hunks_writer_add(w, &old_oid, &new_oid, |
| 829 | (int)xdl_opts, hunks, pe.num_hunks)) |
| 830 | dropped++; |
| 831 | } |
| 832 | if (dropped) { |
| 833 | warning(Q_("diff-hunks store %s: dropping %u invalid entry", |
| 834 | "diff-hunks store %s: dropping %u invalid entries", |
| 835 | dropped), fname, dropped); |
| 836 | *pruned = 1; |
| 837 | } |
| 838 | free(hunks); |
| 839 | free_store(s); |
| 840 | } |
| 841 | |
| 842 | /* |
| 843 | * Writing is off by default. It is enabled per invocation by the |
| 844 | * GIT_DIFF_HUNKS_WRITE environment variable, or persistently by the |
| 845 | * diffHunks.write config, with the environment variable winning when |
| 846 | * set. Only a warming run (a diff or log the repository owner chooses |
| 847 | * to run with writing on) enables it, so ordinary reads never mutate |
| 848 | * the store. |
| 849 | */ |
| 850 | static int diff_hunks_write_enabled(struct repository *r) |
| 851 | { |
| 852 | const char *env = getenv("GIT_DIFF_HUNKS_WRITE"); |
| 853 | int val; |
| 854 | |
| 855 | if (env) { |
| 856 | /* |
| 857 | * This is a warming opt-in, so an unparseable value must not |
| 858 | * abort an ordinary read command: treat it as disabled. |
| 859 | */ |
| 860 | val = git_parse_maybe_bool(env); |
| 861 | return val < 0 ? 0 : val; |
| 862 | } |
| 863 | if (!repo_config_get_bool(r, "diffhunks.write", &val)) |
| 864 | return val; |
| 865 | return 0; |
| 866 | } |
| 867 | |
| 868 | struct diff_hunks_writer *diff_hunks_writer_maybe_new(struct repository *r) |
| 869 | { |
| 870 | struct diff_hunks_writer *w; |
| 871 | char *fname; |
| 872 | int pruned; |
| 873 | |
| 874 | if (!diff_hunks_write_enabled(r)) |
| 875 | return NULL; |
| 876 | /* |
| 877 | * Seed from the existing store so a flush merges with it rather |
| 878 | * than replacing it: a later warm adds newly computed pairs |
| 879 | * without discarding what earlier warms recorded. |
| 880 | */ |
| 881 | w = diff_hunks_writer_new(r); |
| 882 | fname = diff_hunks_store_path(r); |
| 883 | pruned = 0; |
| 884 | diff_hunks_writer_seed(w, fname, &pruned); |
| 885 | free(fname); |
| 886 | w->seed_nr = w->nr; |
| 887 | /* |
| 888 | * A pruning seed means the file on disk holds material the |
| 889 | * rewrite must not preserve; flush even if this warm computes |
| 890 | * nothing new, so the store on disk is repaired rather than |
| 891 | * left serving what the seed refused. |
| 892 | */ |
| 893 | w->force_flush = !!pruned; |
| 894 | return w; |
| 895 | } |
| 896 | |
| 897 | static int writer_entry_cmp(const void *va, const void *vb, void *ctx) |
| 898 | { |
| 899 | const struct writer_entry *a = va, *b = vb; |
| 900 | unsigned int rawsz = *(const unsigned int *)ctx; |
| 901 | return cmp_store_index_key(a->old_oid.hash, a->new_oid.hash, |
| 902 | (uint32_t)a->xdl_opts, |
| 903 | b->old_oid.hash, b->new_oid.hash, |
| 904 | (uint32_t)b->xdl_opts, |
| 905 | rawsz); |
| 906 | } |
| 907 | |
| 908 | struct write_ctx { |
| 909 | struct diff_hunks_writer *w; |
| 910 | unsigned int rawsz; |
| 911 | }; |
| 912 | |
| 913 | static int write_index_chunk(struct hashfile *f, void *data) |
| 914 | { |
| 915 | struct write_ctx *ctx = data; |
| 916 | size_t i; |
| 917 | |
| 918 | for (i = 0; i < ctx->w->nr; i++) { |
| 919 | hashwrite(f, ctx->w->entries[i].old_oid.hash, ctx->rawsz); |
| 920 | hashwrite(f, ctx->w->entries[i].new_oid.hash, ctx->rawsz); |
| 921 | hashwrite_be32(f, ctx->w->entries[i].xdl_opts); |
| 922 | hashwrite_be32(f, ctx->w->entries[i].hdat_offset); |
| 923 | } |
| 924 | return 0; |
| 925 | } |
| 926 | |
| 927 | static int write_data_chunk(struct hashfile *f, void *data) |
| 928 | { |
| 929 | struct write_ctx *ctx = data; |
| 930 | hashwrite(f, ctx->w->hdat.buf, ctx->w->hdat.len); |
| 931 | return 0; |
| 932 | } |
| 933 | |
| 934 | /* Sort, dedup, and write the accumulated entries to the file at fname. */ |
| 935 | static int diff_hunks_writer_flush(struct diff_hunks_writer *w, char *fname) |
| 936 | { |
| 937 | struct lock_file lk = LOCK_INIT; |
| 938 | struct hashfile *f; |
| 939 | struct chunkfile *cf; |
| 940 | unsigned int rawsz = w->r->hash_algo->rawsz; |
| 941 | struct write_ctx ctx = { w, rawsz }; |
| 942 | size_t entry_size; |
| 943 | |
| 944 | QSORT_S(w->entries, w->nr, writer_entry_cmp, &rawsz); |
| 945 | |
| 946 | /* |
| 947 | * The same blob pair recurs across history (reverts, cherry- |
| 948 | * picks); identical keys carry identical hunks, so keep one of |
| 949 | * each. The index must stay duplicate-free for binary search. |
| 950 | */ |
| 951 | if (w->nr > 1) { |
| 952 | size_t kept = 1, i; |
| 953 | for (i = 1; i < w->nr; i++) |
| 954 | if (writer_entry_cmp(&w->entries[kept - 1], |
| 955 | &w->entries[i], &rawsz)) |
| 956 | w->entries[kept++] = w->entries[i]; |
| 957 | w->nr = kept; |
| 958 | } |
| 959 | |
| 960 | if (safe_create_leading_directories(w->r, fname)) { |
| 961 | error(_("unable to create directory for %s"), fname); |
| 962 | return -1; |
| 963 | } |
| 964 | if (hold_lock_file_for_update(&lk, fname, 0) < 0) { |
| 965 | error_errno(_("unable to lock %s"), fname); |
| 966 | return -1; |
| 967 | } |
| 968 | adjust_shared_perm(w->r, get_lock_file_path(&lk)); |
| 969 | f = hashfd(w->r->hash_algo, get_lock_file_fd(&lk), |
| 970 | get_lock_file_path(&lk)); |
| 971 | |
| 972 | entry_size = store_index_entry_size(w->r->hash_algo); |
| 973 | cf = init_chunkfile(f); |
| 974 | add_chunk(cf, DIFF_HUNKS_CHUNKID_INDEX, w->nr * entry_size, |
| 975 | write_index_chunk); |
| 976 | add_chunk(cf, DIFF_HUNKS_CHUNKID_DATA, w->hdat.len, write_data_chunk); |
| 977 | |
| 978 | hashwrite_be32(f, DIFF_HUNKS_SIGNATURE); |
| 979 | hashwrite_u8(f, DIFF_HUNKS_VERSION); |
| 980 | hashwrite_u8(f, oid_version(w->r->hash_algo)); |
| 981 | hashwrite_u8(f, get_num_chunks(cf)); |
| 982 | hashwrite_u8(f, 0); /* reserved */ |
| 983 | |
| 984 | write_chunkfile(cf, &ctx); |
| 985 | free_chunkfile(cf); |
| 986 | |
| 987 | /* |
| 988 | * fsync per the user's configuration (like commit-graph and the |
| 989 | * multi-pack-index), then commit atomically. Readers trust the |
| 990 | * committed file rather than re-checksumming it; diff_hunks_verify() |
| 991 | * checks the checksum separately. |
| 992 | */ |
| 993 | finalize_hashfile(f, NULL, FSYNC_COMPONENT_DIFF_HUNKS, |
| 994 | CSUM_HASH_IN_STREAM | CSUM_FSYNC); |
| 995 | /* |
| 996 | * This same process may hold the current store mmapped (a warm |
| 997 | * that also reads); the commit below renames over it, which must |
| 998 | * never land on a live mapping (Windows refuses it). Close the |
| 999 | * store and clear the load-attempted flag first, so the next |
| 1000 | * read loads the committed file. |
| 1001 | */ |
| 1002 | if (w->r->objects) { |
| 1003 | close_diff_hunks_store(w->r->objects); |
| 1004 | w->r->objects->diff_hunks_store_attempted = 0; |
| 1005 | } |
| 1006 | if (commit_lock_file(&lk)) { |
| 1007 | error_errno(_("unable to write %s"), fname); |
| 1008 | return -1; |
| 1009 | } |
| 1010 | return 0; |
| 1011 | } |
| 1012 | |
| 1013 | static void diff_hunks_writer_free(struct diff_hunks_writer *w) |
| 1014 | { |
| 1015 | if (!w) |
| 1016 | return; |
| 1017 | hashmap_clear_and_free(&w->dedup, struct dedup_entry, ent); |
| 1018 | free(w->entries); |
| 1019 | strbuf_release(&w->hdat); |
| 1020 | free(w); |
| 1021 | } |
| 1022 | |
| 1023 | void diff_hunks_writer_finish(struct diff_hunks_writer *w) |
| 1024 | { |
| 1025 | if (!w) |
| 1026 | return; |
| 1027 | /* Skip the flush when the warm recorded nothing beyond its seed. */ |
| 1028 | if (w->nr != w->seed_nr || w->force_flush) { |
| 1029 | char *fname = diff_hunks_store_path(w->r); |
| 1030 | diff_hunks_writer_flush(w, fname); |
| 1031 | free(fname); |
| 1032 | } |
| 1033 | diff_hunks_writer_free(w); |
| 1034 | } |