1 #include "git-compat-util.h"
7 #include "commit-graph.h"
10 define_commit_slab(bloom_filter_slab
, struct bloom_filter
);
12 static 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;
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
,
35 uint32_t lex_pos
, start_index
, end_index
;
37 while (graph_pos
< g
->num_commits_in_base
)
40 /* The commit graph commit 'c' lives in doesn't carry Bloom filters. */
41 if (!g
->chunk_bloom_indexes
)
44 lex_pos
= graph_pos
- g
->num_commits_in_base
;
46 end_index
= get_be32(g
->chunk_bloom_indexes
+ 4 * lex_pos
);
49 start_index
= get_be32(g
->chunk_bloom_indexes
+ 4 * (lex_pos
- 1));
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
);
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;
75 const uint32_t n
= 0xe6546b64;
80 int len4
= len
/ sizeof(uint32_t);
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
;
90 k
= rotate_left(k
, r1
);
94 seed
= rotate_left(seed
, r2
) * m
+ n
;
97 tail
= (data
+ len4
* sizeof(uint32_t));
99 switch (len
& (sizeof(uint32_t) - 1)) {
101 k1
^= ((uint32_t)tail
[2]) << 16;
104 k1
^= ((uint32_t)tail
[1]) << 8;
107 k1
^= ((uint32_t)tail
[0]) << 0;
109 k1
= rotate_left(k1
, r1
);
115 seed
^= (uint32_t)len
;
116 seed
^= (seed
>> 16);
118 seed
^= (seed
>> 13);
120 seed
^= (seed
>> 16);
125 void fill_bloom_key(const char *data
,
127 struct bloom_key
*key
,
128 const struct bloom_filter_settings
*settings
)
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 clear_bloom_key(struct bloom_key
*key
)
143 FREE_AND_NULL(key
->hashes
);
146 void add_key_to_filter(const struct bloom_key
*key
,
147 struct bloom_filter
*filter
,
148 const struct bloom_filter_settings
*settings
)
151 uint64_t mod
= filter
->len
* BITS_PER_WORD
;
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
;
157 filter
->data
[block_pos
] |= get_bitmask(hash_mod
);
161 void init_bloom_filters(void)
163 init_bloom_filter_slab(&bloom_filters
);
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
,
171 const struct pathmap_hash_entry
*e1
, *e2
;
173 e1
= container_of(eptr
, const struct pathmap_hash_entry
, entry
);
174 e2
= container_of(entry_or_key
, const struct pathmap_hash_entry
, entry
);
176 return strcmp(e1
->path
, e2
->path
);
179 static void init_truncated_large_filter(struct bloom_filter
*filter
)
181 filter
->data
= xmalloc(1);
182 filter
->data
[0] = 0xFF;
186 struct bloom_filter
*get_or_compute_bloom_filter(struct repository
*r
,
188 int compute_if_not_present
,
189 const struct bloom_filter_settings
*settings
,
190 enum bloom_filter_computed
*computed
)
192 struct bloom_filter
*filter
;
194 struct diff_options diffopt
;
197 *computed
= BLOOM_NOT_COMPUTED
;
199 if (!bloom_filters
.slab_size
)
202 filter
= bloom_filter_slab_at(&bloom_filters
, c
);
206 if (repo_find_commit_pos_in_graph(r
, c
, &graph_pos
))
207 load_bloom_filter_from_graph(r
->objects
->commit_graph
,
211 if (filter
->data
&& filter
->len
)
213 if (!compute_if_not_present
)
216 repo_diff_setup(r
, &diffopt
);
217 diffopt
.flags
.recursive
= 1;
218 diffopt
.detect_rename
= 0;
219 diffopt
.max_changes
= settings
->max_changed_paths
;
220 diff_setup_done(&diffopt
);
222 /* ensure commit is parsed so we have parent information */
223 repo_parse_commit(r
, c
);
226 diff_tree_oid(&c
->parents
->item
->object
.oid
, &c
->object
.oid
, "", &diffopt
);
228 diff_tree_oid(NULL
, &c
->object
.oid
, "", &diffopt
);
229 diffcore_std(&diffopt
);
231 if (diff_queued_diff
.nr
<= settings
->max_changed_paths
) {
232 struct hashmap pathmap
= HASHMAP_INIT(pathmap_cmp
, NULL
);
233 struct pathmap_hash_entry
*e
;
234 struct hashmap_iter iter
;
236 for (i
= 0; i
< diff_queued_diff
.nr
; i
++) {
237 const char *path
= diff_queued_diff
.queue
[i
]->two
->path
;
240 * Add each leading directory of the changed file, i.e. for
241 * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
242 * the Bloom filter could be used to speed up commands like
243 * 'git log dir/subdir', too.
245 * Note that directories are added without the trailing '/'.
248 char *last_slash
= strrchr(path
, '/');
250 FLEX_ALLOC_STR(e
, path
, path
);
251 hashmap_entry_init(&e
->entry
, strhash(path
));
253 if (!hashmap_get(&pathmap
, &e
->entry
, NULL
))
254 hashmap_add(&pathmap
, &e
->entry
);
259 last_slash
= (char*)path
;
264 diff_free_filepair(diff_queued_diff
.queue
[i
]);
267 if (hashmap_get_size(&pathmap
) > settings
->max_changed_paths
) {
268 init_truncated_large_filter(filter
);
270 *computed
|= BLOOM_TRUNC_LARGE
;
274 filter
->len
= (hashmap_get_size(&pathmap
) * settings
->bits_per_entry
+ BITS_PER_WORD
- 1) / BITS_PER_WORD
;
277 *computed
|= BLOOM_TRUNC_EMPTY
;
280 CALLOC_ARRAY(filter
->data
, filter
->len
);
282 hashmap_for_each_entry(&pathmap
, &iter
, e
, entry
) {
283 struct bloom_key key
;
284 fill_bloom_key(e
->path
, strlen(e
->path
), &key
, settings
);
285 add_key_to_filter(&key
, filter
, settings
);
286 clear_bloom_key(&key
);
290 hashmap_clear_and_free(&pathmap
, struct pathmap_hash_entry
, entry
);
292 for (i
= 0; i
< diff_queued_diff
.nr
; i
++)
293 diff_free_filepair(diff_queued_diff
.queue
[i
]);
294 init_truncated_large_filter(filter
);
297 *computed
|= BLOOM_TRUNC_LARGE
;
301 *computed
|= BLOOM_COMPUTED
;
303 free(diff_queued_diff
.queue
);
304 DIFF_QUEUE_CLEAR(&diff_queued_diff
);
309 int bloom_filter_contains(const struct bloom_filter
*filter
,
310 const struct bloom_key
*key
,
311 const struct bloom_filter_settings
*settings
)
314 uint64_t mod
= filter
->len
* BITS_PER_WORD
;
319 for (i
= 0; i
< settings
->num_hashes
; i
++) {
320 uint64_t hash_mod
= key
->hashes
[i
] % mod
;
321 uint64_t block_pos
= hash_mod
/ BITS_PER_WORD
;
322 if (!(filter
->data
[block_pos
] & get_bitmask(hash_mod
)))