1 #include "git-compat-util.h"
6 #include "commit-graph.h"
8 #include "commit-slab.h"
10 #include "tree-walk.h"
12 #include "repository.h"
14 define_commit_slab(bloom_filter_slab
, struct bloom_filter
);
16 static struct bloom_filter_slab bloom_filters
;
18 struct pathmap_hash_entry
{
19 struct hashmap_entry entry
;
20 const char path
[FLEX_ARRAY
];
23 static uint32_t rotate_left(uint32_t value
, int32_t count
)
25 uint32_t mask
= 8 * sizeof(uint32_t) - 1;
27 return ((value
<< count
) | (value
>> ((-count
) & mask
)));
30 static inline unsigned char get_bitmask(uint32_t pos
)
32 return ((unsigned char)1) << (pos
& (BITS_PER_WORD
- 1));
35 static int check_bloom_offset(struct commit_graph
*g
, uint32_t pos
,
39 * Note that we allow offsets equal to the data size, which would set
40 * our pointers at one past the end of the chunk memory. This is
41 * necessary because the on-disk index points to the end of the
42 * entries (so we can compute size by comparing adjacent ones). And
43 * naturally the final entry's end is one-past-the-end of the chunk.
45 if (offset
<= g
->chunk_bloom_data_size
- BLOOMDATA_CHUNK_HEADER_SIZE
)
48 warning("ignoring out-of-range offset (%"PRIuMAX
") for changed-path"
49 " filter at pos %"PRIuMAX
" of %s (chunk size: %"PRIuMAX
")",
50 (uintmax_t)offset
, (uintmax_t)pos
,
51 g
->filename
, (uintmax_t)g
->chunk_bloom_data_size
);
55 int load_bloom_filter_from_graph(struct commit_graph
*g
,
56 struct bloom_filter
*filter
,
59 uint32_t lex_pos
, start_index
, end_index
;
61 while (graph_pos
< g
->num_commits_in_base
)
64 /* The commit graph commit 'c' lives in doesn't carry Bloom filters. */
65 if (!g
->chunk_bloom_indexes
)
68 lex_pos
= graph_pos
- g
->num_commits_in_base
;
70 end_index
= get_be32(g
->chunk_bloom_indexes
+ 4 * lex_pos
);
73 start_index
= get_be32(g
->chunk_bloom_indexes
+ 4 * (lex_pos
- 1));
77 if (check_bloom_offset(g
, lex_pos
, end_index
) < 0 ||
78 check_bloom_offset(g
, lex_pos
- 1, start_index
) < 0)
81 if (end_index
< start_index
) {
82 warning("ignoring decreasing changed-path index offsets"
83 " (%"PRIuMAX
" > %"PRIuMAX
") for positions"
84 " %"PRIuMAX
" and %"PRIuMAX
" of %s",
85 (uintmax_t)start_index
, (uintmax_t)end_index
,
86 (uintmax_t)(lex_pos
-1), (uintmax_t)lex_pos
,
91 filter
->len
= end_index
- start_index
;
92 filter
->data
= (unsigned char *)(g
->chunk_bloom_data
+
93 sizeof(unsigned char) * start_index
+
94 BLOOMDATA_CHUNK_HEADER_SIZE
);
95 filter
->version
= g
->bloom_filter_settings
->hash_version
;
96 filter
->to_free
= NULL
;
102 * Calculate the murmur3 32-bit hash value for the given data
103 * using the given seed.
104 * Produces a uniformly distributed hash value.
105 * Not considered to be cryptographically secure.
106 * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
108 uint32_t murmur3_seeded_v2(uint32_t seed
, const char *data
, size_t len
)
110 const uint32_t c1
= 0xcc9e2d51;
111 const uint32_t c2
= 0x1b873593;
112 const uint32_t r1
= 15;
113 const uint32_t r2
= 13;
114 const uint32_t m
= 5;
115 const uint32_t n
= 0xe6546b64;
120 int len4
= len
/ sizeof(uint32_t);
123 for (i
= 0; i
< len4
; i
++) {
124 uint32_t byte1
= (uint32_t)(unsigned char)data
[4*i
];
125 uint32_t byte2
= ((uint32_t)(unsigned char)data
[4*i
+ 1]) << 8;
126 uint32_t byte3
= ((uint32_t)(unsigned char)data
[4*i
+ 2]) << 16;
127 uint32_t byte4
= ((uint32_t)(unsigned char)data
[4*i
+ 3]) << 24;
128 k
= byte1
| byte2
| byte3
| byte4
;
130 k
= rotate_left(k
, r1
);
134 seed
= rotate_left(seed
, r2
) * m
+ n
;
137 tail
= (data
+ len4
* sizeof(uint32_t));
139 switch (len
& (sizeof(uint32_t) - 1)) {
141 k1
^= ((uint32_t)(unsigned char)tail
[2]) << 16;
144 k1
^= ((uint32_t)(unsigned char)tail
[1]) << 8;
147 k1
^= ((uint32_t)(unsigned char)tail
[0]) << 0;
149 k1
= rotate_left(k1
, r1
);
155 seed
^= (uint32_t)len
;
156 seed
^= (seed
>> 16);
158 seed
^= (seed
>> 13);
160 seed
^= (seed
>> 16);
165 static uint32_t murmur3_seeded_v1(uint32_t seed
, const char *data
, size_t len
)
167 const uint32_t c1
= 0xcc9e2d51;
168 const uint32_t c2
= 0x1b873593;
169 const uint32_t r1
= 15;
170 const uint32_t r2
= 13;
171 const uint32_t m
= 5;
172 const uint32_t n
= 0xe6546b64;
177 int len4
= len
/ sizeof(uint32_t);
180 for (i
= 0; i
< len4
; i
++) {
181 uint32_t byte1
= (uint32_t)data
[4*i
];
182 uint32_t byte2
= ((uint32_t)data
[4*i
+ 1]) << 8;
183 uint32_t byte3
= ((uint32_t)data
[4*i
+ 2]) << 16;
184 uint32_t byte4
= ((uint32_t)data
[4*i
+ 3]) << 24;
185 k
= byte1
| byte2
| byte3
| byte4
;
187 k
= rotate_left(k
, r1
);
191 seed
= rotate_left(seed
, r2
) * m
+ n
;
194 tail
= (data
+ len4
* sizeof(uint32_t));
196 switch (len
& (sizeof(uint32_t) - 1)) {
198 k1
^= ((uint32_t)tail
[2]) << 16;
201 k1
^= ((uint32_t)tail
[1]) << 8;
204 k1
^= ((uint32_t)tail
[0]) << 0;
206 k1
= rotate_left(k1
, r1
);
212 seed
^= (uint32_t)len
;
213 seed
^= (seed
>> 16);
215 seed
^= (seed
>> 13);
217 seed
^= (seed
>> 16);
222 void fill_bloom_key(const char *data
,
224 struct bloom_key
*key
,
225 const struct bloom_filter_settings
*settings
)
228 const uint32_t seed0
= 0x293ae76f;
229 const uint32_t seed1
= 0x7e646e2c;
230 uint32_t hash0
, hash1
;
231 if (settings
->hash_version
== 2) {
232 hash0
= murmur3_seeded_v2(seed0
, data
, len
);
233 hash1
= murmur3_seeded_v2(seed1
, data
, len
);
235 hash0
= murmur3_seeded_v1(seed0
, data
, len
);
236 hash1
= murmur3_seeded_v1(seed1
, data
, len
);
239 key
->hashes
= (uint32_t *)xcalloc(settings
->num_hashes
, sizeof(uint32_t));
240 for (i
= 0; i
< settings
->num_hashes
; i
++)
241 key
->hashes
[i
] = hash0
+ i
* hash1
;
244 void clear_bloom_key(struct bloom_key
*key
)
246 FREE_AND_NULL(key
->hashes
);
249 void add_key_to_filter(const struct bloom_key
*key
,
250 struct bloom_filter
*filter
,
251 const struct bloom_filter_settings
*settings
)
254 uint64_t mod
= filter
->len
* BITS_PER_WORD
;
256 for (i
= 0; i
< settings
->num_hashes
; i
++) {
257 uint64_t hash_mod
= key
->hashes
[i
] % mod
;
258 uint64_t block_pos
= hash_mod
/ BITS_PER_WORD
;
260 filter
->data
[block_pos
] |= get_bitmask(hash_mod
);
264 void init_bloom_filters(void)
266 init_bloom_filter_slab(&bloom_filters
);
269 static void free_one_bloom_filter(struct bloom_filter
*filter
)
273 free(filter
->to_free
);
276 void deinit_bloom_filters(void)
278 deep_clear_bloom_filter_slab(&bloom_filters
, free_one_bloom_filter
);
281 static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED
,
282 const struct hashmap_entry
*eptr
,
283 const struct hashmap_entry
*entry_or_key
,
284 const void *keydata UNUSED
)
286 const struct pathmap_hash_entry
*e1
, *e2
;
288 e1
= container_of(eptr
, const struct pathmap_hash_entry
, entry
);
289 e2
= container_of(entry_or_key
, const struct pathmap_hash_entry
, entry
);
291 return strcmp(e1
->path
, e2
->path
);
294 static void init_truncated_large_filter(struct bloom_filter
*filter
,
297 filter
->data
= filter
->to_free
= xmalloc(1);
298 filter
->data
[0] = 0xFF;
300 filter
->version
= version
;
303 #define VISITED (1u<<21)
304 #define HIGH_BITS (1u<<22)
306 static int has_entries_with_high_bit(struct repository
*r
, struct tree
*t
)
311 if (!(t
->object
.flags
& VISITED
)) {
312 struct tree_desc desc
;
313 struct name_entry entry
;
315 init_tree_desc(&desc
, &t
->object
.oid
, t
->buffer
, t
->size
);
316 while (tree_entry(&desc
, &entry
)) {
318 for (i
= 0; i
< entry
.pathlen
; i
++) {
319 if (entry
.path
[i
] & 0x80) {
320 t
->object
.flags
|= HIGH_BITS
;
325 if (S_ISDIR(entry
.mode
)) {
326 struct tree
*sub
= lookup_tree(r
, &entry
.oid
);
327 if (sub
&& has_entries_with_high_bit(r
, sub
)) {
328 t
->object
.flags
|= HIGH_BITS
;
336 t
->object
.flags
|= VISITED
;
339 return !!(t
->object
.flags
& HIGH_BITS
);
342 static int commit_tree_has_high_bit_paths(struct repository
*r
,
346 if (repo_parse_commit(r
, c
))
348 t
= repo_get_commit_tree(r
, c
);
351 return has_entries_with_high_bit(r
, t
);
354 static struct bloom_filter
*upgrade_filter(struct repository
*r
, struct commit
*c
,
355 struct bloom_filter
*filter
,
358 struct commit_list
*p
= c
->parents
;
359 if (commit_tree_has_high_bit_paths(r
, c
))
362 if (p
&& commit_tree_has_high_bit_paths(r
, p
->item
))
365 filter
->version
= hash_version
;
370 struct bloom_filter
*get_bloom_filter(struct repository
*r
, struct commit
*c
)
372 struct bloom_filter
*filter
;
375 filter
= get_or_compute_bloom_filter(r
, c
, 0, NULL
, NULL
);
379 prepare_repo_settings(r
);
380 hash_version
= r
->settings
.commit_graph_changed_paths_version
;
382 if (!(hash_version
== -1 || hash_version
== filter
->version
))
383 return NULL
; /* unusable filter */
387 struct bloom_filter
*get_or_compute_bloom_filter(struct repository
*r
,
389 int compute_if_not_present
,
390 const struct bloom_filter_settings
*settings
,
391 enum bloom_filter_computed
*computed
)
393 struct bloom_filter
*filter
;
395 struct diff_options diffopt
;
398 *computed
= BLOOM_NOT_COMPUTED
;
400 if (!bloom_filters
.slab_size
)
403 filter
= bloom_filter_slab_at(&bloom_filters
, c
);
407 if (repo_find_commit_pos_in_graph(r
, c
, &graph_pos
))
408 load_bloom_filter_from_graph(r
->objects
->commit_graph
,
412 if (filter
->data
&& filter
->len
) {
413 struct bloom_filter
*upgrade
;
414 if (!settings
|| settings
->hash_version
== filter
->version
)
417 /* version mismatch, see if we can upgrade */
418 if (compute_if_not_present
&&
419 git_env_bool("GIT_TEST_UPGRADE_BLOOM_FILTERS", 1)) {
420 upgrade
= upgrade_filter(r
, c
, filter
,
421 settings
->hash_version
);
424 *computed
|= BLOOM_UPGRADED
;
429 if (!compute_if_not_present
)
432 repo_diff_setup(r
, &diffopt
);
433 diffopt
.flags
.recursive
= 1;
434 diffopt
.detect_rename
= 0;
435 diffopt
.max_changes
= settings
->max_changed_paths
;
436 diff_setup_done(&diffopt
);
438 /* ensure commit is parsed so we have parent information */
439 repo_parse_commit(r
, c
);
442 diff_tree_oid(&c
->parents
->item
->object
.oid
, &c
->object
.oid
, "", &diffopt
);
444 diff_tree_oid(NULL
, &c
->object
.oid
, "", &diffopt
);
445 diffcore_std(&diffopt
);
447 if (diff_queued_diff
.nr
<= settings
->max_changed_paths
) {
448 struct hashmap pathmap
= HASHMAP_INIT(pathmap_cmp
, NULL
);
449 struct pathmap_hash_entry
*e
;
450 struct hashmap_iter iter
;
452 for (i
= 0; i
< diff_queued_diff
.nr
; i
++) {
453 const char *path
= diff_queued_diff
.queue
[i
]->two
->path
;
456 * Add each leading directory of the changed file, i.e. for
457 * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
458 * the Bloom filter could be used to speed up commands like
459 * 'git log dir/subdir', too.
461 * Note that directories are added without the trailing '/'.
464 char *last_slash
= strrchr(path
, '/');
466 FLEX_ALLOC_STR(e
, path
, path
);
467 hashmap_entry_init(&e
->entry
, strhash(path
));
469 if (!hashmap_get(&pathmap
, &e
->entry
, NULL
))
470 hashmap_add(&pathmap
, &e
->entry
);
475 last_slash
= (char*)path
;
480 diff_free_filepair(diff_queued_diff
.queue
[i
]);
483 if (hashmap_get_size(&pathmap
) > settings
->max_changed_paths
) {
484 init_truncated_large_filter(filter
,
485 settings
->hash_version
);
487 *computed
|= BLOOM_TRUNC_LARGE
;
491 filter
->len
= (hashmap_get_size(&pathmap
) * settings
->bits_per_entry
+ BITS_PER_WORD
- 1) / BITS_PER_WORD
;
492 filter
->version
= settings
->hash_version
;
495 *computed
|= BLOOM_TRUNC_EMPTY
;
498 CALLOC_ARRAY(filter
->data
, filter
->len
);
499 filter
->to_free
= filter
->data
;
501 hashmap_for_each_entry(&pathmap
, &iter
, e
, entry
) {
502 struct bloom_key key
;
503 fill_bloom_key(e
->path
, strlen(e
->path
), &key
, settings
);
504 add_key_to_filter(&key
, filter
, settings
);
505 clear_bloom_key(&key
);
509 hashmap_clear_and_free(&pathmap
, struct pathmap_hash_entry
, entry
);
511 for (i
= 0; i
< diff_queued_diff
.nr
; i
++)
512 diff_free_filepair(diff_queued_diff
.queue
[i
]);
513 init_truncated_large_filter(filter
, settings
->hash_version
);
516 *computed
|= BLOOM_TRUNC_LARGE
;
520 *computed
|= BLOOM_COMPUTED
;
522 free(diff_queued_diff
.queue
);
523 DIFF_QUEUE_CLEAR(&diff_queued_diff
);
528 int bloom_filter_contains(const struct bloom_filter
*filter
,
529 const struct bloom_key
*key
,
530 const struct bloom_filter_settings
*settings
)
533 uint64_t mod
= filter
->len
* BITS_PER_WORD
;
538 for (i
= 0; i
< settings
->num_hashes
; i
++) {
539 uint64_t hash_mod
= key
->hashes
[i
] % mod
;
540 uint64_t block_pos
= hash_mod
/ BITS_PER_WORD
;
541 if (!(filter
->data
[block_pos
] & get_bitmask(hash_mod
)))