GNUnet  0.11.x
Functions
gnunet-service-set_intersection.h File Reference

two-peer set operations More...

#include "gnunet-service-set.h"
Include dependency graph for gnunet-service-set_intersection.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

int check_intersection_p2p_bf (void *cls, const struct BFMessage *msg)
 Check an BF message from a remote peer. More...
 
void handle_intersection_p2p_bf (void *cls, const struct BFMessage *msg)
 Handle an BF message from a remote peer. More...
 
void handle_intersection_p2p_element_info (void *cls, const struct IntersectionElementInfoMessage *msg)
 Handle the initial struct IntersectionElementInfoMessage from a remote peer. More...
 
void handle_intersection_p2p_done (void *cls, const struct IntersectionDoneMessage *idm)
 Handle a done message from a remote peer. More...
 

Detailed Description

two-peer set operations

Author
Florian Dold
Christian Grothoff

Definition in file gnunet-service-set_intersection.h.

Function Documentation

◆ check_intersection_p2p_bf()

int check_intersection_p2p_bf ( void *  cls,
const struct BFMessage msg 
)

Check an BF message from a remote peer.

Parameters
clsthe intersection operation
msgthe header of the message
Returns
GNUNET_OK if msg is well-formed

Definition at line 891 of file gnunet-service-set_intersection.c.

893 {
894  struct Operation *op = cls;
895 
896  if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation)
897  {
898  GNUNET_break_op (0);
899  return GNUNET_SYSERR;
900  }
901  return GNUNET_OK;
902 }
static struct GNUNET_ARM_Operation * op
Current operation.
Definition: gnunet-arm.c:144
@ GNUNET_OK
Definition: gnunet_common.h:95
@ GNUNET_SYSERR
Definition: gnunet_common.h:93
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
@ GNUNET_SET_OPERATION_INTERSECTION
Set intersection, only return elements that are in both sets.
Operation context used to execute a set operation.

References GNUNET_break_op, GNUNET_OK, GNUNET_SET_OPERATION_INTERSECTION, GNUNET_SYSERR, and op.

◆ handle_intersection_p2p_bf()

void handle_intersection_p2p_bf ( void *  cls,
const struct BFMessage msg 
)

Handle an BF message from a remote peer.

Parameters
clsthe intersection operation
msgthe header of the message

Definition at line 912 of file gnunet-service-set_intersection.c.

914 {
915  struct Operation *op = cls;
916  uint32_t bf_size;
917  uint32_t chunk_size;
918  uint32_t bf_bits_per_element;
919 
920  switch (op->state->phase)
921  {
922  case PHASE_INITIAL:
923  GNUNET_break_op (0);
925  return;
926 
927  case PHASE_COUNT_SENT:
928  case PHASE_BF_EXCHANGE:
929  bf_size = ntohl (msg->bloomfilter_total_length);
930  bf_bits_per_element = ntohl (msg->bits_per_element);
931  chunk_size = htons (msg->header.size) - sizeof(struct BFMessage);
932  op->state->other_xor = msg->element_xor_hash;
933  if (bf_size == chunk_size)
934  {
935  if (NULL != op->state->bf_data)
936  {
937  GNUNET_break_op (0);
939  return;
940  }
941  /* single part, done here immediately */
942  op->state->remote_bf
943  = GNUNET_CONTAINER_bloomfilter_init ((const char *) &msg[1],
944  bf_size,
945  bf_bits_per_element);
946  op->state->salt = ntohl (msg->sender_mutator);
947  op->remote_element_count = ntohl (msg->sender_element_count);
948  process_bf (op);
949  break;
950  }
951  /* multipart chunk */
952  if (NULL == op->state->bf_data)
953  {
954  /* first chunk, initialize */
955  op->state->bf_data = GNUNET_malloc (bf_size);
956  op->state->bf_data_size = bf_size;
957  op->state->bf_bits_per_element = bf_bits_per_element;
958  op->state->bf_data_offset = 0;
959  op->state->salt = ntohl (msg->sender_mutator);
960  op->remote_element_count = ntohl (msg->sender_element_count);
961  }
962  else
963  {
964  /* increment */
965  if ((op->state->bf_data_size != bf_size) ||
966  (op->state->bf_bits_per_element != bf_bits_per_element) ||
967  (op->state->bf_data_offset + chunk_size > bf_size) ||
968  (op->state->salt != ntohl (msg->sender_mutator)) ||
969  (op->remote_element_count != ntohl (msg->sender_element_count)))
970  {
971  GNUNET_break_op (0);
973  return;
974  }
975  }
976  GNUNET_memcpy (&op->state->bf_data[op->state->bf_data_offset],
977  (const char *) &msg[1],
978  chunk_size);
979  op->state->bf_data_offset += chunk_size;
980  if (op->state->bf_data_offset == bf_size)
981  {
982  /* last chunk, run! */
983  op->state->remote_bf
984  = GNUNET_CONTAINER_bloomfilter_init (op->state->bf_data,
985  bf_size,
986  bf_bits_per_element);
987  GNUNET_free (op->state->bf_data);
988  op->state->bf_data = NULL;
989  op->state->bf_data_size = 0;
990  process_bf (op);
991  }
992  break;
993 
994  default:
995  GNUNET_break_op (0);
997  return;
998  }
999  GNUNET_CADET_receive_done (op->channel);
1000 }
struct GNUNET_MessageHeader * msg
Definition: 005.c:2
@ PHASE_INITIAL
We are just starting.
@ 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.
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 process_bf(struct Operation *op)
Process a Bloomfilter once we got all the chunks.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
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_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:888
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
Bloom filter messages exchanged for set intersection calculation.
uint16_t size
The length of the struct (in bytes, including the length field itself), in big-endian format.
uint32_t bf_bits_per_element
size of the bloomfilter

References Operation::bf_bits_per_element, fail_intersection_operation(), GNUNET_break_op, GNUNET_CADET_receive_done(), GNUNET_CONTAINER_bloomfilter_init(), GNUNET_free, GNUNET_malloc, GNUNET_memcpy, msg, op, PHASE_BF_EXCHANGE, PHASE_COUNT_SENT, PHASE_INITIAL, process_bf(), and GNUNET_MessageHeader::size.

Here is the call graph for this function:

◆ handle_intersection_p2p_element_info()

void handle_intersection_p2p_element_info ( void *  cls,
const struct IntersectionElementInfoMessage msg 
)

Handle the initial struct IntersectionElementInfoMessage from a remote peer.

Parameters
clsthe intersection operation
mhthe header of the message

Definition at line 765 of file gnunet-service-set_intersection.c.

768 {
769  struct Operation *op = cls;
770 
771  if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation)
772  {
773  GNUNET_break_op (0);
775  return;
776  }
777  op->remote_element_count = ntohl (msg->sender_element_count);
779  "Received remote element count (%u), I have %u\n",
780  op->remote_element_count,
781  op->state->my_element_count);
782  if (((PHASE_INITIAL != op->state->phase) &&
783  (PHASE_COUNT_SENT != op->state->phase)) ||
784  (op->state->my_element_count > op->remote_element_count) ||
785  (0 == op->state->my_element_count) ||
786  (0 == op->remote_element_count))
787  {
788  GNUNET_break_op (0);
790  return;
791  }
792  GNUNET_break (NULL == op->state->remote_bf);
794  GNUNET_CADET_receive_done (op->channel);
795 }
static void begin_bf_exchange(struct Operation *op)
We go first, initialize our map with all elements and send the first Bloom filter.
#define GNUNET_log(kind,...)
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
@ GNUNET_ERROR_TYPE_DEBUG

References begin_bf_exchange(), fail_intersection_operation(), GNUNET_break, GNUNET_break_op, GNUNET_CADET_receive_done(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_SET_OPERATION_INTERSECTION, msg, op, PHASE_COUNT_SENT, and PHASE_INITIAL.

Here is the call graph for this function:

◆ handle_intersection_p2p_done()

void handle_intersection_p2p_done ( void *  cls,
const struct IntersectionDoneMessage idm 
)

Handle a done message from a remote peer.

Parameters
clsthe intersection operation
mhthe message

Definition at line 1045 of file gnunet-service-set_intersection.c.

1047 {
1048  struct Operation *op = cls;
1049 
1050  if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation)
1051  {
1052  GNUNET_break_op (0);
1054  return;
1055  }
1056  if (PHASE_BF_EXCHANGE != op->state->phase)
1057  {
1058  /* wrong phase to conclude? FIXME: Or should we allow this
1059  if the other peer has _initially_ already an empty set? */
1060  GNUNET_break_op (0);
1062  return;
1063  }
1064  if (0 == ntohl (idm->final_element_count))
1065  {
1066  /* other peer determined empty set is the intersection,
1067  remove all elements */
1068  GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements,
1069  &filter_all,
1070  op);
1071  }
1072  if ((op->state->my_element_count != ntohl (idm->final_element_count)) ||
1073  (0 != GNUNET_memcmp (&op->state->my_xor,
1074  &idm->element_xor_hash)))
1075  {
1076  /* Other peer thinks we are done, but we disagree on the result! */
1077  GNUNET_break_op (0);
1079  return;
1080  }
1082  "Got IntersectionDoneMessage, have %u elements in intersection\n",
1083  op->state->my_element_count);
1084  op->state->phase = PHASE_DONE_RECEIVED;
1085  GNUNET_CADET_receive_done (op->channel);
1086 
1087  GNUNET_assert (GNUNET_NO == op->state->client_done_sent);
1088  if (GNUNET_SET_RESULT_FULL == op->result_mode)
1089  {
1091  "Sending full result set to client (%u elements)\n",
1092  GNUNET_CONTAINER_multihashmap_size (op->state->my_elements));
1093  op->state->full_result_iter
1094  = GNUNET_CONTAINER_multihashmap_iterator_create (op->state->my_elements);
1096  return;
1097  }
1098  op->state->phase = PHASE_FINISHED;
1100 }
@ 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.
static int filter_all(void *cls, const struct GNUNET_HashCode *key, void *value)
Remove all elements from our hashmap.
static void send_remaining_elements(void *cls)
Send all elements in the full result iterator.
static void send_client_done_and_destroy(void *cls)
Signal to the client that the operation has finished and destroy the operation.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
@ GNUNET_NO
Definition: gnunet_common.h:94
unsigned int GNUNET_CONTAINER_multihashmap_size(const struct GNUNET_CONTAINER_MultiHashMap *map)
Get the number of key-value pairs in the map.
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_CONTAINER_MultiHashMapIterator * GNUNET_CONTAINER_multihashmap_iterator_create(const struct GNUNET_CONTAINER_MultiHashMap *map)
Create an iterator for a multihashmap.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
@ GNUNET_SET_RESULT_FULL
Client gets every element in the resulting 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.

References IntersectionDoneMessage::element_xor_hash, fail_intersection_operation(), filter_all(), IntersectionDoneMessage::final_element_count, GNUNET_assert, GNUNET_break_op, GNUNET_CADET_receive_done(), GNUNET_CONTAINER_multihashmap_iterate(), GNUNET_CONTAINER_multihashmap_iterator_create(), GNUNET_CONTAINER_multihashmap_size(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_memcmp, GNUNET_NO, GNUNET_SET_OPERATION_INTERSECTION, GNUNET_SET_RESULT_FULL, op, PHASE_BF_EXCHANGE, PHASE_DONE_RECEIVED, PHASE_FINISHED, send_client_done_and_destroy(), and send_remaining_elements().

Here is the call graph for this function: