src/ats/gnunet-service-ats_normalization.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2011 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 /**
  22  * @file ats/gnunet-service-ats_normalization.c
  23  * @brief ats service address: management of ATS properties and preferences normalization
  24  * @author Matthias Wachs
  25  * @author Christian Grothoff
  26  */
  27 #include "platform.h"
  28 #include "gnunet_ats_service.h"
  29 #include "gnunet-service-ats_normalization.h"
  30
  31
  32
  33 /**
  34  * Preference client
  35  */
  36 struct PreferenceClient
  37 {
  38   /**
  39    * Next in DLL
  40    */
  41   struct PreferenceClient *prev;
  42
  43   /**
  44    * Next in DLL
  45    */
  46
  47   struct PreferenceClient *next;
  48
  49   /**
  50    * Client handle
  51    */
  52   void *client;
  53
  54   /**
  55    * Total preference for this peer
  56    */
  57   double f_abs_sum[GNUNET_ATS_PreferenceCount];
  58
  59   /**
  60    * List of peer preferences for this client
  61    */
  62
  63   /**
  64    * Head of peer list
  65    */
  66   struct PreferencePeer *p_head;
  67
  68   /**
  69    * Tail of peer list
  70    */
  71   struct PreferencePeer *p_tail;
  72 };
  73
  74
  75 /**
  76  * Preference peer
  77  */
  78 struct PreferencePeer
  79 {
  80   /**
  81    * Next in DLL
  82    */
  83   struct PreferencePeer *next;
  84
  85   /**
  86    * Previous in DLL
  87    */
  88   struct PreferencePeer *prev;
  89
  90   /**
  91    * Client
  92    */
  93   struct PreferenceClient *client;
  94
  95   /**
  96    * Peer id
  97    */
  98   struct GNUNET_PeerIdentity id;
  99
 100   /**
 101    * Absolute preference values
 102    */
 103   double f_abs[GNUNET_ATS_PreferenceCount];
 104
 105   /**
 106    * Relative preference values
 107    */
 108   double f_rel[GNUNET_ATS_PreferenceCount];
 109
 110   /**
 111    * Aging Task
 112    */
 113   GNUNET_SCHEDULER_TaskIdentifier aging_task;
 114 };
 115
 116 /**
 117  * Relative preferences for a peer
 118  */
 119 struct PeerRelative
 120 {
 121   /**
 122    * Relative preference values
 123    */
 124   double f_rel[GNUNET_ATS_PreferenceCount];
 125
 126   /**
 127    * Peer id
 128    */
 129   struct GNUNET_PeerIdentity id;
 130 };
 131
 132
 133 /**
 134  * Callback to call on changing preference values
 135  */
 136 static GAS_Normalization_preference_changed_cb pref_changed_cb;
 137
 138
 139 /**
 140  * Closure for callback to call on changing preference values
 141  */
 142 static void *pref_changed_cb_cls;
 143
 144
 145 /**
 146  * Hashmap to store peer information
 147  */
 148 static struct GNUNET_CONTAINER_MultiHashMap *peers;
 149
 150
 151 /**
 152  * Clients in DLL: head
 153  */
 154 static struct PreferenceClient *pc_head;
 155
 156
 157 /**
 158  * Clients in DLL: tail
 159  */
 160 static struct PreferenceClient *pc_tail;
 161
 162
 163 /**
 164  * Default values
 165  */
 166 static struct PeerRelative defvalues;
 167
 168
 169 /**
 170  * Update a peer
 171  * @param id peer id
 172  * @pram kind the kind
 173  */
 174 static double
 175 update_peers (struct GNUNET_PeerIdentity *id,
 176                                                         enum GNUNET_ATS_PreferenceKind kind)
 177 {
 178         struct PreferenceClient *c_cur;
 179         struct PreferencePeer *p_cur;
 180         struct PeerRelative *rp;
 181         double f_rel_total;
 182         double backup;
 183         unsigned int count;
 184
 185         f_rel_total = 0.0;
 186         count = 0;
 187
 188         /* For all clients */
 189         for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
 190         {
 191                 /* Find peer with id */
 192                 for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
 193                 {
 194                         if (0 == memcmp (id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity)))
 195                                 break;
 196                 }
 197                 if (NULL != p_cur)
 198                 {
 199                         /* Found peer with id */
 200                         f_rel_total +=  p_cur->f_rel[kind];
 201                         count ++;
 202                 }
 203         }
 204
 205         /* Find a client */
 206         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 207                         "%u clients have a total relative preference for peer `%s''s `%s' of %.3f\n",
 208                         count,
 209                         GNUNET_i2s (id),
 210                         GNUNET_ATS_print_preference_type (kind),
 211                         f_rel_total);
 212         if (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey)))
 213         {
 214                 backup = rp->f_rel[kind];
 215                 if (0 < count)
 216                 {
 217                         rp->f_rel[kind] = f_rel_total / count;
 218                 }
 219                 else
 220                 {
 221                         rp->f_rel[kind] = DEFAULT_REL_PREFERENCE;
 222                 }
 223         }
 224         else
 225         {
 226                 return DEFAULT_REL_PREFERENCE;
 227         }
 228
 229         if ((backup != rp->f_rel[kind]) && (NULL != pref_changed_cb))
 230         {
 231                 pref_changed_cb (pref_changed_cb_cls, &rp->id, kind, rp->f_rel[kind]);
 232         }
 233
 234         return rp->f_rel[kind];
 235 }
 236
 237
 238 /**
 239  * Recalculate preference for a specific ATS property
 240  *
 241  * @param c the preference client
 242  * @param p the peer
 243  * @param kind the preference kind
 244  * @return the result
 245  */
 246 static double
 247 recalculate_rel_preferences (struct PreferenceClient *c,
 248                                                          struct PreferencePeer *p,
 249                                                          enum GNUNET_ATS_PreferenceKind kind)
 250 {
 251         struct PreferencePeer *p_cur;
 252         struct PeerRelative *rp;
 253         double backup;
 254         double res;
 255         double ret;
 256
 257         /* For this client: sum preferences to total preference */
 258         c->f_abs_sum[kind] = 0;
 259         for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
 260                 c->f_abs_sum[kind] += p_cur->f_abs[kind];
 261         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 262                         "Client %p has total preference for %s of %.3f\n",
 263                         c->client,
 264                         GNUNET_ATS_print_preference_type (kind),
 265                         c->f_abs_sum[kind]);
 266
 267         ret = DEFAULT_REL_PREFERENCE;
 268         /* For all peers: calculate relative preference */
 269         for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
 270         {
 271                 /* Calculate relative preference for specific kind */
 272                 backup = p_cur->f_rel[kind];
 273                 if (DEFAULT_ABS_PREFERENCE == c->f_abs_sum[kind])
 274                                 /* No peer has a preference for this property,
 275                                  * so set default preference */
 276                                 p_cur->f_rel[kind] = DEFAULT_REL_PREFERENCE;
 277                 else
 278                                 p_cur->f_rel[kind] = (c->f_abs_sum[kind] + p_cur->f_abs[kind]) /
 279                                 c->f_abs_sum[kind];
 280
 281                 GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 282                                 "Client %p: peer `%s' has relative preference for %s of %.3f\n",
 283                                 c->client,
 284                                 GNUNET_i2s (&p_cur->id),
 285                                 GNUNET_ATS_print_preference_type (kind),
 286                                 p_cur->f_rel[kind]);
 287
 288                 res = 0.0;
 289                 if (p_cur->f_rel[kind] != backup)
 290                 {
 291                         /* Value changed, recalculate */
 292                         res = update_peers (&p_cur->id,kind);
 293                         if (0 == memcmp (&p->id, &p_cur->id, sizeof (struct GNUNET_PeerIdentity)))
 294                                 ret = res;
 295                 }
 296                 else
 297           {
 298                         /* Value did not chang, return old value*/
 299                         GNUNET_assert (NULL != (rp = GNUNET_CONTAINER_multihashmap_get (peers,
 300                                         &p->id.hashPubKey)));
 301                         ret = rp->f_rel[kind];
 302           }
 303         }
 304         return ret;
 305 }
 306
 307
 308 /**
 309  * Update the absolute preference value for a peer
 310  * @param id peer id
 311  * @param kind the kind
 312  * @return the new relative preference value
 313  */
 314 static double
 315 update_preference (struct PreferenceClient *c,
 316                                                                          struct PreferencePeer *p,
 317                                                                          enum GNUNET_ATS_PreferenceKind kind,
 318                                                          float score_abs)
 319 {
 320         double score = score_abs;
 321
 322   /* Update preference value according to type */
 323   switch (kind) {
 324     case GNUNET_ATS_PREFERENCE_BANDWIDTH:
 325     case GNUNET_ATS_PREFERENCE_LATENCY:
 326       p->f_abs[kind] = (p->f_abs[kind] + score) / 2;
 327       break;
 328     case GNUNET_ATS_PREFERENCE_END:
 329       break;
 330     default:
 331       break;
 332   }
 333   return recalculate_rel_preferences (c, p, kind);
 334 }
 335
 336
 337 /**
 338  * Reduce absolute preferences since they got old
 339  *
 340  * @param cls the PreferencePeer
 341  * @param tc context
 342  */
 343 static void
 344 preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 345 {
 346         int i;
 347         double backup;
 348         struct PreferencePeer *p = cls;
 349         GNUNET_assert (NULL != p);
 350
 351         p->aging_task = GNUNET_SCHEDULER_NO_TASK;
 352
 353         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aging preferences for peer `%s'\n",
 354                 GNUNET_i2s (&p->id));
 355
 356   /* Aging absolute values: */
 357   for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 358   {
 359                         backup = p->f_abs[i];
 360                 if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
 361                         p->f_abs[i] *= PREF_AGING_FACTOR;
 362                 if (backup != p->f_abs[i])
 363                 {
 364                         GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, "Aged preference for peer `%s' from %.3f to %.3f\n",
 365                         GNUNET_i2s (&p->id), backup, p->f_abs[i]);
 366                         recalculate_rel_preferences (p->client, p, i);
 367                 }
 368   }
 369   p->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
 370                 &preference_aging, p);
 371 }
 372
 373
 374 /**
 375  * Normalize an updated preference value
 376  *
 377  * @param src the client with this preference
 378  * @param peer the peer to change the preference for
 379  * @param kind the kind to change the preference
 380  * @param score_abs the normalized score
 381  */
 382 float
 383 GAS_normalization_change_preference (void *src,
 384                                          const struct GNUNET_PeerIdentity *peer,
 385                                          enum GNUNET_ATS_PreferenceKind kind,
 386                                          float score_abs)
 387 {
 388   float score_rel;
 389   struct PreferenceClient *c_cur;
 390   struct PreferencePeer *p_cur;
 391   struct PeerRelative *r_cur;
 392   int i;
 393
 394
 395   GNUNET_assert (NULL != src);
 396   GNUNET_assert (NULL != peer);
 397
 398   GNUNET_log (GNUNET_ERROR_TYPE_DEBUG,
 399                 "Client %p changes preference for peer `%s' for `%s' to %.2f\n",
 400                         src,
 401                         GNUNET_i2s (peer),
 402                         GNUNET_ATS_print_preference_type (kind),
 403                         score_abs);
 404
 405   if (kind >= GNUNET_ATS_PreferenceCount)
 406   {
 407       GNUNET_break (0);
 408       return 0.0;
 409   }
 410
 411   /* Find preference client */
 412   for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
 413   {
 414       if (src == c_cur->client)
 415         break;
 416   }
 417   /* Not found: create new preference client */
 418   if (NULL == c_cur)
 419   {
 420     c_cur = GNUNET_malloc (sizeof (struct PreferenceClient));
 421     c_cur->client = src;
 422     GNUNET_CONTAINER_DLL_insert (pc_head, pc_tail, c_cur);
 423   }
 424
 425   /* Find entry for peer */
 426   for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
 427     if (0 == memcmp (&p_cur->id, peer, sizeof (p_cur->id)))
 428         break;
 429
 430   /* Not found: create new peer entry */
 431   if (NULL == p_cur)
 432   {
 433       p_cur = GNUNET_malloc (sizeof (struct PreferencePeer));
 434       p_cur->client = c_cur;
 435       p_cur->id = (*peer);
 436       for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 437       {
 438         /* Default value per peer absolut preference for a quality:
 439          * No value set, so absolute preference 0 */
 440         p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
 441         /* Default value per peer relative preference for a quality: 1.0 */
 442         p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
 443       }
 444       p_cur->aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
 445                 &preference_aging, p_cur);
 446       GNUNET_CONTAINER_DLL_insert (c_cur->p_head, c_cur->p_tail, p_cur);
 447   }
 448
 449   if (NULL == (r_cur = GNUNET_CONTAINER_multihashmap_get (peers,
 450                 &peer->hashPubKey)))
 451   {
 452         r_cur = GNUNET_malloc (sizeof (struct PeerRelative));
 453         r_cur->id = (*peer);
 454         for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 455                 r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
 456         GNUNET_CONTAINER_multihashmap_put (peers, &r_cur->id.hashPubKey,
 457                         r_cur, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
 458   }
 459
 460   score_rel = update_preference (c_cur, p_cur, kind, score_abs);
 461   return score_rel;
 462 }
 463
 464
 465 /**
 466  * Get the normalized preference values for a specific peer or
 467  * the default values if
 468  *
 469  * @param id the peer
 470  * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
 471  * default preferences if peer does not exist
 472  */
 473 const double *
 474 GAS_normalization_get_preferences (const struct GNUNET_PeerIdentity *id)
 475 {
 476         GNUNET_assert (NULL != peers);
 477         GNUNET_assert (NULL != id);
 478
 479         struct PeerRelative *rp;
 480         if (NULL == (rp = GNUNET_CONTAINER_multihashmap_get (peers, &id->hashPubKey)))
 481         {
 482                 return defvalues.f_rel;
 483         }
 484         return rp->f_rel;
 485 }
 486
 487
 488 /**
 489  * Start the normalization component
 490  *
 491  * @param pref_ch_cb callback to call on relative preference changing
 492  * @param ref_ch_cb_cls cls for the callback
 493  */
 494 void
 495 GAS_normalization_start (GAS_Normalization_preference_changed_cb pref_ch_cb,
 496                 void *pref_ch_cb_cls)
 497 {
 498         int i;
 499         peers = GNUNET_CONTAINER_multihashmap_create(10, GNUNET_NO);
 500         pref_changed_cb = pref_ch_cb;
 501         pref_changed_cb_cls = pref_ch_cb_cls;
 502         for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 503                 defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
 504         return;
 505 }
 506
 507
 508 /**
 509  * Free a peer
 510  *
 511  * @param cls unused
 512  * @param key the key
 513  * @param value RelativePeer
 514  * @return GNUNET_OK to continue
 515  */
 516 static int
 517 free_peer (void *cls,
 518                          const struct GNUNET_HashCode * key,
 519                          void *value)
 520 {
 521         struct PeerRelative *rp = value;
 522         GNUNET_CONTAINER_multihashmap_remove (peers, key, value);
 523         GNUNET_free (rp);
 524         return GNUNET_OK;
 525 }
 526
 527
 528 /**
 529  * Stop the normalization component and free all items
 530  */
 531 void
 532 GAS_normalization_stop ()
 533 {
 534   struct PreferenceClient *pc;
 535   struct PreferenceClient *next_pc;
 536   struct PreferencePeer *p;
 537   struct PreferencePeer *next_p;
 538
 539   next_pc = pc_head;
 540   while (NULL != (pc = next_pc))
 541   {
 542       next_pc = pc->next;
 543       GNUNET_CONTAINER_DLL_remove (pc_head, pc_tail, pc);
 544       next_p = pc->p_head;
 545       while (NULL != (p = next_p))
 546       {
 547           next_p = p->next;
 548           if (GNUNET_SCHEDULER_NO_TASK != p->aging_task)
 549           {
 550                 GNUNET_SCHEDULER_cancel(p->aging_task);
 551                 p->aging_task = GNUNET_SCHEDULER_NO_TASK;
 552           }
 553           GNUNET_CONTAINER_DLL_remove (pc->p_head, pc->p_tail, p);
 554           GNUNET_free (p);
 555       }
 556       GNUNET_free (pc);
 557   }
 558   GNUNET_CONTAINER_multihashmap_iterate (peers, &free_peer, NULL);
 559   GNUNET_CONTAINER_multihashmap_destroy (peers);
 560         return;
 561 }
 562
 563 /* end of gnunet-service-ats_normalization.c */