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