diff options
Diffstat (limited to 'src/libsystemd/sd-bus')
| -rw-r--r-- | src/libsystemd/sd-bus/PORTING-DBUS1 | 40 | ||||
| -rw-r--r-- | src/libsystemd/sd-bus/bus-bloom.c | 112 | ||||
| -rw-r--r-- | src/libsystemd/sd-bus/bus-bloom.h | 22 | ||||
| -rw-r--r-- | src/libsystemd/sd-bus/bus-control.c | 26 | ||||
| -rw-r--r-- | src/libsystemd/sd-bus/bus-internal.h | 3 | ||||
| -rw-r--r-- | src/libsystemd/sd-bus/bus-kernel.c | 41 |
6 files changed, 167 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; } |