GNUnet  0.20.0
rps-sampler_client.c
Go to the documentation of this file.
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 
26 #include "platform.h"
27 #include "gnunet_util_lib.h"
29 #include "rps.h"
30 
31 #include "rps-sampler_common.h"
34 
35 #include <math.h>
36 #include <inttypes.h>
37 
38 #include "rps-test_util.h"
39 
40 #define LOG(kind, ...) GNUNET_log_from (kind, "rps-sampler", __VA_ARGS__)
41 
42 
43 // multiple 'clients'?
44 
45 // TODO check for overflows
46 
47 // TODO align message structs
48 
49 // hist_size_init, hist_size_max
50 
51 /***********************************************************************
52 * WARNING: This section needs to be reviewed regarding the use of
53 * functions providing (pseudo)randomness!
54 ***********************************************************************/
55 
56 // TODO care about invalid input of the caller (size 0 or less...)
57 
63 typedef void
64 (*SamplerNotifyUpdateCB) (void *cls);
65 
72 {
77 
81  void *cls;
82 
87 
92 };
93 
94 
99 typedef void
100 (*RPS_get_peers_type) (void *cls);
101 
102 
109 static void
111 
112 
117 {
123 
127  uint32_t num_peers;
128 
132  uint32_t cur_num_peers;
133 
137  struct GNUNET_PeerIdentity *ids;
138 
142  struct GetPeerCls *gpc_head;
143  struct GetPeerCls *gpc_tail;
144 
148  struct RPS_Sampler *sampler;
149 
154 
158  void *cls;
159 };
160 
161 
166 {
172 
177 
183 
188 
193 
197  void *cls;
198 };
199 
200 
202 // * Global sampler variable.
203 // */
204 // struct RPS_Sampler *sampler;
205 
206 
210 static size_t min_size;
211 
215 static size_t max_size;
216 
220 // static size_t extra_size;
221 
225 static uint32_t client_get_index;
226 
227 
235 struct RPS_Sampler *
236 RPS_sampler_mod_init (size_t init_size,
238 {
239  struct RPS_Sampler *sampler;
240 
241  /* Initialise context around extended sampler */
242  min_size = 10; // TODO make input to _samplers_init()
243  max_size = 1000; // TODO make input to _samplers_init()
244 
245  sampler = GNUNET_new (struct RPS_Sampler);
248  // sampler->sampler_elements = GNUNET_new_array(init_size, struct GNUNET_PeerIdentity);
249  // GNUNET_array_grow (sampler->sampler_elements, sampler->sampler_size, min_size);
250 
251  client_get_index = 0;
252 
253  // GNUNET_assert (init_size == sampler->sampler_size);
254 
255  RPS_sampler_resize (sampler, init_size);
256 
257  return sampler;
258 }
259 
260 
261 // /**
262 // * @brief Compute the probability that we already observed all peers from a
263 // * biased stream of peer ids.
264 // *
265 // * Deficiency factor:
266 // * As introduced by Brahms: Factor between the number of unique ids in a
267 // * truly random stream and number of unique ids in the gossip stream.
268 // *
269 // * @param num_peers_estim The estimated number of peers in the network
270 // * @param num_peers_observed The number of peers the given element has observed
271 // * @param deficiency_factor A factor that catches the 'bias' of a random stream
272 // * of peer ids
273 // *
274 // * @return The estimated probability
275 // */
276 // static double
277 // prob_observed_n_peers (uint32_t num_peers_estim,
278 // uint32_t num_peers_observed,
279 // double deficiency_factor)
280 // {
281 // uint32_t num_peers = num_peers_estim * (1 / deficiency_factor);
282 // uint64_t sum = 0;
283 //
284 // for (uint32_t i = 0; i < num_peers; i++)
285 // {
286 // uint64_t a = pow (-1, num_peers - i);
287 // uint64_t b = binom (num_peers, i);
288 // uint64_t c = pow (i, num_peers_observed);
289 // sum += a * b * c;
290 // }
291 //
292 // return sum / (double) pow (num_peers, num_peers_observed);
293 // }
294 
295 
301 static void
303 {
304  struct GetPeerCls *gpc = cls;
305  struct RPS_SamplerElement *s_elem;
306  struct GNUNET_TIME_Relative last_request_diff;
307  struct RPS_Sampler *sampler;
308  double prob_observed_n;
309  uint32_t num_observed;
310 
311  gpc->get_peer_task = NULL;
312  gpc->notify_ctx = NULL;
313  GNUNET_assert ((NULL != gpc->req_handle) ||
314  (NULL != gpc->req_single_info_handle));
315  if (NULL != gpc->req_handle)
316  sampler = gpc->req_handle->sampler;
317  else
318  sampler = gpc->req_single_info_handle->sampler;
319 
320  LOG (GNUNET_ERROR_TYPE_DEBUG, "Single peer was requested\n");
321 
322  /* Cycle the #client_get_index one step further */
324 
325  s_elem = sampler->sampler_elements[client_get_index];
326  *gpc->id = s_elem->peer_id;
327  GNUNET_assert (NULL != s_elem);
328 
329  if (EMPTY == s_elem->is_empty)
330  {
332  "Sampler_mod element empty, rescheduling.\n");
333  GNUNET_assert (NULL == gpc->notify_ctx);
334  gpc->notify_ctx =
335  sampler_notify_on_update (sampler,
337  gpc);
338  return;
339  }
340 
341  /* Check whether we may use this sampler to give it back to the client */
342  if (GNUNET_TIME_UNIT_FOREVER_ABS.abs_value_us !=
344  {
345  // TODO remove this condition at least for the client sampler
346  last_request_diff =
349  /* We're not going to give it back now if it was
350  * already requested by a client this round */
351  if (last_request_diff.rel_value_us <
353  {
355  "Last client request on this sampler was less than max round interval ago -- scheduling for later\n");
357  // inv_last_request_diff =
358  // GNUNET_TIME_absolute_get_difference (last_request_diff,
359  // sampler->max_round_interval);
360  // add a little delay
361  /* Schedule it one round later */
362  GNUNET_assert (NULL == gpc->notify_ctx);
363  gpc->notify_ctx =
364  sampler_notify_on_update (sampler,
366  gpc);
367  return;
368  }
369  }
370  if (2 > s_elem->num_peers)
371  {
373  "This s_elem saw less than two peers -- scheduling for later\n");
374  GNUNET_assert (NULL == gpc->notify_ctx);
375  gpc->notify_ctx =
376  sampler_notify_on_update (sampler,
378  gpc);
379  return;
380  }
381  /* compute probability */
382  /* FIXME: Currently disabled due to numerical limitations */
383  prob_observed_n = 0; // Inititialise to some value
384  // prob_observed_n = prob_observed_n_peers (sampler->num_peers_estim,
385  // s_elem->num_peers,
386  // sampler->deficiency_factor);
387  // LOG (GNUNET_ERROR_TYPE_DEBUG,
388  // "Computed sample - prob %f, %" PRIu32 " peers, n: %" PRIu32 ", roh: %f\n",
389  // prob_observed_n,
390  // s_elem->num_peers,
391  // sampler->num_peers_estim,
392  // sampler->deficiency_factor);
394  // if (prob_observed_n < sampler->desired_probability)
395  // {
396  // LOG (GNUNET_ERROR_TYPE_DEBUG,
397  // "Probability of having observed all peers (%f) too small ( < %f).\n",
398  // prob_observed_n,
399  // sampler->desired_probability);
400  // GNUNET_assert (NULL == gpc->notify_ctx);
401  // gpc->notify_ctx =
402  // sampler_notify_on_update (sampler,
403  // &sampler_mod_get_rand_peer,
404  // gpc);
405  // return;
406  // }
407  /* More reasons to wait could be added here */
408 
409 // GNUNET_STATISTICS_set (stats,
410 // "# client sampler element input",
411 // s_elem->num_peers,
412 // GNUNET_NO);
413 // GNUNET_STATISTICS_set (stats,
414 // "# client sampler element change",
415 // s_elem->num_change,
416 // GNUNET_NO);
417 
418  num_observed = s_elem->num_peers;
419  RPS_sampler_elem_reinit (s_elem);
421 
422  if (NULL != gpc->req_handle)
423  {
425  gpc->req_handle->gpc_tail,
426  gpc);
427  }
428  else
429  {
432  gpc);
433  }
434  gpc->cont (gpc->cont_cls, gpc->id, prob_observed_n, num_observed);
435  GNUNET_free (gpc);
436 }
437 
438 
439 /* end of gnunet-service-rps.c */
sampler implementation
void RPS_sampler_resize(struct RPS_Sampler *sampler, unsigned int new_size)
Grow or shrink the size of the sampler.
void RPS_sampler_elem_reinit(struct RPS_SamplerElement *sampler_elem)
Reinitialise a previously initialised sampler element.
sampler element implementation
API to create, modify and access statistics.
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_free(ptr)
Wrapper around free.
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:111
struct GNUNET_TIME_Relative GNUNET_TIME_absolute_get_difference(struct GNUNET_TIME_Absolute start, struct GNUNET_TIME_Absolute end)
Compute the time difference between the given start and end times.
Definition: time.c:421
#define GNUNET_TIME_UNIT_FOREVER_ABS
Constant used to specify "forever".
void(* RPS_get_peers_type)(void *cls)
Type of function used to differentiate between modified and not modified Sampler.
struct RPS_Sampler * RPS_sampler_mod_init(size_t init_size, struct GNUNET_TIME_Relative max_round_interval)
Initialise a modified tuple of sampler elements.
void(* SamplerNotifyUpdateCB)(void *cls)
Callback called each time a new peer was put into the sampler.
static uint32_t client_get_index
The size the extended sampler elements currently have.
static void sampler_mod_get_rand_peer(void *cls)
Get one random peer out of the sampled peers.
#define LOG(kind,...)
static size_t max_size
The maximal size the extended sampler elements should grow to.
static size_t min_size
‍**
struct SamplerNotifyUpdateCTX * sampler_notify_on_update(struct RPS_Sampler *sampler, SamplerNotifyUpdateCB notify_cb, void *cls)
Add a callback that will be called when the next peer is inserted into the sampler.
Code common to client and service sampler.
void(* RPS_sampler_n_rand_peers_ready_cb)(const struct GNUNET_PeerIdentity *ids, uint32_t num_peers, void *cls)
Callback that is called from _get_n_rand_peers() when the PeerIDs are ready.
void(* RPS_sampler_sinlge_info_ready_cb)(const struct GNUNET_PeerIdentity *ids, void *cls, double probability, uint32_t num_observed)
Callback that is called from _get_n_rand_peers() when the PeerIDs are ready.
Some utils facilitating the view into the internals for the sampler needed for evaluation.
example IPC messages between RPS API and GNS service
The identity of the host (wraps the signing key of the peer).
uint64_t abs_value_us
The actual value.
Time for relative time used by GNUnet, in microseconds.
uint64_t rel_value_us
The actual value.
Closure for sampler_mod_get_rand_peer() and sampler_get_rand_peer.
struct RPS_SamplerRequestHandleSingleInfo * req_single_info_handle
The RPS_SamplerRequestHandleSingleInfo this single request belongs to.
struct SamplerNotifyUpdateCTX * notify_ctx
Context to the given callback.
struct GNUNET_PeerIdentity * id
The address of the id to be stored at.
RPS_sampler_rand_peer_ready_cont cont
The callback.
struct RPS_SamplerRequestHandle * req_handle
The RPS_SamplerRequestHandle this single request belongs to.
struct GNUNET_SCHEDULER_Task * get_peer_task
The task for this function.
void * cont_cls
The closure to the callback cont.
A sampler element sampling one PeerID at a time.
struct GNUNET_TIME_Absolute last_client_request
Time of last request.
uint32_t num_peers
How many times a PeerID was put in this sampler.
struct GNUNET_PeerIdentity peer_id
The PeerID this sampler currently samples.
enum RPS_SamplerEmpty is_empty
Flag that indicates that we are not holding a valid PeerID right now.
Closure to _get_rand_peer_info()
void * cls
Closure given to the callback.
struct RPS_Sampler * sampler
Sampler.
struct RPS_SamplerRequestHandleSingleInfo * next
DLL.
struct RPS_SamplerRequestHandleSingleInfo * prev
RPS_sampler_sinlge_info_ready_cb callback
Callback to be called when all ids are available.
struct GetPeerCls * gpc_head
Head and tail for the DLL to store the tasks for single requests.
struct GNUNET_PeerIdentity * id
Pointer to the id.
Closure to _get_n_rand_peers_ready_cb()
struct RPS_Sampler * sampler
Sampler.
struct RPS_SamplerRequestHandle * prev
RPS_sampler_n_rand_peers_ready_cb callback
Callback to be called when all ids are available.
uint32_t num_peers
Number of peers we are waiting for.
struct GNUNET_PeerIdentity * ids
Pointer to the array holding the ids.
struct GetPeerCls * gpc_head
Head and tail for the DLL to store the tasks for single requests.
struct RPS_SamplerRequestHandle * next
DLL.
void * cls
Closure given to the callback.
uint32_t cur_num_peers
Number of peers we currently have.
Sampler with its own array of SamplerElements.
RPS_get_peers_type get_peers
Stores the function to return peers.
struct RPS_SamplerElement ** sampler_elements
All sampler elements in one array.
struct GNUNET_TIME_Relative max_round_interval
Maximum time a round takes.
unsigned int sampler_size
Number of sampler elements we hold.
struct SamplerNotifyUpdateCTX * prev
Previous element in DLL.
struct SamplerNotifyUpdateCTX * next
Next element in DLL.
SamplerNotifyUpdateCB notify_cb
The Callback to call on updates.
void * cls
The according closure.