src/rps/rps-sampler_common.h

   1 /*
   2      This file is part of GNUnet.
   3      Copyright (C)
   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 /**
  22  * @file rps/rps-sampler_common.h
  23  * @brief Code common to client and service sampler
  24  * @author Julius Bünger
  25  */
  26
  27 #ifndef RPS_SAMPLER_COMMON_H
  28 #define RPS_SAMPLER_COMMON_H
  29
  30 #include "platform.h"
  31 #include "gnunet_util_lib.h"
  32 #include "gnunet_statistics_service.h"
  33
  34 #include "gnunet-service-rps_sampler_elem.h"
  35
  36 #include <math.h>
  37 #include <inttypes.h>
  38
  39 #include "rps-test_util.h"
  40
  41
  42 /**
  43  * Callback that is called from _get_rand_peer() when the PeerID is ready.
  44  *
  45  * @param cls the closure given alongside this function.
  46  * @param id the PeerID that was returned
  47  * @param probability The probability with which this sampler has seen all ids
  48  * @param num_observed How many ids this sampler has observed
  49  */
  50 typedef void
  51 (*RPS_sampler_rand_peer_ready_cont) (void *cls,
  52                                      const struct GNUNET_PeerIdentity *id,
  53                                      double probability,
  54                                      uint32_t num_observed);
  55
  56
  57 /**
  58  * Type of function used to differentiate between modified and not modified
  59  * Sampler.
  60  */
  61 typedef void
  62 (*RPS_get_peers_type) (void *cls);
  63
  64
  65 /**
  66  * Callback that is called from _get_n_rand_peers() when the PeerIDs are ready.
  67  *
  68  * @param cls the closure given alongside this function.
  69  * @param ids the PeerIDs that were returned
  70  *        to be freed
  71  */
  72 typedef void
  73 (*RPS_sampler_n_rand_peers_ready_cb) (const struct GNUNET_PeerIdentity *ids,
  74                                       uint32_t num_peers,
  75                                       void *cls);
  76
  77
  78 /**
  79  * Callback that is called from _get_n_rand_peers() when the PeerIDs are ready.
  80  *
  81  * @param cls the closure given alongside this function.
  82  * @param probability Probability with which all IDs have been observed
  83  * @param num_observed Number of observed IDs
  84  * @param ids the PeerIDs that were returned
  85  *        to be freed
  86  */
  87 typedef void
  88 (*RPS_sampler_sinlge_info_ready_cb) (const struct GNUNET_PeerIdentity *ids,
  89                                      void *cls,
  90                                      double probability,
  91                                      uint32_t num_observed);
  92
  93
  94 /**
  95  * @brief Callback called each time a new peer was put into the sampler
  96  *
  97  * @param cls A possibly given closure
  98  */
  99 typedef void
 100 (*SamplerNotifyUpdateCB) (void *cls);
 101
 102
 103 /**
 104  * Closure for #sampler_mod_get_rand_peer() and #sampler_get_rand_peer
 105  */
 106 struct GetPeerCls
 107 {
 108   /**
 109    * DLL
 110    */
 111   struct GetPeerCls *next;
 112   struct GetPeerCls *prev;
 113
 114   /**
 115    * The #RPS_SamplerRequestHandle this single request belongs to.
 116    */
 117   struct RPS_SamplerRequestHandle *req_handle;
 118
 119   /**
 120    * The #RPS_SamplerRequestHandleSingleInfo this single request belongs to.
 121    */
 122   struct RPS_SamplerRequestHandleSingleInfo *req_single_info_handle;
 123
 124   /**
 125    * The task for this function.
 126    */
 127   struct GNUNET_SCHEDULER_Task *get_peer_task;
 128
 129   /**
 130    * @brief Context to the given callback.
 131    */
 132   struct SamplerNotifyUpdateCTX *notify_ctx;
 133
 134   /**
 135    * The callback
 136    */
 137   RPS_sampler_rand_peer_ready_cont cont;
 138
 139   /**
 140    * The closure to the callback @e cont
 141    */
 142   void *cont_cls;
 143
 144   /**
 145    * The address of the id to be stored at
 146    */
 147   struct GNUNET_PeerIdentity *id;
 148 };
 149
 150
 151 /**
 152  * Sampler with its own array of SamplerElements
 153  */
 154 struct RPS_Sampler
 155 {
 156   /**
 157    * Number of sampler elements we hold.
 158    */
 159   unsigned int sampler_size;
 160   // size_t size;
 161
 162   /**
 163    * All sampler elements in one array.
 164    */
 165   struct RPS_SamplerElement **sampler_elements;
 166
 167   /**
 168    * Maximum time a round takes
 169    *
 170    * Used in the context of RPS
 171    */
 172   struct GNUNET_TIME_Relative max_round_interval;
 173
 174   /**
 175    * @brief The estimated total number of peers in the network
 176    */
 177   uint32_t num_peers_estim;
 178
 179   /**
 180    * @brief The desired probability with which we want to have observed all
 181    * peers.
 182    */
 183   double desired_probability;
 184
 185   /**
 186    * @brief A factor that catches the 'bias' of a random stream of peer ids.
 187    *
 188    * As introduced by Brahms: Factor between the number of unique ids in a
 189    * truly random stream and number of unique ids in the gossip stream.
 190    */
 191   double deficiency_factor;
 192
 193   /**
 194    * Stores the function to return peers. Which one it is depends on whether
 195    * the Sampler is the modified one or not.
 196    */
 197   RPS_get_peers_type get_peers;
 198
 199   /**
 200    * Head and tail for the DLL to store the #RPS_SamplerRequestHandle
 201    */
 202   struct RPS_SamplerRequestHandle *req_handle_head;
 203   struct RPS_SamplerRequestHandle *req_handle_tail;
 204
 205   /**
 206    * Head and tail for the DLL to store the #RPS_SamplerRequestHandleSingleInfo
 207    */
 208   struct RPS_SamplerRequestHandleSingleInfo *req_handle_single_head;
 209   struct RPS_SamplerRequestHandleSingleInfo *req_handle_single_tail;
 210
 211   struct SamplerNotifyUpdateCTX *notify_ctx_head;
 212   struct SamplerNotifyUpdateCTX *notify_ctx_tail;
 213 };
 214
 215
 216 /**
 217  * @brief Update the current estimate of the network size stored at the sampler
 218  *
 219  * Used for computing the condition when to return elements to the client
 220  *
 221  * @param sampler The sampler to update
 222  * @param num_peers The estimated value
 223  */
 224 void
 225 RPS_sampler_update_with_nw_size (struct RPS_Sampler *sampler,
 226                                  uint32_t num_peers);
 227
 228
 229 /**
 230  * @brief Set the probability that is needed at least with what a sampler
 231  * element has to have observed all elements from the network.
 232  *
 233  * Only used/useful with the client sampler
 234  * (Maybe move to rps-sampler_client.{h|c} ?)
 235  *
 236  * @param sampler
 237  * @param desired_probability
 238  */
 239 void
 240 RPS_sampler_set_desired_probability (struct RPS_Sampler *sampler,
 241                                      double desired_probability);
 242
 243
 244 /**
 245  * @brief Set the deficiency factor.
 246  *
 247  * Only used/useful with the client sampler
 248  * (Maybe move to rps-sampler_client.{h|c} ?)
 249  *
 250  * @param sampler
 251  * @param desired_probability
 252  */
 253 void
 254 RPS_sampler_set_deficiency_factor (struct RPS_Sampler *sampler,
 255                                    double deficiency_factor);
 256
 257
 258 /**
 259  * @brief Add a callback that will be called when the next peer is inserted
 260  * into the sampler
 261  *
 262  * @param sampler The sampler on which update it will be called
 263  * @param notify_cb The callback
 264  * @param cls Closure given to the callback
 265  *
 266  * @return The context containing callback and closure
 267  */
 268 struct SamplerNotifyUpdateCTX *
 269 sampler_notify_on_update (struct RPS_Sampler *sampler,
 270                           SamplerNotifyUpdateCB notify_cb,
 271                           void *cls);
 272
 273
 274 /**
 275  * Update every sampler element of this sampler with given peer
 276  *
 277  * @param sampler the sampler to update.
 278  * @param id the PeerID that is put in the sampler
 279  */
 280 void
 281 RPS_sampler_update (struct RPS_Sampler *sampler,
 282                     const struct GNUNET_PeerIdentity *id);
 283
 284
 285 /**
 286  * Reinitialise all previously initialised sampler elements with the given value.
 287  *
 288  * Used to get rid of a PeerID.
 289  *
 290  * @param sampler the sampler to reinitialise a sampler element in.
 291  * @param id the id of the sampler elements to update.
 292  */
 293 void
 294 RPS_sampler_reinitialise_by_value (struct RPS_Sampler *sampler,
 295                                    const struct GNUNET_PeerIdentity *id);
 296
 297
 298 /**
 299  * Get the size of the sampler.
 300  *
 301  * @param sampler the sampler to return the size of.
 302  * @return the size of the sampler
 303  */
 304 unsigned int
 305 RPS_sampler_get_size (struct RPS_Sampler *sampler);
 306
 307
 308 /**
 309  * Grow or shrink the size of the sampler.
 310  *
 311  * @param sampler the sampler to resize.
 312  * @param new_size the new size of the sampler
 313  */
 314 void
 315 RPS_sampler_resize (struct RPS_Sampler *sampler, unsigned int new_size);
 316
 317
 318 /**
 319  * Get n random peers out of the sampled peers.
 320  *
 321  * We might want to reinitialise this sampler after giving the
 322  * corrsponding peer to the client.
 323  * Random with or without consumption?
 324  *
 325  * @param sampler the sampler to get peers from.
 326  * @param cb callback that will be called once the ids are ready.
 327  * @param cls closure given to @a cb
 328  * @param for_client #GNUNET_YES if result is used for client,
 329  *                   #GNUNET_NO if used internally
 330  * @param num_peers the number of peers requested
 331  */
 332 struct RPS_SamplerRequestHandle *
 333 RPS_sampler_get_n_rand_peers (struct RPS_Sampler *sampler,
 334                               uint32_t num_peers,
 335                               RPS_sampler_n_rand_peers_ready_cb cb,
 336                               void *cls);
 337
 338
 339 /**
 340  * Get one random peer with additional information.
 341  *
 342  * @param sampler the sampler to get peers from.
 343  * @param cb callback that will be called once the ids are ready.
 344  * @param cls closure given to @a cb
 345  */
 346 struct RPS_SamplerRequestHandleSingleInfo *
 347 RPS_sampler_get_rand_peer_info (struct RPS_Sampler *sampler,
 348                                 RPS_sampler_sinlge_info_ready_cb cb,
 349                                 void *cls);
 350
 351
 352 /**
 353  * Counts how many Samplers currently hold a given PeerID.
 354  *
 355  * @param sampler the sampler to count ids in.
 356  * @param id the PeerID to count.
 357  *
 358  * @return the number of occurrences of id.
 359  */
 360 uint32_t
 361 RPS_sampler_count_id (struct RPS_Sampler *sampler,
 362                       const struct GNUNET_PeerIdentity *id);
 363
 364
 365 /**
 366  * Cancle a request issued through #RPS_sampler_n_rand_peers_ready_cb.
 367  *
 368  * @param req_handle the handle to the request
 369  */
 370 void
 371 RPS_sampler_request_cancel (struct RPS_SamplerRequestHandle *req_handle);
 372
 373
 374 /**
 375  * Cancle a request issued through #RPS_sampler_n_rand_peers_ready_cb.
 376  *
 377  * @param req_handle the handle to the request
 378  */
 379 void
 380 RPS_sampler_request_single_info_cancel (
 381   struct RPS_SamplerRequestHandleSingleInfo *req_single_info_handle);
 382
 383
 384 /**
 385  * Cleans the sampler.
 386  */
 387 void
 388 RPS_sampler_destroy (struct RPS_Sampler *sampler);
 389
 390 #endif /* RPS_SAMPLER_COMMON_H */
 391 /* end of rps-sampler_common.h */