X-Git-Url: https://www.chiark.greenend.org.uk/ucgi/~ianmdlvl/git?p=elogind.git;a=blobdiff_plain;f=src%2Flibsystemd%2Fsd-bus%2Fbus-bloom.c;h=e1542969942ab706b7608d98255786e8832e392c;hp=9e51334b5269ce125e1c035e9ccfe078bae62e70;hb=b28ff39f42877daef31383748fd2f313d7fd67c1;hpb=af08d2f9cde8f46d9d3e731dbd1f06ffb3b08942

diff --git a/src/libsystemd/sd-bus/bus-bloom.c b/src/libsystemd/sd-bus/bus-bloom.c
index 9e51334b5..e15429699 100644
--- a/src/libsystemd/sd-bus/bus-bloom.c
+++ b/src/libsystemd/sd-bus/bus-bloom.c
@@ -23,41 +23,70 @@
 #include "siphash24.h"
 #include "bus-bloom.h"
 
-static inline void set_bit(uint64_t filter[], unsigned b) {
+static inline void set_bit(uint64_t filter[], unsigned long b) {
         filter[b >> 6] |= 1ULL << (b & 63);
 }
 
-#define HASH_KEY1 SD_ID128_MAKE(b9,66,0b,f0,46,70,47,c1,88,75,c4,9c,54,b9,bd,15)
-#define HASH_KEY2 SD_ID128_MAKE(aa,a1,54,a2,e0,71,4b,39,bf,e1,dd,2e,9f,c5,4a,3b)
-
-static void bloom_add_data(uint64_t filter[BLOOM_SIZE/8], const void *data, size_t n) {
-        uint8_t a[8], b[8];
-        unsigned k = 0;
-
-        /*
-         * Our bloom filter has the following parameters:
-         *
-         * m=512   (bits in the filter)
-         * k=8     (hash functions)
-         *
-         * We calculate a two 64bit SipHash values (for two fixed but
-         * randomly generated hash keys) of which we use 8 parts of 9 bits
-         * as individual hash functions.
-         *
-         */
-
-        siphash24(a, data, n, HASH_KEY1.bytes);
-        siphash24(b, data, n, HASH_KEY2.bytes);
-
-        assert_cc(BLOOM_SIZE*8 == 512);
-
-        for (k = 0; k < 8; k++)
-                set_bit(filter, ((uint16_t) a[k] << 1) ^ (uint16_t) b[k]);
+static const sd_id128_t hash_keys[] = {
+        SD_ID128_ARRAY(b9,66,0b,f0,46,70,47,c1,88,75,c4,9c,54,b9,bd,15),
+        SD_ID128_ARRAY(aa,a1,54,a2,e0,71,4b,39,bf,e1,dd,2e,9f,c5,4a,3b),
+        SD_ID128_ARRAY(63,fd,ae,be,cd,82,48,12,a1,6e,41,26,cb,fa,a0,c8),
+        SD_ID128_ARRAY(23,be,45,29,32,d2,46,2d,82,03,52,28,fe,37,17,f5),
+        SD_ID128_ARRAY(56,3b,bf,ee,5a,4f,43,39,af,aa,94,08,df,f0,fc,10),
+        SD_ID128_ARRAY(31,80,c8,73,c7,ea,46,d3,aa,25,75,0f,9e,4c,09,29),
+        SD_ID128_ARRAY(7d,f7,18,4b,7b,a4,44,d5,85,3c,06,e0,65,53,96,6d),
+        SD_ID128_ARRAY(f2,77,e9,6f,93,b5,4e,71,9a,0c,34,88,39,25,bf,35),
+};
+
+static void bloom_add_data(
+                uint64_t filter[],     /* The filter bits */
+                size_t size,           /* Size of the filter in bytes */
+                unsigned k,            /* Number of hash functions */
+                const void *data,      /* Data to hash */
+                size_t n) {            /* Size of data to hash in bytes */
+
+        uint8_t h[8];
+        uint64_t m;
+        unsigned w, i, c = 0;
+
+        assert(size > 0);
+        assert(k > 0);
+
+        /* Determine bits in filter */
+        m = size * 8;
+
+        /* Determine how many bytes we need to generate a bit index 0..m for this filter */
+        w = (u64log2(m) + 7) / 8;
+
+        assert(w <= sizeof(uint64_t));
+
+        /* Make sure we have enough hash keys to generate m * k bits
+         * of hash value. Note that SipHash24 generates 64 bits of
+         * hash value for each 128 bits of hash key. */
+        assert(k * w <= ELEMENTSOF(hash_keys) * 8);
+
+        for (i = 0; i < k; i++) {
+                uint64_t p = 0;
+                unsigned d;
+
+                for (d = 0; d < w; d++) {
+                        if (c <= 0) {
+                                siphash24(h, data, n, hash_keys[i++].bytes);
+                                c += 8;
+                        }
+
+                        p = (p << 8ULL) | (uint64_t) h[8 - c];
+                        c--;
+                }
+
+                p &= m - 1;
+                set_bit(filter, p);
+        }
 
         /* log_debug("bloom: adding <%.*s>", (int) n, (char*) data); */
 }
 
-void bloom_add_pair(uint64_t filter[BLOOM_SIZE/8], const char *a, const char *b) {
+void bloom_add_pair(uint64_t filter[], size_t size, unsigned k, const char *a, const char *b) {
         size_t n;
         char *c;
 
@@ -69,10 +98,10 @@ void bloom_add_pair(uint64_t filter[BLOOM_SIZE/8], const char *a, const char *b)
         c = alloca(n + 1);
         strcpy(stpcpy(stpcpy(c, a), ":"), b);
 
-        bloom_add_data(filter, c, n);
+        bloom_add_data(filter, size, k, c, n);
 }
 
-void bloom_add_prefixes(uint64_t filter[BLOOM_SIZE/8], const char *a, const char *b, char sep) {
+void bloom_add_prefixes(uint64_t filter[], size_t size, unsigned k, const char *a, const char *b, char sep) {
         size_t n;
         char *c, *p;
 
@@ -94,6 +123,27 @@ void bloom_add_prefixes(uint64_t filter[BLOOM_SIZE/8], const char *a, const char
                         break;
 
                 *e = 0;
-                bloom_add_data(filter, c, e - c);
+                bloom_add_data(filter, size, k, c, e - c);
         }
 }
+
+bool bloom_validate_parameters(size_t size, unsigned k) {
+        uint64_t m;
+        unsigned w;
+
+        if (size <= 0)
+                return false;
+
+        if (k <= 0)
+                return false;
+
+        m = size * 8;
+        w = (u64log2(m) + 7) / 8;
+        if (w > sizeof(uint64_t))
+                return false;
+
+        if (k * w > ELEMENTSOF(hash_keys) * 8)
+                return false;
+
+        return true;
+}