projects / oweals / gnunet.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
adding DEBUG logic for #3863
[oweals/gnunet.git] / src / set / gnunet-service-set.h
diff --git a/src/set/gnunet-service-set.h b/src/set/gnunet-service-set.h
index 533fd0ef72b3d5821757984dbf0e126621a10a7a..bc3052f02ed6dda644a72018df3ead84afb495cc 100644 (file)
--- a/src/set/gnunet-service-set.h
+++ b/src/set/gnunet-service-set.h
@@ -1,10 +1,10 @@
 /*
       This file is part of GNUnet
 /*
       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
 
       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
       option) any later version.
 
       GNUnet is distributed in the hope that it will be useful, but
@@ -14,333 +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
 
       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
 /**
  * @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"
 #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_protocols.h"
 #include "gnunet_applications.h"
-#include "gnunet_util_lib.h"
 #include "gnunet_core_service.h"
 #include "gnunet_core_service.h"
-#include "gnunet_mesh2_service.h"
+#include "gnunet_cadet_service.h"
 #include "gnunet_set_service.h"
 #include "set.h"
 
 
 #include "gnunet_set_service.h"
 #include "set.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;
 
 
+/**
+ * A set that supports a specific operation with other peers.
+ */
+struct Set;
 
 /**
 
 /**
- * Extra state required for set union.
+ * 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 UnionState;
+struct ElementEntry;
 
 
-struct UnionEvaluateOperation;
+/**
+ * Operation context used to execute a set operation.
+ */
+struct Operation;
 
 
 /**
 
 
 /**
- * A set that supports a specific operation
- * with other peers.
+ * Detail information about an operation.
  */
  */
-struct Set
+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_Handle *client_mq;
+  struct GNUNET_HashCode app_id;
 
   /**
 
   /**
-   * Type of operation supported for this set
+   * 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.
    */
    */
-  uint32_t operation; // use enum from API
+  struct Set *set;
 
   /**
 
   /**
-   * Sets are held in a doubly linked list.
+   * Salt to use for the operation.
    */
    */
-  struct Set *next;
+  uint32_t salt;
 
   /**
 
   /**
-   * Sets are held in a doubly linked list.
+   * Remote peers element count
    */
    */
-  struct Set *prev;
+  uint32_t remote_element_count;
 
   /**
 
   /**
-   * Appropriate state for each type of
-   * operation.
+   * ID used to identify an operation between service and client
    */
    */
-  union {
-    struct IntersectionState *i;
-    struct UnionState *u;
-  } state;
+  uint32_t client_request_id;
+
+  /**
+   * The type of the operation.
+   */
+  enum GNUNET_SET_OperationType operation;
+
+  /**
+   * When are elements sent to the client, and which elements are sent?
+   */
+  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
+ */
+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 Listener
+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 listener.
-   * Only one client may own a listener.
+   * 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_Handle *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
+{
   /**
   /**
-   * Tunnel context, stores information about
-   * the tunnel and its peer.
+   * The actual element. The data for the element
+   * should be allocated at the end of this struct.
    */
    */
-  struct TunnelContext *tc;
+  struct GNUNET_SET_Element element;
 
   /**
 
   /**
-   * GNUNET_YES if the incoming peer has sent
-   * an operation request (and we are waiting
-   * for the client to ack/nack), GNUNET_NO otherwise.
+   * Hash of the element.  For set union: Will be used to derive the
+   * different IBF keys for different salts.
    */
    */
-  int received_request;
+  struct GNUNET_HashCode element_hash;
 
   /**
 
   /**
-   * App code, set once the peer has
-   * requested an operation
+   * 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_HashCode app_id;
+  struct MutationEvent *mutations;
 
   /**
 
   /**
-   * Context message, set once the peer
-   * has requested an operation.
+   * Number of elements in the array @a mutations.
    */
    */
-  struct GNUNET_MessageHeader *context_msg;
+  unsigned int mutations_size;
 
   /**
 
   /**
-   * Salt the peer has requested to use for the
-   * operation
+   * #GNUNET_YES if the element is a remote element, and does not belong
+   * to the operation's set.
    */
    */
-  uint16_t salt;
+  int remote;
+};
 
 
+
+/**
+ * Operation context used to execute a set operation.
+ */
+struct Operation
+{
   /**
   /**
-   * Operation the other peer wants to do
+   * V-Table for the operation belonging to the tunnel contest.
+   *
+   * Used for all operation specific operations after receiving the ops request
    */
    */
-  enum GNUNET_SET_OperationType operation;
+  const struct SetVT *vt;
+
+  /**
+   * Channel to the peer.
+   */
+  struct GNUNET_CADET_Channel *channel;
+
+  /**
+   * Message queue for the channel.
+   */
+  struct GNUNET_MQ_Handle *mq;
 
   /**
 
   /**
-   * Has the incoming request been suggested to
-   * a client listener yet?
+   * Detail information about the set operation, including the set to
+   * use.  When 'spec' is NULL, the operation is not yet entirely
+   * initialized.
    */
    */
-  int suggested;
+  struct OperationSpecification *spec;
 
   /**
 
   /**
-   * Unique request id for the request from
-   * a remote peer, sent to the client, which will
-   * accept or reject the request.
+   * Operation-specific operation state.  Note that the exact
+   * type depends on this being a union or intersection operation
+   * (and thus on @e vt).
    */
    */
-  uint32_t accept_id;
+  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.
    */
 
   /**
    * Timeout task, if the incoming peer has not been accepted
    * after the timeout, it will be disconnected.
    */
-  GNUNET_SCHEDULER_TaskIdentifier timeout_task;
-};
+  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;
 
 
-enum TunnelContextType {
-  CONTEXT_INCOMING,
-  CONTEXT_OPERATION_UNION,
-  CONTEXT_OPERATION_INTERSECTION,
+  /**
+   * 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;
 };
 
 };
 
+
 /**
 /**
- * Information about a tunnel we are connected to.
- * Used as tunnel context with mesh.
+ * SetContent stores the actual set elements,
+ * which may be shared by multiple generations derived
+ * from one set.
  */
  */
-struct TunnelContext
+struct SetContent
 {
   /**
 {
   /**
-   * The mesh tunnel that has this context
+   * Number of references to the content.
    */
    */
-  struct GNUNET_MESH_Tunnel *tunnel;
+  unsigned int refcount;
 
   /**
 
   /**
-   * The peer on the other side.
+   * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
    */
    */
-  struct GNUNET_PeerIdentity peer;
+  struct GNUNET_CONTAINER_MultiHashMap *elements;
+
+  unsigned int latest_generation;
 
   /**
 
   /**
-   * Handle to the message queue for the tunnel.
+   * 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_MQ_Handle *mq;
+  struct PendingMutation *pending_mutations_head;
 
   /**
 
   /**
-   * Type of the tunnel.
+   * 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 TunnelContextType type;
+  struct PendingMutation *pending_mutations_tail;
 
   /**
 
   /**
-   * State associated with the tunnel, dependent on
-   * tunnel type.
+   * Number of concurrently active iterators.
    */
    */
-  void *data;
+  int iterator_count;
 };
 
 
 };
 
 
+struct GenerationRange
+{
+  /**
+   * First generation that is excluded.
+   */
+  unsigned int start;
+
+  /**
+   * Generation after the last excluded generation.
+   */
+  unsigned int end;
+};
 
 
-/**
- * Configuration of the local peer
- */
-extern const struct GNUNET_CONFIGURATION_Handle *configuration;
 
 
-extern struct GNUNET_MESH_Handle *mesh;
+struct PendingMutation
+{
+  struct PendingMutation *prev;
+  struct PendingMutation *next;
 
 
+  struct Set *set;
 
 
-/**
- * Create a new set supporting the union operation
- *
- * @return the newly created set
- */
-struct Set *
-_GSS_union_set_create (void);
+  /**
+   * 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
- * @param set the set to evaluate the operation with
+ * A set that supports a specific operation with other peers.
  */
  */
-void
-_GSS_union_evaluate (struct GNUNET_SET_EvaluateMessage *m, struct Set *set);
+struct Set
+{
 
 
+  /**
+   * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`).
+   */
+  struct Set *next;
 
 
-/**
- * Add the element from the given element message to the set.
- *
- * @param m message with the element
- * @param set set to add the element to
- */
-void
-_GSS_union_add (struct GNUNET_SET_ElementMessage *m, struct Set *set);
+  /**
+   * 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;
 
 
-/**
- * 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.
- *
- * @param m message with the element
- * @param set set to remove the element from
- */
-void
-_GSS_union_remove (struct GNUNET_SET_ElementMessage *m, struct Set *set);
+  /**
+   * 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;
 
 
-/**
- * Destroy a set that supports the union operation
- *
- * @param set the set to destroy, must be of type GNUNET_SET_OPERATION_UNION
- */
-void
-_GSS_union_set_destroy (struct Set *set);
+  /**
+   * 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;
+};
 
 
 /**
 
 
 /**
- * Accept an union operation request from a remote peer
+ * 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 the accept message from the client
- * @param set the set of the client
- * @param incoming information about the requesting remote peer
+ * @param op operation to destroy
+ * @param gc #GNUNET_YES to perform garbage collection on the set
  */
 void
  */
 void
-_GSS_union_accept (struct GNUNET_SET_AcceptRejectMessage *m, struct Set *set,
-                   struct Incoming *incoming);
+_GSS_operation_destroy (struct Operation *op,
+                        int gc);
 
 
 /**
 
 
 /**
- * Destroy a union operation, and free all resources
- * associated with it.
+ * Get the table with implementing functions for set union.
  *
  *
- * @param eo the union operation to destroy
+ * @return the operation specific VTable
  */
  */
-void
-_GSS_union_operation_destroy (struct UnionEvaluateOperation *eo);
+const struct SetVT *
+_GSS_union_vt (void);
 
 
 /**
 
 
 /**
- * Dispatch messages for a union operation.
+ * Get the table with implementing functions for set intersection.
  *
  *
- * @param cls closure
- * @param tunnel mesh tunnel
- * @param tunnel_ctx tunnel context
- * @param mh message to process
- * @return ???
+ * @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
 int
-_GSS_union_handle_p2p_message (void *cls,
-                               struct GNUNET_MESH_Tunnel *tunnel,
-                               void **tunnel_ctx,
-                               const struct GNUNET_MessageHeader *mh);
+_GSS_is_element_of_operation (struct ElementEntry *ee,
+                              struct Operation *op);
 
 
 #endif
 
 
 #endif
Unnamed repository; edit this file 'description' to name the repository.