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;
499  req_handle->ids,
500  num_peers * sizeof(struct GNUNET_PeerIdentity));
501  cb_cls = req_handle->cls;
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;
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
586  req_handle->num_peers = num_peers;
587  req_handle->cur_num_peers = 0;
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
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  {
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;
696  req_handle);
698 }
699 
700 
706 void
709 {
710  struct GetPeerCls *i;
711 
712  while (NULL != (i = req_single_info_handle->gpc_head))
713  {
716  i);
717  if (NULL != i->get_peer_task)
718  {
720  }
721  if (NULL != i->notify_ctx)
722  {
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  }
734  req_single_info_handle->id = NULL;
738  req_handle_single_tail,
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 */
static struct CadetPeer * peers
Operation to get peer ids.
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
#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_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_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:1296
void * GNUNET_SCHEDULER_cancel(struct GNUNET_SCHEDULER_Task *task)
Cancel the task with the specified identifier.
Definition: scheduler.c:972
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.