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 /**
 159  * Dispatch table for a specific set operation.  Every set operation
 160  * has to implement the callback in this struct.
 161  */
 162 struct SetVT {
 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    * First generation affected by this mutation event.
 217    *
 218    * If @a generation is 0, this mutation event is a list
 219    * sentinel element.
 220    */
 221   unsigned int generation;
 222
 223   /**
 224    * If @a added is #GNUNET_YES, then this is a
 225    * `remove` event, otherwise it is an `add` event.
 226    */
 227   int added;
 228 };
 229
 230
 231 /**
 232  * Information about an element element in the set.  All elements are
 233  * stored in a hash-table from their hash-code to their `struct
 234  * Element`, so that the remove and add operations are reasonably
 235  * fast.
 236  */
 237 struct ElementEntry {
 238   /**
 239    * The actual element. The data for the element
 240    * should be allocated at the end of this struct.
 241    */
 242   struct GNUNET_SET_Element element;
 243
 244   /**
 245    * Hash of the element.  For set union: Will be used to derive the
 246    * different IBF keys for different salts.
 247    */
 248   struct GNUNET_HashCode element_hash;
 249
 250   /**
 251    * If @a mutations is not NULL, it contains
 252    * a list of mutations, ordered by increasing generation.
 253    * The list is terminated by a sentinel event with `generation`
 254    * set to 0.
 255    *
 256    * If @a mutations is NULL, then this element exists in all generations
 257    * of the respective set content this element belongs to.
 258    */
 259   struct MutationEvent *mutations;
 260
 261   /**
 262    * Number of elements in the array @a mutations.
 263    */
 264   unsigned int mutations_size;
 265
 266   /**
 267    * #GNUNET_YES if the element is a remote element, and does not belong
 268    * to the operation's set.
 269    */
 270   int remote;
 271 };
 272
 273
 274 /**
 275  * A listener is inhabited by a client, and waits for evaluation
 276  * requests from remote peers.
 277  */
 278 struct Listener;
 279
 280
 281 /**
 282  * State we keep per client.
 283  */
 284 struct ClientState {
 285   /**
 286    * Set, if associated with the client, otherwise NULL.
 287    */
 288   struct Set *set;
 289
 290   /**
 291    * Listener, if associated with the client, otherwise NULL.
 292    */
 293   struct Listener *listener;
 294
 295   /**
 296    * Client handle.
 297    */
 298   struct GNUNET_SERVICE_Client *client;
 299
 300   /**
 301    * Message queue.
 302    */
 303   struct GNUNET_MQ_Handle *mq;
 304 };
 305
 306
 307 /**
 308  * Operation context used to execute a set operation.
 309  */
 310 struct Operation {
 311   /**
 312    * Kept in a DLL of the listener, if @e listener is non-NULL.
 313    */
 314   struct Operation *next;
 315
 316   /**
 317    * Kept in a DLL of the listener, if @e listener is non-NULL.
 318    */
 319   struct Operation *prev;
 320
 321   /**
 322    * Channel to the peer.
 323    */
 324   struct GNUNET_CADET_Channel *channel;
 325
 326   /**
 327    * Port this operation runs on.
 328    */
 329   struct Listener *listener;
 330
 331   /**
 332    * Message queue for the channel.
 333    */
 334   struct GNUNET_MQ_Handle *mq;
 335
 336   /**
 337    * Context message, may be NULL.
 338    */
 339   struct GNUNET_MessageHeader *context_msg;
 340
 341   /**
 342    * Set associated with the operation, NULL until the spec has been
 343    * associated with a set.
 344    */
 345   struct Set *set;
 346
 347   /**
 348    * Operation-specific operation state.  Note that the exact
 349    * type depends on this being a union or intersection operation
 350    * (and thus on @e vt).
 351    */
 352   struct OperationState *state;
 353
 354   /**
 355    * The identity of the requesting peer.  Needs to
 356    * be stored here as the op spec might not have been created yet.
 357    */
 358   struct GNUNET_PeerIdentity peer;
 359
 360   /**
 361    * Timeout task, if the incoming peer has not been accepted
 362    * after the timeout, it will be disconnected.
 363    */
 364   struct GNUNET_SCHEDULER_Task *timeout_task;
 365
 366   /**
 367    * Salt to use for the operation.
 368    */
 369   uint32_t salt;
 370
 371   /**
 372    * Remote peers element count
 373    */
 374   uint32_t remote_element_count;
 375
 376   /**
 377    * ID used to identify an operation between service and client
 378    */
 379   uint32_t client_request_id;
 380
 381   /**
 382    * When are elements sent to the client, and which elements are sent?
 383    */
 384   enum GNUNET_SET_ResultMode result_mode;
 385
 386   /**
 387    * Always use delta operation instead of sending full sets,
 388    * even it it's less efficient.
 389    */
 390   int force_delta;
 391
 392   /**
 393    * Always send full sets, even if delta operations would
 394    * be more efficient.
 395    */
 396   int force_full;
 397
 398   /**
 399    * #GNUNET_YES to fail operations where Byzantine faults
 400    * are suspected
 401    */
 402   int byzantine;
 403
 404   /**
 405    * Lower bound for the set size, used only when
 406    * byzantine mode is enabled.
 407    */
 408   int byzantine_lower_bound;
 409
 410   /**
 411    * Unique request id for the request from a remote peer, sent to the
 412    * client, which will accept or reject the request.  Set to '0' iff
 413    * the request has not been suggested yet.
 414    */
 415   uint32_t suggest_id;
 416
 417   /**
 418    * Generation in which the operation handle
 419    * was created.
 420    */
 421   unsigned int generation_created;
 422 };
 423
 424
 425 /**
 426  * SetContent stores the actual set elements, which may be shared by
 427  * multiple generations derived from one set.
 428  */
 429 struct SetContent {
 430   /**
 431    * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
 432    */
 433   struct GNUNET_CONTAINER_MultiHashMap *elements;
 434
 435   /**
 436    * Mutations requested by the client that we're
 437    * unable to execute right now because we're iterating
 438    * over the underlying hash map of elements.
 439    */
 440   struct PendingMutation *pending_mutations_head;
 441
 442   /**
 443    * Mutations requested by the client that we're
 444    * unable to execute right now because we're iterating
 445    * over the underlying hash map of elements.
 446    */
 447   struct PendingMutation *pending_mutations_tail;
 448
 449   /**
 450    * Number of references to the content.
 451    */
 452   unsigned int refcount;
 453
 454   /**
 455    * FIXME: document!
 456    */
 457   unsigned int latest_generation;
 458
 459   /**
 460    * Number of concurrently active iterators.
 461    */
 462   int iterator_count;
 463 };
 464
 465
 466 struct GenerationRange {
 467   /**
 468    * First generation that is excluded.
 469    */
 470   unsigned int start;
 471
 472   /**
 473    * Generation after the last excluded generation.
 474    */
 475   unsigned int end;
 476 };
 477
 478
 479 /**
 480  * Information about a mutation to apply to a set.
 481  */
 482 struct PendingMutation {
 483   /**
 484    * Mutations are kept in a DLL.
 485    */
 486   struct PendingMutation *prev;
 487
 488   /**
 489    * Mutations are kept in a DLL.
 490    */
 491   struct PendingMutation *next;
 492
 493   /**
 494    * Set this mutation is about.
 495    */
 496   struct Set *set;
 497
 498   /**
 499    * Message that describes the desired mutation.
 500    * May only be a #GNUNET_MESSAGE_TYPE_SET_ADD or
 501    * #GNUNET_MESSAGE_TYPE_SET_REMOVE.
 502    */
 503   struct GNUNET_SET_ElementMessage *msg;
 504 };
 505
 506
 507 /**
 508  * A set that supports a specific operation with other peers.
 509  */
 510 struct Set {
 511   /**
 512    * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`).
 513    */
 514   struct Set *next;
 515
 516   /**
 517    * Sets are held in a doubly linked list.
 518    */
 519   struct Set *prev;
 520
 521   /**
 522    * Client that owns the set.  Only one client may own a set,
 523    * and there can only be one set per client.
 524    */
 525   struct ClientState *cs;
 526
 527   /**
 528    * Content, possibly shared by multiple sets,
 529    * and thus reference counted.
 530    */
 531   struct SetContent *content;
 532
 533   /**
 534    * Virtual table for this set.  Determined by the operation type of
 535    * this set.
 536    *
 537    * Used only for Add/remove of elements and when receiving an incoming
 538    * operation from a remote peer.
 539    */
 540   const struct SetVT *vt;
 541
 542   /**
 543    * Implementation-specific state.
 544    */
 545   struct SetState *state;
 546
 547   /**
 548    * Current state of iterating elements for the client.
 549    * NULL if we are not currently iterating.
 550    */
 551   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
 552
 553   /**
 554    * Evaluate operations are held in a linked list.
 555    */
 556   struct Operation *ops_head;
 557
 558   /**
 559    * Evaluate operations are held in a linked list.
 560    */
 561   struct Operation *ops_tail;
 562
 563   /**
 564    * List of generations we have to exclude, due to lazy copies.
 565    */
 566   struct GenerationRange *excluded_generations;
 567
 568   /**
 569    * Current generation, that is, number of previously executed
 570    * operations and lazy copies on the underlying set content.
 571    */
 572   unsigned int current_generation;
 573
 574   /**
 575    * Number of elements in array @a excluded_generations.
 576    */
 577   unsigned int excluded_generations_size;
 578
 579   /**
 580    * Type of operation supported for this set
 581    */
 582   enum GNUNET_SET_OperationType operation;
 583
 584   /**
 585    * Generation we're currently iteration over.
 586    */
 587   unsigned int iter_generation;
 588
 589   /**
 590    * Each @e iter is assigned a unique number, so that the client
 591    * can distinguish iterations.
 592    */
 593   uint16_t iteration_id;
 594 };
 595
 596
 597 extern struct GNUNET_STATISTICS_Handle *_GSS_statistics;
 598
 599
 600 /**
 601  * Destroy the given operation.   Used for any operation where both
 602  * peers were known and that thus actually had a vt and channel.  Must
 603  * not be used for operations where 'listener' is still set and we do
 604  * not know the other peer.
 605  *
 606  * Call the implementation-specific cancel function of the operation.
 607  * Disconnects from the remote peer.  Does not disconnect the client,
 608  * as there may be multiple operations per set.
 609  *
 610  * @param op operation to destroy
 611  * @param gc #GNUNET_YES to perform garbage collection on the set
 612  */
 613 void
 614 _GSS_operation_destroy(struct Operation *op,
 615                        int gc);
 616
 617
 618 /**
 619  * This function probably should not exist
 620  * and be replaced by inlining more specific
 621  * logic in the various places where it is called.
 622  */
 623 void
 624 _GSS_operation_destroy2(struct Operation *op);
 625
 626
 627 /**
 628  * Get the table with implementing functions for set union.
 629  *
 630  * @return the operation specific VTable
 631  */
 632 const struct SetVT *
 633 _GSS_union_vt(void);
 634
 635
 636 /**
 637  * Get the table with implementing functions for set intersection.
 638  *
 639  * @return the operation specific VTable
 640  */
 641 const struct SetVT *
 642 _GSS_intersection_vt(void);
 643
 644
 645 /**
 646  * Is element @a ee part of the set used by @a op?
 647  *
 648  * @param ee element to test
 649  * @param op operation the defines the set and its generation
 650  * @return #GNUNET_YES if the element is in the set, #GNUNET_NO if not
 651  */
 652 int
 653 _GSS_is_element_of_operation(struct ElementEntry *ee,
 654                              struct Operation *op);
 655
 656
 657 #endif