2 This file is part of GNUnet
3 Copyright (C) 2013-2017 GNUnet e.V.
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.
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.
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/>.
19 * @file set/gnunet-service-set.h
20 * @brief common components for the implementation the different set operations
21 * @author Florian Dold
22 * @author Christian Grothoff
24 #ifndef GNUNET_SERVICE_SET_H_PRIVATE
25 #define GNUNET_SERVICE_SET_H_PRIVATE
28 #include "gnunet_util_lib.h"
29 #include "gnunet_protocols.h"
30 #include "gnunet_applications.h"
31 #include "gnunet_core_service.h"
32 #include "gnunet_cadet_service.h"
33 #include "gnunet_set_service.h"
38 * Implementation-specific set state. Used as opaque pointer, and
39 * specified further in the respective implementation.
44 * Implementation-specific set operation. Used as opaque pointer, and
45 * specified further in the respective implementation.
47 struct OperationState;
50 * A set that supports a specific operation with other peers.
55 * Information about an element element in the set. All elements are
56 * stored in a hash-table from their hash-code to their 'struct
57 * Element', so that the remove and add operations are reasonably
63 * Operation context used to execute a set operation.
69 * Signature of functions that create the implementation-specific
70 * state for a set supporting a specific operation.
72 * @return a set state specific to the supported operation, NULL on error
74 typedef struct SetState *
75 (*SetCreateImpl) (void);
79 * Signature of functions that implement the add/remove functionality
80 * for a set supporting a specific operation.
82 * @param set implementation-specific set state
83 * @param ee element message from the client
86 (*SetAddRemoveImpl) (struct SetState *state,
87 struct ElementEntry *ee);
91 * Make a copy of a set's internal state.
93 * @param state set state to copy
94 * @return copy of the internal state
96 typedef struct SetState *
97 (*SetCopyStateImpl) (struct SetState *state);
101 * Signature of functions that implement the destruction of the
102 * implementation-specific set state.
104 * @param state the set state, contains implementation-specific data
107 (*SetDestroyImpl) (struct SetState *state);
111 * Signature of functions that implement accepting a set operation.
113 * @param op operation that is created by accepting the operation,
114 * should be initialized by the implementation
115 * @return operation-specific state to keep in @a op
117 typedef struct OperationState *
118 (*OpAcceptImpl) (struct Operation *op);
122 * Signature of functions that implement starting the evaluation of
125 * @param op operation that is created, should be initialized to
126 * begin the evaluation
127 * @param opaque_context message to be transmitted to the listener
128 * to convince him to accept, may be NULL
129 * @return operation-specific state to keep in @a op
131 typedef struct OperationState *
132 (*OpEvaluateImpl) (struct Operation *op,
133 const struct GNUNET_MessageHeader *opaque_context);
136 * Signature of functions that implement operation cancelation.
137 * This includes notifying the client about the operation's final
140 * @param op operation state
143 (*OpCancelImpl) (struct Operation *op);
147 * Signature of functions called when the CADET channel died.
149 * @param op operation state
152 (*OpChannelDeathImpl) (struct Operation *op);
157 * Dispatch table for a specific set operation. Every set operation
158 * has to implement the callback in this struct.
163 * Callback for the set creation.
165 SetCreateImpl create;
168 * Callback for element insertion
170 SetAddRemoveImpl add;
173 * Callback for element removal.
175 SetAddRemoveImpl remove;
178 * Callback for making a copy of a set's internal state.
180 SetCopyStateImpl copy_state;
183 * Callback for destruction of the set state.
185 SetDestroyImpl destroy_set;
188 * Callback for accepting a set operation request
193 * Callback for starting evaluation with a remote peer.
195 OpEvaluateImpl evaluate;
198 * Callback for canceling an operation.
203 * Callback called in case the CADET channel died.
205 OpChannelDeathImpl channel_death;
211 * MutationEvent gives information about changes
212 * to an element (removal / addition) in a set content.
217 * First generation affected by this mutation event.
219 * If @a generation is 0, this mutation event is a list
222 unsigned int generation;
225 * If @a added is #GNUNET_YES, then this is a
226 * `remove` event, otherwise it is an `add` event.
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
241 * The actual element. The data for the element
242 * should be allocated at the end of this struct.
244 struct GNUNET_SET_Element element;
247 * Hash of the element. For set union: Will be used to derive the
248 * different IBF keys for different salts.
250 struct GNUNET_HashCode element_hash;
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`
258 * If @a mutations is NULL, then this element exists in all generations
259 * of the respective set content this element belongs to.
261 struct MutationEvent *mutations;
264 * Number of elements in the array @a mutations.
266 unsigned int mutations_size;
269 * #GNUNET_YES if the element is a remote element, and does not belong
270 * to the operation's set.
277 * A listener is inhabited by a client, and waits for evaluation
278 * requests from remote peers.
284 * State we keep per client.
289 * Set, if associated with the client, otherwise NULL.
294 * Listener, if associated with the client, otherwise NULL.
296 struct Listener *listener;
301 struct GNUNET_SERVICE_Client *client;
306 struct GNUNET_MQ_Handle *mq;
312 * Operation context used to execute a set operation.
318 * Kept in a DLL of the listener, if @e listener is non-NULL.
320 struct Operation *next;
323 * Kept in a DLL of the listener, if @e listener is non-NULL.
325 struct Operation *prev;
328 * Channel to the peer.
330 struct GNUNET_CADET_Channel *channel;
333 * Port this operation runs on.
335 struct Listener *listener;
338 * Message queue for the channel.
340 struct GNUNET_MQ_Handle *mq;
343 * Context message, may be NULL.
345 struct GNUNET_MessageHeader *context_msg;
348 * Set associated with the operation, NULL until the spec has been
349 * associated with a set.
354 * Operation-specific operation state. Note that the exact
355 * type depends on this being a union or intersection operation
356 * (and thus on @e vt).
358 struct OperationState *state;
361 * The identity of the requesting peer. Needs to
362 * be stored here as the op spec might not have been created yet.
364 struct GNUNET_PeerIdentity peer;
367 * Timeout task, if the incoming peer has not been accepted
368 * after the timeout, it will be disconnected.
370 struct GNUNET_SCHEDULER_Task *timeout_task;
373 * Salt to use for the operation.
378 * Remote peers element count
380 uint32_t remote_element_count;
383 * ID used to identify an operation between service and client
385 uint32_t client_request_id;
388 * When are elements sent to the client, and which elements are sent?
390 enum GNUNET_SET_ResultMode result_mode;
393 * Always use delta operation instead of sending full sets,
394 * even it it's less efficient.
399 * Always send full sets, even if delta operations would
405 * #GNUNET_YES to fail operations where Byzantine faults
411 * Lower bound for the set size, used only when
412 * byzantine mode is enabled.
414 int byzantine_lower_bound;
417 * Unique request id for the request from a remote peer, sent to the
418 * client, which will accept or reject the request. Set to '0' iff
419 * the request has not been suggested yet.
424 * Generation in which the operation handle
427 unsigned int generation_created;
433 * SetContent stores the actual set elements, which may be shared by
434 * multiple generations derived from one set.
440 * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
442 struct GNUNET_CONTAINER_MultiHashMap *elements;
445 * Mutations requested by the client that we're
446 * unable to execute right now because we're iterating
447 * over the underlying hash map of elements.
449 struct PendingMutation *pending_mutations_head;
452 * Mutations requested by the client that we're
453 * unable to execute right now because we're iterating
454 * over the underlying hash map of elements.
456 struct PendingMutation *pending_mutations_tail;
459 * Number of references to the content.
461 unsigned int refcount;
466 unsigned int latest_generation;
469 * Number of concurrently active iterators.
475 struct GenerationRange
478 * First generation that is excluded.
483 * Generation after the last excluded generation.
490 * Information about a mutation to apply to a set.
492 struct PendingMutation
495 * Mutations are kept in a DLL.
497 struct PendingMutation *prev;
500 * Mutations are kept in a DLL.
502 struct PendingMutation *next;
505 * Set this mutation is about.
510 * Message that describes the desired mutation.
511 * May only be a #GNUNET_MESSAGE_TYPE_SET_ADD or
512 * #GNUNET_MESSAGE_TYPE_SET_REMOVE.
514 struct GNUNET_SET_ElementMessage *msg;
519 * A set that supports a specific operation with other peers.
525 * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`).
530 * Sets are held in a doubly linked list.
535 * Client that owns the set. Only one client may own a set,
536 * and there can only be one set per client.
538 struct ClientState *cs;
541 * Content, possibly shared by multiple sets,
542 * and thus reference counted.
544 struct SetContent *content;
547 * Virtual table for this set. Determined by the operation type of
550 * Used only for Add/remove of elements and when receiving an incoming
551 * operation from a remote peer.
553 const struct SetVT *vt;
556 * Implementation-specific state.
558 struct SetState *state;
561 * Current state of iterating elements for the client.
562 * NULL if we are not currently iterating.
564 struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
567 * Evaluate operations are held in a linked list.
569 struct Operation *ops_head;
572 * Evaluate operations are held in a linked list.
574 struct Operation *ops_tail;
577 * List of generations we have to exclude, due to lazy copies.
579 struct GenerationRange *excluded_generations;
582 * Current generation, that is, number of previously executed
583 * operations and lazy copies on the underlying set content.
585 unsigned int current_generation;
588 * Number of elements in array @a excluded_generations.
590 unsigned int excluded_generations_size;
593 * Type of operation supported for this set
595 enum GNUNET_SET_OperationType operation;
598 * Generation we're currently iteration over.
600 unsigned int iter_generation;
603 * Each @e iter is assigned a unique number, so that the client
604 * can distinguish iterations.
606 uint16_t iteration_id;
611 extern struct GNUNET_STATISTICS_Handle *_GSS_statistics;
615 * Destroy the given operation. Used for any operation where both
616 * peers were known and that thus actually had a vt and channel. Must
617 * not be used for operations where 'listener' is still set and we do
618 * not know the other peer.
620 * Call the implementation-specific cancel function of the operation.
621 * Disconnects from the remote peer. Does not disconnect the client,
622 * as there may be multiple operations per set.
624 * @param op operation to destroy
625 * @param gc #GNUNET_YES to perform garbage collection on the set
628 _GSS_operation_destroy (struct Operation *op,
633 * Get the table with implementing functions for set union.
635 * @return the operation specific VTable
638 _GSS_union_vt (void);
642 * Get the table with implementing functions for set intersection.
644 * @return the operation specific VTable
647 _GSS_intersection_vt (void);
651 * Is element @a ee part of the set used by @a op?
653 * @param ee element to test
654 * @param op operation the defines the set and its generation
655 * @return #GNUNET_YES if the element is in the set, #GNUNET_NO if not
658 _GSS_is_element_of_operation (struct ElementEntry *ee,
659 struct Operation *op);