X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fset%2Fgnunet-service-set.h;h=68d8fe81f60a6a75fcffdaa7247765fca3a1ffc8;hb=2d92ec0f27dbefef916e94f5d272a2ff72091c54;hp=d82c72b16287c0a3a5ce713b34b73811273dc0d9;hpb=c544c71578c4557722aae8c4f0f359decd38f689;p=oweals%2Fgnunet.git diff --git a/src/set/gnunet-service-set.h b/src/set/gnunet-service-set.h index d82c72b16..68d8fe81f 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, 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 @@ -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,30 +31,39 @@ #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; + +/** + * 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; @@ -64,13 +72,9 @@ struct 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; @@ -85,6 +89,12 @@ 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. */ @@ -101,27 +111,49 @@ struct OperationSpecification 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); /** @@ -129,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 Operation *op); +typedef void +(*PeerDisconnectImpl) (struct Operation *op); /** @@ -149,16 +184,32 @@ typedef void (*PeerDisconnectImpl) (struct Operation *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 accepting a set operation. + * + * @param op operation that is created by accepting the operation, + * should be initialized by the implementation + */ +typedef void +(*OpAcceptImpl) (struct Operation *op); /** - * Signature of functions that implement the creation of set operations - * (currently evaluate and accept). + * Signature of functions that implement starting the evaluation of + * set operations. * - * @param op operation that is created, should be initialized by the implementation + * @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 void (*OpCreateImpl) (struct Operation *op); +typedef void +(*OpEvaluateImpl) (struct Operation *op, + const struct GNUNET_MessageHeader *opaque_context); /** @@ -167,24 +218,30 @@ typedef void (*OpCreateImpl) (struct Operation *op); * * @param op operation state * @param msg received message - * @return GNUNET_OK on success, GNUNET_SYSERR to + * @return #GNUNET_OK on success, #GNUNET_SYSERR to * destroy the operation and the tunnel */ -typedef int (*MsgHandlerImpl) (struct Operation *op, - const struct GNUNET_MessageHeader *msg); +typedef int +(*MsgHandlerImpl) (struct Operation *op, + const struct GNUNET_MessageHeader *msg); + /** * Signature of functions that implement operation cancellation * * @param op operation state */ -typedef void (*CancelImpl) (struct Operation *op); +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 +263,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. @@ -224,24 +281,45 @@ struct SetVT MsgHandlerImpl msg_handler; /** - * Callback for handling the remote peer's - * disconnect. + * Callback for handling the remote peer's disconnect. */ PeerDisconnectImpl peer_disconnect; /** - * Callback for canceling an operation by - * its ID. + * Callback for canceling an operation by its ID. */ CancelImpl cancel; + + CopyStateImpl copy_state; +}; + + +/** + * MutationEvent gives information about changes + * to an element (removal / addition) in a set content. + */ +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; }; /** - * 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 @@ -253,135 +331,207 @@ struct ElementEntry struct GNUNET_SET_Element element; /** - * Hash of the element. - * For set union: - * 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. - * - * //TODO: Move to Union, unless additional set-operations are implemented ever */ int remote; }; +struct Listener; + + +/** + * Operation context used to execute a set operation. + */ struct Operation { /** - * V-Table for the operation belonging - * to the tunnel contest. + * V-Table for the operation belonging to the tunnel contest. * * Used for all operation specific operations after receiving the ops request */ const struct SetVT *vt; /** - * Tunnel to the peer. - */ - struct GNUNET_MESH_Channel *channel; - - /** - * Message queue for the tunnel. + * Channel to the peer. */ - struct GNUNET_MQ_Handle *mq; + struct GNUNET_CADET_Channel *channel; /** - * 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. - * - * //TODO: replace with state-enum + * Port this operation runs on. */ - int is_incoming; + struct Listener *listener; /** - * Generation in which the operation handle - * was created. + * Message queue for the channel. */ - unsigned int generation_created; + 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 + * 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. + * 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. + * Evaluate operations are held in a linked list. */ struct Operation *next; - /** - * Evaluate operations are held in - * a linked list. - */ + /** + * 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; + + /** + * 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; + + /** + * #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; }; /** - * A set that supports a specific operation - * with other peers. + * SetContent stores the actual set elements, + * which may be shared by multiple generations derived + * from one set. */ -struct Set +struct SetContent { /** - * Client that owns the set. - * Only one client may own a set. + * Number of references to the content. */ - struct GNUNET_SERVER_Client *client; + unsigned int refcount; /** - * Message queue for the client + * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`. */ - struct GNUNET_MQ_Handle *client_mq; + struct GNUNET_CONTAINER_MultiHashMap *elements; + + unsigned int latest_generation; /** - * Type of operation supported for this 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. */ - enum GNUNET_SET_OperationType operation; + struct PendingMutation *pending_mutations_head; /** - * 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. + * Mutations requested by the client that we're + * unable to execute right now because we're iterating + * over the underlying hash map of elements. */ - const struct SetVT *vt; + struct PendingMutation *pending_mutations_tail; /** - * Sets are held in a doubly linked list. + * 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; @@ -390,6 +540,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. */ @@ -402,44 +572,74 @@ 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; /** - * Evaluate operations are held in - * a linked list. + * List of generations we have to exclude, due to lazy copies. */ - struct Operation *ops_head; + struct GenerationRange *excluded_generations; /** - * Evaluate operations are held in - * a linked list. + * Number of elements in array @a excluded_generations. */ - struct Operation *ops_tail; + unsigned int excluded_generations_size; + + /** + * Type of operation supported for this set + */ + enum GNUNET_SET_OperationType operation; + + /** + * Each @e iter is assigned a unique number, so that the client + * can distinguish iterations. + */ + 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; + + /** - * 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. + * 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); +_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 */ @@ -448,8 +648,7 @@ _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 */ @@ -457,4 +656,13 @@ 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