GNUnet  0.11.x
Data Structures | Macros | Typedefs | Functions | Variables
rps-sampler_client.c File Reference
#include "platform.h"
#include "gnunet_util_lib.h"
#include "gnunet_statistics_service.h"
#include "rps.h"
#include "rps-sampler_common.h"
#include "gnunet-service-rps_sampler.h"
#include "gnunet-service-rps_sampler_elem.h"
#include <math.h>
#include <inttypes.h>
#include "rps-test_util.h"
Include dependency graph for rps-sampler_client.c:

Go to the source code of this file.

Data Structures

struct  SamplerNotifyUpdateCTX
 Context for a callback. More...
 
struct  RPS_SamplerRequestHandle
 Closure to _get_n_rand_peers_ready_cb() More...
 
struct  RPS_SamplerRequestHandleSingleInfo
 Closure to _get_rand_peer_info() More...
 

Macros

#define LOG(kind, ...)   GNUNET_log_from (kind, "rps-sampler", __VA_ARGS__)
 

Typedefs

typedef void(* SamplerNotifyUpdateCB) (void *cls)
 Callback called each time a new peer was put into the sampler. More...
 
typedef void(* RPS_get_peers_type) (void *cls)
 Type of function used to differentiate between modified and not modified Sampler. More...
 

Functions

static void sampler_mod_get_rand_peer (void *cls)
 Get one random peer out of the sampled peers. More...
 
struct RPS_SamplerRPS_sampler_mod_init (size_t init_size, struct GNUNET_TIME_Relative max_round_interval)
 Initialise a modified tuple of sampler elements. More...
 

Variables

static size_t min_size
 Global sampler variable. More...
 
static size_t max_size
 The maximal size the extended sampler elements should grow to. More...
 
static uint32_t client_get_index
 The size the extended sampler elements currently have. More...
 

Macro Definition Documentation

◆ LOG

#define LOG (   kind,
  ... 
)    GNUNET_log_from (kind, "rps-sampler", __VA_ARGS__)

Definition at line 40 of file rps-sampler_client.c.

Referenced by sampler_mod_get_rand_peer().

Typedef Documentation

◆ SamplerNotifyUpdateCB

typedef void(* SamplerNotifyUpdateCB) (void *cls)

Callback called each time a new peer was put into the sampler.

Parameters
clsA possibly given closure

Definition at line 64 of file rps-sampler_client.c.

◆ RPS_get_peers_type

typedef void(* RPS_get_peers_type) (void *cls)

Type of function used to differentiate between modified and not modified Sampler.

Definition at line 100 of file rps-sampler_client.c.

Function Documentation

◆ sampler_mod_get_rand_peer()

static void sampler_mod_get_rand_peer ( void *  cls)
static

Get one random peer out of the sampled peers.

Compute the probability that we already observed all peers from a biased stream of peer ids.

We might want to reinitialise this sampler after giving the corrsponding peer to the client.

Deficiency factor: 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.

Parameters
num_peers_estimThe estimated number of peers in the network
num_peers_observedThe number of peers the given element has observed
deficiency_factorA factor that catches the 'bias' of a random stream of peer ids
Returns
The estimated probability Get one random peer out of the sampled peers.

This reinitialises the queried sampler element.

  • How many time remains untile the next round has started? */
  • check if probability is above desired */

Definition at line 302 of file rps-sampler_client.c.

References GNUNET_TIME_Absolute::abs_value_us, SamplerNotifyUpdateCTX::cls, GetPeerCls::cont, GetPeerCls::cont_cls, EMPTY, GetPeerCls::get_peer_task, GNUNET_assert, GNUNET_CONTAINER_DLL_remove, GNUNET_ERROR_TYPE_DEBUG, GNUNET_free, GNUNET_TIME_absolute_get(), GNUNET_TIME_absolute_get_difference(), GNUNET_TIME_UNIT_FOREVER_ABS, RPS_SamplerRequestHandle::gpc_head, RPS_SamplerRequestHandleSingleInfo::gpc_head, RPS_SamplerRequestHandle::gpc_tail, RPS_SamplerRequestHandleSingleInfo::gpc_tail, GetPeerCls::id, RPS_SamplerElement::is_empty, RPS_SamplerElement::last_client_request, LOG, RPS_Sampler::max_round_interval, GetPeerCls::notify_ctx, RPS_SamplerElement::num_peers, RPS_SamplerElement::peer_id, GNUNET_TIME_Relative::rel_value_us, GetPeerCls::req_handle, GetPeerCls::req_single_info_handle, RPS_sampler_elem_reinit(), RPS_SamplerRequestHandle::sampler, RPS_SamplerRequestHandleSingleInfo::sampler, RPS_Sampler::sampler_elements, sampler_notify_on_update(), and RPS_Sampler::sampler_size.

Referenced by RPS_sampler_mod_init().

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 }
#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.
uint64_t rel_value_us
The actual value.
RPS_sampler_rand_peer_ready_cont cont
The callback.
A sampler element sampling one PeerID at a time.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
struct GNUNET_TIME_Absolute last_client_request
Time of last request.
#define LOG(kind,...)
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.
#define GNUNET_TIME_UNIT_FOREVER_ABS
Constant used to specify "forever".
struct SamplerNotifyUpdateCTX * notify_ctx
Context to the given callback.
static uint32_t client_get_index
The size the extended sampler elements currently have.
struct RPS_Sampler * sampler
Sampler.
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.
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:86
struct GetPeerCls * gpc_head
Head and tail for the DLL to store the tasks for single requests.
struct RPS_SamplerRequestHandleSingleInfo * req_single_info_handle
The RPS_SamplerRequestHandleSingleInfo this single request belongs to.
void * cont_cls
The closure to the callback cont.
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.
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:248
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.
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.
Here is the call graph for this function:
Here is the caller graph for this function:

◆ RPS_sampler_mod_init()

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.

Parameters
init_sizethe size the sampler is initialised with
max_round_intervalmaximum time a round takes
Returns
a handle to a sampler that consists of sampler elements.

Definition at line 236 of file rps-sampler_client.c.

References RPS_Sampler::get_peers, GNUNET_new, RPS_Sampler::max_round_interval, RPS_sampler_resize(), and sampler_mod_get_rand_peer().

Referenced by GNUNET_RPS_request_peer_info(), and GNUNET_RPS_request_peers().

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 }
static size_t min_size
Global sampler variable.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
struct GNUNET_TIME_Relative max_round_interval
Maximum time a round takes.
static size_t max_size
The maximal size the extended sampler elements should grow to.
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.
void RPS_sampler_resize(struct RPS_Sampler *sampler, unsigned int new_size)
Grow or shrink the size of the sampler.
RPS_get_peers_type get_peers
Stores the function to return peers.
Sampler with its own array of SamplerElements.
Here is the call graph for this function:
Here is the caller graph for this function:

Variable Documentation

◆ min_size

size_t min_size
static

Global sampler variable.

The minimal size for the extended sampler elements.

Definition at line 210 of file rps-sampler_client.c.

◆ max_size

size_t max_size
static

The maximal size the extended sampler elements should grow to.

Definition at line 215 of file rps-sampler_client.c.

◆ client_get_index

uint32_t client_get_index
static

The size the extended sampler elements currently have.

Inedex to the sampler element that is the next to be returned

Definition at line 225 of file rps-sampler_client.c.