[systemd-devel] [PATCH] bus-bloom: Fix bloom filter calculation

Denis Kenzior denkenz at gmail.com
Sat Aug 9 00:06:21 PDT 2014


i is being used incorrectly.  It is used to refer to the number of
indexes calculated so far (out of k).  However, it is also incremented
when a new hash key is being used.  This means that the results are
inconsistent with the desired behavior described in PORTING-DBUS1
document.

The expected result is that for the default values of m and k (512, 8)
the 1st hash key should produce 4 indexes.  The second hash key is used
for the next 4 and overall 8 indexes into m are calculated.

The current behavior results in 6 indexes being calculated, 4 coming
from hash key 1 and 2 others from hash key 5.
---
 src/libsystemd/sd-bus/bus-bloom.c | 5 +++--
 1 file changed, 3 insertions(+), 2 deletions(-)

diff --git a/src/libsystemd/sd-bus/bus-bloom.c b/src/libsystemd/sd-bus/bus-bloom.c
index e154296..3556774 100644
--- a/src/libsystemd/sd-bus/bus-bloom.c
+++ b/src/libsystemd/sd-bus/bus-bloom.c
@@ -48,6 +48,7 @@ static void bloom_add_data(
         uint8_t h[8];
         uint64_t m;
         unsigned w, i, c = 0;
+        unsigned hash_index;
 
         assert(size > 0);
         assert(k > 0);
@@ -65,13 +66,13 @@ static void bloom_add_data(
          * hash value for each 128 bits of hash key. */
         assert(k * w <= ELEMENTSOF(hash_keys) * 8);
 
-        for (i = 0; i < k; i++) {
+        for (i = 0, hash_index = 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);
+                                siphash24(h, data, n, hash_keys[hash_index++].bytes);
                                 c += 8;
                         }
 
-- 
1.8.5.5



More information about the systemd-devel mailing list