diff options
Diffstat (limited to 'third_party/git/bloom.c')
| -rw-r--r-- | third_party/git/bloom.c | 327 |
1 files changed, 0 insertions, 327 deletions
diff --git a/third_party/git/bloom.c b/third_party/git/bloom.c deleted file mode 100644 index 68c73200a54a..000000000000 --- a/third_party/git/bloom.c +++ /dev/null @@ -1,327 +0,0 @@ -#include "git-compat-util.h" -#include "bloom.h" -#include "diff.h" -#include "diffcore.h" -#include "revision.h" -#include "hashmap.h" -#include "commit-graph.h" -#include "commit.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 load_bloom_filter_from_graph(struct commit_graph *g, - struct bloom_filter *filter, - struct commit *c) -{ - uint32_t lex_pos, start_index, end_index; - uint32_t graph_pos = commit_graph_position(c); - - 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; - - 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, - const struct hashmap_entry *eptr, - const struct hashmap_entry *entry_or_key, - const void *keydata) -{ - 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) { - load_commit_graph_info(r, c); - if (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH) - load_bloom_filter_from_graph(r->objects->commit_graph, filter, c); - } - - 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; - struct pathmap_hash_entry *e; - struct hashmap_iter iter; - hashmap_init(&pathmap, pathmap_cmp, NULL, 0); - - 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; - } - filter->data = xcalloc(filter->len, sizeof(unsigned char)); - - 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); - } - - cleanup: - hashmap_free_entries(&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; -} |