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      SPDX-License-Identifier: AGPL3.0-or-later
  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  * Signature of functions that create the implementation-specific
  72  * state for a set supporting a specific operation.
  73  *
  74  * @return a set state specific to the supported operation, NULL on error
  75  */
  76 typedef struct SetState *
  77 (*SetCreateImpl) (void);
  78
  79
  80 /**
  81  * Signature of functions that implement the add/remove functionality
  82  * for a set supporting a specific operation.
  83  *
  84  * @param set implementation-specific set state
  85  * @param ee element message from the client
  86  */
  87 typedef void
  88 (*SetAddRemoveImpl) (struct SetState *state,
  89                      struct ElementEntry *ee);
  90
  91
  92 /**
  93  * Make a copy of a set's internal state.
  94  *
  95  * @param state set state to copy
  96  * @return copy of the internal state
  97  */
  98 typedef struct SetState *
  99 (*SetCopyStateImpl) (struct SetState *state);
 100
 101
 102 /**
 103  * Signature of functions that implement the destruction of the
 104  * implementation-specific set state.
 105  *
 106  * @param state the set state, contains implementation-specific data
 107  */
 108 typedef void
 109 (*SetDestroyImpl) (struct SetState *state);
 110
 111
 112 /**
 113  * Signature of functions that implement accepting a set operation.
 114  *
 115  * @param op operation that is created by accepting the operation,
 116  *        should be initialized by the implementation
 117  * @return operation-specific state to keep in @a op
 118  */
 119 typedef struct OperationState *
 120 (*OpAcceptImpl) (struct Operation *op);
 121
 122
 123 /**
 124  * Signature of functions that implement starting the evaluation of
 125  * set operations.
 126  *
 127  * @param op operation that is created, should be initialized to
 128  *        begin the evaluation
 129  * @param opaque_context message to be transmitted to the listener
 130  *        to convince it to accept, may be NULL
 131  * @return operation-specific state to keep in @a op
 132  */
 133 typedef struct OperationState *
 134 (*OpEvaluateImpl) (struct Operation *op,
 135                    const struct GNUNET_MessageHeader *opaque_context);
 136
 137 /**
 138  * Signature of functions that implement operation cancelation.
 139  * This includes notifying the client about the operation's final
 140  * state.
 141  *
 142  * @param op operation state
 143  */
 144 typedef void
 145 (*OpCancelImpl) (struct Operation *op);
 146
 147
 148 /**
 149  * Signature of functions called when the CADET channel died.
 150  *
 151  * @param op operation state
 152  */
 153 typedef void
 154 (*OpChannelDeathImpl) (struct Operation *op);
 155
 156
 157 /**
 158  * Dispatch table for a specific set operation.  Every set operation
 159  * has to implement the callback in this struct.
 160  */
 161 struct SetVT
 162 {
 163   /**
 164    * Callback for the set creation.
 165    */
 166   SetCreateImpl create;
 167
 168   /**
 169    * Callback for element insertion
 170    */
 171   SetAddRemoveImpl add;
 172
 173   /**
 174    * Callback for element removal.
 175    */
 176   SetAddRemoveImpl remove;
 177
 178   /**
 179    * Callback for making a copy of a set's internal state.
 180    */
 181   SetCopyStateImpl copy_state;
 182
 183   /**
 184    * Callback for destruction of the set state.
 185    */
 186   SetDestroyImpl destroy_set;
 187
 188   /**
 189    * Callback for accepting a set operation request
 190    */
 191   OpAcceptImpl accept;
 192
 193   /**
 194    * Callback for starting evaluation with a remote peer.
 195    */
 196   OpEvaluateImpl evaluate;
 197
 198   /**
 199    * Callback for canceling an operation.
 200    */
 201   OpCancelImpl cancel;
 202
 203   /**
 204    * Callback called in case the CADET channel died.
 205    */
 206   OpChannelDeathImpl channel_death;
 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  * Operation context used to execute a set operation.
 312  */
 313 struct Operation
 314 {
 315   /**
 316    * Kept in a DLL of the listener, if @e listener is non-NULL.
 317    */
 318   struct Operation *next;
 319
 320   /**
 321    * Kept in a DLL of the listener, if @e listener is non-NULL.
 322    */
 323   struct Operation *prev;
 324
 325   /**
 326    * Channel to the peer.
 327    */
 328   struct GNUNET_CADET_Channel *channel;
 329
 330   /**
 331    * Port this operation runs on.
 332    */
 333   struct Listener *listener;
 334
 335   /**
 336    * Message queue for the channel.
 337    */
 338   struct GNUNET_MQ_Handle *mq;
 339
 340   /**
 341    * Context message, may be NULL.
 342    */
 343   struct GNUNET_MessageHeader *context_msg;
 344
 345   /**
 346    * Set associated with the operation, NULL until the spec has been
 347    * associated with a set.
 348    */
 349   struct Set *set;
 350
 351   /**
 352    * Operation-specific operation state.  Note that the exact
 353    * type depends on this being a union or intersection operation
 354    * (and thus on @e vt).
 355    */
 356   struct OperationState *state;
 357
 358   /**
 359    * The identity of the requesting peer.  Needs to
 360    * be stored here as the op spec might not have been created yet.
 361    */
 362   struct GNUNET_PeerIdentity peer;
 363
 364   /**
 365    * Timeout task, if the incoming peer has not been accepted
 366    * after the timeout, it will be disconnected.
 367    */
 368   struct GNUNET_SCHEDULER_Task *timeout_task;
 369
 370   /**
 371    * Salt to use for the operation.
 372    */
 373   uint32_t salt;
 374
 375   /**
 376    * Remote peers element count
 377    */
 378   uint32_t remote_element_count;
 379
 380   /**
 381    * ID used to identify an operation between service and client
 382    */
 383   uint32_t client_request_id;
 384
 385   /**
 386    * When are elements sent to the client, and which elements are sent?
 387    */
 388   enum GNUNET_SET_ResultMode result_mode;
 389
 390   /**
 391    * Always use delta operation instead of sending full sets,
 392    * even it it's less efficient.
 393    */
 394   int force_delta;
 395
 396   /**
 397    * Always send full sets, even if delta operations would
 398    * be more efficient.
 399    */
 400   int force_full;
 401
 402   /**
 403    * #GNUNET_YES to fail operations where Byzantine faults
 404    * are suspected
 405    */
 406   int byzantine;
 407
 408   /**
 409    * Lower bound for the set size, used only when
 410    * byzantine mode is enabled.
 411    */
 412   int byzantine_lower_bound;
 413
 414   /**
 415    * Unique request id for the request from a remote peer, sent to the
 416    * client, which will accept or reject the request.  Set to '0' iff
 417    * the request has not been suggested yet.
 418    */
 419   uint32_t suggest_id;
 420
 421   /**
 422    * Generation in which the operation handle
 423    * was created.
 424    */
 425   unsigned int generation_created;
 426 };
 427
 428
 429 /**
 430  * SetContent stores the actual set elements, which may be shared by
 431  * multiple generations derived from one set.
 432  */
 433 struct SetContent
 434 {
 435   /**
 436    * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
 437    */
 438   struct GNUNET_CONTAINER_MultiHashMap *elements;
 439
 440   /**
 441    * Mutations requested by the client that we're
 442    * unable to execute right now because we're iterating
 443    * over the underlying hash map of elements.
 444    */
 445   struct PendingMutation *pending_mutations_head;
 446
 447   /**
 448    * Mutations requested by the client that we're
 449    * unable to execute right now because we're iterating
 450    * over the underlying hash map of elements.
 451    */
 452   struct PendingMutation *pending_mutations_tail;
 453
 454   /**
 455    * Number of references to the content.
 456    */
 457   unsigned int refcount;
 458
 459   /**
 460    * FIXME: document!
 461    */
 462   unsigned int latest_generation;
 463
 464   /**
 465    * Number of concurrently active iterators.
 466    */
 467   int iterator_count;
 468 };
 469
 470
 471 struct GenerationRange
 472 {
 473   /**
 474    * First generation that is excluded.
 475    */
 476   unsigned int start;
 477
 478   /**
 479    * Generation after the last excluded generation.
 480    */
 481   unsigned int end;
 482 };
 483
 484
 485 /**
 486  * Information about a mutation to apply to a set.
 487  */
 488 struct PendingMutation
 489 {
 490   /**
 491    * Mutations are kept in a DLL.
 492    */
 493   struct PendingMutation *prev;
 494
 495   /**
 496    * Mutations are kept in a DLL.
 497    */
 498   struct PendingMutation *next;
 499
 500   /**
 501    * Set this mutation is about.
 502    */
 503   struct Set *set;
 504
 505   /**
 506    * Message that describes the desired mutation.
 507    * May only be a #GNUNET_MESSAGE_TYPE_SET_ADD or
 508    * #GNUNET_MESSAGE_TYPE_SET_REMOVE.
 509    */
 510   struct GNUNET_SET_ElementMessage *msg;
 511 };
 512
 513
 514 /**
 515  * A set that supports a specific operation with other peers.
 516  */
 517 struct Set
 518 {
 519   /**
 520    * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`).
 521    */
 522   struct Set *next;
 523
 524   /**
 525    * Sets are held in a doubly linked list.
 526    */
 527   struct Set *prev;
 528
 529   /**
 530    * Client that owns the set.  Only one client may own a set,
 531    * and there can only be one set per client.
 532    */
 533   struct ClientState *cs;
 534
 535   /**
 536    * Content, possibly shared by multiple sets,
 537    * and thus reference counted.
 538    */
 539   struct SetContent *content;
 540
 541   /**
 542    * Virtual table for this set.  Determined by the operation type of
 543    * this set.
 544    *
 545    * Used only for Add/remove of elements and when receiving an incoming
 546    * operation from a remote peer.
 547    */
 548   const struct SetVT *vt;
 549
 550   /**
 551    * Implementation-specific state.
 552    */
 553   struct SetState *state;
 554
 555   /**
 556    * Current state of iterating elements for the client.
 557    * NULL if we are not currently iterating.
 558    */
 559   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
 560
 561   /**
 562    * Evaluate operations are held in a linked list.
 563    */
 564   struct Operation *ops_head;
 565
 566   /**
 567    * Evaluate operations are held in a linked list.
 568    */
 569   struct Operation *ops_tail;
 570
 571   /**
 572    * List of generations we have to exclude, due to lazy copies.
 573    */
 574   struct GenerationRange *excluded_generations;
 575
 576   /**
 577    * Current generation, that is, number of previously executed
 578    * operations and lazy copies on the underlying set content.
 579    */
 580   unsigned int current_generation;
 581
 582   /**
 583    * Number of elements in array @a excluded_generations.
 584    */
 585   unsigned int excluded_generations_size;
 586
 587   /**
 588    * Type of operation supported for this set
 589    */
 590   enum GNUNET_SET_OperationType operation;
 591
 592   /**
 593    * Generation we're currently iteration over.
 594    */
 595   unsigned int iter_generation;
 596
 597   /**
 598    * Each @e iter is assigned a unique number, so that the client
 599    * can distinguish iterations.
 600    */
 601   uint16_t iteration_id;
 602 };
 603
 604
 605 extern struct GNUNET_STATISTICS_Handle *_GSS_statistics;
 606
 607
 608 /**
 609  * Destroy the given operation.   Used for any operation where both
 610  * peers were known and that thus actually had a vt and channel.  Must
 611  * not be used for operations where 'listener' is still set and we do
 612  * not know the other peer.
 613  *
 614  * Call the implementation-specific cancel function of the operation.
 615  * Disconnects from the remote peer.  Does not disconnect the client,
 616  * as there may be multiple operations per set.
 617  *
 618  * @param op operation to destroy
 619  * @param gc #GNUNET_YES to perform garbage collection on the set
 620  */
 621 void
 622 _GSS_operation_destroy (struct Operation *op,
 623                         int gc);
 624
 625
 626 /**
 627  * This function probably should not exist
 628  * and be replaced by inlining more specific
 629  * logic in the various places where it is called.
 630  */
 631 void
 632 _GSS_operation_destroy2 (struct Operation *op);
 633
 634
 635 /**
 636  * Get the table with implementing functions for set union.
 637  *
 638  * @return the operation specific VTable
 639  */
 640 const struct SetVT *
 641 _GSS_union_vt (void);
 642
 643
 644 /**
 645  * Get the table with implementing functions for set intersection.
 646  *
 647  * @return the operation specific VTable
 648  */
 649 const struct SetVT *
 650 _GSS_intersection_vt (void);
 651
 652
 653 /**
 654  * Is element @a ee part of the set used by @a op?
 655  *
 656  * @param ee element to test
 657  * @param op operation the defines the set and its generation
 658  * @return #GNUNET_YES if the element is in the set, #GNUNET_NO if not
 659  */
 660 int
 661 _GSS_is_element_of_operation (struct ElementEntry *ee,
 662                               struct Operation *op);
 663
 664
 665 #endif