aboutsummaryrefslogtreecommitdiff
path: root/src/rps/rps-sampler_common.h
blob: 1abe43720841eaa56ccb3ad1307fbf365462def1 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
/*
     This file is part of GNUnet.
     Copyright (C)

     GNUnet is free software: you can redistribute it and/or modify it
     under the terms of the GNU Affero General Public License as published
     by the Free Software Foundation, either version 3 of the License,
     or (at your option) any later version.

     GNUnet is distributed in the hope that it will be useful, but
     WITHOUT ANY WARRANTY; without even the implied warranty of
     MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
     Affero General Public License for more details.

     You should have received a copy of the GNU Affero General Public License
     along with this program.  If not, see <http://www.gnu.org/licenses/>.

     SPDX-License-Identifier: AGPL3.0-or-later
*/

/**
 * @file rps/rps-sampler_common.h
 * @brief Code common to client and service sampler
 * @author Julius Bünger
 */

#ifndef RPS_SAMPLER_COMMON_H
#define RPS_SAMPLER_COMMON_H

#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_statistics_service.h"

#include "gnunet-service-rps_sampler_elem.h"

#include <math.h>
#include <inttypes.h>

#include "rps-test_util.h"


/**
 * Callback that is called from _get_rand_peer() when the PeerID is ready.
 *
 * @param cls the closure given alongside this function.
 * @param id the PeerID that was returned
 */
typedef void
(*RPS_sampler_rand_peer_ready_cont) (void *cls,
                                     const struct GNUNET_PeerIdentity *id);


/**
 * Type of function used to differentiate between modified and not modified
 * Sampler.
 */
typedef void
(*RPS_get_peers_type) (void *cls);


/**
 * Callback that is called from _get_n_rand_peers() when the PeerIDs are ready.
 *
 * @param cls the closure given alongside this function.
 * @param ids the PeerIDs that were returned
 *        to be freed
 */
  typedef void
(*RPS_sampler_n_rand_peers_ready_cb) (const struct GNUNET_PeerIdentity *ids,
                                      uint32_t num_peers,
                                      void *cls);


/**
 * @brief Callback called each time a new peer was put into the sampler
 *
 * @param cls A possibly given closure
 */
typedef void
(*SamplerNotifyUpdateCB) (void *cls);


/**
 * Closure for #sampler_mod_get_rand_peer() and #sampler_get_rand_peer
 */
struct GetPeerCls
{
  /**
   * DLL
   */
  struct GetPeerCls *next;
  struct GetPeerCls *prev;

  /**
   * The #RPS_SamplerRequestHandle this single request belongs to.
   */
  struct RPS_SamplerRequestHandle *req_handle;

  /**
   * The task for this function.
   */
  struct GNUNET_SCHEDULER_Task *get_peer_task;

  /**
   * @brief Context to the given callback.
   */
  struct SamplerNotifyUpdateCTX *notify_ctx;

  /**
   * The callback
   */
  RPS_sampler_rand_peer_ready_cont cont;

  /**
   * The closure to the callback @e cont
   */
  void *cont_cls;

  /**
   * The address of the id to be stored at
   */
  struct GNUNET_PeerIdentity *id;
};


/**
 * Sampler with its own array of SamplerElements
 */
struct RPS_Sampler
{
  /**
   * Number of sampler elements we hold.
   */
  unsigned int sampler_size;
  //size_t size;

  /**
   * All sampler elements in one array.
   */
  struct RPS_SamplerElement **sampler_elements;

  /**
   * Maximum time a round takes
   *
   * Used in the context of RPS
   */
  struct GNUNET_TIME_Relative max_round_interval;

  /**
   * @brief The estimated total number of peers in the network
   */
  uint32_t num_peers_estim;

  /**
   * @brief The desired probability with which we want to have observed all
   * peers.
   */
  double desired_probability;

  /**
   * @brief A factor that catches the 'bias' of a random stream of peer ids.
   *
   * As introduced by Brahms: Factor between the number of unique ids in a
   * truly random stream and number of unique ids in the gossip stream.
   */
  double deficiency_factor;

  /**
   * Stores the function to return peers. Which one it is depends on whether
   * the Sampler is the modified one or not.
   */
  RPS_get_peers_type get_peers;

  /**
   * Head and tail for the DLL to store the #RPS_SamplerRequestHandle
   */
  struct RPS_SamplerRequestHandle *req_handle_head;
  struct RPS_SamplerRequestHandle *req_handle_tail;

  struct SamplerNotifyUpdateCTX *notify_ctx_head;
  struct SamplerNotifyUpdateCTX *notify_ctx_tail;
};


/**
 * @brief Update the current estimate of the network size stored at the sampler
 *
 * Used for computing the condition when to return elements to the client
 *
 * @param sampler The sampler to update
 * @param num_peers The estimated value
 */
void
RPS_sampler_update_with_nw_size (struct RPS_Sampler *sampler,
                                 uint32_t num_peers);


/**
 * @brief Set the probability that is needed at least with what a sampler
 * element has to have observed all elements from the network.
 *
 * Only used/useful with the client sampler
 * (Maybe move to rps-sampler_client.{h|c} ?)
 *
 * @param sampler
 * @param desired_probability
 */
void
RPS_sampler_set_desired_probability (struct RPS_Sampler *sampler,
                                     double desired_probability);


/**
 * @brief Set the deficiency factor.
 *
 * Only used/useful with the client sampler
 * (Maybe move to rps-sampler_client.{h|c} ?)
 *
 * @param sampler
 * @param desired_probability
 */
void
RPS_sampler_set_deficiency_factor (struct RPS_Sampler *sampler,
                                   double deficiency_factor);


/**
 * @brief Add a callback that will be called when the next peer is inserted
 * into the sampler
 *
 * @param sampler The sampler on which update it will be called
 * @param notify_cb The callback
 * @param cls Closure given to the callback
 *
 * @return The context containing callback and closure
 */
struct SamplerNotifyUpdateCTX *
sampler_notify_on_update (struct RPS_Sampler *sampler,
                          SamplerNotifyUpdateCB notify_cb,
                          void *cls);


/**
 * Update every sampler element of this sampler with given peer
 *
 * @param sampler the sampler to update.
 * @param id the PeerID that is put in the sampler
 */
  void
RPS_sampler_update (struct RPS_Sampler *sampler,
                    const struct GNUNET_PeerIdentity *id);


/**
 * Reinitialise all previously initialised sampler elements with the given value.
 *
 * Used to get rid of a PeerID.
 *
 * @param sampler the sampler to reinitialise a sampler element in.
 * @param id the id of the sampler elements to update.
 */
  void
RPS_sampler_reinitialise_by_value (struct RPS_Sampler *sampler,
                                   const struct GNUNET_PeerIdentity *id);


/**
 * Get the size of the sampler.
 *
 * @param sampler the sampler to return the size of.
 * @return the size of the sampler
 */
unsigned int
RPS_sampler_get_size (struct RPS_Sampler *sampler);


/**
 * Grow or shrink the size of the sampler.
 *
 * @param sampler the sampler to resize.
 * @param new_size the new size of the sampler
 */
void
RPS_sampler_resize (struct RPS_Sampler *sampler, unsigned int new_size);


/**
 * Get n random peers out of the sampled peers.
 *
 * We might want to reinitialise this sampler after giving the
 * corrsponding peer to the client.
 * Random with or without consumption?
 *
 * @param sampler the sampler to get peers from.
 * @param cb callback that will be called once the ids are ready.
 * @param cls closure given to @a cb
 * @param for_client #GNUNET_YES if result is used for client,
 *                   #GNUNET_NO if used internally
 * @param num_peers the number of peers requested
 */
struct RPS_SamplerRequestHandle *
RPS_sampler_get_n_rand_peers (struct RPS_Sampler *sampler,
                              uint32_t num_peers,
                              RPS_sampler_n_rand_peers_ready_cb cb,
                              void *cls);


/**
 * Counts how many Samplers currently hold a given PeerID.
 *
 * @param sampler the sampler to count ids in.
 * @param id the PeerID to count.
 *
 * @return the number of occurrences of id.
 */
  uint32_t
RPS_sampler_count_id (struct RPS_Sampler *sampler,
                      const struct GNUNET_PeerIdentity *id);


/**
 * Cancle a request issued through #RPS_sampler_n_rand_peers_ready_cb.
 *
 * @param req_handle the handle to the request
 */
void
RPS_sampler_request_cancel (struct RPS_SamplerRequestHandle *req_handle);


/**
 * Cleans the sampler.
 */
  void
RPS_sampler_destroy (struct RPS_Sampler *sampler);

#endif /* RPS_SAMPLER_COMMON_H */
/* end of rps-sampler_common.h */