[gnunet] 69/164: Pack IBF counter to use only as much storage as needed

[gnunet]

This is an automated email from the git hooks/post-receive script.

grothoff pushed a commit to branch master
in repository gnunet.

commit 5729ab1b2ac498e40e780d137325716b95819148
Author: Elias Summermatter <elias.summermatter@seccom.ch>
AuthorDate: Mon Apr 26 17:55:38 2021 +0200

    Pack IBF counter to use only as much storage as needed
---
 src/setu/gnunet-service-setu.c                  |  11 +--
 src/setu/gnunet-service-setu_protocol.h         |   5 ++
 src/setu/gnunet-service-setu_strata_estimator.c |   5 +-
 src/setu/ibf.c                                  | 113 +++++++++++++++++++++---
 src/setu/ibf.h                                  |  15 ++--
 src/setu/perf_setu_api.c                        |   2 +-
 src/setu/test_setu_api.c                        |   4 +-
 7 files changed, 129 insertions(+), 26 deletions(-)

diff --git a/src/setu/gnunet-service-setu.c b/src/setu/gnunet-service-setu.c
index 69086a504..60d8095a4 100644
--- a/src/setu/gnunet-service-setu.c
+++ b/src/setu/gnunet-service-setu.c
@@ -326,7 +326,7 @@ struct Operation
   /**
    * Number of ibf buckets already received into the @a remote_ibf.
    */
-  unsigned int ibf_buckets_received;
+  uint64_t ibf_buckets_received;
 
   /**
    * Salt that we're using for sending IBFs
@@ -1411,7 +1411,7 @@ static int
 send_ibf (struct Operation *op,
           uint32_t ibf_size)
 {
-  unsigned int buckets_sent = 0;
+  uint64_t buckets_sent = 0;
   struct InvertibleBloomFilter *ibf;
 
     /**
@@ -1460,8 +1460,9 @@ send_ibf (struct Operation *op,
     msg->ibf_size = ibf_size;
     msg->offset = htonl (buckets_sent);
     msg->salt = htonl (op->salt_send);
+    msg->ibf_counter_bit_length = ibf_get_max_counter(ibf);
     ibf_write_slice (ibf, buckets_sent,
-                     buckets_in_message, &msg[1]);
+                     buckets_in_message, &msg[1], msg->ibf_counter_bit_length);
     buckets_sent += buckets_in_message;
     LOG (GNUNET_ERROR_TYPE_DEBUG,
          "ibf chunk size %u, %u/%u sent\n",
@@ -2118,7 +2119,7 @@ handle_union_p2p_ibf (void *cls,
   ibf_read_slice (&msg[1],
                   op->ibf_buckets_received,
                   buckets_in_message,
-                  op->remote_ibf);
+                  op->remote_ibf, msg->ibf_counter_bit_length);
   op->ibf_buckets_received += buckets_in_message;
 
   if (op->ibf_buckets_received == op->remote_ibf->size)
@@ -3928,7 +3929,7 @@ handle_client_accept (void *cls,
     perf_rtt.se.sent += 1;
     perf_rtt.se.sent_var_bytes += len;
 
-      if (len < se->strata_count * IBF_BUCKET_SIZE * se->ibf_size)
+    if (len < se->strata_count * IBF_BUCKET_SIZE * se->ibf_size)
       type = GNUNET_MESSAGE_TYPE_SETU_P2P_SEC;
     else
       type = GNUNET_MESSAGE_TYPE_SETU_P2P_SE;
diff --git a/src/setu/gnunet-service-setu_protocol.h 
b/src/setu/gnunet-service-setu_protocol.h
index 97065441d..418fa7c7e 100644
--- a/src/setu/gnunet-service-setu_protocol.h
+++ b/src/setu/gnunet-service-setu_protocol.h
@@ -76,6 +76,11 @@ struct IBFMessage
    */
   uint32_t ibf_size;
 
+  /**
+  * The bit lenght of the counter
+   */
+  uint8_t ibf_counter_bit_length;
+
   /**
    * Offset of the strata in the rest of the message
    */
diff --git a/src/setu/gnunet-service-setu_strata_estimator.c 
b/src/setu/gnunet-service-setu_strata_estimator.c
index fe7590433..0d7e40396 100644
--- a/src/setu/gnunet-service-setu_strata_estimator.c
+++ b/src/setu/gnunet-service-setu_strata_estimator.c
@@ -49,7 +49,8 @@ strata_estimator_write (const struct StrataEstimator *se,
     ibf_write_slice (se->strata[i],
                      0,
                      se->ibf_size,
-                     &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i]);
+                     &sbuf[se->ibf_size * IBF_BUCKET_SIZE * i],
+                     8);
   }
   osize = se->ibf_size * IBF_BUCKET_SIZE * se->strata_count;
   {
@@ -117,7 +118,7 @@ strata_estimator_read (const void *buf,
 
   for (unsigned int i = 0; i < se->strata_count; i++)
   {
-    ibf_read_slice (buf, 0, se->ibf_size, se->strata[i]);
+    ibf_read_slice (buf, 0, se->ibf_size, se->strata[i], 8);
     buf += se->ibf_size * IBF_BUCKET_SIZE;
   }
   GNUNET_free (dbuf);
diff --git a/src/setu/ibf.c b/src/setu/ibf.c
index 2f436eff1..27d053cd1 100644
--- a/src/setu/ibf.c
+++ b/src/setu/ibf.c
@@ -85,7 +85,7 @@ ibf_create (uint32_t size,
 
   GNUNET_assert (0 != size);
   ibf = GNUNET_new (struct InvertibleBloomFilter);
-  ibf->count = GNUNET_malloc_large (size * sizeof(uint8_t));
+  ibf->count = GNUNET_malloc_large (size * sizeof(uint64_t));
   if (NULL == ibf->count)
   {
     GNUNET_free (ibf);
@@ -298,6 +298,23 @@ ibf_decode (struct InvertibleBloomFilter *ibf,
   return GNUNET_SYSERR;
 }
 
+/**
+ * Returns the minimal bytes needed to store the counter of the IBF
+ *
+ * @param ibf the IBF
+ */
+uint8_t
+ibf_get_max_counter (struct InvertibleBloomFilter *ibf)
+    {
+    uint64_t max_counter=8;
+    for (uint64_t i = 0; i < ibf->size; i++) {
+        if(ibf->count[i].count_val > max_counter){
+            max_counter=ibf->count[i].count_val;
+        }
+    }
+        return floor(log2(max_counter)) + 1;
+
+}
 
 /**
  * Write buckets from an ibf to a buffer.
@@ -307,6 +324,7 @@ ibf_decode (struct InvertibleBloomFilter *ibf,
  * @param start with which bucket to start
  * @param count how many buckets to write
  * @param buf buffer to write the data to
+ * @param max bit length of a counter for unpacking
  */
 void
 ibf_write_slice (const struct InvertibleBloomFilter *ibf,
@@ -332,13 +350,85 @@ ibf_write_slice (const struct InvertibleBloomFilter *ibf,
                  ibf->key_hash_sum + start,
                  count * sizeof *key_hash_dst);
   key_hash_dst += count;
-  /* copy counts */
-  count_dst = (struct IBF_Count *) key_hash_dst;
+
+  /* pack and copy counter */
+  size_t buf_size = ceil((float ) count/(8/(float)counter_max_length));
+  uint64_t *new_buf;
+  new_buf = (uint64_t*) GNUNET_malloc(buf_size);
+  pack_counter(ibf,start,count,new_buf,counter_max_length);
+  count_dst = (uint64_t *) key_hash_dst;
   GNUNET_memcpy (count_dst,
-                 ibf->count + start,
-                 count * sizeof *count_dst);
+                   new_buf,
+                   buf_size);
+
+}
+
+/**
+ *  Packs the counter to transmit only the smallest possible amount of bytes 
and
+ *  preventing overflow of the counter
+ * @param ibf the ibf to write
+ * @param start with which bucket to start
+ * @param count how many buckets to write
+ * @param buf buffer to write the data to
+ * @param max bit length of a counter for unpacking
+ */
+
+void
+pack_counter(const struct InvertibleBloomFilter *ibf,
+             uint32_t start,
+             uint64_t count,
+             uint64_t *buf,
+             uint8_t counter_max_length)
+{
+    uint64_t buf_position=0;
+    for (uint32_t i = start; i< (count + start);){
+        uint64_t byteToWrite = 0x0;
+        uint32_t bytes_to_shift = ((sizeof(uint64_t) * 8)/ counter_max_length);
+
+        for (uint32_t l = 0; l < bytes_to_shift; l++) {
+            if(i>=count) {
+                byteToWrite = byteToWrite << (counter_max_length * 
(bytes_to_shift - l));
+                break;
+            }
+            byteToWrite = (byteToWrite << counter_max_length) | 
ibf->count[i].count_val;
+            i++;
+        }
+        buf[buf_position] = byteToWrite;
+        buf_position++;
+    }
 }
 
+/**
+ *  Unpacks the counter to transmit only the smallest possible amount of bytes 
and
+ *  preventing overflow of the counter
+ * @param ibf the ibf to write
+ * @param start with which bucket to start
+ * @param count how many buckets to write
+ * @param buf buffer to write the data to
+ * @param max bit length of a counter for unpacking
+ */
+
+void
+unpack_counter(const struct InvertibleBloomFilter *ibf,
+               uint32_t start,
+               uint64_t count,
+               uint64_t *buf,
+               uint8_t counter_max_length)
+{
+    uint32_t element_counter=0;
+    for (uint32_t i = 0; i < ceil((float ) 
count/(64/(float)counter_max_length)); i++){
+        for(uint32_t l = (64/counter_max_length); l > 0; l-- ) {
+            uint64_t value = 0;
+            value = (buf[i] >> (counter_max_length * (l -1))) & ((uint64_t) 
pow(2,counter_max_length) - 1 );
+
+            if(element_counter>(ibf->size -1 )) return;
+
+            ibf->count[element_counter].count_val = value;
+            element_counter++;
+        }
+    }
+
+}
 
 /**
  * Read buckets from a buffer into an ibf.
@@ -347,12 +437,14 @@ ibf_write_slice (const struct InvertibleBloomFilter *ibf,
  * @param start which bucket to start at
  * @param count how many buckets to read
  * @param ibf the ibf to read from
+ * @param max bit length of a counter for unpacking
  */
 void
 ibf_read_slice (const void *buf,
                 uint32_t start,
-                uint32_t count,
-                struct InvertibleBloomFilter *ibf)
+                uint64_t count,
+                struct InvertibleBloomFilter *ibf,
+                uint8_t counter_max_length)
 {
   struct IBF_Key *key_src;
   struct IBF_KeyHash *key_hash_src;
@@ -373,11 +465,10 @@ ibf_read_slice (const void *buf,
                  key_hash_src,
                  count * sizeof *key_hash_src);
   key_hash_src += count;
-  /* copy counts */
+
+  /* copy and unpack counts  */
   count_src = (struct IBF_Count *) key_hash_src;
-  GNUNET_memcpy (ibf->count + start,
-                 count_src,
-                 count * sizeof *count_src);
+  unpack_counter(ibf,start,count,count_src,counter_max_length);
 }
 
 
diff --git a/src/setu/ibf.h b/src/setu/ibf.h
index 1969c4d84..fcf52f7eb 100644
--- a/src/setu/ibf.h
+++ b/src/setu/ibf.h
@@ -62,7 +62,7 @@ struct IBF_KeyHash
  */
 struct IBF_Count
 {
-  int8_t count_val;
+  int64_t count_val;
 };
 
 
@@ -139,8 +139,9 @@ struct InvertibleBloomFilter
 void
 ibf_write_slice (const struct InvertibleBloomFilter *ibf,
                  uint32_t start,
-                 uint32_t count,
-                 void *buf);
+                 uint64_t count,
+                 void *buf,
+                 uint8_t counter_max_length);
 
 
 /**
@@ -154,8 +155,9 @@ ibf_write_slice (const struct InvertibleBloomFilter *ibf,
 void
 ibf_read_slice (const void *buf,
                 uint32_t start,
-                uint32_t count,
-                struct InvertibleBloomFilter *ibf);
+                uint64_t count,
+                struct InvertibleBloomFilter *ibf,
+                uint8_t counter_max_length);
 
 
 /**
@@ -258,6 +260,9 @@ ibf_dup (const struct InvertibleBloomFilter *ibf);
 void
 ibf_destroy (struct InvertibleBloomFilter *ibf);
 
+uint8_t
+ibf_get_max_counter(struct InvertibleBloomFilter *ibf);
+
 
 #if 0                           /* keep Emacsens' auto-indent happy */
 {
diff --git a/src/setu/perf_setu_api.c b/src/setu/perf_setu_api.c
index 93ed18e0f..fea836765 100644
--- a/src/setu/perf_setu_api.c
+++ b/src/setu/perf_setu_api.c
@@ -404,7 +404,7 @@ run (void *cls,
                 "Running real set-reconciliation\n");
     //init_set1 ();
     // limit ~23800 element total
-    initRandomSets(0,4500,5000,32);
+    initRandomSets(0,45,50,32);
 }
 
 void perf_thread() {
diff --git a/src/setu/test_setu_api.c b/src/setu/test_setu_api.c
index 2fb7d015e..bee12da97 100644
--- a/src/setu/test_setu_api.c
+++ b/src/setu/test_setu_api.c
@@ -392,8 +392,8 @@ run (void *cls,
   /* test the real set reconciliation */
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
               "Running real set-reconciliation\n");
-  //init_set1 ();
-  initRandomSets(19500,20000,20000,4096);
+  init_set1 ();
+  //initRandomSets(19500,20000,20000,4096);
   //initRandomSets(19500,20000,20000,32);
 }
 

-- 
To stop receiving notification emails like this one, please contact
gnunet@gnunet.org.