GNUnet 0.21.2
gnunet-service-set_intersection.c
Go to the documentation of this file.
1/*
2 This file is part of GNUnet
3 Copyright (C) 2013-2017 GNUnet e.V.
4
5 GNUnet is free software: you can redistribute it and/or modify it
6 under the terms of the GNU Affero General Public License as published
7 by the Free Software Foundation, either version 3 of the License,
8 or (at your option) any later version.
9
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 Affero General Public License for more details.
14
15 You should have received a copy of the GNU Affero General Public License
16 along with this program. If not, see <http://www.gnu.org/licenses/>.
17
18 SPDX-License-Identifier: AGPL3.0-or-later
19 */
26#include "platform.h"
27#include "gnunet_util_lib.h"
29#include "gnunet-service-set.h"
30#include "gnunet_block_lib.h"
33#include <gcrypt.h>
34
35
40{
45
51
58
64
70
76};
77
78
83{
88
93
99
104
109
114
119 char *bf_data;
120
127
134
139
145
149 uint32_t bf_data_size;
150
155
160 uint32_t salt;
161
166
171 unsigned int generation_created;
172
177
184};
185
186
192{
198};
199
200
208static void
210 struct GNUNET_SET_Element *element)
211{
212 struct GNUNET_MQ_Envelope *ev;
213 struct GNUNET_SET_ResultMessage *rm;
214
215 if (GNUNET_SET_RESULT_REMOVED != op->result_mode)
216 return; /* Wrong mode for transmitting removed elements */
218 "Sending removed element (size %u) to client\n",
219 element->size);
221 "# Element removed messages sent",
222 1,
223 GNUNET_NO);
224 GNUNET_assert (0 != op->client_request_id);
225 ev = GNUNET_MQ_msg_extra (rm,
226 element->size,
228 if (NULL == ev)
229 {
230 GNUNET_break (0);
231 return;
232 }
234 rm->request_id = htonl (op->client_request_id);
235 rm->element_type = element->element_type;
236 GNUNET_memcpy (&rm[1],
237 element->data,
238 element->size);
239 GNUNET_MQ_send (op->set->cs->mq,
240 ev);
241}
242
243
252static int
254 const struct GNUNET_HashCode *key,
255 void *value)
256{
257 struct Operation *op = cls;
258 struct ElementEntry *ee = value;
259 struct GNUNET_HashCode mutated_hash;
260
261
263 "FIMA called for %s:%u\n",
265 ee->element.size);
266
268 {
270 "Reduced initialization, not starting with %s:%u (wrong generation)\n",
272 ee->element.size);
273 return GNUNET_YES; /* element not valid in our operation's generation */
274 }
275
276 /* Test if element is in other peer's bloomfilter */
278 op->state->salt,
279 &mutated_hash);
281 "Testing mingled hash %s with salt %u\n",
282 GNUNET_h2s (&mutated_hash),
283 op->state->salt);
284 if (GNUNET_NO ==
285 GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf,
286 &mutated_hash))
287 {
288 /* remove this element */
290 &ee->element);
292 "Reduced initialization, not starting with %s:%u\n",
294 ee->element.size);
295 return GNUNET_YES;
296 }
297 op->state->my_element_count++;
298 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
299 &ee->element_hash,
300 &op->state->my_xor);
302 "Filtered initialization of my_elements, adding %s:%u\n",
304 ee->element.size);
306 GNUNET_CONTAINER_multihashmap_put (op->state->my_elements,
307 &ee->element_hash,
308 ee,
310
311 return GNUNET_YES;
312}
313
314
324static int
326 const struct GNUNET_HashCode *key,
327 void *value)
328{
329 struct Operation *op = cls;
330 struct ElementEntry *ee = value;
331 struct GNUNET_HashCode mutated_hash;
332
334 op->state->salt,
335 &mutated_hash);
337 "Testing mingled hash %s with salt %u\n",
338 GNUNET_h2s (&mutated_hash),
339 op->state->salt);
340 if (GNUNET_NO ==
341 GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf,
342 &mutated_hash))
343 {
344 GNUNET_break (0 < op->state->my_element_count);
345 op->state->my_element_count--;
346 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
347 &ee->element_hash,
348 &op->state->my_xor);
350 "Bloom filter reduction of my_elements, removing %s:%u\n",
352 ee->element.size);
354 GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements,
355 &ee->element_hash,
356 ee));
358 &ee->element);
359 }
360 else
361 {
363 "Bloom filter reduction of my_elements, keeping %s:%u\n",
365 ee->element.size);
366 }
367 return GNUNET_YES;
368}
369
370
379static int
381 const struct GNUNET_HashCode *key,
382 void *value)
383{
384 struct Operation *op = cls;
385 struct ElementEntry *ee = value;
386 struct GNUNET_HashCode mutated_hash;
387
389 op->state->salt,
390 &mutated_hash);
392 "Initializing BF with hash %s with salt %u\n",
393 GNUNET_h2s (&mutated_hash),
394 op->state->salt);
395 GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf,
396 &mutated_hash);
397 return GNUNET_YES;
398}
399
400
407static void
409{
410 struct GNUNET_MQ_Envelope *ev;
412
414 "Intersection operation failed\n");
416 "# Intersection operations failed",
417 1,
418 GNUNET_NO);
419 if (NULL != op->state->my_elements)
420 {
421 GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements);
422 op->state->my_elements = NULL;
423 }
424 ev = GNUNET_MQ_msg (msg,
426 msg->result_status = htons (GNUNET_SET_STATUS_FAILURE);
427 msg->request_id = htonl (op->client_request_id);
428 msg->element_type = htons (0);
429 GNUNET_MQ_send (op->set->cs->mq,
430 ev);
432 GNUNET_YES);
433}
434
435
442static void
444{
445 struct GNUNET_MQ_Envelope *ev;
446 struct BFMessage *msg;
447 uint32_t bf_size;
448 uint32_t bf_elementbits;
449 uint32_t chunk_size;
450 char *bf_data;
451 uint32_t offset;
452
453 /* We consider the ratio of the set sizes to determine
454 the number of bits per element, as the smaller set
455 should use more bits to maximize its set reduction
456 potential and minimize overall bandwidth consumption. */
457 bf_elementbits = 2 + ceil (log2 ((double)
458 (op->remote_element_count
459 / (double) op->state->my_element_count)));
460 if (bf_elementbits < 1)
461 bf_elementbits = 1; /* make sure k is not 0 */
462 /* optimize BF-size to ~50% of bits set */
463 bf_size = ceil ((double) (op->state->my_element_count
464 * bf_elementbits / log (2)));
466 "Sending Bloom filter (%u) of size %u bytes\n",
467 (unsigned int) bf_elementbits,
468 (unsigned int) bf_size);
469 op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL,
470 bf_size,
471 bf_elementbits);
473 UINT32_MAX);
474 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
476 op);
477
478 /* send our Bloom filter */
480 "# Intersection Bloom filters sent",
481 1,
482 GNUNET_NO);
483 chunk_size = 60 * 1024 - sizeof(struct BFMessage);
484 if (bf_size <= chunk_size)
485 {
486 /* singlepart */
487 chunk_size = bf_size;
489 chunk_size,
493 op->state->local_bf,
494 (char *) &msg[1],
495 bf_size));
496 msg->sender_element_count = htonl (op->state->my_element_count);
497 msg->bloomfilter_total_length = htonl (bf_size);
498 msg->bits_per_element = htonl (bf_elementbits);
499 msg->sender_mutator = htonl (op->state->salt);
500 msg->element_xor_hash = op->state->my_xor;
501 GNUNET_MQ_send (op->mq, ev);
502 }
503 else
504 {
505 /* multipart */
506 bf_data = GNUNET_malloc (bf_size);
509 op->state->local_bf,
510 bf_data,
511 bf_size));
512 offset = 0;
513 while (offset < bf_size)
514 {
515 if (bf_size - chunk_size < offset)
516 chunk_size = bf_size - offset;
518 chunk_size,
520 GNUNET_memcpy (&msg[1],
521 &bf_data[offset],
522 chunk_size);
523 offset += chunk_size;
524 msg->sender_element_count = htonl (op->state->my_element_count);
525 msg->bloomfilter_total_length = htonl (bf_size);
526 msg->bits_per_element = htonl (bf_elementbits);
527 msg->sender_mutator = htonl (op->state->salt);
528 msg->element_xor_hash = op->state->my_xor;
529 GNUNET_MQ_send (op->mq, ev);
530 }
531 GNUNET_free (bf_data);
532 }
533 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
534 op->state->local_bf = NULL;
535}
536
537
544static void
546{
547 struct Operation *op = cls;
548 struct GNUNET_MQ_Envelope *ev;
549 struct GNUNET_SET_ResultMessage *rm;
550
552 "Intersection succeeded, sending DONE to local client\n");
554 "# Intersection operations succeeded",
555 1,
556 GNUNET_NO);
557 ev = GNUNET_MQ_msg (rm,
559 rm->request_id = htonl (op->client_request_id);
561 rm->element_type = htons (0);
562 GNUNET_MQ_send (op->set->cs->mq,
563 ev);
565 GNUNET_YES);
566}
567
568
577static void
579{
580 struct Operation *op = cls;
581
583 "DONE sent to other peer, now waiting for other end to close the channel\n");
584 op->state->phase = PHASE_FINISHED;
585 op->state->channel_death_expected = GNUNET_YES;
586}
587
588
596static void
598{
599 struct GNUNET_MQ_Envelope *ev;
600 struct IntersectionDoneMessage *idm;
601
602 GNUNET_assert (PHASE_MUST_SEND_DONE == op->state->phase);
603 GNUNET_assert (GNUNET_NO == op->state->channel_death_expected);
604 ev = GNUNET_MQ_msg (idm,
606 idm->final_element_count = htonl (op->state->my_element_count);
607 idm->element_xor_hash = op->state->my_xor;
610 op);
611 GNUNET_MQ_send (op->mq,
612 ev);
613}
614
615
621static void
623{
624 struct Operation *op = cls;
625 const void *nxt;
626 const struct ElementEntry *ee;
627 struct GNUNET_MQ_Envelope *ev;
628 struct GNUNET_SET_ResultMessage *rm;
629 const struct GNUNET_SET_Element *element;
630 int res;
631
633 op->state->full_result_iter,
634 NULL,
635 &nxt);
636 if (GNUNET_NO == res)
637 {
639 "Sending done and destroy because iterator ran out\n");
641 op->state->full_result_iter);
642 op->state->full_result_iter = NULL;
643 if (PHASE_DONE_RECEIVED == op->state->phase)
644 {
645 op->state->phase = PHASE_FINISHED;
647 }
648 else if (PHASE_MUST_SEND_DONE == op->state->phase)
649 {
651 }
652 else
653 {
654 GNUNET_assert (0);
655 }
656 return;
657 }
658 ee = nxt;
659 element = &ee->element;
661 "Sending element %s:%u to client (full set)\n",
663 element->size);
664 GNUNET_assert (0 != op->client_request_id);
665 ev = GNUNET_MQ_msg_extra (rm,
666 element->size,
668 GNUNET_assert (NULL != ev);
670 rm->request_id = htonl (op->client_request_id);
671 rm->element_type = element->element_type;
672 GNUNET_memcpy (&rm[1],
673 element->data,
674 element->size);
677 op);
678 GNUNET_MQ_send (op->set->cs->mq,
679 ev);
680}
681
682
692static int
694 const struct GNUNET_HashCode *key,
695 void *value)
696{
697 struct ElementEntry *ee = value;
698 struct Operation *op = cls;
699
701 return GNUNET_YES; /* element not live in operation's generation */
702 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
703 &ee->element_hash,
704 &op->state->my_xor);
706 "Initial full initialization of my_elements, adding %s:%u\n",
708 ee->element.size);
710 GNUNET_CONTAINER_multihashmap_put (op->state->my_elements,
711 &ee->element_hash,
712 ee,
714 return GNUNET_YES;
715}
716
717
724static void
726{
727 struct GNUNET_MQ_Envelope *ev;
729
731 "Sending our element count (%u)\n",
732 op->state->my_element_count);
733 ev = GNUNET_MQ_msg (msg,
735 msg->sender_element_count = htonl (op->state->my_element_count);
736 GNUNET_MQ_send (op->mq, ev);
737}
738
739
746static void
748{
749 op->state->phase = PHASE_BF_EXCHANGE;
750 GNUNET_CONTAINER_multihashmap_iterate (op->set->content->elements,
752 op);
754}
755
756
757void
759 const struct
761{
762 struct Operation *op = cls;
763
764 if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation)
765 {
766 GNUNET_break_op (0);
768 return;
769 }
770 op->remote_element_count = ntohl (msg->sender_element_count);
772 "Received remote element count (%u), I have %u\n",
773 op->remote_element_count,
774 op->state->my_element_count);
775 if (((PHASE_INITIAL != op->state->phase) &&
776 (PHASE_COUNT_SENT != op->state->phase)) ||
777 (op->state->my_element_count > op->remote_element_count) ||
778 (0 == op->state->my_element_count) ||
779 (0 == op->remote_element_count))
780 {
781 GNUNET_break_op (0);
783 return;
784 }
785 GNUNET_break (NULL == op->state->remote_bf);
787 GNUNET_CADET_receive_done (op->channel);
788}
789
790
796static void
798{
800 "Received BF in phase %u, foreign count is %u, my element count is %u/%u\n",
801 op->state->phase,
802 op->remote_element_count,
803 op->state->my_element_count,
804 GNUNET_CONTAINER_multihashmap_size (op->set->content->elements));
805 switch (op->state->phase)
806 {
807 case PHASE_INITIAL:
808 GNUNET_break_op (0);
810 return;
811
812 case PHASE_COUNT_SENT:
813 /* This is the first BF being sent, build our initial map with
814 filtering in place */
815 op->state->my_element_count = 0;
816 GNUNET_CONTAINER_multihashmap_iterate (op->set->content->elements,
818 op);
819 break;
820
822 /* Update our set by reduction */
823 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
825 op);
826 break;
827
829 GNUNET_break_op (0);
831 return;
832
834 GNUNET_break_op (0);
836 return;
837
838 case PHASE_FINISHED:
839 GNUNET_break_op (0);
841 return;
842 }
843 GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf);
844 op->state->remote_bf = NULL;
845
846 if ((0 == op->state->my_element_count) || /* fully disjoint */
847 ((op->state->my_element_count == op->remote_element_count) &&
848 (0 == GNUNET_memcmp (&op->state->my_xor,
849 &op->state->other_xor))))
850 {
851 /* we are done */
852 op->state->phase = PHASE_MUST_SEND_DONE;
854 "Intersection succeeded, sending DONE to other peer\n");
855 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
856 op->state->local_bf = NULL;
857 if (GNUNET_SET_RESULT_FULL == op->result_mode)
858 {
860 "Sending full result set (%u elements)\n",
861 GNUNET_CONTAINER_multihashmap_size (op->state->my_elements));
862 op->state->full_result_iter
864 op->state->my_elements);
866 return;
867 }
869 return;
870 }
871 op->state->phase = PHASE_BF_EXCHANGE;
873}
874
875
883int
885 const struct BFMessage *msg)
886{
887 struct Operation *op = cls;
888
889 if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation)
890 {
891 GNUNET_break_op (0);
892 return GNUNET_SYSERR;
893 }
894 return GNUNET_OK;
895}
896
897
904void
906 const struct BFMessage *msg)
907{
908 struct Operation *op = cls;
909 uint32_t bf_size;
910 uint32_t chunk_size;
911 uint32_t bf_bits_per_element;
912
913 switch (op->state->phase)
914 {
915 case PHASE_INITIAL:
916 GNUNET_break_op (0);
918 return;
919
920 case PHASE_COUNT_SENT:
922 bf_size = ntohl (msg->bloomfilter_total_length);
923 bf_bits_per_element = ntohl (msg->bits_per_element);
924 chunk_size = htons (msg->header.size) - sizeof(struct BFMessage);
925 op->state->other_xor = msg->element_xor_hash;
926 if (bf_size == chunk_size)
927 {
928 if (NULL != op->state->bf_data)
929 {
930 GNUNET_break_op (0);
932 return;
933 }
934 /* single part, done here immediately */
935 op->state->remote_bf
936 = GNUNET_CONTAINER_bloomfilter_init ((const char *) &msg[1],
937 bf_size,
938 bf_bits_per_element);
939 op->state->salt = ntohl (msg->sender_mutator);
940 op->remote_element_count = ntohl (msg->sender_element_count);
941 process_bf (op);
942 break;
943 }
944 /* multipart chunk */
945 if (NULL == op->state->bf_data)
946 {
947 /* first chunk, initialize */
948 op->state->bf_data = GNUNET_malloc (bf_size);
949 op->state->bf_data_size = bf_size;
950 op->state->bf_bits_per_element = bf_bits_per_element;
951 op->state->bf_data_offset = 0;
952 op->state->salt = ntohl (msg->sender_mutator);
953 op->remote_element_count = ntohl (msg->sender_element_count);
954 }
955 else
956 {
957 /* increment */
958 if ((op->state->bf_data_size != bf_size) ||
959 (op->state->bf_bits_per_element != bf_bits_per_element) ||
960 (op->state->bf_data_offset + chunk_size > bf_size) ||
961 (op->state->salt != ntohl (msg->sender_mutator)) ||
962 (op->remote_element_count != ntohl (msg->sender_element_count)))
963 {
964 GNUNET_break_op (0);
966 return;
967 }
968 }
969 GNUNET_memcpy (&op->state->bf_data[op->state->bf_data_offset],
970 (const char *) &msg[1],
971 chunk_size);
972 op->state->bf_data_offset += chunk_size;
973 if (op->state->bf_data_offset == bf_size)
974 {
975 /* last chunk, run! */
976 op->state->remote_bf
977 = GNUNET_CONTAINER_bloomfilter_init (op->state->bf_data,
978 bf_size,
979 bf_bits_per_element);
980 GNUNET_free (op->state->bf_data);
981 op->state->bf_data = NULL;
982 op->state->bf_data_size = 0;
983 process_bf (op);
984 }
985 break;
986
987 default:
988 GNUNET_break_op (0);
990 return;
991 }
992 GNUNET_CADET_receive_done (op->channel);
993}
994
995
1004static int
1005filter_all (void *cls,
1006 const struct GNUNET_HashCode *key,
1007 void *value)
1008{
1009 struct Operation *op = cls;
1010 struct ElementEntry *ee = value;
1011
1012 GNUNET_break (0 < op->state->my_element_count);
1013 op->state->my_element_count--;
1014 GNUNET_CRYPTO_hash_xor (&op->state->my_xor,
1015 &ee->element_hash,
1016 &op->state->my_xor);
1018 "Final reduction of my_elements, removing %s:%u\n",
1019 GNUNET_h2s (&ee->element_hash),
1020 ee->element.size);
1022 GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements,
1023 &ee->element_hash,
1024 ee));
1026 &ee->element);
1027 return GNUNET_YES;
1028}
1029
1030
1037void
1039 const struct IntersectionDoneMessage *idm)
1040{
1041 struct Operation *op = cls;
1042
1043 if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation)
1044 {
1045 GNUNET_break_op (0);
1047 return;
1048 }
1049 if (PHASE_BF_EXCHANGE != op->state->phase)
1050 {
1051 /* wrong phase to conclude? FIXME: Or should we allow this
1052 if the other peer has _initially_ already an empty set? */
1053 GNUNET_break_op (0);
1055 return;
1056 }
1057 if (0 == ntohl (idm->final_element_count))
1058 {
1059 /* other peer determined empty set is the intersection,
1060 remove all elements */
1061 GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
1062 &filter_all,
1063 op);
1064 }
1065 if ((op->state->my_element_count != ntohl (idm->final_element_count)) ||
1066 (0 != GNUNET_memcmp (&op->state->my_xor,
1067 &idm->element_xor_hash)))
1068 {
1069 /* Other peer thinks we are done, but we disagree on the result! */
1070 GNUNET_break_op (0);
1072 return;
1073 }
1075 "Got IntersectionDoneMessage, have %u elements in intersection\n",
1076 op->state->my_element_count);
1077 op->state->phase = PHASE_DONE_RECEIVED;
1078 GNUNET_CADET_receive_done (op->channel);
1079
1080 GNUNET_assert (GNUNET_NO == op->state->client_done_sent);
1081 if (GNUNET_SET_RESULT_FULL == op->result_mode)
1082 {
1084 "Sending full result set to client (%u elements)\n",
1085 GNUNET_CONTAINER_multihashmap_size (op->state->my_elements));
1086 op->state->full_result_iter
1087 = GNUNET_CONTAINER_multihashmap_iterator_create (op->state->my_elements);
1089 return;
1090 }
1091 op->state->phase = PHASE_FINISHED;
1093}
1094
1095
1105static struct OperationState *
1107 const struct GNUNET_MessageHeader *opaque_context)
1108{
1109 struct OperationState *state;
1110 struct GNUNET_MQ_Envelope *ev;
1112
1115 opaque_context);
1116 if (NULL == ev)
1117 {
1118 /* the context message is too large!? */
1119 GNUNET_break (0);
1120 return NULL;
1121 }
1123 "Initiating intersection operation evaluation\n");
1124 state = GNUNET_new (struct OperationState);
1125 /* we started the operation, thus we have to send the operation request */
1126 state->phase = PHASE_INITIAL;
1127 state->my_element_count = op->set->state->current_set_element_count;
1128 state->my_elements
1129 = GNUNET_CONTAINER_multihashmap_create (state->my_element_count,
1130 GNUNET_YES);
1131
1132 msg->operation = htonl (GNUNET_SET_OPERATION_INTERSECTION);
1133 msg->element_count = htonl (state->my_element_count);
1134 GNUNET_MQ_send (op->mq,
1135 ev);
1136 state->phase = PHASE_COUNT_SENT;
1137 if (NULL != opaque_context)
1139 "Sent op request with context message\n");
1140 else
1142 "Sent op request without context message\n");
1143 return state;
1144}
1145
1146
1153static struct OperationState *
1155{
1156 struct OperationState *state;
1157
1159 "Accepting set intersection operation\n");
1160 state = GNUNET_new (struct OperationState);
1161 state->phase = PHASE_INITIAL;
1162 state->my_element_count
1163 = op->set->state->current_set_element_count;
1164 state->my_elements
1166 op->remote_element_count),
1167 GNUNET_YES);
1168 op->state = state;
1169 if (op->remote_element_count < state->my_element_count)
1170 {
1171 /* If the other peer (Alice) has fewer elements than us (Bob),
1172 we just send the count as Alice should send the first BF */
1174 state->phase = PHASE_COUNT_SENT;
1175 return state;
1176 }
1177 /* We have fewer elements, so we start with the BF */
1179 return state;
1180}
1181
1182
1189static void
1191{
1192 /* check if the op was canceled twice */
1193 GNUNET_assert (NULL != op->state);
1194 if (NULL != op->state->remote_bf)
1195 {
1196 GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf);
1197 op->state->remote_bf = NULL;
1198 }
1199 if (NULL != op->state->local_bf)
1200 {
1201 GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
1202 op->state->local_bf = NULL;
1203 }
1204 if (NULL != op->state->my_elements)
1205 {
1206 GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements);
1207 op->state->my_elements = NULL;
1208 }
1209 if (NULL != op->state->full_result_iter)
1210 {
1212 op->state->full_result_iter);
1213 op->state->full_result_iter = NULL;
1214 }
1215 GNUNET_free (op->state);
1216 op->state = NULL;
1218 "Destroying intersection op state done\n");
1219}
1220
1221
1227static struct SetState *
1229{
1230 struct SetState *set_state;
1231
1233 "Intersection set created\n");
1234 set_state = GNUNET_new (struct SetState);
1235 set_state->current_set_element_count = 0;
1236
1237 return set_state;
1238}
1239
1240
1247static void
1248intersection_add (struct SetState *set_state,
1249 struct ElementEntry *ee)
1250{
1251 set_state->current_set_element_count++;
1252}
1253
1254
1260static void
1262{
1263 GNUNET_free (set_state);
1264}
1265
1266
1273static void
1275 struct ElementEntry *element)
1276{
1278 set_state->current_set_element_count--;
1279}
1280
1281
1287static void
1289{
1290 if (GNUNET_YES == op->state->channel_death_expected)
1291 {
1292 /* oh goodie, we are done! */
1294 }
1295 else
1296 {
1297 /* sorry, channel went down early, too bad. */
1299 GNUNET_YES);
1300 }
1301}
1302
1303
1309const struct SetVT *
1311{
1312 static const struct SetVT intersection_vt = {
1314 .add = &intersection_add,
1315 .remove = &intersection_remove,
1316 .destroy_set = &intersection_set_destroy,
1317 .evaluate = &intersection_evaluate,
1318 .accept = &intersection_accept,
1319 .cancel = &intersection_op_cancel,
1320 .channel_death = &intersection_channel_death,
1321 };
1322
1323 return &intersection_vt;
1324}
struct GNUNET_MessageHeader * msg
Definition: 005.c:2
static struct GNUNET_ARM_Operation * op
Current operation.
Definition: gnunet-arm.c:144
struct GNUNET_HashCode key
The key used in the DHT.
static char * res
Currently read line or NULL on EOF.
static char * value
Value of the record to add/remove.
enum State state
current state of profiling
int _GSS_is_element_of_operation(struct ElementEntry *ee, struct Operation *op)
Is element ee part of the set used by op?
struct GNUNET_STATISTICS_Handle * _GSS_statistics
Statistics handle.
void _GSS_operation_destroy(struct Operation *op, int gc)
Destroy the given operation.
common components for the implementation the different set operations
const struct SetVT * _GSS_intersection_vt()
Get the table with implementing functions for set intersection.
static void intersection_remove(struct SetState *set_state, struct ElementEntry *element)
Remove the element given in the element message from the set.
void handle_intersection_p2p_bf(void *cls, const struct BFMessage *msg)
Handle an BF message from a remote peer.
void handle_intersection_p2p_element_info(void *cls, const struct IntersectionElementInfoMessage *msg)
Handle the initial struct IntersectionElementInfoMessage from a remote peer.
IntersectionOperationPhase
Current phase we are in for a intersection operation.
@ PHASE_INITIAL
We are just starting.
@ PHASE_DONE_RECEIVED
We have received the P2P DONE message, and must finish with the local client before terminating the c...
@ PHASE_FINISHED
The protocol is over.
@ PHASE_BF_EXCHANGE
We have initialized our set and are now reducing it by exchanging Bloom filters until one party notic...
@ PHASE_COUNT_SENT
We have send the number of our elements to the other peer, but did not setup our element set yet.
@ PHASE_MUST_SEND_DONE
We must next send the P2P DONE message (after finishing mostly with the local client).
static int iterator_bf_reduce(void *cls, const struct GNUNET_HashCode *key, void *value)
Removes elements from our hashmap if they are not contained within the provided remote bloomfilter.
static struct SetState * intersection_set_create()
Create a new set supporting the intersection operation.
static void begin_bf_exchange(struct Operation *op)
We go first, initialize our map with all elements and send the first Bloom filter.
static void intersection_set_destroy(struct SetState *set_state)
Destroy a set that supports the intersection operation.
static int filter_all(void *cls, const struct GNUNET_HashCode *key, void *value)
Remove all elements from our hashmap.
static int filtered_map_initialization(void *cls, const struct GNUNET_HashCode *key, void *value)
Fills the "my_elements" hashmap with all relevant elements.
static void send_p2p_done(struct Operation *op)
Notify the other peer that we are done.
static void send_remaining_elements(void *cls)
Send all elements in the full result iterator.
void handle_intersection_p2p_done(void *cls, const struct IntersectionDoneMessage *idm)
Handle a done message from a remote peer.
static void fail_intersection_operation(struct Operation *op)
Inform the client that the intersection operation has failed, and proceed to destroy the evaluate ope...
static void finished_local_operations(void *cls)
Remember that we are done dealing with the local client AND have sent the other peer our message that...
int check_intersection_p2p_bf(void *cls, const struct BFMessage *msg)
Check an BF message from a remote peer.
static struct OperationState * intersection_evaluate(struct Operation *op, const struct GNUNET_MessageHeader *opaque_context)
Initiate a set intersection operation with a remote peer.
static void send_client_done_and_destroy(void *cls)
Signal to the client that the operation has finished and destroy the operation.
static int initialize_map_unfiltered(void *cls, const struct GNUNET_HashCode *key, void *value)
Fills the "my_elements" hashmap with the initial set of (non-deleted) elements from the set of the sp...
static void send_bloomfilter(struct Operation *op)
Send a bloomfilter to our peer.
static void intersection_op_cancel(struct Operation *op)
Destroy the intersection operation.
static void process_bf(struct Operation *op)
Process a Bloomfilter once we got all the chunks.
static void send_element_count(struct Operation *op)
Send our element count to the peer, in case our element count is lower than theirs.
static void intersection_add(struct SetState *set_state, struct ElementEntry *ee)
Add the element from the given element message to the set.
static void intersection_channel_death(struct Operation *op)
Callback for channel death for the intersection operation.
static void send_client_removed_element(struct Operation *op, struct GNUNET_SET_Element *element)
If applicable in the current operation mode, send a result message to the client indicating we remove...
static struct OperationState * intersection_accept(struct Operation *op)
Accept an intersection operation request from a remote peer.
static int iterator_bf_create(void *cls, const struct GNUNET_HashCode *key, void *value)
Create initial bloomfilter based on all the elements given.
two-peer set operations
Peer-to-Peer messages for gnunet set.
Library for data block manipulation.
API to create, modify and access statistics.
void GNUNET_BLOCK_mingle_hash(const struct GNUNET_HashCode *in, uint32_t mingle_number, struct GNUNET_HashCode *hc)
Mingle hash with the mingle_number to produce different bits.
Definition: block.c:96
struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_init(const char *data, size_t size, unsigned int k)
Create a Bloom filter from raw bits.
void GNUNET_CONTAINER_bloomfilter_add(struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Add an element to the filter.
bool GNUNET_CONTAINER_bloomfilter_test(const struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Test if an element is in the filter.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_bloomfilter_get_raw_data(const struct GNUNET_CONTAINER_BloomFilter *bf, char *data, size_t size)
Copy the raw data of this Bloom filter into the given data array.
void GNUNET_CONTAINER_bloomfilter_free(struct GNUNET_CONTAINER_BloomFilter *bf)
Free the space associated with a filter in memory, flush to drive if needed (do not free the space on...
void GNUNET_CADET_receive_done(struct GNUNET_CADET_Channel *channel)
Indicate readiness to receive the next message on a channel.
Definition: cadet_api.c:872
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
@ GNUNET_CRYPTO_QUALITY_NONCE
Randomness for IVs etc.
void GNUNET_CRYPTO_hash_xor(const struct GNUNET_HashCode *a, const struct GNUNET_HashCode *b, struct GNUNET_HashCode *result)
compute result = a ^ b
Definition: crypto_hash.c:135
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MultiHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multihashmap_iterator_next(struct GNUNET_CONTAINER_MultiHashMapIterator *iter, struct GNUNET_HashCode *key, const void **value)
Retrieve the next element from the hash map at the iterator's position.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multihashmap_remove(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, const void *value)
Remove the given key-value pair from the map.
enum GNUNET_GenericReturnValue GNUNET_CONTAINER_multihashmap_put(struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
unsigned int GNUNET_CONTAINER_multihashmap_size(const struct GNUNET_CONTAINER_MultiHashMap *map)
Get the number of key-value pairs in the map.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
void GNUNET_CONTAINER_multihashmap_iterator_destroy(struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
Destroy a multihashmap iterator.
struct GNUNET_CONTAINER_MultiHashMapIterator * GNUNET_CONTAINER_multihashmap_iterator_create(const struct GNUNET_CONTAINER_MultiHashMap *map)
Create an iterator for a multihashmap.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY
There must only be one value per key; storing a value should fail if a value under the same key alrea...
#define GNUNET_log(kind,...)
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_MIN(a, b)
uint16_t size
The length of the struct (in bytes, including the length field itself), in big-endian format.
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
@ GNUNET_ERROR_TYPE_WARNING
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
void GNUNET_MQ_send(struct GNUNET_MQ_Handle *mq, struct GNUNET_MQ_Envelope *ev)
Send a message with the given message queue.
Definition: mq.c:304
#define GNUNET_MQ_msg_extra(mvar, esize, type)
Allocate an envelope, with extra space allocated after the space needed by the message struct.
Definition: gnunet_mq_lib.h:63
#define GNUNET_MQ_msg_nested_mh(mvar, type, mh)
Allocate a GNUNET_MQ_Envelope, and append a payload message after the given message struct.
#define GNUNET_MQ_msg(mvar, type)
Allocate a GNUNET_MQ_Envelope.
Definition: gnunet_mq_lib.h:78
void GNUNET_MQ_notify_sent(struct GNUNET_MQ_Envelope *ev, GNUNET_SCHEDULER_TaskCallback cb, void *cb_cls)
Call a callback once the envelope has been sent, that is, sending it can not be canceled anymore.
Definition: mq.c:638
#define GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST
Request a set operation from a remote peer.
#define GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE
Intersection operation is done.
#define GNUNET_MESSAGE_TYPE_SET_RESULT
Create an empty set.
#define GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO
Information about the element count for intersection.
#define GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF
Bloom filter message for intersection exchange started by Bob.
@ GNUNET_SET_STATUS_OK
Everything went ok, we are transmitting an element of the result (in set, or to be removed from set,...
@ GNUNET_SET_STATUS_FAILURE
The other peer refused to to the operation with us, or something went wrong.
@ GNUNET_SET_STATUS_DONE
Success, all elements have been sent (and received).
@ GNUNET_SET_RESULT_REMOVED
Client gets only elements that have been removed from the set.
@ GNUNET_SET_RESULT_FULL
Client gets every element in the resulting set.
@ GNUNET_SET_OPERATION_INTERSECTION
Set intersection, only return elements that are in both sets.
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
Bloom filter messages exchanged for set intersection calculation.
Information about an element element in the set.
struct GNUNET_SET_Element element
The actual element.
struct GNUNET_HashCode element_hash
Hash of the element.
Internal representation of the hash map.
A 512-bit hashcode.
Header for all communications.
Element stored in a set.
uint16_t size
Number of bytes in the buffer pointed to by data.
const void * data
Actual data of the element.
uint16_t element_type
Application-specific element type.
Message sent by the service to the client to indicate an element that is removed (set intersection) o...
Definition: set.h:245
uint32_t request_id
id the result belongs to
Definition: set.h:259
uint16_t result_status
Was the evaluation successful? Contains an enum GNUNET_SET_Status in NBO.
Definition: set.h:265
uint16_t element_type
Type of the element attached to the message, if any.
Definition: set.h:270
Last message, send to confirm the final set.
uint32_t final_element_count
Final number of elements in intersection.
struct GNUNET_HashCode element_xor_hash
XOR of all hashes over all elements remaining in the set.
During intersection, the first (and possibly second) message send it the number of elements in the se...
State of an evaluate operation with another peer.
uint32_t bf_bits_per_element
size of the bloomfilter
struct GNUNET_CONTAINER_MultiHashMap * my_elements
Remaining elements in the intersection operation.
uint32_t salt
Salt currently used for BF construction (by us or the other peer, depending on where we are in the co...
struct GNUNET_CONTAINER_BloomFilter * local_bf
BF of the set's element.
struct OperationState * next
Evaluate operations are held in a linked list.
unsigned int generation_created
Generation in which the operation handle was created.
uint32_t bf_data_offset
How many bytes of bf_data are valid?
struct GNUNET_HashCode my_xor
XOR of the keys of all of the elements (remaining) in my set.
enum IntersectionOperationPhase phase
Current state of the operation.
char * bf_data
For multipart BF transmissions, we have to store the bloomfilter-data until we fully received it.
struct GNUNET_HashCode other_xor
XOR of the keys of all of the elements (remaining) in the other peer's set.
uint32_t my_element_count
Current element count contained within my_elements.
struct GNUNET_CONTAINER_MultiHashMapIterator * full_result_iter
Iterator for sending the final set of my_elements to the client.
int channel_death_expected
Set whenever we reach the state where the death of the channel is perfectly find and should NOT resul...
uint32_t bf_data_size
size of the bloomfilter in bf_data.
struct GNUNET_CONTAINER_BloomFilter * remote_bf
The bf we currently receive.
struct OperationState * prev
Evaluate operations are held in a linked list.
int client_done_sent
Did we send the client that we are done?
Operation context used to execute a set operation.
uint32_t bf_bits_per_element
size of the bloomfilter
Extra state required for efficient set intersection.
uint32_t current_set_element_count
Number of currently valid elements in the set which have not been removed.
Dispatch table for a specific set operation.
SetCreateImpl create
Callback for the set creation.