X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fset%2Fgnunet-service-set.h;h=86313d17966c4182023f56ac51d807129e0bfa2a;hb=dda2c14c04b6ef6275934e752c6952f9e35dbf44;hp=ae28b24c2e7ce75f453ba900e639289e8be75b5a;hpb=566dfe32be22ed1f071b974be3c4dd8bc5721151;p=oweals%2Fgnunet.git diff --git a/src/set/gnunet-service-set.h b/src/set/gnunet-service-set.h index ae28b24c2..86313d179 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, 2014 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,64 +14,67 @@ 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 #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_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; + +/** + * 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; +/** + * Operation context used to execute a set operation. + */ +struct Operation; + /** * Detail information about an operation. */ struct OperationSpecification { - /** - * The type of the operation. - */ - enum GNUNET_SET_OperationType operation; /** - * The remove peer we evaluate the operation with + * The remove peer we evaluate the operation with. */ struct GNUNET_PeerIdentity peer; @@ -86,33 +89,71 @@ struct OperationSpecification */ struct GNUNET_MessageHeader *context_msg; + /** + * Set associated with the operation, NULL until the spec has been + * associated with a set. + */ + struct Set *set; + /** * Salt to use for the operation. */ uint32_t salt; /** - * ID used to identify responses to a client. + * Remote peers element count + */ + uint32_t remote_element_count; + + /** + * ID used to identify an operation between service and client */ uint32_t client_request_id; /** - * Set associated with the operation, NULL until the spec has been associated - * with a set. + * The type of the operation. */ - struct Set *set; -}; + enum GNUNET_SET_OperationType operation; + /** + * 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; +}; /** * 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 * +(*CreateImpl) (void); /** @@ -120,18 +161,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 +(*AddRemoveImpl) (struct SetState *state, + struct ElementEntry *ee); /** - * Signature of functions that handle disconnection - * of the remote peer. + * Signature of functions that handle disconnection of the remote + * peer. * * @param op the set operation, contains implementation-specific data */ -typedef void (*PeerDisconnectImpl) (struct OperationState *op); +typedef void +(*PeerDisconnectImpl) (struct Operation *op); /** @@ -140,51 +184,50 @@ typedef void (*PeerDisconnectImpl) (struct OperationState *op); * * @param state the set state, contains implementation-specific data */ -typedef void (*DestroySetImpl) (struct SetState *state); +typedef void +(*DestroySetImpl) (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 */ -typedef void (*OpCreateImpl) (struct OperationSpecification *spec, - struct GNUNET_MESH_Tunnel *tunnel, - struct TunnelContext *tc); +typedef void +(*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 */ -typedef int (*MsgHandlerImpl) (struct OperationState *op, - const struct GNUNET_MessageHeader *msg); - -typedef void (*CancelImpl) (struct SetState *set, - uint32_t request_id); +typedef void +(*OpEvaluateImpl) (struct Operation *op, + const struct GNUNET_MessageHeader *opaque_context); /** - * Signature of functions that implement sending all the set's - * elements to the client. + * Signature of functions that implement operation cancellation * - * @param set set that should be iterated over + * @param op operation state */ -typedef void (*IterateImpl) (struct Set *set); +typedef void +(*CancelImpl) (struct Operation *op); + + +typedef struct SetState * +(*CopyStateImpl) (struct Set *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 { @@ -206,12 +249,12 @@ struct SetVT /** * Callback for accepting a set operation request */ - OpCreateImpl accept; + OpAcceptImpl accept; /** * Callback for starting evaluation with a remote peer. */ - OpCreateImpl evaluate; + OpEvaluateImpl evaluate; /** * Callback for destruction of the set state. @@ -219,34 +262,45 @@ struct SetVT DestroySetImpl destroy_set; /** - * Callback for handling operation-specific messages. + * Callback for handling the remote peer's disconnect. */ - MsgHandlerImpl msg_handler; + PeerDisconnectImpl peer_disconnect; /** - * Callback for handling the remote peer's - * disconnect. + * Callback for canceling an operation by its ID. */ - PeerDisconnectImpl peer_disconnect; + CancelImpl cancel; + + CopyStateImpl copy_state; +}; + +/** + * 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 @@ -258,68 +312,212 @@ 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. - */ - unsigned int generation_added; - - /** - * GNUNET_YES if the element has been removed in some generation. + * 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. */ - int removed; + struct MutationEvent *mutations; /** - * 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. + * Number of elements in the array @a mutations. */ - unsigned int generation_removed; + unsigned int mutations_size; /** - * GNUNET_YES if the element is a remote element, and does not belong + * #GNUNET_YES if the element is a remote element, and does not belong * to the operation's set. */ int remote; }; +struct Listener; + + /** - * 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. + * V-Table for the operation belonging to the tunnel contest. + * + * Used for all operation specific operations after receiving the ops request */ - struct GNUNET_SERVER_Client *client; + const struct SetVT *vt; /** - * Message queue for the client + * Channel to the peer. */ - struct GNUNET_MQ_Handle *client_mq; + struct GNUNET_CADET_Channel *channel; /** - * Type of operation supported for this set + * Port this operation runs on. + */ + struct Listener *listener; + + /** + * Message queue for the channel. + */ + struct GNUNET_MQ_Handle *mq; + + /** + * Detail information about the set operation, including the set to + * use. When 'spec' is NULL, the operation is not yet entirely + * initialized. + */ + struct OperationSpecification *spec; + + /** + * 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; + + /** + * Evaluate operations are held in a linked list. + */ + struct Operation *next; + + /** + * Evaluate operations are held in a linked list. + */ + struct Operation *prev; + + /** + * 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; + + /** + * The type of the operation. */ enum GNUNET_SET_OperationType operation; /** - * Virtual table for this set. - * Determined by the operation type of this set. + * 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. */ - const struct SetVT *vt; + uint32_t suggest_id; /** - * Sets are held in a doubly linked list. + * #GNUNET_YES if this is not a "real" set operation yet, and we still + * need to wait for the other peer to give us more details. + */ + int is_incoming; + + /** + * Generation in which the operation handle + * was created. + */ + unsigned int generation_created; + + /** + * Incremented whenever (during shutdown) some component still + * needs to do something with this before the operation is freed. + * (Used as a reference counter, but only during termination.) + */ + unsigned int keep; +}; + + +/** + * SetContent stores the actual set elements, + * which may be shared by multiple generations derived + * from one set. + */ +struct SetContent +{ + /** + * Number of references to the content. + */ + unsigned int refcount; + + /** + * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`. + */ + struct GNUNET_CONTAINER_MultiHashMap *elements; + + unsigned int latest_generation; + + /** + * 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 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; +}; + + +struct PendingMutation +{ + struct PendingMutation *prev; + struct PendingMutation *next; + + 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_MessageHeader *mutation_message; +}; + + +/** + * 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; @@ -328,6 +526,26 @@ 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 GNUNET_SERVICE_Client *client; + + /** + * Message queue for the client. + */ + struct GNUNET_MQ_Handle *client_mq; + + /** + * 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. */ @@ -340,43 +558,97 @@ 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; /** - * Current generation, that is, number of - * previously executed operations on this set + * Evaluate operations are held in a linked list. + */ + struct Operation *ops_tail; + + /** + * Current generation, that is, number of previously executed + * operations and lazy copies on the underlying set content. */ unsigned int current_generation; -}; + /** + * List of generations we have to exclude, due to lazy copies. + */ + struct GenerationRange *excluded_generations; -/** - * 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. + * Number of elements in array @a excluded_generations. */ - const struct SetVT *vt; + unsigned int excluded_generations_size; + + /** + * Type of operation supported for this set + */ + enum GNUNET_SET_OperationType operation; /** - * Implementation-specific operation state. + * Each @e iter is assigned a unique number, so that the client + * can distinguish iterations. */ - struct OperationState *op; + uint16_t iteration_id; + + /** + * Generation we're currently iteration over. + */ + unsigned int iter_generation; + + /** + * Content, possibly shared by multiple sets, + * and thus reference counted. + */ + struct SetContent *content; }; +extern struct GNUNET_STATISTICS_Handle *_GSS_statistics; + + /** - * Get the table with implementing functions for - * set union. + * Destroy the given operation. 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. + * + * @return the operation specific VTable */ const struct SetVT * _GSS_union_vt (void); +/** + * Get the table with implementing functions for set intersection. + * + * @return the operation specific VTable + */ +const struct SetVT * +_GSS_intersection_vt (void); + + +int +_GSS_is_element_of_set (struct ElementEntry *ee, + struct Set *set); + +int +_GSS_is_element_of_operation (struct ElementEntry *ee, + struct Operation *op); + + #endif