/*
This file is part of GNUnet
- (C) 2013 Christian Grothoff (and other contributing authors)
+ Copyright (C) 2013-2017 GNUnet e.V.
GNUnet is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published
- by the Free Software Foundation; either version 2, or (at your
+ by the Free Software Foundation; either version 3, or (at your
option) any later version.
GNUnet is distributed in the hope that it will be useful, but
You should have received a copy of the GNU General Public License
along with GNUnet; see the file COPYING. If not, write to the
- Free Software Foundation, Inc., 59 Temple Place - Suite 330,
- Boston, MA 02111-1307, USA.
+ Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
+ Boston, MA 02110-1301, USA.
*/
-
/**
- * @brief common stuff for the set service
+ * @file set/gnunet-service-set.h
+ * @brief common components for the implementation the different set operations
+ * @author Florian Dold
+ * @author Christian Grothoff
*/
-
#ifndef GNUNET_SERVICE_SET_H_PRIVATE
#define GNUNET_SERVICE_SET_H_PRIVATE
#include "platform.h"
-#include "gnunet_common.h"
+#include "gnunet_util_lib.h"
#include "gnunet_protocols.h"
#include "gnunet_applications.h"
-#include "gnunet_util_lib.h"
#include "gnunet_core_service.h"
-#include "gnunet_stream_lib.h"
+#include "gnunet_cadet_service.h"
#include "gnunet_set_service.h"
#include "set.h"
-#include "mq.h"
-/* FIXME: cfuchs */
-struct IntersectionState;
+/**
+ * Implementation-specific set state. Used as opaque pointer, and
+ * specified further in the respective implementation.
+ */
+struct SetState;
+/**
+ * Implementation-specific set operation. Used as opaque pointer, and
+ * specified further in the respective implementation.
+ */
+struct OperationState;
/**
- * Extra state required for set union.
+ * A set that supports a specific operation with other peers.
*/
-struct UnionState;
+struct Set;
+/**
+ * Information about an element element in the set. All elements are
+ * stored in a hash-table from their hash-code to their 'struct
+ * Element', so that the remove and add operations are reasonably
+ * fast.
+ */
+struct ElementEntry;
/**
- * A set that supports a specific operation
- * with other peers.
+ * Operation context used to execute a set operation.
*/
-struct Set
+struct Operation;
+
+
+/**
+ * Signature of functions that create the implementation-specific
+ * state for a set supporting a specific operation.
+ *
+ * @return a set state specific to the supported operation, NULL on error
+ */
+typedef struct SetState *
+(*SetCreateImpl) (void);
+
+
+/**
+ * Signature of functions that implement the add/remove functionality
+ * for a set supporting a specific operation.
+ *
+ * @param set implementation-specific set state
+ * @param ee element message from the client
+ */
+typedef void
+(*SetAddRemoveImpl) (struct SetState *state,
+ struct ElementEntry *ee);
+
+
+/**
+ * Make a copy of a set's internal state.
+ *
+ * @param state set state to copy
+ * @return copy of the internal state
+ */
+typedef struct SetState *
+(*SetCopyStateImpl) (struct SetState *state);
+
+
+/**
+ * Signature of functions that implement the destruction of the
+ * implementation-specific set state.
+ *
+ * @param state the set state, contains implementation-specific data
+ */
+typedef void
+(*SetDestroyImpl) (struct SetState *state);
+
+
+/**
+ * Signature of functions that implement accepting a set operation.
+ *
+ * @param op operation that is created by accepting the operation,
+ * should be initialized by the implementation
+ * @return operation-specific state to keep in @a op
+ */
+typedef struct OperationState *
+(*OpAcceptImpl) (struct Operation *op);
+
+
+/**
+ * Signature of functions that implement starting the evaluation of
+ * set operations.
+ *
+ * @param op operation that is created, should be initialized to
+ * begin the evaluation
+ * @param opaque_context message to be transmitted to the listener
+ * to convince him to accept, may be NULL
+ * @return operation-specific state to keep in @a op
+ */
+typedef struct OperationState *
+(*OpEvaluateImpl) (struct Operation *op,
+ const struct GNUNET_MessageHeader *opaque_context);
+
+/**
+ * Signature of functions that implement operation cancelation.
+ * This includes notifying the client about the operation's final
+ * state.
+ *
+ * @param op operation state
+ */
+typedef void
+(*OpCancelImpl) (struct Operation *op);
+
+
+/**
+ * Signature of functions called when the CADET channel died.
+ *
+ * @param op operation state
+ */
+typedef void
+(*OpChannelDeathImpl) (struct Operation *op);
+
+
+
+/**
+ * Dispatch table for a specific set operation. Every set operation
+ * has to implement the callback in this struct.
+ */
+struct SetVT
{
/**
- * Client that owns the set.
- * Only one client may own a set.
+ * Callback for the set creation.
*/
- struct GNUNET_SERVER_Client *client;
+ SetCreateImpl create;
/**
- * Message queue for the client
+ * Callback for element insertion
*/
- struct GNUNET_MQ_MessageQueue *client_mq;
+ SetAddRemoveImpl add;
/**
- * Type of operation supported for this set
+ * Callback for element removal.
*/
- uint32_t operation;
+ SetAddRemoveImpl remove;
/**
- * Sets are held in a doubly linked list.
+ * Callback for making a copy of a set's internal state.
*/
- struct Set *next;
+ SetCopyStateImpl copy_state;
/**
- * Sets are held in a doubly linked list.
+ * Callback for destruction of the set state.
*/
- struct Set *prev;
+ SetDestroyImpl destroy_set;
+
+ /**
+ * Callback for accepting a set operation request
+ */
+ OpAcceptImpl accept;
+
+ /**
+ * Callback for starting evaluation with a remote peer.
+ */
+ OpEvaluateImpl evaluate;
/**
- * Appropriate state for each type of
- * operation.
+ * Callback for canceling an operation.
*/
- union {
- struct IntersectionState *i;
- struct UnionState *u;
- } extra;
+ OpCancelImpl cancel;
+
+ /**
+ * Callback called in case the CADET channel died.
+ */
+ OpChannelDeathImpl channel_death;
+
};
/**
- * State for an evaluate operation for a set that
- * supports set union.
+ * MutationEvent gives information about changes
+ * to an element (removal / addition) in a set content.
*/
-struct UnionEvaluateOperation;
+struct MutationEvent
+{
+ /**
+ * First generation affected by this mutation event.
+ *
+ * If @a generation is 0, this mutation event is a list
+ * sentinel element.
+ */
+ unsigned int generation;
+
+ /**
+ * If @a added is #GNUNET_YES, then this is a
+ * `remove` event, otherwise it is an `add` event.
+ */
+ int added;
+};
-/* FIXME: cfuchs */
-struct IntersectionEvaluateOperation
+/**
+ * Information about an element element in the set. All elements are
+ * stored in a hash-table from their hash-code to their `struct
+ * Element`, so that the remove and add operations are reasonably
+ * fast.
+ */
+struct ElementEntry
{
- /* FIXME: cfuchs */
+ /**
+ * The actual element. The data for the element
+ * should be allocated at the end of this struct.
+ */
+ struct GNUNET_SET_Element element;
+
+ /**
+ * Hash of the element. For set union: Will be used to derive the
+ * different IBF keys for different salts.
+ */
+ struct GNUNET_HashCode element_hash;
+
+ /**
+ * If @a mutations is not NULL, it contains
+ * a list of mutations, ordered by increasing generation.
+ * The list is terminated by a sentinel event with `generation`
+ * set to 0.
+ *
+ * If @a mutations is NULL, then this element exists in all generations
+ * of the respective set content this element belongs to.
+ */
+ struct MutationEvent *mutations;
+
+ /**
+ * Number of elements in the array @a mutations.
+ */
+ unsigned int mutations_size;
+
+ /**
+ * #GNUNET_YES if the element is a remote element, and does not belong
+ * to the operation's set.
+ */
+ int remote;
};
/**
- * State of evaluation a set operation with
- * another peer
+ * A listener is inhabited by a client, and waits for evaluation
+ * requests from remote peers.
+ */
+struct Listener;
+
+
+/**
+ * State we keep per client.
*/
-struct EvaluateOperation
+struct ClientState
{
/**
- * Local set the operation is evaluated on
+ * Set, if associated with the client, otherwise NULL.
*/
struct Set *set;
/**
- * Peer with the remote set
+ * Listener, if associated with the client, otherwise NULL.
*/
- struct GNUNET_PeerIdentity peer;
+ struct Listener *listener;
+
+ /**
+ * Client handle.
+ */
+ struct GNUNET_SERVICE_Client *client;
/**
- * Application-specific identifier
+ * Message queue.
*/
- struct GNUNET_HashCode app_id;
+ struct GNUNET_MQ_Handle *mq;
+
+};
+
+
+/**
+ * Operation context used to execute a set operation.
+ */
+struct Operation
+{
/**
- * Context message, given to us
- * by the client, may be NULL.
+ * Kept in a DLL of the listener, if @e listener is non-NULL.
+ */
+ struct Operation *next;
+
+ /**
+ * Kept in a DLL of the listener, if @e listener is non-NULL.
+ */
+ struct Operation *prev;
+
+ /**
+ * Channel to the peer.
+ */
+ struct GNUNET_CADET_Channel *channel;
+
+ /**
+ * Port this operation runs on.
+ */
+ struct Listener *listener;
+
+ /**
+ * Message queue for the channel.
+ */
+ struct GNUNET_MQ_Handle *mq;
+
+ /**
+ * Context message, may be NULL.
*/
struct GNUNET_MessageHeader *context_msg;
/**
- * Stream socket connected to the other peer
+ * Set associated with the operation, NULL until the spec has been
+ * associated with a set.
*/
- struct GNUNET_STREAM_Socket *socket;
+ struct Set *set;
/**
- * Message queue for the peer on the other
- * end
+ * Operation-specific operation state. Note that the exact
+ * type depends on this being a union or intersection operation
+ * (and thus on @e vt).
*/
- struct GNUNET_MQ_MessageQueue *mq;
+ struct OperationState *state;
/**
- * Type of this operation
+ * The identity of the requesting peer. Needs to
+ * be stored here as the op spec might not have been created yet.
*/
- enum GNUNET_SET_OperationType operation;
+ struct GNUNET_PeerIdentity peer;
+
+ /**
+ * Timeout task, if the incoming peer has not been accepted
+ * after the timeout, it will be disconnected.
+ */
+ struct GNUNET_SCHEDULER_Task *timeout_task;
+
+ /**
+ * Salt to use for the operation.
+ */
+ uint32_t salt;
+
+ /**
+ * Remote peers element count
+ */
+ uint32_t remote_element_count;
+
+ /**
+ * ID used to identify an operation between service and client
+ */
+ uint32_t client_request_id;
+
+ /**
+ * When are elements sent to the client, and which elements are sent?
+ */
+ enum GNUNET_SET_ResultMode result_mode;
+
+ /**
+ * Always use delta operation instead of sending full sets,
+ * even it it's less efficient.
+ */
+ int force_delta;
/**
- * GNUNET_YES if we started the operation,
- * GNUNET_NO if the other peer started it.
+ * Always send full sets, even if delta operations would
+ * be more efficient.
*/
- int is_outgoing;
+ int force_full;
/**
- * Request id, so we can use one client handle
- * for multiple operations
+ * #GNUNET_YES to fail operations where Byzantine faults
+ * are suspected
*/
- uint32_t request_id;
+ int byzantine;
+
+ /**
+ * Lower bound for the set size, used only when
+ * byzantine mode is enabled.
+ */
+ int byzantine_lower_bound;
+
+ /**
+ * Unique request id for the request from a remote peer, sent to the
+ * client, which will accept or reject the request. Set to '0' iff
+ * the request has not been suggested yet.
+ */
+ uint32_t suggest_id;
+
+ /**
+ * Generation in which the operation handle
+ * was created.
+ */
+ unsigned int generation_created;
- union {
- struct UnionEvaluateOperation *u;
- struct IntersectionEvaluateOperation *i;
- } extra;
};
-struct Listener
+/**
+ * SetContent stores the actual set elements, which may be shared by
+ * multiple generations derived from one set.
+ */
+struct SetContent
{
+
/**
- * Listeners are held in a doubly linked list.
+ * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
*/
- struct Listener *next;
+ struct GNUNET_CONTAINER_MultiHashMap *elements;
/**
- * Listeners are held in a doubly linked list.
+ * Mutations requested by the client that we're
+ * unable to execute right now because we're iterating
+ * over the underlying hash map of elements.
*/
- struct Listener *prev;
+ struct PendingMutation *pending_mutations_head;
/**
- * Client that owns the set.
- * Only one client may own a set.
+ * Mutations requested by the client that we're
+ * unable to execute right now because we're iterating
+ * over the underlying hash map of elements.
*/
- struct GNUNET_SERVER_Client *client;
+ struct PendingMutation *pending_mutations_tail;
/**
- * Message queue for the client
+ * Number of references to the content.
*/
- struct GNUNET_MQ_MessageQueue *client_mq;
+ unsigned int refcount;
/**
- * Type of operation supported for this set
+ * FIXME: document!
*/
- enum GNUNET_SET_OperationType operation;
+ unsigned int latest_generation;
/**
- * Application id of intereset for this listener.
+ * Number of concurrently active iterators.
*/
- struct GNUNET_HashCode app_id;
+ int iterator_count;
+};
+
+
+struct GenerationRange
+{
+ /**
+ * First generation that is excluded.
+ */
+ unsigned int start;
+
+ /**
+ * Generation after the last excluded generation.
+ */
+ unsigned int end;
};
/**
- * Peer that has connected to us, but is not yet evaluating a set operation.
- * Once the peer has sent a request, and the client has
- * accepted or rejected it, this information will be deleted.
+ * Information about a mutation to apply to a set.
*/
-struct Incoming
+struct PendingMutation
{
/**
- * Incoming peers are held in a linked list
+ * Mutations are kept in a DLL.
*/
- struct Incoming *next;
+ struct PendingMutation *prev;
/**
- * Incoming peers are held in a linked list
+ * Mutations are kept in a DLL.
*/
- struct Incoming *prev;
+ struct PendingMutation *next;
/**
- * Identity of the peer that connected to us
+ * Set this mutation is about.
*/
- struct GNUNET_PeerIdentity peer;
+ struct Set *set;
+
+ /**
+ * Message that describes the desired mutation.
+ * May only be a #GNUNET_MESSAGE_TYPE_SET_ADD or
+ * #GNUNET_MESSAGE_TYPE_SET_REMOVE.
+ */
+ struct GNUNET_SET_ElementMessage *msg;
+};
+
+
+/**
+ * A set that supports a specific operation with other peers.
+ */
+struct Set
+{
/**
- * Socket connected to the peer
+ * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`).
*/
- struct GNUNET_STREAM_Socket *socket;
+ struct Set *next;
/**
- * Message queue for the peer
+ * Sets are held in a doubly linked list.
*/
- struct GNUNET_MQ_MessageQueue *mq;
+ struct Set *prev;
/**
- * App code, set once the peer has
- * requested an operation
+ * Client that owns the set. Only one client may own a set,
+ * and there can only be one set per client.
*/
- struct GNUNET_HashCode app_id;
+ struct ClientState *cs;
/**
- * Context message, set once the peer
- * has requested an operation.
+ * Content, possibly shared by multiple sets,
+ * and thus reference counted.
*/
- struct GNUNET_MessageHeader *context_msg;
+ struct SetContent *content;
+
+ /**
+ * Virtual table for this set. Determined by the operation type of
+ * this set.
+ *
+ * Used only for Add/remove of elements and when receiving an incoming
+ * operation from a remote peer.
+ */
+ const struct SetVT *vt;
+
+ /**
+ * Implementation-specific state.
+ */
+ struct SetState *state;
+
+ /**
+ * Current state of iterating elements for the client.
+ * NULL if we are not currently iterating.
+ */
+ struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
+
+ /**
+ * Evaluate operations are held in a linked list.
+ */
+ struct Operation *ops_head;
+
+ /**
+ * Evaluate operations are held in a linked list.
+ */
+ struct Operation *ops_tail;
+
+ /**
+ * List of generations we have to exclude, due to lazy copies.
+ */
+ struct GenerationRange *excluded_generations;
/**
- * Operation the other peer wants to do
+ * Current generation, that is, number of previously executed
+ * operations and lazy copies on the underlying set content.
+ */
+ unsigned int current_generation;
+
+ /**
+ * Number of elements in array @a excluded_generations.
+ */
+ unsigned int excluded_generations_size;
+
+ /**
+ * Type of operation supported for this set
*/
enum GNUNET_SET_OperationType operation;
/**
- * Request id associated with the
- * request coming from this client
+ * Generation we're currently iteration over.
*/
- uint32_t request_id;
+ unsigned int iter_generation;
+
+ /**
+ * Each @e iter is assigned a unique number, so that the client
+ * can distinguish iterations.
+ */
+ uint16_t iteration_id;
+
};
-/**
- * Configuration of the local peer
- */
-extern const struct GNUNET_CONFIGURATION_Handle *configuration;
+extern struct GNUNET_STATISTICS_Handle *_GSS_statistics;
/**
- * Disconnect a client and free all resources
- * that the client allocated (e.g. Sets or Listeners)
+ * Destroy the given operation. Used for any operation where both
+ * peers were known and that thus actually had a vt and channel. Must
+ * not be used for operations where 'listener' is still set and we do
+ * not know the other peer.
+ *
+ * Call the implementation-specific cancel function of the operation.
+ * Disconnects from the remote peer. Does not disconnect the client,
+ * as there may be multiple operations per set.
*
- * @param client the client to disconnect
+ * @param op operation to destroy
+ * @param gc #GNUNET_YES to perform garbage collection on the set
*/
void
-client_disconnect (struct GNUNET_SERVER_Client *client);
+_GSS_operation_destroy (struct Operation *op,
+ int gc);
-struct Set *
-union_set_create ();
-
-
-void
-union_evaluate (struct EvaluateOperation *eo);
+/**
+ * Get the table with implementing functions for set union.
+ *
+ * @return the operation specific VTable
+ */
+const struct SetVT *
+_GSS_union_vt (void);
-void
-union_add (struct Set *set, struct ElementMessage *m);
+/**
+ * Get the table with implementing functions for set intersection.
+ *
+ * @return the operation specific VTable
+ */
+const struct SetVT *
+_GSS_intersection_vt (void);
-void
-union_accept (struct EvaluateOperation *eo, struct Incoming *incoming);
+/**
+ * Is element @a ee part of the set used by @a op?
+ *
+ * @param ee element to test
+ * @param op operation the defines the set and its generation
+ * @return #GNUNET_YES if the element is in the set, #GNUNET_NO if not
+ */
+int
+_GSS_is_element_of_operation (struct ElementEntry *ee,
+ struct Operation *op);
#endif