src/set/gnunet-service-set.h

   1 /*
   2       This file is part of GNUnet
   3       Copyright (C) 2013, 2014 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  * Detail information about an operation.
  72  */
  73 struct OperationSpecification
  74 {
  75
  76   /**
  77    * The remove peer we evaluate the operation with.
  78    */
  79   struct GNUNET_PeerIdentity peer;
  80
  81   /**
  82    * Application ID for the operation, used to distinguish
  83    * multiple operations of the same type with the same peer.
  84    */
  85   struct GNUNET_HashCode app_id;
  86
  87   /**
  88    * Context message, may be NULL.
  89    */
  90   struct GNUNET_MessageHeader *context_msg;
  91
  92   /**
  93    * Set associated with the operation, NULL until the spec has been
  94    * associated with a set.
  95    */
  96   struct Set *set;
  97
  98   /**
  99    * Salt to use for the operation.
 100    */
 101   uint32_t salt;
 102
 103   /**
 104    * Remote peers element count
 105    */
 106   uint32_t remote_element_count;
 107
 108   /**
 109    * ID used to identify an operation between service and client
 110    */
 111   uint32_t client_request_id;
 112
 113   /**
 114    * The type of the operation.
 115    */
 116   enum GNUNET_SET_OperationType operation;
 117
 118   /**
 119    * When are elements sent to the client, and which elements are sent?
 120    */
 121   enum GNUNET_SET_ResultMode result_mode;
 122 };
 123
 124
 125 /**
 126  * Signature of functions that create the implementation-specific
 127  * state for a set supporting a specific operation.
 128  *
 129  * @return a set state specific to the supported operation, NULL on error
 130  */
 131 typedef struct SetState *
 132 (*CreateImpl) (void);
 133
 134
 135 /**
 136  * Signature of functions that implement the add/remove functionality
 137  * for a set supporting a specific operation.
 138  *
 139  * @param set implementation-specific set state
 140  * @param ee element message from the client
 141  */
 142 typedef void
 143 (*AddRemoveImpl) (struct SetState *state,
 144                   struct ElementEntry *ee);
 145
 146
 147 /**
 148  * Signature of functions that handle disconnection of the remote
 149  * peer.
 150  *
 151  * @param op the set operation, contains implementation-specific data
 152  */
 153 typedef void
 154 (*PeerDisconnectImpl) (struct Operation *op);
 155
 156
 157 /**
 158  * Signature of functions that implement the destruction of the
 159  * implementation-specific set state.
 160  *
 161  * @param state the set state, contains implementation-specific data
 162  */
 163 typedef void
 164 (*DestroySetImpl) (struct SetState *state);
 165
 166
 167 /**
 168  * Signature of functions that implement accepting a set operation.
 169  *
 170  * @param op operation that is created by accepting the operation,
 171  *        should be initialized by the implementation
 172  */
 173 typedef void
 174 (*OpAcceptImpl) (struct Operation *op);
 175
 176
 177 /**
 178  * Signature of functions that implement starting the evaluation of
 179  * set operations.
 180  *
 181  * @param op operation that is created, should be initialized to
 182  *        begin the evaluation
 183  * @param opaque_context message to be transmitted to the listener
 184  *        to convince him to accept, may be NULL
 185  */
 186 typedef void
 187 (*OpEvaluateImpl) (struct Operation *op,
 188                    const struct GNUNET_MessageHeader *opaque_context);
 189
 190
 191 /**
 192  * Signature of functions that implement the message handling for
 193  * the different set operations.
 194  *
 195  * @param op operation state
 196  * @param msg received message
 197  * @return #GNUNET_OK on success, #GNUNET_SYSERR to
 198  *         destroy the operation and the tunnel
 199  */
 200 typedef int
 201 (*MsgHandlerImpl) (struct Operation *op,
 202                    const struct GNUNET_MessageHeader *msg);
 203
 204
 205 /**
 206  * Signature of functions that implement operation cancellation
 207  *
 208  * @param op operation state
 209  */
 210 typedef void
 211 (*CancelImpl) (struct Operation *op);
 212
 213
 214 typedef struct SetState *
 215 (*CopyStateImpl) (struct Set *op);
 216
 217
 218 /**
 219  * Dispatch table for a specific set operation.  Every set operation
 220  * has to implement the callback in this struct.
 221  */
 222 struct SetVT
 223 {
 224   /**
 225    * Callback for the set creation.
 226    */
 227   CreateImpl create;
 228
 229   /**
 230    * Callback for element insertion
 231    */
 232   AddRemoveImpl add;
 233
 234   /**
 235    * Callback for element removal.
 236    */
 237   AddRemoveImpl remove;
 238
 239   /**
 240    * Callback for accepting a set operation request
 241    */
 242   OpAcceptImpl accept;
 243
 244   /**
 245    * Callback for starting evaluation with a remote peer.
 246    */
 247   OpEvaluateImpl evaluate;
 248
 249   /**
 250    * Callback for destruction of the set state.
 251    */
 252   DestroySetImpl destroy_set;
 253
 254   /**
 255    * Callback for handling operation-specific messages.
 256    */
 257   MsgHandlerImpl msg_handler;
 258
 259   /**
 260    * Callback for handling the remote peer's disconnect.
 261    */
 262   PeerDisconnectImpl peer_disconnect;
 263
 264   /**
 265    * Callback for canceling an operation by its ID.
 266    */
 267   CancelImpl cancel;
 268
 269   CopyStateImpl copy_state;
 270 };
 271
 272
 273 /**
 274  * MutationEvent gives information about changes
 275  * to an element (removal / addition) in a set content.
 276  */
 277 struct MutationEvent
 278 {
 279   /**
 280    * First generation affected by this mutation event.
 281    *
 282    * If @a generation is 0, this mutation event is a list
 283    * sentinel element.
 284    */
 285   unsigned int generation;
 286
 287   /**
 288    * If @a added is #GNUNET_YES, then this is a
 289    * `remove` event, otherwise it is an `add` event.
 290    */
 291   int added;
 292 };
 293
 294
 295 /**
 296  * Information about an element element in the set.  All elements are
 297  * stored in a hash-table from their hash-code to their `struct
 298  * Element`, so that the remove and add operations are reasonably
 299  * fast.
 300  */
 301 struct ElementEntry
 302 {
 303   /**
 304    * The actual element. The data for the element
 305    * should be allocated at the end of this struct.
 306    */
 307   struct GNUNET_SET_Element element;
 308
 309   /**
 310    * Hash of the element.  For set union: Will be used to derive the
 311    * different IBF keys for different salts.
 312    */
 313   struct GNUNET_HashCode element_hash;
 314
 315   /**
 316    * If @a mutations is not NULL, it contains
 317    * a list of mutations, ordered by increasing generation.
 318    * The list is terminated by a sentinel event with `generation`
 319    * set to 0.
 320    *
 321    * If @a mutations is NULL, then this element exists in all generations
 322    * of the respective set content this element belongs to.
 323    */
 324   struct MutationEvent *mutations;
 325
 326   /**
 327    * Number of elements in the array @a mutations.
 328    */
 329   unsigned int mutations_size;
 330
 331   /**
 332    * #GNUNET_YES if the element is a remote element, and does not belong
 333    * to the operation's set.
 334    */
 335   int remote;
 336 };
 337
 338
 339 /**
 340  * Operation context used to execute a set operation.
 341  */
 342 struct Operation
 343 {
 344   /**
 345    * V-Table for the operation belonging to the tunnel contest.
 346    *
 347    * Used for all operation specific operations after receiving the ops request
 348    */
 349   const struct SetVT *vt;
 350
 351   /**
 352    * Channel to the peer.
 353    */
 354   struct GNUNET_CADET_Channel *channel;
 355
 356   /**
 357    * Message queue for the channel.
 358    */
 359   struct GNUNET_MQ_Handle *mq;
 360
 361   /**
 362    * Detail information about the set operation, including the set to
 363    * use.  When 'spec' is NULL, the operation is not yet entirely
 364    * initialized.
 365    */
 366   struct OperationSpecification *spec;
 367
 368   /**
 369    * Operation-specific operation state.  Note that the exact
 370    * type depends on this being a union or intersection operation
 371    * (and thus on @e vt).
 372    */
 373   struct OperationState *state;
 374
 375   /**
 376    * Evaluate operations are held in a linked list.
 377    */
 378   struct Operation *next;
 379
 380   /**
 381    * Evaluate operations are held in a linked list.
 382    */
 383   struct Operation *prev;
 384
 385   /**
 386    * The identity of the requesting peer.  Needs to
 387    * be stored here as the op spec might not have been created yet.
 388    */
 389   struct GNUNET_PeerIdentity peer;
 390
 391   /**
 392    * Timeout task, if the incoming peer has not been accepted
 393    * after the timeout, it will be disconnected.
 394    */
 395   struct GNUNET_SCHEDULER_Task *timeout_task;
 396
 397   /**
 398    * Unique request id for the request from a remote peer, sent to the
 399    * client, which will accept or reject the request.  Set to '0' iff
 400    * the request has not been suggested yet.
 401    */
 402   uint32_t suggest_id;
 403
 404   /**
 405    * #GNUNET_YES if this is not a "real" set operation yet, and we still
 406    * need to wait for the other peer to give us more details.
 407    */
 408   int is_incoming;
 409
 410   /**
 411    * Generation in which the operation handle
 412    * was created.
 413    */
 414   unsigned int generation_created;
 415
 416   /**
 417    * Incremented whenever (during shutdown) some component still
 418    * needs to do something with this before the operation is freed.
 419    * (Used as a reference counter, but only during termination.)
 420    */
 421   unsigned int keep;
 422 };
 423
 424
 425 /**
 426  * SetContent stores the actual set elements,
 427  * which may be shared by multiple generations derived
 428  * from one set.
 429  */
 430 struct SetContent
 431 {
 432   /**
 433    * Number of references to the content.
 434    */
 435   unsigned int refcount;
 436
 437   /**
 438    * Maps `struct GNUNET_HashCode *` to `struct ElementEntry *`.
 439    */
 440   struct GNUNET_CONTAINER_MultiHashMap *elements;
 441
 442   unsigned int latest_generation;
 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 concurrently active iterators.
 460    */
 461   int iterator_count;
 462 };
 463
 464
 465 struct GenerationRange
 466 {
 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 struct PendingMutation
 480 {
 481   struct PendingMutation *prev;
 482   struct PendingMutation *next;
 483
 484   struct Set *set;
 485
 486   /**
 487    * Message that describes the desired mutation.
 488    * May only be a GNUNET_MESSAGE_TYPE_SET_ADD or
 489    * GNUNET_MESSAGE_TYPE_SET_REMOVE.
 490    */
 491   struct GNUNET_MessageHeader *mutation_message;
 492 };
 493
 494
 495 /**
 496  * A set that supports a specific operation with other peers.
 497  */
 498 struct Set
 499 {
 500
 501   /**
 502    * Sets are held in a doubly linked list (in `sets_head` and `sets_tail`).
 503    */
 504   struct Set *next;
 505
 506   /**
 507    * Sets are held in a doubly linked list.
 508    */
 509   struct Set *prev;
 510
 511   /**
 512    * Client that owns the set.  Only one client may own a set,
 513    * and there can only be one set per client.
 514    */
 515   struct GNUNET_SERVER_Client *client;
 516
 517   /**
 518    * Message queue for the client.
 519    */
 520   struct GNUNET_MQ_Handle *client_mq;
 521
 522   /**
 523    * Virtual table for this set.  Determined by the operation type of
 524    * this set.
 525    *
 526    * Used only for Add/remove of elements and when receiving an incoming
 527    * operation from a remote peer.
 528    */
 529   const struct SetVT *vt;
 530
 531   /**
 532    * Implementation-specific state.
 533    */
 534   struct SetState *state;
 535
 536   /**
 537    * Current state of iterating elements for the client.
 538    * NULL if we are not currently iterating.
 539    */
 540   struct GNUNET_CONTAINER_MultiHashMapIterator *iter;
 541
 542   /**
 543    * Evaluate operations are held in a linked list.
 544    */
 545   struct Operation *ops_head;
 546
 547   /**
 548    * Evaluate operations are held in a linked list.
 549    */
 550   struct Operation *ops_tail;
 551
 552   /**
 553    * Current generation, that is, number of previously executed
 554    * operations and lazy copies on the underlying set content.
 555    */
 556   unsigned int current_generation;
 557
 558   /**
 559    * List of generations we have to exclude, due to lazy copies.
 560    */
 561   struct GenerationRange *excluded_generations;
 562
 563   /**
 564    * Number of elements in array @a excluded_generations.
 565    */
 566   unsigned int excluded_generations_size;
 567
 568   /**
 569    * Type of operation supported for this set
 570    */
 571   enum GNUNET_SET_OperationType operation;
 572
 573   /**
 574    * Each @e iter is assigned a unique number, so that the client
 575    * can distinguish iterations.
 576    */
 577   uint16_t iteration_id;
 578
 579   /**
 580    * Generation we're currently iteration over.
 581    */
 582   unsigned int iter_generation;
 583
 584   /**
 585    * Content, possibly shared by multiple sets,
 586    * and thus reference counted.
 587    */
 588   struct SetContent *content;
 589 };
 590
 591
 592 extern struct GNUNET_STATISTICS_Handle *_GSS_statistics;
 593
 594
 595 /**
 596  * Destroy the given operation.  Call the implementation-specific
 597  * cancel function of the operation.  Disconnects from the remote
 598  * peer.  Does not disconnect the client, as there may be multiple
 599  * operations per set.
 600  *
 601  * @param op operation to destroy
 602  * @param gc #GNUNET_YES to perform garbage collection on the set
 603  */
 604 void
 605 _GSS_operation_destroy (struct Operation *op,
 606                         int gc);
 607
 608
 609 /**
 610  * Get the table with implementing functions for set union.
 611  *
 612  * @return the operation specific VTable
 613  */
 614 const struct SetVT *
 615 _GSS_union_vt (void);
 616
 617
 618 /**
 619  * Get the table with implementing functions for set intersection.
 620  *
 621  * @return the operation specific VTable
 622  */
 623 const struct SetVT *
 624 _GSS_intersection_vt (void);
 625
 626
 627 int
 628 _GSS_is_element_of_set (struct ElementEntry *ee,
 629                         struct Set *set);
 630
 631 int
 632 _GSS_is_element_of_operation (struct ElementEntry *ee,
 633                               struct Operation *op);
 634
 635
 636 #endif