summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/libsystemd/sd-bus/PORTING-DBUS140
-rw-r--r--src/libsystemd/sd-bus/bus-bloom.c112
-rw-r--r--src/libsystemd/sd-bus/bus-bloom.h22
-rw-r--r--src/libsystemd/sd-bus/bus-control.c26
-rw-r--r--src/libsystemd/sd-bus/bus-internal.h3
-rw-r--r--src/libsystemd/sd-bus/bus-kernel.c41
-rw-r--r--src/systemd/sd-id128.h4
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
generated by cgit v1.2.3-54-g00ecf (git 2.45.2) at 2024-11-11 02:25:53 +0000