1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
|
#ifndef BLOOM_H
#define BLOOM_H
struct commit;
struct repository;
struct commit_graph;
struct bloom_filter_settings {
/*
* The version of the hashing technique being used.
* The newest version is 2, which is
* the seeded murmur3 hashing technique implemented
* in bloom.c. Bloom filters of version 1 were created
* with prior versions of Git, which had a bug in the
* implementation of the hash function.
*/
uint32_t hash_version;
/*
* The number of times a path is hashed, i.e. the
* number of bit positions that cumulatively
* determine whether a path is present in the
* Bloom filter.
*/
uint32_t num_hashes;
/*
* The minimum number of bits per entry in the Bloom
* filter. If the filter contains 'n' entries, then
* filter size is the minimum number of 8-bit words
* that contain n*b bits.
*/
uint32_t bits_per_entry;
/*
* The maximum number of changed paths per commit
* before declaring a Bloom filter to be too-large.
*
* Not written to the commit-graph file.
*/
uint32_t max_changed_paths;
};
#define DEFAULT_BLOOM_MAX_CHANGES 512
#define DEFAULT_BLOOM_FILTER_SETTINGS { 1, 7, 10, DEFAULT_BLOOM_MAX_CHANGES }
#define BITS_PER_WORD 8
#define BLOOMDATA_CHUNK_HEADER_SIZE 3 * sizeof(uint32_t)
/*
* A bloom_filter struct represents a data segment to
* use when testing hash values. The 'len' member
* dictates how many entries are stored in
* 'data'.
*/
struct bloom_filter {
unsigned char *data;
size_t len;
int version;
void *to_free;
};
/*
* A bloom_key represents the k hash values for a
* given string. These can be precomputed and
* stored in a bloom_key for re-use when testing
* against a bloom_filter. The number of hashes is
* given by the Bloom filter settings and is the same
* for all Bloom filters and keys interacting with
* the loaded version of the commit graph file and
* the Bloom data chunks.
*/
struct bloom_key {
uint32_t *hashes;
};
/*
* A bloom_keyvec is a vector of bloom_keys, which
* can be used to store multiple keys for a single
* pathspec item.
*/
struct bloom_keyvec {
size_t count;
struct bloom_key key[FLEX_ARRAY];
};
int load_bloom_filter_from_graph(struct commit_graph *g,
struct bloom_filter *filter,
uint32_t graph_pos);
void bloom_key_fill(struct bloom_key *key, const char *data, size_t len,
const struct bloom_filter_settings *settings);
void bloom_key_clear(struct bloom_key *key);
/*
* bloom_keyvec_new - Allocate and populate a bloom_keyvec with keys for the
* given path.
*
* This function splits the input path by '/' and generates a bloom key for each
* prefix, in reverse order of specificity. For example, given the input
* "a/b/c", it will generate bloom keys for:
* - "a/b/c"
* - "a/b"
* - "a"
*
* The resulting keys are stored in a newly allocated bloom_keyvec.
*/
struct bloom_keyvec *bloom_keyvec_new(const char *path, size_t len,
const struct bloom_filter_settings *settings);
void bloom_keyvec_free(struct bloom_keyvec *vec);
void add_key_to_filter(const struct bloom_key *key,
struct bloom_filter *filter,
const struct bloom_filter_settings *settings);
void init_bloom_filters(void);
void deinit_bloom_filters(void);
enum bloom_filter_computed {
BLOOM_NOT_COMPUTED = (1 << 0),
BLOOM_COMPUTED = (1 << 1),
BLOOM_TRUNC_LARGE = (1 << 2),
BLOOM_TRUNC_EMPTY = (1 << 3),
BLOOM_UPGRADED = (1 << 4),
};
struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
struct commit *c,
int compute_if_not_present,
const struct bloom_filter_settings *settings,
enum bloom_filter_computed *computed);
/*
* Find the Bloom filter associated with the given commit "c".
*
* If any of the following are true
*
* - the repository does not have a commit-graph, or
* - the repository disables reading from the commit-graph, or
* - the given commit does not have a Bloom filter computed, or
* - there is a Bloom filter for commit "c", but it cannot be read
* because the filter uses an incompatible version of murmur3
*
* , then `get_bloom_filter()` will return NULL. Otherwise, the corresponding
* Bloom filter will be returned.
*
* For callers who wish to inspect Bloom filters with incompatible hash
* versions, use get_or_compute_bloom_filter().
*/
struct bloom_filter *get_bloom_filter(struct repository *r, struct commit *c);
int bloom_filter_contains(const struct bloom_filter *filter,
const struct bloom_key *key,
const struct bloom_filter_settings *settings);
/*
* bloom_filter_contains_vec - Check if all keys in a key vector are in the
* Bloom filter.
*
* Returns 1 if **all** keys in the vector are present in the filter,
* 0 if **any** key is not present.
*/
int bloom_filter_contains_vec(const struct bloom_filter *filter,
const struct bloom_keyvec *v,
const struct bloom_filter_settings *settings);
uint32_t test_bloom_murmur3_seeded(uint32_t seed, const char *data, size_t len,
int version);
#endif
|
