[thirdparty/git.git] / bloom.c

#include "git-compat-util.h"
#include "bloom.h"
#include "diff.h"
#include "diffcore.h"
#include "revision.h"
#include "hashmap.h"
#include "commit-graph.h"
#include "commit.h"

define_commit_slab(bloom_filter_slab, struct bloom_filter);

static struct bloom_filter_slab bloom_filters;

struct pathmap_hash_entry {
    struct hashmap_entry entry;
    const char path[FLEX_ARRAY];
};

static uint32_t rotate_left(uint32_t value, int32_t count)
{
	uint32_t mask = 8 * sizeof(uint32_t) - 1;
	count &= mask;
	return ((value << count) | (value >> ((-count) & mask)));
}

static inline unsigned char get_bitmask(uint32_t pos)
{
	return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
}

static int load_bloom_filter_from_graph(struct commit_graph *g,
					struct bloom_filter *filter,
					struct commit *c)
{
	uint32_t lex_pos, start_index, end_index;
	uint32_t graph_pos = commit_graph_position(c);

	while (graph_pos < g->num_commits_in_base)
		g = g->base_graph;

	/* The commit graph commit 'c' lives in doesn't carry Bloom filters. */
	if (!g->chunk_bloom_indexes)
		return 0;

	lex_pos = graph_pos - g->num_commits_in_base;

	end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);

	if (lex_pos > 0)
		start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1));
	else
		start_index = 0;

	filter->len = end_index - start_index;
	filter->data = (unsigned char *)(g->chunk_bloom_data +
					sizeof(unsigned char) * start_index +
					BLOOMDATA_CHUNK_HEADER_SIZE);

	return 1;
}

/*
 * Calculate the murmur3 32-bit hash value for the given data
 * using the given seed.
 * Produces a uniformly distributed hash value.
 * Not considered to be cryptographically secure.
 * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
 */
uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)
{
	const uint32_t c1 = 0xcc9e2d51;
	const uint32_t c2 = 0x1b873593;
	const uint32_t r1 = 15;
	const uint32_t r2 = 13;
	const uint32_t m = 5;
	const uint32_t n = 0xe6546b64;
	int i;
	uint32_t k1 = 0;
	const char *tail;

	int len4 = len / sizeof(uint32_t);

	uint32_t k;
	for (i = 0; i < len4; i++) {
		uint32_t byte1 = (uint32_t)data[4*i];
		uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8;
		uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16;
		uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24;
		k = byte1 | byte2 | byte3 | byte4;
		k *= c1;
		k = rotate_left(k, r1);
		k *= c2;

		seed ^= k;
		seed = rotate_left(seed, r2) * m + n;
	}

	tail = (data + len4 * sizeof(uint32_t));

	switch (len & (sizeof(uint32_t) - 1)) {
	case 3:
		k1 ^= ((uint32_t)tail[2]) << 16;
		/*-fallthrough*/
	case 2:
		k1 ^= ((uint32_t)tail[1]) << 8;
		/*-fallthrough*/
	case 1:
		k1 ^= ((uint32_t)tail[0]) << 0;
		k1 *= c1;
		k1 = rotate_left(k1, r1);
		k1 *= c2;
		seed ^= k1;
		break;
	}

	seed ^= (uint32_t)len;
	seed ^= (seed >> 16);
	seed *= 0x85ebca6b;
	seed ^= (seed >> 13);
	seed *= 0xc2b2ae35;
	seed ^= (seed >> 16);

	return seed;
}

void fill_bloom_key(const char *data,
		    size_t len,
		    struct bloom_key *key,
		    const struct bloom_filter_settings *settings)
{
	int i;
	const uint32_t seed0 = 0x293ae76f;
	const uint32_t seed1 = 0x7e646e2c;
	const uint32_t hash0 = murmur3_seeded(seed0, data, len);
	const uint32_t hash1 = murmur3_seeded(seed1, data, len);

	key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));
	for (i = 0; i < settings->num_hashes; i++)
		key->hashes[i] = hash0 + i * hash1;
}

void clear_bloom_key(struct bloom_key *key)
{
	FREE_AND_NULL(key->hashes);
}

void add_key_to_filter(const struct bloom_key *key,
		       struct bloom_filter *filter,
		       const struct bloom_filter_settings *settings)
{
	int i;
	uint64_t mod = filter->len * BITS_PER_WORD;

	for (i = 0; i < settings->num_hashes; i++) {
		uint64_t hash_mod = key->hashes[i] % mod;
		uint64_t block_pos = hash_mod / BITS_PER_WORD;

		filter->data[block_pos] |= get_bitmask(hash_mod);
	}
}

void init_bloom_filters(void)
{
	init_bloom_filter_slab(&bloom_filters);
}

static int pathmap_cmp(const void *hashmap_cmp_fn_data,
		       const struct hashmap_entry *eptr,
		       const struct hashmap_entry *entry_or_key,
		       const void *keydata)
{
	const struct pathmap_hash_entry *e1, *e2;

	e1 = container_of(eptr, const struct pathmap_hash_entry, entry);
	e2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry);

	return strcmp(e1->path, e2->path);
}

static void init_truncated_large_filter(struct bloom_filter *filter)
{
	filter->data = xmalloc(1);
	filter->data[0] = 0xFF;
	filter->len = 1;
}

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)
{
	struct bloom_filter *filter;
	int i;
	struct diff_options diffopt;

	if (computed)
		*computed = BLOOM_NOT_COMPUTED;

	if (!bloom_filters.slab_size)
		return NULL;

	filter = bloom_filter_slab_at(&bloom_filters, c);

	if (!filter->data) {
		load_commit_graph_info(r, c);
		if (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH &&
			load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))
				return filter;
	}

	if (filter->data)
		return filter;
	if (!compute_if_not_present)
		return NULL;

	repo_diff_setup(r, &diffopt);
	diffopt.flags.recursive = 1;
	diffopt.detect_rename = 0;
	diffopt.max_changes = settings->max_changed_paths;
	diff_setup_done(&diffopt);

	/* ensure commit is parsed so we have parent information */
	repo_parse_commit(r, c);

	if (c->parents)
		diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt);
	else
		diff_tree_oid(NULL, &c->object.oid, "", &diffopt);
	diffcore_std(&diffopt);

	if (diff_queued_diff.nr <= settings->max_changed_paths) {
		struct hashmap pathmap;
		struct pathmap_hash_entry *e;
		struct hashmap_iter iter;
		hashmap_init(&pathmap, pathmap_cmp, NULL, 0);

		for (i = 0; i < diff_queued_diff.nr; i++) {
			const char *path = diff_queued_diff.queue[i]->two->path;

			/*
			 * Add each leading directory of the changed file, i.e. for
			 * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
			 * the Bloom filter could be used to speed up commands like
			 * 'git log dir/subdir', too.
			 *
			 * Note that directories are added without the trailing '/'.
			 */
			do {
				char *last_slash = strrchr(path, '/');

				FLEX_ALLOC_STR(e, path, path);
				hashmap_entry_init(&e->entry, strhash(path));

				if (!hashmap_get(&pathmap, &e->entry, NULL))
					hashmap_add(&pathmap, &e->entry);
				else
					free(e);

				if (!last_slash)
					last_slash = (char*)path;
				*last_slash = '\0';

			} while (*path);

			diff_free_filepair(diff_queued_diff.queue[i]);
		}

		if (hashmap_get_size(&pathmap) > settings->max_changed_paths) {
			init_truncated_large_filter(filter);
			if (computed)
				*computed |= BLOOM_TRUNC_LARGE;
			goto cleanup;
		}

		filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
		if (!filter->len) {
			if (computed)
				*computed |= BLOOM_TRUNC_EMPTY;
			filter->len = 1;
		}
		filter->data = xcalloc(filter->len, sizeof(unsigned char));

		hashmap_for_each_entry(&pathmap, &iter, e, entry) {
			struct bloom_key key;
			fill_bloom_key(e->path, strlen(e->path), &key, settings);
			add_key_to_filter(&key, filter, settings);
		}

	cleanup:
		hashmap_free_entries(&pathmap, struct pathmap_hash_entry, entry);
	} else {
		for (i = 0; i < diff_queued_diff.nr; i++)
			diff_free_filepair(diff_queued_diff.queue[i]);
		init_truncated_large_filter(filter);

		if (computed)
			*computed |= BLOOM_TRUNC_LARGE;
	}

	if (computed)
		*computed |= BLOOM_COMPUTED;

	free(diff_queued_diff.queue);
	DIFF_QUEUE_CLEAR(&diff_queued_diff);

	return filter;
}

int bloom_filter_contains(const struct bloom_filter *filter,
			  const struct bloom_key *key,
			  const struct bloom_filter_settings *settings)
{
	int i;
	uint64_t mod = filter->len * BITS_PER_WORD;

	if (!mod)
		return -1;

	for (i = 0; i < settings->num_hashes; i++) {
		uint64_t hash_mod = key->hashes[i] % mod;
		uint64_t block_pos = hash_mod / BITS_PER_WORD;
		if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
			return 0;
	}

	return 1;
}
Commit	Line	Data
f52207a4 GS	1	#include "git-compat-util.h"
f52207a4 GS	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"
1217c03e GS	8	#include "commit.h"
ed591feb GS	9
	10	define_commit_slab(bloom_filter_slab, struct bloom_filter);
	11
066b70ae	12	static struct bloom_filter_slab bloom_filters;
ed591feb GS	13
	14	struct pathmap_hash_entry {
	15	struct hashmap_entry entry;
	16	const char path[FLEX_ARRAY];
	17	};
f52207a4 GS	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
f1294eaf GS	26	static inline unsigned char get_bitmask(uint32_t pos)
	27	{
	28	return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
	29	}
	30
1217c03e	31	static int load_bloom_filter_from_graph(struct commit_graph *g,
eb591e42 DS	32	struct bloom_filter *filter,
eb591e42 DS	33	struct commit *c)
1217c03e GS	34	{
1217c03e GS	35	uint32_t lex_pos, start_index, end_index;
c752ad09	36	uint32_t graph_pos = commit_graph_position(c);
1217c03e	37
c752ad09	38	while (graph_pos < g->num_commits_in_base)
1217c03e GS	39	g = g->base_graph;
1217c03e GS	40
4f364405	41	/* The commit graph commit 'c' lives in doesn't carry Bloom filters. */
1217c03e GS	42	if (!g->chunk_bloom_indexes)
	43	return 0;
	44
c752ad09	45	lex_pos = graph_pos - g->num_commits_in_base;
1217c03e GS	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
f52207a4 GS	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;
f1294eaf GS	124	}
	125
	126	void fill_bloom_key(const char *data,
eb591e42 DS	127	size_t len,
	128	struct bloom_key *key,
	129	const struct bloom_filter_settings *settings)
f1294eaf GS	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
f32dde8c DS	142	void clear_bloom_key(struct bloom_key *key)
	143	{
	144	FREE_AND_NULL(key->hashes);
	145	}
	146
f1294eaf	147	void add_key_to_filter(const struct bloom_key *key,
eb591e42 DS	148	struct bloom_filter *filter,
eb591e42 DS	149	const struct bloom_filter_settings *settings)
f1294eaf GS	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	}
ed591feb GS	161
	162	void init_bloom_filters(void)
	163	{
	164	init_bloom_filter_slab(&bloom_filters);
	165	}
	166
65c1a28b DS	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
59f0d507 TB	180	static void init_truncated_large_filter(struct bloom_filter *filter)
	181	{
	182	filter->data = xmalloc(1);
	183	filter->data[0] = 0xFF;
	184	filter->len = 1;
	185	}
	186
312cff52 TB	187	struct bloom_filter get_or_compute_bloom_filter(struct repository r,
	188	struct commit *c,
	189	int compute_if_not_present,
9a7a9ed1	190	const struct bloom_filter_settings *settings,
312cff52	191	enum bloom_filter_computed *computed)
ed591feb GS	192	{
ed591feb GS	193	struct bloom_filter *filter;
ed591feb GS	194	int i;
	195	struct diff_options diffopt;
	196
312cff52 TB	197	if (computed)
	198	*computed = BLOOM_NOT_COMPUTED;
	199
94919742	200	if (!bloom_filters.slab_size)
ed591feb GS	201	return NULL;
	202
	203	filter = bloom_filter_slab_at(&bloom_filters, c);
	204
1217c03e GS	205	if (!filter->data) {
1217c03e GS	206	load_commit_graph_info(r, c);
c49c82aa	207	if (commit_graph_position(c) != COMMIT_NOT_FROM_GRAPH &&
4f364405 TB	208	load_bloom_filter_from_graph(r->objects->commit_graph, filter, c))
4f364405 TB	209	return filter;
1217c03e GS	210	}
1217c03e GS	211
94919742	212	if (filter->data)
1217c03e	213	return filter;
94919742 DS	214	if (!compute_if_not_present)
94919742 DS	215	return NULL;
1217c03e	216
ed591feb GS	217	repo_diff_setup(r, &diffopt);
ed591feb GS	218	diffopt.flags.recursive = 1;
caf388ca	219	diffopt.detect_rename = 0;
9a7a9ed1	220	diffopt.max_changes = settings->max_changed_paths;
ed591feb GS	221	diff_setup_done(&diffopt);
ed591feb GS	222
891c17c9 DS	223	/* ensure commit is parsed so we have parent information */
	224	repo_parse_commit(r, c);
	225
ed591feb GS	226	if (c->parents)
	227	diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt);
	228	else
	229	diff_tree_oid(NULL, &c->object.oid, "", &diffopt);
	230	diffcore_std(&diffopt);
	231
b16a8277	232	if (diff_queued_diff.nr <= settings->max_changed_paths) {
ed591feb GS	233	struct hashmap pathmap;
	234	struct pathmap_hash_entry *e;
	235	struct hashmap_iter iter;
65c1a28b	236	hashmap_init(&pathmap, pathmap_cmp, NULL, 0);
ed591feb GS	237
	238	for (i = 0; i < diff_queued_diff.nr; i++) {
	239	const char *path = diff_queued_diff.queue[i]->two->path;
	240
	241	/*
65c1a28b DS	242	* Add each leading directory of the changed file, i.e. for
	243	* 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
	244	* the Bloom filter could be used to speed up commands like
	245	* 'git log dir/subdir', too.
	246	*
	247	* Note that directories are added without the trailing '/'.
	248	*/
ed591feb GS	249	do {
	250	char *last_slash = strrchr(path, '/');
	251
	252	FLEX_ALLOC_STR(e, path, path);
	253	hashmap_entry_init(&e->entry, strhash(path));
65c1a28b DS	254
	255	if (!hashmap_get(&pathmap, &e->entry, NULL))
	256	hashmap_add(&pathmap, &e->entry);
	257	else
	258	free(e);
ed591feb GS	259
	260	if (!last_slash)
	261	last_slash = (char*)path;
	262	*last_slash = '\0';
	263
	264	} while (*path);
	265
	266	diff_free_filepair(diff_queued_diff.queue[i]);
	267	}
	268
b16a8277	269	if (hashmap_get_size(&pathmap) > settings->max_changed_paths) {
59f0d507	270	init_truncated_large_filter(filter);
b16a8277 DS	271	if (computed)
	272	*computed \|= BLOOM_TRUNC_LARGE;
	273	goto cleanup;
	274	}
	275
9a7a9ed1	276	filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
59f0d507 TB	277	if (!filter->len) {
	278	if (computed)
	279	*computed \|= BLOOM_TRUNC_EMPTY;
	280	filter->len = 1;
	281	}
ed591feb GS	282	filter->data = xcalloc(filter->len, sizeof(unsigned char));
	283
	284	hashmap_for_each_entry(&pathmap, &iter, e, entry) {
	285	struct bloom_key key;
9a7a9ed1 TB	286	fill_bloom_key(e->path, strlen(e->path), &key, settings);
9a7a9ed1 TB	287	add_key_to_filter(&key, filter, settings);
ed591feb GS	288	}
ed591feb GS	289
b16a8277	290	cleanup:
ed591feb GS	291	hashmap_free_entries(&pathmap, struct pathmap_hash_entry, entry);
	292	} else {
	293	for (i = 0; i < diff_queued_diff.nr; i++)
	294	diff_free_filepair(diff_queued_diff.queue[i]);
59f0d507	295	init_truncated_large_filter(filter);
312cff52 TB	296
	297	if (computed)
	298	*computed \|= BLOOM_TRUNC_LARGE;
ed591feb GS	299	}
ed591feb GS	300
312cff52 TB	301	if (computed)
	302	*computed \|= BLOOM_COMPUTED;
	303
ed591feb GS	304	free(diff_queued_diff.queue);
	305	DIFF_QUEUE_CLEAR(&diff_queued_diff);
	306
	307	return filter;
	308	}
a56b9464 GS	309
	310	int bloom_filter_contains(const struct bloom_filter *filter,
	311	const struct bloom_key *key,
	312	const struct bloom_filter_settings *settings)
	313	{
	314	int i;
	315	uint64_t mod = filter->len * BITS_PER_WORD;
	316
	317	if (!mod)
	318	return -1;
	319
	320	for (i = 0; i < settings->num_hashes; i++) {
	321	uint64_t hash_mod = key->hashes[i] % mod;
	322	uint64_t block_pos = hash_mod / BITS_PER_WORD;
	323	if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
	324	return 0;
	325	}
	326
	327	return 1;
066b70ae	328	}