#include <gcrypt.h>
#define BLOOMFILTER_SIZE GNUNET_CRYPTO_HASH_LENGTH
+
+#define CALCULATE_BF_SIZE(A, B, s, k) \
+ do { \
+ k = ceil(1 + log2((double) (2*B / (double) A)));\
+ s = ceil((double) (A * k / log(2))); \
+ } while (0)
+
/**
* Current phase we are in for a intersection operation.
*/
* until one notices the their element count is equal
*/
PHASE_BF_EXCHANGE,
+ /**
+ * Multipart continuation of BF_exchange
+ */
+ PHASE_BF_AWAIT_MULTIPART,
/**
* if both peers have an equal peercount, they enter this state for
* one more turn, to see if they actually have agreed on a correct set.
* BF of the set's element.
*/
struct GNUNET_CONTAINER_BloomFilter *local_bf;
-
+
/**
* for multipart msgs we have to store the bloomfilter-data until we fully sent it.
*/
char * local_bf_data;
-
+
/**
- * for multipart msgs we have to store the bloomfilter-data until we fully sent it.
+ * size of the bloomfilter
*/
uint32_t local_bf_data_size;
-
+
/**
* Current state of the operation.
*/
&ee->element_hash, ee,
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
- /* create our own bloomfilter with salt+1 */
- GNUNET_BLOCK_mingle_hash (&ee->element_hash,
- op->spec->salt + 1,
- &mutated_hash);
- GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf,
- &mutated_hash);
-
return GNUNET_YES;
}
GNUNET_CONTAINER_multihashmap_put (op->state->my_elements,
&ee->element_hash, ee,
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
- GNUNET_BLOCK_mingle_hash (&ee->element_hash,
- op->spec->salt,
- &mutated_hash);
- GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf,
- &mutated_hash);
return GNUNET_YES;
}
* #GNUNET_NO if not.
*/
static int
-iterator_bf_round (void *cls,
+iterator_bf_reduce (void *cls,
const struct GNUNET_HashCode *key,
void *value)
{
GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements,
&ee->element_hash,
ee));
- return GNUNET_YES;
}
- GNUNET_BLOCK_mingle_hash(&ee->element_hash,
- op->spec->salt+1,
- &mutated_hash);
+
+ return GNUNET_YES;
+}
+
+/**
+ * create a bloomfilter based on the elements given
+ *
+ * @param cls closure
+ * @param key current key code
+ * @param value value in the hash map
+ * @return #GNUNET_YES if we should continue to
+ * iterate,
+ * #GNUNET_NO if not.
+ */
+static int
+iterator_bf_create (void *cls,
+ const struct GNUNET_HashCode *key,
+ void *value)
+{
+ struct ElementEntry *ee = value;
+ struct Operation *op = cls;
+ struct GNUNET_HashCode mutated_hash;
+
+ GNUNET_BLOCK_mingle_hash(&ee->element_hash, op->spec->salt, &mutated_hash);
+
GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf,
&mutated_hash);
return GNUNET_YES;
}
-
/**
* Inform the client that the union operation has failed,
* and proceed to destroy the evaluate operation.
/**
* Send a request for the evaluate operation to a remote peer
*
- * @param eo operation with the other peer
+ * @param op operation with the other peer
*/
static void
send_operation_request (struct Operation *op)
send_bloomfilter_multipart (struct Operation *op, uint32_t offset)
{
struct GNUNET_MQ_Envelope *ev;
- struct BFMessage *msg;
- uint32_t chunk_size = (GNUNET_SERVER_MAX_MESSAGE_SIZE - sizeof(struct BFMessage));
+ struct BFPart *msg;
+ uint32_t chunk_size = (GNUNET_SERVER_MAX_MESSAGE_SIZE - sizeof(struct BFPart));
uint32_t todo_size = op->state->local_bf_data_size - offset;
-
+
if (todo_size < chunk_size)
- // we probably need many chunks, thus we assume a maximum packet size by default
chunk_size = todo_size;
-
- ev = GNUNET_MQ_msg_extra (msg, chunk_size, GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
-
- msg->reserved = 0;
- msg->bloomfilter_total_length = htonl (op->state->local_bf_data_size);
+
+ ev = GNUNET_MQ_msg_extra (msg, chunk_size, GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF_PART);
+
msg->bloomfilter_length = htonl (chunk_size);
msg->bloomfilter_offset = htonl (offset);
- memcpy(&msg[1], op->state->local_bf, chunk_size);
+ memcpy(&msg[1], &op->state->local_bf_data[offset], chunk_size);
GNUNET_MQ_send (op->mq, ev);
-
+
if (op->state->local_bf_data_size == offset + chunk_size)
{
// done
- GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
GNUNET_free(op->state->local_bf_data);
op->state->local_bf_data = NULL;
- op->state->local_bf = NULL;
return;
}
-
+
send_bloomfilter_multipart (op, offset + chunk_size);
}
* After the result done message has been sent to the client,
* destroy the evaluate operation.
*
- * @param eo intersection operation
+ * @param op intersection operation
*/
static void
send_bloomfilter (struct Operation *op)
struct GNUNET_MQ_Envelope *ev;
struct BFMessage *msg;
uint32_t bf_size;
+ uint32_t bf_elementbits;
+ uint32_t chunk_size;
+ struct GNUNET_CONTAINER_BloomFilter * local_bf;
GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending bf of size %u\n");
+
+ CALCULATE_BF_SIZE(op->state->my_element_count,
+ op->spec->remote_element_count,
+ bf_size,
+ bf_elementbits);
+
+ local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL,
+ bf_size,
+ bf_elementbits);
+
+ op->spec->salt++;
+ GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements,
+ &iterator_bf_create,
+ op);
// send our bloomfilter
- bf_size = GNUNET_CONTAINER_bloomfilter_get_size (op->state->local_bf);
- if ( GNUNET_SERVER_MAX_MESSAGE_SIZE <= bf_size + sizeof(struct BFMessage))
- {
+ if (GNUNET_SERVER_MAX_MESSAGE_SIZE > bf_size + sizeof (struct BFMessage)) {
// singlepart
- ev = GNUNET_MQ_msg_extra (msg, bf_size, GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
-
- GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf);
- op->state->local_bf = NULL;
-
- msg->reserved = 0;
- msg->sender_element_count = htonl (op->state->my_element_count);
- msg->bloomfilter_length = htonl (bf_size);
- msg->bloomfilter_offset = htonl (0);
- msg->sender_mutator = htonl (op->spec->salt);
-
- GNUNET_MQ_send (op->mq, ev);
+ chunk_size = bf_size;
+ ev = GNUNET_MQ_msg_extra (msg, chunk_size, GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
+ GNUNET_assert (GNUNET_SYSERR !=
+ GNUNET_CONTAINER_bloomfilter_get_raw_data (local_bf,
+ &msg[1],
+ bf_size));
}
else {
//multipart
- op->state->local_bf_data = (char *)GNUNET_malloc(bf_size);
+ chunk_size = GNUNET_SERVER_MAX_MESSAGE_SIZE - 1 - sizeof (struct BFMessage);
+ ev = GNUNET_MQ_msg_extra (msg, chunk_size, GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF);
+ op->state->local_bf_data = (char *) GNUNET_malloc (bf_size);
GNUNET_assert (GNUNET_SYSERR !=
- GNUNET_CONTAINER_bloomfilter_get_raw_data (op->state->local_bf,
- op->state->local_bf_data,
- bf_size));
+ GNUNET_CONTAINER_bloomfilter_get_raw_data (local_bf,
+ op->state->local_bf_data,
+ bf_size));
+ memcpy (&msg[1], op->state->local_bf_data, chunk_size);
op->state->local_bf_data_size = bf_size;
- send_bloomfilter_multipart (op, 0);
}
+ GNUNET_CONTAINER_bloomfilter_free (local_bf);
+
+ msg->sender_element_count = htonl (op->state->my_element_count);
+ msg->bloomfilter_total_length = htonl (bf_size);
+ msg->bloomfilter_length = htonl (chunk_size);
+ msg->bits_per_element = htonl (bf_elementbits);
+ msg->sender_mutator = htonl (op->spec->salt);
+
+ GNUNET_MQ_send (op->mq, ev);
+
+ if (op->state->local_bf_data)
+ send_bloomfilter_multipart (op, chunk_size);
}
/**
* Inform the peer that this operation is complete.
*
- * @param eo the intersection operation to fail
+ * @param op the intersection operation to fail
*/
static void
send_peer_done (struct Operation *op)
GNUNET_MQ_send (op->mq, ev);
}
+/**
+ * Handle an BF multipart message from a remote peer.
+ *
+ * @param cls the intersection operation
+ * @param mh the header of the message
+ */
+static void
+handle_p2p_bf_part (void *cls, const struct GNUNET_MessageHeader *mh)
+{
+ struct Operation *op = cls;
+ const struct BFPart *msg = (const struct BFPart *) mh;
+
+ if (op->state->phase != PHASE_BF_AWAIT_MULTIPART){
+ GNUNET_break_op (0);
+ fail_intersection_operation(op);
+ return;
+ }
+
+
+}
/**
* Handle an BF message from a remote peer.
op->spec->salt = ntohl (msg->sender_mutator);
op->state->remote_bf = GNUNET_CONTAINER_bloomfilter_init ((const char*) &msg[1],
- BLOOMFILTER_SIZE,
- ntohl (msg->bloomfilter_length));
+ ntohl (msg->bloomfilter_total_length),
+ ntohl (msg->bits_per_element));
op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL,
BLOOMFILTER_SIZE,
GNUNET_CONSTANTS_BLOOMFILTER_K);
case PHASE_MAYBE_FINISHED:
// if we are bob or alice and are continuing operation
GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements,
- &iterator_bf_round,
+ &iterator_bf_reduce,
op);
break;
default:
op->state->phase = PHASE_BF_EXCHANGE;
op->state->my_elements = GNUNET_CONTAINER_multihashmap_create (1, GNUNET_YES);
-
- op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL,
- BLOOMFILTER_SIZE,
- GNUNET_CONSTANTS_BLOOMFILTER_K);
+
GNUNET_CONTAINER_multihashmap_iterate (op->spec->set->elements,
&iterator_initialization,
op);
/**
* Send our element to the peer, in case our element count is lower than his
*
- * @param eo intersection operation
+ * @param op intersection operation
*/
static void
send_element_count (struct Operation *op)
// just send our element count, as the other peer must start
ev = GNUNET_MQ_msg (msg, GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO);
- msg->reserved = 0;
msg->sender_element_count = htonl (op->state->my_element_count);
msg->bloomfilter_length = htonl (0);
msg->sender_mutator = htonl (0);
/**
* Dispatch messages for a intersection operation.
*
- * @param eo the state of the intersection evaluate operation
+ * @param op the state of the intersection evaluate operation
* @param mh the received message
* @return #GNUNET_SYSERR if the tunnel should be disconnected,
* #GNUNET_OK otherwise
case GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF:
handle_p2p_bf (op, mh);
break;
+ case GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF_PART:
+ handle_p2p_bf_part (op, mh);
+ break;
case GNUNET_MESSAGE_TYPE_SET_P2P_DONE:
handle_p2p_done (op, mh);
break;