blame: use changed-path Bloom filters
[git.git] / bloom.c
blobdd9bab9bbd6cfd6b71a39e73813ecf745bec835e
1 #include "git-compat-util.h"
2 #include "bloom.h"
3 #include "diff.h"
4 #include "diffcore.h"
5 #include "revision.h"
6 #include "hashmap.h"
7 #include "commit-graph.h"
8 #include "commit.h"
10 define_commit_slab(bloom_filter_slab, struct bloom_filter);
12 struct bloom_filter_slab bloom_filters;
14 struct pathmap_hash_entry {
15 struct hashmap_entry entry;
16 const char path[FLEX_ARRAY];
19 static uint32_t rotate_left(uint32_t value, int32_t count)
21 uint32_t mask = 8 * sizeof(uint32_t) - 1;
22 count &= mask;
23 return ((value << count) | (value >> ((-count) & mask)));
26 static inline unsigned char get_bitmask(uint32_t pos)
28 return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
31 static int load_bloom_filter_from_graph(struct commit_graph *g,
32 struct bloom_filter *filter,
33 struct commit *c)
35 uint32_t lex_pos, start_index, end_index;
37 while (c->graph_pos < g->num_commits_in_base)
38 g = g->base_graph;
40 /* The commit graph commit 'c' lives in doesn't carry bloom filters. */
41 if (!g->chunk_bloom_indexes)
42 return 0;
44 lex_pos = c->graph_pos - g->num_commits_in_base;
46 end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
48 if (lex_pos > 0)
49 start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1));
50 else
51 start_index = 0;
53 filter->len = end_index - start_index;
54 filter->data = (unsigned char *)(g->chunk_bloom_data +
55 sizeof(unsigned char) * start_index +
56 BLOOMDATA_CHUNK_HEADER_SIZE);
58 return 1;
62 * Calculate the murmur3 32-bit hash value for the given data
63 * using the given seed.
64 * Produces a uniformly distributed hash value.
65 * Not considered to be cryptographically secure.
66 * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
68 uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)
70 const uint32_t c1 = 0xcc9e2d51;
71 const uint32_t c2 = 0x1b873593;
72 const uint32_t r1 = 15;
73 const uint32_t r2 = 13;
74 const uint32_t m = 5;
75 const uint32_t n = 0xe6546b64;
76 int i;
77 uint32_t k1 = 0;
78 const char *tail;
80 int len4 = len / sizeof(uint32_t);
82 uint32_t k;
83 for (i = 0; i < len4; i++) {
84 uint32_t byte1 = (uint32_t)data[4*i];
85 uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8;
86 uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16;
87 uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24;
88 k = byte1 | byte2 | byte3 | byte4;
89 k *= c1;
90 k = rotate_left(k, r1);
91 k *= c2;
93 seed ^= k;
94 seed = rotate_left(seed, r2) * m + n;
97 tail = (data + len4 * sizeof(uint32_t));
99 switch (len & (sizeof(uint32_t) - 1)) {
100 case 3:
101 k1 ^= ((uint32_t)tail[2]) << 16;
102 /*-fallthrough*/
103 case 2:
104 k1 ^= ((uint32_t)tail[1]) << 8;
105 /*-fallthrough*/
106 case 1:
107 k1 ^= ((uint32_t)tail[0]) << 0;
108 k1 *= c1;
109 k1 = rotate_left(k1, r1);
110 k1 *= c2;
111 seed ^= k1;
112 break;
115 seed ^= (uint32_t)len;
116 seed ^= (seed >> 16);
117 seed *= 0x85ebca6b;
118 seed ^= (seed >> 13);
119 seed *= 0xc2b2ae35;
120 seed ^= (seed >> 16);
122 return seed;
125 void fill_bloom_key(const char *data,
126 size_t len,
127 struct bloom_key *key,
128 const struct bloom_filter_settings *settings)
130 int i;
131 const uint32_t seed0 = 0x293ae76f;
132 const uint32_t seed1 = 0x7e646e2c;
133 const uint32_t hash0 = murmur3_seeded(seed0, data, len);
134 const uint32_t hash1 = murmur3_seeded(seed1, data, len);
136 key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));
137 for (i = 0; i < settings->num_hashes; i++)
138 key->hashes[i] = hash0 + i * hash1;
141 void add_key_to_filter(const struct bloom_key *key,
142 struct bloom_filter *filter,
143 const struct bloom_filter_settings *settings)
145 int i;
146 uint64_t mod = filter->len * BITS_PER_WORD;
148 for (i = 0; i < settings->num_hashes; i++) {
149 uint64_t hash_mod = key->hashes[i] % mod;
150 uint64_t block_pos = hash_mod / BITS_PER_WORD;
152 filter->data[block_pos] |= get_bitmask(hash_mod);
156 void init_bloom_filters(void)
158 init_bloom_filter_slab(&bloom_filters);
161 struct bloom_filter *get_bloom_filter(struct repository *r,
162 struct commit *c,
163 int compute_if_not_present)
165 struct bloom_filter *filter;
166 struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
167 int i;
168 struct diff_options diffopt;
169 int max_changes = 512;
171 if (bloom_filters.slab_size == 0)
172 return NULL;
174 filter = bloom_filter_slab_at(&bloom_filters, c);
176 if (!filter->data) {
177 load_commit_graph_info(r, c);
178 if (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&
179 r->objects->commit_graph->chunk_bloom_indexes) {
180 if (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))
181 return filter;
182 else
183 return NULL;
187 if (filter->data || !compute_if_not_present)
188 return filter;
190 repo_diff_setup(r, &diffopt);
191 diffopt.flags.recursive = 1;
192 diffopt.detect_rename = 0;
193 diffopt.max_changes = max_changes;
194 diff_setup_done(&diffopt);
196 if (c->parents)
197 diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt);
198 else
199 diff_tree_oid(NULL, &c->object.oid, "", &diffopt);
200 diffcore_std(&diffopt);
202 if (diff_queued_diff.nr <= max_changes) {
203 struct hashmap pathmap;
204 struct pathmap_hash_entry *e;
205 struct hashmap_iter iter;
206 hashmap_init(&pathmap, NULL, NULL, 0);
208 for (i = 0; i < diff_queued_diff.nr; i++) {
209 const char *path = diff_queued_diff.queue[i]->two->path;
212 * Add each leading directory of the changed file, i.e. for
213 * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
214 * the Bloom filter could be used to speed up commands like
215 * 'git log dir/subdir', too.
217 * Note that directories are added without the trailing '/'.
219 do {
220 char *last_slash = strrchr(path, '/');
222 FLEX_ALLOC_STR(e, path, path);
223 hashmap_entry_init(&e->entry, strhash(path));
224 hashmap_add(&pathmap, &e->entry);
226 if (!last_slash)
227 last_slash = (char*)path;
228 *last_slash = '\0';
230 } while (*path);
232 diff_free_filepair(diff_queued_diff.queue[i]);
235 filter->len = (hashmap_get_size(&pathmap) * settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
236 filter->data = xcalloc(filter->len, sizeof(unsigned char));
238 hashmap_for_each_entry(&pathmap, &iter, e, entry) {
239 struct bloom_key key;
240 fill_bloom_key(e->path, strlen(e->path), &key, &settings);
241 add_key_to_filter(&key, filter, &settings);
244 hashmap_free_entries(&pathmap, struct pathmap_hash_entry, entry);
245 } else {
246 for (i = 0; i < diff_queued_diff.nr; i++)
247 diff_free_filepair(diff_queued_diff.queue[i]);
248 filter->data = NULL;
249 filter->len = 0;
252 free(diff_queued_diff.queue);
253 DIFF_QUEUE_CLEAR(&diff_queued_diff);
255 return filter;
258 int bloom_filter_contains(const struct bloom_filter *filter,
259 const struct bloom_key *key,
260 const struct bloom_filter_settings *settings)
262 int i;
263 uint64_t mod = filter->len * BITS_PER_WORD;
265 if (!mod)
266 return -1;
268 for (i = 0; i < settings->num_hashes; i++) {
269 uint64_t hash_mod = key->hashes[i] % mod;
270 uint64_t block_pos = hash_mod / BITS_PER_WORD;
271 if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
272 return 0;
275 return 1;