GNUnet  0.19.4
gnunet-service-set_intersection.c File Reference

two-peer set intersection More...

#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_statistics_service.h"
#include "gnunet-service-set.h"
#include "gnunet_block_lib.h"
#include "gnunet-service-set_protocol.h"
#include "gnunet-service-set_intersection.h"
#include <gcrypt.h>
Include dependency graph for gnunet-service-set_intersection.c:

Go to the source code of this file.

Data Structures

struct  OperationState
 State of an evaluate operation with another peer. More...
 
struct  SetState
 Extra state required for efficient set intersection. More...
 

Enumerations

enum  IntersectionOperationPhase {
  PHASE_INITIAL , PHASE_COUNT_SENT , PHASE_BF_EXCHANGE , PHASE_MUST_SEND_DONE ,
  PHASE_DONE_RECEIVED , PHASE_FINISHED , PHASE_INITIAL , PHASE_COUNT_SENT ,
  PHASE_BF_EXCHANGE , PHASE_MUST_SEND_DONE , PHASE_DONE_RECEIVED , PHASE_FINISHED
}
 Current phase we are in for a intersection operation. More...
 

Functions

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 removed an element. More...
 
static int filtered_map_initialization (void *cls, const struct GNUNET_HashCode *key, void *value)
 Fills the "my_elements" hashmap with all relevant elements. More...
 
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. More...
 
static int iterator_bf_create (void *cls, const struct GNUNET_HashCode *key, void *value)
 Create initial bloomfilter based on all the elements given. More...
 
static void fail_intersection_operation (struct Operation *op)
 Inform the client that the intersection operation has failed, and proceed to destroy the evaluate operation. More...
 
static void send_bloomfilter (struct Operation *op)
 Send a bloomfilter to our peer. More...
 
static void send_client_done_and_destroy (void *cls)
 Signal to the client that the operation has finished and destroy the operation. More...
 
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 we are done, so we are not just waiting for the channel to die before telling the local client that we are done as our last act. More...
 
static void send_p2p_done (struct Operation *op)
 Notify the other peer that we are done. More...
 
static void send_remaining_elements (void *cls)
 Send all elements in the full result iterator. More...
 
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 specification. More...
 
static void send_element_count (struct Operation *op)
 Send our element count to the peer, in case our element count is lower than theirs. More...
 
static void begin_bf_exchange (struct Operation *op)
 We go first, initialize our map with all elements and send the first Bloom filter. More...
 
void handle_intersection_p2p_element_info (void *cls, const struct IntersectionElementInfoMessage *msg)
 Handle the initial struct IntersectionElementInfoMessage from a remote peer. More...
 
static void process_bf (struct Operation *op)
 Process a Bloomfilter once we got all the chunks. More...
 
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...
 
static int filter_all (void *cls, const struct GNUNET_HashCode *key, void *value)
 Remove all elements from our hashmap. More...
 
void handle_intersection_p2p_done (void *cls, const struct IntersectionDoneMessage *idm)
 Handle a done message from a remote peer. More...
 
static struct OperationStateintersection_evaluate (struct Operation *op, const struct GNUNET_MessageHeader *opaque_context)
 Initiate a set intersection operation with a remote peer. More...
 
static struct OperationStateintersection_accept (struct Operation *op)
 Accept an intersection operation request from a remote peer. More...
 
static void intersection_op_cancel (struct Operation *op)
 Destroy the intersection operation. More...
 
static struct SetStateintersection_set_create ()
 Create a new set supporting the intersection operation. More...
 
static void intersection_add (struct SetState *set_state, struct ElementEntry *ee)
 Add the element from the given element message to the set. More...
 
static void intersection_set_destroy (struct SetState *set_state)
 Destroy a set that supports the intersection operation. More...
 
static void intersection_remove (struct SetState *set_state, struct ElementEntry *element)
 Remove the element given in the element message from the set. More...
 
static void intersection_channel_death (struct Operation *op)
 Callback for channel death for the intersection operation. More...
 
const struct SetVT_GSS_intersection_vt ()
 Get the table with implementing functions for set intersection. More...
 

Detailed Description

two-peer set intersection

Author
Christian Fuchs
Christian Grothoff

Definition in file gnunet-service-set_intersection.c.

Enumeration Type Documentation

◆ IntersectionOperationPhase

Current phase we are in for a intersection operation.

Enumerator
PHASE_INITIAL 

We are just starting.

PHASE_COUNT_SENT 

We have send the number of our elements to the other peer, but did not setup our element set yet.

PHASE_BF_EXCHANGE 

We have initialized our set and are now reducing it by exchanging Bloom filters until one party notices the their element hashes are equal.

PHASE_MUST_SEND_DONE 

We must next send the P2P DONE message (after finishing mostly with the local client).

Then we will wait for the channel to close.

PHASE_DONE_RECEIVED 

We have received the P2P DONE message, and must finish with the local client before terminating the channel.

PHASE_FINISHED 

The protocol is over.

Results may still have to be sent to the client.

PHASE_INITIAL 

We are just starting.

PHASE_COUNT_SENT 

We have send the number of our elements to the other peer, but did not setup our element set yet.

PHASE_BF_EXCHANGE 

We have initialized our set and are now reducing it by exchanging Bloom filters until one party notices the their element hashes are equal.

PHASE_MUST_SEND_DONE 

We must next send the P2P DONE message (after finishing mostly with the local client).

Then we will wait for the channel to close.

PHASE_DONE_RECEIVED 

We have received the P2P DONE message, and must finish with the local client before terminating the channel.

PHASE_FINISHED 

The protocol is over.

Results may still have to be sent to the client.

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

40 {
45 
51 
58 
64 
70 
76 };
@ 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).

Function Documentation

◆ send_client_removed_element()

static void send_client_removed_element ( struct Operation op,
struct GNUNET_SET_Element element 
)
static

If applicable in the current operation mode, send a result message to the client indicating we removed an element.

Parameters
opintersection operation
elementelement to send

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

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  }
233  rm->result_status = htons (GNUNET_SET_STATUS_OK);
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 }
static struct GNUNET_ARM_Operation * op
Current operation.
Definition: gnunet-arm.c:144
struct GNUNET_STATISTICS_Handle * _GSS_statistics
Statistics handle.
#define GNUNET_log(kind,...)
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
@ GNUNET_NO
#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.
@ GNUNET_ERROR_TYPE_DEBUG
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:62
#define GNUNET_MESSAGE_TYPE_SET_RESULT
Create an empty set.
@ 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_RESULT_REMOVED
Client gets only elements that have been removed from the set.
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
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

References _GSS_statistics, GNUNET_SET_Element::data, GNUNET_SET_Element::element_type, GNUNET_SET_ResultMessage::element_type, GNUNET_assert, GNUNET_break, GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_memcpy, GNUNET_MESSAGE_TYPE_SET_RESULT, GNUNET_MQ_msg_extra, GNUNET_MQ_send(), GNUNET_NO, GNUNET_SET_RESULT_REMOVED, GNUNET_SET_STATUS_OK, GNUNET_STATISTICS_update(), op, GNUNET_SET_ResultMessage::request_id, GNUNET_SET_ResultMessage::result_status, and GNUNET_SET_Element::size.

Referenced by filter_all(), filtered_map_initialization(), and iterator_bf_reduce().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ filtered_map_initialization()

static int filtered_map_initialization ( void *  cls,
const struct GNUNET_HashCode key,
void *  value 
)
static

Fills the "my_elements" hashmap with all relevant elements.

Parameters
clsthe struct Operation * we are performing
keycurrent key code
valuethe struct ElementEntry * from the hash map
Returns
GNUNET_YES (we should continue to iterate)

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

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",
264  GNUNET_h2s (&ee->element_hash),
265  ee->element.size);
266 
268  {
270  "Reduced initialization, not starting with %s:%u (wrong generation)\n",
271  GNUNET_h2s (&ee->element_hash),
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",
293  GNUNET_h2s (&ee->element_hash),
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",
303  GNUNET_h2s (&ee->element_hash),
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 }
static char * value
Value of the record to add/remove.
int _GSS_is_element_of_operation(struct ElementEntry *ee, struct Operation *op)
Is element ee part of the set used by op?
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...
GNUNET_NETWORK_STRUCT_END 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
bool GNUNET_CONTAINER_bloomfilter_test(const struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Test if an element is in the filter.
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
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.
@ 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...
@ GNUNET_YES
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
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.
A 512-bit hashcode.
Operation context used to execute a set operation.

References _GSS_is_element_of_operation(), ElementEntry::element, ElementEntry::element_hash, GNUNET_BLOCK_mingle_hash(), GNUNET_break, GNUNET_CONTAINER_bloomfilter_test(), GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY, GNUNET_CRYPTO_hash_xor(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_NO, GNUNET_YES, op, send_client_removed_element(), GNUNET_SET_Element::size, and value.

Referenced by process_bf().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ iterator_bf_reduce()

static int iterator_bf_reduce ( void *  cls,
const struct GNUNET_HashCode key,
void *  value 
)
static

Removes elements from our hashmap if they are not contained within the provided remote bloomfilter.

Parameters
clsclosure with the struct Operation *
keycurrent key code
valuevalue in the hash map
Returns
GNUNET_YES (we should continue to iterate)

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

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",
351  GNUNET_h2s (&ee->element_hash),
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",
364  GNUNET_h2s (&ee->element_hash),
365  ee->element.size);
366  }
367  return GNUNET_YES;
368 }
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.

References ElementEntry::element, ElementEntry::element_hash, GNUNET_assert, GNUNET_BLOCK_mingle_hash(), GNUNET_break, GNUNET_CONTAINER_bloomfilter_test(), GNUNET_CONTAINER_multihashmap_remove(), GNUNET_CRYPTO_hash_xor(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_NO, GNUNET_YES, op, send_client_removed_element(), GNUNET_SET_Element::size, and value.

Referenced by process_bf().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ iterator_bf_create()

static int iterator_bf_create ( void *  cls,
const struct GNUNET_HashCode key,
void *  value 
)
static

Create initial bloomfilter based on all the elements given.

Parameters
clsthe struct Operation *
keycurrent key code
valuethe struct ElementEntry to process
Returns
GNUNET_YES (we should continue to iterate)

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

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 }
void GNUNET_CONTAINER_bloomfilter_add(struct GNUNET_CONTAINER_BloomFilter *bf, const struct GNUNET_HashCode *e)
Add an element to the filter.

References ElementEntry::element_hash, GNUNET_BLOCK_mingle_hash(), GNUNET_CONTAINER_bloomfilter_add(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_YES, op, and value.

Referenced by send_bloomfilter().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ fail_intersection_operation()

static void fail_intersection_operation ( struct Operation op)
static

Inform the client that the intersection operation has failed, and proceed to destroy the evaluate operation.

Parameters
opthe intersection operation to fail

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

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 }
struct GNUNET_MessageHeader * msg
Definition: 005.c:2
void _GSS_operation_destroy(struct Operation *op, int gc)
Destroy the given operation.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
@ GNUNET_ERROR_TYPE_WARNING
#define GNUNET_MQ_msg(mvar, type)
Allocate a GNUNET_MQ_Envelope.
Definition: gnunet_mq_lib.h:77
@ GNUNET_SET_STATUS_FAILURE
The other peer refused to to the operation with us, or something went wrong.

References _GSS_operation_destroy(), _GSS_statistics, GNUNET_CONTAINER_multihashmap_destroy(), GNUNET_ERROR_TYPE_WARNING, GNUNET_log, GNUNET_MESSAGE_TYPE_SET_RESULT, GNUNET_MQ_msg, GNUNET_MQ_send(), GNUNET_NO, GNUNET_SET_STATUS_FAILURE, GNUNET_STATISTICS_update(), GNUNET_YES, msg, and op.

Referenced by handle_intersection_p2p_bf(), handle_intersection_p2p_done(), handle_intersection_p2p_element_info(), and process_bf().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ send_bloomfilter()

static void send_bloomfilter ( struct Operation op)
static

Send a bloomfilter to our peer.

After the result done message has been sent to the client, destroy the evaluate operation.

Parameters
opintersection operation

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

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;
488  ev = GNUNET_MQ_msg_extra (msg,
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;
517  ev = GNUNET_MQ_msg_extra (msg,
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 }
static int iterator_bf_create(void *cls, const struct GNUNET_HashCode *key, void *value)
Create initial bloomfilter based on all the elements given.
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.
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_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...
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.
int GNUNET_CONTAINER_multihashmap_iterate(struct GNUNET_CONTAINER_MultiHashMap *map, GNUNET_CONTAINER_MultiHashMapIteratorCallback it, void *it_cls)
Iterate over all entries in the map.
@ GNUNET_SYSERR
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_free(ptr)
Wrapper around free.
#define GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF
Bloom filter message for intersection exchange started by Bob.
Bloom filter messages exchanged for set intersection calculation.

References _GSS_statistics, GNUNET_assert, GNUNET_CONTAINER_bloomfilter_free(), GNUNET_CONTAINER_bloomfilter_get_raw_data(), GNUNET_CONTAINER_bloomfilter_init(), GNUNET_CONTAINER_multihashmap_iterate(), GNUNET_CRYPTO_QUALITY_NONCE, GNUNET_CRYPTO_random_u32(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, GNUNET_log, GNUNET_malloc, GNUNET_memcpy, GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF, GNUNET_MQ_msg_extra, GNUNET_MQ_send(), GNUNET_NO, GNUNET_STATISTICS_update(), GNUNET_SYSERR, iterator_bf_create(), msg, and op.

Referenced by begin_bf_exchange(), and process_bf().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ send_client_done_and_destroy()

static void send_client_done_and_destroy ( void *  cls)
static

Signal to the client that the operation has finished and destroy the operation.

Parameters
clsoperation to destroy

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

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 }
@ GNUNET_SET_STATUS_DONE
Success, all elements have been sent (and received).

References _GSS_operation_destroy(), _GSS_statistics, GNUNET_SET_ResultMessage::element_type, GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_MESSAGE_TYPE_SET_RESULT, GNUNET_MQ_msg, GNUNET_MQ_send(), GNUNET_NO, GNUNET_SET_STATUS_DONE, GNUNET_STATISTICS_update(), GNUNET_YES, op, GNUNET_SET_ResultMessage::request_id, and GNUNET_SET_ResultMessage::result_status.

Referenced by handle_intersection_p2p_done(), intersection_channel_death(), and send_remaining_elements().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ finished_local_operations()

static void finished_local_operations ( void *  cls)
static

Remember that we are done dealing with the local client AND have sent the other peer our message that we are done, so we are not just waiting for the channel to die before telling the local client that we are done as our last act.

Parameters
clsthe struct Operation.

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

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 }

References GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_YES, op, and PHASE_FINISHED.

Referenced by send_p2p_done().

Here is the caller graph for this function:

◆ send_p2p_done()

static void send_p2p_done ( struct Operation op)
static

Notify the other peer that we are done.

Once this message is out, we still need to notify the local client that we are done.

Parameters
opoperation to notify for.

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

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 }
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...
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_INTERSECTION_P2P_DONE
Intersection operation is done.
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.

References IntersectionDoneMessage::element_xor_hash, IntersectionDoneMessage::final_element_count, finished_local_operations(), GNUNET_assert, GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE, GNUNET_MQ_msg, GNUNET_MQ_notify_sent(), GNUNET_MQ_send(), GNUNET_NO, op, and PHASE_MUST_SEND_DONE.

Referenced by process_bf(), and send_remaining_elements().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ send_remaining_elements()

static void send_remaining_elements ( void *  cls)
static

Send all elements in the full result iterator.

Parameters
clsthe struct Operation *

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

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  {
650  send_p2p_done (op);
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",
662  GNUNET_h2s (&ee->element_hash),
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);
669  rm->result_status = htons (GNUNET_SET_STATUS_OK);
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 }
static int res
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.
static void send_client_done_and_destroy(void *cls)
Signal to the client that the operation has finished and destroy the operation.
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.
void GNUNET_CONTAINER_multihashmap_iterator_destroy(struct GNUNET_CONTAINER_MultiHashMapIterator *iter)
Destroy a multihashmap iterator.
Element stored in a set.

References GNUNET_SET_Element::data, ElementEntry::element, ElementEntry::element_hash, GNUNET_SET_Element::element_type, GNUNET_SET_ResultMessage::element_type, GNUNET_assert, GNUNET_CONTAINER_multihashmap_iterator_destroy(), GNUNET_CONTAINER_multihashmap_iterator_next(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_memcpy, GNUNET_MESSAGE_TYPE_SET_RESULT, GNUNET_MQ_msg_extra, GNUNET_MQ_notify_sent(), GNUNET_MQ_send(), GNUNET_NO, GNUNET_SET_STATUS_OK, op, PHASE_DONE_RECEIVED, PHASE_FINISHED, PHASE_MUST_SEND_DONE, GNUNET_SET_ResultMessage::request_id, res, GNUNET_SET_ResultMessage::result_status, send_client_done_and_destroy(), send_p2p_done(), and GNUNET_SET_Element::size.

Referenced by handle_intersection_p2p_done(), and process_bf().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ initialize_map_unfiltered()

static int initialize_map_unfiltered ( void *  cls,
const struct GNUNET_HashCode key,
void *  value 
)
static

Fills the "my_elements" hashmap with the initial set of (non-deleted) elements from the set of the specification.

Parameters
clsclosure with the struct Operation *
keycurrent key code for the element
valuevalue in the hash map with the struct ElementEntry *
Returns
GNUNET_YES (we should continue to iterate)

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

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",
707  GNUNET_h2s (&ee->element_hash),
708  ee->element.size);
710  GNUNET_CONTAINER_multihashmap_put (op->state->my_elements,
711  &ee->element_hash,
712  ee,
714  return GNUNET_YES;
715 }

References _GSS_is_element_of_operation(), ElementEntry::element, ElementEntry::element_hash, GNUNET_break, GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY, GNUNET_CRYPTO_hash_xor(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_NO, GNUNET_YES, op, GNUNET_SET_Element::size, and value.

Referenced by begin_bf_exchange().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ send_element_count()

static void send_element_count ( struct Operation op)
static

Send our element count to the peer, in case our element count is lower than theirs.

Parameters
opintersection operation

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

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 }
#define GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO
Information about the element count for intersection.
During intersection, the first (and possibly second) message send it the number of elements in the se...

References GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO, GNUNET_MQ_msg, GNUNET_MQ_send(), msg, and op.

Referenced by intersection_accept().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ begin_bf_exchange()

static void begin_bf_exchange ( struct Operation op)
static

We go first, initialize our map with all elements and send the first Bloom filter.

Parameters
opoperation to start exchange for

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

748 {
749  op->state->phase = PHASE_BF_EXCHANGE;
750  GNUNET_CONTAINER_multihashmap_iterate (op->set->content->elements,
752  op);
754 }
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.

References GNUNET_CONTAINER_multihashmap_iterate(), initialize_map_unfiltered(), op, PHASE_BF_EXCHANGE, and send_bloomfilter().

Referenced by handle_intersection_p2p_element_info(), and intersection_accept().

Here is the call graph for this function:
Here is the caller 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
msgthe header of the message

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

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 }
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 fail_intersection_operation(struct Operation *op)
Inform the client that the intersection operation has failed, and proceed to destroy the evaluate ope...
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:872
#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.

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:

◆ process_bf()

static void process_bf ( struct Operation op)
static

Process a Bloomfilter once we got all the chunks.

Parameters
opthe intersection operation

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

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 
821  case PHASE_BF_EXCHANGE:
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 
833  case PHASE_DONE_RECEIVED:
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  }
868  send_p2p_done (op);
869  return;
870  }
871  op->state->phase = PHASE_BF_EXCHANGE;
873 }
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 int filtered_map_initialization(void *cls, const struct GNUNET_HashCode *key, void *value)
Fills the "my_elements" hashmap with all relevant elements.
unsigned int GNUNET_CONTAINER_multihashmap_size(const struct GNUNET_CONTAINER_MultiHashMap *map)
Get the number of key-value pairs 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_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
@ GNUNET_SET_RESULT_FULL
Client gets every element in the resulting set.

References fail_intersection_operation(), filtered_map_initialization(), GNUNET_break_op, GNUNET_CONTAINER_bloomfilter_free(), GNUNET_CONTAINER_multihashmap_iterate(), GNUNET_CONTAINER_multihashmap_iterator_create(), GNUNET_CONTAINER_multihashmap_size(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_memcmp, GNUNET_SET_RESULT_FULL, iterator_bf_reduce(), op, PHASE_BF_EXCHANGE, PHASE_COUNT_SENT, PHASE_DONE_RECEIVED, PHASE_FINISHED, PHASE_INITIAL, PHASE_MUST_SEND_DONE, send_bloomfilter(), send_p2p_done(), and send_remaining_elements().

Referenced by handle_intersection_p2p_bf().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ 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 884 of file gnunet-service-set_intersection.c.

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 }
@ GNUNET_OK

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 905 of file gnunet-service-set_intersection.c.

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:
921  case PHASE_BF_EXCHANGE:
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 }
static void process_bf(struct Operation *op)
Process a Bloomfilter once we got all the chunks.
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:

◆ filter_all()

static int filter_all ( void *  cls,
const struct GNUNET_HashCode key,
void *  value 
)
static

Remove all elements from our hashmap.

Parameters
clsclosure with the struct Operation *
keycurrent key code
valuevalue in the hash map
Returns
GNUNET_YES (we should continue to iterate)

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

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 }

References ElementEntry::element, ElementEntry::element_hash, GNUNET_assert, GNUNET_break, GNUNET_CONTAINER_multihashmap_remove(), GNUNET_CRYPTO_hash_xor(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_log, GNUNET_YES, op, send_client_removed_element(), GNUNET_SET_Element::size, and value.

Referenced by handle_intersection_p2p_done().

Here is the call graph for this function:
Here is the caller 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
idmthe message

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

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 }
static int filter_all(void *cls, const struct GNUNET_HashCode *key, void *value)
Remove all elements from our hashmap.

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:

◆ intersection_evaluate()

static struct OperationState* intersection_evaluate ( struct Operation op,
const struct GNUNET_MessageHeader opaque_context 
)
static

Initiate a set intersection operation with a remote peer.

Parameters
opoperation that is created, should be initialized to begin the evaluation
opaque_contextmessage to be transmitted to the listener to convince it to accept, may be NULL
Returns
operation-specific state to keep in op

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

1108 {
1109  struct OperationState *state;
1110  struct GNUNET_MQ_Envelope *ev;
1111  struct OperationRequestMessage *msg;
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 }
enum State state
current state of profiling
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#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_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST
Request a set operation from a remote peer.
State of an evaluate operation with another peer.

References GNUNET_break, GNUNET_CONTAINER_multihashmap_create(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST, GNUNET_MQ_msg_nested_mh, GNUNET_MQ_send(), GNUNET_new, GNUNET_SET_OPERATION_INTERSECTION, GNUNET_YES, msg, op, PHASE_COUNT_SENT, PHASE_INITIAL, and state.

Referenced by _GSS_intersection_vt().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ intersection_accept()

static struct OperationState* intersection_accept ( struct Operation op)
static

Accept an intersection operation request from a remote peer.

Only initializes the private operation state.

Parameters
opoperation that will be accepted as an intersection operation

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

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 }
static void send_element_count(struct Operation *op)
Send our element count to the peer, in case our element count is lower than theirs.
#define GNUNET_MIN(a, b)

References begin_bf_exchange(), GNUNET_CONTAINER_multihashmap_create(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_MIN, GNUNET_new, GNUNET_YES, op, PHASE_COUNT_SENT, PHASE_INITIAL, send_element_count(), and state.

Referenced by _GSS_intersection_vt().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ intersection_op_cancel()

static void intersection_op_cancel ( struct Operation op)
static

Destroy the intersection operation.

Only things specific to the intersection operation are destroyed.

Parameters
opintersection operation to destroy

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

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 }

References GNUNET_assert, GNUNET_CONTAINER_bloomfilter_free(), GNUNET_CONTAINER_multihashmap_destroy(), GNUNET_CONTAINER_multihashmap_iterator_destroy(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, GNUNET_log, and op.

Referenced by _GSS_intersection_vt().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ intersection_set_create()

static struct SetState* intersection_set_create ( )
static

Create a new set supporting the intersection operation.

Returns
the newly created set

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

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 }
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.

References SetState::current_set_element_count, GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, and GNUNET_new.

Referenced by _GSS_intersection_vt().

Here is the caller graph for this function:

◆ intersection_add()

static void intersection_add ( struct SetState set_state,
struct ElementEntry ee 
)
static

Add the element from the given element message to the set.

Parameters
set_statestate of the set want to add to
eethe element to add to the set

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

1250 {
1251  set_state->current_set_element_count++;
1252 }

References SetState::current_set_element_count.

Referenced by _GSS_intersection_vt().

Here is the caller graph for this function:

◆ intersection_set_destroy()

static void intersection_set_destroy ( struct SetState set_state)
static

Destroy a set that supports the intersection operation.

Parameters
set_statethe set to destroy

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

1262 {
1263  GNUNET_free (set_state);
1264 }

References GNUNET_free.

Referenced by _GSS_intersection_vt().

Here is the caller graph for this function:

◆ intersection_remove()

static void intersection_remove ( struct SetState set_state,
struct ElementEntry element 
)
static

Remove the element given in the element message from the set.

Parameters
set_statestate of the set to remove from
elementset element to remove

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

1276 {
1277  GNUNET_assert (0 < set_state->current_set_element_count);
1278  set_state->current_set_element_count--;
1279 }

References SetState::current_set_element_count, and GNUNET_assert.

Referenced by _GSS_intersection_vt().

Here is the caller graph for this function:

◆ intersection_channel_death()

static void intersection_channel_death ( struct Operation op)
static

Callback for channel death for the intersection operation.

Parameters
opoperation that lost the channel

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

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 }

References _GSS_operation_destroy(), GNUNET_YES, op, and send_client_done_and_destroy().

Referenced by _GSS_intersection_vt().

Here is the call graph for this function:
Here is the caller graph for this function:

◆ _GSS_intersection_vt()

const struct SetVT* _GSS_intersection_vt ( void  )

Get the table with implementing functions for set intersection.

Returns
the operation specific VTable

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

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 }
static void intersection_remove(struct SetState *set_state, struct ElementEntry *element)
Remove the element given in the element message from the set.
static void intersection_set_destroy(struct SetState *set_state)
Destroy a set that supports the intersection operation.
static struct SetState * intersection_set_create()
Create a new set supporting the intersection operation.
static void intersection_op_cancel(struct Operation *op)
Destroy the intersection operation.
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 struct OperationState * intersection_accept(struct Operation *op)
Accept an intersection operation request 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.
Dispatch table for a specific set operation.
SetCreateImpl create
Callback for the set creation.

References SetVT::create, intersection_accept(), intersection_add(), intersection_channel_death(), intersection_evaluate(), intersection_op_cancel(), intersection_remove(), intersection_set_create(), and intersection_set_destroy().

Referenced by handle_client_copy_lazy_connect(), and handle_client_create_set().

Here is the call graph for this function:
Here is the caller graph for this function: