X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fset%2Fgnunet-service-set.h;h=19413fd3047ea297c13d3648cdd61e89120c82f3;hb=48fc70932f0074447d2ab821f2babb5bfe754a1e;hp=7c2363e9f22b654ada6850ecff0cd9d01c12395a;hpb=3c8f930edb077352ea48fa018a0e80fee0af339d;p=oweals%2Fgnunet.git diff --git a/src/set/gnunet-service-set.h b/src/set/gnunet-service-set.h index 7c2363e9f..19413fd30 100644 --- a/src/set/gnunet-service-set.h +++ b/src/set/gnunet-service-set.h @@ -1,6 +1,6 @@ /* 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 @@ -14,16 +14,15 @@ 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. */ - /** * @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 @@ -32,91 +31,50 @@ #include "gnunet_protocols.h" #include "gnunet_applications.h" #include "gnunet_core_service.h" -#include "gnunet_mesh_service.h" +#include "gnunet_cadet_service.h" #include "gnunet_set_service.h" #include "set.h" /** - * Implementation-specific set state. - * Used as opaque pointer, and specified further - * in the respective implementation. + * 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. + * Implementation-specific set operation. Used as opaque pointer, and + * specified further in the respective implementation. */ struct OperationState; - -/* forward declarations */ +/** + * A set that supports a specific operation with other peers. + */ struct Set; -struct TunnelContext; -struct ElementEntry; - /** - * Detail information about an operation. + * 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 OperationSpecification -{ - /** - * The type of the operation. - */ - enum GNUNET_SET_OperationType operation; - - /** - * The remove peer we evaluate the operation with - */ - struct GNUNET_PeerIdentity peer; - - /** - * Application ID for the operation, used to distinguish - * multiple operations of the same type with the same peer. - */ - struct GNUNET_HashCode app_id; - - /** - * Context message, may be NULL. - */ - struct GNUNET_MessageHeader *context_msg; - - /** - * Salt to use for the operation. - */ - uint32_t salt; - - /** - * ID used to identify responses to a client. - */ - uint32_t client_request_id; - - /** - * Set associated with the operation, NULL until the spec has been associated - * with a set. - */ - struct Set *set; - - /** - * When are elements sent to the client, and which elements are sent? - */ - enum GNUNET_SET_ResultMode result_mode; -}; - +struct ElementEntry; +/** + * Operation context used to execute a set operation. + */ +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 + * @return a set state specific to the supported operation, NULL on error */ -typedef struct SetState *(*CreateImpl) (void); +typedef struct SetState * +(*SetCreateImpl) (void); /** @@ -124,18 +82,21 @@ typedef struct SetState *(*CreateImpl) (void); * for a set supporting a specific operation. * * @param set implementation-specific set state - * @param msg element message from the client + * @param ee element message from the client */ -typedef void (*AddRemoveImpl) (struct SetState *state, struct ElementEntry *ee); +typedef void +(*SetAddRemoveImpl) (struct SetState *state, + struct ElementEntry *ee); /** - * Signature of functions that handle disconnection - * of the remote peer. + * Make a copy of a set's internal state. * - * @param op the set operation, contains implementation-specific data + * @param state set state to copy + * @return copy of the internal state */ -typedef void (*PeerDisconnectImpl) (struct OperationState *op); +typedef struct SetState * +(*SetCopyStateImpl) (struct SetState *state); /** @@ -144,113 +105,136 @@ typedef void (*PeerDisconnectImpl) (struct OperationState *op); * * @param state the set state, contains implementation-specific data */ -typedef void (*DestroySetImpl) (struct SetState *state); +typedef void +(*SetDestroyImpl) (struct SetState *state); /** - * Signature of functions that implement the creation of set operations - * (currently evaluate and accept). + * Signature of functions that implement accepting a set operation. * - * @param spec specification of the set operation to be created - * @param tunnel the tunnel with the other peer - * @param tc tunnel context + * @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 void (*OpCreateImpl) (struct OperationSpecification *spec, - struct GNUNET_MESH_Tunnel *tunnel, - struct TunnelContext *tc); +typedef struct OperationState * +(*OpAcceptImpl) (struct Operation *op); /** - * Signature of functions that implement the message handling for - * the different set operations. + * Signature of functions that implement starting the evaluation of + * set operations. * - * @param op operation state - * @param msg received message - * @return GNUNET_OK on success, GNUNET_SYSERR to - * destroy the operation and the tunnel + * @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 int (*MsgHandlerImpl) (struct OperationState *op, - const struct GNUNET_MessageHeader *msg); +typedef struct OperationState * +(*OpEvaluateImpl) (struct Operation *op, + const struct GNUNET_MessageHeader *opaque_context); -typedef void (*CancelImpl) (struct SetState *set, - uint32_t request_id); +/** + * 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 that implement sending all the set's - * elements to the client. + * Signature of functions called when the CADET channel died. * - * @param set set that should be iterated over + * @param op operation state */ -typedef void (*IterateImpl) (struct Set *set); +typedef void +(*OpChannelDeathImpl) (struct Operation *op); + /** - * Dispatch table for a specific set operation. - * Every set operation has to implement the callback - * in this struct. + * Dispatch table for a specific set operation. Every set operation + * has to implement the callback in this struct. */ struct SetVT { /** * Callback for the set creation. */ - CreateImpl create; + SetCreateImpl create; /** * Callback for element insertion */ - AddRemoveImpl add; + SetAddRemoveImpl add; /** * Callback for element removal. */ - AddRemoveImpl remove; + SetAddRemoveImpl remove; /** - * Callback for accepting a set operation request + * Callback for making a copy of a set's internal state. */ - OpCreateImpl accept; + SetCopyStateImpl copy_state; /** - * Callback for starting evaluation with a remote peer. + * Callback for destruction of the set state. */ - OpCreateImpl evaluate; + SetDestroyImpl destroy_set; /** - * Callback for destruction of the set state. + * Callback for accepting a set operation request + */ + OpAcceptImpl accept; + + /** + * Callback for starting evaluation with a remote peer. */ - DestroySetImpl destroy_set; + OpEvaluateImpl evaluate; /** - * Callback for handling operation-specific messages. + * Callback for canceling an operation. */ - MsgHandlerImpl msg_handler; + OpCancelImpl cancel; /** - * Callback for handling the remote peer's - * disconnect. + * Callback called in case the CADET channel died. */ - PeerDisconnectImpl peer_disconnect; + OpChannelDeathImpl channel_death; + +}; + +/** + * MutationEvent gives information about changes + * to an element (removal / addition) in a set content. + */ +struct MutationEvent +{ /** - * Callback for canceling an operation by - * its ID. + * First generation affected by this mutation event. + * + * If @a generation is 0, this mutation event is a list + * sentinel element. */ - CancelImpl cancel; + unsigned int generation; /** - * Callback for iterating over all set elements. + * If @a added is #GNUNET_YES, then this is a + * `remove` event, otherwise it is an `add` event. */ - IterateImpl iterate; + int added; }; /** - * 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 + * 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 @@ -262,68 +246,285 @@ struct ElementEntry struct GNUNET_SET_Element element; /** - * Hash of the element. - * Will be used to derive the different IBF keys - * for different salts. + * Hash of the element. For set union: Will be used to derive the + * different IBF keys for different salts. */ struct GNUNET_HashCode element_hash; /** - * Generation the element was added by the client. - * Operations of earlier generations will not consider the element. + * 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. */ - unsigned int generation_added; + struct MutationEvent *mutations; /** - * GNUNET_YES if the element has been removed in some generation. + * Number of elements in the array @a mutations. */ - int removed; + unsigned int mutations_size; /** - * Generation the element was removed by the client. - * Operations of later generations will not consider the element. - * Only valid if is_removed is GNUNET_YES. + * #GNUNET_YES if the element is a remote element, and does not belong + * to the operation's set. */ - unsigned int generation_removed; + int remote; +}; + +/** + * A listener is inhabited by a client, and waits for evaluation + * requests from remote peers. + */ +struct Listener; + + +/** + * State we keep per client. + */ +struct ClientState +{ /** - * GNUNET_YES if the element is a remote element, and does not belong - * to the operation's set. + * Set, if associated with the client, otherwise NULL. */ - int remote; + struct Set *set; + + /** + * Listener, if associated with the client, otherwise NULL. + */ + struct Listener *listener; + + /** + * Client handle. + */ + struct GNUNET_SERVICE_Client *client; + + /** + * Message queue. + */ + struct GNUNET_MQ_Handle *mq; + }; /** - * A set that supports a specific operation - * with other peers. + * Operation context used to execute a set operation. */ -struct Set +struct Operation { + /** - * Client that owns the set. - * Only one client may own a set. + * Kept in a DLL of the listener, if @e listener is non-NULL. */ - struct GNUNET_SERVER_Client *client; + struct Operation *next; /** - * Message queue for the client + * Kept in a DLL of the listener, if @e listener is non-NULL. */ - struct GNUNET_MQ_Handle *client_mq; + struct Operation *prev; /** - * Type of operation supported for this set + * Channel to the peer. */ - enum GNUNET_SET_OperationType operation; + struct GNUNET_CADET_Channel *channel; /** - * Virtual table for this set. - * Determined by the operation type of this set. + * Port this operation runs on. */ - const struct SetVT *vt; + struct Listener *listener; /** - * Sets are held in a doubly linked list. + * Message queue for the channel. + */ + struct GNUNET_MQ_Handle *mq; + + /** + * Context message, may be NULL. + */ + struct GNUNET_MessageHeader *context_msg; + + /** + * Set associated with the operation, NULL until the spec has been + * associated with a set. + */ + struct Set *set; + + /** + * Operation-specific operation state. Note that the exact + * type depends on this being a union or intersection operation + * (and thus on @e vt). + */ + struct OperationState *state; + + /** + * The identity of the requesting peer. Needs to + * be stored here as the op spec might not have been created yet. + */ + 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; + + /** + * Always send full sets, even if delta operations would + * be more efficient. + */ + int force_full; + + /** + * #GNUNET_YES to fail operations where Byzantine faults + * are suspected + */ + 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; + +}; + + +/** + * SetContent stores the actual set elements, which may be shared by + * multiple generations derived from one set. + */ +struct SetContent +{ + + /** + * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`. + */ + struct GNUNET_CONTAINER_MultiHashMap *elements; + + /** + * 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 PendingMutation *pending_mutations_head; + + /** + * 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 PendingMutation *pending_mutations_tail; + + /** + * Number of references to the content. + */ + unsigned int refcount; + + /** + * FIXME: document! + */ + unsigned int latest_generation; + + /** + * Number of concurrently active iterators. + */ + int iterator_count; +}; + + +struct GenerationRange +{ + /** + * First generation that is excluded. + */ + unsigned int start; + + /** + * Generation after the last excluded generation. + */ + unsigned int end; +}; + + +/** + * Information about a mutation to apply to a set. + */ +struct PendingMutation +{ + /** + * Mutations are kept in a DLL. + */ + struct PendingMutation *prev; + + /** + * Mutations are kept in a DLL. + */ + struct PendingMutation *next; + + /** + * Set this mutation is about. + */ + 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 +{ + + /** + * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`). */ struct Set *next; @@ -332,6 +533,27 @@ struct Set */ struct Set *prev; + /** + * Client that owns the set. Only one client may own a set, + * and there can only be one set per client. + */ + struct ClientState *cs; + + /** + * Content, possibly shared by multiple sets, + * and thus reference counted. + */ + 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. */ @@ -344,50 +566,99 @@ struct Set struct GNUNET_CONTAINER_MultiHashMapIterator *iter; /** - * Maps 'struct GNUNET_HashCode' to 'struct ElementEntry'. + * Evaluate operations are held in a linked list. */ - struct GNUNET_CONTAINER_MultiHashMap *elements; + struct Operation *ops_head; + + /** + * Evaluate operations are held in a linked list. + */ + struct Operation *ops_tail; /** - * Current generation, that is, number of - * previously executed operations on this set + * List of generations we have to exclude, due to lazy copies. + */ + struct GenerationRange *excluded_generations; + + /** + * 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; -/** - * Information about a tunnel we are connected to. - * Used as tunnel context with mesh. - */ -struct TunnelContext -{ /** - * V-Table for the operation belonging - * to the tunnel contest. + * Type of operation supported for this set */ - const struct SetVT *vt; + enum GNUNET_SET_OperationType operation; /** - * Implementation-specific operation state. + * Generation we're currently iteration over. */ - struct OperationState *op; + unsigned int iter_generation; + + /** + * Each @e iter is assigned a unique number, so that the client + * can distinguish iterations. + */ + uint16_t iteration_id; + }; +extern struct GNUNET_STATISTICS_Handle *_GSS_statistics; + + +/** + * 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 op operation to destroy + * @param gc #GNUNET_YES to perform garbage collection on the set + */ +void +_GSS_operation_destroy (struct Operation *op, + int gc); + + /** - * Get the table with implementing functions for - * set union. + * Get the table with implementing functions for set union. + * + * @return the operation specific VTable */ const struct SetVT * _GSS_union_vt (void); + /** - * Get the table with implementing functions for - * set intersection. + * Get the table with implementing functions for set intersection. + * + * @return the operation specific VTable */ const struct SetVT * _GSS_intersection_vt (void); +/** + * 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