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
   8 define_commit_slab(bloom_filter_slab, struct bloom_filter);
   9
  10 struct bloom_filter_slab bloom_filters;
  11
  12 struct pathmap_hash_entry {
  13     struct hashmap_entry entry;
  14     const char path[FLEX_ARRAY];
  15 };
  16
  17 static uint32_t rotate_left(uint32_t value, int32_t count)
  18 {
  19         uint32_t mask = 8 * sizeof(uint32_t) - 1;
  20         count &= mask;
  21         return ((value << count) | (value >> ((-count) & mask)));
  22 }
  23
  24 static inline unsigned char get_bitmask(uint32_t pos)
  25 {
  26         return ((unsigned char)1) << (pos & (BITS_PER_WORD - 1));
  27 }
  28
  29 /*
  30  * Calculate the murmur3 32-bit hash value for the given data
  31  * using the given seed.
  32  * Produces a uniformly distributed hash value.
  33  * Not considered to be cryptographically secure.
  34  * Implemented as described in https://en.wikipedia.org/wiki/MurmurHash#Algorithm
  35  */
  36 uint32_t murmur3_seeded(uint32_t seed, const char *data, size_t len)
  37 {
  38         const uint32_t c1 = 0xcc9e2d51;
  39         const uint32_t c2 = 0x1b873593;
  40         const uint32_t r1 = 15;
  41         const uint32_t r2 = 13;
  42         const uint32_t m = 5;
  43         const uint32_t n = 0xe6546b64;
  44         int i;
  45         uint32_t k1 = 0;
  46         const char *tail;
  47
  48         int len4 = len / sizeof(uint32_t);
  49
  50         uint32_t k;
  51         for (i = 0; i < len4; i++) {
  52                 uint32_t byte1 = (uint32_t)data[4*i];
  53                 uint32_t byte2 = ((uint32_t)data[4*i + 1]) << 8;
  54                 uint32_t byte3 = ((uint32_t)data[4*i + 2]) << 16;
  55                 uint32_t byte4 = ((uint32_t)data[4*i + 3]) << 24;
  56                 k = byte1 | byte2 | byte3 | byte4;
  57                 k *= c1;
  58                 k = rotate_left(k, r1);
  59                 k *= c2;
  60
  61                 seed ^= k;
  62                 seed = rotate_left(seed, r2) * m + n;
  63         }
  64
  65         tail = (data + len4 * sizeof(uint32_t));
  66
  67         switch (len & (sizeof(uint32_t) - 1)) {
  68         case 3:
  69                 k1 ^= ((uint32_t)tail[2]) << 16;
  70                 /*-fallthrough*/
  71         case 2:
  72                 k1 ^= ((uint32_t)tail[1]) << 8;
  73                 /*-fallthrough*/
  74         case 1:
  75                 k1 ^= ((uint32_t)tail[0]) << 0;
  76                 k1 *= c1;
  77                 k1 = rotate_left(k1, r1);
  78                 k1 *= c2;
  79                 seed ^= k1;
  80                 break;
  81         }
  82
  83         seed ^= (uint32_t)len;
  84         seed ^= (seed >> 16);
  85         seed *= 0x85ebca6b;
  86         seed ^= (seed >> 13);
  87         seed *= 0xc2b2ae35;
  88         seed ^= (seed >> 16);
  89
  90         return seed;
  91 }
  92
  93 void fill_bloom_key(const char *data,
  94                                         size_t len,
  95                                         struct bloom_key *key,
  96                                         const struct bloom_filter_settings *settings)
  97 {
  98         int i;
  99         const uint32_t seed0 = 0x293ae76f;
 100         const uint32_t seed1 = 0x7e646e2c;
 101         const uint32_t hash0 = murmur3_seeded(seed0, data, len);
 102         const uint32_t hash1 = murmur3_seeded(seed1, data, len);
 103
 104         key->hashes = (uint32_t *)xcalloc(settings->num_hashes, sizeof(uint32_t));
 105         for (i = 0; i < settings->num_hashes; i++)
 106                 key->hashes[i] = hash0 + i * hash1;
 107 }
 108
 109 void add_key_to_filter(const struct bloom_key *key,
 110                                            struct bloom_filter *filter,
 111                                            const struct bloom_filter_settings *settings)
 112 {
 113         int i;
 114         uint64_t mod = filter->len * BITS_PER_WORD;
 115
 116         for (i = 0; i < settings->num_hashes; i++) {
 117                 uint64_t hash_mod = key->hashes[i] % mod;
 118                 uint64_t block_pos = hash_mod / BITS_PER_WORD;
 119
 120                 filter->data[block_pos] |= get_bitmask(hash_mod);
 121         }
 122 }
 123
 124 void init_bloom_filters(void)
 125 {
 126         init_bloom_filter_slab(&bloom_filters);
 127 }
 128
 129 struct bloom_filter *get_bloom_filter(struct repository *r,
 130                                       struct commit *c)
 131 {
 132         struct bloom_filter *filter;
 133         struct bloom_filter_settings settings = DEFAULT_BLOOM_FILTER_SETTINGS;
 134         int i;
 135         struct diff_options diffopt;
 136
 137         if (bloom_filters.slab_size == 0)
 138                 return NULL;
 139
 140         filter = bloom_filter_slab_at(&bloom_filters, c);
 141
 142         repo_diff_setup(r, &diffopt);
 143         diffopt.flags.recursive = 1;
 144         diff_setup_done(&diffopt);
 145
 146         if (c->parents)
 147                 diff_tree_oid(&c->parents->item->object.oid, &c->object.oid, "", &diffopt);
 148         else
 149                 diff_tree_oid(NULL, &c->object.oid, "", &diffopt);
 150         diffcore_std(&diffopt);
 151
 152         if (diff_queued_diff.nr <= 512) {
 153                 struct hashmap pathmap;
 154                 struct pathmap_hash_entry *e;
 155                 struct hashmap_iter iter;
 156                 hashmap_init(&pathmap, NULL, NULL, 0);
 157
 158                 for (i = 0; i < diff_queued_diff.nr; i++) {
 159                         const char *path = diff_queued_diff.queue[i]->two->path;
 160
 161                         /*
 162                         * Add each leading directory of the changed file, i.e. for
 163                         * 'dir/subdir/file' add 'dir' and 'dir/subdir' as well, so
 164                         * the Bloom filter could be used to speed up commands like
 165                         * 'git log dir/subdir', too.
 166                         *
 167                         * Note that directories are added without the trailing '/'.
 168                         */
 169                         do {
 170                                 char *last_slash = strrchr(path, '/');
 171
 172                                 FLEX_ALLOC_STR(e, path, path);
 173                                 hashmap_entry_init(&e->entry, strhash(path));
 174                                 hashmap_add(&pathmap, &e->entry);
 175
 176                                 if (!last_slash)
 177                                         last_slash = (char*)path;
 178                                 *last_slash = '\0';
 179
 180                         } while (*path);
 181
 182                         diff_free_filepair(diff_queued_diff.queue[i]);
 183                 }
 184
 185                 filter->len = (hashmap_get_size(&pathmap) * settings.bits_per_entry + BITS_PER_WORD - 1) / BITS_PER_WORD;
 186                 filter->data = xcalloc(filter->len, sizeof(unsigned char));
 187
 188                 hashmap_for_each_entry(&pathmap, &iter, e, entry) {
 189                         struct bloom_key key;
 190                         fill_bloom_key(e->path, strlen(e->path), &key, &settings);
 191                         add_key_to_filter(&key, filter, &settings);
 192                 }
 193
 194                 hashmap_free_entries(&pathmap, struct pathmap_hash_entry, entry);
 195         } else {
 196                 for (i = 0; i < diff_queued_diff.nr; i++)
 197                         diff_free_filepair(diff_queued_diff.queue[i]);
 198                 filter->data = NULL;
 199                 filter->len = 0;
 200         }
 201
 202         free(diff_queued_diff.queue);
 203         DIFF_QUEUE_CLEAR(&diff_queued_diff);
 204
 205         return filter;
 206 }