2 This file is part of GNUnet
3 Copyright (C) 2013, 2014 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 option) any later version.
10 GNUnet is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
21 * @file set/gnunet-service-set_intersection.c
22 * @brief two-peer set intersection
23 * @author Christian Fuchs
24 * @author Christian Grothoff
27 #include "gnunet_util_lib.h"
28 #include "gnunet-service-set.h"
29 #include "gnunet_block_lib.h"
30 #include "gnunet-service-set_protocol.h"
35 * Current phase we are in for a intersection operation.
37 enum IntersectionOperationPhase
40 * We are just starting.
45 * We have send the number of our elements to the other
46 * peer, but did not setup our element set yet.
51 * We have initialized our set and are now reducing it by exchanging
52 * Bloom filters until one party notices the their element hashes
58 * The protocol is over. Results may still have to be sent to the
66 * State of an evaluate operation with another peer.
71 * The bf we currently receive
73 struct GNUNET_CONTAINER_BloomFilter *remote_bf;
76 * BF of the set's element.
78 struct GNUNET_CONTAINER_BloomFilter *local_bf;
81 * Remaining elements in the intersection operation.
82 * Maps element-id-hashes to 'elements in our set'.
84 struct GNUNET_CONTAINER_MultiHashMap *my_elements;
87 * Iterator for sending the final set of @e my_elements to the client.
89 struct GNUNET_CONTAINER_MultiHashMapIterator *full_result_iter;
92 * Evaluate operations are held in a linked list.
94 struct OperationState *next;
97 * Evaluate operations are held in a linked list.
99 struct OperationState *prev;
102 * For multipart BF transmissions, we have to store the
103 * bloomfilter-data until we fully received it.
108 * XOR of the keys of all of the elements (remaining) in my set.
109 * Always updated when elements are added or removed to
112 struct GNUNET_HashCode my_xor;
115 * XOR of the keys of all of the elements (remaining) in
116 * the other peer's set. Updated when we receive the
117 * other peer's Bloom filter.
119 struct GNUNET_HashCode other_xor;
122 * How many bytes of @e bf_data are valid?
124 uint32_t bf_data_offset;
127 * Current element count contained within @e my_elements.
128 * (May differ briefly during initialization.)
130 uint32_t my_element_count;
133 * size of the bloomfilter in @e bf_data.
135 uint32_t bf_data_size;
138 * size of the bloomfilter
140 uint32_t bf_bits_per_element;
143 * Salt currently used for BF construction (by us or the other peer,
144 * depending on where we are in the code).
149 * Current state of the operation.
151 enum IntersectionOperationPhase phase;
154 * Generation in which the operation handle
157 unsigned int generation_created;
160 * Did we send the client that we are done?
162 int client_done_sent;
167 * Extra state required for efficient set intersection.
168 * Merely tracks the total number of elements.
173 * Number of currently valid elements in the set which have not been
176 uint32_t current_set_element_count;
181 * If applicable in the current operation mode, send a result message
182 * to the client indicating we removed an element.
184 * @param op intersection operation
185 * @param element element to send
188 send_client_removed_element (struct Operation *op,
189 struct GNUNET_SET_Element *element)
191 struct GNUNET_MQ_Envelope *ev;
192 struct GNUNET_SET_ResultMessage *rm;
194 if (GNUNET_SET_RESULT_REMOVED != op->spec->result_mode)
195 return; /* Wrong mode for transmitting removed elements */
196 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
197 "Sending removed element (size %u) to client\n",
199 GNUNET_assert (0 != op->spec->client_request_id);
200 ev = GNUNET_MQ_msg_extra (rm,
202 GNUNET_MESSAGE_TYPE_SET_RESULT);
208 rm->result_status = htons (GNUNET_SET_STATUS_OK);
209 rm->request_id = htonl (op->spec->client_request_id);
210 rm->element_type = element->element_type;
214 GNUNET_MQ_send (op->spec->set->client_mq,
220 * Fills the "my_elements" hashmap with all relevant elements.
222 * @param cls the `struct Operation *` we are performing
223 * @param key current key code
224 * @param value the `struct ElementEntry *` from the hash map
225 * @return #GNUNET_YES (we should continue to iterate)
228 filtered_map_initialization (void *cls,
229 const struct GNUNET_HashCode *key,
232 struct Operation *op = cls;
233 struct ElementEntry *ee = value;
234 struct GNUNET_HashCode mutated_hash;
237 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
238 "FIMA called for %s:%u\n",
239 GNUNET_h2s (&ee->element_hash),
242 if (_GSS_is_element_of_operation (ee, op))
244 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
245 "Reduced initialization, not starting with %s:%u (wrong generation)\n",
246 GNUNET_h2s (&ee->element_hash),
248 return GNUNET_YES; /* element not valid in our operation's generation */
251 /* Test if element is in other peer's bloomfilter */
252 GNUNET_BLOCK_mingle_hash (&ee->element_hash,
255 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
256 "Testing mingled hash %s with salt %u\n",
257 GNUNET_h2s (&mutated_hash),
260 GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf,
263 /* remove this element */
264 send_client_removed_element (op,
266 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
267 "Reduced initialization, not starting with %s:%u\n",
268 GNUNET_h2s (&ee->element_hash),
272 op->state->my_element_count++;
273 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
276 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
277 "Filtered initialization of my_elements, adding %s:%u\n",
278 GNUNET_h2s (&ee->element_hash),
280 GNUNET_break (GNUNET_YES ==
281 GNUNET_CONTAINER_multihashmap_put (op->state->my_elements,
284 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
291 * Removes elements from our hashmap if they are not contained within the
292 * provided remote bloomfilter.
294 * @param cls closure with the `struct Operation *`
295 * @param key current key code
296 * @param value value in the hash map
297 * @return #GNUNET_YES (we should continue to iterate)
300 iterator_bf_reduce (void *cls,
301 const struct GNUNET_HashCode *key,
304 struct Operation *op = cls;
305 struct ElementEntry *ee = value;
306 struct GNUNET_HashCode mutated_hash;
308 GNUNET_BLOCK_mingle_hash (&ee->element_hash,
311 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
312 "Testing mingled hash %s with salt %u\n",
313 GNUNET_h2s (&mutated_hash),
316 GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf,
319 GNUNET_break (0 < op->state->my_element_count);
320 op->state->my_element_count--;
321 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
324 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
325 "Bloom filter reduction of my_elements, removing %s:%u\n",
326 GNUNET_h2s (&ee->element_hash),
328 GNUNET_assert (GNUNET_YES ==
329 GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements,
332 send_client_removed_element (op,
337 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
338 "Bloom filter reduction of my_elements, keeping %s:%u\n",
339 GNUNET_h2s (&ee->element_hash),
347 * Create initial bloomfilter based on all the elements given.
349 * @param cls the `struct Operation *`
350 * @param key current key code
351 * @param value the `struct ElementEntry` to process
352 * @return #GNUNET_YES (we should continue to iterate)
355 iterator_bf_create (void *cls,
356 const struct GNUNET_HashCode *key,
359 struct Operation *op = cls;
360 struct ElementEntry *ee = value;
361 struct GNUNET_HashCode mutated_hash;
363 GNUNET_BLOCK_mingle_hash (&ee->element_hash,
366 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
367 "Initializing BF with hash %s with salt %u\n",
368 GNUNET_h2s (&mutated_hash),
370 GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf,
377 * Inform the client that the intersection operation has failed,
378 * and proceed to destroy the evaluate operation.
380 * @param op the intersection operation to fail
383 fail_intersection_operation (struct Operation *op)
385 struct GNUNET_MQ_Envelope *ev;
386 struct GNUNET_SET_ResultMessage *msg;
388 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
389 "Intersection operation failed\n");
390 if (NULL != op->state->my_elements)
392 GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements);
393 op->state->my_elements = NULL;
395 ev = GNUNET_MQ_msg (msg,
396 GNUNET_MESSAGE_TYPE_SET_RESULT);
397 msg->result_status = htons (GNUNET_SET_STATUS_FAILURE);
398 msg->request_id = htonl (op->spec->client_request_id);
399 msg->element_type = htons (0);
400 GNUNET_MQ_send (op->spec->set->client_mq,
402 _GSS_operation_destroy (op,
408 * Send a bloomfilter to our peer. After the result done message has
409 * been sent to the client, destroy the evaluate operation.
411 * @param op intersection operation
414 send_bloomfilter (struct Operation *op)
416 struct GNUNET_MQ_Envelope *ev;
417 struct BFMessage *msg;
419 uint32_t bf_elementbits;
424 /* We consider the ratio of the set sizes to determine
425 the number of bits per element, as the smaller set
426 should use more bits to maximize its set reduction
427 potential and minimize overall bandwidth consumption. */
428 bf_elementbits = 2 + ceil (log2((double)
429 (op->spec->remote_element_count /
430 (double) op->state->my_element_count)));
431 if (bf_elementbits < 1)
432 bf_elementbits = 1; /* make sure k is not 0 */
433 /* optimize BF-size to ~50% of bits set */
434 bf_size = ceil ((double) (op->state->my_element_count
435 * bf_elementbits / log(2)));
436 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
437 "Sending Bloom filter (%u) of size %u bytes\n",
438 (unsigned int) bf_elementbits,
439 (unsigned int) bf_size);
440 op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL,
443 op->state->salt = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
445 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
449 /* send our Bloom filter */
450 chunk_size = 60 * 1024 - sizeof (struct BFMessage);
451 if (bf_size <= chunk_size)
454 chunk_size = bf_size;
455 ev = GNUNET_MQ_msg_extra (msg,
457 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
458 GNUNET_assert (GNUNET_SYSERR !=
459 GNUNET_CONTAINER_bloomfilter_get_raw_data (op->state->local_bf,
462 msg->sender_element_count = htonl (op->state->my_element_count);
463 msg->bloomfilter_total_length = htonl (bf_size);
464 msg->bits_per_element = htonl (bf_elementbits);
465 msg->sender_mutator = htonl (op->state->salt);
466 msg->element_xor_hash = op->state->my_xor;
467 GNUNET_MQ_send (op->mq, ev);
472 bf_data = GNUNET_malloc (bf_size);
473 GNUNET_assert (GNUNET_SYSERR !=
474 GNUNET_CONTAINER_bloomfilter_get_raw_data (op->state->local_bf,
478 while (offset < bf_size)
480 if (bf_size - chunk_size < offset)
481 chunk_size = bf_size - offset;
482 ev = GNUNET_MQ_msg_extra (msg,
484 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
488 offset += chunk_size;
489 msg->sender_element_count = htonl (op->state->my_element_count);
490 msg->bloomfilter_total_length = htonl (bf_size);
491 msg->bits_per_element = htonl (bf_elementbits);
492 msg->sender_mutator = htonl (op->state->salt);
493 msg->element_xor_hash = op->state->my_xor;
494 GNUNET_MQ_send (op->mq, ev);
496 GNUNET_free (bf_data);
498 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
499 op->state->local_bf = NULL;
504 * Signal to the client that the operation has finished and
505 * destroy the operation.
507 * @param cls operation to destroy
510 send_client_done_and_destroy (void *cls)
512 struct Operation *op = cls;
513 struct GNUNET_MQ_Envelope *ev;
514 struct GNUNET_SET_ResultMessage *rm;
516 ev = GNUNET_MQ_msg (rm,
517 GNUNET_MESSAGE_TYPE_SET_RESULT);
518 rm->request_id = htonl (op->spec->client_request_id);
519 rm->result_status = htons (GNUNET_SET_STATUS_DONE);
520 rm->element_type = htons (0);
521 GNUNET_MQ_send (op->spec->set->client_mq,
523 _GSS_operation_destroy (op,
529 * Send all elements in the full result iterator.
531 * @param cls the `struct Operation *`
534 send_remaining_elements (void *cls)
536 struct Operation *op = cls;
538 const struct ElementEntry *ee;
539 struct GNUNET_MQ_Envelope *ev;
540 struct GNUNET_SET_ResultMessage *rm;
541 const struct GNUNET_SET_Element *element;
544 res = GNUNET_CONTAINER_multihashmap_iterator_next (op->state->full_result_iter,
547 if (GNUNET_NO == res)
549 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
550 "Sending done and destroy because iterator ran out\n");
552 send_client_done_and_destroy (op);
556 element = &ee->element;
557 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
558 "Sending element %s:%u to client (full set)\n",
559 GNUNET_h2s (&ee->element_hash),
561 GNUNET_assert (0 != op->spec->client_request_id);
562 ev = GNUNET_MQ_msg_extra (rm,
564 GNUNET_MESSAGE_TYPE_SET_RESULT);
565 GNUNET_assert (NULL != ev);
566 rm->result_status = htons (GNUNET_SET_STATUS_OK);
567 rm->request_id = htonl (op->spec->client_request_id);
568 rm->element_type = element->element_type;
572 GNUNET_MQ_notify_sent (ev,
573 &send_remaining_elements,
575 GNUNET_MQ_send (op->spec->set->client_mq,
581 * Inform the peer that this operation is complete.
583 * @param op the intersection operation to fail
586 send_peer_done (struct Operation *op)
588 struct GNUNET_MQ_Envelope *ev;
589 struct IntersectionDoneMessage *idm;
591 op->state->phase = PHASE_FINISHED;
592 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
593 "Intersection succeeded, sending DONE\n");
594 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
595 op->state->local_bf = NULL;
597 ev = GNUNET_MQ_msg (idm,
598 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE);
599 idm->final_element_count = htonl (op->state->my_element_count);
600 idm->element_xor_hash = op->state->my_xor;
601 GNUNET_MQ_send (op->mq,
607 * Process a Bloomfilter once we got all the chunks.
609 * @param op the intersection operation
612 process_bf (struct Operation *op)
614 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
615 "Received BF in phase %u, foreign count is %u, my element count is %u/%u\n",
617 op->spec->remote_element_count,
618 op->state->my_element_count,
619 GNUNET_CONTAINER_multihashmap_size (op->spec->set->content->elements));
620 switch (op->state->phase)
624 fail_intersection_operation(op);
626 case PHASE_COUNT_SENT:
627 /* This is the first BF being sent, build our initial map with
628 filtering in place */
629 op->state->my_elements
630 = GNUNET_CONTAINER_multihashmap_create (op->spec->remote_element_count,
632 op->state->my_element_count = 0;
633 GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->content->elements,
634 &filtered_map_initialization,
637 case PHASE_BF_EXCHANGE:
638 /* Update our set by reduction */
639 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
645 fail_intersection_operation(op);
648 GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf);
649 op->state->remote_bf = NULL;
651 if ( (0 == op->state->my_element_count) || /* fully disjoint */
652 ( (op->state->my_element_count == op->spec->remote_element_count) &&
653 (0 == memcmp (&op->state->my_xor,
654 &op->state->other_xor,
655 sizeof (struct GNUNET_HashCode))) ) )
661 op->state->phase = PHASE_BF_EXCHANGE;
662 send_bloomfilter (op);
667 * Handle an BF message from a remote peer.
669 * @param cls the intersection operation
670 * @param mh the header of the message
673 handle_p2p_bf (void *cls,
674 const struct GNUNET_MessageHeader *mh)
676 struct Operation *op = cls;
677 const struct BFMessage *msg;
680 uint32_t bf_bits_per_element;
683 msize = htons (mh->size);
684 if (msize < sizeof (struct BFMessage))
687 fail_intersection_operation (op);
690 msg = (const struct BFMessage *) mh;
691 switch (op->state->phase)
695 fail_intersection_operation (op);
697 case PHASE_COUNT_SENT:
698 case PHASE_BF_EXCHANGE:
699 bf_size = ntohl (msg->bloomfilter_total_length);
700 bf_bits_per_element = ntohl (msg->bits_per_element);
701 chunk_size = msize - sizeof (struct BFMessage);
702 op->state->other_xor = msg->element_xor_hash;
703 if (bf_size == chunk_size)
705 if (NULL != op->state->bf_data)
708 fail_intersection_operation (op);
711 /* single part, done here immediately */
713 = GNUNET_CONTAINER_bloomfilter_init ((const char*) &msg[1],
715 bf_bits_per_element);
716 op->state->salt = ntohl (msg->sender_mutator);
717 op->spec->remote_element_count = ntohl (msg->sender_element_count);
721 /* multipart chunk */
722 if (NULL == op->state->bf_data)
724 /* first chunk, initialize */
725 op->state->bf_data = GNUNET_malloc (bf_size);
726 op->state->bf_data_size = bf_size;
727 op->state->bf_bits_per_element = bf_bits_per_element;
728 op->state->bf_data_offset = 0;
729 op->state->salt = ntohl (msg->sender_mutator);
730 op->spec->remote_element_count = ntohl (msg->sender_element_count);
735 if ( (op->state->bf_data_size != bf_size) ||
736 (op->state->bf_bits_per_element != bf_bits_per_element) ||
737 (op->state->bf_data_offset + chunk_size > bf_size) ||
738 (op->state->salt != ntohl (msg->sender_mutator)) ||
739 (op->spec->remote_element_count != ntohl (msg->sender_element_count)) )
742 fail_intersection_operation (op);
746 memcpy (&op->state->bf_data[op->state->bf_data_offset],
747 (const char*) &msg[1],
749 op->state->bf_data_offset += chunk_size;
750 if (op->state->bf_data_offset == bf_size)
752 /* last chunk, run! */
754 = GNUNET_CONTAINER_bloomfilter_init (op->state->bf_data,
756 bf_bits_per_element);
757 GNUNET_free (op->state->bf_data);
758 op->state->bf_data = NULL;
759 op->state->bf_data_size = 0;
765 fail_intersection_operation (op);
772 * Fills the "my_elements" hashmap with the initial set of
773 * (non-deleted) elements from the set of the specification.
775 * @param cls closure with the `struct Operation *`
776 * @param key current key code for the element
777 * @param value value in the hash map with the `struct ElementEntry *`
778 * @return #GNUNET_YES (we should continue to iterate)
781 initialize_map_unfiltered (void *cls,
782 const struct GNUNET_HashCode *key,
785 struct ElementEntry *ee = value;
786 struct Operation *op = cls;
788 if (_GSS_is_element_of_operation (ee, op))
789 return GNUNET_YES; /* element not live in operation's generation */
790 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
793 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
794 "Initial full initialization of my_elements, adding %s:%u\n",
795 GNUNET_h2s (&ee->element_hash),
797 GNUNET_break (GNUNET_YES ==
798 GNUNET_CONTAINER_multihashmap_put (op->state->my_elements,
801 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
807 * Send our element count to the peer, in case our element count is
810 * @param op intersection operation
813 send_element_count (struct Operation *op)
815 struct GNUNET_MQ_Envelope *ev;
816 struct IntersectionElementInfoMessage *msg;
818 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
819 "Sending our element count (%u)\n",
820 op->state->my_element_count);
821 ev = GNUNET_MQ_msg (msg,
822 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO);
823 msg->sender_element_count = htonl (op->state->my_element_count);
824 GNUNET_MQ_send (op->mq, ev);
829 * We go first, initialize our map with all elements and
830 * send the first Bloom filter.
832 * @param op operation to start exchange for
835 begin_bf_exchange (struct Operation *op)
837 op->state->phase = PHASE_BF_EXCHANGE;
838 op->state->my_elements
839 = GNUNET_CONTAINER_multihashmap_create (op->state->my_element_count,
841 GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->content->elements,
842 &initialize_map_unfiltered,
844 send_bloomfilter (op);
849 * Handle the initial `struct IntersectionElementInfoMessage` from a
852 * @param cls the intersection operation
853 * @param mh the header of the message
856 handle_p2p_element_info (void *cls,
857 const struct GNUNET_MessageHeader *mh)
859 struct Operation *op = cls;
860 const struct IntersectionElementInfoMessage *msg;
862 if (ntohs (mh->size) != sizeof (struct IntersectionElementInfoMessage))
865 fail_intersection_operation(op);
868 msg = (const struct IntersectionElementInfoMessage *) mh;
869 op->spec->remote_element_count = ntohl (msg->sender_element_count);
870 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
871 "Received remote element count (%u), I have %u\n",
872 op->spec->remote_element_count,
873 op->state->my_element_count);
874 if ( ( (PHASE_INITIAL != op->state->phase) &&
875 (PHASE_COUNT_SENT != op->state->phase) ) ||
876 (op->state->my_element_count > op->spec->remote_element_count) ||
877 (0 == op->state->my_element_count) ||
878 (0 == op->spec->remote_element_count) )
881 fail_intersection_operation(op);
884 GNUNET_break (NULL == op->state->remote_bf);
885 begin_bf_exchange (op);
890 * Send a result message to the client indicating that the operation
891 * is over. After the result done message has been sent to the
892 * client, destroy the evaluate operation.
894 * @param op intersection operation
897 finish_and_destroy (struct Operation *op)
899 GNUNET_assert (GNUNET_NO == op->state->client_done_sent);
901 if (GNUNET_SET_RESULT_FULL == op->spec->result_mode)
903 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
904 "Sending full result set (%u elements)\n",
905 GNUNET_CONTAINER_multihashmap_size (op->state->my_elements));
906 op->state->full_result_iter
907 = GNUNET_CONTAINER_multihashmap_iterator_create (op->state->my_elements);
909 send_remaining_elements (op);
912 send_client_done_and_destroy (op);
917 * Remove all elements from our hashmap.
919 * @param cls closure with the `struct Operation *`
920 * @param key current key code
921 * @param value value in the hash map
922 * @return #GNUNET_YES (we should continue to iterate)
925 filter_all (void *cls,
926 const struct GNUNET_HashCode *key,
929 struct Operation *op = cls;
930 struct ElementEntry *ee = value;
932 GNUNET_break (0 < op->state->my_element_count);
933 op->state->my_element_count--;
934 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
937 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
938 "Final reduction of my_elements, removing %s:%u\n",
939 GNUNET_h2s (&ee->element_hash),
941 GNUNET_assert (GNUNET_YES ==
942 GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements,
945 send_client_removed_element (op,
952 * Handle a done message from a remote peer
954 * @param cls the intersection operation
955 * @param mh the message
958 handle_p2p_done (void *cls,
959 const struct GNUNET_MessageHeader *mh)
961 struct Operation *op = cls;
962 const struct IntersectionDoneMessage *idm;
964 if (PHASE_BF_EXCHANGE != op->state->phase)
966 /* wrong phase to conclude? FIXME: Or should we allow this
967 if the other peer has _initially_ already an empty set? */
969 fail_intersection_operation (op);
972 if (ntohs (mh->size) != sizeof (struct IntersectionDoneMessage))
975 fail_intersection_operation (op);
978 idm = (const struct IntersectionDoneMessage *) mh;
979 if (0 == ntohl (idm->final_element_count))
981 /* other peer determined empty set is the intersection,
982 remove all elements */
983 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
987 if ( (op->state->my_element_count != ntohl (idm->final_element_count)) ||
988 (0 != memcmp (&op->state->my_xor,
989 &idm->element_xor_hash,
990 sizeof (struct GNUNET_HashCode))) )
992 /* Other peer thinks we are done, but we disagree on the result! */
994 fail_intersection_operation (op);
997 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
998 "Got IntersectionDoneMessage, have %u elements in intersection\n",
999 op->state->my_element_count);
1000 op->state->phase = PHASE_FINISHED;
1001 finish_and_destroy (op);
1006 * Initiate a set intersection operation with a remote peer.
1008 * @param op operation that is created, should be initialized to
1009 * begin the evaluation
1010 * @param opaque_context message to be transmitted to the listener
1011 * to convince him to accept, may be NULL
1014 intersection_evaluate (struct Operation *op,
1015 const struct GNUNET_MessageHeader *opaque_context)
1017 struct GNUNET_MQ_Envelope *ev;
1018 struct OperationRequestMessage *msg;
1020 op->state = GNUNET_new (struct OperationState);
1021 /* we started the operation, thus we have to send the operation request */
1022 op->state->phase = PHASE_INITIAL;
1023 op->state->my_element_count = op->spec->set->state->current_set_element_count;
1025 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1026 "Initiating intersection operation evaluation\n");
1027 ev = GNUNET_MQ_msg_nested_mh (msg,
1028 GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST,
1032 /* the context message is too large!? */
1034 GNUNET_SERVER_client_disconnect (op->spec->set->client);
1037 msg->operation = htonl (GNUNET_SET_OPERATION_INTERSECTION);
1038 msg->app_id = op->spec->app_id;
1039 msg->element_count = htonl (op->state->my_element_count);
1040 GNUNET_MQ_send (op->mq,
1042 op->state->phase = PHASE_COUNT_SENT;
1043 if (NULL != opaque_context)
1044 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1045 "Sent op request with context message\n");
1047 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1048 "Sent op request without context message\n");
1053 * Accept an intersection operation request from a remote peer. Only
1054 * initializes the private operation state.
1056 * @param op operation that will be accepted as an intersection operation
1059 intersection_accept (struct Operation *op)
1061 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1062 "Accepting set intersection operation\n");
1063 op->state = GNUNET_new (struct OperationState);
1064 op->state->phase = PHASE_INITIAL;
1065 op->state->my_element_count
1066 = op->spec->set->state->current_set_element_count;
1067 op->state->my_elements
1068 = GNUNET_CONTAINER_multihashmap_create
1069 (GNUNET_MIN (op->state->my_element_count,
1070 op->spec->remote_element_count),
1072 if (op->spec->remote_element_count < op->state->my_element_count)
1074 /* If the other peer (Alice) has fewer elements than us (Bob),
1075 we just send the count as Alice should send the first BF */
1076 send_element_count (op);
1077 op->state->phase = PHASE_COUNT_SENT;
1080 /* We have fewer elements, so we start with the BF */
1081 begin_bf_exchange (op);
1086 * Dispatch messages for a intersection operation.
1088 * @param op the state of the intersection evaluate operation
1089 * @param mh the received message
1090 * @return #GNUNET_SYSERR if the tunnel should be disconnected,
1091 * #GNUNET_OK otherwise
1094 intersection_handle_p2p_message (struct Operation *op,
1095 const struct GNUNET_MessageHeader *mh)
1097 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1098 "Received p2p message (t: %u, s: %u)\n",
1099 ntohs (mh->type), ntohs (mh->size));
1100 switch (ntohs (mh->type))
1102 /* this message handler is not active until after we received an
1103 * operation request message, thus the ops request is not handled here
1105 case GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO:
1106 handle_p2p_element_info (op, mh);
1108 case GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF:
1109 handle_p2p_bf (op, mh);
1111 case GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE:
1112 handle_p2p_done (op, mh);
1115 /* something wrong with cadet's message handlers? */
1123 * Handler for peer-disconnects, notifies the client about the aborted
1124 * operation. If we did not expect anything from the other peer, we
1125 * gracefully terminate the operation.
1127 * @param op the destroyed operation
1130 intersection_peer_disconnect (struct Operation *op)
1132 if (PHASE_FINISHED != op->state->phase)
1134 fail_intersection_operation (op);
1137 /* the session has already been concluded */
1138 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1139 "Other peer disconnected (finished)\n");
1140 if (GNUNET_NO == op->state->client_done_sent)
1141 finish_and_destroy (op);
1146 * Destroy the intersection operation. Only things specific to the
1147 * intersection operation are destroyed.
1149 * @param op intersection operation to destroy
1152 intersection_op_cancel (struct Operation *op)
1154 /* check if the op was canceled twice */
1155 GNUNET_assert (NULL != op->state);
1156 if (NULL != op->state->remote_bf)
1158 GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf);
1159 op->state->remote_bf = NULL;
1161 if (NULL != op->state->local_bf)
1163 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
1164 op->state->local_bf = NULL;
1166 if (NULL != op->state->my_elements)
1168 GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements);
1169 op->state->my_elements = NULL;
1171 GNUNET_free (op->state);
1173 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1174 "Destroying intersection op state done\n");
1179 * Create a new set supporting the intersection operation.
1181 * @return the newly created set
1183 static struct SetState *
1184 intersection_set_create ()
1186 struct SetState *set_state;
1188 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1189 "Intersection set created\n");
1190 set_state = GNUNET_new (struct SetState);
1191 set_state->current_set_element_count = 0;
1198 * Add the element from the given element message to the set.
1200 * @param set_state state of the set want to add to
1201 * @param ee the element to add to the set
1204 intersection_add (struct SetState *set_state,
1205 struct ElementEntry *ee)
1207 set_state->current_set_element_count++;
1212 * Destroy a set that supports the intersection operation
1214 * @param set_state the set to destroy
1217 intersection_set_destroy (struct SetState *set_state)
1219 GNUNET_free (set_state);
1224 * Remove the element given in the element message from the set.
1226 * @param set_state state of the set to remove from
1227 * @param element set element to remove
1230 intersection_remove (struct SetState *set_state,
1231 struct ElementEntry *element)
1233 GNUNET_assert (0 < set_state->current_set_element_count);
1234 set_state->current_set_element_count--;
1239 * Get the table with implementing functions for set intersection.
1241 * @return the operation specific VTable
1243 const struct SetVT *
1244 _GSS_intersection_vt ()
1246 static const struct SetVT intersection_vt = {
1247 .create = &intersection_set_create,
1248 .msg_handler = &intersection_handle_p2p_message,
1249 .add = &intersection_add,
1250 .remove = &intersection_remove,
1251 .destroy_set = &intersection_set_destroy,
1252 .evaluate = &intersection_evaluate,
1253 .accept = &intersection_accept,
1254 .peer_disconnect = &intersection_peer_disconnect,
1255 .cancel = &intersection_op_cancel,
1258 return &intersection_vt;