From d779c75db604ca6dfadbf88f33bf8d2c4b10163c Mon Sep 17 00:00:00 2001 From: Adrian Szyndela Date: Thu, 20 Feb 2020 09:16:13 +0100 Subject: [PATCH] Revert "sd-bus: drop bloom stuff, it's not needed anymore since kdbus is gone" This reverts commit 1a86b085138234c9166614adc5ad399a19dae84b. Change-Id: I14360ef56ba8852487f3cf005d7b0344a493f262 --- src/libsystemd/meson.build | 2 + src/libsystemd/sd-bus/bus-bloom.c | 158 +++++++++++++++++++++++++++++ src/libsystemd/sd-bus/bus-bloom.h | 44 ++++++++ src/libsystemd/sd-bus/bus-control-kernel.c | 18 ++-- src/libsystemd/sd-bus/bus-control.c | 1 + src/libsystemd/sd-bus/bus-kernel.c | 45 ++++---- 6 files changed, 237 insertions(+), 31 deletions(-) create mode 100644 src/libsystemd/sd-bus/bus-bloom.c create mode 100644 src/libsystemd/sd-bus/bus-bloom.h diff --git a/src/libsystemd/meson.build b/src/libsystemd/meson.build index db5d4d0..94d165a 100644 --- a/src/libsystemd/meson.build +++ b/src/libsystemd/meson.build @@ -18,6 +18,8 @@ sd_login_c = files('sd-login/sd-login.c') libsystemd_sources = files(''' + sd-bus/bus-bloom.c + sd-bus/bus-bloom.h sd-bus/bus-common-errors.c sd-bus/bus-common-errors.h sd-bus/bus-container.c diff --git a/src/libsystemd/sd-bus/bus-bloom.c b/src/libsystemd/sd-bus/bus-bloom.c new file mode 100644 index 0000000..900c14f --- /dev/null +++ b/src/libsystemd/sd-bus/bus-bloom.c @@ -0,0 +1,158 @@ +/* SPDX-License-Identifier: LGPL-2.1+ */ +/*** + This file is part of systemd. + + Copyright 2013 Lennart Poettering + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include "bus-bloom.h" +#include "sd-id128.h" +#include "siphash24.h" +#include "util.h" + +static inline void set_bit(uint64_t filter[], unsigned long b) { + filter[b >> 6] |= 1ULL << (b & 63); +} + +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 */ + + uint64_t h; + uint64_t m; + unsigned w, i, c = 0; + unsigned hash_index; + + 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, hash_index = 0; i < k; i++) { + uint64_t p = 0; + unsigned d; + + for (d = 0; d < w; d++) { + if (c <= 0) { + h = siphash24(data, n, hash_keys[hash_index++].bytes); + c += 8; + } + + p = (p << 8ULL) | (uint64_t) ((uint8_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[], size_t size, unsigned k, const char *a, const char *b) { + size_t n; + char *c; + + assert(filter); + assert(a); + assert(b); + + n = strlen(a) + 1 + strlen(b); + c = alloca(n + 1); + strcpy(stpcpy(stpcpy(c, a), ":"), b); + + bloom_add_data(filter, size, k, c, n); +} + +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; + + assert(filter); + assert(a); + assert(b); + + n = strlen(a) + 1 + strlen(b); + c = alloca(n + 1); + + p = stpcpy(stpcpy(c, a), ":"); + strcpy(p, b); + + bloom_add_data(filter, size, k, c, n); + + for (;;) { + char *e; + + e = strrchr(p, sep); + if (!e) + break; + + *(e + 1) = 0; + bloom_add_data(filter, size, k, c, e - c + 1); + + if (e == p) + break; + + *e = 0; + 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 new file mode 100644 index 0000000..2650762 --- /dev/null +++ b/src/libsystemd/sd-bus/bus-bloom.h @@ -0,0 +1,44 @@ +/* SPDX-License-Identifier: LGPL-2.1+ */ +#pragma once + +/*** + This file is part of systemd. + + Copyright 2013 Lennart Poettering + + systemd is free software; you can redistribute it and/or modify it + under the terms of the GNU Lesser General Public License as published by + the Free Software Foundation; either version 2.1 of the License, or + (at your option) any later version. + + systemd is distributed in the hope that it will be useful, but + WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU + Lesser General Public License for more details. + + You should have received a copy of the GNU Lesser General Public License + along with systemd; If not, see . +***/ + +#include +#include +#include + +/* + * 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-kernel.c b/src/libsystemd/sd-bus/bus-control-kernel.c index 5508c58..b897f39 100644 --- a/src/libsystemd/sd-bus/bus-control-kernel.c +++ b/src/libsystemd/sd-bus/bus-control-kernel.c @@ -28,7 +28,7 @@ #include "sd-bus.h" #include "alloc-util.h" -//#include "bus-bloom.h" +#include "bus-bloom.h" #include "bus-control-kernel.h" #include "bus-internal.h" #include "bus-message.h" @@ -862,7 +862,7 @@ int bus_add_match_internal_kernel( if (c->value_u8 != SD_BUS_MESSAGE_SIGNAL) matches_name_change = false; -// bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "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; @@ -870,7 +870,7 @@ int bus_add_match_internal_kernel( if (!streq(c->value_str, "org.freedesktop.DBus")) matches_name_change = false; -// bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "interface", c->value_str); + bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "interface", c->value_str); using_bloom = true; break; @@ -878,7 +878,7 @@ int bus_add_match_internal_kernel( if (!streq(c->value_str, "NameOwnerChanged")) matches_name_change = false; -// bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "member", c->value_str); + bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "member", c->value_str); using_bloom = true; break; @@ -886,12 +886,12 @@ int bus_add_match_internal_kernel( if (!streq(c->value_str, "/org/freedesktop/DBus")) matches_name_change = false; - //bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "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: - //bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, "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; @@ -902,7 +902,7 @@ int bus_add_match_internal_kernel( name_change_arg[c->type - BUS_MATCH_ARG] = c->value_str; xsprintf(buf, "arg%i", c->type - BUS_MATCH_ARG); - //bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, buf, c->value_str); + bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, buf, c->value_str); using_bloom = true; break; } @@ -911,7 +911,7 @@ int bus_add_match_internal_kernel( char buf[sizeof("arg")-1 + 2 + sizeof("-has")]; xsprintf(buf, "arg%i-has", c->type - BUS_MATCH_ARG_HAS); - //bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, buf, c->value_str); + bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, buf, c->value_str); using_bloom = true; break; } @@ -935,7 +935,7 @@ int bus_add_match_internal_kernel( char buf[sizeof("arg")-1 + 2 + sizeof("-dot-prefix")]; xsprintf(buf, "arg%i-dot-prefix", c->type - BUS_MATCH_ARG_NAMESPACE); - //bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, buf, c->value_str); + bloom_add_pair(bloom, bus->bloom_size, bus->bloom_n_hash, buf, c->value_str); using_bloom = true; break; } diff --git a/src/libsystemd/sd-bus/bus-control.c b/src/libsystemd/sd-bus/bus-control.c index 6b50d7f..77592e83 100644 --- a/src/libsystemd/sd-bus/bus-control.c +++ b/src/libsystemd/sd-bus/bus-control.c @@ -28,6 +28,7 @@ #include "sd-bus.h" #include "alloc-util.h" +#include "bus-bloom.h" #include "bus-control.h" #include "bus-control-kernel.h" #include "bus-internal.h" diff --git a/src/libsystemd/sd-bus/bus-kernel.c b/src/libsystemd/sd-bus/bus-kernel.c index fd80b1c..a5d0d1c 100644 --- a/src/libsystemd/sd-bus/bus-kernel.c +++ b/src/libsystemd/sd-bus/bus-kernel.c @@ -34,6 +34,7 @@ #undef basename #include "alloc-util.h" +#include "bus-bloom.h" #include "bus-internal.h" #include "bus-kernel.h" #include "bus-label.h" @@ -165,12 +166,12 @@ static void add_bloom_arg(void *data, size_t size, unsigned n_hash, unsigned i, } *e = 0; - //bloom_add_pair(data, size, n_hash, buf, t); + bloom_add_pair(data, size, n_hash, buf, t); strcpy(e, "-dot-prefix"); - //bloom_add_prefixes(data, size, n_hash, buf, t, '.'); + bloom_add_prefixes(data, size, n_hash, buf, t, '.'); strcpy(e, "-slash-prefix"); - //bloom_add_prefixes(data, size, n_hash, buf, t, '/'); + bloom_add_prefixes(data, size, n_hash, buf, t, '/'); } static void add_bloom_arg_has(void *data, size_t size, unsigned n_hash, unsigned i, const char *t) { @@ -191,7 +192,7 @@ static void add_bloom_arg_has(void *data, size_t size, unsigned n_hash, unsigned } strcpy(e, "-has"); - //bloom_add_pair(data, size, n_hash, buf, t); + bloom_add_pair(data, size, n_hash, buf, t); } static int bus_message_setup_bloom(sd_bus_message *m, struct kdbus_bloom_filter *bloom) { @@ -206,17 +207,17 @@ static int bus_message_setup_bloom(sd_bus_message *m, struct kdbus_bloom_filter memzero(data, m->bus->bloom_size); bloom->generation = 0; - //bloom_add_pair(data, m->bus->bloom_size, m->bus->bloom_n_hash, "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, m->bus->bloom_size, m->bus->bloom_n_hash, "interface", m->interface); - //if (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, 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, '/'); - //} + if (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, m->bus->bloom_size, m->bus->bloom_n_hash, "member", m->member); + if (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); if (r < 0) @@ -1027,10 +1028,10 @@ int bus_kernel_take_fd(sd_bus *b) { } } - //if (!bloom || !bloom_validate_parameters((size_t) bloom->size, (unsigned) bloom->n_hash)) { - //r = -EOPNOTSUPP; - //goto fail; - //} + if (!bloom || !bloom_validate_parameters((size_t) bloom->size, (unsigned) bloom->n_hash)) { + r = -EOPNOTSUPP; + goto fail; + } b->bloom_size = (size_t) bloom->size; b->bloom_n_hash = (unsigned) bloom->n_hash; @@ -1566,11 +1567,11 @@ 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 = DEFAULT_BLOOM_SIZE; - //n->bloom_parameter.n_hash = DEFAULT_BLOOM_N_HASH; + 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); + assert_cc(DEFAULT_BLOOM_SIZE > 0); + assert_cc(DEFAULT_BLOOM_N_HASH > 0); make->size += ALIGN8(n->size); -- 2.7.4