2 This file is part of GNUnet.
3 Copyright (C) 2011-2015 Christian Grothoff (and other contributing authors)
5 GNUnet is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published
7 by the Free Software Foundation; either version 3, or (at your
8 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 General Public License for more details.
15 You should have received a copy of the GNU General Public License
16 along with GNUnet; see the file COPYING. If not, write to the
17 Free Software Foundation, Inc., 59 Temple Place - Suite 330,
18 Boston, MA 02111-1307, USA.
21 * @file ats/gnunet-service-ats_preferences.c
22 * @brief manage preferences expressed by clients
23 * @author Matthias Wachs
24 * @author Christian Grothoff
27 #include "gnunet-service-ats.h"
28 #include "gnunet-service-ats_addresses.h"
29 #include "gnunet-service-ats_performance.h"
30 #include "gnunet-service-ats_plugins.h"
31 #include "gnunet-service-ats_preferences.h"
32 #include "gnunet-service-ats_reservations.h"
35 #define LOG(kind,...) GNUNET_log_from (kind, "ats-preferences",__VA_ARGS__)
38 * How frequently do we age preference values?
40 #define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 10)
43 * By which factor do we age preferences expressed during
44 * each #PREF_AGING_INTERVAL?
46 #define PREF_AGING_FACTOR 0.95
49 * What is the lowest threshold up to which prefernce values
50 * are aged, and below which we consider them zero and thus
51 * no longer subject to aging?
53 #define PREF_EPSILON 0.01
57 * Relative preferences for a peer.
62 * Array of relative preference values, to be indexed by
63 * an `enum GNUNET_ATS_PreferenceKind`.
65 double f_rel[GNUNET_ATS_PREFERENCE_END];
68 * Number of clients that are expressing a preference for
69 * this peer. When this counter reaches zero, this entry
72 unsigned int num_clients;
77 * Default values, returned as our preferences if we do not
78 * have any preferences expressed for a peer.
80 static struct PeerRelative defvalues;
84 * Preference information per peer and client.
89 * Next in DLL of preference entries for the same client.
91 struct PreferencePeer *next;
94 * Previous in DLL of preference entries for the same client.
96 struct PreferencePeer *prev;
99 * Absolute preference values for all preference types
100 * as expressed by this client for this peer.
102 double f_abs[GNUNET_ATS_PREFERENCE_END];
105 * Relative preference values for all preference types,
106 * normalized in [0..1] based on how the respective
107 * client scored other peers.
109 double f_rel[GNUNET_ATS_PREFERENCE_END];
115 * Preference client, as in a client that expressed preferences
116 * for peers. This is the information we keep track of for each
119 struct PreferenceClient
123 * Next in client list
125 struct PreferenceClient *next;
128 * Previous in client peer list
130 struct PreferenceClient *prev;
135 struct GNUNET_SERVER_Client *client;
138 * Mapping peer identities to `struct PreferencePeer` entry
139 * for the respective peer.
141 struct GNUNET_CONTAINER_MultiPeerMap *peer2pref;
144 * Array of sums of absolute preferences for all
145 * peers as expressed by this client.
147 double f_abs_sum[GNUNET_ATS_PREFERENCE_END];
153 * Hashmap to store peer information for preference normalization.
154 * Maps the identity of a peer to a `struct PeerRelative` containing
155 * the current relative preference values for that peer.
157 static struct GNUNET_CONTAINER_MultiPeerMap *preference_peers;
160 * Clients in DLL: head
162 static struct PreferenceClient *pc_head;
165 * Clients in DLL: tail
167 static struct PreferenceClient *pc_tail;
170 * Handle for task we run periodically to age preferences over time.
172 static struct GNUNET_SCHEDULER_Task *aging_task;
176 * Closure for #sum_relative_preferences().
181 * Where to accumulate the result.
186 * Which kind of preference value are we adding up?
188 enum GNUNET_ATS_PreferenceKind kind;
193 * Add the relative preference for the kind given to the
196 * @param cls the `struct SumContext` with the kind and place
197 * to store the result
198 * @param peer ignored
199 * @param value the `struct PreferencePeer` for getting the rel pref.
203 sum_relative_preferences (void *cls,
204 const struct GNUNET_PeerIdentity *peer,
207 struct SumContext *sum_ctx = cls;
208 struct PreferencePeer *p_cur = value;
210 sum_ctx->f_rel_total += p_cur->f_rel[sum_ctx->kind];
216 * Update the total releative preference for a peer by summing
217 * up the relative preferences all clients have for this peer.
219 * @param id peer id of the peer for which we should do the update
220 * @param kind the kind of preference value to update
221 * @param rp the relative peer struct where we store the global result
222 * @return the new relative preference
225 update_relative_values_for_peer (const struct GNUNET_PeerIdentity *id,
226 enum GNUNET_ATS_PreferenceKind kind)
228 struct PreferenceClient *c_cur;
229 struct SumContext sum_ctx;
230 struct PeerRelative *rp;
232 sum_ctx.f_rel_total = 0.0;
234 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
235 GNUNET_CONTAINER_multipeermap_get_multiple (c_cur->peer2pref,
237 &sum_relative_preferences,
239 LOG (GNUNET_ERROR_TYPE_DEBUG,
240 "Total relative preference for peer `%s' for `%s' is %.3f\n",
242 GNUNET_ATS_print_preference_type (kind),
243 sum_ctx.f_rel_total);
244 rp = GNUNET_CONTAINER_multipeermap_get (preference_peers,
246 GNUNET_assert (NULL != rp);
247 if (rp->f_rel[kind] != sum_ctx.f_rel_total)
249 rp->f_rel[kind] = sum_ctx.f_rel_total;
250 GAS_plugin_notify_preference_changed (id,
258 * Free a peer's `struct PeerRelative`.
262 * @param value the `struct PeerRelative` to free.
263 * @return #GNUNET_OK to continue
266 free_peer (void *cls,
267 const struct GNUNET_PeerIdentity *key,
270 struct PeerRelative *rp = value;
272 GNUNET_assert (GNUNET_YES ==
273 GNUNET_CONTAINER_multipeermap_remove (preference_peers,
282 * Free `struct PreferencePeer` entry in map.
284 * @param cls the `struct PreferenceClient` with the map
285 * @param key the peer the entry is for
286 * @param value the `struct PreferencePeer` entry to free
287 * @return #GNUNET_OK (continue to iterate)
290 free_preference (void *cls,
291 const struct GNUNET_PeerIdentity *key,
294 struct PreferenceClient *pc = cls;
295 struct PreferencePeer *p = value;
296 struct PeerRelative *pr;
298 GNUNET_assert (GNUNET_OK ==
299 GNUNET_CONTAINER_multipeermap_remove (pc->peer2pref,
303 pr = GNUNET_CONTAINER_multipeermap_get (preference_peers,
305 GNUNET_assert (NULL != pr);
306 GNUNET_assert (pr->num_clients > 0);
308 if (0 == pr->num_clients)
319 * Closure for #age_values().
324 * Counter of values remaining to update, incremented for each value
325 * changed (to a new non-zero value).
327 unsigned int values_to_update;
330 * Client we are currently aging values for.
332 struct PreferenceClient *cur_client;
338 * Age preference values of the given peer.
341 * @param peer peer being aged
342 * @param value the `struct PreferencePeer` for the peer
343 * @return #GNUNET_OK (continue to iterate)
346 age_values (void *cls,
347 const struct GNUNET_PeerIdentity *peer,
350 struct AgeContext *ac = cls;
351 struct PreferencePeer *p = value;
356 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
358 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
359 "Aging preference for peer `%s'\n",
361 if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
362 p->f_abs[i] *= PREF_AGING_FACTOR;
363 if (p->f_abs[i] <= DEFAULT_ABS_PREFERENCE + PREF_EPSILON)
365 p->f_abs[i] = DEFAULT_ABS_PREFERENCE;
366 p->f_rel[i] = DEFAULT_REL_PREFERENCE;
367 update_relative_values_for_peer (peer,
372 ac->values_to_update++;
376 if (GNUNET_YES == dead)
378 /* all preferences are zero, remove this entry */
379 free_preference (ac->cur_client,
388 * Reduce absolute preferences since they got old.
394 preference_aging (void *cls,
395 const struct GNUNET_SCHEDULER_TaskContext *tc)
397 struct AgeContext ac;
400 GAS_plugin_solver_lock ();
401 ac.values_to_update = 0;
402 for (ac.cur_client = pc_head; NULL != ac.cur_client; ac.cur_client = ac.cur_client->next)
403 GNUNET_CONTAINER_multipeermap_iterate (ac.cur_client->peer2pref,
406 GAS_plugin_solver_unlock ();
407 if (ac.values_to_update > 0)
409 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
410 "Rescheduling aging task due to %u elements remaining to age\n",
411 ac.values_to_update);
412 if (NULL == aging_task)
413 aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
419 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
420 "No values to age left, not rescheduling aging task\n");
426 * Closure for #update_rel_sum() and #update_abs_sum().
431 * Preference client with the sum of all absolute scores.
433 struct PreferenceClient *pc;
436 * Which kind are we updating?
438 enum GNUNET_ATS_PreferenceKind kind;
444 * Compute updated absolute score for the client based on the
445 * current absolute scores for each peer.
447 * @param cls a `struct UpdateContext`
448 * @param peer peer being updated
449 * @param value the `struct PreferencePeer` for the peer
450 * @return #GNUNET_OK (continue to iterate)
453 update_abs_sum (void *cls,
454 const struct GNUNET_PeerIdentity *peer,
457 struct UpdateContext *uc = cls;
458 struct PreferencePeer *p_cur = value;
460 uc->pc->f_abs_sum[uc->kind] += p_cur->f_abs[uc->kind];
466 * Compute updated relative score for each peer based on the
467 * current absolute score given by this client.
469 * @param cls a `struct UpdateContext`
470 * @param peer peer being updated
471 * @param value the `struct PreferencePeer` for the peer (updated)
472 * @return #GNUNET_OK (continue to iterate)
475 update_rel_sum (void *cls,
476 const struct GNUNET_PeerIdentity *peer,
479 struct UpdateContext *uc = cls;
480 struct PreferencePeer *p_cur = value;
482 p_cur->f_rel[uc->kind] = p_cur->f_abs[uc->kind] / uc->pc->f_abs_sum[uc->kind];
483 LOG (GNUNET_ERROR_TYPE_DEBUG,
484 "Client has relative preference for %s for peer `%s' of %.3f\n",
485 GNUNET_ATS_print_preference_type (uc->kind),
487 p_cur->f_rel[uc->kind]);
493 * Recalculate preference for a specific ATS property
495 * @param c the preference client
496 * @param kind the preference kind
500 recalculate_relative_preferences (struct PreferenceClient *c,
501 enum GNUNET_ATS_PreferenceKind kind)
503 struct UpdateContext uc;
505 /* For this client: sum of absolute preference values for this preference */
508 c->f_abs_sum[kind] = 0.0;
510 /* For all peers: calculate sum of absolute preferences */
511 GNUNET_CONTAINER_multipeermap_iterate (c->peer2pref,
514 LOG (GNUNET_ERROR_TYPE_DEBUG,
515 "Client has sum of total preferences for %s of %.3f\n",
516 GNUNET_ATS_print_preference_type (kind),
519 /* For all peers: calculate relative preference */
520 GNUNET_CONTAINER_multipeermap_iterate (c->peer2pref,
527 * The relative preferences of one of the clients have
528 * changed, update the global preferences for the given
529 * peer and notify the plugin.
531 * @param value the kind of preference to calculate the
532 * new global relative preference values for
533 * @param key the peer to update relative preference values for
534 * @param value a `struct PeerRelative`, unused
537 update_iterator (void *cls,
538 const struct GNUNET_PeerIdentity *key,
541 enum GNUNET_ATS_PreferenceKind *kind = cls;
543 update_relative_values_for_peer (key,
550 * Update the absolute preference and calculate the
551 * new relative preference value.
553 * @param client the client with this preference
554 * @param peer the peer to change the preference for
555 * @param kind the kind to change the preference
556 * @param score_abs the normalized score
559 update_preference (struct GNUNET_SERVER_Client *client,
560 const struct GNUNET_PeerIdentity *peer,
561 enum GNUNET_ATS_PreferenceKind kind,
564 struct PreferenceClient *c_cur;
565 struct PreferencePeer *p_cur;
566 struct PeerRelative *r_cur;
569 if (kind >= GNUNET_ATS_PREFERENCE_END)
574 LOG (GNUNET_ERROR_TYPE_DEBUG,
575 "Client changes preference for peer `%s' for `%s' to %.2f\n",
577 GNUNET_ATS_print_preference_type (kind),
580 /* Find preference client */
581 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
582 if (client == c_cur->client)
584 /* Not found: create new preference client */
587 c_cur = GNUNET_new (struct PreferenceClient);
588 c_cur->client = client;
589 c_cur->peer2pref = GNUNET_CONTAINER_multipeermap_create (16,
591 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
592 c_cur->f_abs_sum[i] = DEFAULT_ABS_PREFERENCE;
593 GNUNET_CONTAINER_DLL_insert (pc_head,
598 /* check global peer entry exists */
600 (r_cur = GNUNET_CONTAINER_multipeermap_get (preference_peers,
603 /* Create struct for peer */
604 r_cur = GNUNET_new (struct PeerRelative);
605 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
606 r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
607 GNUNET_assert (GNUNET_OK ==
608 GNUNET_CONTAINER_multipeermap_put (preference_peers,
611 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
614 /* Find entry for peer */
615 p_cur = GNUNET_CONTAINER_multipeermap_get (c_cur->peer2pref,
619 /* Not found: create new peer entry */
620 p_cur = GNUNET_new (struct PreferencePeer);
621 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
623 /* Default value per peer absolute preference for a preference*/
624 p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
625 /* Default value per peer relative preference for a quality */
626 p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
628 GNUNET_assert (GNUNET_YES ==
629 GNUNET_CONTAINER_multipeermap_put (c_cur->peer2pref,
632 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
633 r_cur->num_clients++;
636 p_cur->f_abs[kind] += score_abs;
637 recalculate_relative_preferences (c_cur, kind);
638 GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
642 if (NULL == aging_task)
643 aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
650 * Handle 'preference change' messages from clients.
652 * @param cls unused, NULL
653 * @param client client that sent the request
654 * @param message the request message
657 GAS_handle_preference_change (void *cls,
658 struct GNUNET_SERVER_Client *client,
659 const struct GNUNET_MessageHeader *message)
661 const struct ChangePreferenceMessage *msg;
662 const struct PreferenceInformation *pi;
667 msize = ntohs (message->size);
668 if (msize < sizeof (struct ChangePreferenceMessage))
671 GNUNET_SERVER_receive_done (client,
675 msg = (const struct ChangePreferenceMessage *) message;
676 nump = ntohl (msg->num_preferences);
678 sizeof (struct ChangePreferenceMessage) +
679 nump * sizeof (struct PreferenceInformation)) ||
680 (UINT16_MAX / sizeof (struct PreferenceInformation) < nump) )
683 GNUNET_SERVER_receive_done (client,
687 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
688 "Received PREFERENCE_CHANGE message for peer `%s'\n",
689 GNUNET_i2s (&msg->peer));
690 GNUNET_STATISTICS_update (GSA_stats,
691 "# preference change requests processed",
694 pi = (const struct PreferenceInformation *) &msg[1];
695 GAS_plugin_solver_lock ();
696 for (i = 0; i < nump; i++)
697 update_preference (client,
699 (enum GNUNET_ATS_PreferenceKind) ntohl (pi[i].preference_kind),
700 pi[i].preference_value);
701 GAS_plugin_solver_unlock ();
702 GNUNET_SERVER_receive_done (client,
708 * Initialize preferences subsystem.
711 GAS_preference_init ()
715 preference_peers = GNUNET_CONTAINER_multipeermap_create (16,
717 for (i = 0; i < GNUNET_ATS_PREFERENCE_END; i++)
718 defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
723 * Shutdown preferences subsystem.
726 GAS_preference_done ()
728 struct PreferenceClient *pc;
729 struct PreferenceClient *next_pc;
731 if (NULL != aging_task)
733 GNUNET_SCHEDULER_cancel (aging_task);
737 while (NULL != (pc = next_pc))
740 GNUNET_CONTAINER_DLL_remove (pc_head,
743 GNUNET_CONTAINER_multipeermap_iterate (pc->peer2pref,
746 GNUNET_CONTAINER_multipeermap_destroy (pc->peer2pref);
749 GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
752 GNUNET_CONTAINER_multipeermap_destroy (preference_peers);
758 * Get the normalized preference values for a specific peer or
759 * the default values if
763 * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
764 * default preferences if peer does not exist
767 GAS_preference_get_by_peer (void *cls,
768 const struct GNUNET_PeerIdentity *id)
770 struct PeerRelative *rp;
773 (rp = GNUNET_CONTAINER_multipeermap_get (preference_peers,
776 return defvalues.f_rel;
783 * A performance client disconnected
785 * @param client the client
788 GAS_preference_client_disconnect (struct GNUNET_SERVER_Client *client)
790 struct PreferenceClient *c_cur;
792 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
793 if (client == c_cur->client)
797 GNUNET_CONTAINER_DLL_remove (pc_head,
800 GNUNET_CONTAINER_multipeermap_iterate (c_cur->peer2pref,
803 GNUNET_CONTAINER_multipeermap_destroy (c_cur->peer2pref);
808 /* end of gnunet-service-ats_preferences.c */