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