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.
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/>.
19 * @file ats/gnunet-service-ats_preferences.c
20 * @brief manage preferences expressed by clients
21 * @author Matthias Wachs
22 * @author Christian Grothoff
25 #include "gnunet-service-ats.h"
26 #include "gnunet-service-ats_addresses.h"
27 #include "gnunet-service-ats_performance.h"
28 #include "gnunet-service-ats_plugins.h"
29 #include "gnunet-service-ats_preferences.h"
30 #include "gnunet-service-ats_reservations.h"
33 #define LOG(kind,...) GNUNET_log_from (kind, "ats-preferences",__VA_ARGS__)
36 * How frequently do we age preference values?
38 #define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 10)
41 * By which factor do we age preferences expressed during
42 * each #PREF_AGING_INTERVAL?
44 #define PREF_AGING_FACTOR 0.95
47 * What is the lowest threshold up to which prefernce values
48 * are aged, and below which we consider them zero and thus
49 * no longer subject to aging?
51 #define PREF_EPSILON 0.01
55 * Relative preferences for a peer.
60 * Array of relative preference values, to be indexed by
61 * an `enum GNUNET_ATS_PreferenceKind`.
63 double f_rel[GNUNET_ATS_PREFERENCE_END];
66 * Number of clients that are expressing a preference for
67 * this peer. When this counter reaches zero, this entry
70 unsigned int num_clients;
75 * Default values, returned as our preferences if we do not
76 * have any preferences expressed for a peer.
78 static struct PeerRelative defvalues;
82 * Preference information per peer and client.
87 * Next in DLL of preference entries for the same client.
89 struct PreferencePeer *next;
92 * Previous in DLL of preference entries for the same client.
94 struct PreferencePeer *prev;
97 * Absolute preference values for all preference types
98 * as expressed by this client for this peer.
100 double f_abs[GNUNET_ATS_PREFERENCE_END];
103 * Relative preference values for all preference types,
104 * normalized in [0..1] based on how the respective
105 * client scored other peers.
107 double f_rel[GNUNET_ATS_PREFERENCE_END];
113 * Preference client, as in a client that expressed preferences
114 * for peers. This is the information we keep track of for each
117 struct PreferenceClient
121 * Next in client list
123 struct PreferenceClient *next;
126 * Previous in client peer list
128 struct PreferenceClient *prev;
133 struct GNUNET_SERVICE_Client *client;
136 * Mapping peer identities to `struct PreferencePeer` entry
137 * for the respective peer.
139 struct GNUNET_CONTAINER_MultiPeerMap *peer2pref;
142 * Array of sums of absolute preferences for all
143 * peers as expressed by this client.
145 double f_abs_sum[GNUNET_ATS_PREFERENCE_END];
151 * Hashmap to store peer information for preference normalization.
152 * Maps the identity of a peer to a `struct PeerRelative` containing
153 * the current relative preference values for that peer.
155 static struct GNUNET_CONTAINER_MultiPeerMap *preference_peers;
158 * Clients in DLL: head
160 static struct PreferenceClient *pc_head;
163 * Clients in DLL: tail
165 static struct PreferenceClient *pc_tail;
168 * Handle for task we run periodically to age preferences over time.
170 static struct GNUNET_SCHEDULER_Task *aging_task;
174 * Closure for #sum_relative_preferences().
179 * Where to accumulate the result.
184 * Which kind of preference value are we adding up?
186 enum GNUNET_ATS_PreferenceKind kind;
191 * Add the relative preference for the kind given to the
194 * @param cls the `struct SumContext` with the kind and place
195 * to store the result
196 * @param peer ignored
197 * @param value the `struct PreferencePeer` for getting the rel pref.
201 sum_relative_preferences (void *cls,
202 const struct GNUNET_PeerIdentity *peer,
205 struct SumContext *sum_ctx = cls;
206 struct PreferencePeer *p_cur = value;
208 sum_ctx->f_rel_total += p_cur->f_rel[sum_ctx->kind];
214 * Update the total releative preference for a peer by summing
215 * up the relative preferences all clients have for this peer.
217 * @param id peer id of the peer for which we should do the update
218 * @param kind the kind of preference value to update
219 * @return the new relative preference
222 update_relative_values_for_peer (const struct GNUNET_PeerIdentity *id,
223 enum GNUNET_ATS_PreferenceKind kind)
225 struct PreferenceClient *c_cur;
226 struct SumContext sum_ctx;
227 struct PeerRelative *rp;
229 sum_ctx.f_rel_total = 0.0;
231 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
232 GNUNET_CONTAINER_multipeermap_get_multiple (c_cur->peer2pref,
234 &sum_relative_preferences,
236 LOG (GNUNET_ERROR_TYPE_DEBUG,
237 "Total relative preference for peer `%s' for `%s' is %.3f\n",
239 GNUNET_ATS_print_preference_type (kind),
240 sum_ctx.f_rel_total);
241 rp = GNUNET_CONTAINER_multipeermap_get (preference_peers,
243 GNUNET_assert (NULL != rp);
244 if (rp->f_rel[kind] != sum_ctx.f_rel_total)
246 rp->f_rel[kind] = sum_ctx.f_rel_total;
247 GAS_plugin_notify_preference_changed (id,
255 * Free a peer's `struct PeerRelative`.
259 * @param value the `struct PeerRelative` to free.
260 * @return #GNUNET_OK to continue
263 free_peer (void *cls,
264 const struct GNUNET_PeerIdentity *key,
267 struct PeerRelative *rp = value;
269 GNUNET_assert (GNUNET_YES ==
270 GNUNET_CONTAINER_multipeermap_remove (preference_peers,
279 * Free `struct PreferencePeer` entry in map.
281 * @param cls the `struct PreferenceClient` with the map
282 * @param key the peer the entry is for
283 * @param value the `struct PreferencePeer` entry to free
284 * @return #GNUNET_OK (continue to iterate)
287 free_preference (void *cls,
288 const struct GNUNET_PeerIdentity *key,
291 struct PreferenceClient *pc = cls;
292 struct PreferencePeer *p = value;
293 struct PeerRelative *pr;
295 GNUNET_assert (GNUNET_OK ==
296 GNUNET_CONTAINER_multipeermap_remove (pc->peer2pref,
300 pr = GNUNET_CONTAINER_multipeermap_get (preference_peers,
302 GNUNET_assert (NULL != pr);
303 GNUNET_assert (pr->num_clients > 0);
305 if (0 == pr->num_clients)
316 * Closure for #age_values().
321 * Counter of values remaining to update, incremented for each value
322 * changed (to a new non-zero value).
324 unsigned int values_to_update;
327 * Client we are currently aging values for.
329 struct PreferenceClient *cur_client;
335 * Age preference values of the given peer.
338 * @param peer peer being aged
339 * @param value the `struct PreferencePeer` for the peer
340 * @return #GNUNET_OK (continue to iterate)
343 age_values (void *cls,
344 const struct GNUNET_PeerIdentity *peer,
347 struct AgeContext *ac = cls;
348 struct PreferencePeer *p = value;
353 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
355 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
356 "Aging preference for peer `%s'\n",
358 if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
359 p->f_abs[i] *= PREF_AGING_FACTOR;
360 if (p->f_abs[i] <= DEFAULT_ABS_PREFERENCE + PREF_EPSILON)
362 p->f_abs[i] = DEFAULT_ABS_PREFERENCE;
363 p->f_rel[i] = DEFAULT_REL_PREFERENCE;
364 update_relative_values_for_peer (peer,
369 ac->values_to_update++;
373 if (GNUNET_YES == dead)
375 /* all preferences are zero, remove this entry */
376 free_preference (ac->cur_client,
385 * Reduce absolute preferences since they got old.
390 preference_aging (void *cls)
392 struct AgeContext ac;
395 GAS_plugin_solver_lock ();
396 ac.values_to_update = 0;
397 for (ac.cur_client = pc_head; NULL != ac.cur_client; ac.cur_client = ac.cur_client->next)
398 GNUNET_CONTAINER_multipeermap_iterate (ac.cur_client->peer2pref,
401 GAS_plugin_solver_unlock ();
402 if (ac.values_to_update > 0)
404 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
405 "Rescheduling aging task due to %u elements remaining to age\n",
406 ac.values_to_update);
407 if (NULL == aging_task)
408 aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
414 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
415 "No values to age left, not rescheduling aging task\n");
421 * Closure for #update_rel_sum() and #update_abs_sum().
426 * Preference client with the sum of all absolute scores.
428 struct PreferenceClient *pc;
431 * Which kind are we updating?
433 enum GNUNET_ATS_PreferenceKind kind;
439 * Compute updated absolute score for the client based on the
440 * current absolute scores for each peer.
442 * @param cls a `struct UpdateContext`
443 * @param peer peer being updated
444 * @param value the `struct PreferencePeer` for the peer
445 * @return #GNUNET_OK (continue to iterate)
448 update_abs_sum (void *cls,
449 const struct GNUNET_PeerIdentity *peer,
452 struct UpdateContext *uc = cls;
453 struct PreferencePeer *p_cur = value;
455 uc->pc->f_abs_sum[uc->kind] += p_cur->f_abs[uc->kind];
461 * Compute updated relative score for each peer based on the
462 * current absolute score given by this client.
464 * @param cls a `struct UpdateContext`
465 * @param peer peer being updated
466 * @param value the `struct PreferencePeer` for the peer (updated)
467 * @return #GNUNET_OK (continue to iterate)
470 update_rel_sum (void *cls,
471 const struct GNUNET_PeerIdentity *peer,
474 struct UpdateContext *uc = cls;
475 struct PreferencePeer *p_cur = value;
477 p_cur->f_rel[uc->kind] = p_cur->f_abs[uc->kind] / uc->pc->f_abs_sum[uc->kind];
478 LOG (GNUNET_ERROR_TYPE_DEBUG,
479 "Client has relative preference for %s for peer `%s' of %.3f\n",
480 GNUNET_ATS_print_preference_type (uc->kind),
482 p_cur->f_rel[uc->kind]);
488 * Recalculate preference for a specific ATS property
490 * @param c the preference client
491 * @param kind the preference kind
495 recalculate_relative_preferences (struct PreferenceClient *c,
496 enum GNUNET_ATS_PreferenceKind kind)
498 struct UpdateContext uc;
500 /* For this client: sum of absolute preference values for this preference */
503 c->f_abs_sum[kind] = 0.0;
505 /* For all peers: calculate sum of absolute preferences */
506 GNUNET_CONTAINER_multipeermap_iterate (c->peer2pref,
509 LOG (GNUNET_ERROR_TYPE_DEBUG,
510 "Client has sum of total preferences for %s of %.3f\n",
511 GNUNET_ATS_print_preference_type (kind),
514 /* For all peers: calculate relative preference */
515 GNUNET_CONTAINER_multipeermap_iterate (c->peer2pref,
522 * The relative preferences of one of the clients have
523 * changed, update the global preferences for the given
524 * peer and notify the plugin.
526 * @param cls the kind of preference to calculate the
527 * new global relative preference values for
528 * @param key the peer to update relative preference values for
529 * @param value a `struct PeerRelative`, unused
532 update_iterator (void *cls,
533 const struct GNUNET_PeerIdentity *key,
536 enum GNUNET_ATS_PreferenceKind *kind = cls;
538 update_relative_values_for_peer (key,
545 * Update the absolute preference and calculate the
546 * new relative preference value.
548 * @param client the client with this preference
549 * @param peer the peer to change the preference for
550 * @param kind the kind to change the preference
551 * @param score_abs the normalized score
554 update_preference (struct GNUNET_SERVICE_Client *client,
555 const struct GNUNET_PeerIdentity *peer,
556 enum GNUNET_ATS_PreferenceKind kind,
559 struct PreferenceClient *c_cur;
560 struct PreferencePeer *p_cur;
561 struct PeerRelative *r_cur;
564 if (kind >= GNUNET_ATS_PREFERENCE_END)
569 LOG (GNUNET_ERROR_TYPE_DEBUG,
570 "Client changes preference for peer `%s' for `%s' to %.2f\n",
572 GNUNET_ATS_print_preference_type (kind),
575 /* Find preference client */
576 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
577 if (client == c_cur->client)
579 /* Not found: create new preference client */
582 c_cur = GNUNET_new (struct PreferenceClient);
583 c_cur->client = client;
584 c_cur->peer2pref = GNUNET_CONTAINER_multipeermap_create (16,
586 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
587 c_cur->f_abs_sum[i] = DEFAULT_ABS_PREFERENCE;
588 GNUNET_CONTAINER_DLL_insert (pc_head,
593 /* check global peer entry exists */
595 (r_cur = GNUNET_CONTAINER_multipeermap_get (preference_peers,
598 /* Create struct for peer */
599 r_cur = GNUNET_new (struct PeerRelative);
600 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
601 r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
602 GNUNET_assert (GNUNET_OK ==
603 GNUNET_CONTAINER_multipeermap_put (preference_peers,
606 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
609 /* Find entry for peer */
610 p_cur = GNUNET_CONTAINER_multipeermap_get (c_cur->peer2pref,
614 /* Not found: create new peer entry */
615 p_cur = GNUNET_new (struct PreferencePeer);
616 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
618 /* Default value per peer absolute preference for a preference*/
619 p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
620 /* Default value per peer relative preference for a quality */
621 p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
623 GNUNET_assert (GNUNET_YES ==
624 GNUNET_CONTAINER_multipeermap_put (c_cur->peer2pref,
627 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
628 r_cur->num_clients++;
631 p_cur->f_abs[kind] += score_abs;
632 recalculate_relative_preferences (c_cur, kind);
633 GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
637 if (NULL == aging_task)
638 aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
645 * Handle 'preference change' messages from clients.
647 * @param client the client that sent the request
648 * @param msg the request message
651 GAS_handle_preference_change (struct GNUNET_SERVICE_Client *client,
652 const struct ChangePreferenceMessage *msg)
654 const struct PreferenceInformation *pi;
657 nump = ntohl (msg->num_preferences);
658 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
659 "Received PREFERENCE_CHANGE message for peer `%s'\n",
660 GNUNET_i2s (&msg->peer));
661 GNUNET_STATISTICS_update (GSA_stats,
662 "# preference change requests processed",
665 pi = (const struct PreferenceInformation *) &msg[1];
666 GAS_plugin_solver_lock ();
667 for (uint32_t i = 0; i < nump; i++)
668 update_preference (client,
670 (enum GNUNET_ATS_PreferenceKind) ntohl (pi[i].preference_kind),
671 pi[i].preference_value);
672 GAS_plugin_solver_unlock ();
677 * Initialize preferences subsystem.
680 GAS_preference_init ()
684 preference_peers = GNUNET_CONTAINER_multipeermap_create (16,
686 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
687 defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
692 * Shutdown preferences subsystem.
695 GAS_preference_done ()
697 struct PreferenceClient *pc;
698 struct PreferenceClient *next_pc;
700 if (NULL != aging_task)
702 GNUNET_SCHEDULER_cancel (aging_task);
706 while (NULL != (pc = next_pc))
709 GNUNET_CONTAINER_DLL_remove (pc_head,
712 GNUNET_CONTAINER_multipeermap_iterate (pc->peer2pref,
715 GNUNET_CONTAINER_multipeermap_destroy (pc->peer2pref);
718 GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
721 GNUNET_CONTAINER_multipeermap_destroy (preference_peers);
727 * Get the normalized preference values for a specific peer or
728 * the default values if
732 * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
733 * default preferences if peer does not exist
736 GAS_preference_get_by_peer (void *cls,
737 const struct GNUNET_PeerIdentity *id)
739 struct PeerRelative *rp;
742 (rp = GNUNET_CONTAINER_multipeermap_get (preference_peers,
745 return defvalues.f_rel;
752 * A performance client disconnected
754 * @param client the client
757 GAS_preference_client_disconnect (struct GNUNET_SERVICE_Client *client)
759 struct PreferenceClient *c_cur;
761 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
762 if (client == c_cur->client)
766 GNUNET_CONTAINER_DLL_remove (pc_head,
769 GNUNET_CONTAINER_multipeermap_iterate (c_cur->peer2pref,
772 GNUNET_CONTAINER_multipeermap_destroy (c_cur->peer2pref);
777 /* end of gnunet-service-ats_preferences.c */