X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fset%2Fgnunet-service-set_intersection.c;h=9dc4217921d65fe54fce53744c91f68f19027491;hb=3611a5295f95fad5d9e1fdb3866e7db9ecf8f47e;hp=9c21f3b566b62d25313964a03c34b92fa7ddb571;hpb=656aba44ab3cc71e88d76edcc8955835c4e6f037;p=oweals%2Fgnunet.git diff --git a/src/set/gnunet-service-set_intersection.c b/src/set/gnunet-service-set_intersection.c index 9c21f3b56..9dc421792 100644 --- a/src/set/gnunet-service-set_intersection.c +++ b/src/set/gnunet-service-set_intersection.c @@ -1,6 +1,6 @@ /* This file is part of GNUnet - (C) 2013 Christian Grothoff (and other contributing authors) + Copyright (C) 2013-2017 GNUnet e.V. GNUnet is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published @@ -14,185 +14,383 @@ You should have received a copy of the GNU General Public License along with GNUnet; see the file COPYING. If not, write to the - Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. + Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. */ - /** * @file set/gnunet-service-set_intersection.c * @brief two-peer set intersection * @author Christian Fuchs + * @author Christian Grothoff */ #include "platform.h" #include "gnunet_util_lib.h" #include "gnunet-service-set.h" -#include "strata_estimator.h" -#include "set_protocol.h" +#include "gnunet_block_lib.h" +#include "gnunet-service-set_protocol.h" +#include "gnunet-service-set_intersection.h" #include + /** * Current phase we are in for a intersection operation. */ enum IntersectionOperationPhase { /** - * We get our tunnel but received no message as of now + * We are just starting. */ - PHASE_EXPECT_INITIAL, + PHASE_INITIAL, + /** - * We expect a BF + the number of the other peers elements + * We have send the number of our elements to the other + * peer, but did not setup our element set yet. + */ + PHASE_COUNT_SENT, + + /** + * We have initialized our set and are now reducing it by exchanging + * Bloom filters until one party notices the their element hashes + * are equal. */ PHASE_BF_EXCHANGE, + /** - * The protocol is over. - * Results may still have to be sent to the client. + * We must next send the P2P DONE message (after finishing mostly + * with the local client). Then we will wait for the channel to close. + */ + PHASE_MUST_SEND_DONE, + + /** + * We have received the P2P DONE message, and must finish with the + * local client before terminating the channel. + */ + PHASE_DONE_RECEIVED, + + /** + * The protocol is over. Results may still have to be sent to the + * client. */ PHASE_FINISHED + }; /** - * State of an evaluate operation - * with another peer. + * State of an evaluate operation with another peer. */ struct OperationState { /** - * Tunnel to the remote peer. + * The bf we currently receive */ - struct GNUNET_MESH_Tunnel *tunnel; + struct GNUNET_CONTAINER_BloomFilter *remote_bf; /** - * Detail information about the set operation, - * including the set to use. + * BF of the set's element. */ - struct OperationSpecification *spec; + struct GNUNET_CONTAINER_BloomFilter *local_bf; /** - * Message queue for the peer. + * Remaining elements in the intersection operation. + * Maps element-id-hashes to 'elements in our set'. */ - struct GNUNET_MQ_Handle *mq; + struct GNUNET_CONTAINER_MultiHashMap *my_elements; /** - * The bf we currently receive + * Iterator for sending the final set of @e my_elements to the client. */ - struct GNUNET_CONTAINER_BloomFilter *remote_bf; + struct GNUNET_CONTAINER_MultiHashMapIterator *full_result_iter; /** - * BF of the set's element. + * Evaluate operations are held in a linked list. */ - struct GNUNET_CONTAINER_BloomFilter *local_bf; + struct OperationState *next; /** - * Current state of the operation. + * Evaluate operations are held in a linked list. */ - enum IntersectionOperationPhase phase; + struct OperationState *prev; /** - * Generation in which the operation handle - * was created. + * For multipart BF transmissions, we have to store the + * bloomfilter-data until we fully received it. */ - unsigned int generation_created; + char *bf_data; /** - * Set state of the set that this operation - * belongs to. + * XOR of the keys of all of the elements (remaining) in my set. + * Always updated when elements are added or removed to + * @e my_elements. */ - struct Set *set; - + struct GNUNET_HashCode my_xor; + /** - * Maps element-id-hashes to 'elements in our set'. + * XOR of the keys of all of the elements (remaining) in + * the other peer's set. Updated when we receive the + * other peer's Bloom filter. */ - struct GNUNET_CONTAINER_MultiHashMap *contained_elements; - + struct GNUNET_HashCode other_xor; + /** - * Current element count contained within contained_elements + * How many bytes of @e bf_data are valid? */ - uint64_t contained_elements_count; + uint32_t bf_data_offset; /** - * Iterator for sending elements on the key to element mapping to the client. + * Current element count contained within @e my_elements. + * (May differ briefly during initialization.) */ - struct GNUNET_CONTAINER_MultiHashMap32Iterator *full_result_iter; - + uint32_t my_element_count; + /** - * Evaluate operations are held in - * a linked list. + * size of the bloomfilter in @e bf_data. */ - struct OperationState *next; + uint32_t bf_data_size; - /** - * Evaluate operations are held in - * a linked list. - */ - struct OperationState *prev; + /** + * size of the bloomfilter + */ + uint32_t bf_bits_per_element; + + /** + * Salt currently used for BF construction (by us or the other peer, + * depending on where we are in the code). + */ + uint32_t salt; + + /** + * Current state of the operation. + */ + enum IntersectionOperationPhase phase; + + /** + * Generation in which the operation handle + * was created. + */ + unsigned int generation_created; /** * Did we send the client that we are done? */ int client_done_sent; + + /** + * Set whenever we reach the state where the death of the + * channel is perfectly find and should NOT result in the + * operation being cancelled. + */ + int channel_death_expected; }; /** * Extra state required for efficient set intersection. + * Merely tracks the total number of elements. */ struct SetState { /** - * Evaluate operations are held in - * a linked list. + * Number of currently valid elements in the set which have not been + * removed. */ - struct OperationState *ops_head; - - /** - * Evaluate operations are held in - * a linked list. - */ - struct OperationState *ops_tail; + uint32_t current_set_element_count; }; /** - * Destroy a intersection operation, and free all resources - * associated with it. + * If applicable in the current operation mode, send a result message + * to the client indicating we removed an element. * - * @param eo the intersection operation to destroy + * @param op intersection operation + * @param element element to send */ static void -intersection_operation_destroy (struct OperationState *eo) +send_client_removed_element (struct Operation *op, + struct GNUNET_SET_Element *element) +{ + struct GNUNET_MQ_Envelope *ev; + struct GNUNET_SET_ResultMessage *rm; + + if (GNUNET_SET_RESULT_REMOVED != op->result_mode) + return; /* Wrong mode for transmitting removed elements */ + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending removed element (size %u) to client\n", + element->size); + GNUNET_assert (0 != op->client_request_id); + ev = GNUNET_MQ_msg_extra (rm, + element->size, + GNUNET_MESSAGE_TYPE_SET_RESULT); + if (NULL == ev) + { + GNUNET_break (0); + return; + } + rm->result_status = htons (GNUNET_SET_STATUS_OK); + rm->request_id = htonl (op->client_request_id); + rm->element_type = element->element_type; + GNUNET_memcpy (&rm[1], + element->data, + element->size); + GNUNET_MQ_send (op->set->cs->mq, + ev); +} + + +/** + * Fills the "my_elements" hashmap with all relevant elements. + * + * @param cls the `struct Operation *` we are performing + * @param key current key code + * @param value the `struct ElementEntry *` from the hash map + * @return #GNUNET_YES (we should continue to iterate) + */ +static int +filtered_map_initialization (void *cls, + const struct GNUNET_HashCode *key, + void *value) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "destroying intersection op\n"); - GNUNET_CONTAINER_DLL_remove (eo->set->state->ops_head, - eo->set->state->ops_tail, - eo); - if (NULL != eo->mq) + struct Operation *op = cls; + struct ElementEntry *ee = value; + struct GNUNET_HashCode mutated_hash; + + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "FIMA called for %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + + if (GNUNET_NO == _GSS_is_element_of_operation (ee, op)) { - GNUNET_MQ_destroy (eo->mq); - eo->mq = NULL; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Reduced initialization, not starting with %s:%u (wrong generation)\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + return GNUNET_YES; /* element not valid in our operation's generation */ } - if (NULL != eo->tunnel) + + /* Test if element is in other peer's bloomfilter */ + GNUNET_BLOCK_mingle_hash (&ee->element_hash, + op->state->salt, + &mutated_hash); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Testing mingled hash %s with salt %u\n", + GNUNET_h2s (&mutated_hash), + op->state->salt); + if (GNUNET_NO == + GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf, + &mutated_hash)) { - struct GNUNET_MESH_Tunnel *t = eo->tunnel; - eo->tunnel = NULL; - GNUNET_MESH_tunnel_destroy (t); + /* remove this element */ + send_client_removed_element (op, + &ee->element); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Reduced initialization, not starting with %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + return GNUNET_YES; } - // TODO: destroy set elements? - if (NULL != eo->spec) + op->state->my_element_count++; + GNUNET_CRYPTO_hash_xor (&op->state->my_xor, + &ee->element_hash, + &op->state->my_xor); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Filtered initialization of my_elements, adding %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + GNUNET_break (GNUNET_YES == + GNUNET_CONTAINER_multihashmap_put (op->state->my_elements, + &ee->element_hash, + ee, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); + + return GNUNET_YES; +} + + +/** + * Removes elements from our hashmap if they are not contained within the + * provided remote bloomfilter. + * + * @param cls closure with the `struct Operation *` + * @param key current key code + * @param value value in the hash map + * @return #GNUNET_YES (we should continue to iterate) + */ +static int +iterator_bf_reduce (void *cls, + const struct GNUNET_HashCode *key, + void *value) +{ + struct Operation *op = cls; + struct ElementEntry *ee = value; + struct GNUNET_HashCode mutated_hash; + + GNUNET_BLOCK_mingle_hash (&ee->element_hash, + op->state->salt, + &mutated_hash); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Testing mingled hash %s with salt %u\n", + GNUNET_h2s (&mutated_hash), + op->state->salt); + if (GNUNET_NO == + GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf, + &mutated_hash)) { - if (NULL != eo->spec->context_msg) - { - GNUNET_free (eo->spec->context_msg); - eo->spec->context_msg = NULL; - } - GNUNET_free (eo->spec); - eo->spec = NULL; + GNUNET_break (0 < op->state->my_element_count); + op->state->my_element_count--; + GNUNET_CRYPTO_hash_xor (&op->state->my_xor, + &ee->element_hash, + &op->state->my_xor); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Bloom filter reduction of my_elements, removing %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + GNUNET_assert (GNUNET_YES == + GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements, + &ee->element_hash, + ee)); + send_client_removed_element (op, + &ee->element); + } + else + { + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Bloom filter reduction of my_elements, keeping %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); } - GNUNET_free (eo); + return GNUNET_YES; +} - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "destroying intersection op done\n"); - /* FIXME: do a garbage collection of the set generations */ +/** + * Create initial bloomfilter based on all the elements given. + * + * @param cls the `struct Operation *` + * @param key current key code + * @param value the `struct ElementEntry` to process + * @return #GNUNET_YES (we should continue to iterate) + */ +static int +iterator_bf_create (void *cls, + const struct GNUNET_HashCode *key, + void *value) +{ + struct Operation *op = cls; + struct ElementEntry *ee = value; + struct GNUNET_HashCode mutated_hash; + + GNUNET_BLOCK_mingle_hash (&ee->element_hash, + op->state->salt, + &mutated_hash); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Initializing BF with hash %s with salt %u\n", + GNUNET_h2s (&mutated_hash), + op->state->salt); + GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf, + &mutated_hash); + return GNUNET_YES; } @@ -200,457 +398,821 @@ intersection_operation_destroy (struct OperationState *eo) * Inform the client that the intersection operation has failed, * and proceed to destroy the evaluate operation. * - * @param eo the intersection operation to fail + * @param op the intersection operation to fail */ static void -fail_intersection_operation (struct OperationState *eo) +fail_intersection_operation (struct Operation *op) { struct GNUNET_MQ_Envelope *ev; struct GNUNET_SET_ResultMessage *msg; - ev = GNUNET_MQ_msg (msg, GNUNET_MESSAGE_TYPE_SET_RESULT); + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, + "Intersection operation failed\n"); + if (NULL != op->state->my_elements) + { + GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements); + op->state->my_elements = NULL; + } + ev = GNUNET_MQ_msg (msg, + GNUNET_MESSAGE_TYPE_SET_RESULT); msg->result_status = htons (GNUNET_SET_STATUS_FAILURE); - msg->request_id = htonl (eo->spec->client_request_id); + msg->request_id = htonl (op->client_request_id); msg->element_type = htons (0); - GNUNET_MQ_send (eo->spec->set->client_mq, ev); - intersection_operation_destroy (eo); + GNUNET_MQ_send (op->set->cs->mq, + ev); + _GSS_operation_destroy (op, + GNUNET_YES); } /** - * Send a request for the evaluate operation to a remote peer + * Send a bloomfilter to our peer. After the result done message has + * been sent to the client, destroy the evaluate operation. * - * @param eo operation with the other peer + * @param op intersection operation */ static void -send_operation_request (struct Operation *op) +send_bloomfilter (struct Operation *op) { struct GNUNET_MQ_Envelope *ev; - struct OperationRequestMessage *msg; - - ev = GNUNET_MQ_msg_nested_mh (msg, GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST, - op->spec->context_msg); - - if (NULL == ev) + struct BFMessage *msg; + uint32_t bf_size; + uint32_t bf_elementbits; + uint32_t chunk_size; + char *bf_data; + uint32_t offset; + + /* We consider the ratio of the set sizes to determine + the number of bits per element, as the smaller set + should use more bits to maximize its set reduction + potential and minimize overall bandwidth consumption. */ + bf_elementbits = 2 + ceil (log2((double) + (op->remote_element_count / + (double) op->state->my_element_count))); + if (bf_elementbits < 1) + bf_elementbits = 1; /* make sure k is not 0 */ + /* optimize BF-size to ~50% of bits set */ + bf_size = ceil ((double) (op->state->my_element_count + * bf_elementbits / log(2))); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending Bloom filter (%u) of size %u bytes\n", + (unsigned int) bf_elementbits, + (unsigned int) bf_size); + op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL, + bf_size, + bf_elementbits); + op->state->salt = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, + UINT32_MAX); + GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements, + &iterator_bf_create, + op); + + /* send our Bloom filter */ + chunk_size = 60 * 1024 - sizeof (struct BFMessage); + if (bf_size <= chunk_size) { - /* the context message is too large */ - GNUNET_break (0); - GNUNET_SERVER_client_disconnect (op->spec->set->client); - return; + /* singlepart */ + 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 (op->state->local_bf, + (char*) &msg[1], + bf_size)); + msg->sender_element_count = htonl (op->state->my_element_count); + msg->bloomfilter_total_length = htonl (bf_size); + msg->bits_per_element = htonl (bf_elementbits); + msg->sender_mutator = htonl (op->state->salt); + msg->element_xor_hash = op->state->my_xor; + GNUNET_MQ_send (op->mq, ev); } - msg->operation = htonl (GNUNET_SET_OPERATION_INTERSECTION); - msg->app_id = op->spec->app_id; - msg->salt = htonl (op->spec->salt); - GNUNET_MQ_send (op->mq, ev); - - if (NULL != op->spec->context_msg) - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sent op request with context message\n"); else - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sent op request without context message\n"); - - if (NULL != op->spec->context_msg) { - GNUNET_free (op->spec->context_msg); - op->spec->context_msg = NULL; + /* multipart */ + bf_data = GNUNET_malloc (bf_size); + GNUNET_assert (GNUNET_SYSERR != + GNUNET_CONTAINER_bloomfilter_get_raw_data (op->state->local_bf, + bf_data, + bf_size)); + offset = 0; + while (offset < bf_size) + { + if (bf_size - chunk_size < offset) + chunk_size = bf_size - offset; + ev = GNUNET_MQ_msg_extra (msg, + chunk_size, + GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF); + GNUNET_memcpy (&msg[1], + &bf_data[offset], + chunk_size); + offset += chunk_size; + msg->sender_element_count = htonl (op->state->my_element_count); + msg->bloomfilter_total_length = htonl (bf_size); + msg->bits_per_element = htonl (bf_elementbits); + msg->sender_mutator = htonl (op->state->salt); + msg->element_xor_hash = op->state->my_xor; + GNUNET_MQ_send (op->mq, ev); + } + GNUNET_free (bf_data); } + GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf); + op->state->local_bf = NULL; +} + + +/** + * Signal to the client that the operation has finished and + * destroy the operation. + * + * @param cls operation to destroy + */ +static void +send_client_done_and_destroy (void *cls) +{ + struct Operation *op = cls; + struct GNUNET_MQ_Envelope *ev; + struct GNUNET_SET_ResultMessage *rm; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Intersection succeeded, sending DONE to local client\n"); + ev = GNUNET_MQ_msg (rm, + GNUNET_MESSAGE_TYPE_SET_RESULT); + rm->request_id = htonl (op->client_request_id); + rm->result_status = htons (GNUNET_SET_STATUS_DONE); + rm->element_type = htons (0); + GNUNET_MQ_send (op->set->cs->mq, + ev); + _GSS_operation_destroy (op, + GNUNET_YES); } /** - * Handle an BF message from a remote peer. + * Remember that we are done dealing with the local client + * AND have sent the other peer our message that we are done, + * so we are not just waiting for the channel to die before + * telling the local client that we are done as our last act. * - * @param cls the intersection operation - * @param mh the header of the message + * @param cls the `struct Operation`. */ static void -handle_p2p_bf (void *cls, const struct GNUNET_MessageHeader *mh) +finished_local_operations (void *cls) { - struct OperationState *eo = cls; - struct BFMessage *msg = (struct BFMessage *) mh; - unsigned int buckets_in_message; + struct Operation *op = cls; - if (eo->phase == PHASE_EXPECT_INITIAL ) - { - eo->phase = PHASE_BF_EXCHANGE; - - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "creating new bf of size %u\n", 1<order); - - // if (the remote peer has less elements than us) - // run our elements through his bloomfilter - // else if (we have the same elements) - // done; - // - // evict elements we can exclude through the bloomfilter - // - // create a new bloomfilter over our remaining elements - // - // send our new count and the bloomfilter back - } - else if (eo->phase == PHASE_BF_EXCHANGE) - { + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "DONE sent to other peer, now waiting for other end to close the channel\n"); + op->state->phase = PHASE_FINISHED; + op->state->channel_death_expected = GNUNET_YES; +} - } +/** + * Notify the other peer that we are done. Once this message + * is out, we still need to notify the local client that we + * are done. + * + * @param op operation to notify for. + */ +static void +send_p2p_done (struct Operation *op) +{ + struct GNUNET_MQ_Envelope *ev; + struct IntersectionDoneMessage *idm; + + GNUNET_assert (PHASE_MUST_SEND_DONE == op->state->phase); + GNUNET_assert (GNUNET_NO == op->state->channel_death_expected); + ev = GNUNET_MQ_msg (idm, + GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE); + idm->final_element_count = htonl (op->state->my_element_count); + idm->element_xor_hash = op->state->my_xor; + GNUNET_MQ_notify_sent (ev, + &finished_local_operations, + op); + GNUNET_MQ_send (op->mq, + ev); } /** - * Send a result message to the client indicating - * that there is a new element. + * Send all elements in the full result iterator. * - * @param eo intersection operation - * @param element element to send + * @param cls the `struct Operation *` */ static void -send_client_element (struct OperationState *eo, - struct GNUNET_SET_Element *element) +send_remaining_elements (void *cls) { + struct Operation *op = cls; + const void *nxt; + const struct ElementEntry *ee; struct GNUNET_MQ_Envelope *ev; struct GNUNET_SET_ResultMessage *rm; + const struct GNUNET_SET_Element *element; + int res; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending element (size %u) to client\n", element->size); - GNUNET_assert (0 != eo->spec->client_request_id); - ev = GNUNET_MQ_msg_extra (rm, element->size, GNUNET_MESSAGE_TYPE_SET_RESULT); - if (NULL == ev) + res = GNUNET_CONTAINER_multihashmap_iterator_next (op->state->full_result_iter, + NULL, + &nxt); + if (GNUNET_NO == res) { - GNUNET_MQ_discard (ev); - GNUNET_break (0); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending done and destroy because iterator ran out\n"); + GNUNET_CONTAINER_multihashmap_iterator_destroy (op->state->full_result_iter); + op->state->full_result_iter = NULL; + if (PHASE_DONE_RECEIVED == op->state->phase) + { + op->state->phase = PHASE_FINISHED; + send_client_done_and_destroy (op); + } + else if (PHASE_MUST_SEND_DONE == op->state->phase) + { + send_p2p_done (op); + } + else + { + GNUNET_assert (0); + } return; } + ee = nxt; + element = &ee->element; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending element %s:%u to client (full set)\n", + GNUNET_h2s (&ee->element_hash), + element->size); + GNUNET_assert (0 != op->client_request_id); + ev = GNUNET_MQ_msg_extra (rm, + element->size, + GNUNET_MESSAGE_TYPE_SET_RESULT); + GNUNET_assert (NULL != ev); rm->result_status = htons (GNUNET_SET_STATUS_OK); - rm->request_id = htonl (eo->spec->client_request_id); - rm->element_type = element->type; - memcpy (&rm[1], element->data, element->size); - GNUNET_MQ_send (eo->spec->set->client_mq, ev); + rm->request_id = htonl (op->client_request_id); + rm->element_type = element->element_type; + GNUNET_memcpy (&rm[1], + element->data, + element->size); + GNUNET_MQ_notify_sent (ev, + &send_remaining_elements, + op); + GNUNET_MQ_send (op->set->cs->mq, + ev); } /** - * Send a result message to the client indicating - * that the operation is over. - * After the result done message has been sent to the client, - * destroy the evaluate operation. + * Fills the "my_elements" hashmap with the initial set of + * (non-deleted) elements from the set of the specification. * - * @param eo intersection operation + * @param cls closure with the `struct Operation *` + * @param key current key code for the element + * @param value value in the hash map with the `struct ElementEntry *` + * @return #GNUNET_YES (we should continue to iterate) */ -static void -send_client_done_and_destroy (struct OperationState *eo) +static int +initialize_map_unfiltered (void *cls, + const struct GNUNET_HashCode *key, + void *value) { - struct GNUNET_MQ_Envelope *ev; - struct GNUNET_SET_ResultMessage *rm; - - GNUNET_assert (GNUNET_NO == eo->client_done_sent); + struct ElementEntry *ee = value; + struct Operation *op = cls; - eo->client_done_sent = GNUNET_YES; + if (GNUNET_NO == _GSS_is_element_of_operation (ee, op)) + return GNUNET_YES; /* element not live in operation's generation */ + GNUNET_CRYPTO_hash_xor (&op->state->my_xor, + &ee->element_hash, + &op->state->my_xor); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Initial full initialization of my_elements, adding %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + GNUNET_break (GNUNET_YES == + GNUNET_CONTAINER_multihashmap_put (op->state->my_elements, + &ee->element_hash, + ee, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); + return GNUNET_YES; +} - ev = GNUNET_MQ_msg (rm, GNUNET_MESSAGE_TYPE_SET_RESULT); - rm->request_id = htonl (eo->spec->client_request_id); - rm->result_status = htons (GNUNET_SET_STATUS_DONE); - rm->element_type = htons (0); - GNUNET_MQ_send (eo->spec->set->client_mq, ev); - intersection_operation_destroy (eo); +/** + * Send our element count to the peer, in case our element count is + * lower than his. + * + * @param op intersection operation + */ +static void +send_element_count (struct Operation *op) +{ + struct GNUNET_MQ_Envelope *ev; + struct IntersectionElementInfoMessage *msg; + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending our element count (%u)\n", + op->state->my_element_count); + ev = GNUNET_MQ_msg (msg, + GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO); + msg->sender_element_count = htonl (op->state->my_element_count); + GNUNET_MQ_send (op->mq, ev); } + /** - * Send a bloomfilter to our peer. - * that the operation is over. - * After the result done message has been sent to the client, - * destroy the evaluate operation. + * We go first, initialize our map with all elements and + * send the first Bloom filter. * - * @param eo intersection operation + * @param op operation to start exchange for */ static void -send_bloomfilter (struct Operation *op){ - //get number of all elements still in the set - - // send the bloomfilter - unsigned int buckets_sent = 0; - struct BloomFilter *bf; - //TODO: - // add all our elements to the bloomfilter - // create new bloomfilter for all our elements & count elements - //GNUNET_CONTAINER_multihashmap32_remove - //eo->local_bf = GNUNET_CONTAINER_multihashmap32_iterate(eo->set->elements, add); - - op->state->local_bf; - - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending bf of size %u\n", 1<local_bf; - - while (buckets_sent < (1 << bf_order)) - { - unsigned int buckets_in_message; - struct GNUNET_MQ_Envelope *ev; - struct IBFMessage *msg; - - buckets_in_message = (1 << bf_order) - buckets_sent; - /* limit to maximum */ - if (buckets_in_message > MAX_BUCKETS_PER_MESSAGE) - buckets_in_message = MAX_BUCKETS_PER_MESSAGE; - - ev = GNUNET_MQ_msg_extra (msg, buckets_in_message * IBF_BUCKET_SIZE, - GNUNET_MESSAGE_TYPE_SET_P2P_BF); - msg->reserved = 0; - msg->order = bf_order; - msg->offset = htons (buckets_sent); - ibf_write_slice (ibf, buckets_sent, - buckets_in_message, &msg[1]); - buckets_sent += buckets_in_message; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "ibf chunk size %u, %u/%u sent\n", - buckets_in_message, buckets_sent, 1<mq, ev); - } - - eo->phase = PHASE_BF_EXCHANGE; +begin_bf_exchange (struct Operation *op) +{ + op->state->phase = PHASE_BF_EXCHANGE; + GNUNET_CONTAINER_multihashmap_iterate (op->set->content->elements, + &initialize_map_unfiltered, + op); + send_bloomfilter (op); } + /** - * Handle a done message from a remote peer + * Handle the initial `struct IntersectionElementInfoMessage` from a + * remote peer. * * @param cls the intersection operation - * @param mh the message + * @param mh the header of the message */ -static void -handle_p2p_done (void *cls, const struct GNUNET_MessageHeader *mh) +void +handle_intersection_p2p_element_info (void *cls, + const struct IntersectionElementInfoMessage *msg) { - struct OperationState *eo = cls; - struct GNUNET_MQ_Envelope *ev; + struct Operation *op = cls; - if (eo->phase == PHASE_EXPECT_ELEMENTS_AND_REQUESTS) + if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation) { - /* we got all requests, but still have to send our elements as response */ - - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "got DONE, sending final DONE after elements\n"); - eo->phase = PHASE_FINISHED; - ev = GNUNET_MQ_msg_header (GNUNET_MESSAGE_TYPE_SET_P2P_DONE); - GNUNET_MQ_send (eo->mq, ev); + GNUNET_break_op (0); + fail_intersection_operation(op); return; } - if (eo->phase == PHASE_EXPECT_ELEMENTS) + op->remote_element_count = ntohl (msg->sender_element_count); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Received remote element count (%u), I have %u\n", + op->remote_element_count, + op->state->my_element_count); + if ( ( (PHASE_INITIAL != op->state->phase) && + (PHASE_COUNT_SENT != op->state->phase) ) || + (op->state->my_element_count > op->remote_element_count) || + (0 == op->state->my_element_count) || + (0 == op->remote_element_count) ) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "got final DONE\n"); - eo->phase = PHASE_FINISHED; - send_client_done_and_destroy (eo); + GNUNET_break_op (0); + fail_intersection_operation(op); return; } - GNUNET_break (0); - fail_intersection_operation (eo); + GNUNET_break (NULL == op->state->remote_bf); + begin_bf_exchange (op); + GNUNET_CADET_receive_done (op->channel); } /** - * Evaluate a union operation with - * a remote peer. + * Process a Bloomfilter once we got all the chunks. * - * @param op operation to evaluate + * @param op the intersection operation */ static void -intersection_evaluate (struct Operation *op) +process_bf (struct Operation *op) { - op->state = GNUNET_new (struct OperationState); - /* we started the operation, thus we have to send the operation request */ + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Received BF in phase %u, foreign count is %u, my element count is %u/%u\n", + op->state->phase, + op->remote_element_count, + op->state->my_element_count, + GNUNET_CONTAINER_multihashmap_size (op->set->content->elements)); + switch (op->state->phase) + { + case PHASE_INITIAL: + GNUNET_break_op (0); + fail_intersection_operation(op); + return; + case PHASE_COUNT_SENT: + /* This is the first BF being sent, build our initial map with + filtering in place */ + op->state->my_element_count = 0; + GNUNET_CONTAINER_multihashmap_iterate (op->set->content->elements, + &filtered_map_initialization, + op); + break; + case PHASE_BF_EXCHANGE: + /* Update our set by reduction */ + GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements, + &iterator_bf_reduce, + op); + break; + case PHASE_MUST_SEND_DONE: + GNUNET_break_op (0); + fail_intersection_operation(op); + return; + case PHASE_DONE_RECEIVED: + GNUNET_break_op (0); + fail_intersection_operation(op); + return; + case PHASE_FINISHED: + GNUNET_break_op (0); + fail_intersection_operation(op); + return; + } + GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf); + op->state->remote_bf = NULL; + + if ( (0 == op->state->my_element_count) || /* fully disjoint */ + ( (op->state->my_element_count == op->remote_element_count) && + (0 == memcmp (&op->state->my_xor, + &op->state->other_xor, + sizeof (struct GNUNET_HashCode))) ) ) + { + /* we are done */ + op->state->phase = PHASE_MUST_SEND_DONE; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Intersection succeeded, sending DONE to other peer\n"); + GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf); + op->state->local_bf = NULL; + if (GNUNET_SET_RESULT_FULL == op->result_mode) + { + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending full result set (%u elements)\n", + GNUNET_CONTAINER_multihashmap_size (op->state->my_elements)); + op->state->full_result_iter + = GNUNET_CONTAINER_multihashmap_iterator_create (op->state->my_elements); + send_remaining_elements (op); + return; + } + send_p2p_done (op); + return; + } op->state->phase = PHASE_BF_EXCHANGE; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "evaluating intersection operation"); - send_operation_request (op); + send_bloomfilter (op); } /** - * Alice's version: - * - * fills the contained-elements hashmap with all relevant - * elements and adds their mutated hashes to our local bloomfilter with mutator+1 - * - * @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 -intersection_iterator_set_to_contained_alice (void *cls, - const struct GNUNET_HashCode *key, - void *value){ - struct ElementEntry *ee = value; + * Check an BF message from a remote peer. + * + * @param cls the intersection operation + * @param msg the header of the message + * @return #GNUNET_OK if @a msg is well-formed + */ +int +check_intersection_p2p_bf (void *cls, + const struct BFMessage *msg) +{ struct Operation *op = cls; - struct GNUNET_HashCode mutated_hash; - - //only consider this element, if it is valid for us - if ((op->generation_created >= ee->generation_removed) - || (op->generation_created < ee->generation_added)) - return GNUNET_YES; - - // not contained according to bob's bloomfilter - GNUNET_BLOCK_mingle_hash(&ee->element_hash, op->spec->salt, &mutated_hash); - if (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf, - &mutated_hash)) - return GNUNET_YES; - - op->state->contained_elements_count++; - GNUNET_CONTAINER_multihashmap_put (op->state->contained_elements, - &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; + + if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation) + { + GNUNET_break_op (0); + return GNUNET_SYSERR; + } + return GNUNET_OK; } + /** - * Bob's version: - * - * fills the contained-elements hashmap with all relevant - * elements and adds their mutated hashes to our local bloomfilter - * - * @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 -intersection_iterator_set_to_contained_bob (void *cls, - const struct GNUNET_HashCode *key, - void *value){ - struct ElementEntry *ee = value; + * Handle an BF message from a remote peer. + * + * @param cls the intersection operation + * @param msg the header of the message + */ +void +handle_intersection_p2p_bf (void *cls, + const struct BFMessage *msg) +{ struct Operation *op = cls; - struct GNUNET_HashCode mutated_hash; - - //only consider this element, if it is valid for us - if ((op->generation_created >= ee->generation_removed) - || (op->generation_created < ee->generation_added)) - return GNUNET_YES; - - GNUNET_CONTAINER_multihashmap_put (op->state->contained_elements, - &ee->element_hash, ee, - GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY); - - op->state->contained_elements_count++; - - 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; + uint32_t bf_size; + uint32_t chunk_size; + uint32_t bf_bits_per_element; + + switch (op->state->phase) + { + case PHASE_INITIAL: + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + case PHASE_COUNT_SENT: + case PHASE_BF_EXCHANGE: + bf_size = ntohl (msg->bloomfilter_total_length); + bf_bits_per_element = ntohl (msg->bits_per_element); + chunk_size = htons (msg->header.size) - sizeof (struct BFMessage); + op->state->other_xor = msg->element_xor_hash; + if (bf_size == chunk_size) + { + if (NULL != op->state->bf_data) + { + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + } + /* single part, done here immediately */ + op->state->remote_bf + = GNUNET_CONTAINER_bloomfilter_init ((const char*) &msg[1], + bf_size, + bf_bits_per_element); + op->state->salt = ntohl (msg->sender_mutator); + op->remote_element_count = ntohl (msg->sender_element_count); + process_bf (op); + break; + } + /* multipart chunk */ + if (NULL == op->state->bf_data) + { + /* first chunk, initialize */ + op->state->bf_data = GNUNET_malloc (bf_size); + op->state->bf_data_size = bf_size; + op->state->bf_bits_per_element = bf_bits_per_element; + op->state->bf_data_offset = 0; + op->state->salt = ntohl (msg->sender_mutator); + op->remote_element_count = ntohl (msg->sender_element_count); + } + else + { + /* increment */ + if ( (op->state->bf_data_size != bf_size) || + (op->state->bf_bits_per_element != bf_bits_per_element) || + (op->state->bf_data_offset + chunk_size > bf_size) || + (op->state->salt != ntohl (msg->sender_mutator)) || + (op->remote_element_count != ntohl (msg->sender_element_count)) ) + { + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + } + } + GNUNET_memcpy (&op->state->bf_data[op->state->bf_data_offset], + (const char*) &msg[1], + chunk_size); + op->state->bf_data_offset += chunk_size; + if (op->state->bf_data_offset == bf_size) + { + /* last chunk, run! */ + op->state->remote_bf + = GNUNET_CONTAINER_bloomfilter_init (op->state->bf_data, + bf_size, + bf_bits_per_element); + GNUNET_free (op->state->bf_data); + op->state->bf_data = NULL; + op->state->bf_data_size = 0; + process_bf (op); + } + break; + default: + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + } + GNUNET_CADET_receive_done (op->channel); } + /** - * removes element from a hashmap if it is not contained within the - * provided remote bloomfilter. - * - * @param cls closure + * Remove all elements from our hashmap. + * + * @param cls closure with the `struct Operation *` * @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. + * @return #GNUNET_YES (we should continue to iterate) */ static int -intersection_iterator_element_removal (void *cls, - const struct GNUNET_HashCode *key, - void *value){ - struct ElementEntry *ee = value; +filter_all (void *cls, + const struct GNUNET_HashCode *key, + void *value) +{ struct Operation *op = cls; - struct GNUNET_HashCode mutated_hash; - - GNUNET_BLOCK_mingle_hash(&ee->element_hash, op->spec->salt, &mutated_hash); - - if (GNUNET_NO == GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf, - &mutated_hash)){ - op->state->contained_elements_count--; - GNUNET_CONTAINER_multihashmap_remove (op->state->contained_elements, - &ee->element_hash, - ee); - } - + struct ElementEntry *ee = value; + + GNUNET_break (0 < op->state->my_element_count); + op->state->my_element_count--; + GNUNET_CRYPTO_hash_xor (&op->state->my_xor, + &ee->element_hash, + &op->state->my_xor); + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Final reduction of my_elements, removing %s:%u\n", + GNUNET_h2s (&ee->element_hash), + ee->element.size); + GNUNET_assert (GNUNET_YES == + GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements, + &ee->element_hash, + ee)); + send_client_removed_element (op, + &ee->element); return GNUNET_YES; } + /** - * removes element from a hashmap if it is not contained within the - * provided remote bloomfilter. - * - * @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. + * Handle a done message from a remote peer + * + * @param cls the intersection operation + * @param mh the message */ -static int -intersection_iterator_create_bf (void *cls, - const struct GNUNET_HashCode *key, - void *value){ - struct ElementEntry *ee = value; +void +handle_intersection_p2p_done (void *cls, + const struct IntersectionDoneMessage *idm) +{ 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; + + if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation) + { + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + } + if (PHASE_BF_EXCHANGE != op->state->phase) + { + /* wrong phase to conclude? FIXME: Or should we allow this + if the other peer has _initially_ already an empty set? */ + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + } + if (0 == ntohl (idm->final_element_count)) + { + /* other peer determined empty set is the intersection, + remove all elements */ + GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements, + &filter_all, + op); + } + if ( (op->state->my_element_count != ntohl (idm->final_element_count)) || + (0 != memcmp (&op->state->my_xor, + &idm->element_xor_hash, + sizeof (struct GNUNET_HashCode))) ) + { + /* Other peer thinks we are done, but we disagree on the result! */ + GNUNET_break_op (0); + fail_intersection_operation (op); + return; + } + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Got IntersectionDoneMessage, have %u elements in intersection\n", + op->state->my_element_count); + op->state->phase = PHASE_DONE_RECEIVED; + GNUNET_CADET_receive_done (op->channel); + + GNUNET_assert (GNUNET_NO == op->state->client_done_sent); + if (GNUNET_SET_RESULT_FULL == op->result_mode) + { + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sending full result set to client (%u elements)\n", + GNUNET_CONTAINER_multihashmap_size (op->state->my_elements)); + op->state->full_result_iter + = GNUNET_CONTAINER_multihashmap_iterator_create (op->state->my_elements); + send_remaining_elements (op); + return; + } + op->state->phase = PHASE_FINISHED; + send_client_done_and_destroy (op); } /** - * Accept an union operation request from a remote peer. - * Only initializes the private operation state. + * Initiate a set intersection operation with a remote peer. * - * @param op operation that will be accepted as a union operation + * @param op operation that is created, should be initialized to + * begin the evaluation + * @param opaque_context message to be transmitted to the listener + * to convince him to accept, may be NULL + * @return operation-specific state to keep in @a op */ -static void +static struct OperationState * +intersection_evaluate (struct Operation *op, + const struct GNUNET_MessageHeader *opaque_context) +{ + struct OperationState *state; + struct GNUNET_MQ_Envelope *ev; + struct OperationRequestMessage *msg; + + ev = GNUNET_MQ_msg_nested_mh (msg, + GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST, + opaque_context); + if (NULL == ev) + { + /* the context message is too large!? */ + GNUNET_break (0); + return NULL; + } + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Initiating intersection operation evaluation\n"); + state = GNUNET_new (struct OperationState); + /* we started the operation, thus we have to send the operation request */ + state->phase = PHASE_INITIAL; + state->my_element_count = op->set->state->current_set_element_count; + state->my_elements + = GNUNET_CONTAINER_multihashmap_create (state->my_element_count, + GNUNET_YES); + + msg->operation = htonl (GNUNET_SET_OPERATION_INTERSECTION); + msg->element_count = htonl (state->my_element_count); + GNUNET_MQ_send (op->mq, + ev); + state->phase = PHASE_COUNT_SENT; + if (NULL != opaque_context) + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sent op request with context message\n"); + else + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Sent op request without context message\n"); + return state; +} + + +/** + * Accept an intersection operation request from a remote peer. Only + * initializes the private operation state. + * + * @param op operation that will be accepted as an intersection operation + */ +static struct OperationState * intersection_accept (struct Operation *op) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "accepting set union operation\n"); - op->state = GNUNET_new (struct OperationState); - - op->state->contained_elements = GNUNET_CONTAINER_multihashmap_create(1, GNUNET_YES); - - GNUNET_CONTAINER_multihashmap_iterate(op->spec->set->elements, - &intersection_iterator_set_to_contained_bob, - op); - - - op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init(NULL, sizeof(struct GNUNET_HashCode), GNUNET_CONSTANTS_BLOOMFILTER_K); - - if (NULL != op->state->remote_bf){ - // run the set through the remote bloomfilter - ; + struct OperationState *state; + + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Accepting set intersection operation\n"); + state = GNUNET_new (struct OperationState); + state->phase = PHASE_INITIAL; + state->my_element_count + = op->set->state->current_set_element_count; + state->my_elements + = GNUNET_CONTAINER_multihashmap_create (GNUNET_MIN (state->my_element_count, + op->remote_element_count), + GNUNET_YES); + op->state = state; + if (op->remote_element_count < state->my_element_count) + { + /* If the other peer (Alice) has fewer elements than us (Bob), + we just send the count as Alice should send the first BF */ + send_element_count (op); + state->phase = PHASE_COUNT_SENT; + return state; } - - // - op->state->local_bf; - - /* kick off the operation */ - send_bloomfilter (op); + /* We have fewer elements, so we start with the BF */ + begin_bf_exchange (op); + return state; +} + + +/** + * Destroy the intersection operation. Only things specific to the + * intersection operation are destroyed. + * + * @param op intersection operation to destroy + */ +static void +intersection_op_cancel (struct Operation *op) +{ + /* check if the op was canceled twice */ + GNUNET_assert (NULL != op->state); + if (NULL != op->state->remote_bf) + { + GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf); + op->state->remote_bf = NULL; + } + if (NULL != op->state->local_bf) + { + GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf); + op->state->local_bf = NULL; + } + if (NULL != op->state->my_elements) + { + GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements); + op->state->my_elements = NULL; + } + if (NULL != op->state->full_result_iter) + { + GNUNET_CONTAINER_multihashmap_iterator_destroy (op->state->full_result_iter); + op->state->full_result_iter = NULL; + } + GNUNET_free (op->state); + op->state = NULL; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Destroying intersection op state done\n"); } /** - * Create a new set supporting the intersection operation + * Create a new set supporting the intersection operation. * * @return the newly created set */ static struct SetState * -intersection_set_create (void) +intersection_set_create () { struct SetState *set_state; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "intersection set created\n"); - + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Intersection set created\n"); set_state = GNUNET_new (struct SetState); - + set_state->current_set_element_count = 0; + return set_state; } @@ -662,9 +1224,10 @@ intersection_set_create (void) * @param ee the element to add to the set */ static void -intersection_add (struct SetState *set_state, struct ElementEntry *ee) +intersection_add (struct SetState *set_state, + struct ElementEntry *ee) { - //nothing to do here + set_state->current_set_element_count++; } @@ -687,157 +1250,53 @@ intersection_set_destroy (struct SetState *set_state) * @param element set element to remove */ static void -intersection_remove (struct SetState *set_state, struct ElementEntry *element) -{ - //nothing to do here -} - - -/** - * Dispatch messages for a intersection operation. - * - * @param eo the state of the intersection evaluate operation - * @param mh the received message - * @return GNUNET_SYSERR if the tunnel should be disconnected, - * GNUNET_OK otherwise - */ -int -intersection_handle_p2p_message (struct OperationState *eo, - const struct GNUNET_MessageHeader *mh) +intersection_remove (struct SetState *set_state, + struct ElementEntry *element) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "received p2p message (t: %u, s: %u)\n", - ntohs (mh->type), ntohs (mh->size)); - switch (ntohs (mh->type)) - { - /* this message handler is not active until after we received an - * operation request message, thus the ops request is not handled here - */ - case GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF: - handle_p2p_bf (eo, mh); - break; - case GNUNET_MESSAGE_TYPE_SET_P2P_DONE: - handle_p2p_done (eo, mh); - break; - default: - /* something wrong with mesh's message handlers? */ - GNUNET_assert (0); - } - return GNUNET_OK; + GNUNET_assert (0 < set_state->current_set_element_count); + set_state->current_set_element_count--; } -/** - * Signal to the client that the operation has finished and - * destroy the operation. - * - * @param cls operation to destroy - */ -static void -send_done_and_destroy (void *cls) -{ - struct Operation *op = cls; - struct GNUNET_MQ_Envelope *ev; - struct GNUNET_SET_ResultMessage *rm; - ev = GNUNET_MQ_msg (rm, GNUNET_MESSAGE_TYPE_SET_RESULT); - rm->request_id = htonl (op->spec->client_request_id); - rm->result_status = htons (GNUNET_SET_STATUS_DONE); - rm->element_type = htons (0); - GNUNET_MQ_send (op->spec->set->client_mq, ev); - _GSS_operation_destroy (op); -} /** - * Send a result message to the client indicating - * that the operation is over. - * After the result done message has been sent to the client, - * destroy the evaluate operation. + * Callback for channel death for the intersection operation. * - * @param op union operation + * @param op operation that lost the channel */ static void -finish_and_destroy (struct Operation *op) +intersection_channel_death (struct Operation *op) { - GNUNET_assert (GNUNET_NO == op->state->client_done_sent); - - if (GNUNET_SET_RESULT_FULL == op->spec->result_mode) + if (GNUNET_YES == op->state->channel_death_expected) { - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "sending full result set\n"); - GNUNET_assert (NULL == op->state->full_result_iter); - op->state->full_result_iter = - GNUNET_CONTAINER_multihashmap32_iterator_create (op->state->contained_elements); - return; + /* oh goodie, we are done! */ + send_client_done_and_destroy (op); } - send_done_and_destroy (op); -} - - -static void -intersection_peer_disconnect (struct Operation *op) -{ - if (PHASE_FINISHED != op->state->phase) + else { - struct GNUNET_MQ_Envelope *ev; - struct GNUNET_SET_ResultMessage *msg; - - ev = GNUNET_MQ_msg (msg, GNUNET_MESSAGE_TYPE_SET_RESULT); - msg->request_id = htonl (op->spec->client_request_id); - msg->result_status = htons (GNUNET_SET_STATUS_FAILURE); - msg->element_type = htons (0); - GNUNET_MQ_send (op->spec->set->client_mq, ev); - GNUNET_log (GNUNET_ERROR_TYPE_WARNING, "other peer disconnected prematurely\n"); - _GSS_operation_destroy (op); - return; + /* sorry, channel went down early, too bad. */ + _GSS_operation_destroy (op, + GNUNET_YES); } - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "other peer disconnected (finished)\n"); - if (GNUNET_NO == op->state->client_done_sent) - finish_and_destroy (op); } /** - * Destroy the union operation. Only things specific to the union operation are destroyed. - * - * @param op union operation to destroy + * Get the table with implementing functions for set intersection. + * + * @return the operation specific VTable */ -static void -intersection_op_cancel (struct Operation *op) -{ - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "destroying intersection op\n"); - /* check if the op was canceled twice */ - GNUNET_assert (NULL != op->state); - if (NULL != op->state->remote_bf) - { - GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf); - op->state->remote_bf = NULL; - } - if (NULL != op->state->local_bf) - { - GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf); - op->state->local_bf = NULL; - } - if (NULL != op->state->contained_elements) - { - // no need to free the elements, they are still part of the set - GNUNET_CONTAINER_multihashmap_destroy (op->state->contained_elements); - op->state->contained_elements = NULL; - } - GNUNET_free (op->state); - op->state = NULL; - GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "destroying intersection op done\n"); -} - const struct SetVT * _GSS_intersection_vt () { static const struct SetVT intersection_vt = { .create = &intersection_set_create, - .msg_handler = &intersection_handle_p2p_message, .add = &intersection_add, .remove = &intersection_remove, .destroy_set = &intersection_set_destroy, .evaluate = &intersection_evaluate, .accept = &intersection_accept, - .peer_disconnect = &intersection_peer_disconnect, .cancel = &intersection_op_cancel, + .channel_death = &intersection_channel_death, }; return &intersection_vt;