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

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