| #include "git-compat-util.h" |
| #include "bloom.h" |
| #include "diff.h" |
| #include "diffcore.h" |
| #include "hashmap.h" |
| #include "commit-graph.h" |
| #include "commit.h" |
| #include "commit-slab.h" |
| |
| define_commit_slab(bloom_filter_slab, struct bloom_filter); |
| |
| static struct bloom_filter_slab bloom_filters; |
| |
| struct pathmap_hash_entry { |
| struct hashmap_entry entry; |
| const char path[FLEX_ARRAY]; |
| }; |
| |
| static uint32_t rotate_left(uint32_t value, int32_t count) |
| { |
| uint32_t mask = 8 * sizeof(uint32_t) - 1; |
| count &= mask; |
| return ((value << count) | (value >> ((-count) & mask))); |
| } |
| |
| static inline unsigned char get_bitmask(uint32_t pos) |
| { |
| return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1)); |
| } |
| |
| static int check_bloom_offset(struct commit_graph *g, uint32_t pos, |
| uint32_t offset) |
| { |
| /* |
| * Note that we allow offsets equal to the data size, which would set |
| * our pointers at one past the end of the chunk memory. This is |
| * necessary because the on-disk index points to the end of the |
| * entries (so we can compute size by comparing adjacent ones). And |
| * naturally the final entry's end is one-past-the-end of the chunk. |
| */ |
| if (offset <= g->chunk_bloom_data_size - BLOOMDATA_CHUNK_HEADER_SIZE) |
| return 0; |
| |
| warning("ignoring out-of-range offset (%"PRIuMAX") for changed-path" |
| " filter at pos %"PRIuMAX" of %s (chunk size: %"PRIuMAX")", |
| (uintmax_t)offset, (uintmax_t)pos, |
| g->filename, (uintmax_t)g->chunk_bloom_data_size); |
| return -1; |
| } |
| |
| static int load_bloom_filter_from_graph(struct commit_graph *g, |
| struct bloom_filter *filter, |
| uint32_t graph_pos) |
| { |
| uint32_t lex_pos, start_index, end_index; |
| |
| while (graph_pos < g->num_commits_in_base) |
| g = g->base_graph; |
| |
| /* The commit graph commit 'c' lives in doesn't carry Bloom filters. */ |
| if (!g->chunk_bloom_indexes) |
| return 0; |
| |
| lex_pos = graph_pos - g->num_commits_in_base; |
| |
| end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos); |
| |
| if (lex_pos > 0) |
| start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1)); |
| else |
| start_index = 0; |
| |
| if (check_bloom_offset(g, lex_pos, end_index) < 0 || |
| check_bloom_offset(g, lex_pos - 1, start_index) < 0) |
| return 0; |
| |
| if (end_index < start_index) { |
| warning("ignoring decreasing changed-path index offsets" |
| " (%"PRIuMAX" > %"PRIuMAX") for positions" |
| " %"PRIuMAX" and %"PRIuMAX" of %s", |
| (uintmax_t)start_index, (uintmax_t)end_index, |
| (uintmax_t)(lex_pos-1), (uintmax_t)lex_pos, |
| g->filename); |
| return 0; |
| } |
| |
| filter->len = end_index - start_index; |
| filter->data = (unsigned char *)(g->chunk_bloom_data + |
| sizeof(unsigned char) * start_index + |
| BLOOMDATA_CHUNK_HEADER_SIZE); |
| |
| return 1; |
| } |
| |
| /* |
| * Calculate the murmur3 32-bit hash value for the given data |
| * using the given seed. |
| * Produces a uniformly distributed hash value. |
| * Not considered to be cryptographically secure. |
| * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm |
| */ |
| uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len) |
| { |
| const uint32_t c1 = 0xcc9e2d51; |
| const uint32_t c2 = 0x1b873593; |
| const uint32_t r1 = 15; |
| const uint32_t r2 = 13; |
| const uint32_t m = 5; |
| const uint32_t n = 0xe6546b64; |
| int i; |
| uint32_t k1 = 0; |
| const char *tail; |
| |
| int len4 = len / sizeof(uint32_t); |
| |
| uint32_t k; |
| for (i = 0; i < len4; i++) { |
| uint32_t byte1 = (uint32_t)data[4*i]; |
| uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8; |
| uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16; |
| uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24; |
| k = byte1 | byte2 | byte3 | byte4; |
| k *= c1; |
| k = rotate_left(k, r1); |
| k *= c2; |
| |
| seed ^= k; |
| seed = rotate_left(seed, r2) * m + n; |
| } |
| |
| tail = (data + len4 * sizeof(uint32_t)); |
| |
| switch (len & (sizeof(uint32_t) - 1)) { |
| case 3: |
| k1 ^= ((uint32_t)tail[2]) << 16; |
| /*-fallthrough*/ |
| case 2: |
| k1 ^= ((uint32_t)tail[1]) << 8; |
| /*-fallthrough*/ |
| case 1: |
| k1 ^= ((uint32_t)tail[0]) << 0; |
| k1 *= c1; |
| k1 = rotate_left(k1, r1); |
| k1 *= c2; |
| seed ^= k1; |
| break; |
| } |
| |
| seed ^= (uint32_t)len; |
| seed ^= (seed >> 16); |
| seed *= 0x85ebca6b; |
| seed ^= (seed >> 13); |
| seed *= 0xc2b2ae35; |
| seed ^= (seed >> 16); |
| |
| return seed; |
| } |
| |
| void fill_bloom_key(const char *data, |
| size_t len, |
| struct bloom_key *key, |
| const struct bloom_filter_settings *settings) |
| { |
| int i; |
| const uint32_t seed0 = 0x293ae76f; |
| const uint32_t seed1 = 0x7e646e2c; |
| const uint32_t hash0 = murmur3_seeded(seed0, data, len); |
| const uint32_t hash1 = murmur3_seeded(seed1, data, len); |
| |
| key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t)); |
| for (i = 0; i < settings->num_hashes; i++) |
| key->hashes[i] = hash0 + i * hash1; |
| } |
| |
| void clear_bloom_key(struct bloom_key *key) |
| { |
| FREE_AND_NULL(key->hashes); |
| } |
| |
| void add_key_to_filter(const struct bloom_key *key, |
| struct bloom_filter *filter, |
| const struct bloom_filter_settings *settings) |
| { |
| int i; |
| uint64_t mod = filter->len * BITS_PER_WORD; |
| |
| for (i = 0; i < settings->num_hashes; i++) { |
| uint64_t hash_mod = key->hashes[i] % mod; |
| uint64_t block_pos = hash_mod / BITS_PER_WORD; |
| |
| filter->data[block_pos] |= get_bitmask(hash_mod); |
| } |
| } |
| |
| void init_bloom_filters(void) |
| { |
| init_bloom_filter_slab(&bloom_filters); |
| } |
| |
| static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, |
| const struct hashmap_entry *eptr, |
| const struct hashmap_entry *entry_or_key, |
| const void *keydata UNUSED) |
| { |
| const struct pathmap_hash_entry *e1, *e2; |
| |
| e1 = container_of(eptr, const struct pathmap_hash_entry, entry); |
| e2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry); |
| |
| return strcmp(e1->path, e2->path); |
| } |
| |
| static void init_truncated_large_filter(struct bloom_filter *filter) |
| { |
| filter->data = xmalloc(1); |
| filter->data[0] = 0xFF; |
| filter->len = 1; |
| } |
| |
| struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, |
| struct commit *c, |
| int compute_if_not_present, |
| const struct bloom_filter_settings *settings, |
| enum bloom_filter_computed *computed) |
| { |
| struct bloom_filter *filter; |
| int i; |
| struct diff_options diffopt; |
| |
| if (computed) |
| *computed = BLOOM_NOT_COMPUTED; |
| |
| if (!bloom_filters.slab_size) |
| return NULL; |
| |
| filter = bloom_filter_slab_at(&bloom_filters, c); |
| |
| if (!filter->data) { |
| uint32_t graph_pos; |
| if (repo_find_commit_pos_in_graph(r, c, &graph_pos)) |
| load_bloom_filter_from_graph(r->objects->commit_graph, |
| filter, graph_pos); |
| } |
| |
| if (filter->data && filter->len) |
| return filter; |
| if (!compute_if_not_present) |
| return NULL; |
| |
| repo_diff_setup(r, &diffopt); |
| diffopt.flags.recursive = 1; |
| diffopt.detect_rename = 0; |
| diffopt.max_changes = settings->max_changed_paths; |
| diff_setup_done(&diffopt); |
| |
| /* ensure commit is parsed so we have parent information */ |
| repo_parse_commit(r, c); |
| |
| if (c->parents) |
| diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt); |
| else |
| diff_tree_oid(NULL, &c->object.oid, "", &diffopt); |
| diffcore_std(&diffopt); |
| |
| if (diff_queued_diff.nr <= settings->max_changed_paths) { |
| struct hashmap pathmap = HASHMAP_INIT(pathmap_cmp, NULL); |
| struct pathmap_hash_entry *e; |
| struct hashmap_iter iter; |
| |
| for (i = 0; i < diff_queued_diff.nr; i++) { |
| const char *path = diff_queued_diff.queue[i]->two->path; |
| |
| /* |
| * Add each leading directory of the changed file, i.e. for |
| * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so |
| * the Bloom filter could be used to speed up commands like |
| * 'git log dir/subdir', too. |
| * |
| * Note that directories are added without the trailing '/'. |
| */ |
| do { |
| char *last_slash = strrchr(path, '/'); |
| |
| FLEX_ALLOC_STR(e, path, path); |
| hashmap_entry_init(&e->entry, strhash(path)); |
| |
| if (!hashmap_get(&pathmap, &e->entry, NULL)) |
| hashmap_add(&pathmap, &e->entry); |
| else |
| free(e); |
| |
| if (!last_slash) |
| last_slash = (char*)path; |
| *last_slash = '\0'; |
| |
| } while (*path); |
| |
| diff_free_filepair(diff_queued_diff.queue[i]); |
| } |
| |
| if (hashmap_get_size(&pathmap) > settings->max_changed_paths) { |
| init_truncated_large_filter(filter); |
| if (computed) |
| *computed |= BLOOM_TRUNC_LARGE; |
| goto cleanup; |
| } |
| |
| filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD; |
| if (!filter->len) { |
| if (computed) |
| *computed |= BLOOM_TRUNC_EMPTY; |
| filter->len = 1; |
| } |
| CALLOC_ARRAY(filter->data, filter->len); |
| |
| hashmap_for_each_entry(&pathmap, &iter, e, entry) { |
| struct bloom_key key; |
| fill_bloom_key(e->path, strlen(e->path), &key, settings); |
| add_key_to_filter(&key, filter, settings); |
| clear_bloom_key(&key); |
| } |
| |
| cleanup: |
| hashmap_clear_and_free(&pathmap, struct pathmap_hash_entry, entry); |
| } else { |
| for (i = 0; i < diff_queued_diff.nr; i++) |
| diff_free_filepair(diff_queued_diff.queue[i]); |
| init_truncated_large_filter(filter); |
| |
| if (computed) |
| *computed |= BLOOM_TRUNC_LARGE; |
| } |
| |
| if (computed) |
| *computed |= BLOOM_COMPUTED; |
| |
| free(diff_queued_diff.queue); |
| DIFF_QUEUE_CLEAR(&diff_queued_diff); |
| |
| return filter; |
| } |
| |
| int bloom_filter_contains(const struct bloom_filter *filter, |
| const struct bloom_key *key, |
| const struct bloom_filter_settings *settings) |
| { |
| int i; |
| uint64_t mod = filter->len * BITS_PER_WORD; |
| |
| if (!mod) |
| return -1; |
| |
| for (i = 0; i < settings->num_hashes; i++) { |
| uint64_t hash_mod = key->hashes[i] % mod; |
| uint64_t block_pos = hash_mod / BITS_PER_WORD; |
| if (!(filter->data[block_pos] & get_bitmask(hash_mod))) |
| return 0; |
| } |
| |
| return 1; |
| } |