aboutsummaryrefslogtreecommitdiff
path: root/src/set/gnunet-service-set.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/set/gnunet-service-set.h')
-rw-r--r--src/set/gnunet-service-set.h665
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 */
43struct SetState;
44
45/**
46 * Implementation-specific set operation. Used as opaque pointer, and
47 * specified further in the respective implementation.
48 */
49struct OperationState;
50
51/**
52 * A set that supports a specific operation with other peers.
53 */
54struct 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 */
62struct ElementEntry;
63
64/**
65 * Operation context used to execute a set operation.
66 */
67struct 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 */
76typedef 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 */
87typedef 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 */
98typedef 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 */
108typedef 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 */
119typedef 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 */
133typedef 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 */
144typedef 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 */
153typedef 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 */
161struct 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 */
214struct 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 */
238struct 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 */
280struct Listener;
281
282
283/**
284 * State we keep per client.
285 */
286struct 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 */
313struct 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 */
433struct 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
471struct 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 */
488struct 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 */
517struct 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
605extern 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 */
621void
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 */
631void
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 */
640const 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 */
649const 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 */
660int
661_GSS_is_element_of_operation (struct ElementEntry *ee,
662 struct Operation *op);
663
664
665#endif