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