]>
Commit | Line | Data |
---|---|---|
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 | uint32_t graph_pos = commit_graph_position(c); | |
37 | ||
38 | while (graph_pos < g->num_commits_in_base) | |
39 | g = g->base_graph; | |
40 | ||
41 | /* The commit graph commit 'c' lives in doesn't carry bloom filters. */ | |
42 | if (!g->chunk_bloom_indexes) | |
43 | return 0; | |
44 | ||
45 | lex_pos = graph_pos - g->num_commits_in_base; | |
46 | ||
47 | end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos); | |
48 | ||
49 | if (lex_pos > 0) | |
50 | start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1)); | |
51 | else | |
52 | start_index = 0; | |
53 | ||
54 | filter->len = end_index - start_index; | |
55 | filter->data = (unsigned char *)(g->chunk_bloom_data + | |
56 | sizeof(unsigned char) * start_index + | |
57 | BLOOMDATA_CHUNK_HEADER_SIZE); | |
58 | ||
59 | return 1; | |
60 | } | |
61 | ||
62 | /* | |
63 | * Calculate the murmur3 32-bit hash value for the given data | |
64 | * using the given seed. | |
65 | * Produces a uniformly distributed hash value. | |
66 | * Not considered to be cryptographically secure. | |
67 | * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm | |
68 | */ | |
69 | uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len) | |
70 | { | |
71 | const uint32_t c1 = 0xcc9e2d51; | |
72 | const uint32_t c2 = 0x1b873593; | |
73 | const uint32_t r1 = 15; | |
74 | const uint32_t r2 = 13; | |
75 | const uint32_t m = 5; | |
76 | const uint32_t n = 0xe6546b64; | |
77 | int i; | |
78 | uint32_t k1 = 0; | |
79 | const char *tail; | |
80 | ||
81 | int len4 = len / sizeof(uint32_t); | |
82 | ||
83 | uint32_t k; | |
84 | for (i = 0; i < len4; i++) { | |
85 | uint32_t byte1 = (uint32_t)data[4*i]; | |
86 | uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8; | |
87 | uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16; | |
88 | uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24; | |
89 | k = byte1 | byte2 | byte3 | byte4; | |
90 | k *= c1; | |
91 | k = rotate_left(k, r1); | |
92 | k *= c2; | |
93 | ||
94 | seed ^= k; | |
95 | seed = rotate_left(seed, r2) * m + n; | |
96 | } | |
97 | ||
98 | tail = (data + len4 * sizeof(uint32_t)); | |
99 | ||
100 | switch (len & (sizeof(uint32_t) - 1)) { | |
101 | case 3: | |
102 | k1 ^= ((uint32_t)tail[2]) << 16; | |
103 | /*-fallthrough*/ | |
104 | case 2: | |
105 | k1 ^= ((uint32_t)tail[1]) << 8; | |
106 | /*-fallthrough*/ | |
107 | case 1: | |
108 | k1 ^= ((uint32_t)tail[0]) << 0; | |
109 | k1 *= c1; | |
110 | k1 = rotate_left(k1, r1); | |
111 | k1 *= c2; | |
112 | seed ^= k1; | |
113 | break; | |
114 | } | |
115 | ||
116 | seed ^= (uint32_t)len; | |
117 | seed ^= (seed >> 16); | |
118 | seed *= 0x85ebca6b; | |
119 | seed ^= (seed >> 13); | |
120 | seed *= 0xc2b2ae35; | |
121 | seed ^= (seed >> 16); | |
122 | ||
123 | return seed; | |
124 | } | |
125 | ||
126 | void fill_bloom_key(const char *data, | |
127 | size_t len, | |
128 | struct bloom_key *key, | |
129 | const struct bloom_filter_settings *settings) | |
130 | { | |
131 | int i; | |
132 | const uint32_t seed0 = 0x293ae76f; | |
133 | const uint32_t seed1 = 0x7e646e2c; | |
134 | const uint32_t hash0 = murmur3_seeded(seed0, data, len); | |
135 | const uint32_t hash1 = murmur3_seeded(seed1, data, len); | |
136 | ||
137 | key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t)); | |
138 | for (i = 0; i < settings->num_hashes; i++) | |
139 | key->hashes[i] = hash0 + i * hash1; | |
140 | } | |
141 | ||
142 | void clear_bloom_key(struct bloom_key *key) | |
143 | { | |
144 | FREE_AND_NULL(key->hashes); | |
145 | } | |
146 | ||
147 | void add_key_to_filter(const struct bloom_key *key, | |
148 | struct bloom_filter *filter, | |
149 | const struct bloom_filter_settings *settings) | |
150 | { | |
151 | int i; | |
152 | uint64_t mod = filter->len * BITS_PER_WORD; | |
153 | ||
154 | for (i = 0; i < settings->num_hashes; i++) { | |
155 | uint64_t hash_mod = key->hashes[i] % mod; | |
156 | uint64_t block_pos = hash_mod / BITS_PER_WORD; | |
157 | ||
158 | filter->data[block_pos] |= get_bitmask(hash_mod); | |
159 | } | |
160 | } | |
161 | ||
162 | void init_bloom_filters(void) | |
163 | { | |
164 | init_bloom_filter_slab(&bloom_filters); | |
165 | } | |
166 | ||
167 | static int pathmap_cmp(const void *hashmap_cmp_fn_data, | |
168 | const struct hashmap_entry *eptr, | |
169 | const struct hashmap_entry *entry_or_key, | |
170 | const void *keydata) | |
171 | { | |
172 | const struct pathmap_hash_entry *e1, *e2; | |
173 | ||
174 | e1 = container_of(eptr, const struct pathmap_hash_entry, entry); | |
175 | e2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry); | |
176 | ||
177 | return strcmp(e1->path, e2->path); | |
178 | } | |
179 | ||
180 | struct bloom_filter *get_bloom_filter(struct repository *r, | |
181 | struct commit *c, | |
182 | int compute_if_not_present) | |
183 | { | |
184 | struct bloom_filter *filter; | |
185 | struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS; | |
186 | int i; | |
187 | struct diff_options diffopt; | |
188 | int max_changes = 512; | |
189 | ||
190 | if (!bloom_filters.slab_size) | |
191 | return NULL; | |
192 | ||
193 | filter = bloom_filter_slab_at(&bloom_filters, c); | |
194 | ||
195 | if (!filter->data) { | |
196 | load_commit_graph_info(r, c); | |
197 | if (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH && | |
198 | r->objects->commit_graph->chunk_bloom_indexes) | |
199 | load_bloom_filter_from_graph(r->objects->commit_graph, filter, c); | |
200 | } | |
201 | ||
202 | if (filter->data) | |
203 | return filter; | |
204 | if (!compute_if_not_present) | |
205 | return NULL; | |
206 | ||
207 | repo_diff_setup(r, &diffopt); | |
208 | diffopt.flags.recursive = 1; | |
209 | diffopt.detect_rename = 0; | |
210 | diffopt.max_changes = max_changes; | |
211 | diff_setup_done(&diffopt); | |
212 | ||
213 | /* ensure commit is parsed so we have parent information */ | |
214 | repo_parse_commit(r, c); | |
215 | ||
216 | if (c->parents) | |
217 | diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt); | |
218 | else | |
219 | diff_tree_oid(NULL, &c->object.oid, "", &diffopt); | |
220 | diffcore_std(&diffopt); | |
221 | ||
222 | if (diffopt.num_changes <= max_changes) { | |
223 | struct hashmap pathmap; | |
224 | struct pathmap_hash_entry *e; | |
225 | struct hashmap_iter iter; | |
226 | hashmap_init(&pathmap, pathmap_cmp, NULL, 0); | |
227 | ||
228 | for (i = 0; i < diff_queued_diff.nr; i++) { | |
229 | const char *path = diff_queued_diff.queue[i]->two->path; | |
230 | ||
231 | /* | |
232 | * Add each leading directory of the changed file, i.e. for | |
233 | * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so | |
234 | * the Bloom filter could be used to speed up commands like | |
235 | * 'git log dir/subdir', too. | |
236 | * | |
237 | * Note that directories are added without the trailing '/'. | |
238 | */ | |
239 | do { | |
240 | char *last_slash = strrchr(path, '/'); | |
241 | ||
242 | FLEX_ALLOC_STR(e, path, path); | |
243 | hashmap_entry_init(&e->entry, strhash(path)); | |
244 | ||
245 | if (!hashmap_get(&pathmap, &e->entry, NULL)) | |
246 | hashmap_add(&pathmap, &e->entry); | |
247 | else | |
248 | free(e); | |
249 | ||
250 | if (!last_slash) | |
251 | last_slash = (char*)path; | |
252 | *last_slash = '\0'; | |
253 | ||
254 | } while (*path); | |
255 | ||
256 | diff_free_filepair(diff_queued_diff.queue[i]); | |
257 | } | |
258 | ||
259 | filter->len = (hashmap_get_size(&pathmap) * settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD; | |
260 | filter->data = xcalloc(filter->len, sizeof(unsigned char)); | |
261 | ||
262 | hashmap_for_each_entry(&pathmap, &iter, e, entry) { | |
263 | struct bloom_key key; | |
264 | fill_bloom_key(e->path, strlen(e->path), &key, &settings); | |
265 | add_key_to_filter(&key, filter, &settings); | |
266 | } | |
267 | ||
268 | hashmap_free_entries(&pathmap, struct pathmap_hash_entry, entry); | |
269 | } else { | |
270 | for (i = 0; i < diff_queued_diff.nr; i++) | |
271 | diff_free_filepair(diff_queued_diff.queue[i]); | |
272 | filter->data = NULL; | |
273 | filter->len = 0; | |
274 | } | |
275 | ||
276 | free(diff_queued_diff.queue); | |
277 | DIFF_QUEUE_CLEAR(&diff_queued_diff); | |
278 | ||
279 | return filter; | |
280 | } | |
281 | ||
282 | int bloom_filter_contains(const struct bloom_filter *filter, | |
283 | const struct bloom_key *key, | |
284 | const struct bloom_filter_settings *settings) | |
285 | { | |
286 | int i; | |
287 | uint64_t mod = filter->len * BITS_PER_WORD; | |
288 | ||
289 | if (!mod) | |
290 | return -1; | |
291 | ||
292 | for (i = 0; i < settings->num_hashes; i++) { | |
293 | uint64_t hash_mod = key->hashes[i] % mod; | |
294 | uint64_t block_pos = hash_mod / BITS_PER_WORD; | |
295 | if (!(filter->data[block_pos] & get_bitmask(hash_mod))) | |
296 | return 0; | |
297 | } | |
298 | ||
299 | return 1; | |
300 | } |