GNUnet  0.20.0
rps-sampler_common.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 
30 #include "rps-sampler_common.h"
32 
33 #include <math.h>
34 #include <inttypes.h>
35 
36 #include "rps-test_util.h"
37 
38 #define LOG(kind, ...) GNUNET_log_from (kind, "rps-sampler_common", __VA_ARGS__)
39 
46 {
51 
55  void *cls;
56 
61 
66 };
67 
68 
73 {
79 
83  uint32_t num_peers;
84 
88  uint32_t cur_num_peers;
89 
93  struct GNUNET_PeerIdentity *ids;
94 
98  struct GetPeerCls *gpc_head;
99  struct GetPeerCls *gpc_tail;
100 
104  struct RPS_Sampler *sampler;
105 
110 
114  void *cls;
115 };
116 
117 
122 {
128 
132  struct GNUNET_PeerIdentity *id;
133 
137  struct GetPeerCls *gpc_head;
138  struct GetPeerCls *gpc_tail;
139 
143  struct RPS_Sampler *sampler;
144 
149 
153  void *cls;
154 };
155 
156 
168 void
170  uint32_t num_peers)
171 {
172  sampler->num_peers_estim = num_peers;
173 }
174 
175 
186 void
188  double desired_probability)
189 {
191 }
192 
193 
194 void
196  double deficiency_factor)
197 {
199 }
200 
201 
212 struct SamplerNotifyUpdateCTX *
215  void *cls)
216 {
217  struct SamplerNotifyUpdateCTX *notify_ctx;
218 
220  "Inserting new context for notification\n");
221  notify_ctx = GNUNET_new (struct SamplerNotifyUpdateCTX);
222  notify_ctx->notify_cb = notify_cb;
223  notify_ctx->cls = cls;
225  sampler->notify_ctx_tail,
226  notify_ctx);
227  return notify_ctx;
228 }
229 
230 
237 unsigned int
239 {
240  return sampler->sampler_size;
241 }
242 
243 
252 static void
253 notify_update (struct RPS_Sampler *sampler)
254 {
255  struct SamplerNotifyUpdateCTX *tmp_notify_head;
256  struct SamplerNotifyUpdateCTX *tmp_notify_tail;
257 
259  "Calling callbacks waiting for update notification.\n");
260  tmp_notify_head = sampler->notify_ctx_head;
261  tmp_notify_tail = sampler->notify_ctx_tail;
262  sampler->notify_ctx_head = NULL;
263  sampler->notify_ctx_tail = NULL;
264  for (struct SamplerNotifyUpdateCTX *notify_iter = tmp_notify_head;
265  NULL != tmp_notify_head;
266  notify_iter = tmp_notify_head)
267  {
268  GNUNET_assert (NULL != notify_iter->notify_cb);
269  GNUNET_CONTAINER_DLL_remove (tmp_notify_head,
270  tmp_notify_tail,
271  notify_iter);
272  notify_iter->notify_cb (notify_iter->cls);
273  GNUNET_free (notify_iter);
274  }
275 }
276 
277 
284 void
286  const struct GNUNET_PeerIdentity *id)
287 {
288  for (uint32_t i = 0; i < sampler->sampler_size; i++)
289  {
291  id);
292  }
293  notify_update (sampler);
294 }
295 
296 
311 void
313  const struct GNUNET_PeerIdentity *id)
314 {
315  uint32_t i;
316 
317  for (i = 0; i < sampler->sampler_size; i++)
318  {
319  if (0 == GNUNET_memcmp (id,
320  &(sampler->sampler_elements[i]->peer_id)))
321  {
322  LOG (GNUNET_ERROR_TYPE_DEBUG, "Reinitialising sampler\n");
324  }
325  }
326 }
327 
328 
337 uint32_t
339  const struct GNUNET_PeerIdentity *id)
340 {
341  uint32_t count;
342  uint32_t i;
343 
344  count = 0;
345  for (i = 0; i < sampler->sampler_size; i++)
346  {
347  if ((0 == GNUNET_memcmp (&sampler->sampler_elements[i]->peer_id, id))
348  && (EMPTY != sampler->sampler_elements[i]->is_empty) )
349  count++;
350  }
351  return count;
352 }
353 
354 
361 static void
362 sampler_resize (struct RPS_Sampler *sampler, unsigned int new_size)
363 {
364  unsigned int old_size;
365  uint32_t i;
366 
367  // TODO check min and max size
368 
369  old_size = sampler->sampler_size;
370 
371  if (old_size > new_size)
372  { /* Shrinking */
374  "Shrinking sampler %d -> %d\n",
375  old_size,
376  new_size);
377 
378  for (i = new_size; i < old_size; i++)
379  {
381  }
382 
384  sampler->sampler_size,
385  new_size);
387  "sampler->sampler_elements now points to %p\n",
388  sampler->sampler_elements);
389  }
390  else if (old_size < new_size)
391  { /* Growing */
393  "Growing sampler %d -> %d\n",
394  old_size,
395  new_size);
396 
398  sampler->sampler_size,
399  new_size);
400 
401  for (i = old_size; i < new_size; i++)
402  { /* Add new sampler elements */
403  sampler->sampler_elements[i] = RPS_sampler_elem_create ();
404  }
405  }
406  else
407  {
408  LOG (GNUNET_ERROR_TYPE_DEBUG, "Size remains the same -- nothing to do\n");
409  return;
410  }
411 
412  GNUNET_assert (sampler->sampler_size == new_size);
413 }
414 
415 
422 void
423 RPS_sampler_resize (struct RPS_Sampler *sampler, unsigned int new_size)
424 {
425  GNUNET_assert (0 < new_size);
426  sampler_resize (sampler, new_size);
427 }
428 
429 
435 static void
436 sampler_empty (struct RPS_Sampler *sampler)
437 {
438  sampler_resize (sampler, 0);
439 }
440 
441 
454 static void
456  const struct GNUNET_PeerIdentity *id,
457  double probability,
458  uint32_t num_observed)
459 {
461 
462  (void) id;
464  struct GNUNET_PeerIdentity *peers;
465  uint32_t num_peers;
466  void *cb_cls;
467  (void) probability;
468  (void) num_observed;
469 
470  req_handle->cur_num_peers++;
472  "Got %" PRIX32 ". of %" PRIX32 " peers\n",
473  req_handle->cur_num_peers, req_handle->num_peers);
474 
475  if (req_handle->num_peers == req_handle->cur_num_peers)
476  { /* All peers are ready -- return those to the client */
477  GNUNET_assert (NULL != req_handle->callback);
478 
480  "returning %" PRIX32 " peers to the client\n",
481  req_handle->num_peers);
482 
483  /* Copy pointers and peers temporarily as they
484  * might be deleted from within the callback */
485  tmp_cb = req_handle->callback;
486  num_peers = req_handle->num_peers;
489  req_handle->ids,
490  num_peers * sizeof(struct GNUNET_PeerIdentity));
491  cb_cls = req_handle->cls;
493  req_handle = NULL;
494  tmp_cb (peers, num_peers, cb_cls);
495  GNUNET_free (peers);
496  }
497 }
498 
499 
510 static void
512  const struct GNUNET_PeerIdentity *id,
513  double probability,
514  uint32_t num_observed)
515 {
517 
518  (void) id;
520  struct GNUNET_PeerIdentity *peer;
521  void *cb_cls;
522  (void) probability;
523  (void) num_observed;
524 
526  "Got single peer with additional info\n");
527 
528  GNUNET_assert (NULL != req_handle->callback);
529 
531  "returning single peer with info to the client\n");
532 
533  /* Copy pointers and peers temporarily as they
534  * might be deleted from within the callback */
535  tmp_cb = req_handle->callback;
538  req_handle->id,
539  sizeof(struct GNUNET_PeerIdentity));
540  cb_cls = req_handle->cls;
542  req_handle = NULL;
543  tmp_cb (peer, cb_cls, probability, num_observed);
544  GNUNET_free (peer);
545 }
546 
547 
550  uint32_t num_peers,
552  void *cls)
553 {
554  uint32_t i;
556  struct GetPeerCls *gpc;
557 
558  GNUNET_assert (0 != sampler->sampler_size);
559  if (0 == num_peers)
560  return NULL;
561 
562  // TODO check if we have too much (distinct) sampled peers
564  req_handle->num_peers = num_peers;
565  req_handle->cur_num_peers = 0;
567  req_handle->sampler = sampler;
568  req_handle->callback = cb;
569  req_handle->cls = cls;
571  sampler->req_handle_tail,
572  req_handle);
573 
575  "Scheduling requests for %" PRIu32 " peers\n", num_peers);
576 
577  for (i = 0; i < num_peers; i++)
578  {
579  gpc = GNUNET_new (struct GetPeerCls);
580  gpc->req_handle = req_handle;
581  gpc->req_single_info_handle = NULL;
582  gpc->cont = check_n_peers_ready;
583  gpc->cont_cls = req_handle;
584  gpc->id = &req_handle->ids[i];
585 
587  req_handle->gpc_tail,
588  gpc);
589  // maybe add a little delay
591  gpc);
592  }
593  return req_handle;
594 }
595 
596 
607  void *cls)
608 {
610  struct GetPeerCls *gpc;
611 
612  GNUNET_assert (0 != sampler->sampler_size);
613 
614  // TODO check if we have too much (distinct) sampled peers
616  req_handle->id = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity));
617  req_handle->sampler = sampler;
618  req_handle->callback = cb;
619  req_handle->cls = cls;
621  sampler->req_handle_single_tail,
622  req_handle);
623 
624  gpc = GNUNET_new (struct GetPeerCls);
625  gpc->req_handle = NULL;
628  gpc->cont_cls = req_handle;
629  gpc->id = req_handle->id;
630 
632  req_handle->gpc_tail,
633  gpc);
634  // maybe add a little delay
636  gpc);
637  return req_handle;
638 }
639 
640 
646 void
648 {
649  struct GetPeerCls *i;
650 
651  while (NULL != (i = req_handle->gpc_head))
652  {
654  req_handle->gpc_tail,
655  i);
656  if (NULL != i->get_peer_task)
657  {
659  }
660  if (NULL != i->notify_ctx)
661  {
664  i->notify_ctx);
665  GNUNET_free (i->notify_ctx);
666  i->notify_ctx = NULL;
667  }
668  GNUNET_free (i);
669  }
670  GNUNET_free (req_handle->ids);
671  req_handle->ids = NULL;
674  req_handle);
676 }
677 
678 
684 void
687 {
688  struct GetPeerCls *i;
689 
690  while (NULL != (i = req_single_info_handle->gpc_head))
691  {
694  i);
695  if (NULL != i->get_peer_task)
696  {
698  }
699  if (NULL != i->notify_ctx)
700  {
704  notify_ctx_tail,
705  i->notify_ctx);
706  GNUNET_free (i->notify_ctx);
707  i->notify_ctx = NULL;
708  }
709  GNUNET_free (i);
710  }
712  req_single_info_handle->id = NULL;
716  req_handle_single_tail,
719 }
720 
721 
725 void
727 {
728  if (NULL != sampler->req_handle_head)
729  {
731  "There are still pending requests. Going to remove them.\n");
732  while (NULL != sampler->req_handle_head)
733  {
735  }
736  }
737  sampler_empty (sampler);
738  GNUNET_free (sampler);
739 }
740 
741 
742 /* end of rps-sampler_common.c */
static struct CadetPeer * peers
Operation to get peer ids.
static void notify_cb(void *cls, const struct GNUNET_PeerIdentity *sender, const struct GNUNET_MessageHeader *msg)
Function called when the transport service has received a backchannel message for this communicator (...
static unsigned int num_peers
static struct GNUNET_RPS_Request_Handle * req_handle
Request handle.
Definition: gnunet-rps.c:41
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.
void RPS_sampler_elem_destroy(struct RPS_SamplerElement *sampler_elem)
Destroy a sampler element.
void RPS_sampler_elem_next(struct RPS_SamplerElement *sampler_elem, const struct GNUNET_PeerIdentity *new_ID)
Update a sampler element with a PeerID.
struct RPS_SamplerElement * RPS_sampler_elem_create(void)
Create a sampler element and initialise it.
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_CONTAINER_DLL_insert(head, tail, element)
Insert an element at the head of a DLL.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
@ GNUNET_ERROR_TYPE_WARNING
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
#define GNUNET_free(ptr)
Wrapper around free.
struct GNUNET_SCHEDULER_Task * GNUNET_SCHEDULER_add_now(GNUNET_SCHEDULER_TaskCallback task, void *task_cls)
Schedule a new task to be run as soon as possible.
Definition: scheduler.c:1299
void * GNUNET_SCHEDULER_cancel(struct GNUNET_SCHEDULER_Task *task)
Cancel the task with the specified identifier.
Definition: scheduler.c:975
static void notify_update(struct RPS_Sampler *sampler)
Notify about update of the sampler.
void RPS_sampler_update(struct RPS_Sampler *sampler, const struct GNUNET_PeerIdentity *id)
Update every sampler element of this sampler with given peer.
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.
void RPS_sampler_update_with_nw_size(struct RPS_Sampler *sampler, uint32_t num_peers)
Update the current estimate of the network size stored at the sampler.
void RPS_sampler_reinitialise_by_value(struct RPS_Sampler *sampler, const struct GNUNET_PeerIdentity *id)
Reinitialise all previously initialised sampler elements with the given value.
void RPS_sampler_resize(struct RPS_Sampler *sampler, unsigned int new_size)
Grow or shrink the size of the sampler.
static void check_peer_info_ready(void *cls, const struct GNUNET_PeerIdentity *id, double probability, uint32_t num_observed)
Callback to _get_rand_peer() used by _get_rand_peer_info().
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)
Get n random peers out of the sampled peers.
void RPS_sampler_request_cancel(struct RPS_SamplerRequestHandle *req_handle)
Cancel a request issued through RPS_sampler_n_rand_peers_ready_cb.
static void sampler_resize(struct RPS_Sampler *sampler, unsigned int new_size)
Grow or shrink the size of the sampler.
void RPS_sampler_destroy(struct RPS_Sampler *sampler)
Cleans the sampler.
unsigned int RPS_sampler_get_size(struct RPS_Sampler *sampler)
Get the size of the sampler.
void RPS_sampler_set_deficiency_factor(struct RPS_Sampler *sampler, double deficiency_factor)
Set the deficiency factor.
struct RPS_SamplerRequestHandleSingleInfo * RPS_sampler_get_rand_peer_info(struct RPS_Sampler *sampler, RPS_sampler_sinlge_info_ready_cb cb, void *cls)
Get one random peer with additional information.
#define LOG(kind,...)
void RPS_sampler_set_desired_probability(struct RPS_Sampler *sampler, double desired_probability)
Set the probability that is needed at least with what a sampler element has to have observed all elem...
void RPS_sampler_request_single_info_cancel(struct RPS_SamplerRequestHandleSingleInfo *req_single_info_handle)
Cancel a request issued through RPS_sampler_sinlge_info_ready_cb.
static void check_n_peers_ready(void *cls, const struct GNUNET_PeerIdentity *id, double probability, uint32_t num_observed)
Callback to _get_rand_peer() used by _get_n_rand_peers().
static void sampler_empty(struct RPS_Sampler *sampler)
Empty the sampler.
uint32_t RPS_sampler_count_id(struct RPS_Sampler *sampler, const struct GNUNET_PeerIdentity *id)
Counts how many Samplers currently hold a given PeerID.
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.
The identity of the host (wraps the signing key of the peer).
struct RPS_Sampler * sampler
The Sampler for the client request.
Definition: rps_api.c:174
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.
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.
struct RPS_SamplerRequestHandle * req_handle_head
Head and tail for the DLL to store the RPS_SamplerRequestHandle.
struct RPS_SamplerRequestHandleSingleInfo * req_handle_single_tail
struct SamplerNotifyUpdateCTX * notify_ctx_head
RPS_get_peers_type get_peers
Stores the function to return peers.
struct RPS_SamplerElement ** sampler_elements
All sampler elements in one array.
double deficiency_factor
A factor that catches the 'bias' of a random stream of peer ids.
struct RPS_SamplerRequestHandleSingleInfo * req_handle_single_head
Head and tail for the DLL to store the RPS_SamplerRequestHandleSingleInfo.
struct RPS_SamplerRequestHandle * req_handle_tail
uint32_t num_peers_estim
The estimated total number of peers in the network.
struct SamplerNotifyUpdateCTX * notify_ctx_tail
double desired_probability
The desired probability with which we want to have observed all peers.
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.
struct GNUNET_TESTBED_Peer * peer
The peer associated with this model.