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_addresses.h"
  30 #include "gnunet-service-ats_normalization.h"
  31
  32 #define LOG(kind,...) GNUNET_log_from (kind, "ats-normalization",__VA_ARGS__)
  33
  34 /**
  35  * Preference client
  36  */
  37 struct PreferenceClient
  38 {
  39   /**
  40    * Next in DLL
  41    */
  42   struct PreferenceClient *prev;
  43
  44   /**
  45    * Next in DLL
  46    */
  47
  48   struct PreferenceClient *next;
  49
  50   /**
  51    * Client handle
  52    */
  53   void *client;
  54
  55   /**
  56    * Array of sum of absolute preferences for this client
  57    */
  58   double f_abs_sum[GNUNET_ATS_PreferenceCount];
  59
  60   /**
  61    * Array of sum of relative preferences for this client
  62    */
  63   double f_rel_sum[GNUNET_ATS_PreferenceCount];
  64
  65   /**
  66    * List of peer preferences for this client
  67    */
  68
  69   /**
  70    * Head of peer list
  71    */
  72   struct PreferencePeer *p_head;
  73
  74   /**
  75    * Tail of peer list
  76    */
  77   struct PreferencePeer *p_tail;
  78 };
  79
  80 /**
  81  * Preference peer
  82  */
  83 struct PreferencePeer
  84 {
  85   /**
  86    * Next in DLL
  87    */
  88   struct PreferencePeer *next;
  89
  90   /**
  91    * Previous in DLL
  92    */
  93   struct PreferencePeer *prev;
  94
  95   /**
  96    * Client
  97    */
  98   struct PreferenceClient *client;
  99
 100   /**
 101    * Peer id
 102    */
 103   struct GNUNET_PeerIdentity id;
 104
 105   /**
 106    * Absolute preference values for all preference types
 107    */
 108   double f_abs[GNUNET_ATS_PreferenceCount];
 109
 110   /**
 111    * Relative preference values for all preference types
 112    */
 113   double f_rel[GNUNET_ATS_PreferenceCount];
 114
 115   /**
 116    * Absolute point of time of next aging process
 117    */
 118   struct GNUNET_TIME_Absolute next_aging[GNUNET_ATS_PreferenceCount];
 119 };
 120
 121 /**
 122  * Relative preferences for a peer
 123  */
 124 struct PeerRelative
 125 {
 126   /**
 127    * Relative preference values
 128    */
 129   double f_rel[GNUNET_ATS_PreferenceCount];
 130
 131   /**
 132    * Peer id
 133    */
 134   struct GNUNET_PeerIdentity id;
 135 };
 136
 137 /**
 138  * Quality Normalization
 139  */
 140 struct Property
 141 {
 142   uint32_t prop_type;
 143   uint32_t atsi_type;
 144   uint32_t min;
 145   uint32_t max;
 146 };
 147
 148 struct Property properties[GNUNET_ATS_QualityPropertiesCount];
 149
 150
 151 /**
 152  * Callback to call on changing preference values
 153  */
 154 static GAS_Normalization_preference_changed_cb pref_changed_cb;
 155
 156 /**
 157  * Closure for callback to call on changing preference values
 158  */
 159 static void *pref_changed_cb_cls;
 160
 161 /**
 162  * Callback to call on changing property values
 163  */
 164 GAS_Normalization_property_changed_cb prop_ch_cb;
 165
 166 /**
 167  * Closure for callback to call on changing property values
 168  */
 169 void *prop_ch_cb_cls;
 170
 171 /**
 172  * Hashmap to store peer information for preference normalization
 173  */
 174 static struct GNUNET_CONTAINER_MultiPeerMap *preference_peers;
 175
 176 /**
 177  * Hashmap to store peer information for property normalization
 178  * FIXME: this map is not used!
 179  */
 180 static struct GNUNET_CONTAINER_MultiPeerMap *property_peers;
 181
 182 /**
 183  * Clients in DLL: head
 184  */
 185 static struct PreferenceClient *pc_head;
 186
 187 /**
 188  * Clients in DLL: tail
 189  */
 190 static struct PreferenceClient *pc_tail;
 191
 192 /**
 193  * Default values
 194  */
 195 static struct PeerRelative defvalues;
 196
 197 static GNUNET_SCHEDULER_TaskIdentifier aging_task;
 198
 199 /**
 200  * Application Preference Normalization
 201  */
 202
 203 /**
 204  * Update a peer
 205  *
 206  * @param id peer id
 207  * @param kind the kind
 208  * @param rp the relative peer struct
 209  * @return the new relative preference
 210  */
 211 static void
 212 update_relative_values_for_peer (const struct GNUNET_PeerIdentity *id,
 213     enum GNUNET_ATS_PreferenceKind kind, struct PeerRelative *rp)
 214 {
 215   struct PreferenceClient *c_cur;
 216   struct PreferencePeer *p_cur;
 217   double f_rel_total;
 218   double f_rel_sum;
 219   double backup;
 220   unsigned int peer_count;
 221
 222   f_rel_sum = 0.0;
 223   f_rel_total = 0.0;
 224   peer_count = 0;
 225
 226   /* For all clients */
 227   for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
 228   {
 229     /* For peer entries with this id */
 230     for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
 231     {
 232       f_rel_sum += p_cur->f_rel[kind];
 233       if (0 == memcmp (id, &p_cur->id, sizeof(struct GNUNET_PeerIdentity)))
 234       {
 235         peer_count ++;
 236         f_rel_total += p_cur->f_rel[kind];
 237       }
 238
 239     }
 240   }
 241
 242   LOG (GNUNET_ERROR_TYPE_DEBUG,
 243       "%u clients have a total relative preference for peer `%s' `%s' of %.3f and for %s in total %.3f\n",
 244       peer_count, GNUNET_i2s (id),
 245       GNUNET_ATS_print_preference_type (kind),
 246       f_rel_total,
 247       GNUNET_ATS_print_preference_type (kind),
 248       f_rel_sum);
 249
 250   /* Find entry for the peer containing relative values in the hashmap */
 251   if (NULL != rp)
 252   {
 253     backup = rp->f_rel[kind];
 254     if (f_rel_sum > 0)
 255       rp->f_rel[kind] = f_rel_total / f_rel_sum;
 256     else
 257     {
 258       /* No client had any preferences for this type and any peer */
 259       rp->f_rel[kind] = DEFAULT_REL_PREFERENCE;
 260     }
 261     if ((backup != rp->f_rel[kind]) && (NULL != pref_changed_cb))
 262     {
 263       pref_changed_cb (pref_changed_cb_cls, &rp->id, kind, rp->f_rel[kind]);
 264     }
 265   }
 266 }
 267
 268 /**
 269  * Recalculate preference for a specific ATS property
 270  *
 271  * @param c the preference client
 272  * @param kind the preference kind
 273  * @return the result
 274  */
 275 static void
 276 recalculate_relative_preferences (struct PreferenceClient *c, enum GNUNET_ATS_PreferenceKind kind)
 277 {
 278   struct PreferencePeer *p_cur;
 279
 280   /* For this client: sum of absolute preference values for this preference */
 281   c->f_abs_sum[kind] = 0.0;
 282   /* For this client: sum of relative preference values for this preference
 283    *
 284    * Note: this value should also be 1.0, but:
 285    * if no preferences exist due to aging, this value can be 0.0
 286    * and the client can be removed */
 287   c->f_rel_sum[kind] = 0.0;
 288
 289   for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
 290     c->f_abs_sum[kind] += p_cur->f_abs[kind];
 291   LOG (GNUNET_ERROR_TYPE_DEBUG,
 292       "Client %p has sum of total preferences for %s of %.3f\n",
 293       c->client, GNUNET_ATS_print_preference_type (kind), c->f_abs_sum[kind]);
 294
 295   /* For all peers: calculate relative preference */
 296   for (p_cur = c->p_head; NULL != p_cur; p_cur = p_cur->next)
 297   {
 298     /* Calculate relative preference for specific kind */
 299
 300     /* Every application has a preference for each peer between
 301      * [0 .. 1] in relative values
 302      * and [0 .. inf] in absolute values */
 303     p_cur->f_rel[kind] =  p_cur->f_abs[kind] / c->f_abs_sum[kind];
 304     c->f_rel_sum[kind] += p_cur->f_rel[kind];
 305
 306     LOG (GNUNET_ERROR_TYPE_DEBUG,
 307         "Client %p has relative preference for %s for peer `%s' of %.3f\n",
 308         c->client,
 309         GNUNET_ATS_print_preference_type (kind),
 310         GNUNET_i2s (&p_cur->id),
 311         p_cur->f_rel[kind]);
 312   }
 313
 314 }
 315
 316 /**
 317  * Update the absolute preference value for a peer
 318  * @param c the client
 319  * @param p the peer
 320  * @param kind the preference kind
 321  * @param score_abs the absolute value
 322  * @return the new relative preference value
 323  */
 324 static void
 325 update_abs_preference (struct PreferenceClient *c, struct PreferencePeer *p,
 326     enum GNUNET_ATS_PreferenceKind kind, float score_abs)
 327 {
 328   double score = score_abs;
 329
 330   /* Update preference value according to type */
 331   switch (kind)
 332   {
 333   case GNUNET_ATS_PREFERENCE_BANDWIDTH:
 334   case GNUNET_ATS_PREFERENCE_LATENCY:
 335     p->f_abs[kind] = score;
 336     /* p->f_abs[kind] = (p->f_abs[kind] + score) / 2;  */
 337     p->next_aging[kind] = GNUNET_TIME_absolute_add (GNUNET_TIME_absolute_get (),
 338         PREF_AGING_INTERVAL);
 339     break;
 340   case GNUNET_ATS_PREFERENCE_END:
 341     break;
 342   default:
 343     break;
 344   }
 345 }
 346
 347 static int update_iterator (void *cls,
 348                            const struct GNUNET_PeerIdentity *key,
 349                            void *value)
 350 {
 351   enum GNUNET_ATS_PreferenceKind *kind = cls;
 352   update_relative_values_for_peer (key, (*kind), (struct PeerRelative *) value);
 353   return GNUNET_OK;
 354 }
 355
 356 static void
 357 run_preference_update (struct PreferenceClient *c_cur,
 358     struct PreferencePeer *p_cur,enum GNUNET_ATS_PreferenceKind kind,
 359     float score_abs)
 360 {
 361   double old_value;
 362
 363   /* Update relative value */
 364   old_value = p_cur->f_rel[kind];
 365   recalculate_relative_preferences (c_cur, kind);
 366   if (p_cur->f_rel[kind] == old_value)
 367     return;
 368
 369   /* Relative preference value changed, recalculate for all peers */
 370   GNUNET_CONTAINER_multipeermap_iterate (preference_peers, &update_iterator, &kind);
 371 }
 372
 373 /**
 374  * Reduce absolute preferences since they got old
 375  *
 376  * @param cls the PreferencePeer
 377  * @param tc context
 378  */
 379 static void
 380 preference_aging (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc)
 381 {
 382   struct PreferencePeer *p;
 383   struct PreferenceClient *cur_client;
 384   int i;
 385   int values_to_update;
 386   double backup;
 387
 388   aging_task = GNUNET_SCHEDULER_NO_TASK;
 389   values_to_update = 0;
 390   cur_client = NULL;
 391
 392   for (cur_client = pc_head; NULL != cur_client; cur_client = cur_client->next)
 393   {
 394     for (p = cur_client->p_head; NULL != p; p = p->next)
 395     {
 396       /* Aging absolute values: */
 397       for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 398       {
 399         if (0
 400             == GNUNET_TIME_absolute_get_remaining (p->next_aging[i]).rel_value_us)
 401         {
 402           GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 403               "Aging preference for peer `%s'\n", GNUNET_i2s (&p->id));
 404           backup = p->f_abs[i];
 405           if (p->f_abs[i] > DEFAULT_ABS_PREFERENCE)
 406             p->f_abs[i] *= PREF_AGING_FACTOR;
 407
 408           if (p->f_abs[i] <= DEFAULT_ABS_PREFERENCE + PREF_EPSILON)
 409             p->f_abs[i] = DEFAULT_ABS_PREFERENCE;
 410
 411           if ( (p->f_abs[i] != DEFAULT_ABS_PREFERENCE) &&
 412                (backup != p->f_abs[i]) )
 413           {
 414             GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 415                 "Aged preference for peer `%s' from %.3f to %.3f\n",
 416                 GNUNET_i2s (&p->id), backup, p->f_abs[i]);
 417
 418             run_preference_update(cur_client, p, i, p->f_abs[i]);
 419
 420             p->next_aging[i] = GNUNET_TIME_absolute_add (
 421                 GNUNET_TIME_absolute_get (), PREF_AGING_INTERVAL);
 422             values_to_update++;
 423           }
 424         }
 425       }
 426     }
 427   }
 428
 429   if (values_to_update > 0)
 430   {
 431     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 432         "Rescheduling aging task due to %u elements to age\n",
 433         values_to_update);
 434     aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
 435         &preference_aging, NULL );
 436   }
 437   else
 438     GNUNET_log(GNUNET_ERROR_TYPE_DEBUG,
 439         "No values to age left, not rescheduling aging task\n");
 440
 441 }
 442
 443 /**
 444  * Normalize an updated preference value
 445  *
 446  * @param client the client with this preference
 447  * @param peer the peer to change the preference for
 448  * @param kind the kind to change the preference
 449  * @param score_abs the normalized score
 450  */
 451 void
 452 GAS_normalization_normalize_preference (void *client,
 453     const struct GNUNET_PeerIdentity *peer,
 454     enum GNUNET_ATS_PreferenceKind kind,
 455     float score_abs)
 456 {
 457   struct PreferenceClient *c_cur;
 458   struct PreferencePeer *p_cur;
 459   struct PeerRelative *r_cur;
 460   double old_value;
 461   int i;
 462
 463   GNUNET_assert(NULL != client);
 464   GNUNET_assert(NULL != peer);
 465
 466   LOG (GNUNET_ERROR_TYPE_DEBUG,
 467       "Client %p changes preference for peer `%s' for `%s' to %.2f\n",
 468       client,
 469       GNUNET_i2s (peer),
 470       GNUNET_ATS_print_preference_type (kind),
 471       score_abs);
 472
 473   if (kind >= GNUNET_ATS_PreferenceCount)
 474   {
 475     GNUNET_break(0);
 476     return;
 477   }
 478
 479   /* Find preference client */
 480   for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
 481   {
 482     if (client == c_cur->client)
 483       break;
 484   }
 485   /* Not found: create new preference client */
 486   if (NULL == c_cur)
 487   {
 488     c_cur = GNUNET_new (struct PreferenceClient);
 489     c_cur->client = client;
 490     for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 491     {
 492       c_cur->f_abs_sum[i] = DEFAULT_ABS_PREFERENCE;
 493       c_cur->f_rel_sum[i] = DEFAULT_REL_PREFERENCE;
 494     }
 495
 496     GNUNET_CONTAINER_DLL_insert(pc_head, pc_tail, c_cur);
 497     LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding new client %p \n", c_cur);
 498   }
 499
 500   /* Find entry for peer */
 501   for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
 502     if (0 == memcmp (&p_cur->id, peer, sizeof(p_cur->id)))
 503       break;
 504
 505   /* Not found: create new peer entry */
 506   if (NULL == p_cur)
 507   {
 508     p_cur = GNUNET_new (struct PreferencePeer);
 509     p_cur->client = c_cur;
 510     p_cur->id = (*peer);
 511     for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 512     {
 513       /* Default value per peer absolute preference for a preference: 0 */
 514       p_cur->f_abs[i] = DEFAULT_ABS_PREFERENCE;
 515       /* Default value per peer relative preference for a quality: 1.0 */
 516       p_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
 517       p_cur->next_aging[i] = GNUNET_TIME_UNIT_FOREVER_ABS;
 518     }
 519     LOG (GNUNET_ERROR_TYPE_DEBUG, "Adding new peer %p for client %p \n",
 520         p_cur, c_cur);
 521     GNUNET_CONTAINER_DLL_insert(c_cur->p_head, c_cur->p_tail, p_cur);
 522   }
 523
 524   /* Create struct for peer */
 525   if (NULL == GNUNET_CONTAINER_multipeermap_get (preference_peers, peer))
 526   {
 527     r_cur = GNUNET_new (struct PeerRelative);
 528     r_cur->id = (*peer);
 529     for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 530       r_cur->f_rel[i] = DEFAULT_REL_PREFERENCE;
 531     GNUNET_assert(
 532         GNUNET_OK == GNUNET_CONTAINER_multipeermap_put (preference_peers,
 533             &r_cur->id, r_cur, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
 534   }
 535
 536   /* Update absolute value */
 537   old_value = p_cur->f_abs[kind];
 538   update_abs_preference (c_cur, p_cur, kind, score_abs);
 539   if (p_cur->f_abs[kind] == old_value)
 540     return;
 541
 542   run_preference_update (c_cur, p_cur, kind, score_abs);
 543
 544   /* Start aging task */
 545   if (GNUNET_SCHEDULER_NO_TASK == aging_task)
 546     aging_task = GNUNET_SCHEDULER_add_delayed (PREF_AGING_INTERVAL,
 547         &preference_aging, NULL );
 548
 549 }
 550
 551 /**
 552  * Get the normalized preference values for a specific peer or
 553  * the default values if
 554  *
 555  * @param id the peer
 556  * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
 557  * default preferences if peer does not exist
 558  */
 559 const double *
 560 GAS_normalization_get_preferences_by_peer (const struct GNUNET_PeerIdentity *id)
 561 {
 562   GNUNET_assert(NULL != preference_peers);
 563   GNUNET_assert(NULL != id);
 564
 565   struct PeerRelative *rp;
 566   if (NULL == (rp = GNUNET_CONTAINER_multipeermap_get (preference_peers, id)))
 567   {
 568     return defvalues.f_rel;
 569   }
 570   return rp->f_rel;
 571 }
 572
 573 /**
 574  * Get the normalized preference values for a specific client and peer
 575  *
 576  * @param client client
 577  * @param peer the peer
 578  * @param pref the preference type
 579  * @return the value
 580  */
 581 double
 582 GAS_normalization_get_preferences_by_client (const void *client,
 583                                              const struct GNUNET_PeerIdentity *peer,
 584                                              enum GNUNET_ATS_PreferenceKind pref)
 585 {
 586   struct PreferenceClient *c_cur;
 587   struct PreferencePeer *p_cur;
 588
 589   /* Find preference client */
 590   for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
 591   {
 592     if (client == c_cur->client)
 593       break;
 594   }
 595   if (NULL == c_cur)
 596     return -1.0;
 597
 598   for (p_cur = c_cur->p_head; NULL != p_cur; p_cur = p_cur->next)
 599   {
 600     if (0 == memcmp (peer, &p_cur->id, sizeof (struct GNUNET_PeerIdentity)))
 601       break;
 602   }
 603   if (NULL == p_cur)
 604     return DEFAULT_REL_PREFERENCE; /* Not found, return default */
 605
 606   return p_cur->f_rel[pref];
 607 }
 608
 609 /**
 610  * Get the normalized properties values for a specific peer or
 611  * the default values if
 612  *
 613  * @param address the address
 614  * @return pointer to the values, can be indexed with GNUNET_ATS_PreferenceKind,
 615  * default preferences if peer does not exist
 616  */
 617 const double *
 618 GAS_normalization_get_properties (struct ATS_Address *address)
 619 {
 620   static double norm_values[GNUNET_ATS_QualityPropertiesCount];
 621   int i;
 622
 623   GNUNET_assert(NULL != address);
 624
 625   for (i = 0; i < GNUNET_ATS_QualityPropertiesCount; i++)
 626   {
 627     if ((address->atsin[i].norm >= 1.0) && (address->atsin[i].norm <= 2.0))
 628       norm_values[i] = address->atsin[i].norm;
 629     else
 630       norm_values[i] = DEFAULT_REL_QUALITY;
 631   }
 632   return norm_values;
 633 }
 634
 635 /**
 636  * Normalize a specific ATS type with the values in queue
 637  * @param address the address
 638  * @param atsi the ats information
 639  * @return the new average or GNUNET_ATS_VALUE_UNDEFINED
 640  */
 641
 642 uint32_t
 643 property_average (struct ATS_Address *address,
 644     const struct GNUNET_ATS_Information *atsi)
 645 {
 646   struct GAS_NormalizationInfo *ni;
 647   uint32_t current_type;
 648   uint32_t current_val;
 649   uint32_t res;
 650   uint64_t sum;
 651   uint32_t count;
 652   unsigned int c1;
 653   unsigned int index;
 654   unsigned int props[] = GNUNET_ATS_QualityProperties;
 655
 656   /* Average the values of this property */
 657   current_type = ntohl (atsi->type);
 658   current_val = ntohl (atsi->value);
 659
 660   for (c1 = 0; c1 < GNUNET_ATS_QualityPropertiesCount; c1++)
 661   {
 662     if (current_type == props[c1])
 663       break;
 664   }
 665   if (c1 == GNUNET_ATS_QualityPropertiesCount)
 666   {
 667     GNUNET_break(0);
 668     return GNUNET_ATS_VALUE_UNDEFINED;
 669   }
 670   index = c1;
 671
 672   ni = &address->atsin[index];
 673   ni->atsi_abs[ni->avg_queue_index] = current_val;
 674   ni->avg_queue_index++;
 675   if (GAS_normalization_queue_length == ni->avg_queue_index)
 676     ni->avg_queue_index = 0;
 677
 678   count = 0;
 679   sum = 0;
 680   for (c1 = 0; c1 < GAS_normalization_queue_length; c1++)
 681   {
 682     if (GNUNET_ATS_VALUE_UNDEFINED != ni->atsi_abs[c1])
 683     {
 684       count++;
 685       if (GNUNET_ATS_VALUE_UNDEFINED > (sum + ni->atsi_abs[c1]))
 686         sum += ni->atsi_abs[c1];
 687       else
 688       {
 689         sum = GNUNET_ATS_VALUE_UNDEFINED - 1;
 690         GNUNET_break(0);
 691       }
 692     }
 693   }
 694   GNUNET_assert(0 != count);
 695   res = sum / count;
 696   LOG(GNUNET_ERROR_TYPE_DEBUG,
 697       "New average of `%s' created by adding %u from %u elements: %u\n",
 698       GNUNET_ATS_print_property_type (current_type), current_val, count, res,
 699       sum);
 700   ni->avg = res;
 701   return res;
 702 }
 703
 704 struct FindMinMaxCtx
 705 {
 706   struct Property *p;
 707   uint32_t min;
 708   uint32_t max;
 709 };
 710
 711 static int
 712 find_min_max_it (void *cls, const struct GNUNET_PeerIdentity *h, void *k)
 713 {
 714   struct FindMinMaxCtx *find_res = cls;
 715   struct ATS_Address *a = k;
 716
 717   if (a->atsin[find_res->p->prop_type].avg > find_res->max)
 718     find_res->max = a->atsin[find_res->p->prop_type].avg;
 719
 720   if (a->atsin[find_res->p->prop_type].avg < find_res->min)
 721     find_res->min = a->atsin[find_res->p->prop_type].avg;
 722
 723   return GNUNET_OK;
 724 }
 725
 726 static int
 727 normalize_address (void *cls, const struct GNUNET_PeerIdentity *h, void *k)
 728 {
 729   struct Property *p = cls;
 730   struct ATS_Address *address = k;
 731   double delta;
 732   double backup;
 733   uint32_t avg_value;
 734
 735   backup = address->atsin[p->prop_type].norm;
 736   avg_value = address->atsin[p->prop_type].avg;
 737   delta = p->max - p->min;
 738   /* max - 2 * min + avg_value / max - min */
 739   if (0 != delta)
 740     address->atsin[p->prop_type].norm = (delta + (avg_value - p->min)) / (delta);
 741   else
 742     address->atsin[p->prop_type].norm = DEFAULT_REL_QUALITY;
 743
 744   if (backup == address->atsin[p->prop_type].norm)
 745     return GNUNET_OK;
 746
 747   LOG(GNUNET_ERROR_TYPE_DEBUG,
 748       "Normalize `%s' address %p's '%s' with value %u to range [%u..%u] = %.3f\n",
 749       GNUNET_i2s (&address->peer), address,
 750       GNUNET_ATS_print_property_type (p->atsi_type),
 751       address->atsin[p->prop_type].avg, p->min, p->max,
 752       address->atsin[p->prop_type].norm);
 753
 754   if (NULL != prop_ch_cb)
 755     prop_ch_cb (prop_ch_cb_cls, address, p->atsi_type,
 756         address->atsin[p->prop_type].norm);
 757
 758   return GNUNET_OK;
 759 }
 760
 761 /**
 762  * Normalize avg_value to a range of values between [1.0, 2.0]
 763  * based on min max values currently known.
 764  *
 765  * @param addresses the address hashmap
 766  * @param p the property
 767  * @param address the address
 768  * @param avg_value the value to normalize
 769  */
 770 static void
 771 property_normalize (struct GNUNET_CONTAINER_MultiPeerMap *addresses,
 772     struct Property *p, struct ATS_Address *address, uint32_t avg_value)
 773 {
 774   struct FindMinMaxCtx find_ctx;
 775   int addr_count;
 776   int limits_changed;
 777
 778   find_ctx.p = p;
 779   find_ctx.max = 0;
 780   find_ctx.min = UINT32_MAX;
 781   addr_count = GNUNET_CONTAINER_multipeermap_iterate (addresses,
 782       &find_min_max_it, &find_ctx);
 783   if (0 == addr_count)
 784   {
 785     GNUNET_break(0);
 786     return;
 787   }
 788
 789   limits_changed = GNUNET_NO;
 790   if (find_ctx.max != p->max)
 791   {
 792     LOG(GNUNET_ERROR_TYPE_DEBUG,
 793         "Normalizing %s: new maximum %u -> recalculate all values\n",
 794         GNUNET_ATS_print_property_type (p->atsi_type), find_ctx.max);
 795     p->max = find_ctx.max;
 796     limits_changed = GNUNET_YES;
 797   }
 798
 799   if ((find_ctx.min != p->min) && (find_ctx.min < p->max))
 800   {
 801     LOG(GNUNET_ERROR_TYPE_DEBUG,
 802         "Normalizing %s: new minimum %u -> recalculate all values\n",
 803         GNUNET_ATS_print_property_type (p->atsi_type), find_ctx.min,
 804         find_ctx.max);
 805     p->min = find_ctx.min;
 806     limits_changed = GNUNET_YES;
 807   }
 808   else if (find_ctx.min == p->max)
 809   {
 810     /* Only one value, so minimum has to be 0 */
 811     p->min = 0;
 812   }
 813
 814   /* Normalize the values of this property */
 815   if (GNUNET_NO == limits_changed)
 816   {
 817     /* normalize just this  address */
 818     normalize_address (p, &address->peer, address);
 819     return;
 820   }
 821   else
 822   {
 823     /* limits changed, normalize all addresses */
 824     GNUNET_CONTAINER_multipeermap_iterate (addresses, &normalize_address, p);
 825     return;
 826   }
 827 }
 828
 829 /**
 830  * Update and normalize atsi performance information
 831  *
 832  * @param addresses hashmap containing all addresses
 833  * @param address the address to update
 834  * @param atsi the array of performance information
 835  * @param atsi_count the number of atsi information in the array
 836  */
 837 void
 838 GAS_normalization_normalize_property (
 839     struct GNUNET_CONTAINER_MultiPeerMap *addresses,
 840     struct ATS_Address *address, const struct GNUNET_ATS_Information *atsi,
 841     uint32_t atsi_count)
 842 {
 843   struct Property *cur_prop;
 844   int c1;
 845   int c2;
 846   uint32_t current_type;
 847   uint32_t current_val;
 848   unsigned int existing_properties[] = GNUNET_ATS_QualityProperties;
 849
 850   GNUNET_assert(NULL != address);
 851   GNUNET_assert(NULL != atsi);
 852
 853   LOG(GNUNET_ERROR_TYPE_DEBUG, "Updating %u elements for peer `%s'\n",
 854       atsi_count, GNUNET_i2s (&address->peer));
 855
 856   for (c1 = 0; c1 < atsi_count; c1++)
 857   {
 858     current_type = ntohl (atsi[c1].type);
 859
 860     for (c2 = 0; c2 < GNUNET_ATS_QualityPropertiesCount; c2++)
 861     {
 862       /* Check if type is valid */
 863       if (current_type == existing_properties[c2])
 864         break;
 865     }
 866     if (GNUNET_ATS_QualityPropertiesCount == c2)
 867     {
 868       /* Invalid property, continue with next element */
 869       continue;
 870     }
 871     /* Averaging */
 872     current_val = property_average (address, &atsi[c1]);
 873     if (GNUNET_ATS_VALUE_UNDEFINED == current_val)
 874     {
 875       GNUNET_break(0);
 876       continue;
 877     }
 878
 879     /* Normalizing */
 880     /* Check min, max */
 881     cur_prop = &properties[c2];
 882     property_normalize (addresses, cur_prop, address, current_val);
 883   }
 884 }
 885
 886 static void
 887 free_client (struct PreferenceClient *pc)
 888 {
 889   struct PreferencePeer *next_p;
 890   struct PreferencePeer *p;
 891   next_p = pc->p_head;
 892   while (NULL != (p = next_p))
 893   {
 894     next_p = p->next;
 895     GNUNET_CONTAINER_DLL_remove(pc->p_head, pc->p_tail, p);
 896     GNUNET_free(p);
 897   }
 898   GNUNET_free(pc);
 899 }
 900
 901 /**
 902  * A performance client disconnected
 903  *
 904  * @param client the client
 905  */
 906
 907 void
 908 GAS_normalization_preference_client_disconnect (void *client)
 909 {
 910   struct PreferenceClient *c_cur;
 911   /* Find preference client */
 912
 913   for (c_cur = pc_head; NULL != c_cur; c_cur = c_cur->next)
 914   {
 915     if (client == c_cur->client)
 916       break;
 917   }
 918   if (NULL == c_cur)
 919     return;
 920
 921   GNUNET_CONTAINER_DLL_remove(pc_head, pc_tail, c_cur);
 922   free_client (c_cur);
 923 }
 924
 925 /**
 926  * Start the normalization component
 927  *
 928  * @param pref_ch_cb callback to call on relative preference changing
 929  * @param pref_ch_cb_cls cls for the preference callback
 930  * @param property_ch_cb callback to call on relative property changing
 931  * @param property_ch_cb_cls cls for the property callback
 932  */
 933 void
 934 GAS_normalization_start (GAS_Normalization_preference_changed_cb pref_ch_cb,
 935     void *pref_ch_cb_cls, GAS_Normalization_property_changed_cb property_ch_cb,
 936     void *property_ch_cb_cls)
 937 {
 938   int c1;
 939   int i;
 940   preference_peers = GNUNET_CONTAINER_multipeermap_create (10, GNUNET_NO);
 941   property_peers = GNUNET_CONTAINER_multipeermap_create (10, GNUNET_NO);
 942   unsigned int existing_properties[] = GNUNET_ATS_QualityProperties;
 943
 944   for (c1 = 0; c1 < GNUNET_ATS_QualityPropertiesCount; c1++)
 945   {
 946     properties[c1].prop_type = c1;
 947     properties[c1].atsi_type = existing_properties[c1];
 948     properties[c1].min = 0;
 949     properties[c1].max = 0;
 950   }
 951
 952   pref_changed_cb = pref_ch_cb;
 953   pref_changed_cb_cls = pref_ch_cb_cls;
 954   prop_ch_cb = property_ch_cb;
 955   prop_ch_cb_cls = pref_ch_cb_cls;
 956
 957   pc_head = NULL;
 958   pc_tail = NULL;
 959
 960   for (i = 0; i < GNUNET_ATS_PreferenceCount; i++)
 961     defvalues.f_rel[i] = DEFAULT_REL_PREFERENCE;
 962   aging_task = GNUNET_SCHEDULER_NO_TASK;
 963   return;
 964 }
 965
 966 /**
 967  * Free a peer
 968  *
 969  * @param cls unused
 970  * @param key the key
 971  * @param value RelativePeer
 972  * @return #GNUNET_OK to continue
 973  */
 974 static int
 975 free_peer (void *cls, const struct GNUNET_PeerIdentity *key, void *value)
 976 {
 977   struct PeerRelative *rp = value;
 978   if (GNUNET_YES
 979       == GNUNET_CONTAINER_multipeermap_remove (preference_peers, key, value))
 980     GNUNET_free(rp);
 981   else
 982     GNUNET_break(0);
 983   return GNUNET_OK;
 984 }
 985
 986 /**
 987  * Stop the normalization component and free all items
 988  */
 989 void
 990 GAS_normalization_stop ()
 991 {
 992   struct PreferenceClient *pc;
 993   struct PreferenceClient *next_pc;
 994
 995   if (GNUNET_SCHEDULER_NO_TASK != aging_task)
 996   {
 997     GNUNET_SCHEDULER_cancel (aging_task);
 998     aging_task = GNUNET_SCHEDULER_NO_TASK;
 999   }
1000
1001   next_pc = pc_head;
1002   while (NULL != (pc = next_pc))
1003   {
1004     next_pc = pc->next;
1005     GNUNET_CONTAINER_DLL_remove(pc_head, pc_tail, pc);
1006     free_client (pc);
1007   }
1008
1009   GNUNET_CONTAINER_multipeermap_iterate (preference_peers, &free_peer, NULL );
1010   GNUNET_CONTAINER_multipeermap_destroy (preference_peers);
1011   GNUNET_CONTAINER_multipeermap_destroy (property_peers);
1012   return;
1013 }
1014
1015 /* end of gnunet-service-ats_normalization.c */