X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Fset%2Fgnunet-service-set.h;h=bc3052f02ed6dda644a72018df3ead84afb495cc;hb=4dcb414e2faabc800577c25dec3b63e3ceaaa84b;hp=a5a53671c4e02d98e0656336566696d7d3b5b3da;hpb=ec7e1851bca2894a74326f0a7e4014ec453af0b0;p=oweals%2Fgnunet.git diff --git a/src/set/gnunet-service-set.h b/src/set/gnunet-service-set.h index a5a53671c..bc3052f02 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 Christian Grothoff (and other contributing authors) 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,253 +14,620 @@ 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_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; + + +/** + * Detail information about an operation. + */ +struct OperationSpecification { + /** - * Client that owns the set. - * Only one client may own a set. + * The remove peer we evaluate the operation with. */ - struct GNUNET_SERVER_Client *client; + struct GNUNET_PeerIdentity peer; /** - * Message queue for the client + * Application ID for the operation, used to distinguish + * multiple operations of the same type with the same peer. */ - struct GNUNET_MQ_MessageQueue *client_mq; + struct GNUNET_HashCode app_id; /** - * Type of operation supported for this set + * Context message, may be NULL. */ - uint32_t operation; // use enum from API + struct GNUNET_MessageHeader *context_msg; /** - * Sets are held in a doubly linked list. + * Set associated with the operation, NULL until the spec has been + * associated with a set. */ - struct Set *next; + struct Set *set; /** - * Sets are held in a doubly linked list. + * Salt to use for the operation. */ - struct Set *prev; + 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; + + /** + * The type of the operation. + */ + enum GNUNET_SET_OperationType operation; /** - * Appropriate state for each type of - * operation. + * When are elements sent to the client, and which elements are sent? */ - union { - struct IntersectionState *i; - struct UnionState *u; - } state; + enum GNUNET_SET_ResultMode result_mode; }; /** - * A listener is inhabited by a client, and - * waits for evaluation requests from remote peers. + * 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 + */ +typedef struct SetState * +(*CreateImpl) (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 +(*AddRemoveImpl) (struct SetState *state, + struct ElementEntry *ee); + + +/** + * 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); + + +/** + * Signature of functions that implement the destruction of the + * implementation-specific set state. + * + * @param state the set state, contains implementation-specific data */ -struct Listener +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 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 + */ +typedef void +(*OpEvaluateImpl) (struct Operation *op, + const struct GNUNET_MessageHeader *opaque_context); + + +/** + * Signature of functions that implement the message handling for + * the different set operations. + * + * @param op operation state + * @param msg received message + * @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); + + +/** + * Signature of functions that implement operation cancellation + * + * @param op operation state + */ +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. + */ +struct SetVT { /** - * Listeners are held in a doubly linked list. + * Callback for the set creation. */ - struct Listener *next; + CreateImpl create; /** - * Listeners are held in a doubly linked list. + * Callback for element insertion */ - struct Listener *prev; + AddRemoveImpl add; /** - * Client that owns the set. - * Only one client may own a set. + * Callback for element removal. */ - struct GNUNET_SERVER_Client *client; + AddRemoveImpl remove; /** - * Message queue for the client + * Callback for accepting a set operation request */ - struct GNUNET_MQ_MessageQueue *client_mq; + OpAcceptImpl accept; /** - * Type of operation supported for this set + * Callback for starting evaluation with a remote peer. */ - enum GNUNET_SET_OperationType operation; + OpEvaluateImpl evaluate; /** - * Application id of intereset for this listener. + * Callback for destruction of the set state. */ - struct GNUNET_HashCode app_id; + DestroySetImpl destroy_set; + + /** + * Callback for handling operation-specific messages. + */ + MsgHandlerImpl msg_handler; + + /** + * Callback for handling the remote peer's disconnect. + */ + PeerDisconnectImpl peer_disconnect; + + /** + * Callback for canceling an operation by its ID. + */ + CancelImpl cancel; + + CopyStateImpl copy_state; }; /** - * 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. + * MutationEvent gives information about changes + * to an element (removal / addition) in a set content. */ -struct Incoming +struct MutationEvent { /** - * Incoming peers are held in a linked list + * First generation affected by this mutation event. + * + * If @a generation is 0, this mutation event is a list + * sentinel element. */ - struct Incoming *next; + unsigned int generation; /** - * Incoming peers are held in a linked list + * If @a added is #GNUNET_YES, then this is a + * `remove` event, otherwise it is an `add` event. */ - struct Incoming *prev; + 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 + * fast. + */ +struct ElementEntry +{ /** - * Identity of the peer that connected to us + * The actual element. The data for the element + * should be allocated at the end of this struct. */ - struct GNUNET_PeerIdentity peer; + struct GNUNET_SET_Element element; /** - * Socket connected to the peer + * Hash of the element. For set union: Will be used to derive the + * different IBF keys for different salts. */ - struct GNUNET_STREAM_Socket *socket; + struct GNUNET_HashCode element_hash; /** - * Message queue for the peer + * 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 GNUNET_MQ_MessageQueue *mq; + struct MutationEvent *mutations; /** - * App code, set once the peer has - * requested an operation + * Number of elements in the array @a mutations. */ - struct GNUNET_HashCode app_id; + unsigned int mutations_size; /** - * Context message, set once the peer - * has requested an operation. + * #GNUNET_YES if the element is a remote element, and does not belong + * to the operation's set. */ - struct GNUNET_MessageHeader *context_msg; + int remote; +}; + +/** + * Operation context used to execute a set operation. + */ +struct Operation +{ /** - * Salt the peer has requested to use for the - * operation + * V-Table for the operation belonging to the tunnel contest. + * + * Used for all operation specific operations after receiving the ops request */ - uint16_t salt; + const struct SetVT *vt; /** - * Operation the other peer wants to do + * Channel to the peer. */ - enum GNUNET_SET_OperationType operation; + struct GNUNET_CADET_Channel *channel; /** - * Unique request id for the request from - * a remote peer. + * Message queue for the channel. */ - uint32_t request_id; + 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; + + /** + * 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; }; /** - * Configuration of the local peer + * SetContent stores the actual set elements, + * which may be shared by multiple generations derived + * from one set. */ -extern const struct GNUNET_CONFIGURATION_Handle *configuration; +struct SetContent +{ + /** + * Number of references to the content. + */ + unsigned int refcount; + /** + * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`. + */ + struct GNUNET_CONTAINER_MultiHashMap *elements; -/** - * Disconnect a client and free all resources - * that the client allocated (e.g. Sets or Listeners) - * - * @param client the client to disconnect - */ -void -_GSS_client_disconnect (struct GNUNET_SERVER_Client *client); + 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; +}; -/** - * Create a new set supporting the union operation - * - * @return the newly created set - */ -struct Set * -_GSS_union_set_create (void); + +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; +}; /** - * Evaluate a union operation with - * a remote peer. - * - * @param m the evaluate request message from the client - * @parem set the set to evaluate the operation with + * A set that supports a specific operation with other peers. */ -void -_GSS_union_evaluate (struct EvaluateMessage *m, struct Set *set); +struct Set +{ + + /** + * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`). + */ + struct Set *next; + + /** + * Sets are held in a doubly linked list. + */ + 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_SERVER_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. + */ + 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; + + /** + * 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; + + /** + * 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; + + /** + * 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; +}; /** - * Add the element from the given element message to the 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 m message with the element - * @param set set to add the element to + * @param op operation to destroy + * @param gc #GNUNET_YES to perform garbage collection on the set */ void -_GSS_union_add (struct ElementMessage *m, struct Set *set); +_GSS_operation_destroy (struct Operation *op, + int gc); /** - * Remove the element given in the element message from the set. - * Only marks the element as removed, so that older set operations can still exchange it. + * Get the table with implementing functions for set union. * - * @param m message with the element - * @param set set to remove the element from + * @return the operation specific VTable */ -void -_GSS_union_remove (struct ElementMessage *m, struct Set *set); +const struct SetVT * +_GSS_union_vt (void); /** - * Accept an union operation request from a remote peer + * Get the table with implementing functions for set intersection. * - * @param m the accept message from the client - * @param set the set of the client - * @param incoming information about the requesting remote peer + * @return the operation specific VTable */ -void -_GSS_union_accept (struct AcceptMessage *m, struct Set *set, - struct Incoming *incoming); +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