diff options
Diffstat (limited to 'src/set/gnunet-service-set.h')
-rw-r--r-- | src/set/gnunet-service-set.h | 665 |
1 files changed, 0 insertions, 665 deletions
diff --git a/src/set/gnunet-service-set.h b/src/set/gnunet-service-set.h deleted file mode 100644 index abdec7f08..000000000 --- a/src/set/gnunet-service-set.h +++ /dev/null | |||
@@ -1,665 +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.h | ||
22 | * @brief common components for the implementation the different set operations | ||
23 | * @author Florian Dold | ||
24 | * @author Christian Grothoff | ||
25 | */ | ||
26 | #ifndef GNUNET_SERVICE_SET_H_PRIVATE | ||
27 | #define GNUNET_SERVICE_SET_H_PRIVATE | ||
28 | |||
29 | #include "platform.h" | ||
30 | #include "gnunet_util_lib.h" | ||
31 | #include "gnunet_protocols.h" | ||
32 | #include "gnunet_applications.h" | ||
33 | #include "gnunet_core_service.h" | ||
34 | #include "gnunet_cadet_service.h" | ||
35 | #include "gnunet_set_service.h" | ||
36 | #include "set.h" | ||
37 | |||
38 | |||
39 | /** | ||
40 | * Implementation-specific set state. Used as opaque pointer, and | ||
41 | * specified further in the respective implementation. | ||
42 | */ | ||
43 | struct SetState; | ||
44 | |||
45 | /** | ||
46 | * Implementation-specific set operation. Used as opaque pointer, and | ||
47 | * specified further in the respective implementation. | ||
48 | */ | ||
49 | struct OperationState; | ||
50 | |||
51 | /** | ||
52 | * A set that supports a specific operation with other peers. | ||
53 | */ | ||
54 | struct Set; | ||
55 | |||
56 | /** | ||
57 | * Information about an element element in the set. All elements are | ||
58 | * stored in a hash-table from their hash-code to their 'struct | ||
59 | * Element', so that the remove and add operations are reasonably | ||
60 | * fast. | ||
61 | */ | ||
62 | struct ElementEntry; | ||
63 | |||
64 | /** | ||
65 | * Operation context used to execute a set operation. | ||
66 | */ | ||
67 | struct Operation; | ||
68 | |||
69 | |||
70 | /** | ||
71 | * Signature of functions that create the implementation-specific | ||
72 | * state for a set supporting a specific operation. | ||
73 | * | ||
74 | * @return a set state specific to the supported operation, NULL on error | ||
75 | */ | ||
76 | typedef struct SetState * | ||
77 | (*SetCreateImpl) (void); | ||
78 | |||
79 | |||
80 | /** | ||
81 | * Signature of functions that implement the add/remove functionality | ||
82 | * for a set supporting a specific operation. | ||
83 | * | ||
84 | * @param set implementation-specific set state | ||
85 | * @param ee element message from the client | ||
86 | */ | ||
87 | typedef void | ||
88 | (*SetAddRemoveImpl) (struct SetState *state, | ||
89 | struct ElementEntry *ee); | ||
90 | |||
91 | |||
92 | /** | ||
93 | * Make a copy of a set's internal state. | ||
94 | * | ||
95 | * @param state set state to copy | ||
96 | * @return copy of the internal state | ||
97 | */ | ||
98 | typedef struct SetState * | ||
99 | (*SetCopyStateImpl) (struct SetState *state); | ||
100 | |||
101 | |||
102 | /** | ||
103 | * Signature of functions that implement the destruction of the | ||
104 | * implementation-specific set state. | ||
105 | * | ||
106 | * @param state the set state, contains implementation-specific data | ||
107 | */ | ||
108 | typedef void | ||
109 | (*SetDestroyImpl) (struct SetState *state); | ||
110 | |||
111 | |||
112 | /** | ||
113 | * Signature of functions that implement accepting a set operation. | ||
114 | * | ||
115 | * @param op operation that is created by accepting the operation, | ||
116 | * should be initialized by the implementation | ||
117 | * @return operation-specific state to keep in @a op | ||
118 | */ | ||
119 | typedef struct OperationState * | ||
120 | (*OpAcceptImpl) (struct Operation *op); | ||
121 | |||
122 | |||
123 | /** | ||
124 | * Signature of functions that implement starting the evaluation of | ||
125 | * set operations. | ||
126 | * | ||
127 | * @param op operation that is created, should be initialized to | ||
128 | * begin the evaluation | ||
129 | * @param opaque_context message to be transmitted to the listener | ||
130 | * to convince it to accept, may be NULL | ||
131 | * @return operation-specific state to keep in @a op | ||
132 | */ | ||
133 | typedef struct OperationState * | ||
134 | (*OpEvaluateImpl) (struct Operation *op, | ||
135 | const struct GNUNET_MessageHeader *opaque_context); | ||
136 | |||
137 | /** | ||
138 | * Signature of functions that implement operation cancellation. | ||
139 | * This includes notifying the client about the operation's final | ||
140 | * state. | ||
141 | * | ||
142 | * @param op operation state | ||
143 | */ | ||
144 | typedef void | ||
145 | (*OpCancelImpl) (struct Operation *op); | ||
146 | |||
147 | |||
148 | /** | ||
149 | * Signature of functions called when the CADET channel died. | ||
150 | * | ||
151 | * @param op operation state | ||
152 | */ | ||
153 | typedef void | ||
154 | (*OpChannelDeathImpl) (struct Operation *op); | ||
155 | |||
156 | |||
157 | /** | ||
158 | * Dispatch table for a specific set operation. Every set operation | ||
159 | * has to implement the callback in this struct. | ||
160 | */ | ||
161 | struct SetVT | ||
162 | { | ||
163 | /** | ||
164 | * Callback for the set creation. | ||
165 | */ | ||
166 | SetCreateImpl create; | ||
167 | |||
168 | /** | ||
169 | * Callback for element insertion | ||
170 | */ | ||
171 | SetAddRemoveImpl add; | ||
172 | |||
173 | /** | ||
174 | * Callback for element removal. | ||
175 | */ | ||
176 | SetAddRemoveImpl remove; | ||
177 | |||
178 | /** | ||
179 | * Callback for making a copy of a set's internal state. | ||
180 | */ | ||
181 | SetCopyStateImpl copy_state; | ||
182 | |||
183 | /** | ||
184 | * Callback for destruction of the set state. | ||
185 | */ | ||
186 | SetDestroyImpl destroy_set; | ||
187 | |||
188 | /** | ||
189 | * Callback for accepting a set operation request | ||
190 | */ | ||
191 | OpAcceptImpl accept; | ||
192 | |||
193 | /** | ||
194 | * Callback for starting evaluation with a remote peer. | ||
195 | */ | ||
196 | OpEvaluateImpl evaluate; | ||
197 | |||
198 | /** | ||
199 | * Callback for canceling an operation. | ||
200 | */ | ||
201 | OpCancelImpl cancel; | ||
202 | |||
203 | /** | ||
204 | * Callback called in case the CADET channel died. | ||
205 | */ | ||
206 | OpChannelDeathImpl channel_death; | ||
207 | }; | ||
208 | |||
209 | |||
210 | /** | ||
211 | * MutationEvent gives information about changes | ||
212 | * to an element (removal / addition) in a set content. | ||
213 | */ | ||
214 | struct MutationEvent | ||
215 | { | ||
216 | /** | ||
217 | * First generation affected by this mutation event. | ||
218 | * | ||
219 | * If @a generation is 0, this mutation event is a list | ||
220 | * sentinel element. | ||
221 | */ | ||
222 | unsigned int generation; | ||
223 | |||
224 | /** | ||
225 | * If @a added is #GNUNET_YES, then this is a | ||
226 | * `remove` event, otherwise it is an `add` event. | ||
227 | */ | ||
228 | int added; | ||
229 | }; | ||
230 | |||
231 | |||
232 | /** | ||
233 | * Information about an element element in the set. All elements are | ||
234 | * stored in a hash-table from their hash-code to their `struct | ||
235 | * Element`, so that the remove and add operations are reasonably | ||
236 | * fast. | ||
237 | */ | ||
238 | struct ElementEntry | ||
239 | { | ||
240 | /** | ||
241 | * The actual element. The data for the element | ||
242 | * should be allocated at the end of this struct. | ||
243 | */ | ||
244 | struct GNUNET_SET_Element element; | ||
245 | |||
246 | /** | ||
247 | * Hash of the element. For set union: Will be used to derive the | ||
248 | * different IBF keys for different salts. | ||
249 | */ | ||
250 | struct GNUNET_HashCode element_hash; | ||
251 | |||
252 | /** | ||
253 | * If @a mutations is not NULL, it contains | ||
254 | * a list of mutations, ordered by increasing generation. | ||
255 | * The list is terminated by a sentinel event with `generation` | ||
256 | * set to 0. | ||
257 | * | ||
258 | * If @a mutations is NULL, then this element exists in all generations | ||
259 | * of the respective set content this element belongs to. | ||
260 | */ | ||
261 | struct MutationEvent *mutations; | ||
262 | |||
263 | /** | ||
264 | * Number of elements in the array @a mutations. | ||
265 | */ | ||
266 | unsigned int mutations_size; | ||
267 | |||
268 | /** | ||
269 | * #GNUNET_YES if the element is a remote element, and does not belong | ||
270 | * to the operation's set. | ||
271 | */ | ||
272 | int remote; | ||
273 | }; | ||
274 | |||
275 | |||
276 | /** | ||
277 | * A listener is inhabited by a client, and waits for evaluation | ||
278 | * requests from remote peers. | ||
279 | */ | ||
280 | struct Listener; | ||
281 | |||
282 | |||
283 | /** | ||
284 | * State we keep per client. | ||
285 | */ | ||
286 | struct ClientState | ||
287 | { | ||
288 | /** | ||
289 | * Set, if associated with the client, otherwise NULL. | ||
290 | */ | ||
291 | struct Set *set; | ||
292 | |||
293 | /** | ||
294 | * Listener, if associated with the client, otherwise NULL. | ||
295 | */ | ||
296 | struct Listener *listener; | ||
297 | |||
298 | /** | ||
299 | * Client handle. | ||
300 | */ | ||
301 | struct GNUNET_SERVICE_Client *client; | ||
302 | |||
303 | /** | ||
304 | * Message queue. | ||
305 | */ | ||
306 | struct GNUNET_MQ_Handle *mq; | ||
307 | }; | ||
308 | |||
309 | |||
310 | /** | ||
311 | * Operation context used to execute a set operation. | ||
312 | */ | ||
313 | struct Operation | ||
314 | { | ||
315 | /** | ||
316 | * Kept in a DLL of the listener, if @e listener is non-NULL. | ||
317 | */ | ||
318 | struct Operation *next; | ||
319 | |||
320 | /** | ||
321 | * Kept in a DLL of the listener, if @e listener is non-NULL. | ||
322 | */ | ||
323 | struct Operation *prev; | ||
324 | |||
325 | /** | ||
326 | * Channel to the peer. | ||
327 | */ | ||
328 | struct GNUNET_CADET_Channel *channel; | ||
329 | |||
330 | /** | ||
331 | * Port this operation runs on. | ||
332 | */ | ||
333 | struct Listener *listener; | ||
334 | |||
335 | /** | ||
336 | * Message queue for the channel. | ||
337 | */ | ||
338 | struct GNUNET_MQ_Handle *mq; | ||
339 | |||
340 | /** | ||
341 | * Context message, may be NULL. | ||
342 | */ | ||
343 | struct GNUNET_MessageHeader *context_msg; | ||
344 | |||
345 | /** | ||
346 | * Set associated with the operation, NULL until the spec has been | ||
347 | * associated with a set. | ||
348 | */ | ||
349 | struct Set *set; | ||
350 | |||
351 | /** | ||
352 | * Operation-specific operation state. Note that the exact | ||
353 | * type depends on this being a union or intersection operation | ||
354 | * (and thus on @e vt). | ||
355 | */ | ||
356 | struct OperationState *state; | ||
357 | |||
358 | /** | ||
359 | * The identity of the requesting peer. Needs to | ||
360 | * be stored here as the op spec might not have been created yet. | ||
361 | */ | ||
362 | struct GNUNET_PeerIdentity peer; | ||
363 | |||
364 | /** | ||
365 | * Timeout task, if the incoming peer has not been accepted | ||
366 | * after the timeout, it will be disconnected. | ||
367 | */ | ||
368 | struct GNUNET_SCHEDULER_Task *timeout_task; | ||
369 | |||
370 | /** | ||
371 | * Salt to use for the operation. | ||
372 | */ | ||
373 | uint32_t salt; | ||
374 | |||
375 | /** | ||
376 | * Remote peers element count | ||
377 | */ | ||
378 | uint32_t remote_element_count; | ||
379 | |||
380 | /** | ||
381 | * ID used to identify an operation between service and client | ||
382 | */ | ||
383 | uint32_t client_request_id; | ||
384 | |||
385 | /** | ||
386 | * When are elements sent to the client, and which elements are sent? | ||
387 | */ | ||
388 | enum GNUNET_SET_ResultMode result_mode; | ||
389 | |||
390 | /** | ||
391 | * Always use delta operation instead of sending full sets, | ||
392 | * even it it's less efficient. | ||
393 | */ | ||
394 | int force_delta; | ||
395 | |||
396 | /** | ||
397 | * Always send full sets, even if delta operations would | ||
398 | * be more efficient. | ||
399 | */ | ||
400 | int force_full; | ||
401 | |||
402 | /** | ||
403 | * #GNUNET_YES to fail operations where Byzantine faults | ||
404 | * are suspected | ||
405 | */ | ||
406 | int byzantine; | ||
407 | |||
408 | /** | ||
409 | * Lower bound for the set size, used only when | ||
410 | * byzantine mode is enabled. | ||
411 | */ | ||
412 | int byzantine_lower_bound; | ||
413 | |||
414 | /** | ||
415 | * Unique request id for the request from a remote peer, sent to the | ||
416 | * client, which will accept or reject the request. Set to '0' iff | ||
417 | * the request has not been suggested yet. | ||
418 | */ | ||
419 | uint32_t suggest_id; | ||
420 | |||
421 | /** | ||
422 | * Generation in which the operation handle | ||
423 | * was created. | ||
424 | */ | ||
425 | unsigned int generation_created; | ||
426 | }; | ||
427 | |||
428 | |||
429 | /** | ||
430 | * SetContent stores the actual set elements, which may be shared by | ||
431 | * multiple generations derived from one set. | ||
432 | */ | ||
433 | struct SetContent | ||
434 | { | ||
435 | /** | ||
436 | * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`. | ||
437 | */ | ||
438 | struct GNUNET_CONTAINER_MultiHashMap *elements; | ||
439 | |||
440 | /** | ||
441 | * Mutations requested by the client that we're | ||
442 | * unable to execute right now because we're iterating | ||
443 | * over the underlying hash map of elements. | ||
444 | */ | ||
445 | struct PendingMutation *pending_mutations_head; | ||
446 | |||
447 | /** | ||
448 | * Mutations requested by the client that we're | ||
449 | * unable to execute right now because we're iterating | ||
450 | * over the underlying hash map of elements. | ||
451 | */ | ||
452 | struct PendingMutation *pending_mutations_tail; | ||
453 | |||
454 | /** | ||
455 | * Number of references to the content. | ||
456 | */ | ||
457 | unsigned int refcount; | ||
458 | |||
459 | /** | ||
460 | * FIXME: document! | ||
461 | */ | ||
462 | unsigned int latest_generation; | ||
463 | |||
464 | /** | ||
465 | * Number of concurrently active iterators. | ||
466 | */ | ||
467 | int iterator_count; | ||
468 | }; | ||
469 | |||
470 | |||
471 | struct GenerationRange | ||
472 | { | ||
473 | /** | ||
474 | * First generation that is excluded. | ||
475 | */ | ||
476 | unsigned int start; | ||
477 | |||
478 | /** | ||
479 | * Generation after the last excluded generation. | ||
480 | */ | ||
481 | unsigned int end; | ||
482 | }; | ||
483 | |||
484 | |||
485 | /** | ||
486 | * Information about a mutation to apply to a set. | ||
487 | */ | ||
488 | struct PendingMutation | ||
489 | { | ||
490 | /** | ||
491 | * Mutations are kept in a DLL. | ||
492 | */ | ||
493 | struct PendingMutation *prev; | ||
494 | |||
495 | /** | ||
496 | * Mutations are kept in a DLL. | ||
497 | */ | ||
498 | struct PendingMutation *next; | ||
499 | |||
500 | /** | ||
501 | * Set this mutation is about. | ||
502 | */ | ||
503 | struct Set *set; | ||
504 | |||
505 | /** | ||
506 | * Message that describes the desired mutation. | ||
507 | * May only be a #GNUNET_MESSAGE_TYPE_SET_ADD or | ||
508 | * #GNUNET_MESSAGE_TYPE_SET_REMOVE. | ||
509 | */ | ||
510 | struct GNUNET_SET_ElementMessage *msg; | ||
511 | }; | ||
512 | |||
513 | |||
514 | /** | ||
515 | * A set that supports a specific operation with other peers. | ||
516 | */ | ||
517 | struct Set | ||
518 | { | ||
519 | /** | ||
520 | * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`). | ||
521 | */ | ||
522 | struct Set *next; | ||
523 | |||
524 | /** | ||
525 | * Sets are held in a doubly linked list. | ||
526 | */ | ||
527 | struct Set *prev; | ||
528 | |||
529 | /** | ||
530 | * Client that owns the set. Only one client may own a set, | ||
531 | * and there can only be one set per client. | ||
532 | */ | ||
533 | struct ClientState *cs; | ||
534 | |||
535 | /** | ||
536 | * Content, possibly shared by multiple sets, | ||
537 | * and thus reference counted. | ||
538 | */ | ||
539 | struct SetContent *content; | ||
540 | |||
541 | /** | ||
542 | * Virtual table for this set. Determined by the operation type of | ||
543 | * this set. | ||
544 | * | ||
545 | * Used only for Add/remove of elements and when receiving an incoming | ||
546 | * operation from a remote peer. | ||
547 | */ | ||
548 | const struct SetVT *vt; | ||
549 | |||
550 | /** | ||
551 | * Implementation-specific state. | ||
552 | */ | ||
553 | struct SetState *state; | ||
554 | |||
555 | /** | ||
556 | * Current state of iterating elements for the client. | ||
557 | * NULL if we are not currently iterating. | ||
558 | */ | ||
559 | struct GNUNET_CONTAINER_MultiHashMapIterator *iter; | ||
560 | |||
561 | /** | ||
562 | * Evaluate operations are held in a linked list. | ||
563 | */ | ||
564 | struct Operation *ops_head; | ||
565 | |||
566 | /** | ||
567 | * Evaluate operations are held in a linked list. | ||
568 | */ | ||
569 | struct Operation *ops_tail; | ||
570 | |||
571 | /** | ||
572 | * List of generations we have to exclude, due to lazy copies. | ||
573 | */ | ||
574 | struct GenerationRange *excluded_generations; | ||
575 | |||
576 | /** | ||
577 | * Current generation, that is, number of previously executed | ||
578 | * operations and lazy copies on the underlying set content. | ||
579 | */ | ||
580 | unsigned int current_generation; | ||
581 | |||
582 | /** | ||
583 | * Number of elements in array @a excluded_generations. | ||
584 | */ | ||
585 | unsigned int excluded_generations_size; | ||
586 | |||
587 | /** | ||
588 | * Type of operation supported for this set | ||
589 | */ | ||
590 | enum GNUNET_SET_OperationType operation; | ||
591 | |||
592 | /** | ||
593 | * Generation we're currently iteration over. | ||
594 | */ | ||
595 | unsigned int iter_generation; | ||
596 | |||
597 | /** | ||
598 | * Each @e iter is assigned a unique number, so that the client | ||
599 | * can distinguish iterations. | ||
600 | */ | ||
601 | uint16_t iteration_id; | ||
602 | }; | ||
603 | |||
604 | |||
605 | extern struct GNUNET_STATISTICS_Handle *_GSS_statistics; | ||
606 | |||
607 | |||
608 | /** | ||
609 | * Destroy the given operation. Used for any operation where both | ||
610 | * peers were known and that thus actually had a vt and channel. Must | ||
611 | * not be used for operations where 'listener' is still set and we do | ||
612 | * not know the other peer. | ||
613 | * | ||
614 | * Call the implementation-specific cancel function of the operation. | ||
615 | * Disconnects from the remote peer. Does not disconnect the client, | ||
616 | * as there may be multiple operations per set. | ||
617 | * | ||
618 | * @param op operation to destroy | ||
619 | * @param gc #GNUNET_YES to perform garbage collection on the set | ||
620 | */ | ||
621 | void | ||
622 | _GSS_operation_destroy (struct Operation *op, | ||
623 | int gc); | ||
624 | |||
625 | |||
626 | /** | ||
627 | * This function probably should not exist | ||
628 | * and be replaced by inlining more specific | ||
629 | * logic in the various places where it is called. | ||
630 | */ | ||
631 | void | ||
632 | _GSS_operation_destroy2 (struct Operation *op); | ||
633 | |||
634 | |||
635 | /** | ||
636 | * Get the table with implementing functions for set union. | ||
637 | * | ||
638 | * @return the operation specific VTable | ||
639 | */ | ||
640 | const struct SetVT * | ||
641 | _GSS_union_vt (void); | ||
642 | |||
643 | |||
644 | /** | ||
645 | * Get the table with implementing functions for set intersection. | ||
646 | * | ||
647 | * @return the operation specific VTable | ||
648 | */ | ||
649 | const struct SetVT * | ||
650 | _GSS_intersection_vt (void); | ||
651 | |||
652 | |||
653 | /** | ||
654 | * Is element @a ee part of the set used by @a op? | ||
655 | * | ||
656 | * @param ee element to test | ||
657 | * @param op operation the defines the set and its generation | ||
658 | * @return #GNUNET_YES if the element is in the set, #GNUNET_NO if not | ||
659 | */ | ||
660 | int | ||
661 | _GSS_is_element_of_operation (struct ElementEntry *ee, | ||
662 | struct Operation *op); | ||
663 | |||
664 | |||
665 | #endif | ||