2 This file is part of GNUnet.
3 Copyright (C) 2011-2015 GNUnet e.V.
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.
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.
16 * @file ats/gnunet-service-ats_preferences.c
17 * @brief manage preferences expressed by clients
18 * @author Matthias Wachs
19 * @author Christian Grothoff
22 #include "gnunet-service-ats.h"
23 #include "gnunet-service-ats_addresses.h"
24 #include "gnunet-service-ats_performance.h"
25 #include "gnunet-service-ats_plugins.h"
26 #include "gnunet-service-ats_preferences.h"
27 #include "gnunet-service-ats_reservations.h"
30 #define LOG(kind,...) GNUNET_log_from (kind, "ats-preferences",__VA_ARGS__)
33 * How frequently do we age preference values?
35 #define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 10)
38 * By which factor do we age preferences expressed during
39 * each #PREF_AGING_INTERVAL?
41 #define PREF_AGING_FACTOR 0.95
44 * What is the lowest threshold up to which prefernce values
45 * are aged, and below which we consider them zero and thus
46 * no longer subject to aging?
48 #define PREF_EPSILON 0.01
52 * Relative preferences for a peer.
57 * Array of relative preference values, to be indexed by
58 * an `enum GNUNET_ATS_PreferenceKind`.
60 double f_rel[GNUNET_ATS_PREFERENCE_END];
63 * Number of clients that are expressing a preference for
64 * this peer. When this counter reaches zero, this entry
67 unsigned int num_clients;
72 * Default values, returned as our preferences if we do not
73 * have any preferences expressed for a peer.
75 static struct PeerRelative defvalues;
79 * Preference information per peer and client.
84 * Next in DLL of preference entries for the same client.
86 struct PreferencePeer *next;
89 * Previous in DLL of preference entries for the same client.
91 struct PreferencePeer *prev;
94 * Absolute preference values for all preference types
95 * as expressed by this client for this peer.
97 double f_abs[GNUNET_ATS_PREFERENCE_END];
100 * Relative preference values for all preference types,
101 * normalized in [0..1] based on how the respective
102 * client scored other peers.
104 double f_rel[GNUNET_ATS_PREFERENCE_END];
110 * Preference client, as in a client that expressed preferences
111 * for peers. This is the information we keep track of for each
114 struct PreferenceClient
118 * Next in client list
120 struct PreferenceClient *next;
123 * Previous in client peer list
125 struct PreferenceClient *prev;
130 struct GNUNET_SERVICE_Client *client;
133 * Mapping peer identities to `struct PreferencePeer` entry
134 * for the respective peer.
136 struct GNUNET_CONTAINER_MultiPeerMap *peer2pref;
139 * Array of sums of absolute preferences for all
140 * peers as expressed by this client.
142 double f_abs_sum[GNUNET_ATS_PREFERENCE_END];
148 * Hashmap to store peer information for preference normalization.
149 * Maps the identity of a peer to a `struct PeerRelative` containing
150 * the current relative preference values for that peer.
152 static struct GNUNET_CONTAINER_MultiPeerMap *preference_peers;
155 * Clients in DLL: head
157 static struct PreferenceClient *pc_head;
160 * Clients in DLL: tail
162 static struct PreferenceClient *pc_tail;
165 * Handle for task we run periodically to age preferences over time.
167 static struct GNUNET_SCHEDULER_Task *aging_task;
171 * Closure for #sum_relative_preferences().
176 * Where to accumulate the result.
181 * Which kind of preference value are we adding up?
183 enum GNUNET_ATS_PreferenceKind kind;
188 * Add the relative preference for the kind given to the
191 * @param cls the `struct SumContext` with the kind and place
192 * to store the result
193 * @param peer ignored
194 * @param value the `struct PreferencePeer` for getting the rel pref.
198 sum_relative_preferences (void *cls,
199 const struct GNUNET_PeerIdentity *peer,
202 struct SumContext *sum_ctx = cls;
203 struct PreferencePeer *p_cur = value;
205 sum_ctx->f_rel_total += p_cur->f_rel[sum_ctx->kind];
211 * Update the total releative preference for a peer by summing
212 * up the relative preferences all clients have for this peer.
214 * @param id peer id of the peer for which we should do the update
215 * @param kind the kind of preference value to update
216 * @return the new relative preference
219 update_relative_values_for_peer (const struct GNUNET_PeerIdentity *id,
220 enum GNUNET_ATS_PreferenceKind kind)
222 struct PreferenceClient *c_cur;
223 struct SumContext sum_ctx;
224 struct PeerRelative *rp;
226 sum_ctx.f_rel_total = 0.0;
228 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
229 GNUNET_CONTAINER_multipeermap_get_multiple (c_cur->peer2pref,
231 &sum_relative_preferences,
233 LOG (GNUNET_ERROR_TYPE_DEBUG,
234 "Total relative preference for peer `%s' for `%s' is %.3f\n",
236 GNUNET_ATS_print_preference_type (kind),
237 sum_ctx.f_rel_total);
238 rp = GNUNET_CONTAINER_multipeermap_get (preference_peers,
240 GNUNET_assert (NULL != rp);
241 if (rp->f_rel[kind] != sum_ctx.f_rel_total)
243 rp->f_rel[kind] = sum_ctx.f_rel_total;
244 GAS_plugin_notify_preference_changed (id,
252 * Free a peer's `struct PeerRelative`.
256 * @param value the `struct PeerRelative` to free.
257 * @return #GNUNET_OK to continue
260 free_peer (void *cls,
261 const struct GNUNET_PeerIdentity *key,
264 struct PeerRelative *rp = value;
266 GNUNET_assert (GNUNET_YES ==
267 GNUNET_CONTAINER_multipeermap_remove (preference_peers,
276 * Free `struct PreferencePeer` entry in map.
278 * @param cls the `struct PreferenceClient` with the map
279 * @param key the peer the entry is for
280 * @param value the `struct PreferencePeer` entry to free
281 * @return #GNUNET_OK (continue to iterate)
284 free_preference (void *cls,
285 const struct GNUNET_PeerIdentity *key,
288 struct PreferenceClient *pc = cls;
289 struct PreferencePeer *p = value;
290 struct PeerRelative *pr;
292 GNUNET_assert (GNUNET_OK ==
293 GNUNET_CONTAINER_multipeermap_remove (pc->peer2pref,
297 pr = GNUNET_CONTAINER_multipeermap_get (preference_peers,
299 GNUNET_assert (NULL != pr);
300 GNUNET_assert (pr->num_clients > 0);
302 if (0 == pr->num_clients)
313 * Closure for #age_values().
318 * Counter of values remaining to update, incremented for each value
319 * changed (to a new non-zero value).
321 unsigned int values_to_update;
324 * Client we are currently aging values for.
326 struct PreferenceClient *cur_client;
332 * Age preference values of the given peer.
335 * @param peer peer being aged
336 * @param value the `struct PreferencePeer` for the peer
337 * @return #GNUNET_OK (continue to iterate)
340 age_values (void *cls,
341 const struct GNUNET_PeerIdentity *peer,
344 struct AgeContext *ac = cls;
345 struct PreferencePeer *p = value;
350 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
352 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
353 "Aging preference for peer `%s'\n",
355 if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
356 p->f_abs[i] *= PREF_AGING_FACTOR;
357 if (p->f_abs[i] <= DEFAULT_ABS_PREFERENCE + PREF_EPSILON)
359 p->f_abs[i] = DEFAULT_ABS_PREFERENCE;
360 p->f_rel[i] = DEFAULT_REL_PREFERENCE;
361 update_relative_values_for_peer (peer,
366 ac->values_to_update++;
370 if (GNUNET_YES == dead)
372 /* all preferences are zero, remove this entry */
373 free_preference (ac->cur_client,
382 * Reduce absolute preferences since they got old.
387 preference_aging (void *cls)
389 struct AgeContext ac;
392 GAS_plugin_solver_lock ();
393 ac.values_to_update = 0;
394 for (ac.cur_client = pc_head; NULL != ac.cur_client; ac.cur_client = ac.cur_client->next)
395 GNUNET_CONTAINER_multipeermap_iterate (ac.cur_client->peer2pref,
398 GAS_plugin_solver_unlock ();
399 if (ac.values_to_update > 0)
401 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
402 "Rescheduling aging task due to %u elements remaining to age\n",
403 ac.values_to_update);
404 if (NULL == aging_task)
405 aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
411 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
412 "No values to age left, not rescheduling aging task\n");
418 * Closure for #update_rel_sum() and #update_abs_sum().
423 * Preference client with the sum of all absolute scores.
425 struct PreferenceClient *pc;
428 * Which kind are we updating?
430 enum GNUNET_ATS_PreferenceKind kind;
436 * Compute updated absolute score for the client based on the
437 * current absolute scores for each peer.
439 * @param cls a `struct UpdateContext`
440 * @param peer peer being updated
441 * @param value the `struct PreferencePeer` for the peer
442 * @return #GNUNET_OK (continue to iterate)
445 update_abs_sum (void *cls,
446 const struct GNUNET_PeerIdentity *peer,
449 struct UpdateContext *uc = cls;
450 struct PreferencePeer *p_cur = value;
452 uc->pc->f_abs_sum[uc->kind] += p_cur->f_abs[uc->kind];
458 * Compute updated relative score for each peer based on the
459 * current absolute score given by this client.
461 * @param cls a `struct UpdateContext`
462 * @param peer peer being updated
463 * @param value the `struct PreferencePeer` for the peer (updated)
464 * @return #GNUNET_OK (continue to iterate)
467 update_rel_sum (void *cls,
468 const struct GNUNET_PeerIdentity *peer,
471 struct UpdateContext *uc = cls;
472 struct PreferencePeer *p_cur = value;
474 p_cur->f_rel[uc->kind] = p_cur->f_abs[uc->kind] / uc->pc->f_abs_sum[uc->kind];
475 LOG (GNUNET_ERROR_TYPE_DEBUG,
476 "Client has relative preference for %s for peer `%s' of %.3f\n",
477 GNUNET_ATS_print_preference_type (uc->kind),
479 p_cur->f_rel[uc->kind]);
485 * Recalculate preference for a specific ATS property
487 * @param c the preference client
488 * @param kind the preference kind
492 recalculate_relative_preferences (struct PreferenceClient *c,
493 enum GNUNET_ATS_PreferenceKind kind)
495 struct UpdateContext uc;
497 /* For this client: sum of absolute preference values for this preference */
500 c->f_abs_sum[kind] = 0.0;
502 /* For all peers: calculate sum of absolute preferences */
503 GNUNET_CONTAINER_multipeermap_iterate (c->peer2pref,
506 LOG (GNUNET_ERROR_TYPE_DEBUG,
507 "Client has sum of total preferences for %s of %.3f\n",
508 GNUNET_ATS_print_preference_type (kind),
511 /* For all peers: calculate relative preference */
512 GNUNET_CONTAINER_multipeermap_iterate (c->peer2pref,
519 * The relative preferences of one of the clients have
520 * changed, update the global preferences for the given
521 * peer and notify the plugin.
523 * @param cls the kind of preference to calculate the
524 * new global relative preference values for
525 * @param key the peer to update relative preference values for
526 * @param value a `struct PeerRelative`, unused
529 update_iterator (void *cls,
530 const struct GNUNET_PeerIdentity *key,
533 enum GNUNET_ATS_PreferenceKind *kind = cls;
535 update_relative_values_for_peer (key,
542 * Update the absolute preference and calculate the
543 * new relative preference value.
545 * @param client the client with this preference
546 * @param peer the peer to change the preference for
547 * @param kind the kind to change the preference
548 * @param score_abs the normalized score
551 update_preference (struct GNUNET_SERVICE_Client *client,
552 const struct GNUNET_PeerIdentity *peer,
553 enum GNUNET_ATS_PreferenceKind kind,
556 struct PreferenceClient *c_cur;
557 struct PreferencePeer *p_cur;
558 struct PeerRelative *r_cur;
561 if (kind >= GNUNET_ATS_PREFERENCE_END)
566 LOG (GNUNET_ERROR_TYPE_DEBUG,
567 "Client changes preference for peer `%s' for `%s' to %.2f\n",
569 GNUNET_ATS_print_preference_type (kind),
572 /* Find preference client */
573 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
574 if (client == c_cur->client)
576 /* Not found: create new preference client */
579 c_cur = GNUNET_new (struct PreferenceClient);
580 c_cur->client = client;
581 c_cur->peer2pref = GNUNET_CONTAINER_multipeermap_create (16,
583 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
584 c_cur->f_abs_sum[i] = DEFAULT_ABS_PREFERENCE;
585 GNUNET_CONTAINER_DLL_insert (pc_head,
590 /* check global peer entry exists */
592 (r_cur = GNUNET_CONTAINER_multipeermap_get (preference_peers,
595 /* Create struct for peer */
596 r_cur = GNUNET_new (struct PeerRelative);
597 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
598 r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
599 GNUNET_assert (GNUNET_OK ==
600 GNUNET_CONTAINER_multipeermap_put (preference_peers,
603 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
606 /* Find entry for peer */
607 p_cur = GNUNET_CONTAINER_multipeermap_get (c_cur->peer2pref,
611 /* Not found: create new peer entry */
612 p_cur = GNUNET_new (struct PreferencePeer);
613 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
615 /* Default value per peer absolute preference for a preference*/
616 p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
617 /* Default value per peer relative preference for a quality */
618 p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
620 GNUNET_assert (GNUNET_YES ==
621 GNUNET_CONTAINER_multipeermap_put (c_cur->peer2pref,
624 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
625 r_cur->num_clients++;
628 p_cur->f_abs[kind] += score_abs;
629 recalculate_relative_preferences (c_cur, kind);
630 GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
634 if (NULL == aging_task)
635 aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
642 * Handle 'preference change' messages from clients.
644 * @param client the client that sent the request
645 * @param msg the request message
648 GAS_handle_preference_change (struct GNUNET_SERVICE_Client *client,
649 const struct ChangePreferenceMessage *msg)
651 const struct PreferenceInformation *pi;
654 nump = ntohl (msg->num_preferences);
655 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
656 "Received PREFERENCE_CHANGE message for peer `%s'\n",
657 GNUNET_i2s (&msg->peer));
658 GNUNET_STATISTICS_update (GSA_stats,
659 "# preference change requests processed",
662 pi = (const struct PreferenceInformation *) &msg[1];
663 GAS_plugin_solver_lock ();
664 for (uint32_t i = 0; i < nump; i++)
665 update_preference (client,
667 (enum GNUNET_ATS_PreferenceKind) ntohl (pi[i].preference_kind),
668 pi[i].preference_value);
669 GAS_plugin_solver_unlock ();
674 * Initialize preferences subsystem.
677 GAS_preference_init ()
681 preference_peers = GNUNET_CONTAINER_multipeermap_create (16,
683 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
684 defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
689 * Shutdown preferences subsystem.
692 GAS_preference_done ()
694 struct PreferenceClient *pc;
695 struct PreferenceClient *next_pc;
697 if (NULL != aging_task)
699 GNUNET_SCHEDULER_cancel (aging_task);
703 while (NULL != (pc = next_pc))
706 GNUNET_CONTAINER_DLL_remove (pc_head,
709 GNUNET_CONTAINER_multipeermap_iterate (pc->peer2pref,
712 GNUNET_CONTAINER_multipeermap_destroy (pc->peer2pref);
715 GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
718 GNUNET_CONTAINER_multipeermap_destroy (preference_peers);
724 * Get the normalized preference values for a specific peer or
725 * the default values if
729 * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
730 * default preferences if peer does not exist
733 GAS_preference_get_by_peer (void *cls,
734 const struct GNUNET_PeerIdentity *id)
736 struct PeerRelative *rp;
739 (rp = GNUNET_CONTAINER_multipeermap_get (preference_peers,
742 return defvalues.f_rel;
749 * A performance client disconnected
751 * @param client the client
754 GAS_preference_client_disconnect (struct GNUNET_SERVICE_Client *client)
756 struct PreferenceClient *c_cur;
758 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
759 if (client == c_cur->client)
763 GNUNET_CONTAINER_DLL_remove (pc_head,
766 GNUNET_CONTAINER_multipeermap_iterate (c_cur->peer2pref,
769 GNUNET_CONTAINER_multipeermap_destroy (c_cur->peer2pref);
774 /* end of gnunet-service-ats_preferences.c */