762caf8ea16f8269dea54bf00477b065c95611fb
[oweals/gnunet.git] / src / ats / gnunet-service-ats_preferences.c
1 /*
2      This file is part of GNUnet.
3      (C) 2011-2015 Christian Grothoff (and other contributing authors)
4
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.
9
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.
14
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.
19 */
20 /**
21  * @file ats/gnunet-service-ats_preferences.c
22  * @brief manage preferences expressed by clients
23  * @author Matthias Wachs
24  * @author Christian Grothoff
25  */
26 #include "platform.h"
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"
33 #include "ats.h"
34
35 #define LOG(kind,...) GNUNET_log_from (kind, "ats-preferencesx",__VA_ARGS__)
36
37 #define PREF_AGING_INTERVAL GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 10)
38
39 #define PREF_AGING_FACTOR 0.95
40
41 #define PREF_EPSILON 0.01
42
43
44 /**
45  * Relative preferences for a peer
46  */
47 struct PeerRelative
48 {
49   /**
50    * Relative preference values
51    */
52   double f_rel[GNUNET_ATS_PreferenceCount];
53
54   /**
55    * Peer identity for which we have these preferences.
56    */
57   struct GNUNET_PeerIdentity id;
58 };
59
60
61 /**
62  * Default values
63  */
64 static struct PeerRelative defvalues;
65
66
67 /**
68  * Preference client, information we keep track of per client.
69  */
70 struct PreferenceClient
71 {
72   /**
73    * Previous in DLL
74    */
75   struct PreferenceClient *prev;
76
77   /**
78    * Next in DLL
79    */
80   struct PreferenceClient *next;
81
82   /**
83    * Head of peer list
84    */
85   struct PreferencePeer *p_head;
86
87   /**
88    * Tail of peer list
89    */
90   struct PreferencePeer *p_tail;
91
92   /**
93    * Client handle
94    */
95   struct GNUNET_SERVER_Client *client;
96
97   /**
98    * Array of sum of absolute preferences for this client
99    */
100   double f_abs_sum[GNUNET_ATS_PreferenceCount];
101
102   /**
103    * Array of sum of relative preferences for this client
104    */
105   double f_rel_sum[GNUNET_ATS_PreferenceCount];
106 };
107
108
109 /**
110  * Preference information per peer and client.
111  */
112 struct PreferencePeer
113 {
114   /**
115    * Next in DLL of preference entries for the same client.
116    */
117   struct PreferencePeer *next;
118
119   /**
120    * Previous in DLL of preference entries for the same client.
121    */
122   struct PreferencePeer *prev;
123
124   /**
125    * Client that expressed this preferences.
126    */
127   struct PreferenceClient *client;
128
129   /**
130    * Peer identity for which the preference was expressed.
131    */
132   struct GNUNET_PeerIdentity id;
133
134   /**
135    * Absolute preference values for all preference types
136    */
137   double f_abs[GNUNET_ATS_PreferenceCount];
138
139   /**
140    * Relative preference values for all preference types
141    */
142   double f_rel[GNUNET_ATS_PreferenceCount];
143
144   /**
145    * Absolute point of time of next aging process
146    */
147   struct GNUNET_TIME_Absolute next_aging[GNUNET_ATS_PreferenceCount];
148 };
149
150
151 /**
152  * Hashmap to store peer information for preference normalization
153  */
154 static struct GNUNET_CONTAINER_MultiPeerMap *preference_peers;
155
156 /**
157  * Clients in DLL: head
158  */
159 static struct PreferenceClient *pc_head;
160
161 /**
162  * Clients in DLL: tail
163  */
164 static struct PreferenceClient *pc_tail;
165
166 /**
167  * Handle for task we run periodically to age preferences over time.
168  */
169 static struct GNUNET_SCHEDULER_Task *aging_task;
170
171
172 /**
173  * Update a peer
174  *
175  * @param id peer id
176  * @param kind the kind
177  * @param rp the relative peer struct
178  * @return the new relative preference
179  */
180 static void
181 update_relative_values_for_peer (const struct GNUNET_PeerIdentity *id,
182                                  enum GNUNET_ATS_PreferenceKind kind,
183                                  struct PeerRelative *rp)
184 {
185   struct PreferenceClient *c_cur;
186   struct PreferencePeer *p_cur;
187   double f_rel_total;
188   double f_rel_sum;
189   double backup;
190   unsigned int peer_count;
191
192   f_rel_sum = 0.0;
193   f_rel_total = 0.0;
194   peer_count = 0;
195
196   /* For all clients */
197   for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
198   {
199     /* For peer entries with this id */
200     for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
201     {
202       f_rel_sum += p_cur->f_rel[kind];
203       if (0 == memcmp (id, &p_cur->id, sizeof(struct GNUNET_PeerIdentity)))
204       {
205         peer_count ++;
206         f_rel_total += p_cur->f_rel[kind];
207       }
208
209     }
210   }
211
212   LOG (GNUNET_ERROR_TYPE_DEBUG,
213        "%u clients have a total relative preference for peer `%s' `%s' of %.3f and for %s in total %.3f\n",
214        peer_count,
215        GNUNET_i2s (id),
216        GNUNET_ATS_print_preference_type (kind),
217        f_rel_total,
218        GNUNET_ATS_print_preference_type (kind),
219        f_rel_sum);
220
221   /* Find entry for the peer containing relative values in the hashmap */
222   if (NULL != rp)
223   {
224     backup = rp->f_rel[kind];
225     if (f_rel_sum > 0)
226       rp->f_rel[kind] = f_rel_total / f_rel_sum;
227     else
228     {
229       /* No client had any preferences for this type and any peer */
230       rp->f_rel[kind] = DEFAULT_REL_PREFERENCE;
231     }
232     if (backup != rp->f_rel[kind])
233       GAS_normalized_preference_changed (&rp->id, kind, rp->f_rel[kind]);
234   }
235 }
236
237
238 /**
239  * FIXME
240  */
241 static int
242 update_iterator (void *cls,
243                  const struct GNUNET_PeerIdentity *key,
244                  void *value)
245 {
246   enum GNUNET_ATS_PreferenceKind *kind = cls;
247   struct PeerRelative *pr = value;
248
249   update_relative_values_for_peer (key,
250                                    *kind,
251                                    pr);
252   return GNUNET_OK;
253 }
254
255
256 /**
257  * Recalculate preference for a specific ATS property
258  *
259  * @param c the preference client
260  * @param kind the preference kind
261  * @return the result
262  */
263 static void
264 recalculate_relative_preferences (struct PreferenceClient *c,
265                                   enum GNUNET_ATS_PreferenceKind kind)
266 {
267   struct PreferencePeer *p_cur;
268
269   /* For this client: sum of absolute preference values for this preference */
270   c->f_abs_sum[kind] = 0.0;
271   /* For this client: sum of relative preference values for this preference
272    *
273    * Note: this value should also be 1.0, but:
274    * if no preferences exist due to aging, this value can be 0.0
275    * and the client can be removed */
276   c->f_rel_sum[kind] = 0.0;
277
278   for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
279     c->f_abs_sum[kind] += p_cur->f_abs[kind];
280   LOG (GNUNET_ERROR_TYPE_DEBUG,
281       "Client %p has sum of total preferences for %s of %.3f\n",
282       c->client, GNUNET_ATS_print_preference_type (kind), c->f_abs_sum[kind]);
283
284   /* For all peers: calculate relative preference */
285   for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
286   {
287     /* Calculate relative preference for specific kind */
288
289     /* Every application has a preference for each peer between
290      * [0 .. 1] in relative values
291      * and [0 .. inf] in absolute values */
292     p_cur->f_rel[kind] =  p_cur->f_abs[kind] / c->f_abs_sum[kind];
293     c->f_rel_sum[kind] += p_cur->f_rel[kind];
294
295     LOG (GNUNET_ERROR_TYPE_DEBUG,
296         "Client %p has relative preference for %s for peer `%s' of %.3f\n",
297         c->client,
298         GNUNET_ATS_print_preference_type (kind),
299         GNUNET_i2s (&p_cur->id),
300         p_cur->f_rel[kind]);
301   }
302
303 }
304
305
306 /**
307  * FIXME.
308  *
309  */
310 static void
311 run_preference_update (struct PreferenceClient *c_cur,
312                        struct PreferencePeer *p_cur,
313                        enum GNUNET_ATS_PreferenceKind kind,
314                        float score_abs)
315 {
316   double old_value;
317
318   /* Update relative value */
319   old_value = p_cur->f_rel[kind];
320   recalculate_relative_preferences (c_cur, kind);
321   if (p_cur->f_rel[kind] == old_value)
322     return;
323
324   /* Relative preference value changed, recalculate for all peers */
325   GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
326                                          &update_iterator,
327                                          &kind);
328 }
329
330
331 /**
332  * Reduce absolute preferences since they got old
333  *
334  * @param cls the PreferencePeer
335  * @param tc context
336  */
337 static void
338 preference_aging (void *cls,
339                   const struct GNUNET_SCHEDULER_TaskContext *tc)
340 {
341   struct PreferencePeer *p;
342   struct PreferenceClient *cur_client;
343   unsigned int i;
344   unsigned int values_to_update;
345   double backup;
346
347   aging_task = NULL;
348   values_to_update = 0;
349   cur_client = NULL;
350
351   for (cur_client = pc_head; NULL != cur_client; cur_client = cur_client->next)
352   {
353     for (p = cur_client->p_head; NULL != p; p = p->next)
354     {
355       /* Aging absolute values: */
356       for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
357       {
358         if (0
359             == GNUNET_TIME_absolute_get_remaining (p->next_aging[i]).rel_value_us)
360         {
361           GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
362               "Aging preference for peer `%s'\n", GNUNET_i2s (&p->id));
363           backup = p->f_abs[i];
364           if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
365             p->f_abs[i] *= PREF_AGING_FACTOR;
366
367           if (p->f_abs[i] <= DEFAULT_ABS_PREFERENCE + PREF_EPSILON)
368             p->f_abs[i] = DEFAULT_ABS_PREFERENCE;
369
370           if ( (p->f_abs[i] != DEFAULT_ABS_PREFERENCE) &&
371                (backup != p->f_abs[i]) )
372           {
373             GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
374                 "Aged preference for peer `%s' from %.3f to %.3f\n",
375                 GNUNET_i2s (&p->id), backup, p->f_abs[i]);
376
377             run_preference_update(cur_client, p, i, p->f_abs[i]);
378
379             p->next_aging[i] = GNUNET_TIME_absolute_add (
380                 GNUNET_TIME_absolute_get (), PREF_AGING_INTERVAL);
381             values_to_update++;
382           }
383         }
384       }
385     }
386   }
387
388   if (values_to_update > 0)
389   {
390     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
391                 "Rescheduling aging task due to %u elements to age\n",
392                 values_to_update);
393     aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
394                                                &preference_aging,
395                                                NULL);
396   }
397   else
398   {
399     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
400                 "No values to age left, not rescheduling aging task\n");
401   }
402 }
403
404
405 /**
406  * Update the absolute preference value for a peer
407  * @param c the client
408  * @param p the peer
409  * @param kind the preference kind
410  * @param score_abs the absolute value
411  * @return the new relative preference value
412  */
413 static void
414 update_abs_preference (struct PreferenceClient *c,
415                        struct PreferencePeer *p,
416                        enum GNUNET_ATS_PreferenceKind kind,
417                        float score_abs)
418 {
419   double score = score_abs;
420
421   /* Update preference value according to type */
422   switch (kind)
423   {
424   case GNUNET_ATS_PREFERENCE_BANDWIDTH:
425   case GNUNET_ATS_PREFERENCE_LATENCY:
426     p->f_abs[kind] = score;
427     /* p->f_abs[kind] = (p->f_abs[kind] + score) / 2;  */
428     p->next_aging[kind] = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get (),
429         PREF_AGING_INTERVAL);
430     break;
431   case GNUNET_ATS_PREFERENCE_END:
432     break;
433   default:
434     break;
435   }
436 }
437
438
439
440 /**
441  * Change the preference for a peer
442  *
443  * @param client the client sending this request
444  * @param peer the peer id
445  * @param kind the preference kind to change
446  * @param score_abs the new preference score
447  */
448 static void
449 preference_change (struct GNUNET_SERVER_Client *client,
450                     const struct GNUNET_PeerIdentity *peer,
451                     enum GNUNET_ATS_PreferenceKind kind,
452                     float score_abs)
453 {
454   if (GNUNET_NO ==
455       GNUNET_CONTAINER_multipeermap_contains (GSA_addresses,
456                                               peer))
457   {
458     GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
459                 "Received CHANGE_PREFERENCE for unknown peer `%s'\n",
460                 GNUNET_i2s (peer));
461     return;
462   }
463   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
464               "Received CHANGE_PREFERENCE for peer `%s'\n",
465               GNUNET_i2s (peer));
466   GAS_plugin_update_preferences (client,
467                                  peer,
468                                  kind,
469                                  score_abs);
470 }
471
472
473 /**
474  * Handle 'preference change' messages from clients.
475  *
476  * @param cls unused, NULL
477  * @param client client that sent the request
478  * @param message the request message
479  */
480 void
481 GAS_handle_preference_change (void *cls,
482                               struct GNUNET_SERVER_Client *client,
483                               const struct GNUNET_MessageHeader *message)
484 {
485   const struct ChangePreferenceMessage *msg;
486   const struct PreferenceInformation *pi;
487   uint16_t msize;
488   uint32_t nump;
489   uint32_t i;
490
491   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
492               "Received `%s' message\n",
493               "PREFERENCE_CHANGE");
494   msize = ntohs (message->size);
495   if (msize < sizeof (struct ChangePreferenceMessage))
496   {
497     GNUNET_break (0);
498     GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
499     return;
500   }
501   msg = (const struct ChangePreferenceMessage *) message;
502   nump = ntohl (msg->num_preferences);
503   if (msize !=
504       sizeof (struct ChangePreferenceMessage) +
505       nump * sizeof (struct PreferenceInformation))
506   {
507     GNUNET_break (0);
508     GNUNET_SERVER_receive_done (client, GNUNET_SYSERR);
509     return;
510   }
511   GNUNET_STATISTICS_update (GSA_stats,
512                             "# preference change requests processed",
513                             1, GNUNET_NO);
514   pi = (const struct PreferenceInformation *) &msg[1];
515   for (i = 0; i < nump; i++)
516     preference_change (client,
517                        &msg->peer,
518                        (enum GNUNET_ATS_PreferenceKind)
519                        ntohl (pi[i].preference_kind),
520                        pi[i].preference_value);
521   GNUNET_SERVER_receive_done (client, GNUNET_OK);
522 }
523
524
525 /**
526  * Initialize preferences subsystem.
527  */
528 void
529 GAS_preference_init ()
530 {
531   int i;
532
533   preference_peers = GNUNET_CONTAINER_multipeermap_create (10, GNUNET_NO);
534   for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
535     defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
536 }
537
538
539 /**
540  * Free a peer
541  *
542  * @param cls unused
543  * @param key the key
544  * @param value RelativePeer
545  * @return #GNUNET_OK to continue
546  */
547 static int
548 free_peer (void *cls,
549            const struct GNUNET_PeerIdentity *key,
550            void *value)
551 {
552   struct PeerRelative *rp = value;
553
554   if (GNUNET_YES ==
555       GNUNET_CONTAINER_multipeermap_remove (preference_peers,
556                                             key,
557                                             value))
558     GNUNET_free (rp);
559   else
560     GNUNET_break (0);
561   return GNUNET_OK;
562 }
563
564
565 static void
566 free_client (struct PreferenceClient *pc)
567 {
568   struct PreferencePeer *next_p;
569   struct PreferencePeer *p;
570
571   next_p = pc->p_head;
572   while (NULL != (p = next_p))
573   {
574     next_p = p->next;
575     GNUNET_CONTAINER_DLL_remove(pc->p_head, pc->p_tail, p);
576     GNUNET_free(p);
577   }
578   GNUNET_free(pc);
579 }
580
581
582 /**
583  * Shutdown preferences subsystem.
584  */
585 void
586 GAS_preference_done ()
587 {
588   struct PreferenceClient *pc;
589   struct PreferenceClient *next_pc;
590
591   if (NULL != aging_task)
592   {
593     GNUNET_SCHEDULER_cancel (aging_task);
594     aging_task = NULL;
595   }
596   next_pc = pc_head;
597   while (NULL != (pc = next_pc))
598   {
599     next_pc = pc->next;
600     GNUNET_CONTAINER_DLL_remove(pc_head, pc_tail, pc);
601     free_client (pc);
602   }
603   GNUNET_CONTAINER_multipeermap_iterate (preference_peers,
604                                          &free_peer,
605                                          NULL);
606   GNUNET_CONTAINER_multipeermap_destroy (preference_peers);
607
608 }
609
610
611 /**
612  * Normalize an updated preference value
613  *
614  * @param client the client with this preference
615  * @param peer the peer to change the preference for
616  * @param kind the kind to change the preference
617  * @param score_abs the normalized score
618  */
619 void
620 GAS_normalization_normalize_preference (struct GNUNET_SERVER_Client *client,
621                                         const struct GNUNET_PeerIdentity *peer,
622                                         enum GNUNET_ATS_PreferenceKind kind,
623                                         float score_abs)
624 {
625   struct PreferenceClient *c_cur;
626   struct PreferencePeer *p_cur;
627   struct PeerRelative *r_cur;
628   double old_value;
629   int i;
630
631   LOG (GNUNET_ERROR_TYPE_DEBUG,
632        "Client changes preference for peer `%s' for `%s' to %.2f\n",
633        GNUNET_i2s (peer),
634        GNUNET_ATS_print_preference_type (kind),
635        score_abs);
636
637   if (kind >= GNUNET_ATS_PreferenceCount)
638   {
639     GNUNET_break(0);
640     return;
641   }
642
643   /* Find preference client */
644   for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
645   {
646     if (client == c_cur->client)
647       break;
648   }
649   /* Not found: create new preference client */
650   if (NULL == c_cur)
651   {
652     c_cur = GNUNET_new (struct PreferenceClient);
653     c_cur->client = client;
654     for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
655     {
656       c_cur->f_abs_sum[i] = DEFAULT_ABS_PREFERENCE;
657       c_cur->f_rel_sum[i] = DEFAULT_REL_PREFERENCE;
658     }
659
660     GNUNET_CONTAINER_DLL_insert(pc_head, pc_tail, c_cur);
661     LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding new client %p \n", c_cur);
662   }
663
664   /* Find entry for peer */
665   for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
666     if (0 == memcmp (&p_cur->id, peer, sizeof(p_cur->id)))
667       break;
668
669   /* Not found: create new peer entry */
670   if (NULL == p_cur)
671   {
672     p_cur = GNUNET_new (struct PreferencePeer);
673     p_cur->client = c_cur;
674     p_cur->id = (*peer);
675     for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
676     {
677       /* Default value per peer absolute preference for a preference: 0 */
678       p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
679       /* Default value per peer relative preference for a quality: 1.0 */
680       p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
681       p_cur->next_aging[i] = GNUNET_TIME_UNIT_FOREVER_ABS;
682     }
683     LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding new peer %p for client %p \n",
684         p_cur, c_cur);
685     GNUNET_CONTAINER_DLL_insert(c_cur->p_head, c_cur->p_tail, p_cur);
686   }
687
688   /* Create struct for peer */
689   if (NULL == GNUNET_CONTAINER_multipeermap_get (preference_peers, peer))
690   {
691     r_cur = GNUNET_new (struct PeerRelative);
692     r_cur->id = (*peer);
693     for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
694       r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
695     GNUNET_assert(
696         GNUNET_OK == GNUNET_CONTAINER_multipeermap_put (preference_peers,
697             &r_cur->id, r_cur, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
698   }
699
700   /* Update absolute value */
701   old_value = p_cur->f_abs[kind];
702   update_abs_preference (c_cur, p_cur, kind, score_abs);
703   if (p_cur->f_abs[kind] == old_value)
704     return;
705
706   run_preference_update (c_cur, p_cur, kind, score_abs);
707
708   /* Start aging task */
709   if (NULL == aging_task)
710     aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
711                                                &preference_aging,
712                                                NULL);
713
714 }
715
716
717 /**
718  * Get the normalized preference values for a specific peer or
719  * the default values if
720  *
721  * @param cls ignored
722  * @param id the peer
723  * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
724  * default preferences if peer does not exist
725  */
726 const double *
727 GAS_normalization_get_preferences_by_peer (void *cls,
728                                            const struct GNUNET_PeerIdentity *id)
729 {
730   struct PeerRelative *rp;
731
732   if (NULL ==
733       (rp = GNUNET_CONTAINER_multipeermap_get (preference_peers,
734                                                id)))
735   {
736     return defvalues.f_rel;
737   }
738   return rp->f_rel;
739 }
740
741
742 /**
743  * A performance client disconnected
744  *
745  * @param client the client
746  */
747 void
748 GAS_normalization_preference_client_disconnect (struct GNUNET_SERVER_Client *client)
749 {
750   struct PreferenceClient *c_cur;
751   /* Find preference client */
752
753   for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
754   {
755     if (client == c_cur->client)
756       break;
757   }
758   if (NULL == c_cur)
759     return;
760
761   GNUNET_CONTAINER_DLL_remove(pc_head, pc_tail, c_cur);
762   free_client (c_cur);
763 }