src/libelogind/sd-bus/bus-bloom.c

   1 /***
   2   This file is part of systemd.
   3
   4   Copyright 2013 Lennart Poettering
   5
   6   systemd is free software; you can redistribute it and/or modify it
   7   under the terms of the GNU Lesser General Public License as published by
   8   the Free Software Foundation; either version 2.1 of the License, or
   9   (at your option) any later version.
  10
  11   systemd is distributed in the hope that it will be useful, but
  12   WITHOUT ANY WARRANTY; without even the implied warranty of
  13   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
  14   Lesser General Public License for more details.
  15
  16   You should have received a copy of the GNU Lesser General Public License
  17   along with systemd; If not, see <http://www.gnu.org/licenses/>.
  18 ***/
  19
  20 #include "bus-bloom.h"
  21 #include "siphash24.h"
  22 #include "util.h"
  23
  24 static inline void set_bit(uint64_t filter[], unsigned long b) {
  25         filter[b >> 6] |= 1ULL << (b & 63);
  26 }
  27
  28 static const sd_id128_t hash_keys[] = {
  29         SD_ID128_ARRAY(b9,66,0b,f0,46,70,47,c1,88,75,c4,9c,54,b9,bd,15),
  30         SD_ID128_ARRAY(aa,a1,54,a2,e0,71,4b,39,bf,e1,dd,2e,9f,c5,4a,3b),
  31         SD_ID128_ARRAY(63,fd,ae,be,cd,82,48,12,a1,6e,41,26,cb,fa,a0,c8),
  32         SD_ID128_ARRAY(23,be,45,29,32,d2,46,2d,82,03,52,28,fe,37,17,f5),
  33         SD_ID128_ARRAY(56,3b,bf,ee,5a,4f,43,39,af,aa,94,08,df,f0,fc,10),
  34         SD_ID128_ARRAY(31,80,c8,73,c7,ea,46,d3,aa,25,75,0f,9e,4c,09,29),
  35         SD_ID128_ARRAY(7d,f7,18,4b,7b,a4,44,d5,85,3c,06,e0,65,53,96,6d),
  36         SD_ID128_ARRAY(f2,77,e9,6f,93,b5,4e,71,9a,0c,34,88,39,25,bf,35),
  37 };
  38
  39 static void bloom_add_data(
  40                 uint64_t filter[],     /* The filter bits */
  41                 size_t size,           /* Size of the filter in bytes */
  42                 unsigned k,            /* Number of hash functions */
  43                 const void *data,      /* Data to hash */
  44                 size_t n) {            /* Size of data to hash in bytes */
  45
  46         uint64_t h;
  47         uint64_t m;
  48         unsigned w, i, c = 0;
  49         unsigned hash_index;
  50
  51         assert(size > 0);
  52         assert(k > 0);
  53
  54         /* Determine bits in filter */
  55         m = size * 8;
  56
  57         /* Determine how many bytes we need to generate a bit index 0..m for this filter */
  58         w = (u64log2(m) + 7) / 8;
  59
  60         assert(w <= sizeof(uint64_t));
  61
  62         /* Make sure we have enough hash keys to generate m * k bits
  63          * of hash value. Note that SipHash24 generates 64 bits of
  64          * hash value for each 128 bits of hash key. */
  65         assert(k * w <= ELEMENTSOF(hash_keys) * 8);
  66
  67         for (i = 0, hash_index = 0; i < k; i++) {
  68                 uint64_t p = 0;
  69                 unsigned d;
  70
  71                 for (d = 0; d < w; d++) {
  72                         if (c <= 0) {
  73                                 h = siphash24(data, n, hash_keys[hash_index++].bytes);
  74                                 c += 8;
  75                         }
  76
  77                         p = (p << 8ULL) | (uint64_t) ((uint8_t *)&h)[8 - c];
  78                         c--;
  79                 }
  80
  81                 p &= m - 1;
  82                 set_bit(filter, p);
  83         }
  84
  85         /* log_debug("bloom: adding <%.*s>", (int) n, (char*) data); */
  86 }
  87
  88 void bloom_add_pair(uint64_t filter[], size_t size, unsigned k, const char *a, const char *b) {
  89         size_t n;
  90         char *c;
  91
  92         assert(filter);
  93         assert(a);
  94         assert(b);
  95
  96         n = strlen(a) + 1 + strlen(b);
  97         c = alloca(n + 1);
  98         strcpy(stpcpy(stpcpy(c, a), ":"), b);
  99
 100         bloom_add_data(filter, size, k, c, n);
 101 }
 102
 103 void bloom_add_prefixes(uint64_t filter[], size_t size, unsigned k, const char *a, const char *b, char sep) {
 104         size_t n;
 105         char *c, *p;
 106
 107         assert(filter);
 108         assert(a);
 109         assert(b);
 110
 111         n = strlen(a) + 1 + strlen(b);
 112         c = alloca(n + 1);
 113
 114         p = stpcpy(stpcpy(c, a), ":");
 115         strcpy(p, b);
 116
 117         bloom_add_data(filter, size, k, c, n);
 118
 119         for (;;) {
 120                 char *e;
 121
 122                 e = strrchr(p, sep);
 123                 if (!e)
 124                         break;
 125
 126                 *(e + 1) = 0;
 127                 bloom_add_data(filter, size, k, c, e - c + 1);
 128
 129                 if (e == p)
 130                         break;
 131
 132                 *e = 0;
 133                 bloom_add_data(filter, size, k, c, e - c);
 134         }
 135 }
 136
 137 bool bloom_validate_parameters(size_t size, unsigned k) {
 138         uint64_t m;
 139         unsigned w;
 140
 141         if (size <= 0)
 142                 return false;
 143
 144         if (k <= 0)
 145                 return false;
 146
 147         m = size * 8;
 148         w = (u64log2(m) + 7) / 8;
 149         if (w > sizeof(uint64_t))
 150                 return false;
 151
 152         if (k * w > ELEMENTSOF(hash_keys) * 8)
 153                 return false;
 154
 155         return true;
 156 }