2 This file is part of GNUnet
3 Copyright (C) 2013-2017 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"
31 #include "gnunet-service-set_intersection.h"
36 * Current phase we are in for a intersection operation.
38 enum IntersectionOperationPhase
41 * We are just starting.
46 * We have send the number of our elements to the other
47 * peer, but did not setup our element set yet.
52 * We have initialized our set and are now reducing it by exchanging
53 * Bloom filters until one party notices the their element hashes
59 * The protocol is over. Results may still have to be sent to the
68 * State of an evaluate operation with another peer.
73 * The bf we currently receive
75 struct GNUNET_CONTAINER_BloomFilter *remote_bf;
78 * BF of the set's element.
80 struct GNUNET_CONTAINER_BloomFilter *local_bf;
83 * Remaining elements in the intersection operation.
84 * Maps element-id-hashes to 'elements in our set'.
86 struct GNUNET_CONTAINER_MultiHashMap *my_elements;
89 * Iterator for sending the final set of @e my_elements to the client.
91 struct GNUNET_CONTAINER_MultiHashMapIterator *full_result_iter;
94 * Evaluate operations are held in a linked list.
96 struct OperationState *next;
99 * Evaluate operations are held in a linked list.
101 struct OperationState *prev;
104 * For multipart BF transmissions, we have to store the
105 * bloomfilter-data until we fully received it.
110 * XOR of the keys of all of the elements (remaining) in my set.
111 * Always updated when elements are added or removed to
114 struct GNUNET_HashCode my_xor;
117 * XOR of the keys of all of the elements (remaining) in
118 * the other peer's set. Updated when we receive the
119 * other peer's Bloom filter.
121 struct GNUNET_HashCode other_xor;
124 * How many bytes of @e bf_data are valid?
126 uint32_t bf_data_offset;
129 * Current element count contained within @e my_elements.
130 * (May differ briefly during initialization.)
132 uint32_t my_element_count;
135 * size of the bloomfilter in @e bf_data.
137 uint32_t bf_data_size;
140 * size of the bloomfilter
142 uint32_t bf_bits_per_element;
145 * Salt currently used for BF construction (by us or the other peer,
146 * depending on where we are in the code).
151 * Current state of the operation.
153 enum IntersectionOperationPhase phase;
156 * Generation in which the operation handle
159 unsigned int generation_created;
162 * Did we send the client that we are done?
164 int client_done_sent;
169 * Extra state required for efficient set intersection.
170 * Merely tracks the total number of elements.
175 * Number of currently valid elements in the set which have not been
178 uint32_t current_set_element_count;
183 * If applicable in the current operation mode, send a result message
184 * to the client indicating we removed an element.
186 * @param op intersection operation
187 * @param element element to send
190 send_client_removed_element (struct Operation *op,
191 struct GNUNET_SET_Element *element)
193 struct GNUNET_MQ_Envelope *ev;
194 struct GNUNET_SET_ResultMessage *rm;
196 if (GNUNET_SET_RESULT_REMOVED != op->spec->result_mode)
197 return; /* Wrong mode for transmitting removed elements */
198 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
199 "Sending removed element (size %u) to client\n",
201 GNUNET_assert (0 != op->spec->client_request_id);
202 ev = GNUNET_MQ_msg_extra (rm,
204 GNUNET_MESSAGE_TYPE_SET_RESULT);
210 rm->result_status = htons (GNUNET_SET_STATUS_OK);
211 rm->request_id = htonl (op->spec->client_request_id);
212 rm->element_type = element->element_type;
213 GNUNET_memcpy (&rm[1],
216 GNUNET_MQ_send (op->spec->set->client_mq,
222 * Fills the "my_elements" hashmap with all relevant elements.
224 * @param cls the `struct Operation *` we are performing
225 * @param key current key code
226 * @param value the `struct ElementEntry *` from the hash map
227 * @return #GNUNET_YES (we should continue to iterate)
230 filtered_map_initialization (void *cls,
231 const struct GNUNET_HashCode *key,
234 struct Operation *op = cls;
235 struct ElementEntry *ee = value;
236 struct GNUNET_HashCode mutated_hash;
239 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
240 "FIMA called for %s:%u\n",
241 GNUNET_h2s (&ee->element_hash),
244 if (GNUNET_NO == _GSS_is_element_of_operation (ee, op))
246 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
247 "Reduced initialization, not starting with %s:%u (wrong generation)\n",
248 GNUNET_h2s (&ee->element_hash),
250 return GNUNET_YES; /* element not valid in our operation's generation */
253 /* Test if element is in other peer's bloomfilter */
254 GNUNET_BLOCK_mingle_hash (&ee->element_hash,
257 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
258 "Testing mingled hash %s with salt %u\n",
259 GNUNET_h2s (&mutated_hash),
262 GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf,
265 /* remove this element */
266 send_client_removed_element (op,
268 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
269 "Reduced initialization, not starting with %s:%u\n",
270 GNUNET_h2s (&ee->element_hash),
274 op->state->my_element_count++;
275 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
278 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
279 "Filtered initialization of my_elements, adding %s:%u\n",
280 GNUNET_h2s (&ee->element_hash),
282 GNUNET_break (GNUNET_YES ==
283 GNUNET_CONTAINER_multihashmap_put (op->state->my_elements,
286 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
293 * Removes elements from our hashmap if they are not contained within the
294 * provided remote bloomfilter.
296 * @param cls closure with the `struct Operation *`
297 * @param key current key code
298 * @param value value in the hash map
299 * @return #GNUNET_YES (we should continue to iterate)
302 iterator_bf_reduce (void *cls,
303 const struct GNUNET_HashCode *key,
306 struct Operation *op = cls;
307 struct ElementEntry *ee = value;
308 struct GNUNET_HashCode mutated_hash;
310 GNUNET_BLOCK_mingle_hash (&ee->element_hash,
313 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
314 "Testing mingled hash %s with salt %u\n",
315 GNUNET_h2s (&mutated_hash),
318 GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf,
321 GNUNET_break (0 < op->state->my_element_count);
322 op->state->my_element_count--;
323 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
326 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
327 "Bloom filter reduction of my_elements, removing %s:%u\n",
328 GNUNET_h2s (&ee->element_hash),
330 GNUNET_assert (GNUNET_YES ==
331 GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements,
334 send_client_removed_element (op,
339 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
340 "Bloom filter reduction of my_elements, keeping %s:%u\n",
341 GNUNET_h2s (&ee->element_hash),
349 * Create initial bloomfilter based on all the elements given.
351 * @param cls the `struct Operation *`
352 * @param key current key code
353 * @param value the `struct ElementEntry` to process
354 * @return #GNUNET_YES (we should continue to iterate)
357 iterator_bf_create (void *cls,
358 const struct GNUNET_HashCode *key,
361 struct Operation *op = cls;
362 struct ElementEntry *ee = value;
363 struct GNUNET_HashCode mutated_hash;
365 GNUNET_BLOCK_mingle_hash (&ee->element_hash,
368 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
369 "Initializing BF with hash %s with salt %u\n",
370 GNUNET_h2s (&mutated_hash),
372 GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf,
379 * Inform the client that the intersection operation has failed,
380 * and proceed to destroy the evaluate operation.
382 * @param op the intersection operation to fail
385 fail_intersection_operation (struct Operation *op)
387 struct GNUNET_MQ_Envelope *ev;
388 struct GNUNET_SET_ResultMessage *msg;
390 GNUNET_log (GNUNET_ERROR_TYPE_WARNING,
391 "Intersection operation failed\n");
392 if (NULL != op->state->my_elements)
394 GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements);
395 op->state->my_elements = NULL;
397 ev = GNUNET_MQ_msg (msg,
398 GNUNET_MESSAGE_TYPE_SET_RESULT);
399 msg->result_status = htons (GNUNET_SET_STATUS_FAILURE);
400 msg->request_id = htonl (op->spec->client_request_id);
401 msg->element_type = htons (0);
402 GNUNET_MQ_send (op->spec->set->client_mq,
404 _GSS_operation_destroy (op,
410 * Send a bloomfilter to our peer. After the result done message has
411 * been sent to the client, destroy the evaluate operation.
413 * @param op intersection operation
416 send_bloomfilter (struct Operation *op)
418 struct GNUNET_MQ_Envelope *ev;
419 struct BFMessage *msg;
421 uint32_t bf_elementbits;
426 /* We consider the ratio of the set sizes to determine
427 the number of bits per element, as the smaller set
428 should use more bits to maximize its set reduction
429 potential and minimize overall bandwidth consumption. */
430 bf_elementbits = 2 + ceil (log2((double)
431 (op->spec->remote_element_count /
432 (double) op->state->my_element_count)));
433 if (bf_elementbits < 1)
434 bf_elementbits = 1; /* make sure k is not 0 */
435 /* optimize BF-size to ~50% of bits set */
436 bf_size = ceil ((double) (op->state->my_element_count
437 * bf_elementbits / log(2)));
438 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
439 "Sending Bloom filter (%u) of size %u bytes\n",
440 (unsigned int) bf_elementbits,
441 (unsigned int) bf_size);
442 op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL,
445 op->state->salt = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
447 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
451 /* send our Bloom filter */
452 chunk_size = 60 * 1024 - sizeof (struct BFMessage);
453 if (bf_size <= chunk_size)
456 chunk_size = bf_size;
457 ev = GNUNET_MQ_msg_extra (msg,
459 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
460 GNUNET_assert (GNUNET_SYSERR !=
461 GNUNET_CONTAINER_bloomfilter_get_raw_data (op->state->local_bf,
464 msg->sender_element_count = htonl (op->state->my_element_count);
465 msg->bloomfilter_total_length = htonl (bf_size);
466 msg->bits_per_element = htonl (bf_elementbits);
467 msg->sender_mutator = htonl (op->state->salt);
468 msg->element_xor_hash = op->state->my_xor;
469 GNUNET_MQ_send (op->mq, ev);
474 bf_data = GNUNET_malloc (bf_size);
475 GNUNET_assert (GNUNET_SYSERR !=
476 GNUNET_CONTAINER_bloomfilter_get_raw_data (op->state->local_bf,
480 while (offset < bf_size)
482 if (bf_size - chunk_size < offset)
483 chunk_size = bf_size - offset;
484 ev = GNUNET_MQ_msg_extra (msg,
486 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
487 GNUNET_memcpy (&msg[1],
490 offset += chunk_size;
491 msg->sender_element_count = htonl (op->state->my_element_count);
492 msg->bloomfilter_total_length = htonl (bf_size);
493 msg->bits_per_element = htonl (bf_elementbits);
494 msg->sender_mutator = htonl (op->state->salt);
495 msg->element_xor_hash = op->state->my_xor;
496 GNUNET_MQ_send (op->mq, ev);
498 GNUNET_free (bf_data);
500 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
501 op->state->local_bf = NULL;
506 * Signal to the client that the operation has finished and
507 * destroy the operation.
509 * @param cls operation to destroy
512 send_client_done_and_destroy (void *cls)
514 struct Operation *op = cls;
515 struct GNUNET_MQ_Envelope *ev;
516 struct GNUNET_SET_ResultMessage *rm;
518 ev = GNUNET_MQ_msg (rm,
519 GNUNET_MESSAGE_TYPE_SET_RESULT);
520 rm->request_id = htonl (op->spec->client_request_id);
521 rm->result_status = htons (GNUNET_SET_STATUS_DONE);
522 rm->element_type = htons (0);
523 GNUNET_MQ_send (op->spec->set->client_mq,
525 _GSS_operation_destroy (op,
531 * Send all elements in the full result iterator.
533 * @param cls the `struct Operation *`
536 send_remaining_elements (void *cls)
538 struct Operation *op = cls;
540 const struct ElementEntry *ee;
541 struct GNUNET_MQ_Envelope *ev;
542 struct GNUNET_SET_ResultMessage *rm;
543 const struct GNUNET_SET_Element *element;
546 res = GNUNET_CONTAINER_multihashmap_iterator_next (op->state->full_result_iter,
549 if (GNUNET_NO == res)
551 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
552 "Sending done and destroy because iterator ran out\n");
554 GNUNET_CONTAINER_multihashmap_iterator_destroy (op->state->full_result_iter);
555 op->state->full_result_iter = NULL;
556 send_client_done_and_destroy (op);
560 element = &ee->element;
561 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
562 "Sending element %s:%u to client (full set)\n",
563 GNUNET_h2s (&ee->element_hash),
565 GNUNET_assert (0 != op->spec->client_request_id);
566 ev = GNUNET_MQ_msg_extra (rm,
568 GNUNET_MESSAGE_TYPE_SET_RESULT);
569 GNUNET_assert (NULL != ev);
570 rm->result_status = htons (GNUNET_SET_STATUS_OK);
571 rm->request_id = htonl (op->spec->client_request_id);
572 rm->element_type = element->element_type;
573 GNUNET_memcpy (&rm[1],
576 GNUNET_MQ_notify_sent (ev,
577 &send_remaining_elements,
579 GNUNET_MQ_send (op->spec->set->client_mq,
585 * Inform the peer that this operation is complete.
587 * @param op the intersection operation to fail
590 send_peer_done (struct Operation *op)
592 struct GNUNET_MQ_Envelope *ev;
593 struct IntersectionDoneMessage *idm;
595 op->state->phase = PHASE_FINISHED;
596 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
597 "Intersection succeeded, sending DONE\n");
598 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
599 op->state->local_bf = NULL;
601 ev = GNUNET_MQ_msg (idm,
602 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE);
603 idm->final_element_count = htonl (op->state->my_element_count);
604 idm->element_xor_hash = op->state->my_xor;
605 GNUNET_MQ_send (op->mq,
611 * Process a Bloomfilter once we got all the chunks.
613 * @param op the intersection operation
616 process_bf (struct Operation *op)
618 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
619 "Received BF in phase %u, foreign count is %u, my element count is %u/%u\n",
621 op->spec->remote_element_count,
622 op->state->my_element_count,
623 GNUNET_CONTAINER_multihashmap_size (op->spec->set->content->elements));
624 switch (op->state->phase)
628 fail_intersection_operation(op);
630 case PHASE_COUNT_SENT:
631 /* This is the first BF being sent, build our initial map with
632 filtering in place */
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 * Check an BF message from a remote peer.
670 * @param cls the intersection operation
671 * @param msg the header of the message
672 * @return #GNUNET_OK if @a msg is well-formed
675 check_intersection_p2p_bf (void *cls,
676 const struct BFMessage *msg)
678 struct Operation *op = cls;
680 if (OT_INTERSECTION != op->type)
683 return GNUNET_SYSERR;
690 * Handle an BF message from a remote peer.
692 * @param cls the intersection operation
693 * @param msg the header of the message
696 handle_intersection_p2p_bf (void *cls,
697 const struct BFMessage *msg)
699 struct Operation *op = cls;
702 uint32_t bf_bits_per_element;
704 switch (op->state->phase)
708 fail_intersection_operation (op);
710 case PHASE_COUNT_SENT:
711 case PHASE_BF_EXCHANGE:
712 bf_size = ntohl (msg->bloomfilter_total_length);
713 bf_bits_per_element = ntohl (msg->bits_per_element);
714 chunk_size = htons (msg->header.size) - sizeof (struct BFMessage);
715 op->state->other_xor = msg->element_xor_hash;
716 if (bf_size == chunk_size)
718 if (NULL != op->state->bf_data)
721 fail_intersection_operation (op);
724 /* single part, done here immediately */
726 = GNUNET_CONTAINER_bloomfilter_init ((const char*) &msg[1],
728 bf_bits_per_element);
729 op->state->salt = ntohl (msg->sender_mutator);
730 op->spec->remote_element_count = ntohl (msg->sender_element_count);
734 /* multipart chunk */
735 if (NULL == op->state->bf_data)
737 /* first chunk, initialize */
738 op->state->bf_data = GNUNET_malloc (bf_size);
739 op->state->bf_data_size = bf_size;
740 op->state->bf_bits_per_element = bf_bits_per_element;
741 op->state->bf_data_offset = 0;
742 op->state->salt = ntohl (msg->sender_mutator);
743 op->spec->remote_element_count = ntohl (msg->sender_element_count);
748 if ( (op->state->bf_data_size != bf_size) ||
749 (op->state->bf_bits_per_element != bf_bits_per_element) ||
750 (op->state->bf_data_offset + chunk_size > bf_size) ||
751 (op->state->salt != ntohl (msg->sender_mutator)) ||
752 (op->spec->remote_element_count != ntohl (msg->sender_element_count)) )
755 fail_intersection_operation (op);
759 GNUNET_memcpy (&op->state->bf_data[op->state->bf_data_offset],
760 (const char*) &msg[1],
762 op->state->bf_data_offset += chunk_size;
763 if (op->state->bf_data_offset == bf_size)
765 /* last chunk, run! */
767 = GNUNET_CONTAINER_bloomfilter_init (op->state->bf_data,
769 bf_bits_per_element);
770 GNUNET_free (op->state->bf_data);
771 op->state->bf_data = NULL;
772 op->state->bf_data_size = 0;
778 fail_intersection_operation (op);
781 GNUNET_CADET_receive_done (op->channel);
786 * Fills the "my_elements" hashmap with the initial set of
787 * (non-deleted) elements from the set of the specification.
789 * @param cls closure with the `struct Operation *`
790 * @param key current key code for the element
791 * @param value value in the hash map with the `struct ElementEntry *`
792 * @return #GNUNET_YES (we should continue to iterate)
795 initialize_map_unfiltered (void *cls,
796 const struct GNUNET_HashCode *key,
799 struct ElementEntry *ee = value;
800 struct Operation *op = cls;
802 if (GNUNET_NO == _GSS_is_element_of_operation (ee, op))
803 return GNUNET_YES; /* element not live in operation's generation */
804 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
807 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
808 "Initial full initialization of my_elements, adding %s:%u\n",
809 GNUNET_h2s (&ee->element_hash),
811 GNUNET_break (GNUNET_YES ==
812 GNUNET_CONTAINER_multihashmap_put (op->state->my_elements,
815 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
821 * Send our element count to the peer, in case our element count is
824 * @param op intersection operation
827 send_element_count (struct Operation *op)
829 struct GNUNET_MQ_Envelope *ev;
830 struct IntersectionElementInfoMessage *msg;
832 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
833 "Sending our element count (%u)\n",
834 op->state->my_element_count);
835 ev = GNUNET_MQ_msg (msg,
836 GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO);
837 msg->sender_element_count = htonl (op->state->my_element_count);
838 GNUNET_MQ_send (op->mq, ev);
843 * We go first, initialize our map with all elements and
844 * send the first Bloom filter.
846 * @param op operation to start exchange for
849 begin_bf_exchange (struct Operation *op)
851 op->state->phase = PHASE_BF_EXCHANGE;
852 GNUNET_assert (NULL == op->state->my_elements);
853 op->state->my_elements
854 = GNUNET_CONTAINER_multihashmap_create (op->state->my_element_count,
856 GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->content->elements,
857 &initialize_map_unfiltered,
859 send_bloomfilter (op);
864 * Handle the initial `struct IntersectionElementInfoMessage` from a
867 * @param cls the intersection operation
868 * @param mh the header of the message
871 handle_intersection_p2p_element_info (void *cls,
872 const struct IntersectionElementInfoMessage *msg)
874 struct Operation *op = cls;
876 if (OT_INTERSECTION != op->type)
879 fail_intersection_operation(op);
882 op->spec->remote_element_count = ntohl (msg->sender_element_count);
883 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
884 "Received remote element count (%u), I have %u\n",
885 op->spec->remote_element_count,
886 op->state->my_element_count);
887 if ( ( (PHASE_INITIAL != op->state->phase) &&
888 (PHASE_COUNT_SENT != op->state->phase) ) ||
889 (op->state->my_element_count > op->spec->remote_element_count) ||
890 (0 == op->state->my_element_count) ||
891 (0 == op->spec->remote_element_count) )
894 fail_intersection_operation(op);
897 GNUNET_break (NULL == op->state->remote_bf);
898 begin_bf_exchange (op);
899 GNUNET_CADET_receive_done (op->channel);
904 * Send a result message to the client indicating that the operation
905 * is over. After the result done message has been sent to the
906 * client, destroy the evaluate operation.
908 * @param op intersection operation
911 finish_and_destroy (struct Operation *op)
913 GNUNET_assert (GNUNET_NO == op->state->client_done_sent);
915 if (GNUNET_SET_RESULT_FULL == op->spec->result_mode)
917 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
918 "Sending full result set (%u elements)\n",
919 GNUNET_CONTAINER_multihashmap_size (op->state->my_elements));
920 op->state->full_result_iter
921 = GNUNET_CONTAINER_multihashmap_iterator_create (op->state->my_elements);
923 send_remaining_elements (op);
926 send_client_done_and_destroy (op);
931 * Remove all elements from our hashmap.
933 * @param cls closure with the `struct Operation *`
934 * @param key current key code
935 * @param value value in the hash map
936 * @return #GNUNET_YES (we should continue to iterate)
939 filter_all (void *cls,
940 const struct GNUNET_HashCode *key,
943 struct Operation *op = cls;
944 struct ElementEntry *ee = value;
946 GNUNET_break (0 < op->state->my_element_count);
947 op->state->my_element_count--;
948 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
951 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
952 "Final reduction of my_elements, removing %s:%u\n",
953 GNUNET_h2s (&ee->element_hash),
955 GNUNET_assert (GNUNET_YES ==
956 GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements,
959 send_client_removed_element (op,
966 * Handle a done message from a remote peer
968 * @param cls the intersection operation
969 * @param mh the message
972 handle_intersection_p2p_done (void *cls,
973 const struct IntersectionDoneMessage *idm)
975 struct Operation *op = cls;
977 if (OT_INTERSECTION != op->type)
980 fail_intersection_operation(op);
983 if (PHASE_BF_EXCHANGE != op->state->phase)
985 /* wrong phase to conclude? FIXME: Or should we allow this
986 if the other peer has _initially_ already an empty set? */
988 fail_intersection_operation (op);
991 if (0 == ntohl (idm->final_element_count))
993 /* other peer determined empty set is the intersection,
994 remove all elements */
995 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
999 if ( (op->state->my_element_count != ntohl (idm->final_element_count)) ||
1000 (0 != memcmp (&op->state->my_xor,
1001 &idm->element_xor_hash,
1002 sizeof (struct GNUNET_HashCode))) )
1004 /* Other peer thinks we are done, but we disagree on the result! */
1005 GNUNET_break_op (0);
1006 fail_intersection_operation (op);
1009 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1010 "Got IntersectionDoneMessage, have %u elements in intersection\n",
1011 op->state->my_element_count);
1012 op->state->phase = PHASE_FINISHED;
1013 finish_and_destroy (op);
1014 GNUNET_CADET_receive_done (op->channel);
1019 * Initiate a set intersection operation with a remote peer.
1021 * @param op operation that is created, should be initialized to
1022 * begin the evaluation
1023 * @param opaque_context message to be transmitted to the listener
1024 * to convince him to accept, may be NULL
1027 intersection_evaluate (struct Operation *op,
1028 const struct GNUNET_MessageHeader *opaque_context)
1030 struct GNUNET_MQ_Envelope *ev;
1031 struct OperationRequestMessage *msg;
1033 op->state = GNUNET_new (struct OperationState);
1034 /* we started the operation, thus we have to send the operation request */
1035 op->state->phase = PHASE_INITIAL;
1036 op->state->my_element_count = op->spec->set->state->current_set_element_count;
1038 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1039 "Initiating intersection operation evaluation\n");
1040 ev = GNUNET_MQ_msg_nested_mh (msg,
1041 GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST,
1045 /* the context message is too large!? */
1047 GNUNET_SERVICE_client_drop (op->spec->set->client);
1050 msg->operation = htonl (GNUNET_SET_OPERATION_INTERSECTION);
1051 msg->element_count = htonl (op->state->my_element_count);
1052 GNUNET_MQ_send (op->mq,
1054 op->state->phase = PHASE_COUNT_SENT;
1055 if (NULL != opaque_context)
1056 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1057 "Sent op request with context message\n");
1059 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1060 "Sent op request without context message\n");
1065 * Accept an intersection operation request from a remote peer. Only
1066 * initializes the private operation state.
1068 * @param op operation that will be accepted as an intersection operation
1071 intersection_accept (struct Operation *op)
1073 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1074 "Accepting set intersection operation\n");
1075 op->state = GNUNET_new (struct OperationState);
1076 op->state->phase = PHASE_INITIAL;
1077 op->state->my_element_count
1078 = op->spec->set->state->current_set_element_count;
1079 GNUNET_assert (NULL == op->state->my_elements);
1080 op->state->my_elements
1081 = GNUNET_CONTAINER_multihashmap_create (GNUNET_MIN (op->state->my_element_count,
1082 op->spec->remote_element_count),
1084 if (op->spec->remote_element_count < op->state->my_element_count)
1086 /* If the other peer (Alice) has fewer elements than us (Bob),
1087 we just send the count as Alice should send the first BF */
1088 send_element_count (op);
1089 op->state->phase = PHASE_COUNT_SENT;
1092 /* We have fewer elements, so we start with the BF */
1093 begin_bf_exchange (op);
1098 * Handler for peer-disconnects, notifies the client about the aborted
1099 * operation. If we did not expect anything from the other peer, we
1100 * gracefully terminate the operation.
1102 * @param op the destroyed operation
1105 intersection_peer_disconnect (struct Operation *op)
1107 if (PHASE_FINISHED != op->state->phase)
1109 fail_intersection_operation (op);
1112 /* the session has already been concluded */
1113 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1114 "Other peer disconnected (finished)\n");
1115 if (GNUNET_NO == op->state->client_done_sent)
1116 finish_and_destroy (op);
1121 * Destroy the intersection operation. Only things specific to the
1122 * intersection operation are destroyed.
1124 * @param op intersection operation to destroy
1127 intersection_op_cancel (struct Operation *op)
1129 /* check if the op was canceled twice */
1130 GNUNET_assert (NULL != op->state);
1131 if (NULL != op->state->remote_bf)
1133 GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf);
1134 op->state->remote_bf = NULL;
1136 if (NULL != op->state->local_bf)
1138 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
1139 op->state->local_bf = NULL;
1141 if (NULL != op->state->my_elements)
1143 GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements);
1144 op->state->my_elements = NULL;
1146 if (NULL != op->state->full_result_iter)
1148 GNUNET_CONTAINER_multihashmap_iterator_destroy (op->state->full_result_iter);
1149 op->state->full_result_iter = NULL;
1151 GNUNET_free (op->state);
1153 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1154 "Destroying intersection op state done\n");
1159 * Create a new set supporting the intersection operation.
1161 * @return the newly created set
1163 static struct SetState *
1164 intersection_set_create ()
1166 struct SetState *set_state;
1168 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
1169 "Intersection set created\n");
1170 set_state = GNUNET_new (struct SetState);
1171 set_state->current_set_element_count = 0;
1178 * Add the element from the given element message to the set.
1180 * @param set_state state of the set want to add to
1181 * @param ee the element to add to the set
1184 intersection_add (struct SetState *set_state,
1185 struct ElementEntry *ee)
1187 set_state->current_set_element_count++;
1192 * Destroy a set that supports the intersection operation
1194 * @param set_state the set to destroy
1197 intersection_set_destroy (struct SetState *set_state)
1199 GNUNET_free (set_state);
1204 * Remove the element given in the element message from the set.
1206 * @param set_state state of the set to remove from
1207 * @param element set element to remove
1210 intersection_remove (struct SetState *set_state,
1211 struct ElementEntry *element)
1213 GNUNET_assert (0 < set_state->current_set_element_count);
1214 set_state->current_set_element_count--;
1219 * Get the table with implementing functions for set intersection.
1221 * @return the operation specific VTable
1223 const struct SetVT *
1224 _GSS_intersection_vt ()
1226 static const struct SetVT intersection_vt = {
1227 .create = &intersection_set_create,
1228 .add = &intersection_add,
1229 .remove = &intersection_remove,
1230 .destroy_set = &intersection_set_destroy,
1231 .evaluate = &intersection_evaluate,
1232 .accept = &intersection_accept,
1233 .peer_disconnect = &intersection_peer_disconnect,
1234 .cancel = &intersection_op_cancel,
1237 return &intersection_vt;