GNUnet  0.10.x
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 
50 
54  void *cls;
55 
60 
65 };
66 
67 
77 
81  uint32_t num_peers;
82 
86  uint32_t cur_num_peers;
87 
91  struct GNUNET_PeerIdentity *ids;
92 
96  struct GetPeerCls *gpc_head;
97  struct GetPeerCls *gpc_tail;
98 
102  struct RPS_Sampler *sampler;
103 
108 
112  void *cls;
113 };
114 
115 
125 
129  struct GNUNET_PeerIdentity *id;
130 
134  struct GetPeerCls *gpc_head;
135  struct GetPeerCls *gpc_tail;
136 
140  struct RPS_Sampler *sampler;
141 
146 
150  void *cls;
151 };
152 
153 
165 void
167  uint32_t num_peers)
168 {
169  sampler->num_peers_estim = num_peers;
170 }
171 
172 
183 void
185  double desired_probability)
186 {
188 }
189 
190 
200 void
202  double deficiency_factor)
203 {
205 }
206 
207 
218 struct SamplerNotifyUpdateCTX *
221  void *cls)
222 {
223  struct SamplerNotifyUpdateCTX *notify_ctx;
224 
226  "Inserting new context for notification\n");
227  notify_ctx = GNUNET_new(struct SamplerNotifyUpdateCTX);
228  notify_ctx->notify_cb = notify_cb;
229  notify_ctx->cls = cls;
231  sampler->notify_ctx_tail,
232  notify_ctx);
233  return notify_ctx;
234 }
235 
236 
243 unsigned int
245 {
246  return sampler->sampler_size;
247 }
248 
249 
258 static void
259 notify_update(struct RPS_Sampler *sampler)
260 {
261  struct SamplerNotifyUpdateCTX *tmp_notify_head;
262  struct SamplerNotifyUpdateCTX *tmp_notify_tail;
263 
265  "Calling callbacks waiting for update notification.\n");
266  tmp_notify_head = sampler->notify_ctx_head;
267  tmp_notify_tail = sampler->notify_ctx_tail;
268  sampler->notify_ctx_head = NULL;
269  sampler->notify_ctx_tail = NULL;
270  for (struct SamplerNotifyUpdateCTX *notify_iter = tmp_notify_head;
271  NULL != tmp_notify_head;
272  notify_iter = tmp_notify_head)
273  {
274  GNUNET_assert(NULL != notify_iter->notify_cb);
275  GNUNET_CONTAINER_DLL_remove(tmp_notify_head,
276  tmp_notify_tail,
277  notify_iter);
278  notify_iter->notify_cb(notify_iter->cls);
279  GNUNET_free(notify_iter);
280  }
281 }
282 
283 
290 void
292  const struct GNUNET_PeerIdentity *id)
293 {
294  for (uint32_t i = 0; i < sampler->sampler_size; i++)
295  {
297  id);
298  }
299  notify_update(sampler);
300 }
301 
302 
317 void
319  const struct GNUNET_PeerIdentity *id)
320 {
321  uint32_t i;
322 
323  for (i = 0; i < sampler->sampler_size; i++)
324  {
325  if (0 == GNUNET_memcmp(id,
326  &(sampler->sampler_elements[i]->peer_id)))
327  {
328  LOG(GNUNET_ERROR_TYPE_DEBUG, "Reinitialising sampler\n");
330  }
331  }
332 }
333 
334 
343 uint32_t
345  const struct GNUNET_PeerIdentity *id)
346 {
347  uint32_t count;
348  uint32_t i;
349 
350  count = 0;
351  for (i = 0; i < sampler->sampler_size; i++)
352  {
353  if (0 == GNUNET_memcmp(&sampler->sampler_elements[i]->peer_id, id)
354  && EMPTY != sampler->sampler_elements[i]->is_empty)
355  count++;
356  }
357  return count;
358 }
359 
360 
367 static void
368 sampler_resize(struct RPS_Sampler *sampler, unsigned int new_size)
369 {
370  unsigned int old_size;
371  uint32_t i;
372 
373  // TODO check min and max size
374 
375  old_size = sampler->sampler_size;
376 
377  if (old_size > new_size)
378  { /* Shrinking */
380  "Shrinking sampler %d -> %d\n",
381  old_size,
382  new_size);
383 
384  for (i = new_size; i < old_size; i++)
385  {
387  }
388 
390  sampler->sampler_size,
391  new_size);
393  "sampler->sampler_elements now points to %p\n",
394  sampler->sampler_elements);
395  }
396  else if (old_size < new_size)
397  { /* Growing */
399  "Growing sampler %d -> %d\n",
400  old_size,
401  new_size);
402 
404  sampler->sampler_size,
405  new_size);
406 
407  for (i = old_size; i < new_size; i++)
408  { /* Add new sampler elements */
410  }
411  }
412  else
413  {
414  LOG(GNUNET_ERROR_TYPE_DEBUG, "Size remains the same -- nothing to do\n");
415  return;
416  }
417 
418  GNUNET_assert(sampler->sampler_size == new_size);
419 }
420 
421 
428 void
429 RPS_sampler_resize(struct RPS_Sampler *sampler, unsigned int new_size)
430 {
431  GNUNET_assert(0 < new_size);
432  sampler_resize(sampler, new_size);
433 }
434 
435 
442 static void
443 sampler_empty(struct RPS_Sampler *sampler)
444 {
445  sampler_resize(sampler, 0);
446 }
447 
448 
461 static void
463  const struct GNUNET_PeerIdentity *id,
464  double probability,
465  uint32_t num_observed)
466 {
468 
469  (void)id;
471  struct GNUNET_PeerIdentity *peers;
472  uint32_t num_peers;
473  void *cb_cls;
474  (void)probability;
475  (void)num_observed;
476 
477  req_handle->cur_num_peers++;
479  "Got %" PRIX32 ". of %" PRIX32 " peers\n",
480  req_handle->cur_num_peers, req_handle->num_peers);
481 
482  if (req_handle->num_peers == req_handle->cur_num_peers)
483  { /* All peers are ready -- return those to the client */
484  GNUNET_assert(NULL != req_handle->callback);
485 
487  "returning %" PRIX32 " peers to the client\n",
488  req_handle->num_peers);
489 
490  /* Copy pointers and peers temporarily as they
491  * might be deleted from within the callback */
492  tmp_cb = req_handle->callback;
493  num_peers = req_handle->num_peers;
494  peers = GNUNET_new_array(num_peers, struct GNUNET_PeerIdentity);
495  GNUNET_memcpy(peers,
496  req_handle->ids,
497  num_peers * sizeof(struct GNUNET_PeerIdentity));
498  cb_cls = req_handle->cls;
499  RPS_sampler_request_cancel(req_handle);
500  req_handle = NULL;
501  tmp_cb(peers, num_peers, cb_cls);
502  GNUNET_free(peers);
503  }
504 }
505 
506 
517 static void
519  const struct GNUNET_PeerIdentity *id,
520  double probability,
521  uint32_t num_observed)
522 {
524 
525  (void)id;
527  struct GNUNET_PeerIdentity *peer;
528  void *cb_cls;
529  (void)probability;
530  (void)num_observed;
531 
533  "Got single peer with additional info\n");
534 
535  GNUNET_assert(NULL != req_handle->callback);
536 
538  "returning single peer with info to the client\n");
539 
540  /* Copy pointers and peers temporarily as they
541  * might be deleted from within the callback */
542  tmp_cb = req_handle->callback;
543  peer = GNUNET_new(struct GNUNET_PeerIdentity);
544  GNUNET_memcpy(peer,
545  req_handle->id,
546  sizeof(struct GNUNET_PeerIdentity));
547  cb_cls = req_handle->cls;
549  req_handle = NULL;
550  tmp_cb(peer, cb_cls, probability, num_observed);
551  GNUNET_free(peer);
552 }
553 
554 
569  uint32_t num_peers,
571  void *cls)
572 {
573  uint32_t i;
575  struct GetPeerCls *gpc;
576 
577  GNUNET_assert(0 != sampler->sampler_size);
578  if (0 == num_peers)
579  return NULL;
580 
581  // TODO check if we have too much (distinct) sampled peers
582  req_handle = GNUNET_new(struct RPS_SamplerRequestHandle);
583  req_handle->num_peers = num_peers;
584  req_handle->cur_num_peers = 0;
585  req_handle->ids = GNUNET_new_array(num_peers, struct GNUNET_PeerIdentity);
586  req_handle->sampler = sampler;
587  req_handle->callback = cb;
588  req_handle->cls = cls;
590  sampler->req_handle_tail,
591  req_handle);
592 
594  "Scheduling requests for %" PRIu32 " peers\n", num_peers);
595 
596  for (i = 0; i < num_peers; i++)
597  {
598  gpc = GNUNET_new(struct GetPeerCls);
599  gpc->req_handle = req_handle;
600  gpc->req_single_info_handle = NULL;
601  gpc->cont = check_n_peers_ready;
602  gpc->cont_cls = req_handle;
603  gpc->id = &req_handle->ids[i];
604 
606  req_handle->gpc_tail,
607  gpc);
608  // maybe add a little delay
610  gpc);
611  }
612  return req_handle;
613 }
614 
615 
626  void *cls)
627 {
629  struct GetPeerCls *gpc;
630 
631  GNUNET_assert(0 != sampler->sampler_size);
632 
633  // TODO check if we have too much (distinct) sampled peers
634  req_handle = GNUNET_new(struct RPS_SamplerRequestHandleSingleInfo);
635  req_handle->id = GNUNET_malloc(sizeof(struct GNUNET_PeerIdentity));
636  req_handle->sampler = sampler;
637  req_handle->callback = cb;
638  req_handle->cls = cls;
640  sampler->req_handle_single_tail,
641  req_handle);
642 
643  gpc = GNUNET_new(struct GetPeerCls);
644  gpc->req_handle = NULL;
647  gpc->cont_cls = req_handle;
648  gpc->id = req_handle->id;
649 
651  req_handle->gpc_tail,
652  gpc);
653  // maybe add a little delay
655  gpc);
656  return req_handle;
657 }
658 
659 
665 void
667 {
668  struct GetPeerCls *i;
669 
670  while (NULL != (i = req_handle->gpc_head))
671  {
673  req_handle->gpc_tail,
674  i);
675  if (NULL != i->get_peer_task)
676  {
678  }
679  if (NULL != i->notify_ctx)
680  {
682  req_handle->sampler->notify_ctx_tail,
683  i->notify_ctx);
685  i->notify_ctx = NULL;
686  }
687  GNUNET_free(i);
688  }
689  GNUNET_free(req_handle->ids);
690  req_handle->ids = NULL;
692  req_handle->sampler->req_handle_tail,
693  req_handle);
694  GNUNET_free(req_handle);
695 }
696 
697 
703 void
706 {
707  struct GetPeerCls *i;
708 
709  while (NULL != (i = req_single_info_handle->gpc_head))
710  {
711  GNUNET_CONTAINER_DLL_remove(req_single_info_handle->gpc_head,
712  req_single_info_handle->gpc_tail,
713  i);
714  if (NULL != i->get_peer_task)
715  {
717  }
718  if (NULL != i->notify_ctx)
719  {
720  GNUNET_CONTAINER_DLL_remove(req_single_info_handle->sampler->notify_ctx_head,
721  req_single_info_handle->sampler->notify_ctx_tail,
722  i->notify_ctx);
724  i->notify_ctx = NULL;
725  }
726  GNUNET_free(i);
727  }
728  GNUNET_free(req_single_info_handle->id);
729  req_single_info_handle->id = NULL;
731  req_single_info_handle->sampler->req_handle_single_tail,
732  req_single_info_handle);
733  GNUNET_free(req_single_info_handle);
734 }
735 
736 
740 void
742 {
743  if (NULL != sampler->req_handle_head)
744  {
746  "There are still pending requests. Going to remove them.\n");
747  while (NULL != sampler->req_handle_head)
748  {
750  }
751  }
752  sampler_empty(sampler);
753  GNUNET_free(sampler);
754 }
755 
756 
757 /* end of rps-sampler_common.c */
struct SamplerNotifyUpdateCTX * notify_ctx_tail
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
double desired_probability
The desired probability with which we want to have observed all peers.
uint32_t num_peers_estim
The estimated total number of peers in the network.
#define GNUNET_CONTAINER_DLL_insert(head, tail, element)
Insert an element at the head of a DLL.
RPS_sampler_rand_peer_ready_cont cont
The callback.
struct SamplerNotifyUpdateCTX * prev
Previous element in DLL.
uint32_t num_peers
Number of peers we are waiting for.
void RPS_sampler_elem_destroy(struct RPS_SamplerElement *sampler_elem)
Destroy a sampler element.
Some utils faciliating the view into the internals for the sampler needed for evaluation.
void RPS_sampler_set_deficiency_factor(struct RPS_Sampler *sampler, double deficiency_factor)
Set the deficiency factor.
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
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 * cls
Closure given to the callback.
void RPS_sampler_request_single_info_cancel(struct RPS_SamplerRequestHandleSingleInfo *req_single_info_handle)
Cancle a request issued through RPS_sampler_sinlge_info_ready_cb.
#define GNUNET_memcpy(dst, src, n)
Call memcpy() but check for n being 0 first.
sampler element implementation
struct RPS_SamplerRequestHandleSingleInfo * req_handle_single_head
Head and tail for the DLL to store the RPS_SamplerRequestHandleSingleInfo.
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().
RPS_sampler_n_rand_peers_ready_cb callback
Callback to be called when all ids are available.
void RPS_sampler_update(struct RPS_Sampler *sampler, const struct GNUNET_PeerIdentity *id)
Update every sampler element of this sampler with given peer.
void RPS_sampler_request_cancel(struct RPS_SamplerRequestHandle *req_handle)
Cancle a request issued through RPS_sampler_n_rand_peers_ready_cb.
Code common to client and service sampler.
Context for a callback.
struct RPS_SamplerElement * RPS_sampler_elem_create(void)
Create a sampler element and initialise it.
static struct GNUNET_IDENTITY_Handle * id
Handle to identity service.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
void RPS_sampler_elem_reinit(struct RPS_SamplerElement *sampler_elem)
Reinitialise a previously initialised sampler element.
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().
struct RPS_SamplerRequestHandle * req_handle
The RPS_SamplerRequestHandle this single request belongs to.
void(* SamplerNotifyUpdateCB)(void *cls)
Callback called each time a new peer was put into the sampler.
Closure to _get_n_rand_peers_ready_cb()
struct SamplerNotifyUpdateCTX * notify_ctx
Context to the given callback.
struct SamplerNotifyUpdateCTX * next
Next element in DLL.
#define GNUNET_array_grow(arr, size, tsize)
Grow a well-typed (!) array.
struct RPS_Sampler * sampler
Sampler.
static void sampler_resize(struct RPS_Sampler *sampler, unsigned int new_size)
Grow or shrink the size of the sampler.
static struct GNUNET_RPS_Request_Handle * req_handle
Request handle.
Definition: gnunet-rps.c:41
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_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:1264
struct GNUNET_PeerIdentity peer_id
The PeerID this sampler currently samples.
SamplerNotifyUpdateCB notify_cb
The Callback to call on updates.
#define LOG(kind,...)
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.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
void * cls
The according closure.
void RPS_sampler_resize(struct RPS_Sampler *sampler, unsigned int new_size)
Grow or shrink the size of the sampler.
Closure to _get_rand_peer_info()
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 * cls
Closure given to the callback.
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.
struct GetPeerCls * gpc_head
Head and tail for the DLL to store the tasks for single requests.
struct GNUNET_TESTBED_Peer * peer
The peer associated with this model.
struct GNUNET_PeerIdentity * ids
Pointer to the array holding the ids.
static unsigned int num_peers
struct RPS_SamplerRequestHandleSingleInfo * req_handle_single_tail
static void sampler_empty(struct RPS_Sampler *sampler)
Empty the sampler.
struct GNUNET_PeerIdentity * id
Pointer to the id.
uint32_t cur_num_peers
Number of peers we currently have.
#define GNUNET_memcmp(a, b)
Compare memory in a and b, where both must be of the same pointer type.
struct RPS_SamplerRequestHandleSingleInfo * req_single_info_handle
The RPS_SamplerRequestHandleSingleInfo this single request belongs to.
void * cont_cls
The closure to the callback cont.
static void notify_update(struct RPS_Sampler *sampler)
Notify about update of the sampler.
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.
unsigned int RPS_sampler_get_size(struct RPS_Sampler *sampler)
Get the size of the sampler.
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.
static struct CadetPeer * peers
Operation to get peer ids.
Closure for sampler_mod_get_rand_peer() and sampler_get_rand_peer.
struct RPS_SamplerRequestHandle * req_handle_head
Head and tail for the DLL to store the RPS_SamplerRequestHandle.
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.
void RPS_sampler_destroy(struct RPS_Sampler *sampler)
Cleans the sampler.
struct SamplerNotifyUpdateCTX * notify_ctx_head
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.
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 ** sampler_elements
All sampler elements in one array.
struct RPS_SamplerRequestHandle * req_handle_tail
Sampler with its own array of SamplerElements.
uint32_t RPS_sampler_count_id(struct RPS_Sampler *sampler, const struct GNUNET_PeerIdentity *id)
Counts how many Samplers currently hold a given PeerID.
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.
#define GNUNET_malloc(size)
Wrapper around malloc.
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.
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.
struct RPS_Sampler * sampler
Sampler.
void * GNUNET_SCHEDULER_cancel(struct GNUNET_SCHEDULER_Task *task)
Cancel the task with the specified identifier.
Definition: scheduler.c:956