2 This file is part of GNUnet.
3 (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 ats service, interaction with 'performance' API
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-preferencesx",__VA_ARGS__)
37 #define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 10)
38 #define PREF_AGING_FACTOR 0.95
39 #define PREF_EPSILON 0.01
43 * Relative preferences for a peer
48 * Relative preference values
50 double f_rel[GNUNET_ATS_PreferenceCount];
55 struct GNUNET_PeerIdentity id;
62 struct GAS_Addresses_Preference_Clients
67 struct GAS_Addresses_Preference_Clients *next;
72 struct GAS_Addresses_Preference_Clients *prev;
82 * Preference requests DLL head
84 static struct GAS_Addresses_Preference_Clients *preference_clients_head;
87 * Preference requests DLL head
89 static struct GAS_Addresses_Preference_Clients *preference_clients_tail;
94 static int pref_clients;
99 static struct PeerRelative defvalues;
106 struct PreferenceClient
111 struct PreferenceClient *prev;
116 struct PreferenceClient *next;
124 * Array of sum of absolute preferences for this client
126 double f_abs_sum[GNUNET_ATS_PreferenceCount];
129 * Array of sum of relative preferences for this client
131 double f_rel_sum[GNUNET_ATS_PreferenceCount];
136 struct PreferencePeer *p_head;
141 struct PreferencePeer *p_tail;
148 struct PreferencePeer
153 struct PreferencePeer *next;
158 struct PreferencePeer *prev;
163 struct PreferenceClient *client;
168 struct GNUNET_PeerIdentity id;
171 * Absolute preference values for all preference types
173 double f_abs[GNUNET_ATS_PreferenceCount];
176 * Relative preference values for all preference types
178 double f_rel[GNUNET_ATS_PreferenceCount];
181 * Absolute point of time of next aging process
183 struct GNUNET_TIME_Absolute next_aging[GNUNET_ATS_PreferenceCount];
188 * Hashmap to store peer information for preference normalization
190 static struct GNUNET_CONTAINER_MultiPeerMap *preference_peers;
193 * Clients in DLL: head
195 static struct PreferenceClient *pc_head;
198 * Clients in DLL: tail
200 static struct PreferenceClient *pc_tail;
204 static struct GNUNET_SCHEDULER_Task * aging_task;
209 static struct GAS_Addresses_Preference_Clients *
210 find_preference_client (struct GNUNET_SERVER_Client *client)
212 struct GAS_Addresses_Preference_Clients *cur;
214 for (cur = preference_clients_head; NULL != cur; cur = cur->next)
215 if (cur->client == client)
225 * @param kind the kind
226 * @param rp the relative peer struct
227 * @return the new relative preference
230 update_relative_values_for_peer (const struct GNUNET_PeerIdentity *id,
231 enum GNUNET_ATS_PreferenceKind kind,
232 struct PeerRelative *rp)
234 struct PreferenceClient *c_cur;
235 struct PreferencePeer *p_cur;
239 unsigned int peer_count;
245 /* For all clients */
246 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
248 /* For peer entries with this id */
249 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
251 f_rel_sum += p_cur->f_rel[kind];
252 if (0 == memcmp (id, &p_cur->id, sizeof(struct GNUNET_PeerIdentity)))
255 f_rel_total += p_cur->f_rel[kind];
261 LOG (GNUNET_ERROR_TYPE_DEBUG,
262 "%u clients have a total relative preference for peer `%s' `%s' of %.3f and for %s in total %.3f\n",
263 peer_count, GNUNET_i2s (id),
264 GNUNET_ATS_print_preference_type (kind),
266 GNUNET_ATS_print_preference_type (kind),
269 /* Find entry for the peer containing relative values in the hashmap */
272 backup = rp->f_rel[kind];
274 rp->f_rel[kind] = f_rel_total / f_rel_sum;
277 /* No client had any preferences for this type and any peer */
278 rp->f_rel[kind] = DEFAULT_REL_PREFERENCE;
280 if (backup != rp->f_rel[kind])
281 GAS_normalized_preference_changed (&rp->id, kind, rp->f_rel[kind]);
287 update_iterator (void *cls,
288 const struct GNUNET_PeerIdentity *key,
291 enum GNUNET_ATS_PreferenceKind *kind = cls;
292 struct PeerRelative *pr = value;
294 update_relative_values_for_peer (key,
303 * Recalculate preference for a specific ATS property
305 * @param c the preference client
306 * @param kind the preference kind
310 recalculate_relative_preferences (struct PreferenceClient *c,
311 enum GNUNET_ATS_PreferenceKind kind)
313 struct PreferencePeer *p_cur;
315 /* For this client: sum of absolute preference values for this preference */
316 c->f_abs_sum[kind] = 0.0;
317 /* For this client: sum of relative preference values for this preference
319 * Note: this value should also be 1.0, but:
320 * if no preferences exist due to aging, this value can be 0.0
321 * and the client can be removed */
322 c->f_rel_sum[kind] = 0.0;
324 for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
325 c->f_abs_sum[kind] += p_cur->f_abs[kind];
326 LOG (GNUNET_ERROR_TYPE_DEBUG,
327 "Client %p has sum of total preferences for %s of %.3f\n",
328 c->client, GNUNET_ATS_print_preference_type (kind), c->f_abs_sum[kind]);
330 /* For all peers: calculate relative preference */
331 for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
333 /* Calculate relative preference for specific kind */
335 /* Every application has a preference for each peer between
336 * [0 .. 1] in relative values
337 * and [0 .. inf] in absolute values */
338 p_cur->f_rel[kind] = p_cur->f_abs[kind] / c->f_abs_sum[kind];
339 c->f_rel_sum[kind] += p_cur->f_rel[kind];
341 LOG (GNUNET_ERROR_TYPE_DEBUG,
342 "Client %p has relative preference for %s for peer `%s' of %.3f\n",
344 GNUNET_ATS_print_preference_type (kind),
345 GNUNET_i2s (&p_cur->id),
354 run_preference_update (struct PreferenceClient *c_cur,
355 struct PreferencePeer *p_cur,
356 enum GNUNET_ATS_PreferenceKind kind,
361 /* Update relative value */
362 old_value = p_cur->f_rel[kind];
363 recalculate_relative_preferences (c_cur, kind);
364 if (p_cur->f_rel[kind] == old_value)
367 /* Relative preference value changed, recalculate for all peers */
368 GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
377 * Reduce absolute preferences since they got old
379 * @param cls the PreferencePeer
383 preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
385 struct PreferencePeer *p;
386 struct PreferenceClient *cur_client;
388 int values_to_update;
392 values_to_update = 0;
395 for (cur_client = pc_head; NULL != cur_client; cur_client = cur_client->next)
397 for (p = cur_client->p_head; NULL != p; p = p->next)
399 /* Aging absolute values: */
400 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
403 == GNUNET_TIME_absolute_get_remaining (p->next_aging[i]).rel_value_us)
405 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
406 "Aging preference for peer `%s'\n", GNUNET_i2s (&p->id));
407 backup = p->f_abs[i];
408 if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
409 p->f_abs[i] *= PREF_AGING_FACTOR;
411 if (p->f_abs[i] <= DEFAULT_ABS_PREFERENCE + PREF_EPSILON)
412 p->f_abs[i] = DEFAULT_ABS_PREFERENCE;
414 if ( (p->f_abs[i] != DEFAULT_ABS_PREFERENCE) &&
415 (backup != p->f_abs[i]) )
417 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
418 "Aged preference for peer `%s' from %.3f to %.3f\n",
419 GNUNET_i2s (&p->id), backup, p->f_abs[i]);
421 run_preference_update(cur_client, p, i, p->f_abs[i]);
423 p->next_aging[i] = GNUNET_TIME_absolute_add (
424 GNUNET_TIME_absolute_get (), PREF_AGING_INTERVAL);
432 if (values_to_update > 0)
434 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
435 "Rescheduling aging task due to %u elements to age\n",
437 aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
438 &preference_aging, NULL );
441 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
442 "No values to age left, not rescheduling aging task\n");
448 * Update the absolute preference value for a peer
449 * @param c the client
451 * @param kind the preference kind
452 * @param score_abs the absolute value
453 * @return the new relative preference value
456 update_abs_preference (struct PreferenceClient *c,
457 struct PreferencePeer *p,
458 enum GNUNET_ATS_PreferenceKind kind,
461 double score = score_abs;
463 /* Update preference value according to type */
466 case GNUNET_ATS_PREFERENCE_BANDWIDTH:
467 case GNUNET_ATS_PREFERENCE_LATENCY:
468 p->f_abs[kind] = score;
469 /* p->f_abs[kind] = (p->f_abs[kind] + score) / 2; */
470 p->next_aging[kind] = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get (),
471 PREF_AGING_INTERVAL);
473 case GNUNET_ATS_PREFERENCE_END:
485 * A performance client disconnected
487 * @param client the client
490 GAS_preference_client_disconnect (struct GNUNET_SERVER_Client *client)
492 struct GAS_Addresses_Preference_Clients *pc;
494 if (NULL != (pc = find_preference_client (client)))
496 GNUNET_CONTAINER_DLL_remove (preference_clients_head,
497 preference_clients_tail,
500 GNUNET_assert (pref_clients > 0);
502 GNUNET_STATISTICS_set (GSA_stats,
503 "# active performance clients",
511 * Change the preference for a peer
513 * @param client the client sending this request
514 * @param peer the peer id
515 * @param kind the preference kind to change
516 * @param score_abs the new preference score
519 preference_change (struct GNUNET_SERVER_Client *client,
520 const struct GNUNET_PeerIdentity *peer,
521 enum GNUNET_ATS_PreferenceKind kind,
524 struct GAS_Addresses_Preference_Clients *pc;
526 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
527 "Received `%s' for peer `%s' for client %p\n", "CHANGE PREFERENCE",
528 GNUNET_i2s (peer), client);
531 GNUNET_CONTAINER_multipeermap_contains (GSA_addresses,
534 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
535 "Received `%s' for unknown peer `%s' from client %p\n",
536 "CHANGE PREFERENCE", GNUNET_i2s (peer), client);
540 if (NULL == find_preference_client (client))
542 pc = GNUNET_new (struct GAS_Addresses_Preference_Clients);
544 GNUNET_CONTAINER_DLL_insert (preference_clients_head,
545 preference_clients_tail,
548 GNUNET_STATISTICS_set (GSA_stats,
549 "# active performance clients",
553 GAS_plugin_update_preferences (client, peer, kind, score_abs);
558 * Handle 'preference change' messages from clients.
560 * @param cls unused, NULL
561 * @param client client that sent the request
562 * @param message the request message
565 GAS_handle_preference_change (void *cls,
566 struct GNUNET_SERVER_Client *client,
567 const struct GNUNET_MessageHeader *message)
569 const struct ChangePreferenceMessage *msg;
570 const struct PreferenceInformation *pi;
575 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
576 "Received `%s' message\n",
577 "PREFERENCE_CHANGE");
578 msize = ntohs (message->size);
579 if (msize < sizeof (struct ChangePreferenceMessage))
582 GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
585 msg = (const struct ChangePreferenceMessage *) message;
586 nump = ntohl (msg->num_preferences);
588 sizeof (struct ChangePreferenceMessage) +
589 nump * sizeof (struct PreferenceInformation))
592 GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
595 GNUNET_STATISTICS_update (GSA_stats,
596 "# preference change requests processed",
598 pi = (const struct PreferenceInformation *) &msg[1];
599 for (i = 0; i < nump; i++)
600 preference_change (client,
602 (enum GNUNET_ATS_PreferenceKind)
603 ntohl (pi[i].preference_kind),
604 pi[i].preference_value);
605 GNUNET_SERVER_receive_done (client, GNUNET_OK);
610 * Initialize preferences subsystem.
613 GAS_preference_init ()
617 preference_peers = GNUNET_CONTAINER_multipeermap_create (10, GNUNET_NO);
618 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
619 defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
628 * @param value RelativePeer
629 * @return #GNUNET_OK to continue
632 free_peer (void *cls,
633 const struct GNUNET_PeerIdentity *key,
636 struct PeerRelative *rp = value;
639 GNUNET_CONTAINER_multipeermap_remove (preference_peers,
650 free_client (struct PreferenceClient *pc)
652 struct PreferencePeer *next_p;
653 struct PreferencePeer *p;
656 while (NULL != (p = next_p))
659 GNUNET_CONTAINER_DLL_remove(pc->p_head, pc->p_tail, p);
667 * Shutdown preferences subsystem.
670 GAS_preference_done ()
672 struct GAS_Addresses_Preference_Clients *pcur;
673 struct PreferenceClient *pc;
674 struct PreferenceClient *next_pc;
676 if (NULL != aging_task)
678 GNUNET_SCHEDULER_cancel (aging_task);
682 while (NULL != (pc = next_pc))
685 GNUNET_CONTAINER_DLL_remove(pc_head, pc_tail, pc);
688 GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
691 GNUNET_CONTAINER_multipeermap_destroy (preference_peers);
693 while (NULL != (pcur = preference_clients_head))
695 GNUNET_CONTAINER_DLL_remove (preference_clients_head,
696 preference_clients_tail,
698 GNUNET_assert (pref_clients > 0);
700 GNUNET_STATISTICS_set (GSA_stats,
701 "# active performance clients",
710 * Normalize an updated preference value
712 * @param client the client with this preference
713 * @param peer the peer to change the preference for
714 * @param kind the kind to change the preference
715 * @param score_abs the normalized score
718 GAS_normalization_normalize_preference (struct GNUNET_SERVER_Client *client,
719 const struct GNUNET_PeerIdentity *peer,
720 enum GNUNET_ATS_PreferenceKind kind,
723 struct PreferenceClient *c_cur;
724 struct PreferencePeer *p_cur;
725 struct PeerRelative *r_cur;
729 LOG (GNUNET_ERROR_TYPE_DEBUG,
730 "Client changes preference for peer `%s' for `%s' to %.2f\n",
732 GNUNET_ATS_print_preference_type (kind),
735 if (kind >= GNUNET_ATS_PreferenceCount)
741 /* Find preference client */
742 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
744 if (client == c_cur->client)
747 /* Not found: create new preference client */
750 c_cur = GNUNET_new (struct PreferenceClient);
751 c_cur->client = client;
752 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
754 c_cur->f_abs_sum[i] = DEFAULT_ABS_PREFERENCE;
755 c_cur->f_rel_sum[i] = DEFAULT_REL_PREFERENCE;
758 GNUNET_CONTAINER_DLL_insert(pc_head, pc_tail, c_cur);
759 LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding new client %p \n", c_cur);
762 /* Find entry for peer */
763 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
764 if (0 == memcmp (&p_cur->id, peer, sizeof(p_cur->id)))
767 /* Not found: create new peer entry */
770 p_cur = GNUNET_new (struct PreferencePeer);
771 p_cur->client = c_cur;
773 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
775 /* Default value per peer absolute preference for a preference: 0 */
776 p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
777 /* Default value per peer relative preference for a quality: 1.0 */
778 p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
779 p_cur->next_aging[i] = GNUNET_TIME_UNIT_FOREVER_ABS;
781 LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding new peer %p for client %p \n",
783 GNUNET_CONTAINER_DLL_insert(c_cur->p_head, c_cur->p_tail, p_cur);
786 /* Create struct for peer */
787 if (NULL == GNUNET_CONTAINER_multipeermap_get (preference_peers, peer))
789 r_cur = GNUNET_new (struct PeerRelative);
791 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
792 r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
794 GNUNET_OK == GNUNET_CONTAINER_multipeermap_put (preference_peers,
795 &r_cur->id, r_cur, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
798 /* Update absolute value */
799 old_value = p_cur->f_abs[kind];
800 update_abs_preference (c_cur, p_cur, kind, score_abs);
801 if (p_cur->f_abs[kind] == old_value)
804 run_preference_update (c_cur, p_cur, kind, score_abs);
806 /* Start aging task */
807 if (NULL == aging_task)
808 aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
816 * Get the normalized preference values for a specific peer or
817 * the default values if
821 * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
822 * default preferences if peer does not exist
825 GAS_normalization_get_preferences_by_peer (void *cls,
826 const struct GNUNET_PeerIdentity *id)
828 GNUNET_assert(NULL != preference_peers);
829 GNUNET_assert(NULL != id);
831 struct PeerRelative *rp;
832 if (NULL == (rp = GNUNET_CONTAINER_multipeermap_get (preference_peers, id)))
834 return defvalues.f_rel;
841 * A performance client disconnected
843 * @param client the client
846 GAS_normalization_preference_client_disconnect (struct GNUNET_SERVER_Client *client)
848 struct PreferenceClient *c_cur;
849 /* Find preference client */
851 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
853 if (client == c_cur->client)
859 GNUNET_CONTAINER_DLL_remove(pc_head, pc_tail, c_cur);