[GNUnet-SVN] r30830 - gnunet/src/set

[gnunet]

Author: cfuchs
Date: 2013-11-20 17:20:26 +0100 (Wed, 20 Nov 2013)
New Revision: 30830

Modified:
   gnunet/src/set/Makefile.am
   gnunet/src/set/gnunet-service-set.c
   gnunet/src/set/gnunet-service-set.h
   gnunet/src/set/gnunet-service-set_intersection.c
Log:
added intersection to set's automake script
renamed shared variable in set-service's common structure
reordered code in intersection
i assume: finished reworking intersection, still misses dynamic bloomfilter size
re-added struct SetState to intersection, which keeps track of the newest (and 
only this!) element count in the set's hashmap.
removed iterator over the set for counting (see line above)
a bugfix here and there



Modified: gnunet/src/set/Makefile.am
===================================================================
--- gnunet/src/set/Makefile.am  2013-11-20 15:39:58 UTC (rev 30829)
+++ gnunet/src/set/Makefile.am  2013-11-20 16:20:26 UTC (rev 30830)
@@ -45,12 +45,14 @@
 gnunet_service_set_SOURCES = \
  gnunet-service-set.c \
  gnunet-service-set_union.c \
+ gnunet-service-set_intersection.c \
  ibf.c \
  strata_estimator.c
 gnunet_service_set_LDADD = \
   $(top_builddir)/src/util/libgnunetutil.la \
   $(top_builddir)/src/core/libgnunetcore.la \
   $(top_builddir)/src/mesh/libgnunetmesh.la \
+  $(top_builddir)/src/block/libgnunetblock.la \
   $(GN_LIBINTL)
 
 libgnunetset_la_SOURCES = \

Modified: gnunet/src/set/gnunet-service-set.c
===================================================================
--- gnunet/src/set/gnunet-service-set.c 2013-11-20 15:39:58 UTC (rev 30829)
+++ gnunet/src/set/gnunet-service-set.c 2013-11-20 16:20:26 UTC (rev 30830)
@@ -567,7 +567,7 @@
   spec->app_id = msg->app_id;
   spec->salt = ntohl (msg->salt);
   spec->peer = op->state->peer;
-  spec->element_count = ntohl (msg->element_count);
+  spec->remote_element_count = ntohl (msg->element_count);
 
   op->spec = spec;
 

Modified: gnunet/src/set/gnunet-service-set.h
===================================================================
--- gnunet/src/set/gnunet-service-set.h 2013-11-20 15:39:58 UTC (rev 30829)
+++ gnunet/src/set/gnunet-service-set.h 2013-11-20 16:20:26 UTC (rev 30830)
@@ -93,7 +93,7 @@
   /**
    * Remote peers element count
    */
-  uint32_t element_count;
+  uint32_t remote_element_count;
 
   /**
    * ID used to identify an operation between service and client 

Modified: gnunet/src/set/gnunet-service-set_intersection.c
===================================================================
--- gnunet/src/set/gnunet-service-set_intersection.c    2013-11-20 15:39:58 UTC 
(rev 30829)
+++ gnunet/src/set/gnunet-service-set_intersection.c    2013-11-20 16:20:26 UTC 
(rev 30830)
@@ -26,7 +26,7 @@
 #include "platform.h"
 #include "gnunet_util_lib.h"
 #include "gnunet-service-set.h"
-#include "strata_estimator.h"
+#include "gnunet_block_lib.h"
 #include "set_protocol.h"
 #include <gcrypt.h>
 
@@ -96,12 +96,12 @@
   /**
    * Current element count contained within contained_elements
    */
-  uint32_t my_elements_count;
+  uint32_t my_element_count;
 
   /**
    * Iterator for sending elements on the key to element mapping to the client.
    */
-  struct GNUNET_CONTAINER_MultiHashMap32Iterator *full_result_iter;
+  struct GNUNET_CONTAINER_MultiHashMapIterator *full_result_iter;
   
   /**
    * Evaluate operations are held in
@@ -123,6 +123,18 @@
 
 
 /**
+ * Extra state required for efficient set intersection.
+ */
+struct SetState
+{
+  /**
+   * Number of currently valid elements in the set which have not been removed
+   */
+  uint32_t current_set_element_count;
+};
+
+
+/**
  * Alice's version:
  * 
  * fills the contained-elements hashmap with all relevant 
@@ -154,7 +166,7 @@
                                                       &mutated_hash))
     return GNUNET_YES;
   
-  op->state->my_elements_count++;  
+  op->state->my_element_count++;  
   GNUNET_CONTAINER_multihashmap_put (op->state->my_elements, 
                                      &ee->element_hash, ee,
                                      
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
@@ -203,33 +215,6 @@
   return GNUNET_YES;
 }
 
-/**
- * Counts all valid elements in the hashmap 
- * (the ones that are valid in our generation)
- * 
- * @param cls closure
- * @param key current key code
- * @param value value in the hash map
- * @return #GNUNET_YES if we should continue to
- *         iterate,
- *         #GNUNET_NO if not.
- */
-static int 
-iterator_element_count (void *cls,
-                                      const struct GNUNET_HashCode *key,
-                                      void *value){
-  struct ElementEntry *ee = value;
-  struct Operation *op = cls;
-  
-  //only consider this element, if it is valid for us
-  if ((op->generation_created >= ee->generation_removed) 
-       || (op->generation_created < ee->generation_added))
-    return GNUNET_YES;
-  
-  op->state->my_elements_count++;
-  
-  return GNUNET_YES;
-}
 
 /**
  * removes element from a hashmap if it is not contained within the
@@ -254,7 +239,7 @@
   
   if (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf, 
                                      &mutated_hash)){
-    op->state->my_elements_count--;
+    op->state->my_element_count--;
     GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements, 
                                      &ee->element_hash,
                                      ee);
@@ -295,27 +280,7 @@
 }
 
 
-
 /**
- * Inform the peer that this operation is complete.
- *
- * @param eo the intersection operation to fail
- */
-static void
-send_peer_done (struct Operation *op)
-{
-  struct GNUNET_MQ_Envelope *ev;
-
-  op->state->phase = PHASE_FINISHED;
-  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Intersection succeeded, sending 
DONE\n");
-  GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
-  op->state->local_bf = NULL;
-
-  ev = GNUNET_MQ_msg_header (GNUNET_MESSAGE_TYPE_SET_P2P_DONE);
-  GNUNET_MQ_send (op->mq, ev);
-}
-
-/**
  * Send a request for the evaluate operation to a remote peer
  *
  * @param eo operation with the other peer
@@ -339,7 +304,7 @@
   msg->operation = htonl (GNUNET_SET_OPERATION_INTERSECTION);
   msg->app_id = op->spec->app_id;
   msg->salt = htonl (op->spec->salt);
-  msg->element_count = htonl(op->state->my_elements);
+  msg->element_count = htonl(op->state->my_element_count);
   
   GNUNET_MQ_send (op->mq, ev);
 
@@ -357,6 +322,121 @@
 }
 
 /**
+ * Send a bloomfilter to our peer.
+ * that the operation is over.
+ * After the result done message has been sent to the client,
+ * destroy the evaluate operation.
+ *
+ * @param eo intersection operation
+ */
+static void
+send_bloomfilter (struct Operation *op)
+{
+  struct GNUNET_MQ_Envelope *ev;
+  struct BFMessage *msg;
+  uint32_t bf_size;
+
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending bf of size %u\n");
+
+  // send our bloomfilter
+  bf_size = GNUNET_CONTAINER_bloomfilter_get_size (op->state->local_bf);
+
+  ev = GNUNET_MQ_msg_extra (msg, bf_size, 
GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
+  msg->reserved = 0;
+  msg->sender_element_count = htonl (op->state->my_element_count);
+  msg->bloomfilter_length = htonl (bf_size);
+  msg->sender_mutator = htonl (op->spec->salt);
+  GNUNET_assert (GNUNET_SYSERR !=
+                 GNUNET_CONTAINER_bloomfilter_get_raw_data 
(op->state->local_bf,
+                                                            (char *) &msg[1],
+                                                            bf_size));
+  GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
+  op->state->local_bf = NULL;
+  GNUNET_MQ_send (op->mq, ev);
+}
+
+
+/**
+ * Signal to the client that the operation has finished and
+ * destroy the operation.
+ *
+ * @param cls operation to destroy
+ */
+static void
+send_client_done_and_destroy (void *cls)
+{
+  struct Operation *op = cls;
+  struct GNUNET_MQ_Envelope *ev;
+  struct GNUNET_SET_ResultMessage *rm;
+  ev = GNUNET_MQ_msg (rm, GNUNET_MESSAGE_TYPE_SET_RESULT);
+  rm->request_id = htonl (op->spec->client_request_id);
+  rm->result_status = htons (GNUNET_SET_STATUS_DONE);
+  rm->element_type = htons (0);
+  GNUNET_MQ_send (op->spec->set->client_mq, ev);
+  _GSS_operation_destroy (op);
+}
+
+
+/**
+ * Send all elements in the full result iterator.
+ *
+ * @param cls operation
+ */
+static void
+send_remaining_elements (void *cls)
+{
+  struct Operation *op = cls;
+  struct ElementEntry *remaining; //TODO rework this, key entry does not exist 
here
+  struct GNUNET_MQ_Envelope *ev;
+  struct GNUNET_SET_ResultMessage *rm;
+  struct GNUNET_SET_Element *element;
+  int res;
+
+  res = GNUNET_CONTAINER_multihashmap_iterator_next 
(op->state->full_result_iter, NULL, (const void **) &remaining);
+  if (GNUNET_NO == res) {
+    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending done and destroy because 
iterator ran out\n");
+    send_client_done_and_destroy (op);
+    return;
+  }
+  
+  element = &remaining->element;
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending element (size %u) to client 
(full set)\n", element->size);
+  GNUNET_assert (0 != op->spec->client_request_id);
+  
+  ev = GNUNET_MQ_msg_extra (rm, element->size, GNUNET_MESSAGE_TYPE_SET_RESULT);
+  GNUNET_assert (NULL != ev);
+  
+  rm->result_status = htons (GNUNET_SET_STATUS_OK);
+  rm->request_id = htonl (op->spec->client_request_id);
+  rm->element_type = element->type;
+  memcpy (&rm[1], element->data, element->size);
+
+  GNUNET_MQ_notify_sent (ev, send_remaining_elements, op);
+  GNUNET_MQ_send (op->spec->set->client_mq, ev);
+}
+
+
+/**
+ * Inform the peer that this operation is complete.
+ *
+ * @param eo the intersection operation to fail
+ */
+static void
+send_peer_done (struct Operation *op)
+{
+  struct GNUNET_MQ_Envelope *ev;
+
+  op->state->phase = PHASE_FINISHED;
+  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Intersection succeeded, sending 
DONE\n");
+  GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
+  op->state->local_bf = NULL;
+
+  ev = GNUNET_MQ_msg_header (GNUNET_MESSAGE_TYPE_SET_P2P_DONE);
+  GNUNET_MQ_send (op->mq, ev);
+}
+
+
+/**
  * Handle an BF message from a remote peer.
  *
  * @param cls the intersection operation
@@ -366,13 +446,14 @@
 handle_p2p_bf (void *cls, const struct GNUNET_MessageHeader *mh)
 {
   struct Operation *op = cls;
-  struct BFMessage *msg = (struct BFMessage *) mh;
-  uint32_t old_count;
+  const struct BFMessage *msg = (const struct BFMessage *) mh;
+  uint32_t old_elements;
+  uint32_t peer_elements;
 
-  old_count = op->state->my_elements_count;
+  old_elements = op->state->my_element_count;
   op->spec->salt = ntohl (msg->sender_mutator);
   
-  op->state->remote_bf = GNUNET_CONTAINER_bloomfilter_init (&msg[1],
+  op->state->remote_bf = GNUNET_CONTAINER_bloomfilter_init ((const char*) 
&msg[1],
                                                             BLOOMFILTER_SIZE,
                                                             ntohl 
(msg->bloomfilter_length));
   op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL,
@@ -382,7 +463,7 @@
   {
   case PHASE_INITIAL:
     // If we are ot our first msg
-    op->state->my_elements = GNUNET_CONTAINER_multihashmap_create 
(op->state->my_elements_count, GNUNET_YES);
+    op->state->my_elements = GNUNET_CONTAINER_multihashmap_create 
(op->state->my_element_count, GNUNET_YES);
 
     GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements,
                                            &iterator_initialization_by_alice,
@@ -407,8 +488,10 @@
   GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf);
   op->state->remote_bf = NULL;
   
+  peer_elements = ntohl(msg->sender_element_count);
   if ((op->state->phase == PHASE_MAYBE_FINISHED) 
-       && (old_count == op->state->my_elements_count)){
+       && (old_elements == op->state->my_element_count)
+       && (op->state->my_element_count == peer_elements)){
     // In the last round we though we were finished, we now know this is 
correct
     send_peer_done(op);
     return;
@@ -417,7 +500,7 @@
   op->state->phase = PHASE_BF_EXCHANGE;
   // maybe we are finished, but we do one more round to make certain
   // we don't have false positives ...
-  if (op->state->my_elements_count == ntohl (msg->sender_element_count))
+  if (op->state->my_element_count == peer_elements)
       op->state->phase = PHASE_MAYBE_FINISHED;
 
   send_bloomfilter (op);
@@ -435,11 +518,10 @@
 {
   struct Operation *op = cls;
   struct BFMessage *msg = (struct BFMessage *) mh;
-  uint32_t remote_element_count;
 
-  remote_element_count = ntohl(msg->sender_element_count);
-  if ((op->state->phase == PHASE_INITIAL)
-      || (op->state->my_elements_count > remote_element_count)){
+  op->spec->remote_element_count = ntohl(msg->sender_element_count);
+  if ((op->state->phase != PHASE_INITIAL)
+      || (op->state->my_element_count > op->spec->remote_element_count)){
     GNUNET_break_op (0);
     fail_intersection_operation(op);
   }
@@ -457,7 +539,7 @@
   GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf);
   op->state->remote_bf = NULL;
 
-  if (op->state->my_elements_count == ntohl (msg->sender_element_count))
+  if (op->state->my_element_count == ntohl (msg->sender_element_count))
     op->state->phase = PHASE_MAYBE_FINISHED;
 
   send_bloomfilter (op);
@@ -465,40 +547,6 @@
 
 
 /**
- * Send a bloomfilter to our peer.
- * that the operation is over.
- * After the result done message has been sent to the client,
- * destroy the evaluate operation.
- *
- * @param eo intersection operation
- */
-static void
-send_bloomfilter (struct Operation *op)
-{
-  struct GNUNET_MQ_Envelope *ev;
-  struct BFMessage *msg;
-  uint32_t bf_size;
-
-  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending bf of size %u\n",);
-
-  // send our bloomfilter
-  bf_size = GNUNET_CONTAINER_bloomfilter_get_size (op->state->local_bf);
-
-  ev = GNUNET_MQ_msg_extra (msg, bf_size, 
GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
-  msg->reserved = 0;
-  msg->sender_element_count = htonl (op->state->my_elements_count);
-  msg->bloomfilter_length = htonl (bf_size);
-  msg->sender_mutator = htonl (op->spec->salt);
-  GNUNET_assert (GNUNET_SYSERR !=
-                 GNUNET_CONTAINER_bloomfilter_get_raw_data 
(op->state->local_bf,
-                                                            
&msg->sender_bf_data,
-                                                            BLOOMFILTER_SIZE));
-  GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
-  op->state->local_bf = NULL;
-  GNUNET_MQ_send (op->mq, ev);
-}
-
-/**
  * Send our element to the peer, in case our element count is lower than his
  *
  * @param eo intersection operation
@@ -514,7 +562,7 @@
   // just send our element count, as the other peer must start
   ev = GNUNET_MQ_msg (msg, 
GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO);
   msg->reserved = 0;
-  msg->sender_element_count = htonl (op->state->my_elements_count);
+  msg->sender_element_count = htonl (op->state->my_element_count);
   msg->bloomfilter_length = htonl (0);
   msg->sender_mutator = htonl (0);
 
@@ -538,7 +586,7 @@
   {
     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending full result set\n");
     op->state->full_result_iter =
-        GNUNET_CONTAINER_multihashmap32_iterator_create 
(op->state->my_elements);
+        GNUNET_CONTAINER_multihashmap_iterator_create (op->state->my_elements);
     send_remaining_elements (op);
     return;
   }
@@ -555,7 +603,6 @@
 handle_p2p_done (void *cls, const struct GNUNET_MessageHeader *mh)
 {
   struct Operation *op = cls;
-  struct GNUNET_MQ_Envelope *ev;
 
   if ((op->state->phase = PHASE_FINISHED) || (op->state->phase = 
PHASE_MAYBE_FINISHED)){
     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "got final DONE\n");
@@ -582,9 +629,7 @@
   /* we started the operation, thus we have to send the operation request */
   op->state->phase = PHASE_INITIAL;
   op->state->my_elements = GNUNET_CONTAINER_multihashmap_create(1, GNUNET_YES);
-  GNUNET_CONTAINER_multihashmap_iterate(op->spec->set->elements, 
-                                        &iterator_element_count,
-                                        op);
+  op->state->my_element_count = 
op->spec->set->state->current_set_element_count;
   
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "evaluating intersection operation");
   send_operation_request (op);
@@ -602,11 +647,10 @@
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "accepting set union operation\n");
   op->state = GNUNET_new (struct OperationState);
   op->state->my_elements = GNUNET_CONTAINER_multihashmap_create(1, GNUNET_YES);
-  GNUNET_CONTAINER_multihashmap_iterate(op->spec->set->elements, 
-                                        &iterator_element_count,
-                                        op);
+  op->state->my_element_count = 
op->spec->set->state->current_set_element_count;
+  
   // if Alice (the peer) has more elements than Bob (us), she should start
-  if (op->spec->element_count < op->state->my_elements_count){
+  if (op->spec->remote_element_count < op->state->my_element_count){
     op->state->phase = PHASE_INITIAL;
     send_element_count(op);
     return;
@@ -636,6 +680,7 @@
   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "intersection set created\n");
 
   set_state = GNUNET_new (struct SetState);
+  set_state->current_set_element_count = 0;
   
   return set_state;
 }
@@ -650,7 +695,8 @@
 static void
 intersection_add (struct SetState *set_state, struct ElementEntry *ee)
 {
-  //nothing to do here
+  GNUNET_assert(0 < set_state->current_set_element_count);
+  set_state->current_set_element_count++;
 }
 
 
@@ -675,6 +721,8 @@
 static void
 intersection_remove (struct SetState *set_state, struct ElementEntry *element)
 {
+  GNUNET_assert(0 < set_state->current_set_element_count);
+  set_state->current_set_element_count--;
   //nothing to do here
 }
 
@@ -714,63 +762,7 @@
   return GNUNET_OK;
 }
 
-/**
- * Signal to the client that the operation has finished and
- * destroy the operation.
- *
- * @param cls operation to destroy
- */
-static void
-send_client_done_and_destroy (void *cls)
-{
-  struct Operation *op = cls;
-  struct GNUNET_MQ_Envelope *ev;
-  struct GNUNET_SET_ResultMessage *rm;
-  ev = GNUNET_MQ_msg (rm, GNUNET_MESSAGE_TYPE_SET_RESULT);
-  rm->request_id = htonl (op->spec->client_request_id);
-  rm->result_status = htons (GNUNET_SET_STATUS_DONE);
-  rm->element_type = htons (0);
-  GNUNET_MQ_send (op->spec->set->client_mq, ev);
-  _GSS_operation_destroy (op);
-}
-/**
- * Send all elements in the full result iterator.
- *
- * @param cls operation
- */
-static void
-send_remaining_elements (void *cls)
-{
-  struct Operation *op = cls;
-  struct ElementEntry *remaining; //TODO rework this, key entry does not exist 
here
-  struct GNUNET_MQ_Envelope *ev;
-  struct GNUNET_SET_ResultMessage *rm;
-  struct GNUNET_SET_Element *element;
-  int res;
 
-  res = GNUNET_CONTAINER_multihashmap32_iterator_next 
(op->state->full_result_iter, NULL, (const void **) &remaining);
-  if (GNUNET_NO == res) {
-    GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending done and destroy because 
iterator ran out\n");
-    send_client_done_and_destroy (op);
-    return;
-  }
-  
-  element = &remaining->element;
-  GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending element (size %u) to client 
(full set)\n", element->size);
-  GNUNET_assert (0 != op->spec->client_request_id);
-  
-  ev = GNUNET_MQ_msg_extra (rm, element->size, GNUNET_MESSAGE_TYPE_SET_RESULT);
-  GNUNET_assert (NULL != ev);
-  
-  rm->result_status = htons (GNUNET_SET_STATUS_OK);
-  rm->request_id = htonl (op->spec->client_request_id);
-  rm->element_type = element->type;
-  memcpy (&rm[1], element->data, element->size);
-
-  GNUNET_MQ_notify_sent (ev, send_remaining_elements, op);
-  GNUNET_MQ_send (op->spec->set->client_mq, ev);
-}
-
 /**
  * handler for peer-disconnects, notifies the client about the aborted 
operation
  *