GNUnet 0.21.1
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
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
168void
170 uint32_t num_peers)
171{
172 sampler->num_peers_estim = num_peers;
173}
174
175
186void
188 double desired_probability)
189{
191}
192
193
194void
196 double deficiency_factor)
197{
199}
200
201
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
237unsigned int
239{
240 return sampler->sampler_size;
241}
242
243
252static void
253notify_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
284void
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
311void
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
337uint32_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
361static void
362sampler_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 */
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
422void
423RPS_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
435static void
436sampler_empty (struct RPS_Sampler *sampler)
437{
438 sampler_resize (sampler, 0);
439}
440
441
454static void
456 const struct GNUNET_PeerIdentity *id,
457 double probability,
458 uint32_t num_observed)
459{
461
462 (void) id;
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);
496 }
497}
498
499
510static 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;
536 peer = GNUNET_new (struct GNUNET_PeerIdentity);
537 GNUNET_memcpy (peer,
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;
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
646void
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);
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
684void
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);
707 i->notify_ctx = NULL;
708 }
709 GNUNET_free (i);
710 }
716 req_handle_single_tail,
719}
720
721
725void
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 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 struct GNUNET_RPS_Request_Handle * req_handle
Request handle.
Definition: gnunet-rps.c:41
struct GNUNET_CONTAINER_MultiPeerMap * peers
Map from PIDs to struct CadetPeer entries.
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.
struct RPS_SamplerElement * RPS_sampler_elem_create(void)
Create a sampler element and initialise it.
void RPS_sampler_elem_next(struct RPS_SamplerElement *sampler_elem, const struct GNUNET_PeerIdentity *new_ID)
Update a sampler element with a PeerID.
sampler element implementation
static unsigned int num_peers
Number of peers.
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.
void * GNUNET_SCHEDULER_cancel(struct GNUNET_SCHEDULER_Task *task)
Cancel the task with the specified identifier.
Definition: scheduler.c:981
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:1305
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.
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 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.
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.
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.
#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.
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.