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