@leroysheep / BookAlchemy
Code Commits Pulls CI/CD 82,027
next
bisect jch maint master next seen test todo
c 619 lines 15 KB
Raw
1 #define DISABLE_SIGN_COMPARE_WARNINGS
2
3 #include "git-compat-util.h"
4 #include "bloom.h"
5 #include "diff.h"
6 #include "diffcore.h"
7 #include "hashmap.h"
8 #include "commit-graph.h"
9 #include "commit.h"
10 #include "commit-slab.h"
11 #include "tree.h"
12 #include "tree-walk.h"
13 #include "config.h"
14 #include "repository.h"
15
16 define_commit_slab(bloom_filter_slab, struct bloom_filter);
17
18 static struct bloom_filter_slab bloom_filters;
19 static int bloom_filter_slab_initialized;
20
21 struct pathmap_hash_entry {
22 struct hashmap_entry entry;
23 const char path[FLEX_ARRAY];
24 };
25
26 static uint32_t rotate_left(uint32_t value, int32_t count)
27 {
28 uint32_t mask = 8 * sizeof(uint32_t) - 1;
29 count &= mask;
30 return ((value << count) | (value >> ((-count) & mask)));
31 }
32
33 static inline unsigned char get_bitmask(uint32_t pos)
34 {
35 return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
36 }
37
38 static int check_bloom_offset(struct commit_graph *g, uint32_t pos,
39 uint32_t offset)
40 {
41 /*
42 * Note that we allow offsets equal to the data size, which would set
43 * our pointers at one past the end of the chunk memory. This is
44 * necessary because the on-disk index points to the end of the
45 * entries (so we can compute size by comparing adjacent ones). And
46 * naturally the final entry's end is one-past-the-end of the chunk.
47 */
48 if (offset <= g->chunk_bloom_data_size - BLOOMDATA_CHUNK_HEADER_SIZE)
49 return 0;
50
51 warning("ignoring out-of-range offset (%"PRIuMAX") for changed-path"
52 " filter at pos %"PRIuMAX" of %s (chunk size: %"PRIuMAX")",
53 (uintmax_t)offset, (uintmax_t)pos,
54 g->filename, (uintmax_t)g->chunk_bloom_data_size);
55 return -1;
56 }
57
58 int load_bloom_filter_from_graph(struct commit_graph *g,
59 struct bloom_filter *filter,
60 uint32_t graph_pos)
61 {
62 uint32_t lex_pos, start_index, end_index;
63
64 while (graph_pos < g->num_commits_in_base)
65 g = g->base_graph;
66
67 /* The commit graph commit 'c' lives in doesn't carry Bloom filters. */
68 if (!g->chunk_bloom_indexes)
69 return 0;
70
71 lex_pos = graph_pos - g->num_commits_in_base;
72
73 end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
74
75 if (lex_pos > 0)
76 start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1));
77 else
78 start_index = 0;
79
80 if (check_bloom_offset(g, lex_pos, end_index) < 0 ||
81 check_bloom_offset(g, lex_pos - 1, start_index) < 0)
82 return 0;
83
84 if (end_index < start_index) {
85 warning("ignoring decreasing changed-path index offsets"
86 " (%"PRIuMAX" > %"PRIuMAX") for positions"
87 " %"PRIuMAX" and %"PRIuMAX" of %s",
88 (uintmax_t)start_index, (uintmax_t)end_index,
89 (uintmax_t)(lex_pos-1), (uintmax_t)lex_pos,
90 g->filename);
91 return 0;
92 }
93
94 filter->len = end_index - start_index;
95 filter->data = (unsigned char *)(g->chunk_bloom_data +
96 sizeof(unsigned char) * start_index +
97 BLOOMDATA_CHUNK_HEADER_SIZE);
98 filter->version = g->bloom_filter_settings->hash_version;
99 filter->to_free = NULL;
100
101 return 1;
102 }
103
104 /*
105 * Calculate the murmur3 32-bit hash value for the given data
106 * using the given seed.
107 * Produces a uniformly distributed hash value.
108 * Not considered to be cryptographically secure.
109 * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
110 */
111 static uint32_t murmur3_seeded_v2(uint32_t seed, const char *data, size_t len)
112 {
113 const uint32_t c1 = 0xcc9e2d51;
114 const uint32_t c2 = 0x1b873593;
115 const uint32_t r1 = 15;
116 const uint32_t r2 = 13;
117 const uint32_t m = 5;
118 const uint32_t n = 0xe6546b64;
119 int i;
120 uint32_t k1 = 0;
121 const char *tail;
122
123 int len4 = len / sizeof(uint32_t);
124
125 uint32_t k;
126 for (i = 0; i < len4; i++) {
127 uint32_t byte1 = (uint32_t)(unsigned char)data[4*i];
128 uint32_t byte2 = ((uint32_t)(unsigned char)data[4*i + 1]) << 8;
129 uint32_t byte3 = ((uint32_t)(unsigned char)data[4*i + 2]) << 16;
130 uint32_t byte4 = ((uint32_t)(unsigned char)data[4*i + 3]) << 24;
131 k = byte1 | byte2 | byte3 | byte4;
132 k *= c1;
133 k = rotate_left(k, r1);
134 k *= c2;
135
136 seed ^= k;
137 seed = rotate_left(seed, r2) * m + n;
138 }
139
140 tail = (data + len4 * sizeof(uint32_t));
141
142 switch (len & (sizeof(uint32_t) - 1)) {
143 case 3:
144 k1 ^= ((uint32_t)(unsigned char)tail[2]) << 16;
145 /*-fallthrough*/
146 case 2:
147 k1 ^= ((uint32_t)(unsigned char)tail[1]) << 8;
148 /*-fallthrough*/
149 case 1:
150 k1 ^= ((uint32_t)(unsigned char)tail[0]) << 0;
151 k1 *= c1;
152 k1 = rotate_left(k1, r1);
153 k1 *= c2;
154 seed ^= k1;
155 break;
156 }
157
158 seed ^= (uint32_t)len;
159 seed ^= (seed >> 16);
160 seed *= 0x85ebca6b;
161 seed ^= (seed >> 13);
162 seed *= 0xc2b2ae35;
163 seed ^= (seed >> 16);
164
165 return seed;
166 }
167
168 static uint32_t murmur3_seeded_v1(uint32_t seed, const char *data, size_t len)
169 {
170 const uint32_t c1 = 0xcc9e2d51;
171 const uint32_t c2 = 0x1b873593;
172 const uint32_t r1 = 15;
173 const uint32_t r2 = 13;
174 const uint32_t m = 5;
175 const uint32_t n = 0xe6546b64;
176 int i;
177 uint32_t k1 = 0;
178 const char *tail;
179
180 int len4 = len / sizeof(uint32_t);
181
182 uint32_t k;
183 for (i = 0; i < len4; i++) {
184 uint32_t byte1 = (uint32_t)data[4*i];
185 uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8;
186 uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16;
187 uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24;
188 k = byte1 | byte2 | byte3 | byte4;
189 k *= c1;
190 k = rotate_left(k, r1);
191 k *= c2;
192
193 seed ^= k;
194 seed = rotate_left(seed, r2) * m + n;
195 }
196
197 tail = (data + len4 * sizeof(uint32_t));
198
199 switch (len & (sizeof(uint32_t) - 1)) {
200 case 3:
201 k1 ^= ((uint32_t)tail[2]) << 16;
202 /*-fallthrough*/
203 case 2:
204 k1 ^= ((uint32_t)tail[1]) << 8;
205 /*-fallthrough*/
206 case 1:
207 k1 ^= ((uint32_t)tail[0]) << 0;
208 k1 *= c1;
209 k1 = rotate_left(k1, r1);
210 k1 *= c2;
211 seed ^= k1;
212 break;
213 }
214
215 seed ^= (uint32_t)len;
216 seed ^= (seed >> 16);
217 seed *= 0x85ebca6b;
218 seed ^= (seed >> 13);
219 seed *= 0xc2b2ae35;
220 seed ^= (seed >> 16);
221
222 return seed;
223 }
224
225 void bloom_key_fill(struct bloom_key *key, const char *data, size_t len,
226 const struct bloom_filter_settings *settings)
227 {
228 int i;
229 const uint32_t seed0 = 0x293ae76f;
230 const uint32_t seed1 = 0x7e646e2c;
231 uint32_t hash0, hash1;
232 if (settings->hash_version == 2) {
233 hash0 = murmur3_seeded_v2(seed0, data, len);
234 hash1 = murmur3_seeded_v2(seed1, data, len);
235 } else {
236 hash0 = murmur3_seeded_v1(seed0, data, len);
237 hash1 = murmur3_seeded_v1(seed1, data, len);
238 }
239
240 key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));
241 for (i = 0; i < settings->num_hashes; i++)
242 key->hashes[i] = hash0 + i * hash1;
243 }
244
245 void bloom_key_clear(struct bloom_key *key)
246 {
247 FREE_AND_NULL(key->hashes);
248 }
249
250 void add_key_to_filter(const struct bloom_key *key,
251 struct bloom_filter *filter,
252 const struct bloom_filter_settings *settings)
253 {
254 int i;
255 uint64_t mod = filter->len * BITS_PER_WORD;
256
257 for (i = 0; i < settings->num_hashes; i++) {
258 uint64_t hash_mod = key->hashes[i] % mod;
259 uint64_t block_pos = hash_mod / BITS_PER_WORD;
260
261 filter->data[block_pos] |= get_bitmask(hash_mod);
262 }
263 }
264
265 void init_bloom_filters(void)
266 {
267 if (bloom_filter_slab_initialized)
268 return;
269 init_bloom_filter_slab(&bloom_filters);
270 bloom_filter_slab_initialized = 1;
271 }
272
273 static void free_one_bloom_filter(struct bloom_filter *filter)
274 {
275 if (!filter)
276 return;
277 free(filter->to_free);
278 }
279
280 void deinit_bloom_filters(void)
281 {
282 deep_clear_bloom_filter_slab(&bloom_filters, free_one_bloom_filter);
283 bloom_filter_slab_initialized = 0;
284 }
285
286 struct bloom_keyvec *bloom_keyvec_new(const char *path, size_t len,
287 const struct bloom_filter_settings *settings)
288 {
289 struct bloom_keyvec *vec;
290 const char *p;
291 size_t sz;
292 size_t nr = 1;
293
294 p = path;
295 while (*p) {
296 /*
297 * At this point, the path is normalized to use Unix-style
298 * path separators. This is required due to how the
299 * changed-path Bloom filters store the paths.
300 */
301 if (*p == '/')
302 nr++;
303 p++;
304 }
305
306 sz = sizeof(struct bloom_keyvec);
307 sz += nr * sizeof(struct bloom_key);
308 vec = (struct bloom_keyvec *)xcalloc(1, sz);
309 if (!vec)
310 return NULL;
311 vec->count = nr;
312
313 bloom_key_fill(&vec->key[0], path, len, settings);
314 nr = 1;
315 p = path + len - 1;
316 while (p > path) {
317 if (*p == '/') {
318 bloom_key_fill(&vec->key[nr++], path, p - path, settings);
319 }
320 p--;
321 }
322 assert(nr == vec->count);
323 return vec;
324 }
325
326 void bloom_keyvec_free(struct bloom_keyvec *vec)
327 {
328 if (!vec)
329 return;
330 for (size_t nr = 0; nr < vec->count; nr++)
331 bloom_key_clear(&vec->key[nr]);
332 free(vec);
333 }
334
335 static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,
336 const struct hashmap_entry *eptr,
337 const struct hashmap_entry *entry_or_key,
338 const void *keydata UNUSED)
339 {
340 const struct pathmap_hash_entry *e1, *e2;
341
342 e1 = container_of(eptr, const struct pathmap_hash_entry, entry);
343 e2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry);
344
345 return strcmp(e1->path, e2->path);
346 }
347
348 static void init_truncated_large_filter(struct bloom_filter *filter,
349 int version)
350 {
351 filter->data = filter->to_free = xmalloc(1);
352 filter->data[0] = 0xFF;
353 filter->len = 1;
354 filter->version = version;
355 }
356
357 #define VISITED (1u<<21)
358 #define HIGH_BITS (1u<<22)
359
360 static int has_entries_with_high_bit(struct repository *r, struct tree *t)
361 {
362 if (repo_parse_tree(r, t))
363 return 1;
364
365 if (!(t->object.flags & VISITED)) {
366 struct tree_desc desc;
367 struct name_entry entry;
368
369 init_tree_desc(&desc, &t->object.oid, t->buffer, t->size);
370 while (tree_entry(&desc, &entry)) {
371 size_t i;
372 for (i = 0; i < entry.pathlen; i++) {
373 if (entry.path[i] & 0x80) {
374 t->object.flags |= HIGH_BITS;
375 goto done;
376 }
377 }
378
379 if (S_ISDIR(entry.mode)) {
380 struct tree *sub = lookup_tree(r, &entry.oid);
381 if (sub && has_entries_with_high_bit(r, sub)) {
382 t->object.flags |= HIGH_BITS;
383 goto done;
384 }
385 }
386
387 }
388
389 done:
390 t->object.flags |= VISITED;
391 }
392
393 return !!(t->object.flags & HIGH_BITS);
394 }
395
396 static int commit_tree_has_high_bit_paths(struct repository *r,
397 struct commit *c)
398 {
399 struct tree *t;
400 if (repo_parse_commit(r, c))
401 return 1;
402 t = repo_get_commit_tree(r, c);
403 if (!t)
404 return 1;
405 return has_entries_with_high_bit(r, t);
406 }
407
408 static struct bloom_filter *upgrade_filter(struct repository *r, struct commit *c,
409 struct bloom_filter *filter,
410 int hash_version)
411 {
412 struct commit_list *p = c->parents;
413 if (commit_tree_has_high_bit_paths(r, c))
414 return NULL;
415
416 if (p && commit_tree_has_high_bit_paths(r, p->item))
417 return NULL;
418
419 filter->version = hash_version;
420
421 return filter;
422 }
423
424 struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c)
425 {
426 struct bloom_filter *filter;
427 int hash_version;
428
429 filter = get_or_compute_bloom_filter(r, c, 0, NULL, NULL);
430 if (!filter)
431 return NULL;
432
433 prepare_repo_settings(r);
434 hash_version = r->settings.commit_graph_changed_paths_version;
435
436 if (!(hash_version == -1 || hash_version == filter->version))
437 return NULL; /* unusable filter */
438 return filter;
439 }
440
441 struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
442 struct commit *c,
443 int compute_if_not_present,
444 const struct bloom_filter_settings *settings,
445 enum bloom_filter_computed *computed)
446 {
447 struct bloom_filter *filter;
448 int i;
449 struct diff_options diffopt;
450
451 if (computed)
452 *computed = BLOOM_NOT_COMPUTED;
453
454 if (!bloom_filters.slab_size)
455 return NULL;
456
457 filter = bloom_filter_slab_at(&bloom_filters, c);
458
459 if (!filter->data) {
460 struct commit_graph *g;
461 uint32_t graph_pos;
462
463 g = repo_find_commit_pos_in_graph(r, c, &graph_pos);
464 if (g)
465 load_bloom_filter_from_graph(g, filter, graph_pos);
466 }
467
468 if (filter->data && filter->len) {
469 struct bloom_filter *upgrade;
470 if (!settings || settings->hash_version == filter->version)
471 return filter;
472
473 /* version mismatch, see if we can upgrade */
474 if (compute_if_not_present &&
475 git_env_bool("GIT_TEST_UPGRADE_BLOOM_FILTERS", 1)) {
476 upgrade = upgrade_filter(r, c, filter,
477 settings->hash_version);
478 if (upgrade) {
479 if (computed)
480 *computed |= BLOOM_UPGRADED;
481 return upgrade;
482 }
483 }
484 }
485 if (!compute_if_not_present)
486 return NULL;
487
488 repo_diff_setup(r, &diffopt);
489 diffopt.flags.recursive = 1;
490 diffopt.detect_rename = 0;
491 diffopt.max_changes = settings->max_changed_paths;
492 diff_setup_done(&diffopt);
493
494 /* ensure commit is parsed so we have parent information */
495 repo_parse_commit(r, c);
496
497 if (c->parents)
498 diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt);
499 else
500 diff_tree_oid(NULL, &c->object.oid, "", &diffopt);
501 diffcore_std(&diffopt);
502
503 if (diff_queued_diff.nr <= settings->max_changed_paths) {
504 struct hashmap pathmap = HASHMAP_INIT(pathmap_cmp, NULL);
505 struct pathmap_hash_entry *e;
506 struct hashmap_iter iter;
507
508 for (i = 0; i < diff_queued_diff.nr; i++) {
509 char *path = diff_queued_diff.queue[i]->two->path;
510
511 /*
512 * Add each leading directory of the changed file, i.e. for
513 * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
514 * the Bloom filter could be used to speed up commands like
515 * 'git log dir/subdir', too.
516 *
517 * Note that directories are added without the trailing '/'.
518 */
519 do {
520 char *last_slash = strrchr(path, '/');
521
522 FLEX_ALLOC_STR(e, path, path);
523 hashmap_entry_init(&e->entry, strhash(path));
524
525 if (!hashmap_get(&pathmap, &e->entry, NULL))
526 hashmap_add(&pathmap, &e->entry);
527 else
528 free(e);
529
530 if (!last_slash)
531 last_slash = path;
532 *last_slash = '\0';
533
534 } while (*path);
535 }
536
537 if (hashmap_get_size(&pathmap) > settings->max_changed_paths) {
538 init_truncated_large_filter(filter,
539 settings->hash_version);
540 if (computed)
541 *computed |= BLOOM_TRUNC_LARGE;
542 goto cleanup;
543 }
544
545 filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
546 filter->version = settings->hash_version;
547 if (!filter->len) {
548 if (computed)
549 *computed |= BLOOM_TRUNC_EMPTY;
550 filter->len = 1;
551 }
552 CALLOC_ARRAY(filter->data, filter->len);
553 filter->to_free = filter->data;
554
555 hashmap_for_each_entry(&pathmap, &iter, e, entry) {
556 struct bloom_key key;
557 bloom_key_fill(&key, e->path, strlen(e->path), settings);
558 add_key_to_filter(&key, filter, settings);
559 bloom_key_clear(&key);
560 }
561
562 cleanup:
563 hashmap_clear_and_free(&pathmap, struct pathmap_hash_entry, entry);
564 } else {
565 init_truncated_large_filter(filter, settings->hash_version);
566
567 if (computed)
568 *computed |= BLOOM_TRUNC_LARGE;
569 }
570
571 if (computed)
572 *computed |= BLOOM_COMPUTED;
573
574 diff_queue_clear(&diff_queued_diff);
575 return filter;
576 }
577
578 int bloom_filter_contains(const struct bloom_filter *filter,
579 const struct bloom_key *key,
580 const struct bloom_filter_settings *settings)
581 {
582 int i;
583 uint64_t mod = filter->len * BITS_PER_WORD;
584
585 if (!mod)
586 return -1;
587
588 for (i = 0; i < settings->num_hashes; i++) {
589 uint64_t hash_mod = key->hashes[i] % mod;
590 uint64_t block_pos = hash_mod / BITS_PER_WORD;
591 if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
592 return 0;
593 }
594
595 return 1;
596 }
597
598 int bloom_filter_contains_vec(const struct bloom_filter *filter,
599 const struct bloom_keyvec *vec,
600 const struct bloom_filter_settings *settings)
601 {
602 int ret = 1;
603
604 for (size_t nr = 0; ret > 0 && nr < vec->count; nr++)
605 ret = bloom_filter_contains(filter, &vec->key[nr], settings);
606
607 return ret;
608 }
609
610 uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,
611 int version)
612 {
613 if (version == 2)
614 return murmur3_seeded_v2(seed, data, len);
615 else if (version == 1)
616 return murmur3_seeded_v1(seed, data, len);
617 else
618 BUG("unexpected bloom version: %d", version);
619 }