2 This file is part of GNUnet
3 Copyright (C) 2013, 2014 GNUnet e.V.
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
67 * State of an evaluate operation with another peer.
72 * The bf we currently receive
74 struct GNUNET_CONTAINER_BloomFilter *remote_bf;
77 * BF of the set's element.
79 struct GNUNET_CONTAINER_BloomFilter *local_bf;
82 * Remaining elements in the intersection operation.
83 * Maps element-id-hashes to 'elements in our set'.
85 struct GNUNET_CONTAINER_MultiHashMap *my_elements;
88 * Iterator for sending the final set of @e my_elements to the client.
90 struct GNUNET_CONTAINER_MultiHashMapIterator *full_result_iter;
93 * Evaluate operations are held in a linked list.
95 struct OperationState *next;
98 * Evaluate operations are held in a linked list.
100 struct OperationState *prev;
103 * For multipart BF transmissions, we have to store the
104 * bloomfilter-data until we fully received it.
109 * XOR of the keys of all of the elements (remaining) in my set.
110 * Always updated when elements are added or removed to
113 struct GNUNET_HashCode my_xor;
116 * XOR of the keys of all of the elements (remaining) in
117 * the other peer's set. Updated when we receive the
118 * other peer's Bloom filter.
120 struct GNUNET_HashCode other_xor;
123 * How many bytes of @e bf_data are valid?
125 uint32_t bf_data_offset;
128 * Current element count contained within @e my_elements.
129 * (May differ briefly during initialization.)
131 uint32_t my_element_count;
134 * size of the bloomfilter in @e bf_data.
136 uint32_t bf_data_size;
139 * size of the bloomfilter
141 uint32_t bf_bits_per_element;
144 * Salt currently used for BF construction (by us or the other peer,
145 * depending on where we are in the code).
150 * Current state of the operation.
152 enum IntersectionOperationPhase phase;
155 * Generation in which the operation handle
158 unsigned int generation_created;
161 * Did we send the client that we are done?
163 int client_done_sent;
168 * Extra state required for efficient set intersection.
169 * Merely tracks the total number of elements.
174 * Number of currently valid elements in the set which have not been
177 uint32_t current_set_element_count;
182 * If applicable in the current operation mode, send a result message
183 * to the client indicating we removed an element.
185 * @param op intersection operation
186 * @param element element to send
189 send_client_removed_element (struct Operation *op,
190 struct GNUNET_SET_Element *element)
192 struct GNUNET_MQ_Envelope *ev;
193 struct GNUNET_SET_ResultMessage *rm;
195 if (GNUNET_SET_RESULT_REMOVED != op->spec->result_mode)
196 return; /* Wrong mode for transmitting removed elements */
197 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
198 "Sending removed element (size %u) to client\n",
200 GNUNET_assert (0 != op->spec->client_request_id);
201 ev = GNUNET_MQ_msg_extra (rm,
203 GNUNET_MESSAGE_TYPE_SET_RESULT);
209 rm->result_status = htons (GNUNET_SET_STATUS_OK);
210 rm->request_id = htonl (op->spec->client_request_id);
211 rm->element_type = element->element_type;
212 GNUNET_memcpy (&rm[1],
215 GNUNET_MQ_send (op->spec->set->client_mq,
221 * Fills the "my_elements" hashmap with all relevant elements.
223 * @param cls the `struct Operation *` we are performing
224 * @param key current key code
225 * @param value the `struct ElementEntry *` from the hash map
226 * @return #GNUNET_YES (we should continue to iterate)
229 filtered_map_initialization (void *cls,
230 const struct GNUNET_HashCode *key,
233 struct Operation *op = cls;
234 struct ElementEntry *ee = value;
235 struct GNUNET_HashCode mutated_hash;
238 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
239 "FIMA called for %s:%u\n",
240 GNUNET_h2s (&ee->element_hash),
243 if (GNUNET_NO == _GSS_is_element_of_operation (ee, op))
245 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
246 "Reduced initialization, not starting with %s:%u (wrong generation)\n",
247 GNUNET_h2s (&ee->element_hash),
249 return GNUNET_YES; /* element not valid in our operation's generation */
252 /* Test if element is in other peer's bloomfilter */
253 GNUNET_BLOCK_mingle_hash (&ee->element_hash,
256 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
257 "Testing mingled hash %s with salt %u\n",
258 GNUNET_h2s (&mutated_hash),
261 GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf,
264 /* remove this element */
265 send_client_removed_element (op,
267 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
268 "Reduced initialization, not starting with %s:%u\n",
269 GNUNET_h2s (&ee->element_hash),
273 op->state->my_element_count++;
274 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
277 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
278 "Filtered initialization of my_elements, adding %s:%u\n",
279 GNUNET_h2s (&ee->element_hash),
281 GNUNET_break (GNUNET_YES ==
282 GNUNET_CONTAINER_multihashmap_put (op->state->my_elements,
285 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
292 * Removes elements from our hashmap if they are not contained within the
293 * provided remote bloomfilter.
295 * @param cls closure with the `struct Operation *`
296 * @param key current key code
297 * @param value value in the hash map
298 * @return #GNUNET_YES (we should continue to iterate)
301 iterator_bf_reduce (void *cls,
302 const struct GNUNET_HashCode *key,
305 struct Operation *op = cls;
306 struct ElementEntry *ee = value;
307 struct GNUNET_HashCode mutated_hash;
309 GNUNET_BLOCK_mingle_hash (&ee->element_hash,
312 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
313 "Testing mingled hash %s with salt %u\n",
314 GNUNET_h2s (&mutated_hash),
317 GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf,
320 GNUNET_break (0 < op->state->my_element_count);
321 op->state->my_element_count--;
322 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
325 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
326 "Bloom filter reduction of my_elements, removing %s:%u\n",
327 GNUNET_h2s (&ee->element_hash),
329 GNUNET_assert (GNUNET_YES ==
330 GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements,
333 send_client_removed_element (op,
338 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
339 "Bloom filter reduction of my_elements, keeping %s:%u\n",
340 GNUNET_h2s (&ee->element_hash),
348 * Create initial bloomfilter based on all the elements given.
350 * @param cls the `struct Operation *`
351 * @param key current key code
352 * @param value the `struct ElementEntry` to process
353 * @return #GNUNET_YES (we should continue to iterate)
356 iterator_bf_create (void *cls,
357 const struct GNUNET_HashCode *key,
360 struct Operation *op = cls;
361 struct ElementEntry *ee = value;
362 struct GNUNET_HashCode mutated_hash;
364 GNUNET_BLOCK_mingle_hash (&ee->element_hash,
367 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
368 "Initializing BF with hash %s with salt %u\n",
369 GNUNET_h2s (&mutated_hash),
371 GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf,
378 * Inform the client that the intersection operation has failed,
379 * and proceed to destroy the evaluate operation.
381 * @param op the intersection operation to fail
384 fail_intersection_operation (struct Operation *op)
386 struct GNUNET_MQ_Envelope *ev;
387 struct GNUNET_SET_ResultMessage *msg;
389 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
390 "Intersection operation failed\n");
391 if (NULL != op->state->my_elements)
393 GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements);
394 op->state->my_elements = NULL;
396 ev = GNUNET_MQ_msg (msg,
397 GNUNET_MESSAGE_TYPE_SET_RESULT);
398 msg->result_status = htons (GNUNET_SET_STATUS_FAILURE);
399 msg->request_id = htonl (op->spec->client_request_id);
400 msg->element_type = htons (0);
401 GNUNET_MQ_send (op->spec->set->client_mq,
403 _GSS_operation_destroy (op,
409 * Send a bloomfilter to our peer. After the result done message has
410 * been sent to the client, destroy the evaluate operation.
412 * @param op intersection operation
415 send_bloomfilter (struct Operation *op)
417 struct GNUNET_MQ_Envelope *ev;
418 struct BFMessage *msg;
420 uint32_t bf_elementbits;
425 /* We consider the ratio of the set sizes to determine
426 the number of bits per element, as the smaller set
427 should use more bits to maximize its set reduction
428 potential and minimize overall bandwidth consumption. */
429 bf_elementbits = 2 + ceil (log2((double)
430 (op->spec->remote_element_count /
431 (double) op->state->my_element_count)));
432 if (bf_elementbits < 1)
433 bf_elementbits = 1; /* make sure k is not 0 */
434 /* optimize BF-size to ~50% of bits set */
435 bf_size = ceil ((double) (op->state->my_element_count
436 * bf_elementbits / log(2)));
437 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
438 "Sending Bloom filter (%u) of size %u bytes\n",
439 (unsigned int) bf_elementbits,
440 (unsigned int) bf_size);
441 op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL,
444 op->state->salt = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
446 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
450 /* send our Bloom filter */
451 chunk_size = 60 * 1024 - sizeof (struct BFMessage);
452 if (bf_size <= chunk_size)
455 chunk_size = bf_size;
456 ev = GNUNET_MQ_msg_extra (msg,
458 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
459 GNUNET_assert (GNUNET_SYSERR !=
460 GNUNET_CONTAINER_bloomfilter_get_raw_data (op->state->local_bf,
463 msg->sender_element_count = htonl (op->state->my_element_count);
464 msg->bloomfilter_total_length = htonl (bf_size);
465 msg->bits_per_element = htonl (bf_elementbits);
466 msg->sender_mutator = htonl (op->state->salt);
467 msg->element_xor_hash = op->state->my_xor;
468 GNUNET_MQ_send (op->mq, ev);
473 bf_data = GNUNET_malloc (bf_size);
474 GNUNET_assert (GNUNET_SYSERR !=
475 GNUNET_CONTAINER_bloomfilter_get_raw_data (op->state->local_bf,
479 while (offset < bf_size)
481 if (bf_size - chunk_size < offset)
482 chunk_size = bf_size - offset;
483 ev = GNUNET_MQ_msg_extra (msg,
485 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
486 GNUNET_memcpy (&msg[1],
489 offset += chunk_size;
490 msg->sender_element_count = htonl (op->state->my_element_count);
491 msg->bloomfilter_total_length = htonl (bf_size);
492 msg->bits_per_element = htonl (bf_elementbits);
493 msg->sender_mutator = htonl (op->state->salt);
494 msg->element_xor_hash = op->state->my_xor;
495 GNUNET_MQ_send (op->mq, ev);
497 GNUNET_free (bf_data);
499 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
500 op->state->local_bf = NULL;
505 * Signal to the client that the operation has finished and
506 * destroy the operation.
508 * @param cls operation to destroy
511 send_client_done_and_destroy (void *cls)
513 struct Operation *op = cls;
514 struct GNUNET_MQ_Envelope *ev;
515 struct GNUNET_SET_ResultMessage *rm;
517 ev = GNUNET_MQ_msg (rm,
518 GNUNET_MESSAGE_TYPE_SET_RESULT);
519 rm->request_id = htonl (op->spec->client_request_id);
520 rm->result_status = htons (GNUNET_SET_STATUS_DONE);
521 rm->element_type = htons (0);
522 GNUNET_MQ_send (op->spec->set->client_mq,
524 _GSS_operation_destroy (op,
530 * Send all elements in the full result iterator.
532 * @param cls the `struct Operation *`
535 send_remaining_elements (void *cls)
537 struct Operation *op = cls;
539 const struct ElementEntry *ee;
540 struct GNUNET_MQ_Envelope *ev;
541 struct GNUNET_SET_ResultMessage *rm;
542 const struct GNUNET_SET_Element *element;
545 res = GNUNET_CONTAINER_multihashmap_iterator_next (op->state->full_result_iter,
548 if (GNUNET_NO == res)
550 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
551 "Sending done and destroy because iterator ran out\n");
553 send_client_done_and_destroy (op);
557 element = &ee->element;
558 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
559 "Sending element %s:%u to client (full set)\n",
560 GNUNET_h2s (&ee->element_hash),
562 GNUNET_assert (0 != op->spec->client_request_id);
563 ev = GNUNET_MQ_msg_extra (rm,
565 GNUNET_MESSAGE_TYPE_SET_RESULT);
566 GNUNET_assert (NULL != ev);
567 rm->result_status = htons (GNUNET_SET_STATUS_OK);
568 rm->request_id = htonl (op->spec->client_request_id);
569 rm->element_type = element->element_type;
570 GNUNET_memcpy (&rm[1],
573 GNUNET_MQ_notify_sent (ev,
574 &send_remaining_elements,
576 GNUNET_MQ_send (op->spec->set->client_mq,
582 * Inform the peer that this operation is complete.
584 * @param op the intersection operation to fail
587 send_peer_done (struct Operation *op)
589 struct GNUNET_MQ_Envelope *ev;
590 struct IntersectionDoneMessage *idm;
592 op->state->phase = PHASE_FINISHED;
593 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
594 "Intersection succeeded, sending DONE\n");
595 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
596 op->state->local_bf = NULL;
598 ev = GNUNET_MQ_msg (idm,
599 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE);
600 idm->final_element_count = htonl (op->state->my_element_count);
601 idm->element_xor_hash = op->state->my_xor;
602 GNUNET_MQ_send (op->mq,
608 * Process a Bloomfilter once we got all the chunks.
610 * @param op the intersection operation
613 process_bf (struct Operation *op)
615 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
616 "Received BF in phase %u, foreign count is %u, my element count is %u/%u\n",
618 op->spec->remote_element_count,
619 op->state->my_element_count,
620 GNUNET_CONTAINER_multihashmap_size (op->spec->set->content->elements));
621 switch (op->state->phase)
625 fail_intersection_operation(op);
627 case PHASE_COUNT_SENT:
628 /* This is the first BF being sent, build our initial map with
629 filtering in place */
630 op->state->my_elements
631 = GNUNET_CONTAINER_multihashmap_create (op->spec->remote_element_count,
633 op->state->my_element_count = 0;
634 GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->content->elements,
635 &filtered_map_initialization,
638 case PHASE_BF_EXCHANGE:
639 /* Update our set by reduction */
640 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
646 fail_intersection_operation(op);
649 GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf);
650 op->state->remote_bf = NULL;
652 if ( (0 == op->state->my_element_count) || /* fully disjoint */
653 ( (op->state->my_element_count == op->spec->remote_element_count) &&
654 (0 == memcmp (&op->state->my_xor,
655 &op->state->other_xor,
656 sizeof (struct GNUNET_HashCode))) ) )
662 op->state->phase = PHASE_BF_EXCHANGE;
663 send_bloomfilter (op);
668 * Handle an BF message from a remote peer.
670 * @param cls the intersection operation
671 * @param mh the header of the message
674 handle_p2p_bf (void *cls,
675 const struct GNUNET_MessageHeader *mh)
677 struct Operation *op = cls;
678 const struct BFMessage *msg;
681 uint32_t bf_bits_per_element;
684 msize = htons (mh->size);
685 if (msize < sizeof (struct BFMessage))
688 fail_intersection_operation (op);
691 msg = (const struct BFMessage *) mh;
692 switch (op->state->phase)
696 fail_intersection_operation (op);
698 case PHASE_COUNT_SENT:
699 case PHASE_BF_EXCHANGE:
700 bf_size = ntohl (msg->bloomfilter_total_length);
701 bf_bits_per_element = ntohl (msg->bits_per_element);
702 chunk_size = msize - sizeof (struct BFMessage);
703 op->state->other_xor = msg->element_xor_hash;
704 if (bf_size == chunk_size)
706 if (NULL != op->state->bf_data)
709 fail_intersection_operation (op);
712 /* single part, done here immediately */
714 = GNUNET_CONTAINER_bloomfilter_init ((const char*) &msg[1],
716 bf_bits_per_element);
717 op->state->salt = ntohl (msg->sender_mutator);
718 op->spec->remote_element_count = ntohl (msg->sender_element_count);
722 /* multipart chunk */
723 if (NULL == op->state->bf_data)
725 /* first chunk, initialize */
726 op->state->bf_data = GNUNET_malloc (bf_size);
727 op->state->bf_data_size = bf_size;
728 op->state->bf_bits_per_element = bf_bits_per_element;
729 op->state->bf_data_offset = 0;
730 op->state->salt = ntohl (msg->sender_mutator);
731 op->spec->remote_element_count = ntohl (msg->sender_element_count);
736 if ( (op->state->bf_data_size != bf_size) ||
737 (op->state->bf_bits_per_element != bf_bits_per_element) ||
738 (op->state->bf_data_offset + chunk_size > bf_size) ||
739 (op->state->salt != ntohl (msg->sender_mutator)) ||
740 (op->spec->remote_element_count != ntohl (msg->sender_element_count)) )
743 fail_intersection_operation (op);
747 GNUNET_memcpy (&op->state->bf_data[op->state->bf_data_offset],
748 (const char*) &msg[1],
750 op->state->bf_data_offset += chunk_size;
751 if (op->state->bf_data_offset == bf_size)
753 /* last chunk, run! */
755 = GNUNET_CONTAINER_bloomfilter_init (op->state->bf_data,
757 bf_bits_per_element);
758 GNUNET_free (op->state->bf_data);
759 op->state->bf_data = NULL;
760 op->state->bf_data_size = 0;
766 fail_intersection_operation (op);
773 * Fills the "my_elements" hashmap with the initial set of
774 * (non-deleted) elements from the set of the specification.
776 * @param cls closure with the `struct Operation *`
777 * @param key current key code for the element
778 * @param value value in the hash map with the `struct ElementEntry *`
779 * @return #GNUNET_YES (we should continue to iterate)
782 initialize_map_unfiltered (void *cls,
783 const struct GNUNET_HashCode *key,
786 struct ElementEntry *ee = value;
787 struct Operation *op = cls;
789 if (GNUNET_NO == _GSS_is_element_of_operation (ee, op))
790 return GNUNET_YES; /* element not live in operation's generation */
791 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
794 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
795 "Initial full initialization of my_elements, adding %s:%u\n",
796 GNUNET_h2s (&ee->element_hash),
798 GNUNET_break (GNUNET_YES ==
799 GNUNET_CONTAINER_multihashmap_put (op->state->my_elements,
802 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
808 * Send our element count to the peer, in case our element count is
811 * @param op intersection operation
814 send_element_count (struct Operation *op)
816 struct GNUNET_MQ_Envelope *ev;
817 struct IntersectionElementInfoMessage *msg;
819 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
820 "Sending our element count (%u)\n",
821 op->state->my_element_count);
822 ev = GNUNET_MQ_msg (msg,
823 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO);
824 msg->sender_element_count = htonl (op->state->my_element_count);
825 GNUNET_MQ_send (op->mq, ev);
830 * We go first, initialize our map with all elements and
831 * send the first Bloom filter.
833 * @param op operation to start exchange for
836 begin_bf_exchange (struct Operation *op)
838 op->state->phase = PHASE_BF_EXCHANGE;
839 op->state->my_elements
840 = GNUNET_CONTAINER_multihashmap_create (op->state->my_element_count,
842 GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->content->elements,
843 &initialize_map_unfiltered,
845 send_bloomfilter (op);
850 * Handle the initial `struct IntersectionElementInfoMessage` from a
853 * @param cls the intersection operation
854 * @param mh the header of the message
857 handle_p2p_element_info (void *cls,
858 const struct GNUNET_MessageHeader *mh)
860 struct Operation *op = cls;
861 const struct IntersectionElementInfoMessage *msg;
863 if (ntohs (mh->size) != sizeof (struct IntersectionElementInfoMessage))
866 fail_intersection_operation(op);
869 msg = (const struct IntersectionElementInfoMessage *) mh;
870 op->spec->remote_element_count = ntohl (msg->sender_element_count);
871 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
872 "Received remote element count (%u), I have %u\n",
873 op->spec->remote_element_count,
874 op->state->my_element_count);
875 if ( ( (PHASE_INITIAL != op->state->phase) &&
876 (PHASE_COUNT_SENT != op->state->phase) ) ||
877 (op->state->my_element_count > op->spec->remote_element_count) ||
878 (0 == op->state->my_element_count) ||
879 (0 == op->spec->remote_element_count) )
882 fail_intersection_operation(op);
885 GNUNET_break (NULL == op->state->remote_bf);
886 begin_bf_exchange (op);
891 * Send a result message to the client indicating that the operation
892 * is over. After the result done message has been sent to the
893 * client, destroy the evaluate operation.
895 * @param op intersection operation
898 finish_and_destroy (struct Operation *op)
900 GNUNET_assert (GNUNET_NO == op->state->client_done_sent);
902 if (GNUNET_SET_RESULT_FULL == op->spec->result_mode)
904 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
905 "Sending full result set (%u elements)\n",
906 GNUNET_CONTAINER_multihashmap_size (op->state->my_elements));
907 op->state->full_result_iter
908 = GNUNET_CONTAINER_multihashmap_iterator_create (op->state->my_elements);
910 send_remaining_elements (op);
913 send_client_done_and_destroy (op);
918 * Remove all elements from our hashmap.
920 * @param cls closure with the `struct Operation *`
921 * @param key current key code
922 * @param value value in the hash map
923 * @return #GNUNET_YES (we should continue to iterate)
926 filter_all (void *cls,
927 const struct GNUNET_HashCode *key,
930 struct Operation *op = cls;
931 struct ElementEntry *ee = value;
933 GNUNET_break (0 < op->state->my_element_count);
934 op->state->my_element_count--;
935 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
938 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
939 "Final reduction of my_elements, removing %s:%u\n",
940 GNUNET_h2s (&ee->element_hash),
942 GNUNET_assert (GNUNET_YES ==
943 GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements,
946 send_client_removed_element (op,
953 * Handle a done message from a remote peer
955 * @param cls the intersection operation
956 * @param mh the message
959 handle_p2p_done (void *cls,
960 const struct GNUNET_MessageHeader *mh)
962 struct Operation *op = cls;
963 const struct IntersectionDoneMessage *idm;
965 if (PHASE_BF_EXCHANGE != op->state->phase)
967 /* wrong phase to conclude? FIXME: Or should we allow this
968 if the other peer has _initially_ already an empty set? */
970 fail_intersection_operation (op);
973 if (ntohs (mh->size) != sizeof (struct IntersectionDoneMessage))
976 fail_intersection_operation (op);
979 idm = (const struct IntersectionDoneMessage *) mh;
980 if (0 == ntohl (idm->final_element_count))
982 /* other peer determined empty set is the intersection,
983 remove all elements */
984 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
988 if ( (op->state->my_element_count != ntohl (idm->final_element_count)) ||
989 (0 != memcmp (&op->state->my_xor,
990 &idm->element_xor_hash,
991 sizeof (struct GNUNET_HashCode))) )
993 /* Other peer thinks we are done, but we disagree on the result! */
995 fail_intersection_operation (op);
998 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
999 "Got IntersectionDoneMessage, have %u elements in intersection\n",
1000 op->state->my_element_count);
1001 op->state->phase = PHASE_FINISHED;
1002 finish_and_destroy (op);
1007 * Initiate a set intersection operation with a remote peer.
1009 * @param op operation that is created, should be initialized to
1010 * begin the evaluation
1011 * @param opaque_context message to be transmitted to the listener
1012 * to convince him to accept, may be NULL
1015 intersection_evaluate (struct Operation *op,
1016 const struct GNUNET_MessageHeader *opaque_context)
1018 struct GNUNET_MQ_Envelope *ev;
1019 struct OperationRequestMessage *msg;
1021 op->state = GNUNET_new (struct OperationState);
1022 /* we started the operation, thus we have to send the operation request */
1023 op->state->phase = PHASE_INITIAL;
1024 op->state->my_element_count = op->spec->set->state->current_set_element_count;
1026 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1027 "Initiating intersection operation evaluation\n");
1028 ev = GNUNET_MQ_msg_nested_mh (msg,
1029 GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST,
1033 /* the context message is too large!? */
1035 GNUNET_SERVER_client_disconnect (op->spec->set->client);
1038 msg->operation = htonl (GNUNET_SET_OPERATION_INTERSECTION);
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;