GNUnet  0.11.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 
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 
203 void
205  double deficiency_factor)
206 {
208 }
209 
210 
221 struct SamplerNotifyUpdateCTX *
224  void *cls)
225 {
226  struct SamplerNotifyUpdateCTX *notify_ctx;
227 
229  "Inserting new context for notification\n");
230  notify_ctx = GNUNET_new (struct SamplerNotifyUpdateCTX);
231  notify_ctx->notify_cb = notify_cb;
232  notify_ctx->cls = cls;
234  sampler->notify_ctx_tail,
235  notify_ctx);
236  return notify_ctx;
237 }
238 
239 
246 unsigned int
248 {
249  return sampler->sampler_size;
250 }
251 
252 
261 static void
262 notify_update (struct RPS_Sampler *sampler)
263 {
264  struct SamplerNotifyUpdateCTX *tmp_notify_head;
265  struct SamplerNotifyUpdateCTX *tmp_notify_tail;
266 
268  "Calling callbacks waiting for update notification.\n");
269  tmp_notify_head = sampler->notify_ctx_head;
270  tmp_notify_tail = sampler->notify_ctx_tail;
271  sampler->notify_ctx_head = NULL;
272  sampler->notify_ctx_tail = NULL;
273  for (struct SamplerNotifyUpdateCTX *notify_iter = tmp_notify_head;
274  NULL != tmp_notify_head;
275  notify_iter = tmp_notify_head)
276  {
277  GNUNET_assert (NULL != notify_iter->notify_cb);
278  GNUNET_CONTAINER_DLL_remove (tmp_notify_head,
279  tmp_notify_tail,
280  notify_iter);
281  notify_iter->notify_cb (notify_iter->cls);
282  GNUNET_free (notify_iter);
283  }
284 }
285 
286 
293 void
295  const struct GNUNET_PeerIdentity *id)
296 {
297  for (uint32_t i = 0; i < sampler->sampler_size; i++)
298  {
300  id);
301  }
302  notify_update (sampler);
303 }
304 
305 
320 void
322  const struct GNUNET_PeerIdentity *id)
323 {
324  uint32_t i;
325 
326  for (i = 0; i < sampler->sampler_size; i++)
327  {
328  if (0 == GNUNET_memcmp (id,
329  &(sampler->sampler_elements[i]->peer_id)))
330  {
331  LOG (GNUNET_ERROR_TYPE_DEBUG, "Reinitialising sampler\n");
333  }
334  }
335 }
336 
337 
346 uint32_t
348  const struct GNUNET_PeerIdentity *id)
349 {
350  uint32_t count;
351  uint32_t i;
352 
353  count = 0;
354  for (i = 0; i < sampler->sampler_size; i++)
355  {
356  if ((0 == GNUNET_memcmp (&sampler->sampler_elements[i]->peer_id, id))
357  && (EMPTY != sampler->sampler_elements[i]->is_empty) )
358  count++;
359  }
360  return count;
361 }
362 
363 
370 static void
371 sampler_resize (struct RPS_Sampler *sampler, unsigned int new_size)
372 {
373  unsigned int old_size;
374  uint32_t i;
375 
376  // TODO check min and max size
377 
378  old_size = sampler->sampler_size;
379 
380  if (old_size > new_size)
381  { /* Shrinking */
383  "Shrinking sampler %d -> %d\n",
384  old_size,
385  new_size);
386 
387  for (i = new_size; i < old_size; i++)
388  {
390  }
391 
393  sampler->sampler_size,
394  new_size);
396  "sampler->sampler_elements now points to %p\n",
397  sampler->sampler_elements);
398  }
399  else if (old_size < new_size)
400  { /* Growing */
402  "Growing sampler %d -> %d\n",
403  old_size,
404  new_size);
405 
407  sampler->sampler_size,
408  new_size);
409 
410  for (i = old_size; i < new_size; i++)
411  { /* Add new sampler elements */
412  sampler->sampler_elements[i] = RPS_sampler_elem_create ();
413  }
414  }
415  else
416  {
417  LOG (GNUNET_ERROR_TYPE_DEBUG, "Size remains the same -- nothing to do\n");
418  return;
419  }
420 
421  GNUNET_assert (sampler->sampler_size == new_size);
422 }
423 
424 
431 void
432 RPS_sampler_resize (struct RPS_Sampler *sampler, unsigned int new_size)
433 {
434  GNUNET_assert (0 < new_size);
435  sampler_resize (sampler, new_size);
436 }
437 
438 
445 static void
446 sampler_empty (struct RPS_Sampler *sampler)
447 {
448  sampler_resize (sampler, 0);
449 }
450 
451 
464 static void
466  const struct GNUNET_PeerIdentity *id,
467  double probability,
468  uint32_t num_observed)
469 {
471 
472  (void) id;
474  struct GNUNET_PeerIdentity *peers;
475  uint32_t num_peers;
476  void *cb_cls;
477  (void) probability;
478  (void) num_observed;
479 
480  req_handle->cur_num_peers++;
482  "Got %" PRIX32 ". of %" PRIX32 " peers\n",
483  req_handle->cur_num_peers, req_handle->num_peers);
484 
485  if (req_handle->num_peers == req_handle->cur_num_peers)
486  { /* All peers are ready -- return those to the client */
487  GNUNET_assert (NULL != req_handle->callback);
488 
490  "returning %" PRIX32 " peers to the client\n",
491  req_handle->num_peers);
492 
493  /* Copy pointers and peers temporarily as they
494  * might be deleted from within the callback */
495  tmp_cb = req_handle->callback;
496  num_peers = req_handle->num_peers;
497  peers = GNUNET_new_array (num_peers, struct GNUNET_PeerIdentity);
498  GNUNET_memcpy (peers,
499  req_handle->ids,
500  num_peers * sizeof(struct GNUNET_PeerIdentity));
501  cb_cls = req_handle->cls;
502  RPS_sampler_request_cancel (req_handle);
503  req_handle = NULL;
504  tmp_cb (peers, num_peers, cb_cls);
505  GNUNET_free (peers);
506  }
507 }
508 
509 
520 static void
522  const struct GNUNET_PeerIdentity *id,
523  double probability,
524  uint32_t num_observed)
525 {
527 
528  (void) id;
530  struct GNUNET_PeerIdentity *peer;
531  void *cb_cls;
532  (void) probability;
533  (void) num_observed;
534 
536  "Got single peer with additional info\n");
537 
538  GNUNET_assert (NULL != req_handle->callback);
539 
541  "returning single peer with info to the client\n");
542 
543  /* Copy pointers and peers temporarily as they
544  * might be deleted from within the callback */
545  tmp_cb = req_handle->callback;
546  peer = GNUNET_new (struct GNUNET_PeerIdentity);
547  GNUNET_memcpy (peer,
548  req_handle->id,
549  sizeof(struct GNUNET_PeerIdentity));
550  cb_cls = req_handle->cls;
552  req_handle = NULL;
553  tmp_cb (peer, cb_cls, probability, num_observed);
554  GNUNET_free (peer);
555 }
556 
557 
572  uint32_t num_peers,
574  void *cls)
575 {
576  uint32_t i;
578  struct GetPeerCls *gpc;
579 
580  GNUNET_assert (0 != sampler->sampler_size);
581  if (0 == num_peers)
582  return NULL;
583 
584  // TODO check if we have too much (distinct) sampled peers
585  req_handle = GNUNET_new (struct RPS_SamplerRequestHandle);
586  req_handle->num_peers = num_peers;
587  req_handle->cur_num_peers = 0;
588  req_handle->ids = GNUNET_new_array (num_peers, struct GNUNET_PeerIdentity);
589  req_handle->sampler = sampler;
590  req_handle->callback = cb;
591  req_handle->cls = cls;
593  sampler->req_handle_tail,
594  req_handle);
595 
597  "Scheduling requests for %" PRIu32 " peers\n", num_peers);
598 
599  for (i = 0; i < num_peers; i++)
600  {
601  gpc = GNUNET_new (struct GetPeerCls);
602  gpc->req_handle = req_handle;
603  gpc->req_single_info_handle = NULL;
604  gpc->cont = check_n_peers_ready;
605  gpc->cont_cls = req_handle;
606  gpc->id = &req_handle->ids[i];
607 
609  req_handle->gpc_tail,
610  gpc);
611  // maybe add a little delay
613  gpc);
614  }
615  return req_handle;
616 }
617 
618 
629  void *cls)
630 {
632  struct GetPeerCls *gpc;
633 
634  GNUNET_assert (0 != sampler->sampler_size);
635 
636  // TODO check if we have too much (distinct) sampled peers
637  req_handle = GNUNET_new (struct RPS_SamplerRequestHandleSingleInfo);
638  req_handle->id = GNUNET_malloc (sizeof(struct GNUNET_PeerIdentity));
639  req_handle->sampler = sampler;
640  req_handle->callback = cb;
641  req_handle->cls = cls;
643  sampler->req_handle_single_tail,
644  req_handle);
645 
646  gpc = GNUNET_new (struct GetPeerCls);
647  gpc->req_handle = NULL;
650  gpc->cont_cls = req_handle;
651  gpc->id = req_handle->id;
652 
654  req_handle->gpc_tail,
655  gpc);
656  // maybe add a little delay
658  gpc);
659  return req_handle;
660 }
661 
662 
668 void
670 {
671  struct GetPeerCls *i;
672 
673  while (NULL != (i = req_handle->gpc_head))
674  {
676  req_handle->gpc_tail,
677  i);
678  if (NULL != i->get_peer_task)
679  {
681  }
682  if (NULL != i->notify_ctx)
683  {
685  req_handle->sampler->notify_ctx_tail,
686  i->notify_ctx);
687  GNUNET_free (i->notify_ctx);
688  i->notify_ctx = NULL;
689  }
690  GNUNET_free (i);
691  }
692  GNUNET_free (req_handle->ids);
693  req_handle->ids = NULL;
695  req_handle->sampler->req_handle_tail,
696  req_handle);
697  GNUNET_free (req_handle);
698 }
699 
700 
706 void
709 {
710  struct GetPeerCls *i;
711 
712  while (NULL != (i = req_single_info_handle->gpc_head))
713  {
714  GNUNET_CONTAINER_DLL_remove (req_single_info_handle->gpc_head,
715  req_single_info_handle->gpc_tail,
716  i);
717  if (NULL != i->get_peer_task)
718  {
720  }
721  if (NULL != i->notify_ctx)
722  {
724  req_single_info_handle->sampler->notify_ctx_head,
725  req_single_info_handle->sampler->
726  notify_ctx_tail,
727  i->notify_ctx);
728  GNUNET_free (i->notify_ctx);
729  i->notify_ctx = NULL;
730  }
731  GNUNET_free (i);
732  }
733  GNUNET_free (req_single_info_handle->id);
734  req_single_info_handle->id = NULL;
736  req_single_info_handle->sampler->req_handle_single_head,
737  req_single_info_handle->sampler->
738  req_handle_single_tail,
739  req_single_info_handle);
740  GNUNET_free (req_single_info_handle);
741 }
742 
743 
747 void
749 {
750  if (NULL != sampler->req_handle_head)
751  {
753  "There are still pending requests. Going to remove them.\n");
754  while (NULL != sampler->req_handle_head)
755  {
757  }
758  }
759  sampler_empty (sampler);
760  GNUNET_free (sampler);
761 }
762 
763 
764 /* 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:1280
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:966