src/set/gnunet-service-set.h

   1 /*
   2       This file is part of GNUnet
   3       Copyright (C) 2013, 2014 GNUnet e.V.
   4
   5       GNUnet is free software; you can redistribute it and/or modify
   6       it under the terms of the GNU General Public License as published
   7       by the Free Software Foundation; either version 3, or (at your
   8       option) any later version.
   9
  10       GNUnet is distributed in the hope that it will be useful, but
  11       WITHOUT ANY WARRANTY; without even the implied warranty of
  12       MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13       General Public License for more details.
  14
  15       You should have received a copy of the GNU General Public License
  16       along with GNUnet; see the file COPYING.  If not, write to the
  17       Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  18       Boston, MA 02110-1301, USA.
  19 */
  20 /**
  21  * @file set/gnunet-service-set.h
  22  * @brief common components for the implementation the different set operations
  23  * @author Florian Dold
  24  * @author Christian Grothoff
  25  */
  26 #ifndef GNUNET_SERVICE_SET_H_PRIVATE
  27 #define GNUNET_SERVICE_SET_H_PRIVATE
  28
  29 #include "platform.h"
  30 #include "gnunet_util_lib.h"
  31 #include "gnunet_protocols.h"
  32 #include "gnunet_applications.h"
  33 #include "gnunet_core_service.h"
  34 #include "gnunet_cadet_service.h"
  35 #include "gnunet_set_service.h"
  36 #include "set.h"
  37
  38
  39 /**
  40  * Implementation-specific set state.  Used as opaque pointer, and
  41  * specified further in the respective implementation.
  42  */
  43 struct SetState;
  44
  45 /**
  46  * Implementation-specific set operation.  Used as opaque pointer, and
  47  * specified further in the respective implementation.
  48  */
  49 struct OperationState;
  50
  51 /**
  52  * A set that supports a specific operation with other peers.
  53  */
  54 struct Set;
  55
  56 /**
  57  * Information about an element element in the set.  All elements are
  58  * stored in a hash-table from their hash-code to their 'struct
  59  * Element', so that the remove and add operations are reasonably
  60  * fast.
  61  */
  62 struct ElementEntry;
  63
  64 /**
  65  * Operation context used to execute a set operation.
  66  */
  67 struct Operation;
  68
  69
  70 /**
  71  * Detail information about an operation.
  72  */
  73 struct OperationSpecification
  74 {
  75
  76   /**
  77    * The remove peer we evaluate the operation with.
  78    */
  79   struct GNUNET_PeerIdentity peer;
  80
  81   /**
  82    * Application ID for the operation, used to distinguish
  83    * multiple operations of the same type with the same peer.
  84    */
  85   struct GNUNET_HashCode app_id;
  86
  87   /**
  88    * Context message, may be NULL.
  89    */
  90   struct GNUNET_MessageHeader *context_msg;
  91
  92   /**
  93    * Set associated with the operation, NULL until the spec has been
  94    * associated with a set.
  95    */
  96   struct Set *set;
  97
  98   /**
  99    * Salt to use for the operation.
 100    */
 101   uint32_t salt;
 102
 103   /**
 104    * Remote peers element count
 105    */
 106   uint32_t remote_element_count;
 107
 108   /**
 109    * ID used to identify an operation between service and client
 110    */
 111   uint32_t client_request_id;
 112
 113   /**
 114    * The type of the operation.
 115    */
 116   enum GNUNET_SET_OperationType operation;
 117
 118   /**
 119    * When are elements sent to the client, and which elements are sent?
 120    */
 121   enum GNUNET_SET_ResultMode result_mode;
 122
 123   /**
 124    * Always use delta operation instead of sending full sets,
 125    * even it it's less efficient.
 126    */
 127   int force_delta;
 128
 129   /**
 130    * Always send full sets, even if delta operations would
 131    * be more efficient.
 132    */
 133   int force_full;
 134
 135   /**
 136    * #GNUNET_YES to fail operations where Byzantine faults
 137    * are suspected
 138    */
 139   int byzantine;
 140
 141   /**
 142    * Lower bound for the set size, used only when
 143    * byzantine mode is enabled.
 144    */
 145   int byzantine_lower_bound;
 146 };
 147
 148
 149 /**
 150  * Signature of functions that create the implementation-specific
 151  * state for a set supporting a specific operation.
 152  *
 153  * @return a set state specific to the supported operation, NULL on error
 154  */
 155 typedef struct SetState *
 156 (*CreateImpl) (void);
 157
 158
 159 /**
 160  * Signature of functions that implement the add/remove functionality
 161  * for a set supporting a specific operation.
 162  *
 163  * @param set implementation-specific set state
 164  * @param ee element message from the client
 165  */
 166 typedef void
 167 (*AddRemoveImpl) (struct SetState *state,
 168                   struct ElementEntry *ee);
 169
 170
 171 /**
 172  * Signature of functions that handle disconnection of the remote
 173  * peer.
 174  *
 175  * @param op the set operation, contains implementation-specific data
 176  */
 177 typedef void
 178 (*PeerDisconnectImpl) (struct Operation *op);
 179
 180
 181 /**
 182  * Signature of functions that implement the destruction of the
 183  * implementation-specific set state.
 184  *
 185  * @param state the set state, contains implementation-specific data
 186  */
 187 typedef void
 188 (*DestroySetImpl) (struct SetState *state);
 189
 190
 191 /**
 192  * Signature of functions that implement accepting a set operation.
 193  *
 194  * @param op operation that is created by accepting the operation,
 195  *        should be initialized by the implementation
 196  */
 197 typedef void
 198 (*OpAcceptImpl) (struct Operation *op);
 199
 200
 201 /**
 202  * Signature of functions that implement starting the evaluation of
 203  * set operations.
 204  *
 205  * @param op operation that is created, should be initialized to
 206  *        begin the evaluation
 207  * @param opaque_context message to be transmitted to the listener
 208  *        to convince him to accept, may be NULL
 209  */
 210 typedef void
 211 (*OpEvaluateImpl) (struct Operation *op,
 212                    const struct GNUNET_MessageHeader *opaque_context);
 213
 214
 215 /**
 216  * Signature of functions that implement operation cancellation
 217  *
 218  * @param op operation state
 219  */
 220 typedef void
 221 (*CancelImpl) (struct Operation *op);
 222
 223
 224 typedef struct SetState *
 225 (*CopyStateImpl) (struct Set *op);
 226
 227
 228 /**
 229  * Dispatch table for a specific set operation.  Every set operation
 230  * has to implement the callback in this struct.
 231  */
 232 struct SetVT
 233 {
 234   /**
 235    * Callback for the set creation.
 236    */
 237   CreateImpl create;
 238
 239   /**
 240    * Callback for element insertion
 241    */
 242   AddRemoveImpl add;
 243
 244   /**
 245    * Callback for element removal.
 246    */
 247   AddRemoveImpl remove;
 248
 249   /**
 250    * Callback for accepting a set operation request
 251    */
 252   OpAcceptImpl accept;
 253
 254   /**
 255    * Callback for starting evaluation with a remote peer.
 256    */
 257   OpEvaluateImpl evaluate;
 258
 259   /**
 260    * Callback for destruction of the set state.
 261    */
 262   DestroySetImpl destroy_set;
 263
 264   /**
 265    * Callback for handling the remote peer's disconnect.
 266    */
 267   PeerDisconnectImpl peer_disconnect;
 268
 269   /**
 270    * Callback for canceling an operation by its ID.
 271    */
 272   CancelImpl cancel;
 273
 274   CopyStateImpl copy_state;
 275 };
 276
 277
 278 /**
 279  * MutationEvent gives information about changes
 280  * to an element (removal / addition) in a set content.
 281  */
 282 struct MutationEvent
 283 {
 284   /**
 285    * First generation affected by this mutation event.
 286    *
 287    * If @a generation is 0, this mutation event is a list
 288    * sentinel element.
 289    */
 290   unsigned int generation;
 291
 292   /**
 293    * If @a added is #GNUNET_YES, then this is a
 294    * `remove` event, otherwise it is an `add` event.
 295    */
 296   int added;
 297 };
 298
 299
 300 /**
 301  * Information about an element element in the set.  All elements are
 302  * stored in a hash-table from their hash-code to their `struct
 303  * Element`, so that the remove and add operations are reasonably
 304  * fast.
 305  */
 306 struct ElementEntry
 307 {
 308   /**
 309    * The actual element. The data for the element
 310    * should be allocated at the end of this struct.
 311    */
 312   struct GNUNET_SET_Element element;
 313
 314   /**
 315    * Hash of the element.  For set union: Will be used to derive the
 316    * different IBF keys for different salts.
 317    */
 318   struct GNUNET_HashCode element_hash;
 319
 320   /**
 321    * If @a mutations is not NULL, it contains
 322    * a list of mutations, ordered by increasing generation.
 323    * The list is terminated by a sentinel event with `generation`
 324    * set to 0.
 325    *
 326    * If @a mutations is NULL, then this element exists in all generations
 327    * of the respective set content this element belongs to.
 328    */
 329   struct MutationEvent *mutations;
 330
 331   /**
 332    * Number of elements in the array @a mutations.
 333    */
 334   unsigned int mutations_size;
 335
 336   /**
 337    * #GNUNET_YES if the element is a remote element, and does not belong
 338    * to the operation's set.
 339    */
 340   int remote;
 341 };
 342
 343
 344 struct Listener;
 345
 346
 347 /**
 348  * Possible set operations.
 349  */
 350 enum OperationType {
 351   /**
 352    * Operation type unknown.
 353    */
 354   OT_UNKNOWN = 0,
 355
 356   /**
 357    * We are performing a union.
 358    */
 359   OT_UNION,
 360
 361   /**
 362    * We are performing an intersection.
 363    */
 364   OT_INTERSECTION
 365 };
 366
 367
 368 /**
 369  * Operation context used to execute a set operation.
 370  */
 371 struct Operation
 372 {
 373   /**
 374    * V-Table for the operation belonging to the tunnel contest.
 375    *
 376    * Used for all operation specific operations after receiving the ops request
 377    */
 378   const struct SetVT *vt;
 379
 380   /**
 381    * Channel to the peer.
 382    */
 383   struct GNUNET_CADET_Channel *channel;
 384
 385   /**
 386    * Port this operation runs on.
 387    */
 388   struct Listener *listener;
 389
 390   /**
 391    * Message queue for the channel.
 392    */
 393   struct GNUNET_MQ_Handle *mq;
 394
 395   /**
 396    * Detail information about the set operation, including the set to
 397    * use.  When 'spec' is NULL, the operation is not yet entirely
 398    * initialized.
 399    */
 400   struct OperationSpecification *spec;
 401
 402   /**
 403    * Operation-specific operation state.  Note that the exact
 404    * type depends on this being a union or intersection operation
 405    * (and thus on @e vt).
 406    */
 407   struct OperationState *state;
 408
 409   /**
 410    * Evaluate operations are held in a linked list.
 411    */
 412   struct Operation *next;
 413
 414   /**
 415    * Evaluate operations are held in a linked list.
 416    */
 417   struct Operation *prev;
 418
 419   /**
 420    * The identity of the requesting peer.  Needs to
 421    * be stored here as the op spec might not have been created yet.
 422    */
 423   struct GNUNET_PeerIdentity peer;
 424
 425   /**
 426    * Timeout task, if the incoming peer has not been accepted
 427    * after the timeout, it will be disconnected.
 428    */
 429   struct GNUNET_SCHEDULER_Task *timeout_task;
 430
 431   /**
 432    * What type of operation is this?
 433    */
 434   enum OperationType type;
 435
 436   /**
 437    * Unique request id for the request from a remote peer, sent to the
 438    * client, which will accept or reject the request.  Set to '0' iff
 439    * the request has not been suggested yet.
 440    */
 441   uint32_t suggest_id;
 442
 443   /**
 444    * #GNUNET_YES if this is not a "real" set operation yet, and we still
 445    * need to wait for the other peer to give us more details.
 446    */
 447   int is_incoming;
 448
 449   /**
 450    * Generation in which the operation handle
 451    * was created.
 452    */
 453   unsigned int generation_created;
 454
 455   /**
 456    * Incremented whenever (during shutdown) some component still
 457    * needs to do something with this before the operation is freed.
 458    * (Used as a reference counter, but only during termination.)
 459    */
 460   unsigned int keep;
 461 };
 462
 463
 464 /**
 465  * SetContent stores the actual set elements,
 466  * which may be shared by multiple generations derived
 467  * from one set.
 468  */
 469 struct SetContent
 470 {
 471   /**
 472    * Number of references to the content.
 473    */
 474   unsigned int refcount;
 475
 476   /**
 477    * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
 478    */
 479   struct GNUNET_CONTAINER_MultiHashMap *elements;
 480
 481   unsigned int latest_generation;
 482
 483   /**
 484    * Mutations requested by the client that we're
 485    * unable to execute right now because we're iterating
 486    * over the underlying hash map of elements.
 487    */
 488   struct PendingMutation *pending_mutations_head;
 489
 490   /**
 491    * Mutations requested by the client that we're
 492    * unable to execute right now because we're iterating
 493    * over the underlying hash map of elements.
 494    */
 495   struct PendingMutation *pending_mutations_tail;
 496
 497   /**
 498    * Number of concurrently active iterators.
 499    */
 500   int iterator_count;
 501 };
 502
 503
 504 struct GenerationRange
 505 {
 506   /**
 507    * First generation that is excluded.
 508    */
 509   unsigned int start;
 510
 511   /**
 512    * Generation after the last excluded generation.
 513    */
 514   unsigned int end;
 515 };
 516
 517
 518 struct PendingMutation
 519 {
 520   struct PendingMutation *prev;
 521   struct PendingMutation *next;
 522
 523   struct Set *set;
 524
 525   /**
 526    * Message that describes the desired mutation.
 527    * May only be a #GNUNET_MESSAGE_TYPE_SET_ADD or
 528    * #GNUNET_MESSAGE_TYPE_SET_REMOVE.
 529    */
 530   struct GNUNET_MessageHeader *mutation_message;
 531 };
 532
 533
 534 /**
 535  * A set that supports a specific operation with other peers.
 536  */
 537 struct Set
 538 {
 539
 540   /**
 541    * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`).
 542    */
 543   struct Set *next;
 544
 545   /**
 546    * Sets are held in a doubly linked list.
 547    */
 548   struct Set *prev;
 549
 550   /**
 551    * Client that owns the set.  Only one client may own a set,
 552    * and there can only be one set per client.
 553    */
 554   struct GNUNET_SERVICE_Client *client;
 555
 556   /**
 557    * Message queue for the client.
 558    */
 559   struct GNUNET_MQ_Handle *client_mq;
 560
 561   /**
 562    * Virtual table for this set.  Determined by the operation type of
 563    * this set.
 564    *
 565    * Used only for Add/remove of elements and when receiving an incoming
 566    * operation from a remote peer.
 567    */
 568   const struct SetVT *vt;
 569
 570   /**
 571    * Implementation-specific state.
 572    */
 573   struct SetState *state;
 574
 575   /**
 576    * Current state of iterating elements for the client.
 577    * NULL if we are not currently iterating.
 578    */
 579   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
 580
 581   /**
 582    * Evaluate operations are held in a linked list.
 583    */
 584   struct Operation *ops_head;
 585
 586   /**
 587    * Evaluate operations are held in a linked list.
 588    */
 589   struct Operation *ops_tail;
 590
 591   /**
 592    * What type of operation is this set for?
 593    */
 594   enum OperationType type;
 595
 596   /**
 597    * Current generation, that is, number of previously executed
 598    * operations and lazy copies on the underlying set content.
 599    */
 600   unsigned int current_generation;
 601
 602   /**
 603    * List of generations we have to exclude, due to lazy copies.
 604    */
 605   struct GenerationRange *excluded_generations;
 606
 607   /**
 608    * Number of elements in array @a excluded_generations.
 609    */
 610   unsigned int excluded_generations_size;
 611
 612   /**
 613    * Type of operation supported for this set
 614    */
 615   enum GNUNET_SET_OperationType operation;
 616
 617   /**
 618    * Each @e iter is assigned a unique number, so that the client
 619    * can distinguish iterations.
 620    */
 621   uint16_t iteration_id;
 622
 623   /**
 624    * Generation we're currently iteration over.
 625    */
 626   unsigned int iter_generation;
 627
 628   /**
 629    * Content, possibly shared by multiple sets,
 630    * and thus reference counted.
 631    */
 632   struct SetContent *content;
 633 };
 634
 635
 636 extern struct GNUNET_STATISTICS_Handle *_GSS_statistics;
 637
 638
 639 /**
 640  * Destroy the given operation.  Call the implementation-specific
 641  * cancel function of the operation.  Disconnects from the remote
 642  * peer.  Does not disconnect the client, as there may be multiple
 643  * operations per set.
 644  *
 645  * @param op operation to destroy
 646  * @param gc #GNUNET_YES to perform garbage collection on the set
 647  */
 648 void
 649 _GSS_operation_destroy (struct Operation *op,
 650                         int gc);
 651
 652
 653 /**
 654  * Get the table with implementing functions for set union.
 655  *
 656  * @return the operation specific VTable
 657  */
 658 const struct SetVT *
 659 _GSS_union_vt (void);
 660
 661
 662 /**
 663  * Get the table with implementing functions for set intersection.
 664  *
 665  * @return the operation specific VTable
 666  */
 667 const struct SetVT *
 668 _GSS_intersection_vt (void);
 669
 670
 671 int
 672 _GSS_is_element_of_set (struct ElementEntry *ee,
 673                         struct Set *set);
 674
 675 int
 676 _GSS_is_element_of_operation (struct ElementEntry *ee,
 677                               struct Operation *op);
 678
 679
 680 #endif