]>
Commit | Line | Data |
---|---|---|
f52207a4 GS |
1 | #include "git-compat-util.h" |
2 | #include "bloom.h" | |
ed591feb GS |
3 | #include "diff.h" |
4 | #include "diffcore.h" | |
5 | #include "revision.h" | |
6 | #include "hashmap.h" | |
1217c03e GS |
7 | #include "commit-graph.h" |
8 | #include "commit.h" | |
d4a4f929 | 9 | #include "commit-slab.h" |
ed591feb GS |
10 | |
11 | define_commit_slab(bloom_filter_slab, struct bloom_filter); | |
12 | ||
066b70ae | 13 | static struct bloom_filter_slab bloom_filters; |
ed591feb GS |
14 | |
15 | struct pathmap_hash_entry { | |
16 | struct hashmap_entry entry; | |
17 | const char path[FLEX_ARRAY]; | |
18 | }; | |
f52207a4 GS |
19 | |
20 | static uint32_t rotate_left(uint32_t value, int32_t count) | |
21 | { | |
22 | uint32_t mask = 8 * sizeof(uint32_t) - 1; | |
23 | count &= mask; | |
24 | return ((value << count) | (value >> ((-count) & mask))); | |
25 | } | |
26 | ||
f1294eaf GS |
27 | static inline unsigned char get_bitmask(uint32_t pos) |
28 | { | |
29 | return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1)); | |
30 | } | |
31 | ||
920f400e JK |
32 | static int check_bloom_offset(struct commit_graph *g, uint32_t pos, |
33 | uint32_t offset) | |
34 | { | |
35 | /* | |
36 | * Note that we allow offsets equal to the data size, which would set | |
37 | * our pointers at one past the end of the chunk memory. This is | |
38 | * necessary because the on-disk index points to the end of the | |
39 | * entries (so we can compute size by comparing adjacent ones). And | |
40 | * naturally the final entry's end is one-past-the-end of the chunk. | |
41 | */ | |
42 | if (offset <= g->chunk_bloom_data_size - BLOOMDATA_CHUNK_HEADER_SIZE) | |
43 | return 0; | |
44 | ||
45 | warning("ignoring out-of-range offset (%"PRIuMAX") for changed-path" | |
46 | " filter at pos %"PRIuMAX" of %s (chunk size: %"PRIuMAX")", | |
47 | (uintmax_t)offset, (uintmax_t)pos, | |
48 | g->filename, (uintmax_t)g->chunk_bloom_data_size); | |
49 | return -1; | |
50 | } | |
51 | ||
1217c03e | 52 | static int load_bloom_filter_from_graph(struct commit_graph *g, |
eb591e42 | 53 | struct bloom_filter *filter, |
9550f6c1 | 54 | uint32_t graph_pos) |
1217c03e GS |
55 | { |
56 | uint32_t lex_pos, start_index, end_index; | |
57 | ||
c752ad09 | 58 | while (graph_pos < g->num_commits_in_base) |
1217c03e GS |
59 | g = g->base_graph; |
60 | ||
4f364405 | 61 | /* The commit graph commit 'c' lives in doesn't carry Bloom filters. */ |
1217c03e GS |
62 | if (!g->chunk_bloom_indexes) |
63 | return 0; | |
64 | ||
c752ad09 | 65 | lex_pos = graph_pos - g->num_commits_in_base; |
1217c03e GS |
66 | |
67 | end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos); | |
68 | ||
69 | if (lex_pos > 0) | |
70 | start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1)); | |
71 | else | |
72 | start_index = 0; | |
73 | ||
920f400e JK |
74 | if (check_bloom_offset(g, lex_pos, end_index) < 0 || |
75 | check_bloom_offset(g, lex_pos - 1, start_index) < 0) | |
76 | return 0; | |
77 | ||
12192a9d JK |
78 | if (end_index < start_index) { |
79 | warning("ignoring decreasing changed-path index offsets" | |
80 | " (%"PRIuMAX" > %"PRIuMAX") for positions" | |
81 | " %"PRIuMAX" and %"PRIuMAX" of %s", | |
82 | (uintmax_t)start_index, (uintmax_t)end_index, | |
83 | (uintmax_t)(lex_pos-1), (uintmax_t)lex_pos, | |
84 | g->filename); | |
85 | return 0; | |
86 | } | |
87 | ||
1217c03e GS |
88 | filter->len = end_index - start_index; |
89 | filter->data = (unsigned char *)(g->chunk_bloom_data + | |
90 | sizeof(unsigned char) * start_index + | |
91 | BLOOMDATA_CHUNK_HEADER_SIZE); | |
92 | ||
93 | return 1; | |
94 | } | |
95 | ||
f52207a4 GS |
96 | /* |
97 | * Calculate the murmur3 32-bit hash value for the given data | |
98 | * using the given seed. | |
99 | * Produces a uniformly distributed hash value. | |
100 | * Not considered to be cryptographically secure. | |
101 | * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm | |
102 | */ | |
103 | uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len) | |
104 | { | |
105 | const uint32_t c1 = 0xcc9e2d51; | |
106 | const uint32_t c2 = 0x1b873593; | |
107 | const uint32_t r1 = 15; | |
108 | const uint32_t r2 = 13; | |
109 | const uint32_t m = 5; | |
110 | const uint32_t n = 0xe6546b64; | |
111 | int i; | |
112 | uint32_t k1 = 0; | |
113 | const char *tail; | |
114 | ||
115 | int len4 = len / sizeof(uint32_t); | |
116 | ||
117 | uint32_t k; | |
118 | for (i = 0; i < len4; i++) { | |
119 | uint32_t byte1 = (uint32_t)data[4*i]; | |
120 | uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8; | |
121 | uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16; | |
122 | uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24; | |
123 | k = byte1 | byte2 | byte3 | byte4; | |
124 | k *= c1; | |
125 | k = rotate_left(k, r1); | |
126 | k *= c2; | |
127 | ||
128 | seed ^= k; | |
129 | seed = rotate_left(seed, r2) * m + n; | |
130 | } | |
131 | ||
132 | tail = (data + len4 * sizeof(uint32_t)); | |
133 | ||
134 | switch (len & (sizeof(uint32_t) - 1)) { | |
135 | case 3: | |
136 | k1 ^= ((uint32_t)tail[2]) << 16; | |
137 | /*-fallthrough*/ | |
138 | case 2: | |
139 | k1 ^= ((uint32_t)tail[1]) << 8; | |
140 | /*-fallthrough*/ | |
141 | case 1: | |
142 | k1 ^= ((uint32_t)tail[0]) << 0; | |
143 | k1 *= c1; | |
144 | k1 = rotate_left(k1, r1); | |
145 | k1 *= c2; | |
146 | seed ^= k1; | |
147 | break; | |
148 | } | |
149 | ||
150 | seed ^= (uint32_t)len; | |
151 | seed ^= (seed >> 16); | |
152 | seed *= 0x85ebca6b; | |
153 | seed ^= (seed >> 13); | |
154 | seed *= 0xc2b2ae35; | |
155 | seed ^= (seed >> 16); | |
156 | ||
157 | return seed; | |
f1294eaf GS |
158 | } |
159 | ||
160 | void fill_bloom_key(const char *data, | |
eb591e42 DS |
161 | size_t len, |
162 | struct bloom_key *key, | |
163 | const struct bloom_filter_settings *settings) | |
f1294eaf GS |
164 | { |
165 | int i; | |
166 | const uint32_t seed0 = 0x293ae76f; | |
167 | const uint32_t seed1 = 0x7e646e2c; | |
168 | const uint32_t hash0 = murmur3_seeded(seed0, data, len); | |
169 | const uint32_t hash1 = murmur3_seeded(seed1, data, len); | |
170 | ||
171 | key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t)); | |
172 | for (i = 0; i < settings->num_hashes; i++) | |
173 | key->hashes[i] = hash0 + i * hash1; | |
174 | } | |
175 | ||
f32dde8c DS |
176 | void clear_bloom_key(struct bloom_key *key) |
177 | { | |
178 | FREE_AND_NULL(key->hashes); | |
179 | } | |
180 | ||
f1294eaf | 181 | void add_key_to_filter(const struct bloom_key *key, |
eb591e42 DS |
182 | struct bloom_filter *filter, |
183 | const struct bloom_filter_settings *settings) | |
f1294eaf GS |
184 | { |
185 | int i; | |
186 | uint64_t mod = filter->len * BITS_PER_WORD; | |
187 | ||
188 | for (i = 0; i < settings->num_hashes; i++) { | |
189 | uint64_t hash_mod = key->hashes[i] % mod; | |
190 | uint64_t block_pos = hash_mod / BITS_PER_WORD; | |
191 | ||
192 | filter->data[block_pos] |= get_bitmask(hash_mod); | |
193 | } | |
194 | } | |
ed591feb GS |
195 | |
196 | void init_bloom_filters(void) | |
197 | { | |
198 | init_bloom_filter_slab(&bloom_filters); | |
199 | } | |
200 | ||
5cf88fd8 | 201 | static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED, |
65c1a28b DS |
202 | const struct hashmap_entry *eptr, |
203 | const struct hashmap_entry *entry_or_key, | |
5cf88fd8 | 204 | const void *keydata UNUSED) |
65c1a28b DS |
205 | { |
206 | const struct pathmap_hash_entry *e1, *e2; | |
207 | ||
208 | e1 = container_of(eptr, const struct pathmap_hash_entry, entry); | |
209 | e2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry); | |
210 | ||
211 | return strcmp(e1->path, e2->path); | |
212 | } | |
213 | ||
59f0d507 TB |
214 | static void init_truncated_large_filter(struct bloom_filter *filter) |
215 | { | |
216 | filter->data = xmalloc(1); | |
217 | filter->data[0] = 0xFF; | |
218 | filter->len = 1; | |
219 | } | |
220 | ||
312cff52 TB |
221 | struct bloom_filter *get_or_compute_bloom_filter(struct repository *r, |
222 | struct commit *c, | |
223 | int compute_if_not_present, | |
9a7a9ed1 | 224 | const struct bloom_filter_settings *settings, |
312cff52 | 225 | enum bloom_filter_computed *computed) |
ed591feb GS |
226 | { |
227 | struct bloom_filter *filter; | |
ed591feb GS |
228 | int i; |
229 | struct diff_options diffopt; | |
230 | ||
312cff52 TB |
231 | if (computed) |
232 | *computed = BLOOM_NOT_COMPUTED; | |
233 | ||
94919742 | 234 | if (!bloom_filters.slab_size) |
ed591feb GS |
235 | return NULL; |
236 | ||
237 | filter = bloom_filter_slab_at(&bloom_filters, c); | |
238 | ||
1217c03e | 239 | if (!filter->data) { |
9550f6c1 TB |
240 | uint32_t graph_pos; |
241 | if (repo_find_commit_pos_in_graph(r, c, &graph_pos)) | |
242 | load_bloom_filter_from_graph(r->objects->commit_graph, | |
243 | filter, graph_pos); | |
1217c03e GS |
244 | } |
245 | ||
809e0327 | 246 | if (filter->data && filter->len) |
1217c03e | 247 | return filter; |
94919742 DS |
248 | if (!compute_if_not_present) |
249 | return NULL; | |
1217c03e | 250 | |
ed591feb GS |
251 | repo_diff_setup(r, &diffopt); |
252 | diffopt.flags.recursive = 1; | |
caf388ca | 253 | diffopt.detect_rename = 0; |
9a7a9ed1 | 254 | diffopt.max_changes = settings->max_changed_paths; |
ed591feb GS |
255 | diff_setup_done(&diffopt); |
256 | ||
891c17c9 DS |
257 | /* ensure commit is parsed so we have parent information */ |
258 | repo_parse_commit(r, c); | |
259 | ||
ed591feb GS |
260 | if (c->parents) |
261 | diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt); | |
262 | else | |
263 | diff_tree_oid(NULL, &c->object.oid, "", &diffopt); | |
264 | diffcore_std(&diffopt); | |
265 | ||
b16a8277 | 266 | if (diff_queued_diff.nr <= settings->max_changed_paths) { |
b19315d8 | 267 | struct hashmap pathmap = HASHMAP_INIT(pathmap_cmp, NULL); |
ed591feb GS |
268 | struct pathmap_hash_entry *e; |
269 | struct hashmap_iter iter; | |
ed591feb GS |
270 | |
271 | for (i = 0; i < diff_queued_diff.nr; i++) { | |
272 | const char *path = diff_queued_diff.queue[i]->two->path; | |
273 | ||
274 | /* | |
65c1a28b DS |
275 | * Add each leading directory of the changed file, i.e. for |
276 | * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so | |
277 | * the Bloom filter could be used to speed up commands like | |
278 | * 'git log dir/subdir', too. | |
279 | * | |
280 | * Note that directories are added without the trailing '/'. | |
281 | */ | |
ed591feb GS |
282 | do { |
283 | char *last_slash = strrchr(path, '/'); | |
284 | ||
285 | FLEX_ALLOC_STR(e, path, path); | |
286 | hashmap_entry_init(&e->entry, strhash(path)); | |
65c1a28b DS |
287 | |
288 | if (!hashmap_get(&pathmap, &e->entry, NULL)) | |
289 | hashmap_add(&pathmap, &e->entry); | |
290 | else | |
291 | free(e); | |
ed591feb GS |
292 | |
293 | if (!last_slash) | |
294 | last_slash = (char*)path; | |
295 | *last_slash = '\0'; | |
296 | ||
297 | } while (*path); | |
298 | ||
299 | diff_free_filepair(diff_queued_diff.queue[i]); | |
300 | } | |
301 | ||
b16a8277 | 302 | if (hashmap_get_size(&pathmap) > settings->max_changed_paths) { |
59f0d507 | 303 | init_truncated_large_filter(filter); |
b16a8277 DS |
304 | if (computed) |
305 | *computed |= BLOOM_TRUNC_LARGE; | |
306 | goto cleanup; | |
307 | } | |
308 | ||
9a7a9ed1 | 309 | filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD; |
59f0d507 TB |
310 | if (!filter->len) { |
311 | if (computed) | |
312 | *computed |= BLOOM_TRUNC_EMPTY; | |
313 | filter->len = 1; | |
314 | } | |
ca56dadb | 315 | CALLOC_ARRAY(filter->data, filter->len); |
ed591feb GS |
316 | |
317 | hashmap_for_each_entry(&pathmap, &iter, e, entry) { | |
318 | struct bloom_key key; | |
9a7a9ed1 TB |
319 | fill_bloom_key(e->path, strlen(e->path), &key, settings); |
320 | add_key_to_filter(&key, filter, settings); | |
b180c681 | 321 | clear_bloom_key(&key); |
ed591feb GS |
322 | } |
323 | ||
b16a8277 | 324 | cleanup: |
6da1a258 | 325 | hashmap_clear_and_free(&pathmap, struct pathmap_hash_entry, entry); |
ed591feb GS |
326 | } else { |
327 | for (i = 0; i < diff_queued_diff.nr; i++) | |
328 | diff_free_filepair(diff_queued_diff.queue[i]); | |
59f0d507 | 329 | init_truncated_large_filter(filter); |
312cff52 TB |
330 | |
331 | if (computed) | |
332 | *computed |= BLOOM_TRUNC_LARGE; | |
ed591feb GS |
333 | } |
334 | ||
312cff52 TB |
335 | if (computed) |
336 | *computed |= BLOOM_COMPUTED; | |
337 | ||
ed591feb GS |
338 | free(diff_queued_diff.queue); |
339 | DIFF_QUEUE_CLEAR(&diff_queued_diff); | |
340 | ||
341 | return filter; | |
342 | } | |
a56b9464 GS |
343 | |
344 | int bloom_filter_contains(const struct bloom_filter *filter, | |
345 | const struct bloom_key *key, | |
346 | const struct bloom_filter_settings *settings) | |
347 | { | |
348 | int i; | |
349 | uint64_t mod = filter->len * BITS_PER_WORD; | |
350 | ||
351 | if (!mod) | |
352 | return -1; | |
353 | ||
354 | for (i = 0; i < settings->num_hashes; i++) { | |
355 | uint64_t hash_mod = key->hashes[i] % mod; | |
356 | uint64_t block_pos = hash_mod / BITS_PER_WORD; | |
357 | if (!(filter->data[block_pos] & get_bitmask(hash_mod))) | |
358 | return 0; | |
359 | } | |
360 | ||
361 | return 1; | |
066b70ae | 362 | } |