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-preferencesx",__VA_ARGS__)
40 #define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 10)
45 #define PREF_AGING_FACTOR 0.95
50 #define PREF_EPSILON 0.01
54 * Relative preferences for a peer
59 * Relative preference values
61 double f_rel[GNUNET_ATS_PreferenceCount];
64 * Peer identity for which we have these preferences.
66 struct GNUNET_PeerIdentity id;
73 static struct PeerRelative defvalues;
77 * Preference client, information we keep track of per client.
79 struct PreferenceClient
84 struct PreferenceClient *prev;
89 struct PreferenceClient *next;
94 struct PreferencePeer *p_head;
99 struct PreferencePeer *p_tail;
104 struct GNUNET_SERVER_Client *client;
107 * Array of sum of absolute preferences for this client
109 double f_abs_sum[GNUNET_ATS_PreferenceCount];
112 * Array of sum of relative preferences for this client
114 double f_rel_sum[GNUNET_ATS_PreferenceCount];
119 * Preference information per peer and client.
121 struct PreferencePeer
124 * Next in DLL of preference entries for the same client.
126 struct PreferencePeer *next;
129 * Previous in DLL of preference entries for the same client.
131 struct PreferencePeer *prev;
134 * Client that expressed this preferences.
136 struct PreferenceClient *client;
139 * Peer identity for which the preference was expressed.
141 struct GNUNET_PeerIdentity id;
144 * Absolute preference values for all preference types
146 double f_abs[GNUNET_ATS_PreferenceCount];
149 * Relative preference values for all preference types
151 double f_rel[GNUNET_ATS_PreferenceCount];
154 * Absolute point of time of next aging process
156 struct GNUNET_TIME_Absolute next_aging[GNUNET_ATS_PreferenceCount];
161 * Hashmap to store peer information for preference normalization
163 static struct GNUNET_CONTAINER_MultiPeerMap *preference_peers;
166 * Clients in DLL: head
168 static struct PreferenceClient *pc_head;
171 * Clients in DLL: tail
173 static struct PreferenceClient *pc_tail;
176 * Handle for task we run periodically to age preferences over time.
178 static struct GNUNET_SCHEDULER_Task *aging_task;
185 * @param kind the kind
186 * @param rp the relative peer struct
187 * @return the new relative preference
190 update_relative_values_for_peer (const struct GNUNET_PeerIdentity *id,
191 enum GNUNET_ATS_PreferenceKind kind,
192 struct PeerRelative *rp)
194 struct PreferenceClient *c_cur;
195 struct PreferencePeer *p_cur;
199 unsigned int peer_count;
205 /* For all clients */
206 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
208 /* For peer entries with this id */
209 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
211 f_rel_sum += p_cur->f_rel[kind];
212 if (0 == memcmp (id, &p_cur->id, sizeof(struct GNUNET_PeerIdentity)))
215 f_rel_total += p_cur->f_rel[kind];
220 LOG (GNUNET_ERROR_TYPE_DEBUG,
221 "%u clients have a total relative preference for peer `%s' `%s' of %.3f and for %s in total %.3f\n",
224 GNUNET_ATS_print_preference_type (kind),
226 GNUNET_ATS_print_preference_type (kind),
229 /* Find entry for the peer containing relative values in the hashmap */
232 backup = rp->f_rel[kind];
234 rp->f_rel[kind] = f_rel_total / f_rel_sum;
237 /* No client had any preferences for this type and any peer */
238 rp->f_rel[kind] = DEFAULT_REL_PREFERENCE;
240 if (backup != rp->f_rel[kind])
241 GAS_plugin_notify_preference_changed (&rp->id, kind,
251 update_iterator (void *cls,
252 const struct GNUNET_PeerIdentity *key,
255 enum GNUNET_ATS_PreferenceKind *kind = cls;
256 struct PeerRelative *pr = value;
258 update_relative_values_for_peer (key,
266 * Recalculate preference for a specific ATS property
268 * @param c the preference client
269 * @param kind the preference kind
273 recalculate_relative_preferences (struct PreferenceClient *c,
274 enum GNUNET_ATS_PreferenceKind kind)
276 struct PreferencePeer *p_cur;
278 /* For this client: sum of absolute preference values for this preference */
279 c->f_abs_sum[kind] = 0.0;
280 /* For this client: sum of relative preference values for this preference
282 * Note: this value should also be 1.0, but:
283 * if no preferences exist due to aging, this value can be 0.0
284 * and the client can be removed */
285 c->f_rel_sum[kind] = 0.0;
287 for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
288 c->f_abs_sum[kind] += p_cur->f_abs[kind];
289 LOG (GNUNET_ERROR_TYPE_DEBUG,
290 "Client %p has sum of total preferences for %s of %.3f\n",
291 c->client, GNUNET_ATS_print_preference_type (kind), c->f_abs_sum[kind]);
293 /* For all peers: calculate relative preference */
294 for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
296 /* Calculate relative preference for specific kind */
298 /* Every application has a preference for each peer between
299 * [0 .. 1] in relative values
300 * and [0 .. inf] in absolute values */
301 p_cur->f_rel[kind] = p_cur->f_abs[kind] / c->f_abs_sum[kind];
302 c->f_rel_sum[kind] += p_cur->f_rel[kind];
304 LOG (GNUNET_ERROR_TYPE_DEBUG,
305 "Client %p has relative preference for %s for peer `%s' of %.3f\n",
307 GNUNET_ATS_print_preference_type (kind),
308 GNUNET_i2s (&p_cur->id),
320 run_preference_update (struct PreferenceClient *c_cur,
321 struct PreferencePeer *p_cur,
322 enum GNUNET_ATS_PreferenceKind kind,
327 /* Update relative value */
328 old_value = p_cur->f_rel[kind];
329 recalculate_relative_preferences (c_cur, kind);
330 if (p_cur->f_rel[kind] == old_value)
333 /* Relative preference value changed, recalculate for all peers */
334 GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
341 * Reduce absolute preferences since they got old
343 * @param cls the PreferencePeer
347 preference_aging (void *cls,
348 const struct GNUNET_SCHEDULER_TaskContext *tc)
350 struct PreferencePeer *p;
351 struct PreferenceClient *cur_client;
353 unsigned int values_to_update;
357 values_to_update = 0;
360 for (cur_client = pc_head; NULL != cur_client; cur_client = cur_client->next)
362 for (p = cur_client->p_head; NULL != p; p = p->next)
364 /* Aging absolute values: */
365 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
368 == GNUNET_TIME_absolute_get_remaining (p->next_aging[i]).rel_value_us)
370 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
371 "Aging preference for peer `%s'\n", GNUNET_i2s (&p->id));
372 backup = p->f_abs[i];
373 if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
374 p->f_abs[i] *= PREF_AGING_FACTOR;
376 if (p->f_abs[i] <= DEFAULT_ABS_PREFERENCE + PREF_EPSILON)
377 p->f_abs[i] = DEFAULT_ABS_PREFERENCE;
379 if ( (p->f_abs[i] != DEFAULT_ABS_PREFERENCE) &&
380 (backup != p->f_abs[i]) )
382 GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
383 "Aged preference for peer `%s' from %.3f to %.3f\n",
384 GNUNET_i2s (&p->id), backup, p->f_abs[i]);
386 run_preference_update(cur_client, p, i, p->f_abs[i]);
388 p->next_aging[i] = GNUNET_TIME_absolute_add (
389 GNUNET_TIME_absolute_get (), PREF_AGING_INTERVAL);
397 if (values_to_update > 0)
399 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
400 "Rescheduling aging task due to %u elements to age\n",
402 aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
408 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
409 "No values to age left, not rescheduling aging task\n");
415 * Update the absolute preference value for a peer
416 * @param c the client
418 * @param kind the preference kind
419 * @param score_abs the absolute value
420 * @return the new relative preference value
423 update_abs_preference (struct PreferenceClient *c,
424 struct PreferencePeer *p,
425 enum GNUNET_ATS_PreferenceKind kind,
428 double score = score_abs;
430 /* Update preference value according to type */
433 case GNUNET_ATS_PREFERENCE_BANDWIDTH:
434 case GNUNET_ATS_PREFERENCE_LATENCY:
435 p->f_abs[kind] = score;
436 /* p->f_abs[kind] = (p->f_abs[kind] + score) / 2; */
437 p->next_aging[kind] = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get (),
438 PREF_AGING_INTERVAL);
440 case GNUNET_ATS_PREFERENCE_END:
449 * Normalize an updated preference value
451 * @param client the client with this preference
452 * @param peer the peer to change the preference for
453 * @param kind the kind to change the preference
454 * @param score_abs the normalized score
457 normalize_preference (struct GNUNET_SERVER_Client *client,
458 const struct GNUNET_PeerIdentity *peer,
459 enum GNUNET_ATS_PreferenceKind kind,
462 struct PreferenceClient *c_cur;
463 struct PreferencePeer *p_cur;
464 struct PeerRelative *r_cur;
468 LOG (GNUNET_ERROR_TYPE_DEBUG,
469 "Client changes preference for peer `%s' for `%s' to %.2f\n",
471 GNUNET_ATS_print_preference_type (kind),
474 if (kind >= GNUNET_ATS_PreferenceCount)
480 /* Find preference client */
481 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
482 if (client == c_cur->client)
484 /* Not found: create new preference client */
487 c_cur = GNUNET_new (struct PreferenceClient);
488 c_cur->client = client;
489 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
491 c_cur->f_abs_sum[i] = DEFAULT_ABS_PREFERENCE;
492 c_cur->f_rel_sum[i] = DEFAULT_REL_PREFERENCE;
494 GNUNET_CONTAINER_DLL_insert (pc_head,
497 LOG (GNUNET_ERROR_TYPE_DEBUG,
498 "Adding new client %p\n",
502 /* Find entry for peer */
503 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
504 if (0 == memcmp (&p_cur->id,
509 /* Not found: create new peer entry */
512 p_cur = GNUNET_new (struct PreferencePeer);
513 p_cur->client = c_cur;
515 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
517 /* Default value per peer absolute preference for a preference: 0 */
518 p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
519 /* Default value per peer relative preference for a quality: 1.0 */
520 p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
521 p_cur->next_aging[i] = GNUNET_TIME_UNIT_FOREVER_ABS;
523 LOG (GNUNET_ERROR_TYPE_DEBUG,
524 "Adding new peer %p for client %p\n",
527 GNUNET_CONTAINER_DLL_insert (c_cur->p_head,
532 /* Create struct for peer */
534 GNUNET_CONTAINER_multipeermap_get (preference_peers,
537 r_cur = GNUNET_new (struct PeerRelative);
539 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
540 r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
541 GNUNET_assert(GNUNET_OK ==
542 GNUNET_CONTAINER_multipeermap_put (preference_peers,
545 GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
548 /* Update absolute value */
549 old_value = p_cur->f_abs[kind];
550 update_abs_preference (c_cur, p_cur, kind, score_abs);
551 if (p_cur->f_abs[kind] == old_value)
554 GAS_plugin_solver_lock ();
555 run_preference_update (c_cur,
559 GAS_plugin_solver_unlock ();
561 if (NULL == aging_task)
562 aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
569 * Handle 'preference change' messages from clients.
571 * @param cls unused, NULL
572 * @param client client that sent the request
573 * @param message the request message
576 GAS_handle_preference_change (void *cls,
577 struct GNUNET_SERVER_Client *client,
578 const struct GNUNET_MessageHeader *message)
580 const struct ChangePreferenceMessage *msg;
581 const struct PreferenceInformation *pi;
586 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
587 "Received PREFERENCE_CHANGE message\n");
588 msize = ntohs (message->size);
589 if (msize < sizeof (struct ChangePreferenceMessage))
592 GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
595 msg = (const struct ChangePreferenceMessage *) message;
596 nump = ntohl (msg->num_preferences);
598 sizeof (struct ChangePreferenceMessage) +
599 nump * sizeof (struct PreferenceInformation))
602 GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
605 GNUNET_STATISTICS_update (GSA_stats,
606 "# preference change requests processed",
608 pi = (const struct PreferenceInformation *) &msg[1];
609 for (i = 0; i < nump; i++)
610 normalize_preference (client,
612 (enum GNUNET_ATS_PreferenceKind)
613 ntohl (pi[i].preference_kind),
614 pi[i].preference_value);
615 GNUNET_SERVER_receive_done (client, GNUNET_OK);
620 * Initialize preferences subsystem.
623 GAS_preference_init ()
627 preference_peers = GNUNET_CONTAINER_multipeermap_create (10, GNUNET_NO);
628 for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
629 defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
638 * @param value RelativePeer
639 * @return #GNUNET_OK to continue
642 free_peer (void *cls,
643 const struct GNUNET_PeerIdentity *key,
646 struct PeerRelative *rp = value;
649 GNUNET_CONTAINER_multipeermap_remove (preference_peers,
660 free_client (struct PreferenceClient *pc)
662 struct PreferencePeer *next_p;
663 struct PreferencePeer *p;
666 while (NULL != (p = next_p))
669 GNUNET_CONTAINER_DLL_remove(pc->p_head, pc->p_tail, p);
677 * Shutdown preferences subsystem.
680 GAS_preference_done ()
682 struct PreferenceClient *pc;
683 struct PreferenceClient *next_pc;
685 if (NULL != aging_task)
687 GNUNET_SCHEDULER_cancel (aging_task);
691 while (NULL != (pc = next_pc))
694 GNUNET_CONTAINER_DLL_remove (pc_head,
699 GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
702 GNUNET_CONTAINER_multipeermap_destroy (preference_peers);
708 * Get the normalized preference values for a specific peer or
709 * the default values if
713 * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
714 * default preferences if peer does not exist
717 GAS_preference_get_by_peer (void *cls,
718 const struct GNUNET_PeerIdentity *id)
720 struct PeerRelative *rp;
723 (rp = GNUNET_CONTAINER_multipeermap_get (preference_peers,
726 return defvalues.f_rel;
733 * A performance client disconnected
735 * @param client the client
738 GAS_preference_client_disconnect (struct GNUNET_SERVER_Client *client)
740 struct PreferenceClient *c_cur;
742 for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
743 if (client == c_cur->client)
747 GNUNET_CONTAINER_DLL_remove (pc_head,
754 /* end of gnunet-service-ats_preferences.c */