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