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
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
18 Boston, MA 02110-1301, USA.
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
26 #ifndef GNUNET_SERVICE_SET_H_PRIVATE
27 #define GNUNET_SERVICE_SET_H_PRIVATE
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"
40 * Implementation-specific set state. Used as opaque pointer, and
41 * specified further in the respective implementation.
46 * Implementation-specific set operation. Used as opaque pointer, and
47 * specified further in the respective implementation.
49 struct OperationState;
52 * A set that supports a specific operation with other peers.
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
65 * Operation context used to execute a set operation.
71 * Signature of functions that create the implementation-specific
72 * state for a set supporting a specific operation.
74 * @return a set state specific to the supported operation, NULL on error
76 typedef struct SetState *
77 (*SetCreateImpl) (void);
81 * Signature of functions that implement the add/remove functionality
82 * for a set supporting a specific operation.
84 * @param set implementation-specific set state
85 * @param ee element message from the client
88 (*SetAddRemoveImpl) (struct SetState *state,
89 struct ElementEntry *ee);
93 * Make a copy of a set's internal state.
95 * @param state set state to copy
96 * @return copy of the internal state
98 typedef struct SetState *
99 (*SetCopyStateImpl) (struct SetState *state);
103 * Signature of functions that implement the destruction of the
104 * implementation-specific set state.
106 * @param state the set state, contains implementation-specific data
109 (*SetDestroyImpl) (struct SetState *state);
113 * Signature of functions that implement accepting a set operation.
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
119 typedef struct OperationState *
120 (*OpAcceptImpl) (struct Operation *op);
124 * Signature of functions that implement starting the evaluation of
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 him to accept, may be NULL
131 * @return operation-specific state to keep in @a op
133 typedef struct OperationState *
134 (*OpEvaluateImpl) (struct Operation *op,
135 const struct GNUNET_MessageHeader *opaque_context);
138 * Signature of functions that implement operation cancelation.
139 * This includes notifying the client about the operation's final
142 * @param op operation state
145 (*OpCancelImpl) (struct Operation *op);
149 * Signature of functions called when the CADET channel died.
151 * @param op operation state
154 (*OpChannelDeathImpl) (struct Operation *op);
159 * Dispatch table for a specific set operation. Every set operation
160 * has to implement the callback in this struct.
165 * Callback for the set creation.
167 SetCreateImpl create;
170 * Callback for element insertion
172 SetAddRemoveImpl add;
175 * Callback for element removal.
177 SetAddRemoveImpl remove;
180 * Callback for making a copy of a set's internal state.
182 SetCopyStateImpl copy_state;
185 * Callback for destruction of the set state.
187 SetDestroyImpl destroy_set;
190 * Callback for accepting a set operation request
195 * Callback for starting evaluation with a remote peer.
197 OpEvaluateImpl evaluate;
200 * Callback for canceling an operation.
205 * Callback called in case the CADET channel died.
207 OpChannelDeathImpl channel_death;
213 * MutationEvent gives information about changes
214 * to an element (removal / addition) in a set content.
219 * First generation affected by this mutation event.
221 * If @a generation is 0, this mutation event is a list
224 unsigned int generation;
227 * If @a added is #GNUNET_YES, then this is a
228 * `remove` event, otherwise it is an `add` event.
235 * Information about an element element in the set. All elements are
236 * stored in a hash-table from their hash-code to their `struct
237 * Element`, so that the remove and add operations are reasonably
243 * The actual element. The data for the element
244 * should be allocated at the end of this struct.
246 struct GNUNET_SET_Element element;
249 * Hash of the element. For set union: Will be used to derive the
250 * different IBF keys for different salts.
252 struct GNUNET_HashCode element_hash;
255 * If @a mutations is not NULL, it contains
256 * a list of mutations, ordered by increasing generation.
257 * The list is terminated by a sentinel event with `generation`
260 * If @a mutations is NULL, then this element exists in all generations
261 * of the respective set content this element belongs to.
263 struct MutationEvent *mutations;
266 * Number of elements in the array @a mutations.
268 unsigned int mutations_size;
271 * #GNUNET_YES if the element is a remote element, and does not belong
272 * to the operation's set.
279 * A listener is inhabited by a client, and waits for evaluation
280 * requests from remote peers.
286 * State we keep per client.
291 * Set, if associated with the client, otherwise NULL.
296 * Listener, if associated with the client, otherwise NULL.
298 struct Listener *listener;
303 struct GNUNET_SERVICE_Client *client;
308 struct GNUNET_MQ_Handle *mq;
314 * Operation context used to execute a set operation.
320 * Kept in a DLL of the listener, if @e listener is non-NULL.
322 struct Operation *next;
325 * Kept in a DLL of the listener, if @e listener is non-NULL.
327 struct Operation *prev;
330 * Channel to the peer.
332 struct GNUNET_CADET_Channel *channel;
335 * Port this operation runs on.
337 struct Listener *listener;
340 * Message queue for the channel.
342 struct GNUNET_MQ_Handle *mq;
345 * Context message, may be NULL.
347 struct GNUNET_MessageHeader *context_msg;
350 * Set associated with the operation, NULL until the spec has been
351 * associated with a set.
356 * Operation-specific operation state. Note that the exact
357 * type depends on this being a union or intersection operation
358 * (and thus on @e vt).
360 struct OperationState *state;
363 * The identity of the requesting peer. Needs to
364 * be stored here as the op spec might not have been created yet.
366 struct GNUNET_PeerIdentity peer;
369 * Timeout task, if the incoming peer has not been accepted
370 * after the timeout, it will be disconnected.
372 struct GNUNET_SCHEDULER_Task *timeout_task;
375 * Salt to use for the operation.
380 * Remote peers element count
382 uint32_t remote_element_count;
385 * ID used to identify an operation between service and client
387 uint32_t client_request_id;
390 * When are elements sent to the client, and which elements are sent?
392 enum GNUNET_SET_ResultMode result_mode;
395 * Always use delta operation instead of sending full sets,
396 * even it it's less efficient.
401 * Always send full sets, even if delta operations would
407 * #GNUNET_YES to fail operations where Byzantine faults
413 * Lower bound for the set size, used only when
414 * byzantine mode is enabled.
416 int byzantine_lower_bound;
419 * Unique request id for the request from a remote peer, sent to the
420 * client, which will accept or reject the request. Set to '0' iff
421 * the request has not been suggested yet.
426 * Generation in which the operation handle
429 unsigned int generation_created;
435 * SetContent stores the actual set elements, which may be shared by
436 * multiple generations derived from one set.
442 * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
444 struct GNUNET_CONTAINER_MultiHashMap *elements;
447 * Mutations requested by the client that we're
448 * unable to execute right now because we're iterating
449 * over the underlying hash map of elements.
451 struct PendingMutation *pending_mutations_head;
454 * Mutations requested by the client that we're
455 * unable to execute right now because we're iterating
456 * over the underlying hash map of elements.
458 struct PendingMutation *pending_mutations_tail;
461 * Number of references to the content.
463 unsigned int refcount;
468 unsigned int latest_generation;
471 * Number of concurrently active iterators.
477 struct GenerationRange
480 * First generation that is excluded.
485 * Generation after the last excluded generation.
492 * Information about a mutation to apply to a set.
494 struct PendingMutation
497 * Mutations are kept in a DLL.
499 struct PendingMutation *prev;
502 * Mutations are kept in a DLL.
504 struct PendingMutation *next;
507 * Set this mutation is about.
512 * Message that describes the desired mutation.
513 * May only be a #GNUNET_MESSAGE_TYPE_SET_ADD or
514 * #GNUNET_MESSAGE_TYPE_SET_REMOVE.
516 struct GNUNET_SET_ElementMessage *msg;
521 * A set that supports a specific operation with other peers.
527 * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`).
532 * Sets are held in a doubly linked list.
537 * Client that owns the set. Only one client may own a set,
538 * and there can only be one set per client.
540 struct ClientState *cs;
543 * Content, possibly shared by multiple sets,
544 * and thus reference counted.
546 struct SetContent *content;
549 * Virtual table for this set. Determined by the operation type of
552 * Used only for Add/remove of elements and when receiving an incoming
553 * operation from a remote peer.
555 const struct SetVT *vt;
558 * Implementation-specific state.
560 struct SetState *state;
563 * Current state of iterating elements for the client.
564 * NULL if we are not currently iterating.
566 struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
569 * Evaluate operations are held in a linked list.
571 struct Operation *ops_head;
574 * Evaluate operations are held in a linked list.
576 struct Operation *ops_tail;
579 * List of generations we have to exclude, due to lazy copies.
581 struct GenerationRange *excluded_generations;
584 * Current generation, that is, number of previously executed
585 * operations and lazy copies on the underlying set content.
587 unsigned int current_generation;
590 * Number of elements in array @a excluded_generations.
592 unsigned int excluded_generations_size;
595 * Type of operation supported for this set
597 enum GNUNET_SET_OperationType operation;
600 * Generation we're currently iteration over.
602 unsigned int iter_generation;
605 * Each @e iter is assigned a unique number, so that the client
606 * can distinguish iterations.
608 uint16_t iteration_id;
613 extern struct GNUNET_STATISTICS_Handle *_GSS_statistics;
617 * Destroy the given operation. Used for any operation where both
618 * peers were known and that thus actually had a vt and channel. Must
619 * not be used for operations where 'listener' is still set and we do
620 * not know the other peer.
622 * Call the implementation-specific cancel function of the operation.
623 * Disconnects from the remote peer. Does not disconnect the client,
624 * as there may be multiple operations per set.
626 * @param op operation to destroy
627 * @param gc #GNUNET_YES to perform garbage collection on the set
630 _GSS_operation_destroy (struct Operation *op,
635 * Get the table with implementing functions for set union.
637 * @return the operation specific VTable
640 _GSS_union_vt (void);
644 * Get the table with implementing functions for set intersection.
646 * @return the operation specific VTable
649 _GSS_intersection_vt (void);
653 * Is element @a ee part of the set used by @a op?
655 * @param ee element to test
656 * @param op operation the defines the set and its generation
657 * @return #GNUNET_YES if the element is in the set, #GNUNET_NO if not
660 _GSS_is_element_of_operation (struct ElementEntry *ee,
661 struct Operation *op);