diff options
Diffstat (limited to 'src/set/gnunet-service-set_intersection.c')
-rw-r--r-- | src/set/gnunet-service-set_intersection.c | 1331 |
1 files changed, 0 insertions, 1331 deletions
diff --git a/src/set/gnunet-service-set_intersection.c b/src/set/gnunet-service-set_intersection.c deleted file mode 100644 index 9313483bb..000000000 --- a/src/set/gnunet-service-set_intersection.c +++ /dev/null | |||
@@ -1,1331 +0,0 @@ | |||
1 | /* | ||
2 | This file is part of GNUnet | ||
3 | Copyright (C) 2013-2017 GNUnet e.V. | ||
4 | |||
5 | GNUnet is free software: you can redistribute it and/or modify it | ||
6 | under the terms of the GNU Affero General Public License as published | ||
7 | by the Free Software Foundation, either version 3 of the License, | ||
8 | or (at your option) any later version. | ||
9 | |||
10 | GNUnet is distributed in the hope that it will be useful, but | ||
11 | WITHOUT ANY WARRANTY; without even the implied warranty of | ||
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | ||
13 | Affero General Public License for more details. | ||
14 | |||
15 | You should have received a copy of the GNU Affero General Public License | ||
16 | along with this program. If not, see <http://www.gnu.org/licenses/>. | ||
17 | |||
18 | SPDX-License-Identifier: AGPL3.0-or-later | ||
19 | */ | ||
20 | /** | ||
21 | * @file set/gnunet-service-set_intersection.c | ||
22 | * @brief two-peer set intersection | ||
23 | * @author Christian Fuchs | ||
24 | * @author Christian Grothoff | ||
25 | */ | ||
26 | #include "platform.h" | ||
27 | #include "gnunet_util_lib.h" | ||
28 | #include "gnunet_statistics_service.h" | ||
29 | #include "gnunet-service-set.h" | ||
30 | #include "gnunet_block_lib.h" | ||
31 | #include "gnunet-service-set_protocol.h" | ||
32 | #include "gnunet-service-set_intersection.h" | ||
33 | #include <gcrypt.h> | ||
34 | |||
35 | |||
36 | /** | ||
37 | * Current phase we are in for a intersection operation. | ||
38 | */ | ||
39 | enum IntersectionOperationPhase | ||
40 | { | ||
41 | /** | ||
42 | * We are just starting. | ||
43 | */ | ||
44 | PHASE_INITIAL, | ||
45 | |||
46 | /** | ||
47 | * We have send the number of our elements to the other | ||
48 | * peer, but did not setup our element set yet. | ||
49 | */ | ||
50 | PHASE_COUNT_SENT, | ||
51 | |||
52 | /** | ||
53 | * We have initialized our set and are now reducing it by exchanging | ||
54 | * Bloom filters until one party notices the their element hashes | ||
55 | * are equal. | ||
56 | */ | ||
57 | PHASE_BF_EXCHANGE, | ||
58 | |||
59 | /** | ||
60 | * We must next send the P2P DONE message (after finishing mostly | ||
61 | * with the local client). Then we will wait for the channel to close. | ||
62 | */ | ||
63 | PHASE_MUST_SEND_DONE, | ||
64 | |||
65 | /** | ||
66 | * We have received the P2P DONE message, and must finish with the | ||
67 | * local client before terminating the channel. | ||
68 | */ | ||
69 | PHASE_DONE_RECEIVED, | ||
70 | |||
71 | /** | ||
72 | * The protocol is over. Results may still have to be sent to the | ||
73 | * client. | ||
74 | */ | ||
75 | PHASE_FINISHED | ||
76 | }; | ||
77 | |||
78 | |||
79 | /** | ||
80 | * State of an evaluate operation with another peer. | ||
81 | */ | ||
82 | struct OperationState | ||
83 | { | ||
84 | /** | ||
85 | * The bf we currently receive | ||
86 | */ | ||
87 | struct GNUNET_CONTAINER_BloomFilter *remote_bf; | ||
88 | |||
89 | /** | ||
90 | * BF of the set's element. | ||
91 | */ | ||
92 | struct GNUNET_CONTAINER_BloomFilter *local_bf; | ||
93 | |||
94 | /** | ||
95 | * Remaining elements in the intersection operation. | ||
96 | * Maps element-id-hashes to 'elements in our set'. | ||
97 | */ | ||
98 | struct GNUNET_CONTAINER_MultiHashMap *my_elements; | ||
99 | |||
100 | /** | ||
101 | * Iterator for sending the final set of @e my_elements to the client. | ||
102 | */ | ||
103 | struct GNUNET_CONTAINER_MultiHashMapIterator *full_result_iter; | ||
104 | |||
105 | /** | ||
106 | * Evaluate operations are held in a linked list. | ||
107 | */ | ||
108 | struct OperationState *next; | ||
109 | |||
110 | /** | ||
111 | * Evaluate operations are held in a linked list. | ||
112 | */ | ||
113 | struct OperationState *prev; | ||
114 | |||
115 | /** | ||
116 | * For multipart BF transmissions, we have to store the | ||
117 | * bloomfilter-data until we fully received it. | ||
118 | */ | ||
119 | char *bf_data; | ||
120 | |||
121 | /** | ||
122 | * XOR of the keys of all of the elements (remaining) in my set. | ||
123 | * Always updated when elements are added or removed to | ||
124 | * @e my_elements. | ||
125 | */ | ||
126 | struct GNUNET_HashCode my_xor; | ||
127 | |||
128 | /** | ||
129 | * XOR of the keys of all of the elements (remaining) in | ||
130 | * the other peer's set. Updated when we receive the | ||
131 | * other peer's Bloom filter. | ||
132 | */ | ||
133 | struct GNUNET_HashCode other_xor; | ||
134 | |||
135 | /** | ||
136 | * How many bytes of @e bf_data are valid? | ||
137 | */ | ||
138 | uint32_t bf_data_offset; | ||
139 | |||
140 | /** | ||
141 | * Current element count contained within @e my_elements. | ||
142 | * (May differ briefly during initialization.) | ||
143 | */ | ||
144 | uint32_t my_element_count; | ||
145 | |||
146 | /** | ||
147 | * size of the bloomfilter in @e bf_data. | ||
148 | */ | ||
149 | uint32_t bf_data_size; | ||
150 | |||
151 | /** | ||
152 | * size of the bloomfilter | ||
153 | */ | ||
154 | uint32_t bf_bits_per_element; | ||
155 | |||
156 | /** | ||
157 | * Salt currently used for BF construction (by us or the other peer, | ||
158 | * depending on where we are in the code). | ||
159 | */ | ||
160 | uint32_t salt; | ||
161 | |||
162 | /** | ||
163 | * Current state of the operation. | ||
164 | */ | ||
165 | enum IntersectionOperationPhase phase; | ||
166 | |||
167 | /** | ||
168 | * Generation in which the operation handle | ||
169 | * was created. | ||
170 | */ | ||
171 | unsigned int generation_created; | ||
172 | |||
173 | /** | ||
174 | * Did we send the client that we are done? | ||
175 | */ | ||
176 | int client_done_sent; | ||
177 | |||
178 | /** | ||
179 | * Set whenever we reach the state where the death of the | ||
180 | * channel is perfectly find and should NOT result in the | ||
181 | * operation being cancelled. | ||
182 | */ | ||
183 | int channel_death_expected; | ||
184 | }; | ||
185 | |||
186 | |||
187 | /** | ||
188 | * Extra state required for efficient set intersection. | ||
189 | * Merely tracks the total number of elements. | ||
190 | */ | ||
191 | struct SetState | ||
192 | { | ||
193 | /** | ||
194 | * Number of currently valid elements in the set which have not been | ||
195 | * removed. | ||
196 | */ | ||
197 | uint32_t current_set_element_count; | ||
198 | }; | ||
199 | |||
200 | |||
201 | /** | ||
202 | * If applicable in the current operation mode, send a result message | ||
203 | * to the client indicating we removed an element. | ||
204 | * | ||
205 | * @param op intersection operation | ||
206 | * @param element element to send | ||
207 | */ | ||
208 | static void | ||
209 | send_client_removed_element (struct Operation *op, | ||
210 | struct GNUNET_SET_Element *element) | ||
211 | { | ||
212 | struct GNUNET_MQ_Envelope *ev; | ||
213 | struct GNUNET_SET_ResultMessage *rm; | ||
214 | |||
215 | if (GNUNET_SET_RESULT_REMOVED != op->result_mode) | ||
216 | return; /* Wrong mode for transmitting removed elements */ | ||
217 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
218 | "Sending removed element (size %u) to client\n", | ||
219 | element->size); | ||
220 | GNUNET_STATISTICS_update (_GSS_statistics, | ||
221 | "# Element removed messages sent", | ||
222 | 1, | ||
223 | GNUNET_NO); | ||
224 | GNUNET_assert (0 != op->client_request_id); | ||
225 | ev = GNUNET_MQ_msg_extra (rm, | ||
226 | element->size, | ||
227 | GNUNET_MESSAGE_TYPE_SET_RESULT); | ||
228 | if (NULL == ev) | ||
229 | { | ||
230 | GNUNET_break (0); | ||
231 | return; | ||
232 | } | ||
233 | rm->result_status = htons (GNUNET_SET_STATUS_OK); | ||
234 | rm->request_id = htonl (op->client_request_id); | ||
235 | rm->element_type = element->element_type; | ||
236 | GNUNET_memcpy (&rm[1], | ||
237 | element->data, | ||
238 | element->size); | ||
239 | GNUNET_MQ_send (op->set->cs->mq, | ||
240 | ev); | ||
241 | } | ||
242 | |||
243 | |||
244 | /** | ||
245 | * Fills the "my_elements" hashmap with all relevant elements. | ||
246 | * | ||
247 | * @param cls the `struct Operation *` we are performing | ||
248 | * @param key current key code | ||
249 | * @param value the `struct ElementEntry *` from the hash map | ||
250 | * @return #GNUNET_YES (we should continue to iterate) | ||
251 | */ | ||
252 | static int | ||
253 | filtered_map_initialization (void *cls, | ||
254 | const struct GNUNET_HashCode *key, | ||
255 | void *value) | ||
256 | { | ||
257 | struct Operation *op = cls; | ||
258 | struct ElementEntry *ee = value; | ||
259 | struct GNUNET_HashCode mutated_hash; | ||
260 | |||
261 | |||
262 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
263 | "FIMA called for %s:%u\n", | ||
264 | GNUNET_h2s (&ee->element_hash), | ||
265 | ee->element.size); | ||
266 | |||
267 | if (GNUNET_NO == _GSS_is_element_of_operation (ee, op)) | ||
268 | { | ||
269 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
270 | "Reduced initialization, not starting with %s:%u (wrong generation)\n", | ||
271 | GNUNET_h2s (&ee->element_hash), | ||
272 | ee->element.size); | ||
273 | return GNUNET_YES; /* element not valid in our operation's generation */ | ||
274 | } | ||
275 | |||
276 | /* Test if element is in other peer's bloomfilter */ | ||
277 | GNUNET_BLOCK_mingle_hash (&ee->element_hash, | ||
278 | op->state->salt, | ||
279 | &mutated_hash); | ||
280 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
281 | "Testing mingled hash %s with salt %u\n", | ||
282 | GNUNET_h2s (&mutated_hash), | ||
283 | op->state->salt); | ||
284 | if (GNUNET_NO == | ||
285 | GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf, | ||
286 | &mutated_hash)) | ||
287 | { | ||
288 | /* remove this element */ | ||
289 | send_client_removed_element (op, | ||
290 | &ee->element); | ||
291 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
292 | "Reduced initialization, not starting with %s:%u\n", | ||
293 | GNUNET_h2s (&ee->element_hash), | ||
294 | ee->element.size); | ||
295 | return GNUNET_YES; | ||
296 | } | ||
297 | op->state->my_element_count++; | ||
298 | GNUNET_CRYPTO_hash_xor (&op->state->my_xor, | ||
299 | &ee->element_hash, | ||
300 | &op->state->my_xor); | ||
301 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
302 | "Filtered initialization of my_elements, adding %s:%u\n", | ||
303 | GNUNET_h2s (&ee->element_hash), | ||
304 | ee->element.size); | ||
305 | GNUNET_break (GNUNET_YES == | ||
306 | GNUNET_CONTAINER_multihashmap_put (op->state->my_elements, | ||
307 | &ee->element_hash, | ||
308 | ee, | ||
309 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
310 | |||
311 | return GNUNET_YES; | ||
312 | } | ||
313 | |||
314 | |||
315 | /** | ||
316 | * Removes elements from our hashmap if they are not contained within the | ||
317 | * provided remote bloomfilter. | ||
318 | * | ||
319 | * @param cls closure with the `struct Operation *` | ||
320 | * @param key current key code | ||
321 | * @param value value in the hash map | ||
322 | * @return #GNUNET_YES (we should continue to iterate) | ||
323 | */ | ||
324 | static int | ||
325 | iterator_bf_reduce (void *cls, | ||
326 | const struct GNUNET_HashCode *key, | ||
327 | void *value) | ||
328 | { | ||
329 | struct Operation *op = cls; | ||
330 | struct ElementEntry *ee = value; | ||
331 | struct GNUNET_HashCode mutated_hash; | ||
332 | |||
333 | GNUNET_BLOCK_mingle_hash (&ee->element_hash, | ||
334 | op->state->salt, | ||
335 | &mutated_hash); | ||
336 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
337 | "Testing mingled hash %s with salt %u\n", | ||
338 | GNUNET_h2s (&mutated_hash), | ||
339 | op->state->salt); | ||
340 | if (GNUNET_NO == | ||
341 | GNUNET_CONTAINER_bloomfilter_test (op->state->remote_bf, | ||
342 | &mutated_hash)) | ||
343 | { | ||
344 | GNUNET_break (0 < op->state->my_element_count); | ||
345 | op->state->my_element_count--; | ||
346 | GNUNET_CRYPTO_hash_xor (&op->state->my_xor, | ||
347 | &ee->element_hash, | ||
348 | &op->state->my_xor); | ||
349 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
350 | "Bloom filter reduction of my_elements, removing %s:%u\n", | ||
351 | GNUNET_h2s (&ee->element_hash), | ||
352 | ee->element.size); | ||
353 | GNUNET_assert (GNUNET_YES == | ||
354 | GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements, | ||
355 | &ee->element_hash, | ||
356 | ee)); | ||
357 | send_client_removed_element (op, | ||
358 | &ee->element); | ||
359 | } | ||
360 | else | ||
361 | { | ||
362 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
363 | "Bloom filter reduction of my_elements, keeping %s:%u\n", | ||
364 | GNUNET_h2s (&ee->element_hash), | ||
365 | ee->element.size); | ||
366 | } | ||
367 | return GNUNET_YES; | ||
368 | } | ||
369 | |||
370 | |||
371 | /** | ||
372 | * Create initial bloomfilter based on all the elements given. | ||
373 | * | ||
374 | * @param cls the `struct Operation *` | ||
375 | * @param key current key code | ||
376 | * @param value the `struct ElementEntry` to process | ||
377 | * @return #GNUNET_YES (we should continue to iterate) | ||
378 | */ | ||
379 | static int | ||
380 | iterator_bf_create (void *cls, | ||
381 | const struct GNUNET_HashCode *key, | ||
382 | void *value) | ||
383 | { | ||
384 | struct Operation *op = cls; | ||
385 | struct ElementEntry *ee = value; | ||
386 | struct GNUNET_HashCode mutated_hash; | ||
387 | |||
388 | GNUNET_BLOCK_mingle_hash (&ee->element_hash, | ||
389 | op->state->salt, | ||
390 | &mutated_hash); | ||
391 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
392 | "Initializing BF with hash %s with salt %u\n", | ||
393 | GNUNET_h2s (&mutated_hash), | ||
394 | op->state->salt); | ||
395 | GNUNET_CONTAINER_bloomfilter_add (op->state->local_bf, | ||
396 | &mutated_hash); | ||
397 | return GNUNET_YES; | ||
398 | } | ||
399 | |||
400 | |||
401 | /** | ||
402 | * Inform the client that the intersection operation has failed, | ||
403 | * and proceed to destroy the evaluate operation. | ||
404 | * | ||
405 | * @param op the intersection operation to fail | ||
406 | */ | ||
407 | static void | ||
408 | fail_intersection_operation (struct Operation *op) | ||
409 | { | ||
410 | struct GNUNET_MQ_Envelope *ev; | ||
411 | struct GNUNET_SET_ResultMessage *msg; | ||
412 | |||
413 | GNUNET_log (GNUNET_ERROR_TYPE_WARNING, | ||
414 | "Intersection operation failed\n"); | ||
415 | GNUNET_STATISTICS_update (_GSS_statistics, | ||
416 | "# Intersection operations failed", | ||
417 | 1, | ||
418 | GNUNET_NO); | ||
419 | if (NULL != op->state->my_elements) | ||
420 | { | ||
421 | GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements); | ||
422 | op->state->my_elements = NULL; | ||
423 | } | ||
424 | ev = GNUNET_MQ_msg (msg, | ||
425 | GNUNET_MESSAGE_TYPE_SET_RESULT); | ||
426 | msg->result_status = htons (GNUNET_SET_STATUS_FAILURE); | ||
427 | msg->request_id = htonl (op->client_request_id); | ||
428 | msg->element_type = htons (0); | ||
429 | GNUNET_MQ_send (op->set->cs->mq, | ||
430 | ev); | ||
431 | _GSS_operation_destroy (op, | ||
432 | GNUNET_YES); | ||
433 | } | ||
434 | |||
435 | |||
436 | /** | ||
437 | * Send a bloomfilter to our peer. After the result done message has | ||
438 | * been sent to the client, destroy the evaluate operation. | ||
439 | * | ||
440 | * @param op intersection operation | ||
441 | */ | ||
442 | static void | ||
443 | send_bloomfilter (struct Operation *op) | ||
444 | { | ||
445 | struct GNUNET_MQ_Envelope *ev; | ||
446 | struct BFMessage *msg; | ||
447 | uint32_t bf_size; | ||
448 | uint32_t bf_elementbits; | ||
449 | uint32_t chunk_size; | ||
450 | char *bf_data; | ||
451 | uint32_t offset; | ||
452 | |||
453 | /* We consider the ratio of the set sizes to determine | ||
454 | the number of bits per element, as the smaller set | ||
455 | should use more bits to maximize its set reduction | ||
456 | potential and minimize overall bandwidth consumption. */ | ||
457 | bf_elementbits = 2 + ceil (log2 ((double) | ||
458 | (op->remote_element_count | ||
459 | / (double) op->state->my_element_count))); | ||
460 | if (bf_elementbits < 1) | ||
461 | bf_elementbits = 1; /* make sure k is not 0 */ | ||
462 | /* optimize BF-size to ~50% of bits set */ | ||
463 | bf_size = ceil ((double) (op->state->my_element_count | ||
464 | * bf_elementbits / log (2))); | ||
465 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
466 | "Sending Bloom filter (%u) of size %u bytes\n", | ||
467 | (unsigned int) bf_elementbits, | ||
468 | (unsigned int) bf_size); | ||
469 | op->state->local_bf = GNUNET_CONTAINER_bloomfilter_init (NULL, | ||
470 | bf_size, | ||
471 | bf_elementbits); | ||
472 | op->state->salt = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE, | ||
473 | UINT32_MAX); | ||
474 | GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements, | ||
475 | &iterator_bf_create, | ||
476 | op); | ||
477 | |||
478 | /* send our Bloom filter */ | ||
479 | GNUNET_STATISTICS_update (_GSS_statistics, | ||
480 | "# Intersection Bloom filters sent", | ||
481 | 1, | ||
482 | GNUNET_NO); | ||
483 | chunk_size = 60 * 1024 - sizeof(struct BFMessage); | ||
484 | if (bf_size <= chunk_size) | ||
485 | { | ||
486 | /* singlepart */ | ||
487 | chunk_size = bf_size; | ||
488 | ev = GNUNET_MQ_msg_extra (msg, | ||
489 | chunk_size, | ||
490 | GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF); | ||
491 | GNUNET_assert (GNUNET_SYSERR != | ||
492 | GNUNET_CONTAINER_bloomfilter_get_raw_data ( | ||
493 | op->state->local_bf, | ||
494 | (char *) &msg[1], | ||
495 | bf_size)); | ||
496 | msg->sender_element_count = htonl (op->state->my_element_count); | ||
497 | msg->bloomfilter_total_length = htonl (bf_size); | ||
498 | msg->bits_per_element = htonl (bf_elementbits); | ||
499 | msg->sender_mutator = htonl (op->state->salt); | ||
500 | msg->element_xor_hash = op->state->my_xor; | ||
501 | GNUNET_MQ_send (op->mq, ev); | ||
502 | } | ||
503 | else | ||
504 | { | ||
505 | /* multipart */ | ||
506 | bf_data = GNUNET_malloc (bf_size); | ||
507 | GNUNET_assert (GNUNET_SYSERR != | ||
508 | GNUNET_CONTAINER_bloomfilter_get_raw_data ( | ||
509 | op->state->local_bf, | ||
510 | bf_data, | ||
511 | bf_size)); | ||
512 | offset = 0; | ||
513 | while (offset < bf_size) | ||
514 | { | ||
515 | if (bf_size - chunk_size < offset) | ||
516 | chunk_size = bf_size - offset; | ||
517 | ev = GNUNET_MQ_msg_extra (msg, | ||
518 | chunk_size, | ||
519 | GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_BF); | ||
520 | GNUNET_memcpy (&msg[1], | ||
521 | &bf_data[offset], | ||
522 | chunk_size); | ||
523 | offset += chunk_size; | ||
524 | msg->sender_element_count = htonl (op->state->my_element_count); | ||
525 | msg->bloomfilter_total_length = htonl (bf_size); | ||
526 | msg->bits_per_element = htonl (bf_elementbits); | ||
527 | msg->sender_mutator = htonl (op->state->salt); | ||
528 | msg->element_xor_hash = op->state->my_xor; | ||
529 | GNUNET_MQ_send (op->mq, ev); | ||
530 | } | ||
531 | GNUNET_free (bf_data); | ||
532 | } | ||
533 | GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf); | ||
534 | op->state->local_bf = NULL; | ||
535 | } | ||
536 | |||
537 | |||
538 | /** | ||
539 | * Signal to the client that the operation has finished and | ||
540 | * destroy the operation. | ||
541 | * | ||
542 | * @param cls operation to destroy | ||
543 | */ | ||
544 | static void | ||
545 | send_client_done_and_destroy (void *cls) | ||
546 | { | ||
547 | struct Operation *op = cls; | ||
548 | struct GNUNET_MQ_Envelope *ev; | ||
549 | struct GNUNET_SET_ResultMessage *rm; | ||
550 | |||
551 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
552 | "Intersection succeeded, sending DONE to local client\n"); | ||
553 | GNUNET_STATISTICS_update (_GSS_statistics, | ||
554 | "# Intersection operations succeeded", | ||
555 | 1, | ||
556 | GNUNET_NO); | ||
557 | ev = GNUNET_MQ_msg (rm, | ||
558 | GNUNET_MESSAGE_TYPE_SET_RESULT); | ||
559 | rm->request_id = htonl (op->client_request_id); | ||
560 | rm->result_status = htons (GNUNET_SET_STATUS_DONE); | ||
561 | rm->element_type = htons (0); | ||
562 | GNUNET_MQ_send (op->set->cs->mq, | ||
563 | ev); | ||
564 | _GSS_operation_destroy (op, | ||
565 | GNUNET_YES); | ||
566 | } | ||
567 | |||
568 | |||
569 | /** | ||
570 | * Remember that we are done dealing with the local client | ||
571 | * AND have sent the other peer our message that we are done, | ||
572 | * so we are not just waiting for the channel to die before | ||
573 | * telling the local client that we are done as our last act. | ||
574 | * | ||
575 | * @param cls the `struct Operation`. | ||
576 | */ | ||
577 | static void | ||
578 | finished_local_operations (void *cls) | ||
579 | { | ||
580 | struct Operation *op = cls; | ||
581 | |||
582 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
583 | "DONE sent to other peer, now waiting for other end to close the channel\n"); | ||
584 | op->state->phase = PHASE_FINISHED; | ||
585 | op->state->channel_death_expected = GNUNET_YES; | ||
586 | } | ||
587 | |||
588 | |||
589 | /** | ||
590 | * Notify the other peer that we are done. Once this message | ||
591 | * is out, we still need to notify the local client that we | ||
592 | * are done. | ||
593 | * | ||
594 | * @param op operation to notify for. | ||
595 | */ | ||
596 | static void | ||
597 | send_p2p_done (struct Operation *op) | ||
598 | { | ||
599 | struct GNUNET_MQ_Envelope *ev; | ||
600 | struct IntersectionDoneMessage *idm; | ||
601 | |||
602 | GNUNET_assert (PHASE_MUST_SEND_DONE == op->state->phase); | ||
603 | GNUNET_assert (GNUNET_NO == op->state->channel_death_expected); | ||
604 | ev = GNUNET_MQ_msg (idm, | ||
605 | GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_DONE); | ||
606 | idm->final_element_count = htonl (op->state->my_element_count); | ||
607 | idm->element_xor_hash = op->state->my_xor; | ||
608 | GNUNET_MQ_notify_sent (ev, | ||
609 | &finished_local_operations, | ||
610 | op); | ||
611 | GNUNET_MQ_send (op->mq, | ||
612 | ev); | ||
613 | } | ||
614 | |||
615 | |||
616 | /** | ||
617 | * Send all elements in the full result iterator. | ||
618 | * | ||
619 | * @param cls the `struct Operation *` | ||
620 | */ | ||
621 | static void | ||
622 | send_remaining_elements (void *cls) | ||
623 | { | ||
624 | struct Operation *op = cls; | ||
625 | const void *nxt; | ||
626 | const struct ElementEntry *ee; | ||
627 | struct GNUNET_MQ_Envelope *ev; | ||
628 | struct GNUNET_SET_ResultMessage *rm; | ||
629 | const struct GNUNET_SET_Element *element; | ||
630 | int res; | ||
631 | |||
632 | res = GNUNET_CONTAINER_multihashmap_iterator_next ( | ||
633 | op->state->full_result_iter, | ||
634 | NULL, | ||
635 | &nxt); | ||
636 | if (GNUNET_NO == res) | ||
637 | { | ||
638 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
639 | "Sending done and destroy because iterator ran out\n"); | ||
640 | GNUNET_CONTAINER_multihashmap_iterator_destroy ( | ||
641 | op->state->full_result_iter); | ||
642 | op->state->full_result_iter = NULL; | ||
643 | if (PHASE_DONE_RECEIVED == op->state->phase) | ||
644 | { | ||
645 | op->state->phase = PHASE_FINISHED; | ||
646 | send_client_done_and_destroy (op); | ||
647 | } | ||
648 | else if (PHASE_MUST_SEND_DONE == op->state->phase) | ||
649 | { | ||
650 | send_p2p_done (op); | ||
651 | } | ||
652 | else | ||
653 | { | ||
654 | GNUNET_assert (0); | ||
655 | } | ||
656 | return; | ||
657 | } | ||
658 | ee = nxt; | ||
659 | element = &ee->element; | ||
660 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
661 | "Sending element %s:%u to client (full set)\n", | ||
662 | GNUNET_h2s (&ee->element_hash), | ||
663 | element->size); | ||
664 | GNUNET_assert (0 != op->client_request_id); | ||
665 | ev = GNUNET_MQ_msg_extra (rm, | ||
666 | element->size, | ||
667 | GNUNET_MESSAGE_TYPE_SET_RESULT); | ||
668 | GNUNET_assert (NULL != ev); | ||
669 | rm->result_status = htons (GNUNET_SET_STATUS_OK); | ||
670 | rm->request_id = htonl (op->client_request_id); | ||
671 | rm->element_type = element->element_type; | ||
672 | GNUNET_memcpy (&rm[1], | ||
673 | element->data, | ||
674 | element->size); | ||
675 | GNUNET_MQ_notify_sent (ev, | ||
676 | &send_remaining_elements, | ||
677 | op); | ||
678 | GNUNET_MQ_send (op->set->cs->mq, | ||
679 | ev); | ||
680 | } | ||
681 | |||
682 | |||
683 | /** | ||
684 | * Fills the "my_elements" hashmap with the initial set of | ||
685 | * (non-deleted) elements from the set of the specification. | ||
686 | * | ||
687 | * @param cls closure with the `struct Operation *` | ||
688 | * @param key current key code for the element | ||
689 | * @param value value in the hash map with the `struct ElementEntry *` | ||
690 | * @return #GNUNET_YES (we should continue to iterate) | ||
691 | */ | ||
692 | static int | ||
693 | initialize_map_unfiltered (void *cls, | ||
694 | const struct GNUNET_HashCode *key, | ||
695 | void *value) | ||
696 | { | ||
697 | struct ElementEntry *ee = value; | ||
698 | struct Operation *op = cls; | ||
699 | |||
700 | if (GNUNET_NO == _GSS_is_element_of_operation (ee, op)) | ||
701 | return GNUNET_YES; /* element not live in operation's generation */ | ||
702 | GNUNET_CRYPTO_hash_xor (&op->state->my_xor, | ||
703 | &ee->element_hash, | ||
704 | &op->state->my_xor); | ||
705 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
706 | "Initial full initialization of my_elements, adding %s:%u\n", | ||
707 | GNUNET_h2s (&ee->element_hash), | ||
708 | ee->element.size); | ||
709 | GNUNET_break (GNUNET_YES == | ||
710 | GNUNET_CONTAINER_multihashmap_put (op->state->my_elements, | ||
711 | &ee->element_hash, | ||
712 | ee, | ||
713 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
714 | return GNUNET_YES; | ||
715 | } | ||
716 | |||
717 | |||
718 | /** | ||
719 | * Send our element count to the peer, in case our element count is | ||
720 | * lower than theirs. | ||
721 | * | ||
722 | * @param op intersection operation | ||
723 | */ | ||
724 | static void | ||
725 | send_element_count (struct Operation *op) | ||
726 | { | ||
727 | struct GNUNET_MQ_Envelope *ev; | ||
728 | struct IntersectionElementInfoMessage *msg; | ||
729 | |||
730 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
731 | "Sending our element count (%u)\n", | ||
732 | op->state->my_element_count); | ||
733 | ev = GNUNET_MQ_msg (msg, | ||
734 | GNUNET_MESSAGE_TYPE_SET_INTERSECTION_P2P_ELEMENT_INFO); | ||
735 | msg->sender_element_count = htonl (op->state->my_element_count); | ||
736 | GNUNET_MQ_send (op->mq, ev); | ||
737 | } | ||
738 | |||
739 | |||
740 | /** | ||
741 | * We go first, initialize our map with all elements and | ||
742 | * send the first Bloom filter. | ||
743 | * | ||
744 | * @param op operation to start exchange for | ||
745 | */ | ||
746 | static void | ||
747 | begin_bf_exchange (struct Operation *op) | ||
748 | { | ||
749 | op->state->phase = PHASE_BF_EXCHANGE; | ||
750 | GNUNET_CONTAINER_multihashmap_iterate (op->set->content->elements, | ||
751 | &initialize_map_unfiltered, | ||
752 | op); | ||
753 | send_bloomfilter (op); | ||
754 | } | ||
755 | |||
756 | |||
757 | /** | ||
758 | * Handle the initial `struct IntersectionElementInfoMessage` from a | ||
759 | * remote peer. | ||
760 | * | ||
761 | * @param cls the intersection operation | ||
762 | * @param mh the header of the message | ||
763 | */ | ||
764 | void | ||
765 | handle_intersection_p2p_element_info (void *cls, | ||
766 | const struct | ||
767 | IntersectionElementInfoMessage *msg) | ||
768 | { | ||
769 | struct Operation *op = cls; | ||
770 | |||
771 | if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation) | ||
772 | { | ||
773 | GNUNET_break_op (0); | ||
774 | fail_intersection_operation (op); | ||
775 | return; | ||
776 | } | ||
777 | op->remote_element_count = ntohl (msg->sender_element_count); | ||
778 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
779 | "Received remote element count (%u), I have %u\n", | ||
780 | op->remote_element_count, | ||
781 | op->state->my_element_count); | ||
782 | if (((PHASE_INITIAL != op->state->phase) && | ||
783 | (PHASE_COUNT_SENT != op->state->phase)) || | ||
784 | (op->state->my_element_count > op->remote_element_count) || | ||
785 | (0 == op->state->my_element_count) || | ||
786 | (0 == op->remote_element_count)) | ||
787 | { | ||
788 | GNUNET_break_op (0); | ||
789 | fail_intersection_operation (op); | ||
790 | return; | ||
791 | } | ||
792 | GNUNET_break (NULL == op->state->remote_bf); | ||
793 | begin_bf_exchange (op); | ||
794 | GNUNET_CADET_receive_done (op->channel); | ||
795 | } | ||
796 | |||
797 | |||
798 | /** | ||
799 | * Process a Bloomfilter once we got all the chunks. | ||
800 | * | ||
801 | * @param op the intersection operation | ||
802 | */ | ||
803 | static void | ||
804 | process_bf (struct Operation *op) | ||
805 | { | ||
806 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
807 | "Received BF in phase %u, foreign count is %u, my element count is %u/%u\n", | ||
808 | op->state->phase, | ||
809 | op->remote_element_count, | ||
810 | op->state->my_element_count, | ||
811 | GNUNET_CONTAINER_multihashmap_size (op->set->content->elements)); | ||
812 | switch (op->state->phase) | ||
813 | { | ||
814 | case PHASE_INITIAL: | ||
815 | GNUNET_break_op (0); | ||
816 | fail_intersection_operation (op); | ||
817 | return; | ||
818 | |||
819 | case PHASE_COUNT_SENT: | ||
820 | /* This is the first BF being sent, build our initial map with | ||
821 | filtering in place */ | ||
822 | op->state->my_element_count = 0; | ||
823 | GNUNET_CONTAINER_multihashmap_iterate (op->set->content->elements, | ||
824 | &filtered_map_initialization, | ||
825 | op); | ||
826 | break; | ||
827 | |||
828 | case PHASE_BF_EXCHANGE: | ||
829 | /* Update our set by reduction */ | ||
830 | GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements, | ||
831 | &iterator_bf_reduce, | ||
832 | op); | ||
833 | break; | ||
834 | |||
835 | case PHASE_MUST_SEND_DONE: | ||
836 | GNUNET_break_op (0); | ||
837 | fail_intersection_operation (op); | ||
838 | return; | ||
839 | |||
840 | case PHASE_DONE_RECEIVED: | ||
841 | GNUNET_break_op (0); | ||
842 | fail_intersection_operation (op); | ||
843 | return; | ||
844 | |||
845 | case PHASE_FINISHED: | ||
846 | GNUNET_break_op (0); | ||
847 | fail_intersection_operation (op); | ||
848 | return; | ||
849 | } | ||
850 | GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf); | ||
851 | op->state->remote_bf = NULL; | ||
852 | |||
853 | if ((0 == op->state->my_element_count) || /* fully disjoint */ | ||
854 | ((op->state->my_element_count == op->remote_element_count) && | ||
855 | (0 == GNUNET_memcmp (&op->state->my_xor, | ||
856 | &op->state->other_xor)))) | ||
857 | { | ||
858 | /* we are done */ | ||
859 | op->state->phase = PHASE_MUST_SEND_DONE; | ||
860 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
861 | "Intersection succeeded, sending DONE to other peer\n"); | ||
862 | GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf); | ||
863 | op->state->local_bf = NULL; | ||
864 | if (GNUNET_SET_RESULT_FULL == op->result_mode) | ||
865 | { | ||
866 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
867 | "Sending full result set (%u elements)\n", | ||
868 | GNUNET_CONTAINER_multihashmap_size (op->state->my_elements)); | ||
869 | op->state->full_result_iter | ||
870 | = GNUNET_CONTAINER_multihashmap_iterator_create ( | ||
871 | op->state->my_elements); | ||
872 | send_remaining_elements (op); | ||
873 | return; | ||
874 | } | ||
875 | send_p2p_done (op); | ||
876 | return; | ||
877 | } | ||
878 | op->state->phase = PHASE_BF_EXCHANGE; | ||
879 | send_bloomfilter (op); | ||
880 | } | ||
881 | |||
882 | |||
883 | /** | ||
884 | * Check an BF message from a remote peer. | ||
885 | * | ||
886 | * @param cls the intersection operation | ||
887 | * @param msg the header of the message | ||
888 | * @return #GNUNET_OK if @a msg is well-formed | ||
889 | */ | ||
890 | int | ||
891 | check_intersection_p2p_bf (void *cls, | ||
892 | const struct BFMessage *msg) | ||
893 | { | ||
894 | struct Operation *op = cls; | ||
895 | |||
896 | if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation) | ||
897 | { | ||
898 | GNUNET_break_op (0); | ||
899 | return GNUNET_SYSERR; | ||
900 | } | ||
901 | return GNUNET_OK; | ||
902 | } | ||
903 | |||
904 | |||
905 | /** | ||
906 | * Handle an BF message from a remote peer. | ||
907 | * | ||
908 | * @param cls the intersection operation | ||
909 | * @param msg the header of the message | ||
910 | */ | ||
911 | void | ||
912 | handle_intersection_p2p_bf (void *cls, | ||
913 | const struct BFMessage *msg) | ||
914 | { | ||
915 | struct Operation *op = cls; | ||
916 | uint32_t bf_size; | ||
917 | uint32_t chunk_size; | ||
918 | uint32_t bf_bits_per_element; | ||
919 | |||
920 | switch (op->state->phase) | ||
921 | { | ||
922 | case PHASE_INITIAL: | ||
923 | GNUNET_break_op (0); | ||
924 | fail_intersection_operation (op); | ||
925 | return; | ||
926 | |||
927 | case PHASE_COUNT_SENT: | ||
928 | case PHASE_BF_EXCHANGE: | ||
929 | bf_size = ntohl (msg->bloomfilter_total_length); | ||
930 | bf_bits_per_element = ntohl (msg->bits_per_element); | ||
931 | chunk_size = htons (msg->header.size) - sizeof(struct BFMessage); | ||
932 | op->state->other_xor = msg->element_xor_hash; | ||
933 | if (bf_size == chunk_size) | ||
934 | { | ||
935 | if (NULL != op->state->bf_data) | ||
936 | { | ||
937 | GNUNET_break_op (0); | ||
938 | fail_intersection_operation (op); | ||
939 | return; | ||
940 | } | ||
941 | /* single part, done here immediately */ | ||
942 | op->state->remote_bf | ||
943 | = GNUNET_CONTAINER_bloomfilter_init ((const char *) &msg[1], | ||
944 | bf_size, | ||
945 | bf_bits_per_element); | ||
946 | op->state->salt = ntohl (msg->sender_mutator); | ||
947 | op->remote_element_count = ntohl (msg->sender_element_count); | ||
948 | process_bf (op); | ||
949 | break; | ||
950 | } | ||
951 | /* multipart chunk */ | ||
952 | if (NULL == op->state->bf_data) | ||
953 | { | ||
954 | /* first chunk, initialize */ | ||
955 | op->state->bf_data = GNUNET_malloc (bf_size); | ||
956 | op->state->bf_data_size = bf_size; | ||
957 | op->state->bf_bits_per_element = bf_bits_per_element; | ||
958 | op->state->bf_data_offset = 0; | ||
959 | op->state->salt = ntohl (msg->sender_mutator); | ||
960 | op->remote_element_count = ntohl (msg->sender_element_count); | ||
961 | } | ||
962 | else | ||
963 | { | ||
964 | /* increment */ | ||
965 | if ((op->state->bf_data_size != bf_size) || | ||
966 | (op->state->bf_bits_per_element != bf_bits_per_element) || | ||
967 | (op->state->bf_data_offset + chunk_size > bf_size) || | ||
968 | (op->state->salt != ntohl (msg->sender_mutator)) || | ||
969 | (op->remote_element_count != ntohl (msg->sender_element_count))) | ||
970 | { | ||
971 | GNUNET_break_op (0); | ||
972 | fail_intersection_operation (op); | ||
973 | return; | ||
974 | } | ||
975 | } | ||
976 | GNUNET_memcpy (&op->state->bf_data[op->state->bf_data_offset], | ||
977 | (const char *) &msg[1], | ||
978 | chunk_size); | ||
979 | op->state->bf_data_offset += chunk_size; | ||
980 | if (op->state->bf_data_offset == bf_size) | ||
981 | { | ||
982 | /* last chunk, run! */ | ||
983 | op->state->remote_bf | ||
984 | = GNUNET_CONTAINER_bloomfilter_init (op->state->bf_data, | ||
985 | bf_size, | ||
986 | bf_bits_per_element); | ||
987 | GNUNET_free (op->state->bf_data); | ||
988 | op->state->bf_data = NULL; | ||
989 | op->state->bf_data_size = 0; | ||
990 | process_bf (op); | ||
991 | } | ||
992 | break; | ||
993 | |||
994 | default: | ||
995 | GNUNET_break_op (0); | ||
996 | fail_intersection_operation (op); | ||
997 | return; | ||
998 | } | ||
999 | GNUNET_CADET_receive_done (op->channel); | ||
1000 | } | ||
1001 | |||
1002 | |||
1003 | /** | ||
1004 | * Remove all elements from our hashmap. | ||
1005 | * | ||
1006 | * @param cls closure with the `struct Operation *` | ||
1007 | * @param key current key code | ||
1008 | * @param value value in the hash map | ||
1009 | * @return #GNUNET_YES (we should continue to iterate) | ||
1010 | */ | ||
1011 | static int | ||
1012 | filter_all (void *cls, | ||
1013 | const struct GNUNET_HashCode *key, | ||
1014 | void *value) | ||
1015 | { | ||
1016 | struct Operation *op = cls; | ||
1017 | struct ElementEntry *ee = value; | ||
1018 | |||
1019 | GNUNET_break (0 < op->state->my_element_count); | ||
1020 | op->state->my_element_count--; | ||
1021 | GNUNET_CRYPTO_hash_xor (&op->state->my_xor, | ||
1022 | &ee->element_hash, | ||
1023 | &op->state->my_xor); | ||
1024 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1025 | "Final reduction of my_elements, removing %s:%u\n", | ||
1026 | GNUNET_h2s (&ee->element_hash), | ||
1027 | ee->element.size); | ||
1028 | GNUNET_assert (GNUNET_YES == | ||
1029 | GNUNET_CONTAINER_multihashmap_remove (op->state->my_elements, | ||
1030 | &ee->element_hash, | ||
1031 | ee)); | ||
1032 | send_client_removed_element (op, | ||
1033 | &ee->element); | ||
1034 | return GNUNET_YES; | ||
1035 | } | ||
1036 | |||
1037 | |||
1038 | /** | ||
1039 | * Handle a done message from a remote peer | ||
1040 | * | ||
1041 | * @param cls the intersection operation | ||
1042 | * @param mh the message | ||
1043 | */ | ||
1044 | void | ||
1045 | handle_intersection_p2p_done (void *cls, | ||
1046 | const struct IntersectionDoneMessage *idm) | ||
1047 | { | ||
1048 | struct Operation *op = cls; | ||
1049 | |||
1050 | if (GNUNET_SET_OPERATION_INTERSECTION != op->set->operation) | ||
1051 | { | ||
1052 | GNUNET_break_op (0); | ||
1053 | fail_intersection_operation (op); | ||
1054 | return; | ||
1055 | } | ||
1056 | if (PHASE_BF_EXCHANGE != op->state->phase) | ||
1057 | { | ||
1058 | /* wrong phase to conclude? FIXME: Or should we allow this | ||
1059 | if the other peer has _initially_ already an empty set? */ | ||
1060 | GNUNET_break_op (0); | ||
1061 | fail_intersection_operation (op); | ||
1062 | return; | ||
1063 | } | ||
1064 | if (0 == ntohl (idm->final_element_count)) | ||
1065 | { | ||
1066 | /* other peer determined empty set is the intersection, | ||
1067 | remove all elements */ | ||
1068 | GNUNET_CONTAINER_multihashmap_iterate (op->state->my_elements, | ||
1069 | &filter_all, | ||
1070 | op); | ||
1071 | } | ||
1072 | if ((op->state->my_element_count != ntohl (idm->final_element_count)) || | ||
1073 | (0 != GNUNET_memcmp (&op->state->my_xor, | ||
1074 | &idm->element_xor_hash))) | ||
1075 | { | ||
1076 | /* Other peer thinks we are done, but we disagree on the result! */ | ||
1077 | GNUNET_break_op (0); | ||
1078 | fail_intersection_operation (op); | ||
1079 | return; | ||
1080 | } | ||
1081 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1082 | "Got IntersectionDoneMessage, have %u elements in intersection\n", | ||
1083 | op->state->my_element_count); | ||
1084 | op->state->phase = PHASE_DONE_RECEIVED; | ||
1085 | GNUNET_CADET_receive_done (op->channel); | ||
1086 | |||
1087 | GNUNET_assert (GNUNET_NO == op->state->client_done_sent); | ||
1088 | if (GNUNET_SET_RESULT_FULL == op->result_mode) | ||
1089 | { | ||
1090 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1091 | "Sending full result set to client (%u elements)\n", | ||
1092 | GNUNET_CONTAINER_multihashmap_size (op->state->my_elements)); | ||
1093 | op->state->full_result_iter | ||
1094 | = GNUNET_CONTAINER_multihashmap_iterator_create (op->state->my_elements); | ||
1095 | send_remaining_elements (op); | ||
1096 | return; | ||
1097 | } | ||
1098 | op->state->phase = PHASE_FINISHED; | ||
1099 | send_client_done_and_destroy (op); | ||
1100 | } | ||
1101 | |||
1102 | |||
1103 | /** | ||
1104 | * Initiate a set intersection operation with a remote peer. | ||
1105 | * | ||
1106 | * @param op operation that is created, should be initialized to | ||
1107 | * begin the evaluation | ||
1108 | * @param opaque_context message to be transmitted to the listener | ||
1109 | * to convince it to accept, may be NULL | ||
1110 | * @return operation-specific state to keep in @a op | ||
1111 | */ | ||
1112 | static struct OperationState * | ||
1113 | intersection_evaluate (struct Operation *op, | ||
1114 | const struct GNUNET_MessageHeader *opaque_context) | ||
1115 | { | ||
1116 | struct OperationState *state; | ||
1117 | struct GNUNET_MQ_Envelope *ev; | ||
1118 | struct OperationRequestMessage *msg; | ||
1119 | |||
1120 | ev = GNUNET_MQ_msg_nested_mh (msg, | ||
1121 | GNUNET_MESSAGE_TYPE_SET_P2P_OPERATION_REQUEST, | ||
1122 | opaque_context); | ||
1123 | if (NULL == ev) | ||
1124 | { | ||
1125 | /* the context message is too large!? */ | ||
1126 | GNUNET_break (0); | ||
1127 | return NULL; | ||
1128 | } | ||
1129 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1130 | "Initiating intersection operation evaluation\n"); | ||
1131 | state = GNUNET_new (struct OperationState); | ||
1132 | /* we started the operation, thus we have to send the operation request */ | ||
1133 | state->phase = PHASE_INITIAL; | ||
1134 | state->my_element_count = op->set->state->current_set_element_count; | ||
1135 | state->my_elements | ||
1136 | = GNUNET_CONTAINER_multihashmap_create (state->my_element_count, | ||
1137 | GNUNET_YES); | ||
1138 | |||
1139 | msg->operation = htonl (GNUNET_SET_OPERATION_INTERSECTION); | ||
1140 | msg->element_count = htonl (state->my_element_count); | ||
1141 | GNUNET_MQ_send (op->mq, | ||
1142 | ev); | ||
1143 | state->phase = PHASE_COUNT_SENT; | ||
1144 | if (NULL != opaque_context) | ||
1145 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1146 | "Sent op request with context message\n"); | ||
1147 | else | ||
1148 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1149 | "Sent op request without context message\n"); | ||
1150 | return state; | ||
1151 | } | ||
1152 | |||
1153 | |||
1154 | /** | ||
1155 | * Accept an intersection operation request from a remote peer. Only | ||
1156 | * initializes the private operation state. | ||
1157 | * | ||
1158 | * @param op operation that will be accepted as an intersection operation | ||
1159 | */ | ||
1160 | static struct OperationState * | ||
1161 | intersection_accept (struct Operation *op) | ||
1162 | { | ||
1163 | struct OperationState *state; | ||
1164 | |||
1165 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1166 | "Accepting set intersection operation\n"); | ||
1167 | state = GNUNET_new (struct OperationState); | ||
1168 | state->phase = PHASE_INITIAL; | ||
1169 | state->my_element_count | ||
1170 | = op->set->state->current_set_element_count; | ||
1171 | state->my_elements | ||
1172 | = GNUNET_CONTAINER_multihashmap_create (GNUNET_MIN (state->my_element_count, | ||
1173 | op->remote_element_count), | ||
1174 | GNUNET_YES); | ||
1175 | op->state = state; | ||
1176 | if (op->remote_element_count < state->my_element_count) | ||
1177 | { | ||
1178 | /* If the other peer (Alice) has fewer elements than us (Bob), | ||
1179 | we just send the count as Alice should send the first BF */ | ||
1180 | send_element_count (op); | ||
1181 | state->phase = PHASE_COUNT_SENT; | ||
1182 | return state; | ||
1183 | } | ||
1184 | /* We have fewer elements, so we start with the BF */ | ||
1185 | begin_bf_exchange (op); | ||
1186 | return state; | ||
1187 | } | ||
1188 | |||
1189 | |||
1190 | /** | ||
1191 | * Destroy the intersection operation. Only things specific to the | ||
1192 | * intersection operation are destroyed. | ||
1193 | * | ||
1194 | * @param op intersection operation to destroy | ||
1195 | */ | ||
1196 | static void | ||
1197 | intersection_op_cancel (struct Operation *op) | ||
1198 | { | ||
1199 | /* check if the op was canceled twice */ | ||
1200 | GNUNET_assert (NULL != op->state); | ||
1201 | if (NULL != op->state->remote_bf) | ||
1202 | { | ||
1203 | GNUNET_CONTAINER_bloomfilter_free (op->state->remote_bf); | ||
1204 | op->state->remote_bf = NULL; | ||
1205 | } | ||
1206 | if (NULL != op->state->local_bf) | ||
1207 | { | ||
1208 | GNUNET_CONTAINER_bloomfilter_free (op->state->local_bf); | ||
1209 | op->state->local_bf = NULL; | ||
1210 | } | ||
1211 | if (NULL != op->state->my_elements) | ||
1212 | { | ||
1213 | GNUNET_CONTAINER_multihashmap_destroy (op->state->my_elements); | ||
1214 | op->state->my_elements = NULL; | ||
1215 | } | ||
1216 | if (NULL != op->state->full_result_iter) | ||
1217 | { | ||
1218 | GNUNET_CONTAINER_multihashmap_iterator_destroy ( | ||
1219 | op->state->full_result_iter); | ||
1220 | op->state->full_result_iter = NULL; | ||
1221 | } | ||
1222 | GNUNET_free (op->state); | ||
1223 | op->state = NULL; | ||
1224 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1225 | "Destroying intersection op state done\n"); | ||
1226 | } | ||
1227 | |||
1228 | |||
1229 | /** | ||
1230 | * Create a new set supporting the intersection operation. | ||
1231 | * | ||
1232 | * @return the newly created set | ||
1233 | */ | ||
1234 | static struct SetState * | ||
1235 | intersection_set_create () | ||
1236 | { | ||
1237 | struct SetState *set_state; | ||
1238 | |||
1239 | GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, | ||
1240 | "Intersection set created\n"); | ||
1241 | set_state = GNUNET_new (struct SetState); | ||
1242 | set_state->current_set_element_count = 0; | ||
1243 | |||
1244 | return set_state; | ||
1245 | } | ||
1246 | |||
1247 | |||
1248 | /** | ||
1249 | * Add the element from the given element message to the set. | ||
1250 | * | ||
1251 | * @param set_state state of the set want to add to | ||
1252 | * @param ee the element to add to the set | ||
1253 | */ | ||
1254 | static void | ||
1255 | intersection_add (struct SetState *set_state, | ||
1256 | struct ElementEntry *ee) | ||
1257 | { | ||
1258 | set_state->current_set_element_count++; | ||
1259 | } | ||
1260 | |||
1261 | |||
1262 | /** | ||
1263 | * Destroy a set that supports the intersection operation | ||
1264 | * | ||
1265 | * @param set_state the set to destroy | ||
1266 | */ | ||
1267 | static void | ||
1268 | intersection_set_destroy (struct SetState *set_state) | ||
1269 | { | ||
1270 | GNUNET_free (set_state); | ||
1271 | } | ||
1272 | |||
1273 | |||
1274 | /** | ||
1275 | * Remove the element given in the element message from the set. | ||
1276 | * | ||
1277 | * @param set_state state of the set to remove from | ||
1278 | * @param element set element to remove | ||
1279 | */ | ||
1280 | static void | ||
1281 | intersection_remove (struct SetState *set_state, | ||
1282 | struct ElementEntry *element) | ||
1283 | { | ||
1284 | GNUNET_assert (0 < set_state->current_set_element_count); | ||
1285 | set_state->current_set_element_count--; | ||
1286 | } | ||
1287 | |||
1288 | |||
1289 | /** | ||
1290 | * Callback for channel death for the intersection operation. | ||
1291 | * | ||
1292 | * @param op operation that lost the channel | ||
1293 | */ | ||
1294 | static void | ||
1295 | intersection_channel_death (struct Operation *op) | ||
1296 | { | ||
1297 | if (GNUNET_YES == op->state->channel_death_expected) | ||
1298 | { | ||
1299 | /* oh goodie, we are done! */ | ||
1300 | send_client_done_and_destroy (op); | ||
1301 | } | ||
1302 | else | ||
1303 | { | ||
1304 | /* sorry, channel went down early, too bad. */ | ||
1305 | _GSS_operation_destroy (op, | ||
1306 | GNUNET_YES); | ||
1307 | } | ||
1308 | } | ||
1309 | |||
1310 | |||
1311 | /** | ||
1312 | * Get the table with implementing functions for set intersection. | ||
1313 | * | ||
1314 | * @return the operation specific VTable | ||
1315 | */ | ||
1316 | const struct SetVT * | ||
1317 | _GSS_intersection_vt () | ||
1318 | { | ||
1319 | static const struct SetVT intersection_vt = { | ||
1320 | .create = &intersection_set_create, | ||
1321 | .add = &intersection_add, | ||
1322 | .remove = &intersection_remove, | ||
1323 | .destroy_set = &intersection_set_destroy, | ||
1324 | .evaluate = &intersection_evaluate, | ||
1325 | .accept = &intersection_accept, | ||
1326 | .cancel = &intersection_op_cancel, | ||
1327 | .channel_death = &intersection_channel_death, | ||
1328 | }; | ||
1329 | |||
1330 | return &intersection_vt; | ||
1331 | } | ||