projects / oweals / gnunet.git / blobdiff
? search:
summary | shortlog | log | commit | commitdiff | tree
raw | inline | side by side
improve logging, indentation
[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 ae28b24c2e7ce75f453ba900e639289e8be75b5a..86313d17966c4182023f56ac51d807129e0bfa2a 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 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
 
       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,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
 
       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_mesh_service.h"
+#include "gnunet_cadet_service.h"
 #include "gnunet_set_service.h"
 #include "set.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;
 
  */
 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;
 
  */
 struct OperationState;
 
-
-/* forward declarations */
+/**
+ * A set that supports a specific operation with other peers.
+ */
 struct Set;
 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;
 
 struct ElementEntry;
 
+/**
+ * Operation context used to execute a set operation.
+ */
+struct Operation;
+
 
 /**
  * Detail information about an operation.
  */
 struct OperationSpecification
 {
 
 /**
  * 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;
 
    */
   struct GNUNET_PeerIdentity peer;
 
@@ -86,33 +89,71 @@ struct OperationSpecification
    */
   struct GNUNET_MessageHeader *context_msg;
 
    */
   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;
 
   /**
   /**
    * 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;
 
   /**
    */
   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.
  *
 
 
 /**
  * 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
  * 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
  */
  *
  * @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
  */
  *
  * @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
 {
  */
 struct SetVT
 {
@@ -206,12 +249,12 @@ struct SetVT
   /**
    * Callback for accepting a set operation request
    */
   /**
    * Callback for accepting a set operation request
    */
-  OpCreateImpl accept;
+  OpAcceptImpl accept;
 
   /**
    * Callback for starting evaluation with a remote peer.
    */
 
   /**
    * Callback for starting evaluation with a remote peer.
    */
-  OpCreateImpl evaluate;
+  OpEvaluateImpl evaluate;
 
   /**
    * Callback for destruction of the set state.
 
   /**
    * Callback for destruction of the set state.
@@ -219,34 +262,45 @@ struct SetVT
   DestroySetImpl destroy_set;
 
   /**
   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
  * fast.
  */
 struct ElementEntry
@@ -258,68 +312,212 @@ struct ElementEntry
   struct GNUNET_SET_Element element;
 
   /**
   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;
 
   /**
    */
   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;
 };
 
 
    * 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;
 
   /**
    */
   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;
 
    */
   struct Set *next;
 
@@ -328,6 +526,26 @@ struct Set
    */
   struct Set *prev;
 
    */
   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.
    */
   /**
    * Implementation-specific state.
    */
@@ -340,43 +558,97 @@ struct Set
   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
 
   /**
   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;
    */
   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);
 
 
  */
 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
 #endif
Unnamed repository; edit this file 'description' to name the repository.