Merge branch 'en/clean-cleanups'
[git] / bloom.c
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"
9
10 define_commit_slab(bloom_filter_slab, struct bloom_filter);
11
12 static struct bloom_filter_slab bloom_filters;
13
14 struct pathmap_hash_entry {
15     struct hashmap_entry entry;
16     const char path[FLEX_ARRAY];
17 };
18
19 static uint32_t rotate_left(uint32_t value, int32_t count)
20 {
21         uint32_t mask = 8 * sizeof(uint32_t) - 1;
22         count &= mask;
23         return ((value << count) | (value >> ((-count) & mask)));
24 }
25
26 static inline unsigned char get_bitmask(uint32_t pos)
27 {
28         return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
29 }
30
31 static int load_bloom_filter_from_graph(struct commit_graph *g,
32                                         struct bloom_filter *filter,
33                                         struct commit *c)
34 {
35         uint32_t lex_pos, start_index, end_index;
36
37         while (c->graph_pos < g->num_commits_in_base)
38                 g = g->base_graph;
39
40         /* The commit graph commit 'c' lives in doesn't carry bloom filters. */
41         if (!g->chunk_bloom_indexes)
42                 return 0;
43
44         lex_pos = c->graph_pos - g->num_commits_in_base;
45
46         end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
47
48         if (lex_pos > 0)
49                 start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1));
50         else
51                 start_index = 0;
52
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);
57
58         return 1;
59 }
60
61 /*
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
67  */
68 uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)
69 {
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;
79
80         int len4 = len / sizeof(uint32_t);
81
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;
92
93                 seed ^= k;
94                 seed = rotate_left(seed, r2) * m + n;
95         }
96
97         tail = (data + len4 * sizeof(uint32_t));
98
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;
113         }
114
115         seed ^= (uint32_t)len;
116         seed ^= (seed >> 16);
117         seed *= 0x85ebca6b;
118         seed ^= (seed >> 13);
119         seed *= 0xc2b2ae35;
120         seed ^= (seed >> 16);
121
122         return seed;
123 }
124
125 void fill_bloom_key(const char *data,
126                     size_t len,
127                     struct bloom_key *key,
128                     const struct bloom_filter_settings *settings)
129 {
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);
135
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;
139 }
140
141 void clear_bloom_key(struct bloom_key *key)
142 {
143         FREE_AND_NULL(key->hashes);
144 }
145
146 void add_key_to_filter(const struct bloom_key *key,
147                        struct bloom_filter *filter,
148                        const struct bloom_filter_settings *settings)
149 {
150         int i;
151         uint64_t mod = filter->len * BITS_PER_WORD;
152
153         for (i = 0; i < settings->num_hashes; i++) {
154                 uint64_t hash_mod = key->hashes[i] % mod;
155                 uint64_t block_pos = hash_mod / BITS_PER_WORD;
156
157                 filter->data[block_pos] |= get_bitmask(hash_mod);
158         }
159 }
160
161 void init_bloom_filters(void)
162 {
163         init_bloom_filter_slab(&bloom_filters);
164 }
165
166 static int pathmap_cmp(const void *hashmap_cmp_fn_data,
167                        const struct hashmap_entry *eptr,
168                        const struct hashmap_entry *entry_or_key,
169                        const void *keydata)
170 {
171         const struct pathmap_hash_entry *e1, *e2;
172
173         e1 = container_of(eptr, const struct pathmap_hash_entry, entry);
174         e2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry);
175
176         return strcmp(e1->path, e2->path);
177 }
178
179 struct bloom_filter *get_bloom_filter(struct repository *r,
180                                       struct commit *c,
181                                       int compute_if_not_present)
182 {
183         struct bloom_filter *filter;
184         struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
185         int i;
186         struct diff_options diffopt;
187         int max_changes = 512;
188
189         if (bloom_filters.slab_size == 0)
190                 return NULL;
191
192         filter = bloom_filter_slab_at(&bloom_filters, c);
193
194         if (!filter->data) {
195                 load_commit_graph_info(r, c);
196                 if (c->graph_pos != COMMIT_NOT_FROM_GRAPH &&
197                         r->objects->commit_graph->chunk_bloom_indexes) {
198                         if (load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))
199                                 return filter;
200                         else
201                                 return NULL;
202                 }
203         }
204
205         if (filter->data || !compute_if_not_present)
206                 return filter;
207
208         repo_diff_setup(r, &diffopt);
209         diffopt.flags.recursive = 1;
210         diffopt.detect_rename = 0;
211         diffopt.max_changes = max_changes;
212         diff_setup_done(&diffopt);
213
214         /* ensure commit is parsed so we have parent information */
215         repo_parse_commit(r, c);
216
217         if (c->parents)
218                 diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt);
219         else
220                 diff_tree_oid(NULL, &c->object.oid, "", &diffopt);
221         diffcore_std(&diffopt);
222
223         if (diffopt.num_changes <= max_changes) {
224                 struct hashmap pathmap;
225                 struct pathmap_hash_entry *e;
226                 struct hashmap_iter iter;
227                 hashmap_init(&pathmap, pathmap_cmp, NULL, 0);
228
229                 for (i = 0; i < diff_queued_diff.nr; i++) {
230                         const char *path = diff_queued_diff.queue[i]->two->path;
231
232                         /*
233                          * Add each leading directory of the changed file, i.e. for
234                          * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
235                          * the Bloom filter could be used to speed up commands like
236                          * 'git log dir/subdir', too.
237                          *
238                          * Note that directories are added without the trailing '/'.
239                          */
240                         do {
241                                 char *last_slash = strrchr(path, '/');
242
243                                 FLEX_ALLOC_STR(e, path, path);
244                                 hashmap_entry_init(&e->entry, strhash(path));
245
246                                 if (!hashmap_get(&pathmap, &e->entry, NULL))
247                                         hashmap_add(&pathmap, &e->entry);
248                                 else
249                                         free(e);
250
251                                 if (!last_slash)
252                                         last_slash = (char*)path;
253                                 *last_slash = '\0';
254
255                         } while (*path);
256
257                         diff_free_filepair(diff_queued_diff.queue[i]);
258                 }
259
260                 filter->len = (hashmap_get_size(&pathmap) * settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
261                 filter->data = xcalloc(filter->len, sizeof(unsigned char));
262
263                 hashmap_for_each_entry(&pathmap, &iter, e, entry) {
264                         struct bloom_key key;
265                         fill_bloom_key(e->path, strlen(e->path), &key, &settings);
266                         add_key_to_filter(&key, filter, &settings);
267                 }
268
269                 hashmap_free_entries(&pathmap, struct pathmap_hash_entry, entry);
270         } else {
271                 for (i = 0; i < diff_queued_diff.nr; i++)
272                         diff_free_filepair(diff_queued_diff.queue[i]);
273                 filter->data = NULL;
274                 filter->len = 0;
275         }
276
277         free(diff_queued_diff.queue);
278         DIFF_QUEUE_CLEAR(&diff_queued_diff);
279
280         return filter;
281 }
282
283 int bloom_filter_contains(const struct bloom_filter *filter,
284                           const struct bloom_key *key,
285                           const struct bloom_filter_settings *settings)
286 {
287         int i;
288         uint64_t mod = filter->len * BITS_PER_WORD;
289
290         if (!mod)
291                 return -1;
292
293         for (i = 0; i < settings->num_hashes; i++) {
294                 uint64_t hash_mod = key->hashes[i] % mod;
295                 uint64_t block_pos = hash_mod / BITS_PER_WORD;
296                 if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
297                         return 0;
298         }
299
300         return 1;
301 }