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