src/set/gnunet-service-set.h

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