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 check_bloom_offset(struct commit_graph *g, uint32_t pos,
  33                               uint32_t offset)
  34 {
  35         /*
  36          * Note that we allow offsets equal to the data size, which would set
  37          * our pointers at one past the end of the chunk memory. This is
  38          * necessary because the on-disk index points to the end of the
  39          * entries (so we can compute size by comparing adjacent ones). And
  40          * naturally the final entry's end is one-past-the-end of the chunk.
  41          */
  42         if (offset <= g->chunk_bloom_data_size - BLOOMDATA_CHUNK_HEADER_SIZE)
  43                 return 0;
  44
  45         warning("ignoring out-of-range offset (%"PRIuMAX") for changed-path"
  46                 " filter at pos %"PRIuMAX" of %s (chunk size: %"PRIuMAX")",
  47                 (uintmax_t)offset, (uintmax_t)pos,
  48                 g->filename, (uintmax_t)g->chunk_bloom_data_size);
  49         return -1;
  50 }
  51
  52 static int load_bloom_filter_from_graph(struct commit_graph *g,
  53                                         struct bloom_filter *filter,
  54                                         uint32_t graph_pos)
  55 {
  56         uint32_t lex_pos, start_index, end_index;
  57
  58         while (graph_pos < g->num_commits_in_base)
  59                 g = g->base_graph;
  60
  61         /* The commit graph commit 'c' lives in doesn't carry Bloom filters. */
  62         if (!g->chunk_bloom_indexes)
  63                 return 0;
  64
  65         lex_pos = graph_pos - g->num_commits_in_base;
  66
  67         end_index = get_be32(g->chunk_bloom_indexes + 4 * lex_pos);
  68
  69         if (lex_pos > 0)
  70                 start_index = get_be32(g->chunk_bloom_indexes + 4 * (lex_pos - 1));
  71         else
  72                 start_index = 0;
  73
  74         if (check_bloom_offset(g, lex_pos, end_index) < 0 ||
  75             check_bloom_offset(g, lex_pos - 1, start_index) < 0)
  76                 return 0;
  77
  78         if (end_index < start_index) {
  79                 warning("ignoring decreasing changed-path index offsets"
  80                         " (%"PRIuMAX" > %"PRIuMAX") for positions"
  81                         " %"PRIuMAX" and %"PRIuMAX" of %s",
  82                         (uintmax_t)start_index, (uintmax_t)end_index,
  83                         (uintmax_t)(lex_pos-1), (uintmax_t)lex_pos,
  84                         g->filename);
  85                 return 0;
  86         }
  87
  88         filter->len = end_index - start_index;
  89         filter->data = (unsigned char *)(g->chunk_bloom_data +
  90                                         sizeof(unsigned char) * start_index +
  91                                         BLOOMDATA_CHUNK_HEADER_SIZE);
  92
  93         return 1;
  94 }
  95
  96 /*
  97  * Calculate the murmur3 32-bit hash value for the given data
  98  * using the given seed.
  99  * Produces a uniformly distributed hash value.
 100  * Not considered to be cryptographically secure.
 101  * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
 102  */
 103 uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)
 104 {
 105         const uint32_t c1 = 0xcc9e2d51;
 106         const uint32_t c2 = 0x1b873593;
 107         const uint32_t r1 = 15;
 108         const uint32_t r2 = 13;
 109         const uint32_t m = 5;
 110         const uint32_t n = 0xe6546b64;
 111         int i;
 112         uint32_t k1 = 0;
 113         const char *tail;
 114
 115         int len4 = len / sizeof(uint32_t);
 116
 117         uint32_t k;
 118         for (i = 0; i < len4; i++) {
 119                 uint32_t byte1 = (uint32_t)data[4*i];
 120                 uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8;
 121                 uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16;
 122                 uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24;
 123                 k = byte1 | byte2 | byte3 | byte4;
 124                 k *= c1;
 125                 k = rotate_left(k, r1);
 126                 k *= c2;
 127
 128                 seed ^= k;
 129                 seed = rotate_left(seed, r2) * m + n;
 130         }
 131
 132         tail = (data + len4 * sizeof(uint32_t));
 133
 134         switch (len & (sizeof(uint32_t) - 1)) {
 135         case 3:
 136                 k1 ^= ((uint32_t)tail[2]) << 16;
 137                 /*-fallthrough*/
 138         case 2:
 139                 k1 ^= ((uint32_t)tail[1]) << 8;
 140                 /*-fallthrough*/
 141         case 1:
 142                 k1 ^= ((uint32_t)tail[0]) << 0;
 143                 k1 *= c1;
 144                 k1 = rotate_left(k1, r1);
 145                 k1 *= c2;
 146                 seed ^= k1;
 147                 break;
 148         }
 149
 150         seed ^= (uint32_t)len;
 151         seed ^= (seed >> 16);
 152         seed *= 0x85ebca6b;
 153         seed ^= (seed >> 13);
 154         seed *= 0xc2b2ae35;
 155         seed ^= (seed >> 16);
 156
 157         return seed;
 158 }
 159
 160 void fill_bloom_key(const char *data,
 161                     size_t len,
 162                     struct bloom_key *key,
 163                     const struct bloom_filter_settings *settings)
 164 {
 165         int i;
 166         const uint32_t seed0 = 0x293ae76f;
 167         const uint32_t seed1 = 0x7e646e2c;
 168         const uint32_t hash0 = murmur3_seeded(seed0, data, len);
 169         const uint32_t hash1 = murmur3_seeded(seed1, data, len);
 170
 171         key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));
 172         for (i = 0; i < settings->num_hashes; i++)
 173                 key->hashes[i] = hash0 + i * hash1;
 174 }
 175
 176 void clear_bloom_key(struct bloom_key *key)
 177 {
 178         FREE_AND_NULL(key->hashes);
 179 }
 180
 181 void add_key_to_filter(const struct bloom_key *key,
 182                        struct bloom_filter *filter,
 183                        const struct bloom_filter_settings *settings)
 184 {
 185         int i;
 186         uint64_t mod = filter->len * BITS_PER_WORD;
 187
 188         for (i = 0; i < settings->num_hashes; i++) {
 189                 uint64_t hash_mod = key->hashes[i] % mod;
 190                 uint64_t block_pos = hash_mod / BITS_PER_WORD;
 191
 192                 filter->data[block_pos] |= get_bitmask(hash_mod);
 193         }
 194 }
 195
 196 void init_bloom_filters(void)
 197 {
 198         init_bloom_filter_slab(&bloom_filters);
 199 }
 200
 201 static int pathmap_cmp(const void *hashmap_cmp_fn_data UNUSED,
 202                        const struct hashmap_entry *eptr,
 203                        const struct hashmap_entry *entry_or_key,
 204                        const void *keydata UNUSED)
 205 {
 206         const struct pathmap_hash_entry *e1, *e2;
 207
 208         e1 = container_of(eptr, const struct pathmap_hash_entry, entry);
 209         e2 = container_of(entry_or_key, const struct pathmap_hash_entry, entry);
 210
 211         return strcmp(e1->path, e2->path);
 212 }
 213
 214 static void init_truncated_large_filter(struct bloom_filter *filter)
 215 {
 216         filter->data = xmalloc(1);
 217         filter->data[0] = 0xFF;
 218         filter->len = 1;
 219 }
 220
 221 struct bloom_filter *get_or_compute_bloom_filter(struct repository *r,
 222                                                  struct commit *c,
 223                                                  int compute_if_not_present,
 224                                                  const struct bloom_filter_settings *settings,
 225                                                  enum bloom_filter_computed *computed)
 226 {
 227         struct bloom_filter *filter;
 228         int i;
 229         struct diff_options diffopt;
 230
 231         if (computed)
 232                 *computed = BLOOM_NOT_COMPUTED;
 233
 234         if (!bloom_filters.slab_size)
 235                 return NULL;
 236
 237         filter = bloom_filter_slab_at(&bloom_filters, c);
 238
 239         if (!filter->data) {
 240                 uint32_t graph_pos;
 241                 if (repo_find_commit_pos_in_graph(r, c, &graph_pos))
 242                         load_bloom_filter_from_graph(r->objects->commit_graph,
 243                                                      filter, graph_pos);
 244         }
 245
 246         if (filter->data && filter->len)
 247                 return filter;
 248         if (!compute_if_not_present)
 249                 return NULL;
 250
 251         repo_diff_setup(r, &diffopt);
 252         diffopt.flags.recursive = 1;
 253         diffopt.detect_rename = 0;
 254         diffopt.max_changes = settings->max_changed_paths;
 255         diff_setup_done(&diffopt);
 256
 257         /* ensure commit is parsed so we have parent information */
 258         repo_parse_commit(r, c);
 259
 260         if (c->parents)
 261                 diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt);
 262         else
 263                 diff_tree_oid(NULL, &c->object.oid, "", &diffopt);
 264         diffcore_std(&diffopt);
 265
 266         if (diff_queued_diff.nr <= settings->max_changed_paths) {
 267                 struct hashmap pathmap = HASHMAP_INIT(pathmap_cmp, NULL);
 268                 struct pathmap_hash_entry *e;
 269                 struct hashmap_iter iter;
 270
 271                 for (i = 0; i < diff_queued_diff.nr; i++) {
 272                         const char *path = diff_queued_diff.queue[i]->two->path;
 273
 274                         /*
 275                          * Add each leading directory of the changed file, i.e. for
 276                          * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
 277                          * the Bloom filter could be used to speed up commands like
 278                          * 'git log dir/subdir', too.
 279                          *
 280                          * Note that directories are added without the trailing '/'.
 281                          */
 282                         do {
 283                                 char *last_slash = strrchr(path, '/');
 284
 285                                 FLEX_ALLOC_STR(e, path, path);
 286                                 hashmap_entry_init(&e->entry, strhash(path));
 287
 288                                 if (!hashmap_get(&pathmap, &e->entry, NULL))
 289                                         hashmap_add(&pathmap, &e->entry);
 290                                 else
 291                                         free(e);
 292
 293                                 if (!last_slash)
 294                                         last_slash = (char*)path;
 295                                 *last_slash = '\0';
 296
 297                         } while (*path);
 298
 299                         diff_free_filepair(diff_queued_diff.queue[i]);
 300                 }
 301
 302                 if (hashmap_get_size(&pathmap) > settings->max_changed_paths) {
 303                         init_truncated_large_filter(filter);
 304                         if (computed)
 305                                 *computed |= BLOOM_TRUNC_LARGE;
 306                         goto cleanup;
 307                 }
 308
 309                 filter->len = (hashmap_get_size(&pathmap) * settings->bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
 310                 if (!filter->len) {
 311                         if (computed)
 312                                 *computed |= BLOOM_TRUNC_EMPTY;
 313                         filter->len = 1;
 314                 }
 315                 CALLOC_ARRAY(filter->data, filter->len);
 316
 317                 hashmap_for_each_entry(&pathmap, &iter, e, entry) {
 318                         struct bloom_key key;
 319                         fill_bloom_key(e->path, strlen(e->path), &key, settings);
 320                         add_key_to_filter(&key, filter, settings);
 321                         clear_bloom_key(&key);
 322                 }
 323
 324         cleanup:
 325                 hashmap_clear_and_free(&pathmap, struct pathmap_hash_entry, entry);
 326         } else {
 327                 for (i = 0; i < diff_queued_diff.nr; i++)
 328                         diff_free_filepair(diff_queued_diff.queue[i]);
 329                 init_truncated_large_filter(filter);
 330
 331                 if (computed)
 332                         *computed |= BLOOM_TRUNC_LARGE;
 333         }
 334
 335         if (computed)
 336                 *computed |= BLOOM_COMPUTED;
 337
 338         free(diff_queued_diff.queue);
 339         DIFF_QUEUE_CLEAR(&diff_queued_diff);
 340
 341         return filter;
 342 }
 343
 344 int bloom_filter_contains(const struct bloom_filter *filter,
 345                           const struct bloom_key *key,
 346                           const struct bloom_filter_settings *settings)
 347 {
 348         int i;
 349         uint64_t mod = filter->len * BITS_PER_WORD;
 350
 351         if (!mod)
 352                 return -1;
 353
 354         for (i = 0; i < settings->num_hashes; i++) {
 355                 uint64_t hash_mod = key->hashes[i] % mod;
 356                 uint64_t block_pos = hash_mod / BITS_PER_WORD;
 357                 if (!(filter->data[block_pos] & get_bitmask(hash_mod)))
 358                         return 0;
 359         }
 360
 361         return 1;
 362 }