X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fset%2Fgnunet-service-set.h;h=19413fd3047ea297c13d3648cdd61e89120c82f3;hb=48fc70932f0074447d2ab821f2babb5bfe754a1e;hp=c6e26db22c4f19d74b97ad9978b130bea9a7455c;hpb=7262570cdee2b0ad228e1d30959b7d5f1c816c58;p=oweals%2Fgnunet.git diff --git a/src/set/gnunet-service-set.h b/src/set/gnunet-service-set.h index c6e26db22..19413fd30 100644 --- a/src/set/gnunet-service-set.h +++ b/src/set/gnunet-service-set.h @@ -1,10 +1,10 @@ /* 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 @@ -14,280 +14,651 @@ 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