GNUnet  0.10.x
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 
44 
50 
57 
63 
69 
75 };
76 
77 
86 
91 
97 
102 
107 
112 
117  char *bf_data;
118 
125 
132 
136  uint32_t bf_data_offset;
137 
143 
147  uint32_t bf_data_size;
148 
153 
158  uint32_t salt;
159 
164 
169  unsigned int generation_created;
170 
175 
182 };
183 
184 
189 struct SetState {
195 };
196 
197 
205 static void
207  struct GNUNET_SET_Element *element)
208 {
209  struct GNUNET_MQ_Envelope *ev;
210  struct GNUNET_SET_ResultMessage *rm;
211 
213  return; /* Wrong mode for transmitting removed elements */
215  "Sending removed element (size %u) to client\n",
216  element->size);
218  "# Element removed messages sent",
219  1,
220  GNUNET_NO);
222  ev = GNUNET_MQ_msg_extra(rm,
223  element->size,
225  if (NULL == ev)
226  {
227  GNUNET_break(0);
228  return;
229  }
230  rm->result_status = htons(GNUNET_SET_STATUS_OK);
231  rm->request_id = htonl(op->client_request_id);
232  rm->element_type = element->element_type;
233  GNUNET_memcpy(&rm[1],
234  element->data,
235  element->size);
236  GNUNET_MQ_send(op->set->cs->mq,
237  ev);
238 }
239 
240 
249 static int
251  const struct GNUNET_HashCode *key,
252  void *value)
253 {
254  struct Operation *op = cls;
255  struct ElementEntry *ee = value;
256  struct GNUNET_HashCode mutated_hash;
257 
258 
260  "FIMA called for %s:%u\n",
261  GNUNET_h2s(&ee->element_hash),
262  ee->element.size);
263 
265  {
267  "Reduced initialization, not starting with %s:%u (wrong generation)\n",
268  GNUNET_h2s(&ee->element_hash),
269  ee->element.size);
270  return GNUNET_YES; /* element not valid in our operation's generation */
271  }
272 
273  /* Test if element is in other peer's bloomfilter */
275  op->state->salt,
276  &mutated_hash);
278  "Testing mingled hash %s with salt %u\n",
279  GNUNET_h2s(&mutated_hash),
280  op->state->salt);
281  if (GNUNET_NO ==
283  &mutated_hash))
284  {
285  /* remove this element */
287  &ee->element);
289  "Reduced initialization, not starting with %s:%u\n",
290  GNUNET_h2s(&ee->element_hash),
291  ee->element.size);
292  return GNUNET_YES;
293  }
294  op->state->my_element_count++;
296  &ee->element_hash,
297  &op->state->my_xor);
299  "Filtered initialization of my_elements, adding %s:%u\n",
300  GNUNET_h2s(&ee->element_hash),
301  ee->element.size);
304  &ee->element_hash,
305  ee,
307 
308  return GNUNET_YES;
309 }
310 
311 
321 static int
323  const struct GNUNET_HashCode *key,
324  void *value)
325 {
326  struct Operation *op = cls;
327  struct ElementEntry *ee = value;
328  struct GNUNET_HashCode mutated_hash;
329 
331  op->state->salt,
332  &mutated_hash);
334  "Testing mingled hash %s with salt %u\n",
335  GNUNET_h2s(&mutated_hash),
336  op->state->salt);
337  if (GNUNET_NO ==
339  &mutated_hash))
340  {
342  op->state->my_element_count--;
344  &ee->element_hash,
345  &op->state->my_xor);
347  "Bloom filter reduction of my_elements, removing %s:%u\n",
348  GNUNET_h2s(&ee->element_hash),
349  ee->element.size);
352  &ee->element_hash,
353  ee));
355  &ee->element);
356  }
357  else
358  {
360  "Bloom filter reduction of my_elements, keeping %s:%u\n",
361  GNUNET_h2s(&ee->element_hash),
362  ee->element.size);
363  }
364  return GNUNET_YES;
365 }
366 
367 
376 static int
378  const struct GNUNET_HashCode *key,
379  void *value)
380 {
381  struct Operation *op = cls;
382  struct ElementEntry *ee = value;
383  struct GNUNET_HashCode mutated_hash;
384 
386  op->state->salt,
387  &mutated_hash);
389  "Initializing BF with hash %s with salt %u\n",
390  GNUNET_h2s(&mutated_hash),
391  op->state->salt);
393  &mutated_hash);
394  return GNUNET_YES;
395 }
396 
397 
404 static void
406 {
407  struct GNUNET_MQ_Envelope *ev;
409 
411  "Intersection operation failed\n");
413  "# Intersection operations failed",
414  1,
415  GNUNET_NO);
416  if (NULL != op->state->my_elements)
417  {
419  op->state->my_elements = NULL;
420  }
421  ev = GNUNET_MQ_msg(msg,
424  msg->request_id = htonl(op->client_request_id);
425  msg->element_type = htons(0);
426  GNUNET_MQ_send(op->set->cs->mq,
427  ev);
429  GNUNET_YES);
430 }
431 
432 
439 static void
441 {
442  struct GNUNET_MQ_Envelope *ev;
443  struct BFMessage *msg;
444  uint32_t bf_size;
445  uint32_t bf_elementbits;
446  uint32_t chunk_size;
447  char *bf_data;
448  uint32_t offset;
449 
450  /* We consider the ratio of the set sizes to determine
451  the number of bits per element, as the smaller set
452  should use more bits to maximize its set reduction
453  potential and minimize overall bandwidth consumption. */
454  bf_elementbits = 2 + ceil(log2((double)
455  (op->remote_element_count /
456  (double)op->state->my_element_count)));
457  if (bf_elementbits < 1)
458  bf_elementbits = 1; /* make sure k is not 0 */
459  /* optimize BF-size to ~50% of bits set */
460  bf_size = ceil((double)(op->state->my_element_count
461  * bf_elementbits / log(2)));
463  "Sending Bloom filter (%u) of size %u bytes\n",
464  (unsigned int)bf_elementbits,
465  (unsigned int)bf_size);
467  bf_size,
468  bf_elementbits);
470  UINT32_MAX);
473  op);
474 
475  /* send our Bloom filter */
477  "# Intersection Bloom filters sent",
478  1,
479  GNUNET_NO);
480  chunk_size = 60 * 1024 - sizeof(struct BFMessage);
481  if (bf_size <= chunk_size)
482  {
483  /* singlepart */
484  chunk_size = bf_size;
485  ev = GNUNET_MQ_msg_extra(msg,
486  chunk_size,
490  (char*)&msg[1],
491  bf_size));
492  msg->sender_element_count = htonl(op->state->my_element_count);
493  msg->bloomfilter_total_length = htonl(bf_size);
494  msg->bits_per_element = htonl(bf_elementbits);
495  msg->sender_mutator = htonl(op->state->salt);
496  msg->element_xor_hash = op->state->my_xor;
497  GNUNET_MQ_send(op->mq, ev);
498  }
499  else
500  {
501  /* multipart */
502  bf_data = GNUNET_malloc(bf_size);
505  bf_data,
506  bf_size));
507  offset = 0;
508  while (offset < bf_size)
509  {
510  if (bf_size - chunk_size < offset)
511  chunk_size = bf_size - offset;
512  ev = GNUNET_MQ_msg_extra(msg,
513  chunk_size,
515  GNUNET_memcpy(&msg[1],
516  &bf_data[offset],
517  chunk_size);
518  offset += chunk_size;
519  msg->sender_element_count = htonl(op->state->my_element_count);
520  msg->bloomfilter_total_length = htonl(bf_size);
521  msg->bits_per_element = htonl(bf_elementbits);
522  msg->sender_mutator = htonl(op->state->salt);
523  msg->element_xor_hash = op->state->my_xor;
524  GNUNET_MQ_send(op->mq, ev);
525  }
526  GNUNET_free(bf_data);
527  }
529  op->state->local_bf = NULL;
530 }
531 
532 
539 static void
541 {
542  struct Operation *op = cls;
543  struct GNUNET_MQ_Envelope *ev;
544  struct GNUNET_SET_ResultMessage *rm;
545 
547  "Intersection succeeded, sending DONE to local client\n");
549  "# Intersection operations succeeded",
550  1,
551  GNUNET_NO);
552  ev = GNUNET_MQ_msg(rm,
554  rm->request_id = htonl(op->client_request_id);
556  rm->element_type = htons(0);
557  GNUNET_MQ_send(op->set->cs->mq,
558  ev);
560  GNUNET_YES);
561 }
562 
563 
572 static void
574 {
575  struct Operation *op = cls;
576 
578  "DONE sent to other peer, now waiting for other end to close the channel\n");
579  op->state->phase = PHASE_FINISHED;
581 }
582 
583 
591 static void
593 {
594  struct GNUNET_MQ_Envelope *ev;
595  struct IntersectionDoneMessage *idm;
596 
599  ev = GNUNET_MQ_msg(idm,
601  idm->final_element_count = htonl(op->state->my_element_count);
602  idm->element_xor_hash = op->state->my_xor;
605  op);
606  GNUNET_MQ_send(op->mq,
607  ev);
608 }
609 
610 
616 static void
618 {
619  struct Operation *op = cls;
620  const void *nxt;
621  const struct ElementEntry *ee;
622  struct GNUNET_MQ_Envelope *ev;
623  struct GNUNET_SET_ResultMessage *rm;
624  const struct GNUNET_SET_Element *element;
625  int res;
626 
628  NULL,
629  &nxt);
630  if (GNUNET_NO == res)
631  {
633  "Sending done and destroy because iterator ran out\n");
635  op->state->full_result_iter = NULL;
636  if (PHASE_DONE_RECEIVED == op->state->phase)
637  {
638  op->state->phase = PHASE_FINISHED;
640  }
641  else if (PHASE_MUST_SEND_DONE == op->state->phase)
642  {
643  send_p2p_done(op);
644  }
645  else
646  {
647  GNUNET_assert(0);
648  }
649  return;
650  }
651  ee = nxt;
652  element = &ee->element;
654  "Sending element %s:%u to client (full set)\n",
655  GNUNET_h2s(&ee->element_hash),
656  element->size);
658  ev = GNUNET_MQ_msg_extra(rm,
659  element->size,
661  GNUNET_assert(NULL != ev);
662  rm->result_status = htons(GNUNET_SET_STATUS_OK);
663  rm->request_id = htonl(op->client_request_id);
664  rm->element_type = element->element_type;
665  GNUNET_memcpy(&rm[1],
666  element->data,
667  element->size);
670  op);
671  GNUNET_MQ_send(op->set->cs->mq,
672  ev);
673 }
674 
675 
685 static int
687  const struct GNUNET_HashCode *key,
688  void *value)
689 {
690  struct ElementEntry *ee = value;
691  struct Operation *op = cls;
692 
694  return GNUNET_YES; /* element not live in operation's generation */
696  &ee->element_hash,
697  &op->state->my_xor);
699  "Initial full initialization of my_elements, adding %s:%u\n",
700  GNUNET_h2s(&ee->element_hash),
701  ee->element.size);
704  &ee->element_hash,
705  ee,
707  return GNUNET_YES;
708 }
709 
710 
717 static void
719 {
720  struct GNUNET_MQ_Envelope *ev;
722 
724  "Sending our element count (%u)\n",
725  op->state->my_element_count);
726  ev = GNUNET_MQ_msg(msg,
728  msg->sender_element_count = htonl(op->state->my_element_count);
729  GNUNET_MQ_send(op->mq, ev);
730 }
731 
732 
739 static void
741 {
745  op);
746  send_bloomfilter(op);
747 }
748 
749 
757 void
759  const struct IntersectionElementInfoMessage *msg)
760 {
761  struct Operation *op = cls;
762 
764  {
765  GNUNET_break_op(0);
767  return;
768  }
769  op->remote_element_count = ntohl(msg->sender_element_count);
771  "Received remote element count (%u), I have %u\n",
773  op->state->my_element_count);
774  if (((PHASE_INITIAL != op->state->phase) &&
775  (PHASE_COUNT_SENT != op->state->phase)) ||
777  (0 == op->state->my_element_count) ||
778  (0 == op->remote_element_count))
779  {
780  GNUNET_break_op(0);
782  return;
783  }
784  GNUNET_break(NULL == op->state->remote_bf);
785  begin_bf_exchange(op);
787 }
788 
789 
795 static void
797 {
799  "Received BF in phase %u, foreign count is %u, my element count is %u/%u\n",
800  op->state->phase,
802  op->state->my_element_count,
804  switch (op->state->phase)
805  {
806  case PHASE_INITIAL:
807  GNUNET_break_op(0);
809  return;
810 
811  case PHASE_COUNT_SENT:
812  /* This is the first BF being sent, build our initial map with
813  filtering in place */
814  op->state->my_element_count = 0;
817  op);
818  break;
819 
820  case PHASE_BF_EXCHANGE:
821  /* Update our set by reduction */
824  op);
825  break;
826 
828  GNUNET_break_op(0);
830  return;
831 
832  case PHASE_DONE_RECEIVED:
833  GNUNET_break_op(0);
835  return;
836 
837  case PHASE_FINISHED:
838  GNUNET_break_op(0);
840  return;
841  }
843  op->state->remote_bf = NULL;
844 
845  if ((0 == op->state->my_element_count) || /* fully disjoint */
847  (0 == GNUNET_memcmp(&op->state->my_xor,
848  &op->state->other_xor))))
849  {
850  /* we are done */
853  "Intersection succeeded, sending DONE to other peer\n");
855  op->state->local_bf = NULL;
857  {
859  "Sending full result set (%u elements)\n",
864  return;
865  }
866  send_p2p_done(op);
867  return;
868  }
870  send_bloomfilter(op);
871 }
872 
873 
881 int
883  const struct BFMessage *msg)
884 {
885  struct Operation *op = cls;
886 
888  {
889  GNUNET_break_op(0);
890  return GNUNET_SYSERR;
891  }
892  return GNUNET_OK;
893 }
894 
895 
902 void
904  const struct BFMessage *msg)
905 {
906  struct Operation *op = cls;
907  uint32_t bf_size;
908  uint32_t chunk_size;
909  uint32_t bf_bits_per_element;
910 
911  switch (op->state->phase)
912  {
913  case PHASE_INITIAL:
914  GNUNET_break_op(0);
916  return;
917 
918  case PHASE_COUNT_SENT:
919  case PHASE_BF_EXCHANGE:
920  bf_size = ntohl(msg->bloomfilter_total_length);
921  bf_bits_per_element = ntohl(msg->bits_per_element);
922  chunk_size = htons(msg->header.size) - sizeof(struct BFMessage);
923  op->state->other_xor = msg->element_xor_hash;
924  if (bf_size == chunk_size)
925  {
926  if (NULL != op->state->bf_data)
927  {
928  GNUNET_break_op(0);
930  return;
931  }
932  /* single part, done here immediately */
933  op->state->remote_bf
934  = GNUNET_CONTAINER_bloomfilter_init((const char*)&msg[1],
935  bf_size,
936  bf_bits_per_element);
937  op->state->salt = ntohl(msg->sender_mutator);
938  op->remote_element_count = ntohl(msg->sender_element_count);
939  process_bf(op);
940  break;
941  }
942  /* multipart chunk */
943  if (NULL == op->state->bf_data)
944  {
945  /* first chunk, initialize */
946  op->state->bf_data = GNUNET_malloc(bf_size);
947  op->state->bf_data_size = bf_size;
949  op->state->bf_data_offset = 0;
950  op->state->salt = ntohl(msg->sender_mutator);
951  op->remote_element_count = ntohl(msg->sender_element_count);
952  }
953  else
954  {
955  /* increment */
956  if ((op->state->bf_data_size != bf_size) ||
957  (op->state->bf_bits_per_element != bf_bits_per_element) ||
958  (op->state->bf_data_offset + chunk_size > bf_size) ||
959  (op->state->salt != ntohl(msg->sender_mutator)) ||
960  (op->remote_element_count != ntohl(msg->sender_element_count)))
961  {
962  GNUNET_break_op(0);
964  return;
965  }
966  }
968  (const char*)&msg[1],
969  chunk_size);
970  op->state->bf_data_offset += chunk_size;
971  if (op->state->bf_data_offset == bf_size)
972  {
973  /* last chunk, run! */
974  op->state->remote_bf
976  bf_size,
977  bf_bits_per_element);
978  GNUNET_free(op->state->bf_data);
979  op->state->bf_data = NULL;
980  op->state->bf_data_size = 0;
981  process_bf(op);
982  }
983  break;
984 
985  default:
986  GNUNET_break_op(0);
988  return;
989  }
991 }
992 
993 
1002 static int
1003 filter_all(void *cls,
1004  const struct GNUNET_HashCode *key,
1005  void *value)
1006 {
1007  struct Operation *op = cls;
1008  struct ElementEntry *ee = value;
1009 
1011  op->state->my_element_count--;
1013  &ee->element_hash,
1014  &op->state->my_xor);
1016  "Final reduction of my_elements, removing %s:%u\n",
1017  GNUNET_h2s(&ee->element_hash),
1018  ee->element.size);
1021  &ee->element_hash,
1022  ee));
1024  &ee->element);
1025  return GNUNET_YES;
1026 }
1027 
1028 
1035 void
1037  const struct IntersectionDoneMessage *idm)
1038 {
1039  struct Operation *op = cls;
1040 
1042  {
1043  GNUNET_break_op(0);
1045  return;
1046  }
1047  if (PHASE_BF_EXCHANGE != op->state->phase)
1048  {
1049  /* wrong phase to conclude? FIXME: Or should we allow this
1050  if the other peer has _initially_ already an empty set? */
1051  GNUNET_break_op(0);
1053  return;
1054  }
1055  if (0 == ntohl(idm->final_element_count))
1056  {
1057  /* other peer determined empty set is the intersection,
1058  remove all elements */
1060  &filter_all,
1061  op);
1062  }
1063  if ((op->state->my_element_count != ntohl(idm->final_element_count)) ||
1064  (0 != GNUNET_memcmp(&op->state->my_xor,
1065  &idm->element_xor_hash)))
1066  {
1067  /* Other peer thinks we are done, but we disagree on the result! */
1068  GNUNET_break_op(0);
1070  return;
1071  }
1073  "Got IntersectionDoneMessage, have %u elements in intersection\n",
1074  op->state->my_element_count);
1077 
1080  {
1082  "Sending full result set to client (%u elements)\n",
1084  op->state->full_result_iter
1087  return;
1088  }
1089  op->state->phase = PHASE_FINISHED;
1091 }
1092 
1093 
1103 static struct OperationState *
1105  const struct GNUNET_MessageHeader *opaque_context)
1106 {
1107  struct OperationState *state;
1108  struct GNUNET_MQ_Envelope *ev;
1109  struct OperationRequestMessage *msg;
1110 
1111  ev = GNUNET_MQ_msg_nested_mh(msg,
1113  opaque_context);
1114  if (NULL == ev)
1115  {
1116  /* the context message is too large!? */
1117  GNUNET_break(0);
1118  return NULL;
1119  }
1121  "Initiating intersection operation evaluation\n");
1122  state = GNUNET_new(struct OperationState);
1123  /* we started the operation, thus we have to send the operation request */
1124  state->phase = PHASE_INITIAL;
1126  state->my_elements
1128  GNUNET_YES);
1129 
1131  msg->element_count = htonl(state->my_element_count);
1132  GNUNET_MQ_send(op->mq,
1133  ev);
1134  state->phase = PHASE_COUNT_SENT;
1135  if (NULL != opaque_context)
1137  "Sent op request with context message\n");
1138  else
1140  "Sent op request without context message\n");
1141  return state;
1142 }
1143 
1144 
1151 static struct OperationState *
1153 {
1154  struct OperationState *state;
1155 
1157  "Accepting set intersection operation\n");
1158  state = GNUNET_new(struct OperationState);
1159  state->phase = PHASE_INITIAL;
1160  state->my_element_count
1162  state->my_elements
1164  op->remote_element_count),
1165  GNUNET_YES);
1166  op->state = state;
1167  if (op->remote_element_count < state->my_element_count)
1168  {
1169  /* If the other peer (Alice) has fewer elements than us (Bob),
1170  we just send the count as Alice should send the first BF */
1171  send_element_count(op);
1172  state->phase = PHASE_COUNT_SENT;
1173  return state;
1174  }
1175  /* We have fewer elements, so we start with the BF */
1176  begin_bf_exchange(op);
1177  return state;
1178 }
1179 
1180 
1187 static void
1189 {
1190  /* check if the op was canceled twice */
1191  GNUNET_assert(NULL != op->state);
1192  if (NULL != op->state->remote_bf)
1193  {
1195  op->state->remote_bf = NULL;
1196  }
1197  if (NULL != op->state->local_bf)
1198  {
1200  op->state->local_bf = NULL;
1201  }
1202  if (NULL != op->state->my_elements)
1203  {
1205  op->state->my_elements = NULL;
1206  }
1207  if (NULL != op->state->full_result_iter)
1208  {
1210  op->state->full_result_iter = NULL;
1211  }
1212  GNUNET_free(op->state);
1213  op->state = NULL;
1215  "Destroying intersection op state done\n");
1216 }
1217 
1218 
1224 static struct SetState *
1226 {
1227  struct SetState *set_state;
1228 
1230  "Intersection set created\n");
1231  set_state = GNUNET_new(struct SetState);
1232  set_state->current_set_element_count = 0;
1233 
1234  return set_state;
1235 }
1236 
1237 
1244 static void
1245 intersection_add(struct SetState *set_state,
1246  struct ElementEntry *ee)
1247 {
1248  set_state->current_set_element_count++;
1249 }
1250 
1251 
1257 static void
1259 {
1260  GNUNET_free(set_state);
1261 }
1262 
1263 
1270 static void
1271 intersection_remove(struct SetState *set_state,
1272  struct ElementEntry *element)
1273 {
1274  GNUNET_assert(0 < set_state->current_set_element_count);
1275  set_state->current_set_element_count--;
1276 }
1277 
1278 
1284 static void
1286 {
1288  {
1289  /* oh goodie, we are done! */
1291  }
1292  else
1293  {
1294  /* sorry, channel went down early, too bad. */
1296  GNUNET_YES);
1297  }
1298 }
1299 
1300 
1306 const struct SetVT *
1308 {
1309  static const struct SetVT intersection_vt = {
1311  .add = &intersection_add,
1312  .remove = &intersection_remove,
1313  .destroy_set = &intersection_set_destroy,
1314  .evaluate = &intersection_evaluate,
1315  .accept = &intersection_accept,
1316  .cancel = &intersection_op_cancel,
1317  .channel_death = &intersection_channel_death,
1318  };
1319 
1320  return &intersection_vt;
1321 }
void GNUNET_CONTAINER_multihashmap_iterator_destroy(struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
Destroy a multihashmap iterator.
State of an evaluate operation with another peer.
struct GNUNET_CONTAINER_BloomFilter * GNUNET_CONTAINER_bloomfilter_init(const char *data, size_t size, unsigned int k)
Create a Bloom filter from raw bits.
static void intersection_add(struct SetState *set_state, struct ElementEntry *ee)
Add the element from the given element message to the set.
int 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&#39;s position.
struct GNUNET_MessageHeader * msg
Definition: 005.c:2
enum GNUNET_SET_ResultMode result_mode
When are elements sent to the client, and which elements are sent?
void GNUNET_CONTAINER_bloomfilter_add(struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Add an element to the filter.
We are just starting.
uint32_t final_element_count
Final number of elements in intersection.
struct Set * set
Set associated with the operation, NULL until the spec has been associated with a set...
unsigned int GNUNET_CONTAINER_multihashmap_size(const struct GNUNET_CONTAINER_MultiHashMap *map)
Get the number of key-value pairs in the map.
int _GSS_is_element_of_operation(struct ElementEntry *ee, struct Operation *op)
Is element ee part of the set used by op?
uint32_t element_count
For Intersection: my element count.
static void fail_intersection_operation(struct Operation *op)
Inform the client that the intersection operation has failed, and proceed to destroy the evaluate ope...
#define GNUNET_MQ_msg_nested_mh(mvar, type, mh)
Allocate a GNUNET_MQ_Envelope, and append a payload message after the given message struct...
int check_intersection_p2p_bf(void *cls, const struct BFMessage *msg)
Check an BF message from a remote peer.
struct GNUNET_MQ_Handle * mq
MQ to talk to client.
struct GNUNET_CONTAINER_MultiHashMapIterator * GNUNET_CONTAINER_multihashmap_iterator_create(const struct GNUNET_CONTAINER_MultiHashMap *map)
Create an iterator for a multihashmap.
static void send_remaining_elements(void *cls)
Send all elements in the full result iterator.
struct SetState * state
Implementation-specific state.
#define GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF
Bloom filter message for intersection exchange started by Bob.
uint32_t bf_data_size
size of the bloomfilter in bf_data.
Message sent by the service to the client to indicate an element that is removed (set intersection) o...
Definition: set.h:238
uint32_t salt
Salt currently used for BF construction (by us or the other peer, depending on where we are in the co...
static void begin_bf_exchange(struct Operation *op)
We go first, initialize our map with all elements and send the first Bloom filter.
Element stored in a set.
struct GNUNET_HashCode element_hash
Hash of the element.
uint32_t sender_element_count
Number of elements the sender still has in the set.
static struct OperationState * intersection_evaluate(struct Operation *op, const struct GNUNET_MessageHeader *opaque_context)
Initiate a set intersection operation with a remote peer.
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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...
struct GNUNET_CADET_Channel * channel
Channel to the peer.
uint32_t bf_bits_per_element
size of the bloomfilter
static int filtered_map_initialization(void *cls, const struct GNUNET_HashCode *key, void *value)
Fills the "my_elements" hashmap with all relevant elements.
#define GNUNET_MESSAGE_TYPE_SET_RESULT
Create an empty set.
static void send_client_done_and_destroy(void *cls)
Signal to the client that the operation has finished and destroy the operation.
struct GNUNET_MessageHeader header
Type: GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF.
static void process_bf(struct Operation *op)
Process a Bloomfilter once we got all the chunks.
uint32_t request_id
id the result belongs to
Definition: set.h:252
We have initialized our set and are now reducing it by exchanging Bloom filters until one party notic...
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
struct GNUNET_CONTAINER_BloomFilter * local_bf
BF of the set&#39;s element.
#define GNUNET_MQ_msg(mvar, type)
Allocate a GNUNET_MQ_Envelope.
Definition: gnunet_mq_lib.h:67
uint32_t my_element_count
Current element count contained within my_elements.
#define GNUNET_NO
Definition: gnunet_common.h:78
static int filter_all(void *cls, const struct GNUNET_HashCode *key, void *value)
Remove all elements from our hashmap.
void _GSS_operation_destroy(struct Operation *op, int gc)
Destroy the given operation.
#define GNUNET_OK
Named constants for return values.
Definition: gnunet_common.h:75
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
#define GNUNET_new(type)
Allocate a struct or union of the given type.
int client_done_sent
Did we send the client that we are done?
Client gets every element in the resulting set.
uint16_t size
The length of the struct (in bytes, including the length field itself), in big-endian format...
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
unsigned int generation_created
Generation in which the operation handle was created.
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...
Success, all elements have been sent (and received).
uint32_t bloomfilter_total_length
Total length of the bloomfilter data.
Internal representation of the hash map.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur...
const void * data
Actual data of the element.
static void send_p2p_done(struct Operation *op)
Notify the other peer that we are done.
struct GNUNET_STATISTICS_Handle * _GSS_statistics
Statistics handle.
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...
struct OperationState * next
Evaluate operations are held in a linked list.
#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:52
#define GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST
Request a set operation from a remote peer.
enum State state
current state of profiling
void handle_intersection_p2p_done(void *cls, const struct IntersectionDoneMessage *idm)
Handle a done message from a remote peer.
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:772
static char * value
Value of the record to add/remove.
Information about an element element in the set.
The other peer refused to to the operation with us, or something went wrong.
uint32_t bf_data_offset
How many bytes of bf_data are valid?
int GNUNET_CONTAINER_bloomfilter_test(const struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Test if an element is in the filter.
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
Everything went ok, we are transmitting an element of the result (in set, or to be removed from set...
Dispatch table for a specific set operation.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
The protocol is over.
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...
#define GNUNET_MIN(a, b)
Definition: gnunet_common.h:80
enum IntersectionOperationPhase phase
Current state of the operation.
uint16_t result_status
Was the evaluation successful? Contains an enum GNUNET_SET_Status in NBO.
Definition: set.h:258
uint32_t sender_element_count
mutator used with this bloomfilter.
Randomness for IVs etc.
We must next send the P2P DONE message (after finishing mostly with the local client).
int 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.
IntersectionOperationPhase
Current phase we are in for a intersection operation.
static struct SetState * intersection_set_create()
Create a new set supporting the intersection operation.
A 512-bit hashcode.
struct GNUNET_HashCode element_xor_hash
XOR of all hashes over all elements remaining in the set.
static int res
void handle_intersection_p2p_element_info(void *cls, const struct IntersectionElementInfoMessage *msg)
Handle the initial struct IntersectionElementInfoMessage from a remote peer.
Bloom filter messages exchanged for set intersection calculation.
struct GNUNET_HashCode element_xor_hash
XOR of all hashes over all elements remaining in the set.
char * bf_data
For multipart BF transmissions, we have to store the bloomfilter-data until we fully received it...
uint16_t element_type
Type of the element attachted to the message, if any.
Definition: set.h:263
There must only be one value per key; storing a value should fail if a value under the same key alrea...
struct GNUNET_HashCode key
The key used in the DHT.
#define GNUNET_SYSERR
Definition: gnunet_common.h:76
#define GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO
Information about the element count for intersection.
uint32_t current_set_element_count
Number of currently valid elements in the set which have not been removed.
int 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.
enum GNUNET_SET_OperationType operation
Type of operation supported for this set.
Operation context used to execute a set operation.
int 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.
static void send_element_count(struct Operation *op)
Send our element count to the peer, in case our element count is lower than theirs.
const struct SetVT * _GSS_intersection_vt()
Get the table with implementing functions for set intersection.
Extra state required for efficient set intersection.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
uint32_t bits_per_element
Number of bits (k-value) used in encoding the bloomfilter.
We have received the P2P DONE message, and must finish with the local client before terminating the c...
We have send the number of our elements to the other peer, but did not setup our element set yet...
static int iterator_bf_create(void *cls, const struct GNUNET_HashCode *key, void *value)
Create initial bloomfilter based on all the elements given.
During intersection, the first (and possibly second) message send it the number of elements in the se...
struct GNUNET_CONTAINER_MultiHashMapIterator * full_result_iter
Iterator for sending the final set of my_elements to the client.
two-peer set operations
void GNUNET_CADET_receive_done(struct GNUNET_CADET_Channel *channel)
Send an ack on the channel to confirm the processing of a message.
Definition: cadet_api.c:951
struct GNUNET_MQ_Handle * mq
Message queue for the channel.
struct OperationState * prev
Evaluate operations are held in a linked list.
uint32_t client_request_id
ID used to identify an operation between service and client.
struct GNUNET_HashCode other_xor
XOR of the keys of all of the elements (remaining) in the other peer&#39;s set.
static void intersection_remove(struct SetState *set_state, struct ElementEntry *element)
Remove the element given in the element message from the set.
struct GNUNET_CONTAINER_BloomFilter * remote_bf
The bf we currently receive.
uint16_t size
Number of bytes in the buffer pointed to by data.
common components for the implementation the different set operations
#define GNUNET_log(kind,...)
#define GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE
Intersection operation is done.
struct GNUNET_SET_Element element
The actual element.
uint32_t operation
Operation to request, values from enum GNUNET_SET_OperationType
Client gets only elements that have been removed from the set.
struct GNUNET_CONTAINER_MultiHashMap * elements
Maps struct GNUNET_HashCode * to struct ElementEntry *.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
static void intersection_channel_death(struct Operation *op)
Callback for channel death for the intersection operation.
static void send_bloomfilter(struct Operation *op)
Send a bloomfilter to our peer.
Header for all communications.
#define GNUNET_YES
Definition: gnunet_common.h:77
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:193
Last message, send to confirm the final set.
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:351
int channel_death_expected
Set whenever we reach the state where the death of the channel is perfectly find and should NOT resul...
struct ClientState * cs
Client that owns the set.
Set intersection, only return elements that are in both sets.
static void intersection_set_destroy(struct SetState *set_state)
Destroy a set that supports the intersection operation.
uint32_t remote_element_count
Remote peers element count.
void handle_intersection_p2p_bf(void *cls, const struct BFMessage *msg)
Handle an BF message from a remote peer.
SetCreateImpl create
Callback for the set creation.
struct OperationState * state
Operation-specific operation state.
static struct GNUNET_ARM_Operation * op
Current operation.
Definition: gnunet-arm.c:139
static struct OperationState * intersection_accept(struct Operation *op)
Accept an intersection operation request from a remote peer.
static void intersection_op_cancel(struct Operation *op)
Destroy the intersection operation.
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MulitHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
struct GNUNET_HashCode my_xor
XOR of the keys of all of the elements (remaining) in my set.
struct GNUNET_CONTAINER_MultiHashMap * my_elements
Remaining elements in the intersection operation.
void GNUNET_CONTAINER_bloomfilter_free(struct GNUNET_CONTAINER_BloomFilter *bf)
Free the space associcated with a filter in memory, flush to drive if needed (do not free the space o...
Peer-to-Peer messages for gnunet set.
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:79
uint32_t sender_mutator
Mutator used with this bloomfilter.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
uint16_t element_type
Application-specific element type.
struct SetContent * content
Content, possibly shared by multiple sets, and thus reference counted.