GNUnet  0.11.x
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
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 
276 static double
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 */
323  client_get_index = (client_get_index + 1) % sampler->sampler_size;
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  /* Currently disabled due to numerical limitations */
383  // prob_observed_n = prob_observed_n_peers (sampler->num_peers_estim,
384  // s_elem->num_peers,
385  // sampler->deficiency_factor);
386  // LOG (GNUNET_ERROR_TYPE_DEBUG,
387  // "Computed sample - prob %f, %" PRIu32 " peers, n: %" PRIu32 ", roh: %f\n",
388  // prob_observed_n,
389  // s_elem->num_peers,
390  // sampler->num_peers_estim,
391  // sampler->deficiency_factor);
393  // if (prob_observed_n < sampler->desired_probability)
394  // {
395  // LOG (GNUNET_ERROR_TYPE_DEBUG,
396  // "Probability of having observed all peers (%f) too small ( < %f).\n",
397  // prob_observed_n,
398  // sampler->desired_probability);
399  // GNUNET_assert (NULL == gpc->notify_ctx);
400  // gpc->notify_ctx =
401  // sampler_notify_on_update (sampler,
402  // &sampler_mod_get_rand_peer,
403  // gpc);
404  // return;
405  // }
406  /* More reasons to wait could be added here */
407 
408 // GNUNET_STATISTICS_set (stats,
409 // "# client sampler element input",
410 // s_elem->num_peers,
411 // GNUNET_NO);
412 // GNUNET_STATISTICS_set (stats,
413 // "# client sampler element change",
414 // s_elem->num_change,
415 // GNUNET_NO);
416 
417  num_observed = s_elem->num_peers;
418  RPS_sampler_elem_reinit (s_elem);
420 
421  if (NULL != gpc->req_handle)
422  {
424  gpc->req_handle->gpc_tail,
425  gpc);
426  }
427  else
428  {
431  gpc);
432  }
433  gpc->cont (gpc->cont_cls, gpc->id, prob_observed_n, num_observed);
434  GNUNET_free (gpc);
435 }
436 
437 
438 /* end of gnunet-service-rps.c */
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
uint32_t num_peers
How many times a PeerID was put in this sampler.
void(* RPS_get_peers_type)(void *cls)
Type of function used to differentiate between modified and not modified Sampler. ...
uint64_t rel_value_us
The actual value.
uint32_t num_peers_estim
The estimated total number of peers in the network.
RPS_sampler_rand_peer_ready_cont cont
The callback.
struct SamplerNotifyUpdateCTX * prev
Previous element in DLL.
A sampler element sampling one PeerID at a time.
static size_t min_size
Global sampler variable.
Some utils faciliating the view into the internals for the sampler needed for evaluation.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct RPS_SamplerRequestHandleSingleInfo * prev
sampler element implementation
Code common to client and service sampler.
Context for a callback.
struct GNUNET_TIME_Absolute last_client_request
Time of last request.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
example IPC messages between RPS API and GNS service
#define LOG(kind,...)
struct RPS_SamplerRequestHandleSingleInfo * next
DLL.
void(* SamplerNotifyUpdateCB)(void *cls)
Callback called each time a new peer was put into the sampler.
void RPS_sampler_elem_reinit(struct RPS_SamplerElement *sampler_elem)
Reinitialise a previously initialised sampler element.
struct RPS_SamplerRequestHandle * req_handle
The RPS_SamplerRequestHandle this single request belongs to.
struct GNUNET_TIME_Relative max_round_interval
Maximum time a round takes.
uint64_t abs_value_us
The actual value.
static size_t max_size
The maximal size the extended sampler elements should grow to.
static double prob_observed_n_peers(uint32_t num_peers_estim, uint32_t num_peers_observed, double deficiency_factor)
Compute the probability that we already observed all peers from a biased stream of peer ids...
#define GNUNET_TIME_UNIT_FOREVER_ABS
Constant used to specify "forever".
Closure to _get_n_rand_peers_ready_cb()
struct SamplerNotifyUpdateCTX * notify_ctx
Context to the given callback.
struct SamplerNotifyUpdateCTX * next
Next element in DLL.
static uint32_t client_get_index
The size the extended sampler elements currently have.
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.
struct RPS_Sampler * sampler
Sampler.
static struct GNUNET_CONTAINER_MultiPeerMap * ids
GNUNET_PeerIdentity -> CadetPeer.
enum RPS_SamplerEmpty is_empty
Flag that indicates that we are not holding a valid PeerID right now.
struct GNUNET_PeerIdentity peer_id
The PeerID this sampler currently samples.
SamplerNotifyUpdateCB notify_cb
The Callback to call on updates.
void * cls
The according closure.
Closure to _get_rand_peer_info()
uint32_t binom(uint32_t n, uint32_t k)
Binomial coefficient (n choose k)
static void sampler_mod_get_rand_peer(void *cls)
Get one random peer out of the sampled peers.
struct GNUNET_TIME_Absolute GNUNET_TIME_absolute_get(void)
Get the current time.
Definition: time.c:118
void * cls
Closure given to the callback.
void RPS_sampler_resize(struct RPS_Sampler *sampler, unsigned int new_size)
Grow or shrink the size of the sampler.
struct GetPeerCls * gpc_head
Head and tail for the DLL to store the tasks for single requests.
sampler implementation
static unsigned int num_peers
struct GNUNET_PeerIdentity * id
Pointer to the id.
uint32_t cur_num_peers
Number of peers we currently have.
struct RPS_SamplerRequestHandleSingleInfo * req_single_info_handle
The RPS_SamplerRequestHandleSingleInfo this single request belongs to.
void * cont_cls
The closure to the callback cont.
The identity of the host (wraps the signing key of the peer).
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.
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.
Closure for sampler_mod_get_rand_peer() and sampler_get_rand_peer.
unsigned int sampler_size
Number of sampler elements we hold.
double deficiency_factor
A factor that catches the &#39;bias&#39; of a random stream of peer ids.
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:354
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.
RPS_get_peers_type get_peers
Stores the function to return peers.
struct RPS_SamplerElement ** sampler_elements
All sampler elements in one array.
Sampler with its own array of SamplerElements.
struct GNUNET_PeerIdentity * id
The address of the id to be stored at.
struct GNUNET_SCHEDULER_Task * get_peer_task
The task for this function.
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.
#define GNUNET_free(ptr)
Wrapper around free.
Time for relative time used by GNUnet, in microseconds.
struct RPS_Sampler * sampler
Sampler.