bloom.c

   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 #include "commit-slab.h"
  10
  11 define_commit_slab(bloom_filter_slab, struct bloom_filter);
  12
  13 static struct bloom_filter_slab bloom_filters;
  14
  15 struct pathmap_hash_entry {
  16     struct hashmap_entry entry;
  17     const char path[FLEX_ARRAY];
  18 };
  19
  20 static uint32_t rotate_left(uint32_t value, int32_t count)
  21 {
  22         uint32_t mask = 8 * sizeof(uint32_t) - 1;
  23         count &= mask;
  24         return ((value << count) | (value >> ((-count) & mask)));
  25 }
  26
  27 static inline unsigned char get_bitmask(uint32_t pos)
  28 {
  29         return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
  30 }
  31
  32 static int load_bloom_filter_from_graph(struct commit_graph *g,
  33                                         struct bloom_filter *filter,
  34                                         uint32_t graph_pos)
  35 {
  36         uint32_t lex_pos, start_index, end_index;
  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 UNUSED,
 168                        const struct hashmap_entry *eptr,
 169                        const struct hashmap_entry *entry_or_key,
 170                        const void *keydata UNUSED)
 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 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
 187 struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
 188                                                  struct commit *c,
 189                                                  int compute_if_not_present,
 190                                                  const struct bloom_filter_settings *settings,
 191                                                  enum bloom_filter_computed *computed)
 192 {
 193         struct bloom_filter *filter;
 194         int i;
 195         struct diff_options diffopt;
 196
 197         if (computed)
 198                 *computed = BLOOM_NOT_COMPUTED;
 199
 200         if (!bloom_filters.slab_size)
 201                 return NULL;
 202
 203         filter = bloom_filter_slab_at(&bloom_filters, c);
 204
 205         if (!filter->data) {
 206                 uint32_t graph_pos;
 207                 if (repo_find_commit_pos_in_graph(r, c, &graph_pos))
 208                         load_bloom_filter_from_graph(r->objects->commit_graph,
 209                                                      filter, graph_pos);
 210         }
 211
 212         if (filter->data && filter->len)
 213                 return filter;
 214         if (!compute_if_not_present)
 215                 return NULL;
 216
 217         repo_diff_setup(r, &diffopt);
 218         diffopt.flags.recursive = 1;
 219         diffopt.detect_rename = 0;
 220         diffopt.max_changes = settings->max_changed_paths;
 221         diff_setup_done(&diffopt);
 222
 223         /* ensure commit is parsed so we have parent information */
 224         repo_parse_commit(r, c);
 225
 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
 232         if (diff_queued_diff.nr <= settings->max_changed_paths) {
 233                 struct hashmap pathmap = HASHMAP_INIT(pathmap_cmp, NULL);
 234                 struct pathmap_hash_entry *e;
 235                 struct hashmap_iter iter;
 236
 237                 for (i = 0; i < diff_queued_diff.nr; i++) {
 238                         const char *path = diff_queued_diff.queue[i]->two->path;
 239
 240                         /*
 241                          * Add each leading directory of the changed file, i.e. for
 242                          * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
 243                          * the Bloom filter could be used to speed up commands like
 244                          * 'git log dir/subdir', too.
 245                          *
 246                          * Note that directories are added without the trailing '/'.
 247                          */
 248                         do {
 249                                 char *last_slash = strrchr(path, '/');
 250
 251                                 FLEX_ALLOC_STR(e, path, path);
 252                                 hashmap_entry_init(&e->entry, strhash(path));
 253
 254                                 if (!hashmap_get(&pathmap, &e->entry, NULL))
 255                                         hashmap_add(&pathmap, &e->entry);
 256                                 else
 257                                         free(e);
 258
 259                                 if (!last_slash)
 260                                         last_slash = (char*)path;
 261                                 *last_slash = '\0';
 262
 263                         } while (*path);
 264
 265                         diff_free_filepair(diff_queued_diff.queue[i]);
 266                 }
 267
 268                 if (hashmap_get_size(&pathmap) > settings->max_changed_paths) {
 269                         init_truncated_large_filter(filter);
 270                         if (computed)
 271                                 *computed |= BLOOM_TRUNC_LARGE;
 272                         goto cleanup;
 273                 }
 274
 275                 filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
 276                 if (!filter->len) {
 277                         if (computed)
 278                                 *computed |= BLOOM_TRUNC_EMPTY;
 279                         filter->len = 1;
 280                 }
 281                 CALLOC_ARRAY(filter->data, filter->len);
 282
 283                 hashmap_for_each_entry(&pathmap, &iter, e, entry) {
 284                         struct bloom_key key;
 285                         fill_bloom_key(e->path, strlen(e->path), &key, settings);
 286                         add_key_to_filter(&key, filter, settings);
 287                         clear_bloom_key(&key);
 288                 }
 289
 290         cleanup:
 291                 hashmap_clear_and_free(&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]);
 295                 init_truncated_large_filter(filter);
 296
 297                 if (computed)
 298                         *computed |= BLOOM_TRUNC_LARGE;
 299         }
 300
 301         if (computed)
 302                 *computed |= BLOOM_COMPUTED;
 303
 304         free(diff_queued_diff.queue);
 305         DIFF_QUEUE_CLEAR(&diff_queued_diff);
 306
 307         return filter;
 308 }
 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;
 328 }