bus: rework bloom filter logic to operate with variable bloom filter

sizes and numbers of hash functions

In order to make the bloom filter logic more future proof communicate
bloom filter parameters from the original bus creator to the clients,
and allow them to be variable within certain ranges.

7 files changed, 171 insertions, 77 deletions

diff --git a/src/libsystemd/sd-bus/PORTING-DBUS1 b/src/libsystemd/sd-bus/PORTING-DBUS1
index 57339ee268..eccb9e628a 100644
--- a/src/libsystemd/sd-bus/PORTING-DBUS1
+++ b/src/libsystemd/sd-bus/PORTING-DBUS1
@@ -231,18 +231,34 @@ probabilistically check whether a certain word is contained in a
 vocabulary. It knows no false negatives, but it does know false
 positives.
 
-The bloom filter that needs to be included has the parameters m=512
-(bits in the filter), k=8 (nr of hash functions). The underlying hash
-function is SipHash-2-4. We calculate two hash values for an input
-strings, one with the hash key b9660bf0467047c18875c49c54b9bd15 (this
-is supposed to be read as a series of 16 hexadecimal formatted
-bytes), and one with the hash key
-aaa154a2e0714b39bfe1dd2e9fc54a3b. This results in two 64bit hash
-values, A and B. The 8 hash functions for the bloom filter require a 9
-bit output each (since m=512=2^9), to generate these we XOR combine
-the first 8 bit of A shifted to the left by 1, with the first 8 bit of
-B. Then, for the next hash function we use the second 8 bit pair, and
-so on.
+The parameters for the bloom filters that need to be included in
+broadcast message is communicated to userspace as part of the hello
+response structure. By default it has the parameters m=512 (bits in
+the filter), k=8 (nr of hash functions). Note however, that this is
+subject to change later on, and userspace implementations must be
+capable of handling m values between at least m=8 and m=2^32, and k
+values between at least k=1 and k=32. The underlying hash function is
+SipHash-2-4. It is used with a number of constant (yet originally
+randomly generated) 128bit hash keys, more specifically:
+
+   b9,66,0b,f0,46,70,47,c1,88,75,c4,9c,54,b9,bd,15,
+   aa,a1,54,a2,e0,71,4b,39,bf,e1,dd,2e,9f,c5,4a,3b,
+   63,fd,ae,be,cd,82,48,12,a1,6e,41,26,cb,fa,a0,c8,
+   23,be,45,29,32,d2,46,2d,82,03,52,28,fe,37,17,f5,
+   56,3b,bf,ee,5a,4f,43,39,af,aa,94,08,df,f0,fc,10,
+   31,80,c8,73,c7,ea,46,d3,aa,25,75,0f,9e,4c,09,29,
+   7d,f7,18,4b,7b,a4,44,d5,85,3c,06,e0,65,53,96,6d,
+   f2,77,e9,6f,93,b5,4e,71,9a,0c,34,88,39,25,bf,35
+
+When calculating the first bit index into the bloom filter, the
+SipHash-2-4 hash value is calculated for the input data and the first
+16 bytes of the array above as hash key. Of the resulting 8 bytes of
+output, as many full bytes are taken for the index as necessary,
+starting from the output's first byte. For the second bit index the
+same hash value is used, continuing with the next unused output byte,
+and so on. Each time the bytes returned by the hash function are
+depleted it is recalculated with the next 16 byte hash key from the
+array above and the same input data.
 
 For each message to send across the bus we populate the bloom filter
 with all possible matchable strings. If a client then wants to
diff --git a/src/libsystemd/sd-bus/bus-bloom.c b/src/libsystemd/sd-bus/bus-bloom.c
index 9e51334b52..e154296994 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;
+}
diff --git a/src/libsystemd/sd-bus/bus-bloom.h b/src/libsystemd/sd-bus/bus-bloom.h
index 422eb4e01a..0dad5db78d 100644
--- a/src/libsystemd/sd-bus/bus-bloom.h
+++ b/src/libsystemd/sd-bus/bus-bloom.h
@@ -23,7 +23,21 @@
 
 #include <sys/types.h>
 
-#define BLOOM_SIZE 64
-
-void bloom_add_pair(uint64_t filter[BLOOM_SIZE/8], const char *a, const char *b);
-void bloom_add_prefixes(uint64_t filter[BLOOM_SIZE/8], const char *a, const char *b, char sep);
+/*
+ * Our default bloom filter has the following parameters:
+ *
+ * m=512   (bits in the filter)
+ * k=8     (hash functions)
+ *
+ * We use SipHash24 as hash function with a number of (originally
+ * randomized) but fixed hash keys.
+ *
+ */
+
+#define DEFAULT_BLOOM_SIZE (512/8) /* m: filter size */
+#define DEFAULT_BLOOM_N_HASH 8     /* k: number of hash functions */
+
+void bloom_add_pair(uint64_t filter[], size_t size, unsigned n_hash, const char *a, const char *b);
+void bloom_add_prefixes(uint64_t filter[], size_t size, unsigned n_hash, const char *a, const char *b, char sep);
+
+bool bloom_validate_parameters(size_t size, unsigned n_hash);
diff --git a/src/libsystemd/sd-bus/bus-control.c b/src/libsystemd/sd-bus/bus-control.c
index 35fd384cdf..846307d664 100644
--- a/src/libsystemd/sd-bus/bus-control.c
+++ b/src/libsystemd/sd-bus/bus-control.c
@@ -926,7 +926,7 @@ int bus_add_match_internal_kernel(
 
         struct kdbus_cmd_match *m;
         struct kdbus_item *item;
-        uint64_t bloom[BLOOM_SIZE/8];
+        uint64_t *bloom;
         size_t sz;
         const char *sender = NULL;
         size_t sender_length = 0;
@@ -939,7 +939,7 @@ int bus_add_match_internal_kernel(
 
         assert(bus);
 
-        zero(bloom);
+        bloom = alloca0(bus->bloom_size);
 
         sz = ALIGN8(offsetof(struct kdbus_cmd_match, items));
 
@@ -969,7 +969,7 @@ int bus_add_match_internal_kernel(
                         if (c->value_u8 != SD_BUS_MESSAGE_SIGNAL)
                                 matches_name_change = false;
 
-                        bloom_add_pair(bloom, "message-type", bus_message_type_to_string(c->value_u8));
+                        bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "message-type", bus_message_type_to_string(c->value_u8));
                         using_bloom = true;
                         break;
 
@@ -977,7 +977,7 @@ int bus_add_match_internal_kernel(
                         if (!streq(c->value_str, "org.freedesktop.DBus"))
                                 matches_name_change = false;
 
-                        bloom_add_pair(bloom, "interface", c->value_str);
+                        bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "interface", c->value_str);
                         using_bloom = true;
                         break;
 
@@ -985,7 +985,7 @@ int bus_add_match_internal_kernel(
                         if (!streq(c->value_str, "NameOwnerChanged"))
                                 matches_name_change = false;
 
-                        bloom_add_pair(bloom, "member", c->value_str);
+                        bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "member", c->value_str);
                         using_bloom = true;
                         break;
 
@@ -993,13 +993,13 @@ int bus_add_match_internal_kernel(
                         if (!streq(c->value_str, "/org/freedesktop/DBus"))
                                 matches_name_change = false;
 
-                        bloom_add_pair(bloom, "path", c->value_str);
+                        bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "path", c->value_str);
                         using_bloom = true;
                         break;
 
                 case BUS_MATCH_PATH_NAMESPACE:
                         if (!streq(c->value_str, "/")) {
-                                bloom_add_pair(bloom, "path-slash-prefix", c->value_str);
+                                bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "path-slash-prefix", c->value_str);
                                 using_bloom = true;
                         }
                         break;
@@ -1011,7 +1011,7 @@ int bus_add_match_internal_kernel(
                                 name_change_arg[c->type - BUS_MATCH_ARG] = c->value_str;
 
                         snprintf(buf, sizeof(buf), "arg%u", c->type - BUS_MATCH_ARG);
-                        bloom_add_pair(bloom, buf, c->value_str);
+                        bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, buf, c->value_str);
                         using_bloom = true;
                         break;
                 }
@@ -1020,7 +1020,7 @@ int bus_add_match_internal_kernel(
                         char buf[sizeof("arg")-1 + 2 + sizeof("-slash-prefix")];
 
                         snprintf(buf, sizeof(buf), "arg%u-slash-prefix", c->type - BUS_MATCH_ARG_PATH);
-                        bloom_add_pair(bloom, buf, c->value_str);
+                        bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, buf, c->value_str);
                         using_bloom = true;
                         break;
                 }
@@ -1029,7 +1029,7 @@ int bus_add_match_internal_kernel(
                         char buf[sizeof("arg")-1 + 2 + sizeof("-dot-prefix")];
 
                         snprintf(buf, sizeof(buf), "arg%u-dot-prefix", c->type - BUS_MATCH_ARG_NAMESPACE);
-                        bloom_add_pair(bloom, buf, c->value_str);
+                        bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, buf, c->value_str);
                         using_bloom = true;
                         break;
                 }
@@ -1052,7 +1052,7 @@ int bus_add_match_internal_kernel(
         }
 
         if (using_bloom)
-                sz += ALIGN8(offsetof(struct kdbus_item, data64) + BLOOM_SIZE);
+                sz += ALIGN8(offsetof(struct kdbus_item, data64) + bus->bloom_size);
 
         m = alloca0(sz);
         m->size = sz;
@@ -1069,9 +1069,9 @@ int bus_add_match_internal_kernel(
         }
 
         if (using_bloom) {
-                item->size = offsetof(struct kdbus_item, data64) + BLOOM_SIZE;
+                item->size = offsetof(struct kdbus_item, data64) + bus->bloom_size;
                 item->type = KDBUS_ITEM_BLOOM_MASK;
-                memcpy(item->data64, bloom, BLOOM_SIZE);
+                memcpy(item->data64, bloom, bus->bloom_size);
                 item = KDBUS_ITEM_NEXT(item);
         }
 
diff --git a/src/libsystemd/sd-bus/bus-internal.h b/src/libsystemd/sd-bus/bus-internal.h
index 69e07018d8..a4160ef4a1 100644
--- a/src/libsystemd/sd-bus/bus-internal.h
+++ b/src/libsystemd/sd-bus/bus-internal.h
@@ -271,6 +271,9 @@ struct sd_bus {
         char *cgroup_root;
 
         char *connection_name;
+
+        size_t bloom_size;
+        unsigned bloom_n_hash;
 };
 
 #define BUS_DEFAULT_TIMEOUT ((usec_t) (25 * USEC_PER_SEC))
diff --git a/src/libsystemd/sd-bus/bus-kernel.c b/src/libsystemd/sd-bus/bus-kernel.c
index b46cada648..0b5bae32d5 100644
--- a/src/libsystemd/sd-bus/bus-kernel.c
+++ b/src/libsystemd/sd-bus/bus-kernel.c
@@ -140,19 +140,19 @@ static int bus_message_setup_bloom(sd_bus_message *m, struct kdbus_bloom_filter
         assert(bloom);
 
         data = bloom->data;
-        memset(data, 0, BLOOM_SIZE);
+        memset(data, 0, m->bus->bloom_size);
         bloom->generation = 0;
 
-        bloom_add_pair(data, "message-type", bus_message_type_to_string(m->header->type));
+        bloom_add_pair(data, m->bus->bloom_size, m->bus->bloom_n_hash, "message-type", bus_message_type_to_string(m->header->type));
 
         if (m->interface)
-                bloom_add_pair(data, "interface", m->interface);
+                bloom_add_pair(data, m->bus->bloom_size, m->bus->bloom_n_hash, "interface", m->interface);
         if (m->member)
-                bloom_add_pair(data, "member", m->member);
+                bloom_add_pair(data, m->bus->bloom_size, m->bus->bloom_n_hash, "member", m->member);
         if (m->path) {
-                bloom_add_pair(data, "path", m->path);
-                bloom_add_pair(data, "path-slash-prefix", m->path);
-                bloom_add_prefixes(data, "path-slash-prefix", m->path, '/');
+                bloom_add_pair(data, m->bus->bloom_size, m->bus->bloom_n_hash, "path", m->path);
+                bloom_add_pair(data, m->bus->bloom_size, m->bus->bloom_n_hash, "path-slash-prefix", m->path);
+                bloom_add_prefixes(data, m->bus->bloom_size, m->bus->bloom_n_hash, "path-slash-prefix", m->path, '/');
         }
 
         r = sd_bus_message_rewind(m, true);
@@ -187,12 +187,12 @@ static int bus_message_setup_bloom(sd_bus_message *m, struct kdbus_bloom_filter
                 }
 
                 *e = 0;
-                bloom_add_pair(data, buf, t);
+                bloom_add_pair(data, m->bus->bloom_size, m->bus->bloom_n_hash, buf, t);
 
                 strcpy(e, "-dot-prefix");
-                bloom_add_prefixes(data, buf, t, '.');
+                bloom_add_prefixes(data, m->bus->bloom_size, m->bus->bloom_n_hash, buf, t, '.');
                 strcpy(e, "-slash-prefix");
-                bloom_add_prefixes(data, buf, t, '/');
+                bloom_add_prefixes(data, m->bus->bloom_size, m->bus->bloom_n_hash, buf, t, '/');
         }
 
         return 0;
@@ -237,7 +237,7 @@ static int bus_message_setup_kmsg(sd_bus *b, sd_bus_message *m) {
         /* Add space for bloom filter */
         sz += ALIGN8(offsetof(struct kdbus_item, bloom_filter) +
                      offsetof(struct kdbus_bloom_filter, data) +
-                     BLOOM_SIZE);
+                     m->bus->bloom_size);
 
         /* Add in well-known destination header */
         if (well_known) {
@@ -311,7 +311,7 @@ static int bus_message_setup_kmsg(sd_bus *b, sd_bus_message *m) {
         if (m->kdbus->dst_id == KDBUS_DST_ID_BROADCAST) {
                 struct kdbus_bloom_filter *bloom;
 
-                bloom = append_bloom(&d, BLOOM_SIZE);
+                bloom = append_bloom(&d, m->bus->bloom_size);
                 r = bus_message_setup_bloom(m, bloom);
                 if (r < 0)
                         goto fail;
@@ -754,9 +754,12 @@ int bus_kernel_take_fd(sd_bus *b) {
             hello->conn_flags > 0xFFFFFFFFULL)
                 return -ENOTSUP;
 
-        if (hello->bloom.size != BLOOM_SIZE)
+        if (!bloom_validate_parameters((size_t) hello->bloom.size, (unsigned) hello->bloom.n_hash))
                 return -ENOTSUP;
 
+        b->bloom_size = (size_t) hello->bloom.size;
+        b->bloom_n_hash = (unsigned) hello->bloom.n_hash;
+
         if (asprintf(&b->unique_name, ":1.%llu", (unsigned long long) hello->id) < 0)
                 return -ENOMEM;
 
@@ -1291,9 +1294,13 @@ int bus_kernel_create_bus(const char *name, bool world, char **s) {
         n->size = offsetof(struct kdbus_item, bloom_parameter) +
                   sizeof(struct kdbus_bloom_parameter);
         n->type = KDBUS_ITEM_BLOOM_PARAMETER;
-        n->bloom_parameter.size = BLOOM_SIZE;
-        n->bloom_parameter.n_hash = 1;
-        assert_cc(BLOOM_SIZE % 8 == 0);
+
+        n->bloom_parameter.size = DEFAULT_BLOOM_SIZE;
+        n->bloom_parameter.n_hash = DEFAULT_BLOOM_N_HASH;
+
+        assert_cc(DEFAULT_BLOOM_SIZE > 0);
+        assert_cc(DEFAULT_BLOOM_N_HASH > 0);
+
         make->size += ALIGN8(n->size);
 
         n = KDBUS_ITEM_NEXT(n);
@@ -1373,7 +1380,7 @@ int bus_kernel_create_starter(const char *bus, const char *name) {
                 return -ENOTSUP;
         }
 
-        if (hello->bloom.size != BLOOM_SIZE) {
+        if (!bloom_validate_parameters((size_t) hello->bloom.size, (unsigned) hello->bloom.n_hash)) {
                 close_nointr_nofail(fd);
                 return -ENOTSUP;
         }
diff --git a/src/systemd/sd-id128.h b/src/systemd/sd-id128.h
index fb82b6fa48..f14efeb28d 100644
--- a/src/systemd/sd-id128.h
+++ b/src/systemd/sd-id128.h
@@ -54,6 +54,10 @@ int sd_id128_get_boot(sd_id128_t *ret);
         ((const sd_id128_t) { .bytes = { 0x##v0, 0x##v1, 0x##v2, 0x##v3, 0x##v4, 0x##v5, 0x##v6, 0x##v7, \
                                    0x##v8, 0x##v9, 0x##v10, 0x##v11, 0x##v12, 0x##v13, 0x##v14, 0x##v15 }})
 
+#define SD_ID128_ARRAY(v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, v10, v11, v12, v13, v14, v15) \
+        { .bytes = { 0x##v0, 0x##v1, 0x##v2, 0x##v3, 0x##v4, 0x##v5, 0x##v6, 0x##v7, \
+                     0x##v8, 0x##v9, 0x##v10, 0x##v11, 0x##v12, 0x##v13, 0x##v14, 0x##v15 }}
+
 /* Note that SD_ID128_FORMAT_VAL will evaluate the passed argument 16
  * times. It is hence not a good idea to call this macro with an
  * expensive function as paramater or an expression with side