src/ats/gnunet-service-ats_normalization.c

   1 /*
   2  This file is part of GNUnet.
   3  Copyright (C) 2011-2015 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 <float.h>
  29 #include "gnunet_ats_service.h"
  30 #include "gnunet-service-ats_addresses.h"
  31 #include "gnunet-service-ats_normalization.h"
  32 #include "gnunet-service-ats_plugins.h"
  33
  34 #define LOG(kind,...) GNUNET_log_from (kind, "ats-normalization",__VA_ARGS__)
  35
  36
  37 /**
  38  * Range information for normalization of quality properties.
  39  */
  40 struct Property
  41 {
  42   /**
  43    * Index into the properties array.
  44    */
  45   uint32_t prop_type;
  46
  47   /**
  48    * Corresponding enum value of the respective quality property.
  49    */
  50   enum GNUNET_ATS_Property atsi_type;
  51
  52   /**
  53    * Minimum value we see for this property across all addresses.
  54    */
  55   uint32_t min;
  56
  57   /**
  58    * Maximum value we see for this property across all addresses.
  59    */
  60   uint32_t max;
  61 };
  62
  63
  64 /**
  65  * Range information for all quality properties we see.
  66  */
  67 static struct Property properties[GNUNET_ATS_QualityPropertiesCount];
  68
  69
  70
  71 /**
  72  * Add the value from @a atsi to the running average of the
  73  * given @a ni quality property.
  74  *
  75  * @param ni normalization information to update
  76  * @param atsi the ats information
  77  */
  78 static void
  79 property_average (struct GAS_NormalizationInfo *ni,
  80                   const struct GNUNET_ATS_Information *atsi)
  81 {
  82   uint32_t current_val;
  83   uint32_t res;
  84   uint64_t sum;
  85   uint32_t count;
  86   unsigned int c1;
  87
  88   current_val = ntohl (atsi->value);
  89   GNUNET_assert (GNUNET_ATS_VALUE_UNDEFINED != current_val);
  90   ni->atsi_abs[ni->avg_queue_index++] = current_val;
  91   if (GAS_normalization_queue_length == ni->avg_queue_index)
  92     ni->avg_queue_index = 0;
  93   count = 0;
  94   sum = 0;
  95   for (c1 = 0; c1 < GAS_normalization_queue_length; c1++)
  96   {
  97     if (GNUNET_ATS_VALUE_UNDEFINED != ni->atsi_abs[c1])
  98     {
  99       count++;
 100       sum += ni->atsi_abs[c1];
 101     }
 102   }
 103   GNUNET_assert (0 != count);
 104   res = sum / count;
 105   ni->avg = res;
 106 }
 107
 108
 109 /**
 110  * Closure for #find_min_max_it().
 111  */
 112 struct FindMinMaxCtx
 113 {
 114   /**
 115    * Property we are looking for.
 116    */
 117   struct Property *p;
 118
 119   /**
 120    * Set to mimimum value observed.
 121    */
 122   uint32_t min;
 123
 124   /**
 125    * Set to maximum value observed.
 126    */
 127   uint32_t max;
 128 };
 129
 130
 131 /**
 132  * Function called for all addresses and peers to find the minimum and
 133  * maximum (averaged) values for a given quality property.  Given
 134  * those, we can then calculate the normalized score.
 135  *
 136  * @param cls the `struct FindMinMaxCtx`
 137  * @param h which peer are we looking at (ignored)
 138  * @param k the address for that peer
 139  * @return #GNUNET_OK (continue to iterate)
 140  */
 141 static int
 142 find_min_max_it (void *cls,
 143                  const struct GNUNET_PeerIdentity *h,
 144                  void *k)
 145 {
 146   struct FindMinMaxCtx *find_res = cls;
 147   const struct ATS_Address *a = k;
 148
 149   find_res->max = GNUNET_MAX (find_res->max,
 150                               a->atsin[find_res->p->prop_type].avg);
 151   find_res->min = GNUNET_MIN (find_res->min,
 152                               a->atsin[find_res->p->prop_type].avg);
 153   return GNUNET_OK;
 154 }
 155
 156
 157 /**
 158  * Normalize the property value for a given address based
 159  * on the range we know that property value has globally.
 160  *
 161  * @param cls the `struct Property` with details on the
 162  *            property and its global range
 163  * @param key which peer are we looking at (ignored)
 164  * @param value the address for that peer, from where we get
 165  *            the original value and where we write the
 166  *            normalized value
 167  * @return #GNUNET_OK (continue to iterate)
 168  */
 169 static int
 170 normalize_address (void *cls,
 171                    const struct GNUNET_PeerIdentity *key,
 172                    void *value)
 173 {
 174   struct Property *p = cls;
 175   struct ATS_Address *address = value;
 176   double delta;
 177   double update;
 178   uint32_t avg_value;
 179
 180   avg_value = address->atsin[p->prop_type].avg;
 181   delta = p->max - p->min;
 182   /* max - 2 * min + avg_value / (max - min) */
 183   if (delta > DBL_EPSILON)
 184     update = DEFAULT_REL_QUALITY + (avg_value - p->min) / delta;
 185   else
 186     update = DEFAULT_REL_QUALITY;
 187
 188   if (update == address->atsin[p->prop_type].norm)
 189     return GNUNET_OK;
 190   address->atsin[p->prop_type].norm = update;
 191
 192   LOG (GNUNET_ERROR_TYPE_DEBUG,
 193        "Normalize `%s' address %p's '%s' with value %u to range [%u..%u] = %.3f\n",
 194        GNUNET_i2s (&address->peer),
 195        address,
 196        GNUNET_ATS_print_property_type (p->atsi_type),
 197        address->atsin[p->prop_type].avg,
 198        p->min,
 199        p->max,
 200        address->atsin[p->prop_type].norm);
 201   return GNUNET_OK;
 202 }
 203
 204
 205 /**
 206  * Notify about change in normalized property.
 207  *
 208  * @param cls the `struct Property` with details on the
 209  *            property and its global range
 210  * @param key which peer are we looking at (ignored)
 211  * @param value the address for that peer
 212  * @return #GNUNET_OK (continue to iterate)
 213  */
 214 static int
 215 notify_change (void *cls,
 216                const struct GNUNET_PeerIdentity *key,
 217                void *value)
 218 {
 219   struct Property *p = cls;
 220   struct ATS_Address *address = value;
 221
 222   GAS_plugin_notify_property_changed (address,
 223                                    p->atsi_type,
 224                                    address->atsin[p->prop_type].norm);
 225   return GNUNET_OK;
 226 }
 227
 228
 229 /**
 230  * Update and normalize atsi performance information
 231  *
 232  * @param address the address to update
 233  * @param atsi the array of performance information
 234  * @param atsi_count the number of atsi information in the array
 235  */
 236 void
 237 GAS_normalization_update_property (struct ATS_Address *address,
 238                                       const struct GNUNET_ATS_Information *atsi,
 239                                       uint32_t atsi_count)
 240 {
 241   unsigned int c1;
 242   unsigned int c2;
 243   uint32_t current_type;
 244   uint32_t old;
 245   struct FindMinMaxCtx find_ctx;
 246   int range_changed;
 247
 248   LOG (GNUNET_ERROR_TYPE_DEBUG,
 249        "Updating %u elements for peer `%s'\n",
 250        atsi_count,
 251        GNUNET_i2s (&address->peer));
 252   GAS_plugin_solver_lock ();
 253   for (c1 = 0; c1 < atsi_count; c1++)
 254   {
 255     current_type = ntohl (atsi[c1].type);
 256
 257     for (c2 = 0; c2 < GNUNET_ATS_QualityPropertiesCount; c2++)
 258       if (current_type == properties[c2].atsi_type)
 259         break;
 260     if (GNUNET_ATS_QualityPropertiesCount == c2)
 261     {
 262       /* Not a quality property, continue with next element */
 263       continue;
 264     }
 265     /* Calculate running average */
 266     old = address->atsin[c2].avg;
 267     property_average (&address->atsin[c2],
 268                       &atsi[c1]);
 269     if (old == address->atsin[c2].avg)
 270       continue; /* no change */
 271     range_changed = GNUNET_NO;
 272     if ( (old == properties[c2].min) ||
 273          (old == properties[c2].max) ||
 274          (address->atsin[c2].avg < properties[c2].min) ||
 275          (address->atsin[c2].avg > properties[c2].max) )
 276     {
 277       /* need to re-calculate min/max range, as it may have changed */
 278       find_ctx.p = &properties[c2];
 279       find_ctx.max = 0;
 280       find_ctx.min = UINT32_MAX;
 281       if (0 ==
 282           GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 283                                                  &find_min_max_it,
 284                                                  &find_ctx))
 285       {
 286         GNUNET_break(0);
 287         continue;
 288       }
 289       if ( (find_ctx.min != properties[c2].min) ||
 290            (find_ctx.max != properties[c2].max) )
 291       {
 292         properties[c2].min = find_ctx.min;
 293         properties[c2].max = find_ctx.max;
 294         /* limits changed, (re)normalize all addresses */
 295         range_changed = GNUNET_YES;
 296       }
 297     }
 298     if (GNUNET_YES == range_changed)
 299       GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 300                                              &normalize_address,
 301                                              &properties[c2]);
 302     else
 303       normalize_address (&properties[c2],
 304                          &address->peer,
 305                          address);
 306     /* after all peers have been updated, notify about changes */
 307     if (GNUNET_YES == range_changed)
 308       GNUNET_CONTAINER_multipeermap_iterate (GSA_addresses,
 309                                              &notify_change,
 310                                              &properties[c2]);
 311     else
 312       notify_change (&properties[c2],
 313                      &address->peer,
 314                      address);
 315
 316   }
 317   GAS_plugin_solver_unlock ();
 318 }
 319
 320
 321 /**
 322  * Start the normalization component
 323  */
 324 void
 325 GAS_normalization_start ()
 326 {
 327   unsigned int c1;
 328   const unsigned int existing_properties[] = GNUNET_ATS_QualityProperties;
 329
 330   for (c1 = 0; c1 < GNUNET_ATS_QualityPropertiesCount; c1++)
 331   {
 332     properties[c1].prop_type = c1;
 333     properties[c1].atsi_type = existing_properties[c1];
 334     properties[c1].min = UINT32_MAX;
 335     properties[c1].max = 0;
 336   }
 337 }
 338
 339
 340 /**
 341  * Stop the normalization component and free all items
 342  */
 343 void
 344 GAS_normalization_stop ()
 345 {
 346   /* nothing to do */
 347 }
 348
 349
 350 /* end of gnunet-service-ats_normalization.c */