GNUnet  0.11.x
Data Structures | Macros | Enumerations | Functions
gnunet-service-set_union.c File Reference

two-peer set operations More...

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

Go to the source code of this file.

Data Structures

struct  OperationState
 State of an evaluate operation with another peer. More...
 
struct  KeyEntry
 The key entry is used to associate an ibf key with an element. More...
 
struct  SendElementClosure
 Used as a closure for sending elements with a specific IBF key. More...
 
struct  SetState
 Extra state required for efficient set intersection. More...
 
struct  GetElementContext
 Context for op_get_element_iterator. More...
 

Macros

#define LOG(kind, ...)   GNUNET_log_from (kind, "set-union", __VA_ARGS__)
 
#define SE_STRATA_COUNT   32
 Number of IBFs in a strata estimator. More...
 
#define SE_IBF_SIZE   80
 Size of the IBFs in the strata estimator. More...
 
#define SE_IBF_HASH_NUM   4
 The hash num parameter for the difference digests and strata estimators. More...
 
#define MAX_BUCKETS_PER_MESSAGE   ((1 << 15) / IBF_BUCKET_SIZE)
 Number of buckets that can be transmitted in one message. More...
 
#define MAX_IBF_ORDER   (20)
 The maximum size of an ibf we use is 2^(MAX_IBF_ORDER). More...
 
#define IBF_ALPHA   4
 Number of buckets used in the ibf per estimated difference. More...
 

Enumerations

enum  UnionOperationPhase {
  PHASE_EXPECT_SE , PHASE_EXPECT_IBF , PHASE_EXPECT_IBF_CONT , PHASE_INVENTORY_ACTIVE ,
  PHASE_INVENTORY_PASSIVE , PHASE_FINISH_CLOSING , PHASE_FINISH_WAITING , PHASE_DONE ,
  PHASE_FULL_SENDING , PHASE_EXPECT_SE , PHASE_EXPECT_IBF , PHASE_EXPECT_IBF_LAST ,
  PHASE_ACTIVE_DECODING , PHASE_PASSIVE_DECODING , PHASE_FINISH_CLOSING , PHASE_FINISH_WAITING ,
  PHASE_FINISHED , PHASE_FULL_SENDING , PHASE_FULL_RECEIVING
}
 Current phase we are in for a union operation. More...
 

Functions

static int destroy_key_to_element_iter (void *cls, uint32_t key, void *value)
 Iterator over hash map entries, called to destroy the linked list of colliding ibf key entries. More...
 
static void union_op_cancel (struct Operation *op)
 Destroy the union operation. More...
 
static void fail_union_operation (struct Operation *op)
 Inform the client that the union operation has failed, and proceed to destroy the evaluate operation. More...
 
static struct IBF_Key get_ibf_key (const struct GNUNET_HashCode *src)
 Derive the IBF key from a hash code and a salt. More...
 
static int op_get_element_iterator (void *cls, uint32_t key, void *value)
 Iterator over the mapping from IBF keys to element entries. More...
 
static struct KeyEntryop_get_element (struct Operation *op, const struct GNUNET_HashCode *element_hash)
 Determine whether the given element is already in the operation's element set. More...
 
static void op_register_element (struct Operation *op, struct ElementEntry *ee, int received)
 Insert an element into the union operation's key-to-element mapping. More...
 
static void salt_key (const struct IBF_Key *k_in, uint32_t salt, struct IBF_Key *k_out)
 FIXME. More...
 
static void unsalt_key (const struct IBF_Key *k_in, uint32_t salt, struct IBF_Key *k_out)
 FIXME. More...
 
static int prepare_ibf_iterator (void *cls, uint32_t key, void *value)
 Insert a key into an ibf. More...
 
static int init_key_to_element_iterator (void *cls, const struct GNUNET_HashCode *key, void *value)
 Iterator for initializing the key-to-element mapping of a union operation. More...
 
static void initialize_key_to_element (struct Operation *op)
 Initialize the IBF key to element mapping local to this set operation. More...
 
static int prepare_ibf (struct Operation *op, uint32_t size)
 Create an ibf with the operation's elements of the specified size. More...
 
static int send_ibf (struct Operation *op, uint16_t ibf_order)
 Send an ibf of appropriate size. More...
 
static unsigned int get_order_from_difference (unsigned int diff)
 Compute the necessary order of an ibf from the size of the symmetric set difference. More...
 
static int send_full_element_iterator (void *cls, const struct GNUNET_HashCode *key, void *value)
 Send a set element. More...
 
static void send_full_set (struct Operation *op)
 Switch to full set transmission for op. More...
 
int check_union_p2p_strata_estimator (void *cls, const struct StrataEstimatorMessage *msg)
 Handle a strata estimator from a remote peer. More...
 
void handle_union_p2p_strata_estimator (void *cls, const struct StrataEstimatorMessage *msg)
 Handle a strata estimator from a remote peer. More...
 
static int send_offers_iterator (void *cls, uint32_t key, void *value)
 Iterator to send elements to a remote peer. More...
 
static void send_offers_for_key (struct Operation *op, struct IBF_Key ibf_key)
 Send offers (in the form of GNUNET_Hash-es) to the remote peer for the given IBF key. More...
 
static int decode_and_send (struct Operation *op)
 Decode which elements are missing on each side, and send the appropriate offers and inquiries. More...
 
int check_union_p2p_ibf (void *cls, const struct IBFMessage *msg)
 Check an IBF message from a remote peer. More...
 
void handle_union_p2p_ibf (void *cls, const struct IBFMessage *msg)
 Handle an IBF message from a remote peer. More...
 
static void send_client_element (struct Operation *op, struct GNUNET_SET_Element *element, int status)
 Send a result message to the client indicating that there is a new element. More...
 
static void send_client_done (void *cls)
 Signal to the client that the operation has finished and destroy the operation. More...
 
static void maybe_finish (struct Operation *op)
 Tests if the operation is finished, and if so notify. More...
 
int check_union_p2p_elements (void *cls, const struct GNUNET_SET_ElementMessage *emsg)
 Check an element message from a remote peer. More...
 
void handle_union_p2p_elements (void *cls, const struct GNUNET_SET_ElementMessage *emsg)
 Handle an element message from a remote peer. More...
 
int check_union_p2p_full_element (void *cls, const struct GNUNET_SET_ElementMessage *emsg)
 Check a full element message from a remote peer. More...
 
void handle_union_p2p_full_element (void *cls, const struct GNUNET_SET_ElementMessage *emsg)
 Handle an element message from a remote peer. More...
 
int check_union_p2p_inquiry (void *cls, const struct InquiryMessage *msg)
 Send offers (for GNUNET_Hash-es) in response to inquiries (for IBF_Key-s). More...
 
void handle_union_p2p_inquiry (void *cls, const struct InquiryMessage *msg)
 Send offers (for GNUNET_Hash-es) in response to inquiries (for IBF_Key-s). More...
 
static int send_missing_full_elements_iter (void *cls, uint32_t key, void *value)
 Iterator over hash map entries, called to destroy the linked list of colliding ibf key entries. More...
 
void handle_union_p2p_request_full (void *cls, const struct GNUNET_MessageHeader *mh)
 Handle a request for full set transmission. More...
 
void handle_union_p2p_full_done (void *cls, const struct GNUNET_MessageHeader *mh)
 Handle a "full done" message. More...
 
int check_union_p2p_demand (void *cls, const struct GNUNET_MessageHeader *mh)
 Check a demand by the other peer for elements based on a list of struct GNUNET_HashCodes. More...
 
void handle_union_p2p_demand (void *cls, const struct GNUNET_MessageHeader *mh)
 Handle a demand by the other peer for elements based on a list of struct GNUNET_HashCodes. More...
 
int check_union_p2p_offer (void *cls, const struct GNUNET_MessageHeader *mh)
 Check offer (of struct GNUNET_HashCodes). More...
 
void handle_union_p2p_offer (void *cls, const struct GNUNET_MessageHeader *mh)
 Handle offers (of struct GNUNET_HashCodes) and respond with demands (of struct GNUNET_HashCodes). More...
 
void handle_union_p2p_done (void *cls, const struct GNUNET_MessageHeader *mh)
 Handle a done message from a remote peer. More...
 
void handle_union_p2p_over (void *cls, const struct GNUNET_MessageHeader *mh)
 Handle a over message from a remote peer. More...
 
static struct OperationStateunion_evaluate (struct Operation *op, const struct GNUNET_MessageHeader *opaque_context)
 Initiate operation to evaluate a set union with a remote peer. More...
 
static struct OperationStateunion_accept (struct Operation *op)
 Accept an union operation request from a remote peer. More...
 
static struct SetStateunion_set_create (void)
 Create a new set supporting the union operation. More...
 
static void union_add (struct SetState *set_state, struct ElementEntry *ee)
 Add the element from the given element message to the set. More...
 
static void union_remove (struct SetState *set_state, struct ElementEntry *ee)
 Remove the element given in the element message from the set. More...
 
static void union_set_destroy (struct SetState *set_state)
 Destroy a set that supports the union operation. More...
 
static struct SetStateunion_copy_state (struct SetState *state)
 Copy union-specific set state. More...
 
static void union_channel_death (struct Operation *op)
 Handle case where channel went down for an operation. More...
 
const struct SetVT_GSS_union_vt ()
 Get the table with implementing functions for set union. More...
 

Detailed Description

two-peer set operations

Author
Florian Dold
Christian Grothoff

Definition in file gnunet-service-set_union.c.

Macro Definition Documentation

◆ LOG

#define LOG (   kind,
  ... 
)    GNUNET_log_from (kind, "set-union", __VA_ARGS__)

Definition at line 37 of file gnunet-service-set_union.c.

◆ SE_STRATA_COUNT

#define SE_STRATA_COUNT   32

Number of IBFs in a strata estimator.

Definition at line 43 of file gnunet-service-set_union.c.

◆ SE_IBF_SIZE

#define SE_IBF_SIZE   80

Size of the IBFs in the strata estimator.

Definition at line 48 of file gnunet-service-set_union.c.

◆ SE_IBF_HASH_NUM

#define SE_IBF_HASH_NUM   4

The hash num parameter for the difference digests and strata estimators.

Definition at line 53 of file gnunet-service-set_union.c.

◆ MAX_BUCKETS_PER_MESSAGE

#define MAX_BUCKETS_PER_MESSAGE   ((1 << 15) / IBF_BUCKET_SIZE)

Number of buckets that can be transmitted in one message.

Definition at line 58 of file gnunet-service-set_union.c.

◆ MAX_IBF_ORDER

#define MAX_IBF_ORDER   (20)

The maximum size of an ibf we use is 2^(MAX_IBF_ORDER).

Choose this value so that computing the IBF is still cheaper than transmitting all values.

Definition at line 65 of file gnunet-service-set_union.c.

◆ IBF_ALPHA

#define IBF_ALPHA   4

Number of buckets used in the ibf per estimated difference.

Definition at line 71 of file gnunet-service-set_union.c.

Enumeration Type Documentation

◆ UnionOperationPhase

Current phase we are in for a union operation.

Enumerator
PHASE_EXPECT_SE 

We sent the request message, and expect a strata estimator.

PHASE_EXPECT_IBF 

We sent the strata estimator, and expect an IBF.

This phase is entered once upon initialization and later via #PHASE_EXPECT_ELEMENTS_AND_REQUESTS.

XXX: could use better wording. XXX: repurposed to also expect a "request full set" message, should be renamed

After receiving the complete IBF, we enter #PHASE_EXPECT_ELEMENTS

PHASE_EXPECT_IBF_CONT 

Continuation for multi part IBFs.

PHASE_INVENTORY_ACTIVE 

We are decoding an IBF.

PHASE_INVENTORY_PASSIVE 

The other peer is decoding the IBF we just sent.

PHASE_FINISH_CLOSING 

The protocol is almost finished, but we still have to flush our message queue and/or expect some elements.

PHASE_FINISH_WAITING 

In the penultimate phase, we wait until all our demands are satisfied.

Then we send a done message, and wait for another done message.

PHASE_DONE 

In the ultimate phase, we wait until our demands are satisfied and then quit (sending another DONE message).

PHASE_FULL_SENDING 

After sending the full set, wait for responses with the elements that the local peer is missing.

PHASE_EXPECT_SE 

We sent the request message, and expect a strata estimator.

PHASE_EXPECT_IBF 

We sent the strata estimator, and expect an IBF.

This phase is entered once upon initialization and later via #PHASE_EXPECT_ELEMENTS_AND_REQUESTS.

XXX: could use better wording. XXX: repurposed to also expect a "request full set" message, should be renamed

After receiving the complete IBF, we enter #PHASE_EXPECT_ELEMENTS

PHASE_EXPECT_IBF_LAST 

Continuation for multi part IBFs.

PHASE_ACTIVE_DECODING 

We are decoding an IBF.

PHASE_PASSIVE_DECODING 

The other peer is decoding the IBF we just sent.

PHASE_FINISH_CLOSING 

The protocol is almost finished, but we still have to flush our message queue and/or expect some elements.

PHASE_FINISH_WAITING 

In the penultimate phase, we wait until all our demands are satisfied.

Then we send a done message, and wait for another done message.

PHASE_FINISHED 

In the ultimate phase, we wait until our demands are satisfied and then quit (sending another DONE message).

PHASE_FULL_SENDING 

After sending the full set, wait for responses with the elements that the local peer is missing.

PHASE_FULL_RECEIVING 

Phase that receives full set first and then sends elements that are the local peer missing.

Definition at line 77 of file gnunet-service-set_union.c.

78 {
83 
94 
99 
104 
109 
115 
123 
129  PHASE_DONE,
130 
136 };
@ PHASE_INVENTORY_PASSIVE
The other peer is decoding the IBF we just sent.
@ PHASE_FINISH_CLOSING
The protocol is almost finished, but we still have to flush our message queue and/or expect some elem...
@ PHASE_DONE
In the ultimate phase, we wait until our demands are satisfied and then quit (sending another DONE me...
@ PHASE_EXPECT_SE
We sent the request message, and expect a strata estimator.
@ PHASE_FINISH_WAITING
In the penultimate phase, we wait until all our demands are satisfied.
@ PHASE_EXPECT_IBF_CONT
Continuation for multi part IBFs.
@ PHASE_FULL_SENDING
After sending the full set, wait for responses with the elements that the local peer is missing.
@ PHASE_EXPECT_IBF
We sent the strata estimator, and expect an IBF.
@ PHASE_INVENTORY_ACTIVE
We are decoding an IBF.

Function Documentation

◆ destroy_key_to_element_iter()

static int destroy_key_to_element_iter ( void *  cls,
uint32_t  key,
void *  value 
)
static

Iterator over hash map entries, called to destroy the linked list of colliding ibf key entries.

Parameters
clsclosure
keycurrent key code
valuevalue in the hash map
Returns
GNUNET_YES if we should continue to iterate, GNUNET_NO if not.

Definition at line 290 of file gnunet-service-set_union.c.

293 {
294  struct KeyEntry *k = value;
295 
296  GNUNET_assert (NULL != k);
297  if (GNUNET_YES == k->element->remote)
298  {
299  GNUNET_free (k->element);
300  k->element = NULL;
301  }
302  GNUNET_free (k);
303  return GNUNET_YES;
304 }
static char * value
Value of the record to add/remove.
@ GNUNET_YES
Definition: gnunet_common.h:97
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_free(ptr)
Wrapper around free.
int remote
GNUNET_YES if the element is a remote element, and does not belong to the operation's set.
The key entry is used to associate an ibf key with an element.
struct ElementEntry * element
The actual element associated with the key.

References KeyEntry::element, GNUNET_assert, GNUNET_free, GNUNET_YES, ElementEntry::remote, and value.

Referenced by union_op_cancel().

Here is the caller graph for this function:

◆ union_op_cancel()

static void union_op_cancel ( struct Operation op)
static

Destroy the union operation.

Only things specific to the union operation are destroyed.

Parameters
opunion operation to destroy

Definition at line 314 of file gnunet-service-set_union.c.

315 {
317  "destroying union op\n");
318  /* check if the op was canceled twice */
319  GNUNET_assert (NULL != op->state);
320  if (NULL != op->state->remote_ibf)
321  {
322  ibf_destroy (op->state->remote_ibf);
323  op->state->remote_ibf = NULL;
324  }
325  if (NULL != op->state->demanded_hashes)
326  {
327  GNUNET_CONTAINER_multihashmap_destroy (op->state->demanded_hashes);
328  op->state->demanded_hashes = NULL;
329  }
330  if (NULL != op->state->local_ibf)
331  {
332  ibf_destroy (op->state->local_ibf);
333  op->state->local_ibf = NULL;
334  }
335  if (NULL != op->state->se)
336  {
337  strata_estimator_destroy (op->state->se);
338  op->state->se = NULL;
339  }
340  if (NULL != op->state->key_to_element)
341  {
342  GNUNET_CONTAINER_multihashmap32_iterate (op->state->key_to_element,
344  NULL);
345  GNUNET_CONTAINER_multihashmap32_destroy (op->state->key_to_element);
346  op->state->key_to_element = NULL;
347  }
348  GNUNET_free (op->state);
349  op->state = NULL;
351  "destroying union op done\n");
352 }
static struct GNUNET_ARM_Operation * op
Current operation.
Definition: gnunet-arm.c:144
static int destroy_key_to_element_iter(void *cls, uint32_t key, void *value)
Iterator over hash map entries, called to destroy the linked list of colliding ibf key entries.
#define LOG(kind,...)
void strata_estimator_destroy(struct StrataEstimator *se)
Destroy a strata estimator, free all of its resources.
int GNUNET_CONTAINER_multihashmap32_iterate(struct GNUNET_CONTAINER_MultiHashMap32 *map, GNUNET_CONTAINER_MulitHashMapIterator32Callback it, void *it_cls)
Iterate over all entries in the map.
void GNUNET_CONTAINER_multihashmap_destroy(struct GNUNET_CONTAINER_MultiHashMap *map)
Destroy a hash map.
void GNUNET_CONTAINER_multihashmap32_destroy(struct GNUNET_CONTAINER_MultiHashMap32 *map)
Destroy a 32-bit key hash map.
@ GNUNET_ERROR_TYPE_DEBUG
void ibf_destroy(struct InvertibleBloomFilter *ibf)
Destroy all resources associated with the invertible bloom filter.
Definition: ibf.c:403

References destroy_key_to_element_iter(), GNUNET_assert, GNUNET_CONTAINER_multihashmap32_destroy(), GNUNET_CONTAINER_multihashmap32_iterate(), GNUNET_CONTAINER_multihashmap_destroy(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, ibf_destroy(), LOG, op, and strata_estimator_destroy().

Referenced by _GSS_union_vt().

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

◆ fail_union_operation()

static void fail_union_operation ( struct Operation op)
static

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

Parameters
opthe union operation to fail

Definition at line 362 of file gnunet-service-set_union.c.

363 {
364  struct GNUNET_MQ_Envelope *ev;
366 
368  "union operation failed\n");
370  msg->result_status = htons (GNUNET_SET_STATUS_FAILURE);
371  msg->request_id = htonl (op->client_request_id);
372  msg->element_type = htons (0);
373  GNUNET_MQ_send (op->set->cs->mq,
374  ev);
376 }
struct GNUNET_MessageHeader * msg
Definition: 005.c:2
void _GSS_operation_destroy(struct Operation *op, int gc)
Destroy the given operation.
@ GNUNET_ERROR_TYPE_WARNING
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:355
#define GNUNET_MQ_msg(mvar, type)
Allocate a GNUNET_MQ_Envelope.
Definition: gnunet_mq_lib.h:67
#define GNUNET_MESSAGE_TYPE_SET_RESULT
Create an empty set.
@ GNUNET_SET_STATUS_FAILURE
The other peer refused to to the operation with us, or something went wrong.
Message sent by the service to the client to indicate an element that is removed (set intersection) o...
Definition: set.h:245

References _GSS_operation_destroy(), GNUNET_ERROR_TYPE_WARNING, GNUNET_MESSAGE_TYPE_SET_RESULT, GNUNET_MQ_msg, GNUNET_MQ_send(), GNUNET_SET_STATUS_FAILURE, GNUNET_YES, LOG, msg, and op.

Referenced by decode_and_send(), handle_union_p2p_demand(), handle_union_p2p_done(), handle_union_p2p_elements(), handle_union_p2p_full_done(), handle_union_p2p_full_element(), handle_union_p2p_ibf(), handle_union_p2p_request_full(), and handle_union_p2p_strata_estimator().

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

◆ get_ibf_key()

static struct IBF_Key get_ibf_key ( const struct GNUNET_HashCode src)
static

Derive the IBF key from a hash code and a salt.

Parameters
srcthe hash code
Returns
the derived IBF key

Definition at line 362 of file gnunet-service-set_union.c.

388 {
389  struct IBF_Key key;
390  uint16_t salt = 0;
391 
393  GNUNET_CRYPTO_kdf (&key, sizeof(key),
394  src, sizeof *src,
395  &salt, sizeof(salt),
396  NULL, 0));
397  return key;
398 }
struct GNUNET_HashCode key
The key used in the DHT.
static struct GNUNET_CRYPTO_PowSalt salt
Salt for PoW calcualations.
@ GNUNET_OK
Definition: gnunet_common.h:95
enum GNUNET_GenericReturnValue GNUNET_CRYPTO_kdf(void *result, size_t out_len, const void *xts, size_t xts_len, const void *skm, size_t skm_len,...)
Derive key.
Definition: crypto_kdf.c:90
Keys that can be inserted into and removed from an IBF.
Definition: ibf.h:46

Referenced by op_get_element(), op_register_element(), union_add(), and union_remove().

Here is the caller graph for this function:

◆ op_get_element_iterator()

static int op_get_element_iterator ( void *  cls,
uint32_t  key,
void *  value 
)
static

Iterator over the mapping from IBF keys to element entries.

Checks if we have an element with a given GNUNET_HashCode.

Parameters
clsclosure
keycurrent key code
valuevalue in the hash map
Returns
GNUNET_YES if we should search further, GNUNET_NO if we've found the element.

Definition at line 429 of file gnunet-service-set_union.c.

432 {
433  struct GetElementContext *ctx = cls;
434  struct KeyEntry *k = value;
435 
436  GNUNET_assert (NULL != k);
438  &ctx->hash))
439  {
440  ctx->k = k;
441  return GNUNET_NO;
442  }
443  return GNUNET_YES;
444 }
static struct GNUNET_DNSSTUB_Context * ctx
Context for DNS resolution.
@ GNUNET_NO
Definition: gnunet_common.h:94
int GNUNET_CRYPTO_hash_cmp(const struct GNUNET_HashCode *h1, const struct GNUNET_HashCode *h2)
Compare function for HashCodes, producing a total ordering of all hashcodes.
Definition: crypto_hash.c:201
struct GNUNET_HashCode element_hash
Hash of the element.
Context for op_get_element_iterator.

References ctx, KeyEntry::element, ElementEntry::element_hash, GNUNET_assert, GNUNET_CRYPTO_hash_cmp(), GNUNET_NO, GNUNET_YES, and value.

Referenced by op_get_element().

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

◆ op_get_element()

static struct KeyEntry* op_get_element ( struct Operation op,
const struct GNUNET_HashCode element_hash 
)
static

Determine whether the given element is already in the operation's element set.

Parameters
opoperation that should be tested for 'element_hash'
element_hashhash of the element to look for
Returns
GNUNET_YES if the element has been found, GNUNET_NO otherwise

Definition at line 456 of file gnunet-service-set_union.c.

458 {
459  int ret;
460  struct IBF_Key ibf_key;
461  struct GetElementContext ctx = { { { 0 } }, 0 };
462 
463  ctx.hash = *element_hash;
464 
465  ibf_key = get_ibf_key (element_hash);
466  ret = GNUNET_CONTAINER_multihashmap32_get_multiple (op->state->key_to_element,
467  (uint32_t) ibf_key.key_val,
469  &ctx);
470 
471  /* was the iteration aborted because we found the element? */
472  if (GNUNET_SYSERR == ret)
473  {
474  GNUNET_assert (NULL != ctx.k);
475  return ctx.k;
476  }
477  return NULL;
478 }
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
static struct IBF_Key get_ibf_key(const struct GNUNET_HashCode *src)
Derive the IBF key from a hash code and a salt.
static int op_get_element_iterator(void *cls, uint32_t key, void *value)
Iterator over the mapping from IBF keys to element entries.
@ GNUNET_SYSERR
Definition: gnunet_common.h:93
int GNUNET_CONTAINER_multihashmap32_get_multiple(struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, GNUNET_CONTAINER_MulitHashMapIterator32Callback it, void *it_cls)
Iterate over all entries in the map that match a particular key.

References ctx, get_ibf_key(), GNUNET_assert, GNUNET_CONTAINER_multihashmap32_get_multiple(), GNUNET_SYSERR, IBF_Key::key_val, op, op_get_element_iterator(), and ret.

Referenced by handle_union_p2p_elements(), and handle_union_p2p_full_element().

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

◆ op_register_element()

static void op_register_element ( struct Operation op,
struct ElementEntry ee,
int  received 
)
static

Insert an element into the union operation's key-to-element mapping.

Takes ownership of 'ee'. Note that this does not insert the element in the set, only in the operation's key-element mapping. This is done to speed up re-tried operations, if some elements were transmitted, and then the IBF fails to decode.

XXX: clarify ownership, doesn't sound right.

Parameters
opthe union operation
eethe element entry
receivedwas this element received from the remote peer?

Definition at line 496 of file gnunet-service-set_union.c.

499 {
500  struct IBF_Key ibf_key;
501  struct KeyEntry *k;
502 
504  k = GNUNET_new (struct KeyEntry);
505  k->element = ee;
506  k->ibf_key = ibf_key;
507  k->received = received;
509  GNUNET_CONTAINER_multihashmap32_put (op->state->key_to_element,
510  (uint32_t) ibf_key.key_val,
511  k,
513 }
int GNUNET_CONTAINER_multihashmap32_put(struct GNUNET_CONTAINER_MultiHashMap32 *map, uint32_t key, void *value, enum GNUNET_CONTAINER_MultiHashMapOption opt)
Store a key-value pair in the map.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE
Allow multiple values with the same key.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
uint64_t key_val
Definition: ibf.h:47
struct IBF_Key ibf_key
IBF key for the entry, derived from the current salt.
int received
Did we receive this element? Even if element->is_foreign is false, we might have received the element...

References KeyEntry::element, ElementEntry::element_hash, get_ibf_key(), GNUNET_assert, GNUNET_CONTAINER_multihashmap32_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE, GNUNET_new, GNUNET_OK, KeyEntry::ibf_key, IBF_Key::key_val, op, and KeyEntry::received.

Referenced by handle_union_p2p_elements(), handle_union_p2p_full_element(), and init_key_to_element_iterator().

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

◆ salt_key()

static void salt_key ( const struct IBF_Key k_in,
uint32_t  salt,
struct IBF_Key k_out 
)
static

FIXME.

Definition at line 520 of file gnunet-service-set_union.c.

523 {
524  int s = salt % 64;
525  uint64_t x = k_in->key_val;
526 
527  /* rotate ibf key */
528  x = (x >> s) | (x << (64 - s));
529  k_out->key_val = x;
530 }

References IBF_Key::key_val, and salt.

Referenced by prepare_ibf_iterator().

Here is the caller graph for this function:

◆ unsalt_key()

static void unsalt_key ( const struct IBF_Key k_in,
uint32_t  salt,
struct IBF_Key k_out 
)
static

FIXME.

Definition at line 537 of file gnunet-service-set_union.c.

540 {
541  int s = salt % 64;
542  uint64_t x = k_in->key_val;
543 
544  x = (x << s) | (x >> (64 - s));
545  k_out->key_val = x;
546 }

References IBF_Key::key_val, and salt.

Referenced by decode_and_send(), and handle_union_p2p_inquiry().

Here is the caller graph for this function:

◆ prepare_ibf_iterator()

static int prepare_ibf_iterator ( void *  cls,
uint32_t  key,
void *  value 
)
static

Insert a key into an ibf.

Parameters
clsthe ibf
keyunused
valuethe key entry to get the key from

Definition at line 557 of file gnunet-service-set_union.c.

560 {
561  struct Operation *op = cls;
562  struct KeyEntry *ke = value;
563  struct IBF_Key salted_key;
564 
566  "[OP %p] inserting %lx (hash %s) into ibf\n",
567  op,
568  (unsigned long) ke->ibf_key.key_val,
570  salt_key (&ke->ibf_key,
571  op->state->salt_send,
572  &salted_key);
573  ibf_insert (op->state->local_ibf, salted_key);
574  return GNUNET_YES;
575 }
static void salt_key(const struct IBF_Key *k_in, uint32_t salt, struct IBF_Key *k_out)
FIXME.
const char * GNUNET_h2s(const struct GNUNET_HashCode *hc)
Convert a hash value to a string (for printing debug messages).
void ibf_insert(struct InvertibleBloomFilter *ibf, struct IBF_Key key)
Insert a key into an IBF.
Definition: ibf.c:167
Operation context used to execute a set operation.

References KeyEntry::element, ElementEntry::element_hash, GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_YES, ibf_insert(), KeyEntry::ibf_key, IBF_Key::key_val, LOG, op, salt_key(), and value.

Referenced by prepare_ibf().

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

◆ init_key_to_element_iterator()

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

Iterator for initializing the key-to-element mapping of a union operation.

Parameters
clsthe union operation struct Operation *
keyunused
valuethe struct ElementEntry * to insert into the key-to-element mapping
Returns
GNUNET_YES (to continue iterating)

Definition at line 589 of file gnunet-service-set_union.c.

592 {
593  struct Operation *op = cls;
594  struct ElementEntry *ee = value;
595 
596  /* make sure that the element belongs to the set at the time
597  * of creating the operation */
598  if (GNUNET_NO ==
600  op))
601  return GNUNET_YES;
602  GNUNET_assert (GNUNET_NO == ee->remote);
604  ee,
605  GNUNET_NO);
606  return GNUNET_YES;
607 }
int _GSS_is_element_of_operation(struct ElementEntry *ee, struct Operation *op)
Is element ee part of the set used by op?
static void op_register_element(struct Operation *op, struct ElementEntry *ee, int received)
Insert an element into the union operation's key-to-element mapping.
Information about an element element in the set.

References _GSS_is_element_of_operation(), GNUNET_assert, GNUNET_NO, GNUNET_YES, op, op_register_element(), ElementEntry::remote, and value.

Referenced by initialize_key_to_element().

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

◆ initialize_key_to_element()

static void initialize_key_to_element ( struct Operation op)
static

Initialize the IBF key to element mapping local to this set operation.

Parameters
opthe set union operation

Definition at line 617 of file gnunet-service-set_union.c.

618 {
619  unsigned int len;
620 
621  GNUNET_assert (NULL == op->state->key_to_element);
622  len = GNUNET_CONTAINER_multihashmap_size (op->set->content->elements);
623  op->state->key_to_element = GNUNET_CONTAINER_multihashmap32_create (len + 1);
624  GNUNET_CONTAINER_multihashmap_iterate (op->set->content->elements,
626  op);
627 }
uint16_t len
length of data (which is always a uint32_t, but presumably this can be used to specify that fewer byt...
static int init_key_to_element_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
Iterator for initializing the key-to-element mapping of a union operation.
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_MultiHashMap32 * GNUNET_CONTAINER_multihashmap32_create(unsigned int len)
Create a 32-bit key multi hash map.

References GNUNET_assert, GNUNET_CONTAINER_multihashmap32_create(), GNUNET_CONTAINER_multihashmap_iterate(), GNUNET_CONTAINER_multihashmap_size(), init_key_to_element_iterator(), len, and op.

Referenced by union_accept(), and union_evaluate().

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

◆ prepare_ibf()

static int prepare_ibf ( struct Operation op,
uint32_t  size 
)
static

Create an ibf with the operation's elements of the specified size.

Parameters
opthe union operation
sizesize of the ibf to create
Returns
GNUNET_OK on success, GNUNET_SYSERR on failure

Definition at line 639 of file gnunet-service-set_union.c.

641 {
642  GNUNET_assert (NULL != op->state->key_to_element);
643 
644  if (NULL != op->state->local_ibf)
645  ibf_destroy (op->state->local_ibf);
646  op->state->local_ibf = ibf_create (size, SE_IBF_HASH_NUM);
647  if (NULL == op->state->local_ibf)
648  {
650  "Failed to allocate local IBF\n");
651  return GNUNET_SYSERR;
652  }
653  GNUNET_CONTAINER_multihashmap32_iterate (op->state->key_to_element,
655  op);
656  return GNUNET_OK;
657 }
#define SE_IBF_HASH_NUM
The hash num parameter for the difference digests and strata estimators.
static int prepare_ibf_iterator(void *cls, uint32_t key, void *value)
Insert a key into an ibf.
#define GNUNET_log(kind,...)
@ GNUNET_ERROR_TYPE_ERROR
static unsigned int size
Size of the "table".
Definition: peer.c:67
struct InvertibleBloomFilter * ibf_create(uint32_t size, uint8_t hash_num)
Create an invertible bloom filter.
Definition: ibf.c:79

References GNUNET_assert, GNUNET_CONTAINER_multihashmap32_iterate(), GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_OK, GNUNET_SYSERR, ibf_create(), ibf_destroy(), op, prepare_ibf_iterator(), SE_IBF_HASH_NUM, and size.

Referenced by decode_and_send(), and send_ibf().

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

◆ send_ibf()

static int send_ibf ( struct Operation op,
uint16_t  ibf_order 
)
static

Send an ibf of appropriate size.

Fragments the IBF into multiple messages if necessary.

Parameters
opthe union operation
ibf_orderorder of the ibf to send, size=2^order
Returns
GNUNET_OK on success, GNUNET_SYSERR on failure

Definition at line 670 of file gnunet-service-set_union.c.

672 {
673  unsigned int buckets_sent = 0;
674  struct InvertibleBloomFilter *ibf;
675 
676  if (GNUNET_OK !=
677  prepare_ibf (op, 1 << ibf_order))
678  {
679  /* allocation failed */
680  return GNUNET_SYSERR;
681  }
682 
684  "sending ibf of size %u\n",
685  1 << ibf_order);
686 
687  {
688  char name[64] = { 0 };
689  snprintf (name, sizeof(name), "# sent IBF (order %u)", ibf_order);
691  }
692 
693  ibf = op->state->local_ibf;
694 
695  while (buckets_sent < (1 << ibf_order))
696  {
697  unsigned int buckets_in_message;
698  struct GNUNET_MQ_Envelope *ev;
699  struct IBFMessage *msg;
700 
701  buckets_in_message = (1 << ibf_order) - buckets_sent;
702  /* limit to maximum */
703  if (buckets_in_message > MAX_BUCKETS_PER_MESSAGE)
704  buckets_in_message = MAX_BUCKETS_PER_MESSAGE;
705 
706  ev = GNUNET_MQ_msg_extra (msg,
707  buckets_in_message * IBF_BUCKET_SIZE,
709  msg->reserved1 = 0;
710  msg->reserved2 = 0;
711  msg->order = ibf_order;
712  msg->offset = htonl (buckets_sent);
713  msg->salt = htonl (op->state->salt_send);
714  ibf_write_slice (ibf, buckets_sent,
715  buckets_in_message, &msg[1]);
716  buckets_sent += buckets_in_message;
718  "ibf chunk size %u, %u/%u sent\n",
719  buckets_in_message,
720  buckets_sent,
721  1 << ibf_order);
722  GNUNET_MQ_send (op->mq, ev);
723  }
724 
725  /* The other peer must decode the IBF, so
726  * we're passive. */
727  op->state->phase = PHASE_INVENTORY_PASSIVE;
728  return GNUNET_OK;
729 }
struct GNUNET_STATISTICS_Handle * _GSS_statistics
Statistics handle.
#define MAX_BUCKETS_PER_MESSAGE
Number of buckets that can be transmitted in one message.
static int prepare_ibf(struct Operation *op, uint32_t size)
Create an ibf with the operation's elements of the specified size.
#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_UNION_P2P_IBF
Invertible bloom filter.
void GNUNET_STATISTICS_update(struct GNUNET_STATISTICS_Handle *handle, const char *name, int64_t delta, int make_persistent)
Set statistic value for the peer.
const char * name
void ibf_write_slice(const struct InvertibleBloomFilter *ibf, uint32_t start, uint32_t count, void *buf)
Write buckets from an ibf to a buffer.
Definition: ibf.c:290
#define IBF_BUCKET_SIZE
Size of one ibf bucket in bytes.
Definition: ibf.h:72
Message containing buckets of an invertible bloom filter.
Invertible bloom filter (IBF).
Definition: ibf.h:83

References _GSS_statistics, GNUNET_ERROR_TYPE_DEBUG, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_IBF, GNUNET_MQ_msg_extra, GNUNET_MQ_send(), GNUNET_NO, GNUNET_OK, GNUNET_STATISTICS_update(), GNUNET_SYSERR, IBF_BUCKET_SIZE, ibf_write_slice(), LOG, MAX_BUCKETS_PER_MESSAGE, msg, name, op, PHASE_INVENTORY_PASSIVE, and prepare_ibf().

Referenced by decode_and_send(), and handle_union_p2p_strata_estimator().

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

◆ get_order_from_difference()

static unsigned int get_order_from_difference ( unsigned int  diff)
static

Compute the necessary order of an ibf from the size of the symmetric set difference.

Parameters
diffthe difference
Returns
the required size of the ibf

Definition at line 740 of file gnunet-service-set_union.c.

741 {
742  unsigned int ibf_order;
743 
744  ibf_order = 2;
745  while (((1 << ibf_order) < (IBF_ALPHA * diff) ||
746  ((1 << ibf_order) < SE_IBF_HASH_NUM)) &&
747  (ibf_order < MAX_IBF_ORDER))
748  ibf_order++;
749  // add one for correction
750  return ibf_order + 1;
751 }
#define IBF_ALPHA
Number of buckets used in the ibf per estimated difference.
#define MAX_IBF_ORDER
The maximum size of an ibf we use is 2^(MAX_IBF_ORDER).

References IBF_ALPHA, MAX_IBF_ORDER, and SE_IBF_HASH_NUM.

Referenced by handle_union_p2p_strata_estimator().

Here is the caller graph for this function:

◆ send_full_element_iterator()

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

Send a set element.

Parameters
clsthe union operation struct Operation *
keyunused
valuethe struct ElementEntry * to insert into the key-to-element mapping
Returns
GNUNET_YES (to continue iterating)

Definition at line 764 of file gnunet-service-set_union.c.

767 {
768  struct Operation *op = cls;
769  struct GNUNET_SET_ElementMessage *emsg;
770  struct ElementEntry *ee = value;
771  struct GNUNET_SET_Element *el = &ee->element;
772  struct GNUNET_MQ_Envelope *ev;
773 
775  "Sending element %s\n",
776  GNUNET_h2s (key));
777  ev = GNUNET_MQ_msg_extra (emsg,
778  el->size,
780  emsg->element_type = htons (el->element_type);
781  GNUNET_memcpy (&emsg[1],
782  el->data,
783  el->size);
784  GNUNET_MQ_send (op->mq,
785  ev);
786  return GNUNET_YES;
787 }
static struct GNUNET_IDENTITY_EgoLookup * el
EgoLookup.
Definition: gnunet-abd.c:51
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_MESSAGE_TYPE_SET_UNION_P2P_FULL_ELEMENT
Send a set element, not as response to a demand but because we're sending the full set.
struct GNUNET_SET_Element element
The actual element.
Message sent by client to the service to add or remove an element to/from the set.
Definition: set.h:281
uint16_t element_type
Type of the element to add or remove.
Definition: set.h:291
Element stored in a set.

References el, ElementEntry::element, GNUNET_SET_ElementMessage::element_type, GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_memcpy, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_FULL_ELEMENT, GNUNET_MQ_msg_extra, GNUNET_MQ_send(), GNUNET_YES, key, LOG, op, and value.

Referenced by send_full_set().

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

◆ send_full_set()

static void send_full_set ( struct Operation op)
static

Switch to full set transmission for op.

Parameters
opoperation to switch to full set transmission.

Definition at line 796 of file gnunet-service-set_union.c.

797 {
798  struct GNUNET_MQ_Envelope *ev;
799 
800  op->state->phase = PHASE_FULL_SENDING;
802  "Dedicing to transmit the full set\n");
803  /* FIXME: use a more memory-friendly way of doing this with an
804  iterator, just as we do in the non-full case! */
805  (void) GNUNET_CONTAINER_multihashmap_iterate (op->set->content->elements,
807  op);
809  GNUNET_MQ_send (op->mq,
810  ev);
811 }
static int send_full_element_iterator(void *cls, const struct GNUNET_HashCode *key, void *value)
Send a set element.
#define GNUNET_MQ_msg_header(type)
Allocate a GNUNET_MQ_Envelope, where the message only consists of a header.
Definition: gnunet_mq_lib.h:76
#define GNUNET_MESSAGE_TYPE_SET_UNION_P2P_FULL_DONE
Request all missing elements from the other peer, based on their sets and the elements we previously ...

References GNUNET_CONTAINER_multihashmap_iterate(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_FULL_DONE, GNUNET_MQ_msg_header, GNUNET_MQ_send(), LOG, op, PHASE_FULL_SENDING, and send_full_element_iterator().

Referenced by handle_union_p2p_request_full(), and handle_union_p2p_strata_estimator().

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

◆ check_union_p2p_strata_estimator()

int check_union_p2p_strata_estimator ( void *  cls,
const struct StrataEstimatorMessage msg 
)

Handle a strata estimator from a remote peer.

Parameters
clsthe union operation
msgthe message

Definition at line 821 of file gnunet-service-set_union.c.

823 {
824  struct Operation *op = cls;
825  int is_compressed;
826  size_t len;
827 
828  if (op->state->phase != PHASE_EXPECT_SE)
829  {
830  GNUNET_break (0);
831  return GNUNET_SYSERR;
832  }
833  is_compressed = (GNUNET_MESSAGE_TYPE_SET_UNION_P2P_SEC == htons (
834  msg->header.type));
835  len = ntohs (msg->header.size) - sizeof(struct StrataEstimatorMessage);
836  if ((GNUNET_NO == is_compressed) &&
838  {
839  GNUNET_break (0);
840  return GNUNET_SYSERR;
841  }
842  return GNUNET_OK;
843 }
#define SE_IBF_SIZE
Size of the IBFs in the strata estimator.
#define SE_STRATA_COUNT
Number of IBFs in a strata estimator.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
#define GNUNET_MESSAGE_TYPE_SET_UNION_P2P_SEC
Compressed strata estimator.
uint16_t type
The type of the message (GNUNET_MESSAGE_TYPE_XXXX), in big-endian format.
uint16_t size
The length of the struct (in bytes, including the length field itself), in big-endian format.
Strata estimator together with the peer's overall set size.

References GNUNET_break, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_SEC, GNUNET_NO, GNUNET_OK, GNUNET_SYSERR, IBF_BUCKET_SIZE, len, msg, op, PHASE_EXPECT_SE, SE_IBF_SIZE, SE_STRATA_COUNT, GNUNET_MessageHeader::size, and GNUNET_MessageHeader::type.

◆ handle_union_p2p_strata_estimator()

void handle_union_p2p_strata_estimator ( void *  cls,
const struct StrataEstimatorMessage msg 
)

Handle a strata estimator from a remote peer.

Parameters
clsthe union operation
msgthe message

Definition at line 853 of file gnunet-service-set_union.c.

855 {
856  struct Operation *op = cls;
857  struct StrataEstimator *remote_se;
858  unsigned int diff;
859  uint64_t other_size;
860  size_t len;
861  int is_compressed;
862 
863  is_compressed = (GNUNET_MESSAGE_TYPE_SET_UNION_P2P_SEC == htons (
864  msg->header.type));
866  "# bytes of SE received",
867  ntohs (msg->header.size),
868  GNUNET_NO);
869  len = ntohs (msg->header.size) - sizeof(struct StrataEstimatorMessage);
870  other_size = GNUNET_ntohll (msg->set_size);
872  SE_IBF_SIZE,
874  if (NULL == remote_se)
875  {
876  /* insufficient resources, fail */
878  return;
879  }
880  if (GNUNET_OK !=
882  len,
883  is_compressed,
884  remote_se))
885  {
886  /* decompression failed */
887  strata_estimator_destroy (remote_se);
889  return;
890  }
891  GNUNET_assert (NULL != op->state->se);
892  diff = strata_estimator_difference (remote_se,
893  op->state->se);
894 
895  if (diff > 200)
896  diff = diff * 3 / 2;
897 
898  strata_estimator_destroy (remote_se);
899  strata_estimator_destroy (op->state->se);
900  op->state->se = NULL;
902  "got se diff=%d, using ibf size %d\n",
903  diff,
904  1U << get_order_from_difference (diff));
905 
906  {
907  char *set_debug;
908 
909  set_debug = getenv ("GNUNET_SET_BENCHMARK");
910  if ((NULL != set_debug) &&
911  (0 == strcmp (set_debug, "1")))
912  {
913  FILE *f = fopen ("set.log", "a");
914  fprintf (f, "%llu\n", (unsigned long long) diff);
915  fclose (f);
916  }
917  }
918 
919  if ((GNUNET_YES == op->byzantine) &&
920  (other_size < op->byzantine_lower_bound))
921  {
922  GNUNET_break (0);
924  return;
925  }
926 
927  if ((GNUNET_YES == op->force_full) ||
928  (diff > op->state->initial_size / 4) ||
929  (0 == other_size))
930  {
932  "Deciding to go for full set transmission (diff=%d, own set=%llu)\n",
933  diff,
934  (unsigned long long) op->state->initial_size);
936  "# of full sends",
937  1,
938  GNUNET_NO);
939  if ((op->state->initial_size <= other_size) ||
940  (0 == other_size))
941  {
942  send_full_set (op);
943  }
944  else
945  {
946  struct GNUNET_MQ_Envelope *ev;
947 
949  "Telling other peer that we expect its full set\n");
950  op->state->phase = PHASE_EXPECT_IBF;
951  ev = GNUNET_MQ_msg_header (
953  GNUNET_MQ_send (op->mq,
954  ev);
955  }
956  }
957  else
958  {
960  "# of ibf sends",
961  1,
962  GNUNET_NO);
963  if (GNUNET_OK !=
964  send_ibf (op,
966  {
967  /* Internal error, best we can do is shut the connection */
969  "Failed to send IBF, closing connection\n");
971  return;
972  }
973  }
974  GNUNET_CADET_receive_done (op->channel);
975 }
char * getenv()
static void send_full_set(struct Operation *op)
Switch to full set transmission for op.
static int send_ibf(struct Operation *op, uint16_t ibf_order)
Send an ibf of appropriate size.
static void fail_union_operation(struct Operation *op)
Inform the client that the union operation has failed, and proceed to destroy the evaluate operation.
static unsigned int get_order_from_difference(unsigned int diff)
Compute the necessary order of an ibf from the size of the symmetric set difference.
unsigned int strata_estimator_difference(const struct StrataEstimator *se1, const struct StrataEstimator *se2)
Estimate set difference with two strata estimators, i.e.
struct StrataEstimator * strata_estimator_create(unsigned int strata_count, uint32_t ibf_size, uint8_t ibf_hashnum)
Create a new strata estimator with the given parameters.
int strata_estimator_read(const void *buf, size_t buf_len, int is_compressed, struct StrataEstimator *se)
Read strata from the buffer into the given strata estimator.
uint64_t GNUNET_ntohll(uint64_t n)
Convert unsigned 64-bit integer to host byte order.
Definition: common_endian.c:53
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_MESSAGE_TYPE_SET_UNION_P2P_REQUEST_FULL
Demand the whole element from the other peer, given only the hash code.
A handle to a strata estimator.

References _GSS_statistics, removetrailingwhitespace::f, fail_union_operation(), get_order_from_difference(), getenv(), GNUNET_assert, GNUNET_break, GNUNET_CADET_receive_done(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_REQUEST_FULL, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_SEC, GNUNET_MQ_msg_header, GNUNET_MQ_send(), GNUNET_NO, GNUNET_ntohll(), GNUNET_OK, GNUNET_STATISTICS_update(), GNUNET_YES, len, LOG, msg, op, PHASE_EXPECT_IBF, SE_IBF_HASH_NUM, SE_IBF_SIZE, SE_STRATA_COUNT, send_full_set(), send_ibf(), GNUNET_MessageHeader::size, strata_estimator_create(), strata_estimator_destroy(), strata_estimator_difference(), strata_estimator_read(), and GNUNET_MessageHeader::type.

Here is the call graph for this function:

◆ send_offers_iterator()

static int send_offers_iterator ( void *  cls,
uint32_t  key,
void *  value 
)
static

Iterator to send elements to a remote peer.

Parameters
clsclosure with the element key and the union operation
keyignored
valuethe key entry

Definition at line 986 of file gnunet-service-set_union.c.

989 {
990  struct SendElementClosure *sec = cls;
991  struct Operation *op = sec->op;
992  struct KeyEntry *ke = value;
993  struct GNUNET_MQ_Envelope *ev;
994  struct GNUNET_MessageHeader *mh;
995 
996  /* Detect 32-bit key collision for the 64-bit IBF keys. */
997  if (ke->ibf_key.key_val != sec->ibf_key.key_val)
998  return GNUNET_YES;
999 
1001  sizeof(struct GNUNET_HashCode),
1003 
1004  GNUNET_assert (NULL != ev);
1005  *(struct GNUNET_HashCode *) &mh[1] = ke->element->element_hash;
1007  "[OP %p] sending element offer (%s) to peer\n",
1008  op,
1009  GNUNET_h2s (&ke->element->element_hash));
1010  GNUNET_MQ_send (op->mq, ev);
1011  return GNUNET_YES;
1012 }
static struct GNUNET_CADET_Handle * mh
Cadet handle.
Definition: gnunet-cadet.c:92
#define GNUNET_MQ_msg_header_extra(mh, esize, type)
Allocate a GNUNET_MQ_Envelope, where the message only consists of a header and extra space.
Definition: gnunet_mq_lib.h:88
#define GNUNET_MESSAGE_TYPE_SET_UNION_P2P_OFFER
Tell the other peer which hashes match a given IBF key.
A 512-bit hashcode.
Header for all communications.
Used as a closure for sending elements with a specific IBF key.
struct Operation * op
Operation for which the elements should be sent.
struct IBF_Key ibf_key
The IBF key whose matching elements should be sent.

References KeyEntry::element, ElementEntry::element_hash, GNUNET_assert, GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_MESSAGE_TYPE_SET_UNION_P2P_OFFER, GNUNET_MQ_msg_header_extra, GNUNET_MQ_send(), GNUNET_YES, KeyEntry::ibf_key, SendElementClosure::ibf_key, IBF_Key::key_val, LOG, mh, op, SendElementClosure::op, and value.

Referenced by send_offers_for_key().

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

◆ send_offers_for_key()

static void send_offers_for_key ( struct Operation op,
struct IBF_Key  ibf_key 
)
static

Send offers (in the form of GNUNET_Hash-es) to the remote peer for the given IBF key.

Parameters
opunion operation
ibf_keyIBF key of interest

Definition at line 1022 of file gnunet-service-set_union.c.

1024 {
1025  struct SendElementClosure send_cls;
1026 
1027  send_cls.ibf_key = ibf_key;
1028  send_cls.op = op;
1030  op->state->key_to_element,
1031  (uint32_t) ibf_key.
1032  key_val,
1034  &send_cls);
1035 }
static int send_offers_iterator(void *cls, uint32_t key, void *value)
Iterator to send elements to a remote peer.

References GNUNET_CONTAINER_multihashmap32_get_multiple(), SendElementClosure::ibf_key, op, SendElementClosure::op, and send_offers_iterator().

Referenced by decode_and_send(), and handle_union_p2p_inquiry().

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

◆ decode_and_send()

static int decode_and_send ( struct Operation op)
static

Decode which elements are missing on each side, and send the appropriate offers and inquiries.

Parameters
opunion operation
Returns
GNUNET_OK on success, GNUNET_SYSERR on failure

Definition at line 1046 of file gnunet-service-set_union.c.

1047 {
1048  struct IBF_Key key;
1049  struct IBF_Key last_key;
1050  int side;
1051  unsigned int num_decoded;
1052  struct InvertibleBloomFilter *diff_ibf;
1053 
1054  GNUNET_assert (PHASE_INVENTORY_ACTIVE == op->state->phase);
1055 
1056  if (GNUNET_OK !=
1057  prepare_ibf (op,
1058  op->state->remote_ibf->size))
1059  {
1060  GNUNET_break (0);
1061  /* allocation failed */
1062  return GNUNET_SYSERR;
1063  }
1064  diff_ibf = ibf_dup (op->state->local_ibf);
1065  ibf_subtract (diff_ibf,
1066  op->state->remote_ibf);
1067 
1068  ibf_destroy (op->state->remote_ibf);
1069  op->state->remote_ibf = NULL;
1070 
1072  "decoding IBF (size=%u)\n",
1073  diff_ibf->size);
1074 
1075  num_decoded = 0;
1076  key.key_val = 0; /* just to avoid compiler thinking we use undef'ed variable */
1077 
1078  while (1)
1079  {
1080  int res;
1081  int cycle_detected = GNUNET_NO;
1082 
1083  last_key = key;
1084 
1085  res = ibf_decode (diff_ibf, &side, &key);
1086  if (res == GNUNET_OK)
1087  {
1089  "decoded ibf key %lx\n",
1090  (unsigned long) key.key_val);
1091  num_decoded += 1;
1092  if ((num_decoded > diff_ibf->size) ||
1093  ((num_decoded > 1) &&
1094  (last_key.key_val == key.key_val)))
1095  {
1097  "detected cyclic ibf (decoded %u/%u)\n",
1098  num_decoded,
1099  diff_ibf->size);
1100  cycle_detected = GNUNET_YES;
1101  }
1102  }
1103  if ((GNUNET_SYSERR == res) ||
1104  (GNUNET_YES == cycle_detected))
1105  {
1106  int next_order;
1107  next_order = 0;
1108  while (1 << next_order < diff_ibf->size)
1109  next_order++;
1110  next_order++;
1111  if (next_order <= MAX_IBF_ORDER)
1112  {
1114  "decoding failed, sending larger ibf (size %u)\n",
1115  1 << next_order);
1117  "# of IBF retries",
1118  1,
1119  GNUNET_NO);
1120  op->state->salt_send++;
1121  if (GNUNET_OK !=
1122  send_ibf (op, next_order))
1123  {
1124  /* Internal error, best we can do is shut the connection */
1126  "Failed to send IBF, closing connection\n");
1128  ibf_destroy (diff_ibf);
1129  return GNUNET_SYSERR;
1130  }
1131  }
1132  else
1133  {
1135  "# of failed union operations (too large)",
1136  1,
1137  GNUNET_NO);
1138  // XXX: Send the whole set, element-by-element
1140  "set union failed: reached ibf limit\n");
1142  ibf_destroy (diff_ibf);
1143  return GNUNET_SYSERR;
1144  }
1145  break;
1146  }
1147  if (GNUNET_NO == res)
1148  {
1149  struct GNUNET_MQ_Envelope *ev;
1150 
1152  "transmitted all values, sending DONE\n");
1154  GNUNET_MQ_send (op->mq, ev);
1155  /* We now wait until we get a DONE message back
1156  * and then wait for our MQ to be flushed and all our
1157  * demands be delivered. */
1158  break;
1159  }
1160  if (1 == side)
1161  {
1162  struct IBF_Key unsalted_key;
1163 
1164  unsalt_key (&key,
1165  op->state->salt_receive,
1166  &unsalted_key);
1168  unsalted_key);
1169  }
1170  else if (-1 == side)
1171  {
1172  struct GNUNET_MQ_Envelope *ev;
1173  struct InquiryMessage *msg;
1174 
1175  /* It may be nice to merge multiple requests, but with CADET's corking it is not worth
1176  * the effort additional complexity. */
1177  ev = GNUNET_MQ_msg_extra (msg,
1178  sizeof(struct IBF_Key),
1180  msg->salt = htonl (op->state->salt_receive);
1181  GNUNET_memcpy (&msg[1],
1182  &key,
1183  sizeof(struct IBF_Key));
1185  "sending element inquiry for IBF key %lx\n",
1186  (unsigned long) key.key_val);
1187  GNUNET_MQ_send (op->mq, ev);
1188  }
1189  else
1190  {
1191  GNUNET_assert (0);
1192  }
1193  }
1194  ibf_destroy (diff_ibf);
1195  return GNUNET_OK;
1196 }
static int res
static void unsalt_key(const struct IBF_Key *k_in, uint32_t salt, struct IBF_Key *k_out)
FIXME.
static void send_offers_for_key(struct Operation *op, struct IBF_Key ibf_key)
Send offers (in the form of GNUNET_Hash-es) to the remote peer for the given IBF key.
#define GNUNET_MESSAGE_TYPE_SET_UNION_P2P_INQUIRY
Tell the other peer to send us a list of hashes that match an IBF key.
#define GNUNET_MESSAGE_TYPE_SET_UNION_P2P_DONE
Set operation is done.
void ibf_subtract(struct InvertibleBloomFilter *ibf1, const struct InvertibleBloomFilter *ibf2)
Subtract ibf2 from ibf1, storing the result in ibf1.
Definition: ibf.c:356
int ibf_decode(struct InvertibleBloomFilter *ibf, int *ret_side, struct IBF_Key *ret_id)
Decode and remove an element from the IBF, if possible.
Definition: ibf.c:228
struct InvertibleBloomFilter * ibf_dup(const struct InvertibleBloomFilter *ibf)
Create a copy of an IBF, the copy has to be destroyed properly.
Definition: ibf.c:379
estimate_best_mode_of_operation (uint64_t avg_element_size, uint64_t local_set_size,...
uint32_t size
How many cells does this IBF have?
Definition: ibf.h:87

References _GSS_statistics, fail_union_operation(), GNUNET_assert, GNUNET_break, GNUNET_ERROR_TYPE_DEBUG, GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_memcpy, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_DONE, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_INQUIRY, GNUNET_MQ_msg_extra, GNUNET_MQ_msg_header, GNUNET_MQ_send(), GNUNET_NO, GNUNET_OK, GNUNET_STATISTICS_update(), GNUNET_SYSERR, GNUNET_YES, ibf_decode(), ibf_destroy(), ibf_dup(), ibf_subtract(), key, IBF_Key::key_val, LOG, MAX_IBF_ORDER, msg, op, PHASE_INVENTORY_ACTIVE, prepare_ibf(), res, send_ibf(), send_offers_for_key(), InvertibleBloomFilter::size, size, and unsalt_key().

Referenced by handle_union_p2p_ibf().

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

◆ check_union_p2p_ibf()

int check_union_p2p_ibf ( void *  cls,
const struct IBFMessage msg 
)

Check an IBF message from a remote peer.

Reassemble the IBF from multiple pieces, and process the whole IBF once possible.

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

Definition at line 1210 of file gnunet-service-set_union.c.

1212 {
1213  struct Operation *op = cls;
1214  unsigned int buckets_in_message;
1215 
1216  if (GNUNET_SET_OPERATION_UNION != op->set->operation)
1217  {
1218  GNUNET_break_op (0);
1219  return GNUNET_SYSERR;
1220  }
1221  buckets_in_message = (ntohs (msg->header.size) - sizeof *msg)
1222  / IBF_BUCKET_SIZE;
1223  if (0 == buckets_in_message)
1224  {
1225  GNUNET_break_op (0);
1226  return GNUNET_SYSERR;
1227  }
1228  if ((ntohs (msg->header.size) - sizeof *msg) != buckets_in_message
1229  * IBF_BUCKET_SIZE)
1230  {
1231  GNUNET_break_op (0);
1232  return GNUNET_SYSERR;
1233  }
1234  if (op->state->phase == PHASE_EXPECT_IBF_CONT)
1235  {
1236  if (ntohl (msg->offset) != op->state->ibf_buckets_received)
1237  {
1238  GNUNET_break_op (0);
1239  return GNUNET_SYSERR;
1240  }
1241  if (1 << msg->order != op->state->remote_ibf->size)
1242  {
1243  GNUNET_break_op (0);
1244  return GNUNET_SYSERR;
1245  }
1246  if (ntohl (msg->salt) != op->state->salt_receive)
1247  {
1248  GNUNET_break_op (0);
1249  return GNUNET_SYSERR;
1250  }
1251  }
1252  else if ((op->state->phase != PHASE_INVENTORY_PASSIVE) &&
1253  (op->state->phase != PHASE_EXPECT_IBF))
1254  {
1255  GNUNET_break_op (0);
1256  return GNUNET_SYSERR;
1257  }
1258 
1259  return GNUNET_OK;
1260 }
#define GNUNET_break_op(cond)
Use this for assertion violations caused by other peers (i.e.
@ GNUNET_SET_OPERATION_UNION
Set union, return all elements that are in at least one of the sets.

References GNUNET_break_op, GNUNET_OK, GNUNET_SET_OPERATION_UNION, GNUNET_SYSERR, IBF_BUCKET_SIZE, msg, op, PHASE_EXPECT_IBF, PHASE_EXPECT_IBF_CONT, PHASE_INVENTORY_PASSIVE, and GNUNET_MessageHeader::size.

◆ handle_union_p2p_ibf()

void handle_union_p2p_ibf ( void *  cls,
const struct IBFMessage msg 
)

Handle an IBF message from a remote peer.

Reassemble the IBF from multiple pieces, and process the whole IBF once possible.

Parameters
clsthe union operation
msgthe header of the message

Definition at line 1273 of file gnunet-service-set_union.c.

1275 {
1276  struct Operation *op = cls;
1277  unsigned int buckets_in_message;
1278 
1279  buckets_in_message = (ntohs (msg->header.size) - sizeof *msg)
1280  / IBF_BUCKET_SIZE;
1281  if ((op->state->phase == PHASE_INVENTORY_PASSIVE) ||
1282  (op->state->phase == PHASE_EXPECT_IBF))
1283  {
1284  op->state->phase = PHASE_EXPECT_IBF_CONT;
1285  GNUNET_assert (NULL == op->state->remote_ibf);
1287  "Creating new ibf of size %u\n",
1288  1 << msg->order);
1289  op->state->remote_ibf = ibf_create (1 << msg->order, SE_IBF_HASH_NUM);
1290  op->state->salt_receive = ntohl (msg->salt);
1292  "Receiving new IBF with salt %u\n",
1293  op->state->salt_receive);
1294  if (NULL == op->state->remote_ibf)
1295  {
1297  "Failed to parse remote IBF, closing connection\n");
1299  return;
1300  }
1301  op->state->ibf_buckets_received = 0;
1302  if (0 != ntohl (msg->offset))
1303  {
1304  GNUNET_break_op (0);
1306  return;
1307  }
1308  }
1309  else
1310  {
1311  GNUNET_assert (op->state->phase == PHASE_EXPECT_IBF_CONT);
1313  "Received more of IBF\n");
1314  }
1315  GNUNET_assert (NULL != op->state->remote_ibf);
1316 
1317  ibf_read_slice (&msg[1],
1318  op->state->ibf_buckets_received,
1319  buckets_in_message,
1320  op->state->remote_ibf);
1321  op->state->ibf_buckets_received += buckets_in_message;
1322 
1323  if (op->state->ibf_buckets_received == op->state->remote_ibf->size)
1324  {
1326  "received full ibf\n");
1327  op->state->phase = PHASE_INVENTORY_ACTIVE;
1328  if (GNUNET_OK !=
1329  decode_and_send (op))
1330  {
1331  /* Internal error, best we can do is shut down */
1333  "Failed to decode IBF, closing connection\n");
1335  return;
1336  }
1337  }
1338  GNUNET_CADET_receive_done (op->channel);
1339 }
static int decode_and_send(struct Operation *op)
Decode which elements are missing on each side, and send the appropriate offers and inquiries.
void ibf_read_slice(const void *buf, uint32_t start, uint32_t count, struct InvertibleBloomFilter *ibf)
Read buckets from a buffer into an ibf.
Definition: ibf.c:323

References decode_and_send(), fail_union_operation(), GNUNET_assert, GNUNET_break_op, GNUNET_CADET_receive_done(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_ERROR_TYPE_ERROR, GNUNET_log, GNUNET_OK, IBF_BUCKET_SIZE, ibf_create(), ibf_read_slice(), LOG, msg, op, PHASE_EXPECT_IBF, PHASE_EXPECT_IBF_CONT, PHASE_INVENTORY_ACTIVE, PHASE_INVENTORY_PASSIVE, SE_IBF_HASH_NUM, and GNUNET_MessageHeader::size.

Here is the call graph for this function:

◆ send_client_element()

static void send_client_element ( struct Operation op,
struct GNUNET_SET_Element element,
int  status 
)
static

Send a result message to the client indicating that there is a new element.

Parameters
opunion operation
elementelement to send
statusstatus to send with the new element

Definition at line 1351 of file gnunet-service-set_union.c.

1354 {
1355  struct GNUNET_MQ_Envelope *ev;
1356  struct GNUNET_SET_ResultMessage *rm;
1357 
1359  "sending element (size %u) to client\n",
1360  element->size);
1361  GNUNET_assert (0 != op->client_request_id);
1363  if (NULL == ev)
1364  {
1365  GNUNET_MQ_discard (ev);
1366  GNUNET_break (0);
1367  return;
1368  }
1369  rm->result_status = htons (status);
1370  rm->request_id = htonl (op->client_request_id);
1371  rm->element_type = htons (element->element_type);
1373  op->state->key_to_element));
1374  GNUNET_memcpy (&rm[1],
1375  element->data,
1376  element->size);
1377  GNUNET_MQ_send (op->set->cs->mq,
1378  ev);
1379 }
uint16_t status
See PRISM_STATUS_*-constants.
uint64_t GNUNET_htonll(uint64_t n)
Convert unsigned 64-bit integer to network byte order.
Definition: common_endian.c:36
unsigned int GNUNET_CONTAINER_multihashmap32_size(const struct GNUNET_CONTAINER_MultiHashMap32 *map)
Get the number of key-value pairs in the map.
void GNUNET_MQ_discard(struct GNUNET_MQ_Envelope *mqm)
Discard the message queue message, free all allocated resources.
Definition: mq.c:323
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.
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
uint64_t current_size
Current set size.
Definition: set.h:254

References GNUNET_SET_ResultMessage::current_size, GNUNET_SET_Element::data, GNUNET_SET_Element::element_type, GNUNET_SET_ResultMessage::element_type, GNUNET_assert, GNUNET_break, GNUNET_CONTAINER_multihashmap32_size(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_htonll(), GNUNET_memcpy, GNUNET_MESSAGE_TYPE_SET_RESULT, GNUNET_MQ_discard(), GNUNET_MQ_msg_extra, GNUNET_MQ_send(), LOG, op, GNUNET_SET_ResultMessage::request_id, GNUNET_SET_ResultMessage::result_status, GNUNET_SET_Element::size, and status.

Referenced by handle_union_p2p_demand(), handle_union_p2p_elements(), and handle_union_p2p_full_element().

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

◆ send_client_done()

static void send_client_done ( void *  cls)
static

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

Parameters
clsoperation to destroy

Definition at line 1389 of file gnunet-service-set_union.c.

1390 {
1391  struct Operation *op = cls;
1392  struct GNUNET_MQ_Envelope *ev;
1393  struct GNUNET_SET_ResultMessage *rm;
1394 
1395  if (GNUNET_YES == op->state->client_done_sent)
1396  {
1397  return;
1398  }
1399 
1400  if (PHASE_DONE != op->state->phase)
1401  {
1403  "Union operation failed\n");
1405  "# Union operations failed",
1406  1,
1407  GNUNET_NO);
1410  rm->request_id = htonl (op->client_request_id);
1411  rm->element_type = htons (0);
1412  GNUNET_MQ_send (op->set->cs->mq,
1413  ev);
1414  return;
1415  }
1416 
1417  op->state->client_done_sent = GNUNET_YES;
1418 
1420  "# Union operations succeeded",
1421  1,
1422  GNUNET_NO);
1424  "Signalling client that union operation is done\n");
1425  ev = GNUNET_MQ_msg (rm,
1427  rm->request_id = htonl (op->client_request_id);
1428  rm->result_status = htons (GNUNET_SET_STATUS_DONE);
1429  rm->element_type = htons (0);
1431  op->state->key_to_element));
1432  GNUNET_MQ_send (op->set->cs->mq,
1433  ev);
1434 }
@ GNUNET_ERROR_TYPE_INFO
@ GNUNET_SET_STATUS_DONE
Success, all elements have been sent (and received).

References _GSS_statistics, GNUNET_SET_ResultMessage::current_size, GNUNET_SET_ResultMessage::element_type, GNUNET_CONTAINER_multihashmap32_size(), GNUNET_ERROR_TYPE_INFO, GNUNET_ERROR_TYPE_WARNING, GNUNET_htonll(), GNUNET_MESSAGE_TYPE_SET_RESULT, GNUNET_MQ_msg, GNUNET_MQ_send(), GNUNET_NO, GNUNET_SET_STATUS_DONE, GNUNET_SET_STATUS_FAILURE, GNUNET_STATISTICS_update(), GNUNET_YES, LOG, op, PHASE_DONE, GNUNET_SET_ResultMessage::request_id, and GNUNET_SET_ResultMessage::result_status.

Referenced by handle_union_p2p_full_done(), handle_union_p2p_over(), maybe_finish(), and union_channel_death().

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

◆ maybe_finish()

static void maybe_finish ( struct Operation op)
static

Tests if the operation is finished, and if so notify.

Parameters
opoperation to check

Definition at line 1443 of file gnunet-service-set_union.c.

1444 {
1445  unsigned int num_demanded;
1446 
1447  num_demanded = GNUNET_CONTAINER_multihashmap_size (
1448  op->state->demanded_hashes);
1449 
1450  if (PHASE_FINISH_WAITING == op->state->phase)
1451  {
1453  "In PHASE_FINISH_WAITING, pending %u demands\n",
1454  num_demanded);
1455  if (0 == num_demanded)
1456  {
1457  struct GNUNET_MQ_Envelope *ev;
1458 
1459  op->state->phase = PHASE_DONE;
1461  GNUNET_MQ_send (op->mq,
1462  ev);
1463  /* We now wait until the other peer sends P2P_OVER
1464  * after it got all elements from us. */
1465  }
1466  }
1467  if (PHASE_FINISH_CLOSING == op->state->phase)
1468  {
1470  "In PHASE_FINISH_CLOSING, pending %u demands\n",
1471  num_demanded);
1472  if (0 == num_demanded)
1473  {
1474  op->state->phase = PHASE_DONE;
1475  send_client_done (op);
1477  }
1478  }
1479 }
void _GSS_operation_destroy2(struct Operation *op)
This function probably should not exist and be replaced by inlining more specific logic in the variou...
static void send_client_done(void *cls)
Signal to the client that the operation has finished and destroy the operation.

References _GSS_operation_destroy2(), GNUNET_CONTAINER_multihashmap_size(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_DONE, GNUNET_MQ_msg_header, GNUNET_MQ_send(), LOG, op, PHASE_DONE, PHASE_FINISH_CLOSING, PHASE_FINISH_WAITING, and send_client_done().

Referenced by handle_union_p2p_done(), and handle_union_p2p_elements().

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

◆ check_union_p2p_elements()

int check_union_p2p_elements ( void *  cls,
const struct GNUNET_SET_ElementMessage emsg 
)

Check an element message from a remote peer.

Parameters
clsthe union operation
emsgthe message

Definition at line 1489 of file gnunet-service-set_union.c.

1491 {
1492  struct Operation *op = cls;
1493 
1494  if (GNUNET_SET_OPERATION_UNION != op->set->operation)
1495  {
1496  GNUNET_break_op (0);
1497  return GNUNET_SYSERR;
1498  }
1499  if (0 == GNUNET_CONTAINER_multihashmap_size (op->state->demanded_hashes))
1500  {
1501  GNUNET_break_op (0);
1502  return GNUNET_SYSERR;
1503  }
1504  return GNUNET_OK;
1505 }

References GNUNET_break_op, GNUNET_CONTAINER_multihashmap_size(), GNUNET_OK, GNUNET_SET_OPERATION_UNION, GNUNET_SYSERR, and op.

Here is the call graph for this function:

◆ handle_union_p2p_elements()

void handle_union_p2p_elements ( void *  cls,
const struct GNUNET_SET_ElementMessage emsg 
)

Handle an element message from a remote peer.

Sent by the other peer either because we decoded an IBF and placed a demand, or because the other peer switched to full set transmission.

Parameters
clsthe union operation
emsgthe message

Definition at line 1517 of file gnunet-service-set_union.c.

1519 {
1520  struct Operation *op = cls;
1521  struct ElementEntry *ee;
1522  struct KeyEntry *ke;
1523  uint16_t element_size;
1524 
1525  element_size = ntohs (emsg->header.size) - sizeof(struct
1527  ee = GNUNET_malloc (sizeof(struct ElementEntry) + element_size);
1528  GNUNET_memcpy (&ee[1],
1529  &emsg[1],
1530  element_size);
1531  ee->element.size = element_size;
1532  ee->element.data = &ee[1];
1533  ee->element.element_type = ntohs (emsg->element_type);
1534  ee->remote = GNUNET_YES;
1536  &ee->element_hash);
1537  if (GNUNET_NO ==
1538  GNUNET_CONTAINER_multihashmap_remove (op->state->demanded_hashes,
1539  &ee->element_hash,
1540  NULL))
1541  {
1542  /* We got something we didn't demand, since it's not in our map. */
1543  GNUNET_break_op (0);
1545  return;
1546  }
1547 
1549  "Got element (size %u, hash %s) from peer\n",
1550  (unsigned int) element_size,
1551  GNUNET_h2s (&ee->element_hash));
1552 
1554  "# received elements",
1555  1,
1556  GNUNET_NO);
1558  "# exchanged elements",
1559  1,
1560  GNUNET_NO);
1561 
1562  op->state->received_total++;
1563 
1564  ke = op_get_element (op, &ee->element_hash);
1565  if (NULL != ke)
1566  {
1567  /* Got repeated element. Should not happen since
1568  * we track demands. */
1570  "# repeated elements",
1571  1,
1572  GNUNET_NO);
1573  ke->received = GNUNET_YES;
1574  GNUNET_free (ee);
1575  }
1576  else
1577  {
1579  "Registering new element from remote peer\n");
1580  op->state->received_fresh++;
1582  /* only send results immediately if the client wants it */
1583  switch (op->result_mode)
1584  {
1587  break;
1588 
1591  break;
1592 
1593  default:
1594  /* Result mode not supported, should have been caught earlier. */
1595  GNUNET_break (0);
1596  break;
1597  }
1598  }
1599 
1600  if ((op->state->received_total > 8) &&
1601  (op->state->received_fresh < op->state->received_total / 3))
1602  {
1603  /* The other peer gave us lots of old elements, there's something wrong. */
1604  GNUNET_break_op (0);
1606  return;
1607  }
1608  GNUNET_CADET_receive_done (op->channel);
1609  maybe_finish (op);
1610 }
static struct KeyEntry * op_get_element(struct Operation *op, const struct GNUNET_HashCode *element_hash)
Determine whether the given element is already in the operation's element set.
static void maybe_finish(struct Operation *op)
Tests if the operation is finished, and if so notify.
static void send_client_element(struct Operation *op, struct GNUNET_SET_Element *element, int status)
Send a result message to the client indicating that there is a new element.
static unsigned int element_size
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.
#define GNUNET_malloc(size)
Wrapper around malloc.
void GNUNET_SET_element_hash(const struct GNUNET_SET_Element *element, struct GNUNET_HashCode *ret_hash)
Hash a set element.
Definition: set_api.c:1245
@ GNUNET_SET_STATUS_OK
Everything went ok, we are transmitting an element of the result (in set, or to be removed from set,...
@ GNUNET_SET_STATUS_ADD_LOCAL
Element should be added to the result set of the local peer, i.e.
@ GNUNET_SET_RESULT_SYMMETRIC
Client gets notified of the required changes for both the local and the remote set.
@ GNUNET_SET_RESULT_ADDED
Client gets only elements that have been added to the set.
struct GNUNET_MessageHeader header
Type: GNUNET_MESSAGE_TYPE_SET_ADD or GNUNET_MESSAGE_TYPE_SET_REMOVE.
Definition: set.h:286

References _GSS_statistics, GNUNET_SET_Element::data, ElementEntry::element, ElementEntry::element_hash, element_size, GNUNET_SET_Element::element_type, GNUNET_SET_ElementMessage::element_type, fail_union_operation(), GNUNET_break, GNUNET_break_op, GNUNET_CADET_receive_done(), GNUNET_CONTAINER_multihashmap_remove(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, GNUNET_h2s(), GNUNET_malloc, GNUNET_memcpy, GNUNET_NO, GNUNET_SET_element_hash(), GNUNET_SET_RESULT_ADDED, GNUNET_SET_RESULT_SYMMETRIC, GNUNET_SET_STATUS_ADD_LOCAL, GNUNET_SET_STATUS_OK, GNUNET_STATISTICS_update(), GNUNET_YES, GNUNET_SET_ElementMessage::header, LOG, maybe_finish(), op, op_get_element(), op_register_element(), KeyEntry::received, ElementEntry::remote, send_client_element(), GNUNET_MessageHeader::size, and GNUNET_SET_Element::size.

Here is the call graph for this function:

◆ check_union_p2p_full_element()

int check_union_p2p_full_element ( void *  cls,
const struct GNUNET_SET_ElementMessage emsg 
)

Check a full element message from a remote peer.

Parameters
clsthe union operation
emsgthe message

Definition at line 1620 of file gnunet-service-set_union.c.

1622 {
1623  struct Operation *op = cls;
1624 
1625  if (GNUNET_SET_OPERATION_UNION != op->set->operation)
1626  {
1627  GNUNET_break_op (0);
1628  return GNUNET_SYSERR;
1629  }
1630  // FIXME: check that we expect full elements here?
1631  return GNUNET_OK;
1632 }

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

◆ handle_union_p2p_full_element()

void handle_union_p2p_full_element ( void *  cls,
const struct GNUNET_SET_ElementMessage emsg 
)

Handle an element message from a remote peer.

Parameters
clsthe union operation
emsgthe message

Definition at line 1642 of file gnunet-service-set_union.c.

1644 {
1645  struct Operation *op = cls;
1646  struct ElementEntry *ee;
1647  struct KeyEntry *ke;
1648  uint16_t element_size;
1649 
1650  element_size = ntohs (emsg->header.size) - sizeof(struct
1652  ee = GNUNET_malloc (sizeof(struct ElementEntry) + element_size);
1653  GNUNET_memcpy (&ee[1], &emsg[1], element_size);
1654  ee->element.size = element_size;
1655  ee->element.data = &ee[1];
1656  ee->element.element_type = ntohs (emsg->element_type);
1657  ee->remote = GNUNET_YES;
1659 
1661  "Got element (full diff, size %u, hash %s) from peer\n",
1662  (unsigned int) element_size,
1663  GNUNET_h2s (&ee->element_hash));
1664 
1666  "# received elements",
1667  1,
1668  GNUNET_NO);
1670  "# exchanged elements",
1671  1,
1672  GNUNET_NO);
1673 
1674  op->state->received_total++;
1675 
1676  ke = op_get_element (op, &ee->element_hash);
1677  if (NULL != ke)
1678  {
1679  /* Got repeated element. Should not happen since
1680  * we track demands. */
1682  "# repeated elements",
1683  1,
1684  GNUNET_NO);
1685  ke->received = GNUNET_YES;
1686  GNUNET_free (ee);
1687  }
1688  else
1689  {
1691  "Registering new element from remote peer\n");
1692  op->state->received_fresh++;
1694  /* only send results immediately if the client wants it */
1695  switch (op->result_mode)
1696  {
1699  break;
1700 
1703  break;
1704 
1705  default:
1706  /* Result mode not supported, should have been caught earlier. */
1707  GNUNET_break (0);
1708  break;
1709  }
1710  }
1711 
1712  if ((GNUNET_YES == op->byzantine) &&
1713  (op->state->received_total > 384 + op->state->received_fresh * 4) &&
1714  (op->state->received_fresh < op->state->received_total / 6))
1715  {
1716  /* The other peer gave us lots of old elements, there's something wrong. */
1718  "Other peer sent only %llu/%llu fresh elements, failing operation\n",
1719  (unsigned long long) op->state->received_fresh,
1720  (unsigned long long) op->state->received_total);
1721  GNUNET_break_op (0);
1723  return;
1724  }
1725  GNUNET_CADET_receive_done (op->channel);
1726 }

References _GSS_statistics, GNUNET_SET_Element::data, ElementEntry::element, ElementEntry::element_hash, element_size, GNUNET_SET_Element::element_type, GNUNET_SET_ElementMessage::element_type, fail_union_operation(), GNUNET_break, GNUNET_break_op, GNUNET_CADET_receive_done(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_ERROR_TYPE_ERROR, GNUNET_free, GNUNET_h2s(), GNUNET_malloc, GNUNET_memcpy, GNUNET_NO, GNUNET_SET_element_hash(), GNUNET_SET_RESULT_ADDED, GNUNET_SET_RESULT_SYMMETRIC, GNUNET_SET_STATUS_ADD_LOCAL, GNUNET_SET_STATUS_OK, GNUNET_STATISTICS_update(), GNUNET_YES, GNUNET_SET_ElementMessage::header, LOG, op, op_get_element(), op_register_element(), KeyEntry::received, ElementEntry::remote, send_client_element(), GNUNET_MessageHeader::size, and GNUNET_SET_Element::size.

Here is the call graph for this function:

◆ check_union_p2p_inquiry()

int check_union_p2p_inquiry ( void *  cls,
const struct InquiryMessage msg 
)

Send offers (for GNUNET_Hash-es) in response to inquiries (for IBF_Key-s).

Parameters
clsthe union operation
msgthe message

Definition at line 1737 of file gnunet-service-set_union.c.

1739 {
1740  struct Operation *op = cls;
1741  unsigned int num_keys;
1742 
1743  if (GNUNET_SET_OPERATION_UNION != op->set->operation)
1744  {
1745  GNUNET_break_op (0);
1746  return GNUNET_SYSERR;
1747  }
1748  if (op->state->phase != PHASE_INVENTORY_PASSIVE)
1749  {
1750  GNUNET_break_op (0);
1751  return GNUNET_SYSERR;
1752  }
1753  num_keys = (ntohs (msg->header.size) - sizeof(struct InquiryMessage))
1754  / sizeof(struct IBF_Key);
1755  if ((ntohs (msg->header.size) - sizeof(struct InquiryMessage))
1756  != num_keys * sizeof(struct IBF_Key))
1757  {
1758  GNUNET_break_op (0);
1759  return GNUNET_SYSERR;
1760  }
1761  return GNUNET_OK;
1762 }

References GNUNET_break_op, GNUNET_OK, GNUNET_SET_OPERATION_UNION, GNUNET_SYSERR, msg, op, PHASE_INVENTORY_PASSIVE, and GNUNET_MessageHeader::size.

◆ handle_union_p2p_inquiry()

void handle_union_p2p_inquiry ( void *  cls,
const struct InquiryMessage msg 
)

Send offers (for GNUNET_Hash-es) in response to inquiries (for IBF_Key-s).

Parameters
clsthe union operation
msgthe message

Definition at line 1773 of file gnunet-service-set_union.c.

1775 {
1776  struct Operation *op = cls;
1777  const struct IBF_Key *ibf_key;
1778  unsigned int num_keys;
1779 
1781  "Received union inquiry\n");
1782  num_keys = (ntohs (msg->header.size) - sizeof(struct InquiryMessage))
1783  / sizeof(struct IBF_Key);
1784  ibf_key = (const struct IBF_Key *) &msg[1];
1785  while (0 != num_keys--)
1786  {
1787  struct IBF_Key unsalted_key;
1788 
1789  unsalt_key (ibf_key,
1790  ntohl (msg->salt),
1791  &unsalted_key);
1793  unsalted_key);
1794  ibf_key++;
1795  }
1796  GNUNET_CADET_receive_done (op->channel);
1797 }

References GNUNET_CADET_receive_done(), GNUNET_ERROR_TYPE_DEBUG, LOG, msg, op, send_offers_for_key(), GNUNET_MessageHeader::size, and unsalt_key().

Here is the call graph for this function:

◆ send_missing_full_elements_iter()

static int send_missing_full_elements_iter ( void *  cls,
uint32_t  key,
void *  value 
)
static

Iterator over hash map entries, called to destroy the linked list of colliding ibf key entries.

Parameters
clsclosure
keycurrent key code
valuevalue in the hash map
Returns
GNUNET_YES if we should continue to iterate, GNUNET_NO if not.

Definition at line 1811 of file gnunet-service-set_union.c.

1814 {
1815  struct Operation *op = cls;
1816  struct KeyEntry *ke = value;
1817  struct GNUNET_MQ_Envelope *ev;
1818  struct GNUNET_SET_ElementMessage *emsg;
1819  struct ElementEntry *ee = ke->element;
1820 
1821  if (GNUNET_YES == ke->received)
1822  return GNUNET_YES;
1823  ev = GNUNET_MQ_msg_extra (emsg,
1824  ee->element.size,
1826  GNUNET_memcpy (&emsg[1],
1827  ee->element.data,
1828  ee->element.size);
1829  emsg->element_type = htons (ee->element.element_type);
1830  GNUNET_MQ_send (op->mq,
1831  ev);
1832  return GNUNET_YES;
1833 }

References GNUNET_SET_Element::data, ElementEntry::element, KeyEntry::element, GNUNET_SET_Element::element_type, GNUNET_SET_ElementMessage::element_type, GNUNET_memcpy, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_FULL_ELEMENT, GNUNET_MQ_msg_extra, GNUNET_MQ_send(), GNUNET_YES, op, KeyEntry::received, GNUNET_SET_Element::size, and value.

Referenced by handle_union_p2p_full_done().

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

◆ handle_union_p2p_request_full()

void handle_union_p2p_request_full ( void *  cls,
const struct GNUNET_MessageHeader mh 
)

Handle a request for full set transmission.

Parameters
clsclosure, a set union operation
mhthe demand message

Definition at line 1843 of file gnunet-service-set_union.c.

1845 {
1846  struct Operation *op = cls;
1847 
1849  "Received request for full set transmission\n");
1850  if (GNUNET_SET_OPERATION_UNION != op->set->operation)
1851  {
1852  GNUNET_break_op (0);
1854  return;
1855  }
1856  if (PHASE_EXPECT_IBF != op->state->phase)
1857  {
1858  GNUNET_break_op (0);
1860  return;
1861  }
1862 
1863  // FIXME: we need to check that our set is larger than the
1864  // byzantine_lower_bound by some threshold
1865  send_full_set (op);
1866  GNUNET_CADET_receive_done (op->channel);
1867 }

References fail_union_operation(), GNUNET_break_op, GNUNET_CADET_receive_done(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_SET_OPERATION_UNION, LOG, op, PHASE_EXPECT_IBF, and send_full_set().

Here is the call graph for this function:

◆ handle_union_p2p_full_done()

void handle_union_p2p_full_done ( void *  cls,
const struct GNUNET_MessageHeader mh 
)

Handle a "full done" message.

Parameters
clsclosure, a set union operation
mhthe demand message

Definition at line 1877 of file gnunet-service-set_union.c.

1879 {
1880  struct Operation *op = cls;
1881 
1882  switch (op->state->phase)
1883  {
1884  case PHASE_EXPECT_IBF:
1885  {
1886  struct GNUNET_MQ_Envelope *ev;
1887 
1889  "got FULL DONE, sending elements that other peer is missing\n");
1890 
1891  /* send all the elements that did not come from the remote peer */
1892  GNUNET_CONTAINER_multihashmap32_iterate (op->state->key_to_element,
1894  op);
1895 
1897  GNUNET_MQ_send (op->mq,
1898  ev);
1899  op->state->phase = PHASE_DONE;
1900  /* we now wait until the other peer sends us the OVER message*/
1901  }
1902  break;
1903 
1904  case PHASE_FULL_SENDING:
1905  {
1907  "got FULL DONE, finishing\n");
1908  /* We sent the full set, and got the response for that. We're done. */
1909  op->state->phase = PHASE_DONE;
1910  GNUNET_CADET_receive_done (op->channel);
1911  send_client_done (op);
1913  return;
1914  }
1915  break;
1916 
1917  default:
1919  "Handle full done phase is %u\n",
1920  (unsigned) op->state->phase);
1921  GNUNET_break_op (0);
1923  return;
1924  }
1925  GNUNET_CADET_receive_done (op->channel);
1926 }
static int send_missing_full_elements_iter(void *cls, uint32_t key, void *value)
Iterator over hash map entries, called to destroy the linked list of colliding ibf key entries.

References _GSS_operation_destroy2(), fail_union_operation(), GNUNET_break_op, GNUNET_CADET_receive_done(), GNUNET_CONTAINER_multihashmap32_iterate(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_log, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_FULL_DONE, GNUNET_MQ_msg_header, GNUNET_MQ_send(), LOG, op, PHASE_DONE, PHASE_EXPECT_IBF, PHASE_FULL_SENDING, send_client_done(), and send_missing_full_elements_iter().

Here is the call graph for this function:

◆ check_union_p2p_demand()

int check_union_p2p_demand ( void *  cls,
const struct GNUNET_MessageHeader mh 
)

Check a demand by the other peer for elements based on a list of struct GNUNET_HashCodes.

Parameters
clsclosure, a set union operation
mhthe demand message
Returns
GNUNET_OK if mh is well-formed

Definition at line 1938 of file gnunet-service-set_union.c.

1940 {
1941  struct Operation *op = cls;
1942  unsigned int num_hashes;
1943 
1944  if (GNUNET_SET_OPERATION_UNION != op->set->operation)
1945  {
1946  GNUNET_break_op (0);
1947  return GNUNET_SYSERR;
1948  }
1949  num_hashes = (ntohs (mh->size) - sizeof(struct GNUNET_MessageHeader))
1950  / sizeof(struct GNUNET_HashCode);
1951  if ((ntohs (mh->size) - sizeof(struct GNUNET_MessageHeader))
1952  != num_hashes * sizeof(struct GNUNET_HashCode))
1953  {
1954  GNUNET_break_op (0);
1955  return GNUNET_SYSERR;
1956  }
1957  return GNUNET_OK;
1958 }

References GNUNET_break_op, GNUNET_OK, GNUNET_SET_OPERATION_UNION, GNUNET_SYSERR, mh, and op.

◆ handle_union_p2p_demand()

void handle_union_p2p_demand ( void *  cls,
const struct GNUNET_MessageHeader mh 
)

Handle a demand by the other peer for elements based on a list of struct GNUNET_HashCodes.

Parameters
clsclosure, a set union operation
mhthe demand message

Definition at line 1969 of file gnunet-service-set_union.c.

1971 {
1972  struct Operation *op = cls;
1973  struct ElementEntry *ee;
1974  struct GNUNET_SET_ElementMessage *emsg;
1975  const struct GNUNET_HashCode *hash;
1976  unsigned int num_hashes;
1977  struct GNUNET_MQ_Envelope *ev;
1978 
1979  num_hashes = (ntohs (mh->size) - sizeof(struct GNUNET_MessageHeader))
1980  / sizeof(struct GNUNET_HashCode);
1981  for (hash = (const struct GNUNET_HashCode *) &mh[1];
1982  num_hashes > 0;
1983  hash++, num_hashes--)
1984  {
1985  ee = GNUNET_CONTAINER_multihashmap_get (op->set->content->elements,
1986  hash);
1987  if (NULL == ee)
1988  {
1989  /* Demand for non-existing element. */
1990  GNUNET_break_op (0);
1992  return;
1993  }
1995  {
1996  /* Probably confused lazily copied sets. */
1997  GNUNET_break_op (0);
1999  return;
2000  }
2001  ev = GNUNET_MQ_msg_extra (emsg, ee->element.size,
2003  GNUNET_memcpy (&emsg[1], ee->element.data, ee->element.size);
2004  emsg->reserved = htons (0);
2005  emsg->element_type = htons (ee->element.element_type);
2007  "[OP %p] Sending demanded element (size %u, hash %s) to peer\n",
2008  op,
2009  (unsigned int) ee->element.size,
2010  GNUNET_h2s (&ee->element_hash));
2011  GNUNET_MQ_send (op->mq, ev);
2013  "# exchanged elements",
2014  1,
2015  GNUNET_NO);
2016 
2017  switch (op->result_mode)
2018  {
2020  /* Nothing to do. */
2021  break;
2022 
2025  break;
2026 
2027  default:
2028  /* Result mode not supported, should have been caught earlier. */
2029  GNUNET_break (0);
2030  break;
2031  }
2032  }
2033  GNUNET_CADET_receive_done (op->channel);
2034 }
void * GNUNET_CONTAINER_multihashmap_get(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Given a key find a value in the map matching the key.
#define GNUNET_MESSAGE_TYPE_SET_P2P_ELEMENTS
Actual set elements.
@ GNUNET_SET_STATUS_ADD_REMOTE
Element should be added to the result set of the remote peer, i.e.
uint16_t reserved
For alignment, always zero.
Definition: set.h:296

References _GSS_is_element_of_operation(), _GSS_statistics, GNUNET_SET_Element::data, ElementEntry::element, ElementEntry::element_hash, GNUNET_SET_Element::element_type, GNUNET_SET_ElementMessage::element_type, fail_union_operation(), GNUNET_break, GNUNET_break_op, GNUNET_CADET_receive_done(), GNUNET_CONTAINER_multihashmap_get(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_memcpy, GNUNET_MESSAGE_TYPE_SET_P2P_ELEMENTS, GNUNET_MQ_msg_extra, GNUNET_MQ_send(), GNUNET_NO, GNUNET_SET_RESULT_ADDED, GNUNET_SET_RESULT_SYMMETRIC, GNUNET_SET_STATUS_ADD_REMOTE, GNUNET_STATISTICS_update(), LOG, mh, op, GNUNET_SET_ElementMessage::reserved, send_client_element(), and GNUNET_SET_Element::size.

Here is the call graph for this function:

◆ check_union_p2p_offer()

int check_union_p2p_offer ( void *  cls,
const struct GNUNET_MessageHeader mh 
)

Check offer (of struct GNUNET_HashCodes).

Parameters
clsthe union operation
mhthe message
Returns
GNUNET_OK if mh is well-formed

Definition at line 2045 of file gnunet-service-set_union.c.

2047 {
2048  struct Operation *op = cls;
2049  unsigned int num_hashes;
2050 
2051  if (GNUNET_SET_OPERATION_UNION != op->set->operation)
2052  {
2053  GNUNET_break_op (0);
2054  return GNUNET_SYSERR;
2055  }
2056  /* look up elements and send them */
2057  if ((op->state->phase != PHASE_INVENTORY_PASSIVE) &&
2058  (op->state->phase != PHASE_INVENTORY_ACTIVE))
2059  {
2060  GNUNET_break_op (0);
2061  return GNUNET_SYSERR;
2062  }
2063  num_hashes = (ntohs (mh->size) - sizeof(struct GNUNET_MessageHeader))
2064  / sizeof(struct GNUNET_HashCode);
2065  if ((ntohs (mh->size) - sizeof(struct GNUNET_MessageHeader)) !=
2066  num_hashes * sizeof(struct GNUNET_HashCode))
2067  {
2068  GNUNET_break_op (0);
2069  return GNUNET_SYSERR;
2070  }
2071  return GNUNET_OK;
2072 }

References GNUNET_break_op, GNUNET_OK, GNUNET_SET_OPERATION_UNION, GNUNET_SYSERR, mh, op, PHASE_INVENTORY_ACTIVE, and PHASE_INVENTORY_PASSIVE.

◆ handle_union_p2p_offer()

void handle_union_p2p_offer ( void *  cls,
const struct GNUNET_MessageHeader mh 
)

Handle offers (of struct GNUNET_HashCodes) and respond with demands (of struct GNUNET_HashCodes).

Parameters
clsthe union operation
mhthe message

Definition at line 2083 of file gnunet-service-set_union.c.

2085 {
2086  struct Operation *op = cls;
2087  const struct GNUNET_HashCode *hash;
2088  unsigned int num_hashes;
2089 
2090  num_hashes = (ntohs (mh->size) - sizeof(struct GNUNET_MessageHeader))
2091  / sizeof(struct GNUNET_HashCode);
2092  for (hash = (const struct GNUNET_HashCode *) &mh[1];
2093  num_hashes > 0;
2094  hash++, num_hashes--)
2095  {
2096  struct ElementEntry *ee;
2097  struct GNUNET_MessageHeader *demands;
2098  struct GNUNET_MQ_Envelope *ev;
2099 
2100  ee = GNUNET_CONTAINER_multihashmap_get (op->set->content->elements,
2101  hash);
2102  if (NULL != ee)
2104  continue;
2105 
2106  if (GNUNET_YES ==
2107  GNUNET_CONTAINER_multihashmap_contains (op->state->demanded_hashes,
2108  hash))
2109  {
2111  "Skipped sending duplicate demand\n");
2112  continue;
2113  }
2114 
2117  op->state->demanded_hashes,
2118  hash,
2119  NULL,
2121 
2123  "[OP %p] Requesting element (hash %s)\n",
2124  op, GNUNET_h2s (hash));
2125  ev = GNUNET_MQ_msg_header_extra (demands,
2126  sizeof(struct GNUNET_HashCode),
2128  GNUNET_memcpy (&demands[1],
2129  hash,
2130  sizeof(struct GNUNET_HashCode));
2131  GNUNET_MQ_send (op->mq, ev);
2132  }
2133  GNUNET_CADET_receive_done (op->channel);
2134 }
int GNUNET_CONTAINER_multihashmap_contains(const struct GNUNET_CONTAINER_MultiHashMap *map, const struct GNUNET_HashCode *key)
Check if the map contains any value under the given key (including values that are NULL).
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.
@ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST
, ' bother checking if a value already exists (faster than GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE...
#define GNUNET_MESSAGE_TYPE_SET_UNION_P2P_DEMAND
Demand the whole element from the other peer, given only the hash code.

References _GSS_is_element_of_operation(), GNUNET_assert, GNUNET_CADET_receive_done(), GNUNET_CONTAINER_multihashmap_contains(), GNUNET_CONTAINER_multihashmap_get(), GNUNET_CONTAINER_multihashmap_put(), GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_FAST, GNUNET_ERROR_TYPE_DEBUG, GNUNET_h2s(), GNUNET_memcpy, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_DEMAND, GNUNET_MQ_msg_header_extra, GNUNET_MQ_send(), GNUNET_OK, GNUNET_YES, LOG, mh, and op.

Here is the call graph for this function:

◆ handle_union_p2p_done()

void handle_union_p2p_done ( void *  cls,
const struct GNUNET_MessageHeader mh 
)

Handle a done message from a remote peer.

Parameters
clsthe union operation
mhthe message

Definition at line 2144 of file gnunet-service-set_union.c.

2146 {
2147  struct Operation *op = cls;
2148 
2149  if (GNUNET_SET_OPERATION_UNION != op->set->operation)
2150  {
2151  GNUNET_break_op (0);
2153  return;
2154  }
2155  switch (op->state->phase)
2156  {
2158  /* We got all requests, but still have to send our elements in response. */
2159  op->state->phase = PHASE_FINISH_WAITING;
2160 
2162  "got DONE (as passive partner), waiting for our demands to be satisfied\n");
2163  /* The active peer is done sending offers
2164  * and inquiries. This means that all
2165  * our responses to that (demands and offers)
2166  * must be in flight (queued or in mesh).
2167  *
2168  * We should notify the active peer once
2169  * all our demands are satisfied, so that the active
2170  * peer can quit if we gave it everything.
2171  */GNUNET_CADET_receive_done (op->channel);
2172  maybe_finish (op);
2173  return;
2174 
2177  "got DONE (as active partner), waiting to finish\n");
2178  /* All demands of the other peer are satisfied,
2179  * and we processed all offers, thus we know
2180  * exactly what our demands must be.
2181  *
2182  * We'll close the channel
2183  * to the other peer once our demands are met.
2184  */op->state->phase = PHASE_FINISH_CLOSING;
2185  GNUNET_CADET_receive_done (op->channel);
2186  maybe_finish (op);
2187  return;
2188 
2189  default:
2190  GNUNET_break_op (0);
2192  return;
2193  }
2194 }

References fail_union_operation(), GNUNET_break_op, GNUNET_CADET_receive_done(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_SET_OPERATION_UNION, LOG, maybe_finish(), op, PHASE_FINISH_CLOSING, PHASE_FINISH_WAITING, PHASE_INVENTORY_ACTIVE, and PHASE_INVENTORY_PASSIVE.

Here is the call graph for this function:

◆ handle_union_p2p_over()

void handle_union_p2p_over ( void *  cls,
const struct GNUNET_MessageHeader mh 
)

Handle a over message from a remote peer.

Handle an over message from a remote peer.

Parameters
clsthe union operation
mhthe message

Definition at line 2204 of file gnunet-service-set_union.c.

2206 {
2207  send_client_done (cls);
2208 }

References send_client_done().

Here is the call graph for this function:

◆ union_evaluate()

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

Initiate operation to evaluate a set union with a remote peer.

Parameters
opoperation to perform (to be initialized)
opaque_contextmessage to be transmitted to the listener to convince it to accept, may be NULL

Definition at line 2219 of file gnunet-service-set_union.c.

2221 {
2222  struct OperationState *state;
2223  struct GNUNET_MQ_Envelope *ev;
2224  struct OperationRequestMessage *msg;
2225 
2228  opaque_context);
2229  if (NULL == ev)
2230  {
2231  /* the context message is too large */
2232  GNUNET_break (0);
2233  return NULL;
2234  }
2235  state = GNUNET_new (struct OperationState);
2236  state->demanded_hashes = GNUNET_CONTAINER_multihashmap_create (32,
2237  GNUNET_NO);
2238  /* copy the current generation's strata estimator for this operation */
2239  state->se = strata_estimator_dup (op->set->state->se);
2240  /* we started the operation, thus we have to send the operation request */
2241  state->phase = PHASE_EXPECT_SE;
2242  state->salt_receive = state->salt_send = 42; // FIXME?????
2244  "Initiating union operation evaluation\n");
2246  "# of total union operations",
2247  1,
2248  GNUNET_NO);
2250  "# of initiated union operations",
2251  1,
2252  GNUNET_NO);
2253  msg->operation = htonl (GNUNET_SET_OPERATION_UNION);
2254  GNUNET_MQ_send (op->mq,
2255  ev);
2256 
2257  if (NULL != opaque_context)
2259  "sent op request with context message\n");
2260  else
2262  "sent op request without context message\n");
2263 
2264  op->state = state;
2267  state->key_to_element);
2268  return state;
2269 }
enum State state
current state of profiling
static void initialize_key_to_element(struct Operation *op)
Initialize the IBF key to element mapping local to this set operation.
struct StrataEstimator * strata_estimator_dup(struct StrataEstimator *se)
Make a copy of a strata estimator.
struct GNUNET_CONTAINER_MultiHashMap * GNUNET_CONTAINER_multihashmap_create(unsigned int len, int do_not_copy_keys)
Create a multi hash map.
#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 _GSS_statistics, GNUNET_break, GNUNET_CONTAINER_multihashmap32_size(), GNUNET_CONTAINER_multihashmap_create(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST, GNUNET_MQ_msg_nested_mh, GNUNET_MQ_send(), GNUNET_new, GNUNET_NO, GNUNET_SET_OPERATION_UNION, GNUNET_STATISTICS_update(), initialize_key_to_element(), LOG, msg, op, PHASE_EXPECT_SE, state, and strata_estimator_dup().

Referenced by _GSS_union_vt().

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

◆ union_accept()

static struct OperationState* union_accept ( struct Operation op)
static

Accept an union operation request from a remote peer.

Only initializes the private operation state.

Parameters
opoperation that will be accepted as a union operation

Definition at line 2279 of file gnunet-service-set_union.c.

2280 {
2281  struct OperationState *state;
2282  const struct StrataEstimator *se;
2283  struct GNUNET_MQ_Envelope *ev;
2284  struct StrataEstimatorMessage *strata_msg;
2285  char *buf;
2286  size_t len;
2287  uint16_t type;
2288 
2290  "accepting set union operation\n");
2292  "# of accepted union operations",
2293  1,
2294  GNUNET_NO);
2296  "# of total union operations",
2297  1,
2298  GNUNET_NO);
2299 
2300  state = GNUNET_new (struct OperationState);
2301  state->se = strata_estimator_dup (op->set->state->se);
2302  state->demanded_hashes = GNUNET_CONTAINER_multihashmap_create (32,
2303  GNUNET_NO);
2304  state->salt_receive = state->salt_send = 42; // FIXME?????
2305  op->state = state;
2308  state->key_to_element);
2309 
2310  /* kick off the operation */
2311  se = state->se;
2314  buf);
2315  if (len < se->strata_count * IBF_BUCKET_SIZE * se->ibf_size)
2317  else
2319  ev = GNUNET_MQ_msg_extra (strata_msg,
2320  len,
2321  type);
2322  GNUNET_memcpy (&strata_msg[1],
2323  buf,
2324  len);
2325  GNUNET_free (buf);
2326  strata_msg->set_size
2328  op->set->content->elements));
2329  GNUNET_MQ_send (op->mq,
2330  ev);
2331  state->phase = PHASE_EXPECT_IBF;
2332  return state;
2333 }
size_t strata_estimator_write(const struct StrataEstimator *se, void *buf)
Write the given strata estimator to the buffer.
static char buf[2048]
#define GNUNET_MESSAGE_TYPE_SET_UNION_P2P_SE
Strata estimator.
uint64_t set_size
Size of the local set.
unsigned int ibf_size
Size of each IBF stratum (in bytes)
unsigned int strata_count
Size of the IBF array in strata.
enum GNUNET_TESTBED_UnderlayLinkModelType type
the type of this model

References _GSS_statistics, buf, GNUNET_CONTAINER_multihashmap32_size(), GNUNET_CONTAINER_multihashmap_create(), GNUNET_CONTAINER_multihashmap_size(), GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, GNUNET_htonll(), GNUNET_malloc, GNUNET_memcpy, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_SE, GNUNET_MESSAGE_TYPE_SET_UNION_P2P_SEC, GNUNET_MQ_msg_extra, GNUNET_MQ_send(), GNUNET_new, GNUNET_NO, GNUNET_STATISTICS_update(), IBF_BUCKET_SIZE, StrataEstimator::ibf_size, initialize_key_to_element(), len, LOG, op, PHASE_EXPECT_IBF, StrataEstimatorMessage::set_size, state, StrataEstimator::strata_count, strata_estimator_dup(), strata_estimator_write(), and type.

Referenced by _GSS_union_vt().

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

◆ union_set_create()

static struct SetState* union_set_create ( void  )
static

Create a new set supporting the union operation.

We maintain one strata estimator per set and then manipulate it over the lifetime of the set, as recreating a strata estimator would be expensive.

Returns
the newly created set, NULL on error

Definition at line 2345 of file gnunet-service-set_union.c.

2346 {
2347  struct SetState *set_state;
2348 
2350  "union set created\n");
2351  set_state = GNUNET_new (struct SetState);
2354  if (NULL == set_state->se)
2355  {
2357  "Failed to allocate strata estimator\n");
2358  GNUNET_free (set_state);
2359  return NULL;
2360  }
2361  return set_state;
2362 }
Extra state required for efficient set intersection.
struct StrataEstimator * se
The strata estimator is only generated once for each set.

References GNUNET_ERROR_TYPE_DEBUG, GNUNET_ERROR_TYPE_ERROR, GNUNET_free, GNUNET_log, GNUNET_new, LOG, SetState::se, SE_IBF_HASH_NUM, SE_IBF_SIZE, SE_STRATA_COUNT, and strata_estimator_create().

Referenced by _GSS_union_vt().

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

◆ union_add()

static void union_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 2372 of file gnunet-service-set_union.c.

2374 {
2375  strata_estimator_insert (set_state->se,
2376  get_ibf_key (&ee->element_hash));
2377 }
void strata_estimator_insert(struct StrataEstimator *se, struct IBF_Key key)
Add a key to the strata estimator.

References ElementEntry::element_hash, get_ibf_key(), SetState::se, and strata_estimator_insert().

Referenced by _GSS_union_vt().

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

◆ union_remove()

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

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

Only marks the element as removed, so that older set operations can still exchange it.

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

Definition at line 2388 of file gnunet-service-set_union.c.

2390 {
2391  strata_estimator_remove (set_state->se,
2392  get_ibf_key (&ee->element_hash));
2393 }
void strata_estimator_remove(struct StrataEstimator *se, struct IBF_Key key)
Remove a key from the strata estimator.

References ElementEntry::element_hash, get_ibf_key(), SetState::se, and strata_estimator_remove().

Referenced by _GSS_union_vt().

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

◆ union_set_destroy()

static void union_set_destroy ( struct SetState set_state)
static

Destroy a set that supports the union operation.

Parameters
set_statethe set to destroy

Definition at line 2402 of file gnunet-service-set_union.c.

2403 {
2404  if (NULL != set_state->se)
2405  {
2406  strata_estimator_destroy (set_state->se);
2407  set_state->se = NULL;
2408  }
2409  GNUNET_free (set_state);
2410 }

References GNUNET_free, SetState::se, and strata_estimator_destroy().

Referenced by _GSS_union_vt().

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

◆ union_copy_state()

static struct SetState* union_copy_state ( struct SetState state)
static

Copy union-specific set state.

Parameters
statesource state for copying the union state
Returns
a copy of the union-specific set state

Definition at line 2420 of file gnunet-service-set_union.c.

2421 {
2422  struct SetState *new_state;
2423 
2424  GNUNET_assert ((NULL != state) &&
2425  (NULL != state->se));
2426  new_state = GNUNET_new (struct SetState);
2427  new_state->se = strata_estimator_dup (state->se);
2428 
2429  return new_state;
2430 }

References GNUNET_assert, GNUNET_new, SetState::se, state, and strata_estimator_dup().

Referenced by _GSS_union_vt().

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

◆ union_channel_death()

static void union_channel_death ( struct Operation op)
static

Handle case where channel went down for an operation.

Parameters
opoperation that lost the channel

Definition at line 2439 of file gnunet-service-set_union.c.

2440 {
2441  send_client_done (op);
2443  GNUNET_YES);
2444 }

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

Referenced by _GSS_union_vt().

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

◆ _GSS_union_vt()

const struct SetVT* _GSS_union_vt ( void  )

Get the table with implementing functions for set union.

Returns
the operation specific VTable

Definition at line 2454 of file gnunet-service-set_union.c.

2455 {
2456  static const struct SetVT union_vt = {
2458  .add = &union_add,
2459  .remove = &union_remove,
2460  .destroy_set = &union_set_destroy,
2461  .evaluate = &union_evaluate,
2462  .accept = &union_accept,
2463  .cancel = &union_op_cancel,
2464  .copy_state = &union_copy_state,
2465  .channel_death = &union_channel_death
2466  };
2467 
2468  return &union_vt;
2469 }
static void union_set_destroy(struct SetState *set_state)
Destroy a set that supports the union operation.
static struct OperationState * union_evaluate(struct Operation *op, const struct GNUNET_MessageHeader *opaque_context)
Initiate operation to evaluate a set union with a remote peer.
static struct SetState * union_set_create(void)
Create a new set supporting the union operation.
static struct SetState * union_copy_state(struct SetState *state)
Copy union-specific set state.
static void union_remove(struct SetState *set_state, struct ElementEntry *ee)
Remove the element given in the element message from the set.
static struct OperationState * union_accept(struct Operation *op)
Accept an union operation request from a remote peer.
static void union_channel_death(struct Operation *op)
Handle case where channel went down for an operation.
static void union_add(struct SetState *set_state, struct ElementEntry *ee)
Add the element from the given element message to the set.
static void union_op_cancel(struct Operation *op)
Destroy the union operation.
Dispatch table for a specific set operation.
SetCreateImpl create
Callback for the set creation.

References SetVT::create, union_accept(), union_add(), union_channel_death(), union_copy_state(), union_evaluate(), union_op_cancel(), union_remove(), union_set_create(), and union_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: