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

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