src/ats/plugin_ats_proportional.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  * @file ats/plugin_ats_proportional.c
  22  * @brief ATS proportional solver
  23  * @author Matthias Wachs
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_statistics_service.h"
  28 #include "gnunet_ats_plugin.h"
  29 #include "gnunet_ats_service.h"
  30 #include "gnunet-service-ats_addresses.h"
  31
  32 #define LOG(kind,...) GNUNET_log_from (kind, "ats-proportional",__VA_ARGS__)
  33
  34 /**
  35  * How much do we value stability over adaptation by default.  A low
  36  * value (close to 1.0) means we adapt as soon as possible, a larger
  37  * value means that we have to have the respective factor of an
  38  * advantage (or delay) before we adapt and sacrifice stability.
  39  */
  40 #define PROP_STABILITY_FACTOR 1.25
  41
  42
  43 /**
  44  * Default value to assume for the proportionality factor, if none is
  45  * given in the configuration.  This factor determines how strong the
  46  * bandwidth allocation will orient itself on the application
  47  * preferences.  A lower factor means a more balanced bandwidth
  48  * distribution while a larger number means a distribution more in
  49  * line with application (bandwidth) preferences.
  50  */
  51 #define PROPORTIONALITY_FACTOR 2.0
  52
  53
  54 /**
  55  * Address information stored for the proportional solver in the
  56  * `solver_information` member of `struct GNUNET_ATS_Address`.
  57  *
  58  * They are also stored in the respective `struct Network`'s linked
  59  * list.
  60  */
  61 struct AddressWrapper
  62 {
  63   /**
  64    * Next in DLL
  65    */
  66   struct AddressWrapper *next;
  67
  68   /**
  69    * Previous in DLL
  70    */
  71   struct AddressWrapper *prev;
  72
  73   /**
  74    * The address
  75    */
  76   struct ATS_Address *addr;
  77
  78     /**
  79    * Network scope this address is in
  80    */
  81   struct Network *network;
  82
  83   /**
  84    * Inbound quota
  85    */
  86   uint32_t calculated_quota_in;
  87
  88   /**
  89    * Outbound quota
  90    */
  91   uint32_t calculated_quota_out;
  92
  93   /**
  94    * When was this address activated
  95    */
  96   struct GNUNET_TIME_Absolute activated;
  97
  98 };
  99
 100
 101 /**
 102  * Representation of a network
 103  */
 104 struct Network
 105 {
 106   /**
 107    * Network description
 108    */
 109   const char *desc;
 110
 111   /**
 112    * String for statistics total addresses
 113    */
 114   char *stat_total;
 115
 116   /**
 117    * String for statistics active addresses
 118    */
 119   char *stat_active;
 120
 121   /**
 122    * Linked list of addresses in this network: head
 123    */
 124   struct AddressWrapper *head;
 125
 126   /**
 127    * Linked list of addresses in this network: tail
 128    */
 129   struct AddressWrapper *tail;
 130
 131   /**
 132    * Total inbound quota
 133    */
 134   unsigned long long total_quota_in;
 135
 136   /**
 137    * Total outbound quota
 138    */
 139   unsigned long long total_quota_out;
 140
 141   /**
 142    * ATS network type
 143    */
 144   enum GNUNET_ATS_Network_Type type;
 145
 146   /**
 147    * Number of active addresses for this network
 148    */
 149   unsigned int active_addresses;
 150
 151   /**
 152    * Number of total addresses for this network
 153    */
 154   unsigned int total_addresses;
 155
 156 };
 157
 158
 159 /**
 160  * A handle for the proportional solver
 161  */
 162 struct GAS_PROPORTIONAL_Handle
 163 {
 164
 165   /**
 166    * Our execution environment.
 167    */
 168   struct GNUNET_ATS_PluginEnvironment *env;
 169
 170   /**
 171    * Networks array
 172    */
 173   struct Network *network_entries;
 174
 175   /**
 176    * Proportionality factor
 177    */
 178   double prop_factor;
 179
 180   /**
 181    * Stability factor
 182    */
 183   double stability_factor;
 184
 185   /**
 186    * Bulk lock counter. If zero, we are not locked.
 187    */
 188   unsigned int bulk_lock;
 189
 190   /**
 191    * Number of changes made while solver was locked.  We really only
 192    * use 0/non-zero to check on unlock if we have to run the update.
 193    */
 194   unsigned int bulk_requests;
 195
 196   /**
 197    * Number of active addresses for solver
 198    */
 199   unsigned int active_addresses;
 200
 201   /**
 202    * Number of networks in @a network_entries
 203    */
 204   unsigned int network_count;
 205 };
 206
 207
 208 /**
 209  * Test if bandwidth is available in this network to add an additional address.
 210  *
 211  * @param net the network type to check
 212  * @param extra for how many extra addresses do we check?
 213  * @return #GNUNET_YES or #GNUNET_NO
 214  */
 215 static int
 216 is_bandwidth_available_in_network (struct Network *net,
 217                                    int extra)
 218 {
 219   unsigned int na;
 220   uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
 221
 222   GNUNET_assert (net->active_addresses + extra >= 0);
 223   na = net->active_addresses + extra;
 224   if (0 == na)
 225     return GNUNET_YES;
 226   if ( ((net->total_quota_in / na) > min_bw) &&
 227        ((net->total_quota_out / na) > min_bw) )
 228     return GNUNET_YES;
 229   return GNUNET_NO;
 230 }
 231
 232
 233 /**
 234  * Test if all peers in this network require connectivity at level at
 235  * least @a con.
 236  *
 237  * @param s the solver handle
 238  * @param net the network type to check
 239  * @param con connection return value threshold to check
 240  * @return #GNUNET_YES or #GNUNET_NO
 241  */
 242 static int
 243 all_require_connectivity (struct GAS_PROPORTIONAL_Handle *s,
 244                           struct Network *net,
 245                           unsigned int con)
 246 {
 247   struct AddressWrapper *aw;
 248
 249   for (aw = net->head; NULL != aw; aw = aw->next)
 250     if (con >
 251         s->env->get_connectivity (s->env->cls,
 252                                   &aw->addr->peer))
 253       return GNUNET_NO;
 254   return GNUNET_YES;
 255 }
 256
 257
 258 /**
 259  * Update bandwidth assigned to peers in this network.  The basic idea
 260  * is to assign every peer in the network the minimum bandwidth, and
 261  * then distribute the remaining bandwidth proportional to application
 262  * preferences.
 263  *
 264  * @param s the solver handle
 265  * @param net the network type to update
 266  */
 267 static void
 268 distribute_bandwidth (struct GAS_PROPORTIONAL_Handle *s,
 269                       struct Network *net)
 270 {
 271   const uint32_t min_bw = ntohl (GNUNET_CONSTANTS_DEFAULT_BW_IN_OUT.value__);
 272   struct AddressWrapper *aw;
 273   unsigned long long remaining_quota_in;
 274   unsigned long long quota_out_used;
 275   unsigned long long remaining_quota_out;
 276   unsigned long long quota_in_used;
 277   unsigned int count_addresses;
 278   double sum_relative_peer_prefences;
 279   double peer_weight;
 280   double total_weight;
 281   const double *peer_relative_prefs;
 282
 283   LOG (GNUNET_ERROR_TYPE_INFO,
 284        "Recalculate quota for network type `%s' for %u addresses (in/out): %llu/%llu \n",
 285        net->desc,
 286        net->active_addresses,
 287        net->total_quota_in,
 288        net->total_quota_in);
 289
 290   if (0 == net->active_addresses)
 291     return; /* no addresses to update */
 292
 293   /* sanity checks */
 294   if ((net->active_addresses * min_bw) > net->total_quota_in)
 295   {
 296     GNUNET_break(0);
 297     return;
 298   }
 299   if ((net->active_addresses * min_bw) > net->total_quota_out)
 300   {
 301     GNUNET_break(0);
 302     return;
 303   }
 304
 305   /* Calculate sum of relative preference for active addresses in this
 306      network */
 307   sum_relative_peer_prefences = 0.0;
 308   count_addresses = 0;
 309   for (aw = net->head; NULL != aw; aw = aw->next)
 310   {
 311     if (GNUNET_YES != aw->addr->active)
 312       continue;
 313     peer_relative_prefs = s->env->get_preferences (s->env->cls,
 314                                                    &aw->addr->peer);
 315     sum_relative_peer_prefences += peer_relative_prefs[GNUNET_ATS_PREFERENCE_BANDWIDTH];
 316     count_addresses++;
 317   }
 318   if (count_addresses != net->active_addresses)
 319   {
 320     GNUNET_break (0);
 321     LOG (GNUNET_ERROR_TYPE_WARNING,
 322          "%s: Counted %u active addresses, expected %u active addresses\n",
 323          net->desc,
 324          count_addresses,
 325          net->active_addresses);
 326     /* try to fix... */
 327     net->active_addresses = count_addresses;
 328   }
 329   LOG (GNUNET_ERROR_TYPE_INFO,
 330        "Total relative preference %.3f for %u addresses in network %s\n",
 331        sum_relative_peer_prefences,
 332        net->active_addresses,
 333        net->desc);
 334
 335   /* check how much we have to distribute */
 336   remaining_quota_in = net->total_quota_in - (net->active_addresses * min_bw);
 337   remaining_quota_out = net->total_quota_out - (net->active_addresses * min_bw);
 338   LOG (GNUNET_ERROR_TYPE_DEBUG,
 339        "Proportionally distributable bandwidth (in/out): %llu/%llu\n",
 340        remaining_quota_in,
 341        remaining_quota_out);
 342
 343   /* distribute remaining quota; we do not do it exactly proportional,
 344      but balance "even" distribution ("net->active_addresses") with
 345      the preference sum using the "prop_factor". */
 346   total_weight = net->active_addresses +
 347     s->prop_factor * sum_relative_peer_prefences;
 348   quota_out_used = 0;
 349   quota_in_used = 0;
 350   for (aw = net->head; NULL != aw; aw = aw->next)
 351   {
 352     if (GNUNET_YES != aw->addr->active)
 353     {
 354       /* set to 0, just to be sure */
 355       aw->calculated_quota_in = 0;
 356       aw->calculated_quota_out = 0;
 357       continue;
 358     }
 359     peer_relative_prefs = s->env->get_preferences (s->env->cls,
 360                                                    &aw->addr->peer);
 361     peer_weight = 1.0
 362       + s->prop_factor * peer_relative_prefs[GNUNET_ATS_PREFERENCE_BANDWIDTH];
 363
 364     aw->calculated_quota_in = min_bw
 365       + (peer_weight / total_weight) * remaining_quota_in;
 366     aw->calculated_quota_out = min_bw
 367       + (peer_weight / total_weight) * remaining_quota_out;
 368
 369     LOG (GNUNET_ERROR_TYPE_INFO,
 370          "New quotas for peer `%s' with weight (cur/total) %.3f/%.3f (in/out) are: %u/%u\n",
 371          GNUNET_i2s (&aw->addr->peer),
 372          peer_weight,
 373          total_weight,
 374          (unsigned int) aw->calculated_quota_in,
 375          (unsigned int) aw->calculated_quota_out);
 376     quota_in_used += aw->calculated_quota_in;
 377     quota_out_used += aw->calculated_quota_out;
 378   }
 379   LOG (GNUNET_ERROR_TYPE_DEBUG,
 380        "Total bandwidth assigned is (in/out): %llu /%llu\n",
 381        quota_in_used,
 382        quota_out_used);
 383   /* +1 due to possible rounding errors */
 384   GNUNET_break (quota_out_used <= net->total_quota_out + 1);
 385   GNUNET_break (quota_in_used <= net->total_quota_in + 1);
 386 }
 387
 388
 389 /**
 390  * Notify ATS service of bandwidth changes to addresses.
 391  *
 392  * @param s solver handle
 393  * @param net the network to propagate changes in
 394  */
 395 static void
 396 propagate_bandwidth (struct GAS_PROPORTIONAL_Handle *s,
 397                      struct Network *net)
 398 {
 399   struct AddressWrapper *cur;
 400
 401   for (cur = net->head; NULL != cur; cur = cur->next)
 402   {
 403     if ( (cur->addr->assigned_bw_in == cur->calculated_quota_in) &&
 404          (cur->addr->assigned_bw_out == cur->calculated_quota_out) )
 405       continue;
 406     cur->addr->assigned_bw_in = cur->calculated_quota_in;
 407     cur->addr->assigned_bw_out = cur->calculated_quota_out;
 408     if (GNUNET_YES == cur->addr->active)
 409       s->env->bandwidth_changed_cb (s->env->cls,
 410                                     cur->addr);
 411   }
 412 }
 413
 414
 415 /**
 416  * Distribute bandwidth.  The addresses have already been selected,
 417  * this is merely distributed the bandwidth among the addresses.
 418  *
 419  * @param s the solver handle
 420  * @param n the network, can be NULL for all networks
 421  */
 422 static void
 423 distribute_bandwidth_in_network (struct GAS_PROPORTIONAL_Handle *s,
 424                                  struct Network *n)
 425 {
 426   unsigned int i;
 427
 428   if (GNUNET_YES == s->bulk_lock)
 429   {
 430     s->bulk_requests++;
 431     return;
 432   }
 433   if (NULL != n)
 434   {
 435     LOG (GNUNET_ERROR_TYPE_DEBUG,
 436         "Redistributing bandwidth in network %s with %u active and %u total addresses\n",
 437          GNUNET_ATS_print_network_type(n->type),
 438          n->active_addresses,
 439          n->total_addresses);
 440     s->env->info_cb (s->env->cls,
 441                      GAS_OP_SOLVE_START,
 442                      GAS_STAT_SUCCESS,
 443                      GAS_INFO_PROP_SINGLE);
 444     distribute_bandwidth(s,
 445                          n);
 446     s->env->info_cb (s->env->cls,
 447                      GAS_OP_SOLVE_STOP,
 448                      GAS_STAT_SUCCESS,
 449                      GAS_INFO_PROP_SINGLE);
 450     s->env->info_cb (s->env->cls,
 451                      GAS_OP_SOLVE_UPDATE_NOTIFICATION_START,
 452                      GAS_STAT_SUCCESS,
 453                      GAS_INFO_PROP_SINGLE);
 454     propagate_bandwidth (s,
 455                          n);
 456
 457     s->env->info_cb (s->env->cls,
 458                      GAS_OP_SOLVE_UPDATE_NOTIFICATION_STOP,
 459                      GAS_STAT_SUCCESS,
 460                      GAS_INFO_PROP_SINGLE);
 461   }
 462   else
 463   {
 464     s->env->info_cb (s->env->cls,
 465                      GAS_OP_SOLVE_START,
 466                      GAS_STAT_SUCCESS,
 467                      GAS_INFO_PROP_ALL);
 468     for (i = 0; i < s->network_count; i++)
 469       distribute_bandwidth (s,
 470                             &s->network_entries[i]);
 471     s->env->info_cb (s->env->cls,
 472                      GAS_OP_SOLVE_STOP,
 473                      GAS_STAT_SUCCESS,
 474                      GAS_INFO_PROP_ALL);
 475     s->env->info_cb (s->env->cls,
 476                      GAS_OP_SOLVE_UPDATE_NOTIFICATION_START,
 477                      GAS_STAT_SUCCESS,
 478                      GAS_INFO_PROP_ALL);
 479     for (i = 0; i < s->network_count; i++)
 480       propagate_bandwidth (s,
 481                            &s->network_entries[i]);
 482     s->env->info_cb (s->env->cls,
 483                      GAS_OP_SOLVE_UPDATE_NOTIFICATION_STOP,
 484                      GAS_STAT_SUCCESS,
 485                      GAS_INFO_PROP_ALL);
 486   }
 487 }
 488
 489
 490 /**
 491  * Context for finding the best address* Linked list of addresses in this network: head
 492  */
 493 struct FindBestAddressCtx
 494 {
 495   /**
 496    * The solver handle
 497    */
 498   struct GAS_PROPORTIONAL_Handle *s;
 499
 500   /**
 501    * The currently best address
 502    */
 503   struct ATS_Address *best;
 504 };
 505
 506
 507 /**
 508  * Find index of a ATS property type in the quality properties array.
 509  *
 510  * @param type ATS property type
 511  * @return index in the quality array, #GNUNET_SYSERR if the type
 512  *         was not a quality property
 513  */
 514 static int
 515 find_quality_property_index (enum GNUNET_ATS_Property type)
 516 {
 517   enum GNUNET_ATS_Property existing_types[] = GNUNET_ATS_QualityProperties;
 518   unsigned int c;
 519
 520   for (c = 0; c < GNUNET_ATS_QualityPropertiesCount; c++)
 521     if (existing_types[c] == type)
 522       return c;
 523   GNUNET_break (0);
 524   return GNUNET_SYSERR;
 525 }
 526
 527
 528 /**
 529  * Find a "good" address to use for a peer by iterating over the
 530  * addresses for this peer.  If we already have an existing address,
 531  * we stick to it.  Otherwise, we pick by lowest distance and then by
 532  * lowest latency.
 533  *
 534  * @param cls the `struct FindBestAddressCtx *' where we store the result
 535  * @param key the peer we are trying to find the best address for
 536  * @param value another `struct ATS_Address*` to consider using
 537  * @return #GNUNET_OK (continue to iterate)
 538  */
 539 static int
 540 find_best_address_it (void *cls,
 541                       const struct GNUNET_PeerIdentity *key,
 542                       void *value)
 543 {
 544   struct FindBestAddressCtx *ctx = cls;
 545   struct ATS_Address *current = value;
 546   struct AddressWrapper *asi = current->solver_information;
 547   struct GNUNET_TIME_Relative active_time;
 548   double best_delay;
 549   double best_distance;
 550   double cur_delay;
 551   double cur_distance;
 552   int index;
 553   unsigned int con;
 554   int bw_available;
 555   int need;
 556
 557   /* we need +1 slot if 'current' is not yet active */
 558   need = (GNUNET_YES == current->active) ? 0 : 1;
 559   /* we save -1 slot if 'best' is active and belongs
 560      to the same network (as we would replace it) */
 561   if ( (NULL != ctx->best) &&
 562        (GNUNET_YES == ctx->best->active) &&
 563        (((struct AddressWrapper *) ctx->best->solver_information)->network ==
 564         asi->network) )
 565     need--;
 566   /* we can gain -1 slot if this peers connectivity
 567      requirement is higher than that of another peer
 568      in that network scope */
 569   con = ctx->s->env->get_connectivity (ctx->s->env->cls,
 570                                        key);
 571   if (GNUNET_YES !=
 572       all_require_connectivity (ctx->s,
 573                                 asi->network,
 574                                 con))
 575     need--;
 576   /* test if minimum bandwidth for 'current' would be available */
 577   bw_available
 578     = is_bandwidth_available_in_network (asi->network,
 579                                          need);
 580   if (! bw_available)
 581   {
 582     /* Bandwidth for this address is unavailable, so we cannot use
 583        it. */
 584     return GNUNET_OK;
 585   }
 586   if (GNUNET_YES == current->active)
 587   {
 588     active_time = GNUNET_TIME_absolute_get_duration (asi->activated);
 589     if (active_time.rel_value_us <=
 590         ((double) GNUNET_TIME_UNIT_SECONDS.rel_value_us) * ctx->s->stability_factor)
 591     {
 592       /* Keep active address for stability reasons */
 593       ctx->best = current;
 594       return GNUNET_NO;
 595     }
 596   }
 597   if (NULL == ctx->best)
 598   {
 599     /* We so far have nothing else, so go with it! */
 600     ctx->best = current;
 601     return GNUNET_OK;
 602   }
 603
 604   /* Now compare ATS information */
 605   index = find_quality_property_index (GNUNET_ATS_QUALITY_NET_DISTANCE);
 606   cur_distance = current->atsin[index].norm;
 607   best_distance = ctx->best->atsin[index].norm;
 608   index = find_quality_property_index (GNUNET_ATS_QUALITY_NET_DELAY);
 609   cur_delay = current->atsin[index].norm;
 610   best_delay = ctx->best->atsin[index].norm;
 611
 612   /* user shorter distance */
 613   if (cur_distance < best_distance)
 614   {
 615     if (GNUNET_NO == ctx->best->active)
 616     {
 617       /* Activity doesn't influence the equation, use current */
 618       ctx->best = current;
 619     }
 620     else if ((best_distance / cur_distance) > ctx->s->stability_factor)
 621     {
 622       /* Distance change is significant, switch active address! */
 623       ctx->best = current;
 624     }
 625   }
 626
 627   /* User connection with less delay */
 628   if (cur_delay < best_delay)
 629   {
 630     if (GNUNET_NO == ctx->best->active)
 631     {
 632       /* Activity doesn't influence the equation, use current */
 633       ctx->best = current;
 634     }
 635     else if ((best_delay / cur_delay) > ctx->s->stability_factor)
 636     {
 637       /* Latency change is significant, switch active address! */
 638       ctx->best = current;
 639     }
 640   }
 641   return GNUNET_OK;
 642 }
 643
 644
 645 /**
 646  * Find the currently best address for a peer from the set of
 647  * addresses available or return NULL of no address is available.
 648  *
 649  * @param s the proportional handle
 650  * @param addresses the address hashmap
 651  * @param id the peer id
 652  * @return the address or NULL
 653  */
 654 struct ATS_Address *
 655 get_best_address (struct GAS_PROPORTIONAL_Handle *s,
 656                   struct GNUNET_CONTAINER_MultiPeerMap *addresses,
 657                   const struct GNUNET_PeerIdentity *id)
 658 {
 659   struct FindBestAddressCtx fba_ctx;
 660
 661   fba_ctx.best = NULL;
 662   fba_ctx.s = s;
 663   GNUNET_CONTAINER_multipeermap_get_multiple (addresses,
 664                                               id,
 665                                               &find_best_address_it,
 666                                               &fba_ctx);
 667   return fba_ctx.best;
 668 }
 669
 670
 671 /**
 672  * Decrease number of active addresses in network.
 673  *
 674  * @param s the solver handle
 675  * @param net the network type
 676  */
 677 static void
 678 address_decrement_active (struct GAS_PROPORTIONAL_Handle *s,
 679                           struct Network *net)
 680 {
 681   GNUNET_assert (net->active_addresses > 0);
 682   net->active_addresses--;
 683   GNUNET_STATISTICS_update (s->env->stats,
 684                             net->stat_active,
 685                             -1,
 686                             GNUNET_NO);
 687   GNUNET_assert (s->active_addresses > 0);
 688   s->active_addresses--;
 689   GNUNET_STATISTICS_update (s->env->stats,
 690                             "# ATS addresses total",
 691                             -1,
 692                             GNUNET_NO);
 693 }
 694
 695
 696 /**
 697  * Address map iterator to find current active address for peer.
 698  * Asserts that only one address is active per peer.
 699  *
 700  * @param cls last active address
 701  * @param key peer's key
 702  * @param value address to check
 703  * @return #GNUNET_NO on double active address else #GNUNET_YES;
 704  */
 705 static int
 706 get_active_address_it (void *cls,
 707                        const struct GNUNET_PeerIdentity *key,
 708                        void *value)
 709 {
 710   struct ATS_Address **dest = cls;
 711   struct ATS_Address *aa = value;
 712
 713   if (GNUNET_YES != aa->active)
 714     return GNUNET_OK;
 715   GNUNET_assert (NULL == (*dest));
 716   (*dest) = aa;
 717   return GNUNET_OK;
 718 }
 719
 720
 721 /**
 722  * Find current active address for peer
 723  *
 724  * @param s the solver handle
 725  * @param peer the peer
 726  * @return active address or NULL
 727  */
 728 static struct ATS_Address *
 729 get_active_address (struct GAS_PROPORTIONAL_Handle *s,
 730                     const struct GNUNET_PeerIdentity *peer)
 731 {
 732   struct ATS_Address *dest;
 733
 734   dest = NULL;
 735   GNUNET_CONTAINER_multipeermap_get_multiple (s->env->addresses,
 736                                               peer,
 737                                               &get_active_address_it,
 738                                               &dest);
 739   return dest;
 740 }
 741
 742
 743 /**
 744  * Update active address for a peer.  Check if active address exists
 745  * and what the best address is, if addresses are different switch.
 746  * Then reallocate bandwidth within the affected network scopes.
 747  *
 748  * @param s solver handle
 749  * @param current_address the address currently active for the peer,
 750  *        NULL for none
 751  * @param peer the peer to check
 752  */
 753 static void
 754 update_active_address (struct GAS_PROPORTIONAL_Handle *s,
 755                        struct ATS_Address *current_address,
 756                        const struct GNUNET_PeerIdentity *peer)
 757 {
 758   struct ATS_Address *best_address;
 759   struct AddressWrapper *asi_cur;
 760   struct AddressWrapper *asi_best;
 761   struct AddressWrapper *aw;
 762   struct AddressWrapper *aw_min;
 763   unsigned int a_con;
 764   unsigned int con_min;
 765
 766   best_address = get_best_address (s,
 767                                    s->env->addresses,
 768                                    peer);
 769   if (NULL != best_address)
 770     asi_best = best_address->solver_information;
 771   else
 772     asi_best = NULL;
 773   if (current_address == best_address)
 774     return; /* no changes */
 775   if (NULL != current_address)
 776   {
 777     /* We switch to a new address (or to none);
 778        mark old address as inactive. */
 779     asi_cur = current_address->solver_information;
 780     GNUNET_assert (GNUNET_YES == current_address->active);
 781     LOG (GNUNET_ERROR_TYPE_INFO,
 782          "Disabling previous active address for peer `%s'\n",
 783          GNUNET_i2s (peer));
 784     asi_cur->activated = GNUNET_TIME_UNIT_ZERO_ABS;
 785     current_address->active = GNUNET_NO;
 786     current_address->assigned_bw_in = 0;
 787     current_address->assigned_bw_out = 0;
 788     address_decrement_active (s,
 789                               asi_cur->network);
 790     if ( (NULL == best_address) ||
 791          (asi_best->network != asi_cur->network) )
 792       distribute_bandwidth_in_network (s,
 793                                        asi_cur->network);
 794     if (NULL == best_address)
 795     {
 796       /* We previously had an active address, but now we cannot
 797        * suggest one.  Therefore we have to disconnect the peer.
 798        * The above call to "distribute_bandwidth_in_network()
 799        * does not see 'current_address' so we need to trigger
 800        * the update here. */
 801       LOG (GNUNET_ERROR_TYPE_DEBUG,
 802            "Disconnecting peer `%s'.\n",
 803            GNUNET_i2s (peer));
 804       s->env->bandwidth_changed_cb (s->env->cls,
 805                                     current_address);
 806       return;
 807     }
 808   }
 809   if (NULL == best_address)
 810   {
 811     /* We do not have a new address, so we are done. */
 812     LOG (GNUNET_ERROR_TYPE_DEBUG,
 813          "Cannot suggest address for peer `%s'\n",
 814          GNUNET_i2s (peer));
 815     return;
 816   }
 817   /* We do have a new address, activate it */
 818   LOG (GNUNET_ERROR_TYPE_DEBUG,
 819        "Suggesting new address %p for peer `%s'\n",
 820        best_address,
 821        GNUNET_i2s (peer));
 822   /* Mark address as active */
 823   best_address->active = GNUNET_YES;
 824   asi_best->activated = GNUNET_TIME_absolute_get ();
 825   asi_best->network->active_addresses++;
 826   s->active_addresses++;
 827   GNUNET_STATISTICS_update (s->env->stats,
 828                             "# ATS active addresses total",
 829                             1,
 830                             GNUNET_NO);
 831   GNUNET_STATISTICS_update (s->env->stats,
 832                             asi_best->network->stat_active,
 833                             1,
 834                             GNUNET_NO);
 835   LOG (GNUNET_ERROR_TYPE_INFO,
 836        "Address %p for peer `%s' is now active\n",
 837        best_address,
 838        GNUNET_i2s (peer));
 839
 840
 841   if (GNUNET_NO ==
 842       is_bandwidth_available_in_network (asi_best->network,
 843                                          0))
 844   {
 845     /* we went over the maximum number of addresses for
 846        this scope; remove the address with the smallest
 847        connectivity requirement */
 848     con_min = UINT32_MAX;
 849     aw_min = NULL;
 850     for (aw = asi_best->network->head; NULL != aw; aw = aw->next)
 851     {
 852       if (con_min >
 853           (a_con = s->env->get_connectivity (s->env->cls,
 854                                              &aw->addr->peer)))
 855       {
 856         aw_min = aw;
 857         con_min = a_con;
 858         if (0 == con_min)
 859           break;
 860       }
 861     }
 862     update_active_address (s,
 863                            aw_min->addr,
 864                            &aw->addr->peer);
 865   }
 866   distribute_bandwidth_in_network (s,
 867                                    asi_best->network);
 868 }
 869
 870
 871 /**
 872  * The preferences for a peer in the problem changed.
 873  *
 874  * @param solver the solver handle
 875  * @param peer the peer to change the preference for
 876  * @param kind the kind to change the preference
 877  * @param pref_rel the normalized preference value for this kind over all clients
 878  */
 879 static void
 880 GAS_proportional_change_preference (void *solver,
 881                                     const struct GNUNET_PeerIdentity *peer,
 882                                     enum GNUNET_ATS_PreferenceKind kind,
 883                                     double pref_rel)
 884 {
 885   struct GAS_PROPORTIONAL_Handle *s = solver;
 886
 887   if (GNUNET_ATS_PREFERENCE_BANDWIDTH != kind)
 888     return; /* we do not care */
 889   distribute_bandwidth_in_network (s,
 890                                    NULL);
 891 }
 892
 893
 894 /**
 895  * Get application feedback for a peer
 896  *
 897  * @param solver the solver handle
 898  * @param application the application
 899  * @param peer the peer to change the preference for
 900  * @param scope the time interval for this feedback: [now - scope .. now]
 901  * @param kind the kind to change the preference
 902  * @param score the score
 903  */
 904 static void
 905 GAS_proportional_feedback (void *solver,
 906                            struct GNUNET_SERVER_Client *application,
 907                            const struct GNUNET_PeerIdentity *peer,
 908                            const struct GNUNET_TIME_Relative scope,
 909                            enum GNUNET_ATS_PreferenceKind kind,
 910                            double score)
 911 {
 912   /* Proportional does not care about feedback */
 913 }
 914
 915
 916 /**
 917  * Get the preferred address for a specific peer
 918  *
 919  * @param solver the solver handle
 920  * @param peer the identity of the peer
 921  */
 922 static void
 923 GAS_proportional_start_get_address (void *solver,
 924                                     const struct GNUNET_PeerIdentity *peer)
 925 {
 926   struct GAS_PROPORTIONAL_Handle *s = solver;
 927
 928   update_active_address (s,
 929                          get_active_address (s,
 930                                              peer),
 931                          peer);
 932 }
 933
 934
 935 /**
 936  * Stop notifying about address and bandwidth changes for this peer
 937  *
 938  * @param solver the solver handle
 939  * @param peer the peer
 940  */
 941 static void
 942 GAS_proportional_stop_get_address (void *solver,
 943                                    const struct GNUNET_PeerIdentity *peer)
 944 {
 945   struct GAS_PROPORTIONAL_Handle *s = solver;
 946   struct ATS_Address *cur;
 947   struct AddressWrapper *asi;
 948
 949   cur = get_active_address (s,
 950                             peer);
 951   if (NULL == cur)
 952     return;
 953   asi = cur->solver_information;
 954   distribute_bandwidth_in_network (s,
 955                                    asi->network);
 956 }
 957
 958
 959 /**
 960  * Start a bulk operation
 961  *
 962  * @param solver the solver
 963  */
 964 static void
 965 GAS_proportional_bulk_start (void *solver)
 966 {
 967   struct GAS_PROPORTIONAL_Handle *s = solver;
 968
 969   LOG (GNUNET_ERROR_TYPE_DEBUG,
 970        "Locking solver for bulk operation ...\n");
 971   GNUNET_assert (NULL != solver);
 972   s->bulk_lock++;
 973 }
 974
 975
 976 /**
 977  * Bulk operation done.
 978  *
 979  * @param solver our `struct GAS_PROPORTIONAL_Handle *`
 980  */
 981 static void
 982 GAS_proportional_bulk_stop (void *solver)
 983 {
 984   struct GAS_PROPORTIONAL_Handle *s = solver;
 985
 986   LOG (GNUNET_ERROR_TYPE_DEBUG,
 987        "Unlocking solver from bulk operation ...\n");
 988   if (s->bulk_lock < 1)
 989   {
 990     GNUNET_break(0);
 991     return;
 992   }
 993   s->bulk_lock--;
 994   if ( (0 == s->bulk_lock) &&
 995        (0 < s->bulk_requests) )
 996   {
 997     LOG (GNUNET_ERROR_TYPE_INFO,
 998          "No lock pending, recalculating\n");
 999     distribute_bandwidth_in_network (s,
1000                                      NULL);
1001     s->bulk_requests = 0;
1002   }
1003 }
1004
1005
1006 /**
1007  * Transport properties for this address have changed
1008  *
1009  * @param solver solver handle
1010  * @param address the address
1011  * @param type the ATSI type
1012  * @param abs_value the absolute value of the property
1013  * @param rel_value the normalized value
1014  */
1015 static void
1016 GAS_proportional_address_property_changed (void *solver,
1017                                            struct ATS_Address *address,
1018                                            enum GNUNET_ATS_Property type,
1019                                            uint32_t abs_value,
1020                                            double rel_value)
1021 {
1022   struct GAS_PROPORTIONAL_Handle *s = solver;
1023   struct AddressWrapper *asi = address->solver_information;
1024
1025   distribute_bandwidth_in_network (s,
1026                                    asi->network);
1027 }
1028
1029
1030 /**
1031  * Add a new single address to a network
1032  *
1033  * @param solver the solver Handle
1034  * @param address the address to add
1035  * @param network network type of this address
1036  */
1037 static void
1038 GAS_proportional_address_add (void *solver,
1039                               struct ATS_Address *address,
1040                               enum GNUNET_ATS_Network_Type network)
1041 {
1042   struct GAS_PROPORTIONAL_Handle *s = solver;
1043   struct Network *net;
1044   struct AddressWrapper *aw;
1045
1046   GNUNET_assert (network < s->env->network_count);
1047   net = &s->network_entries[network];
1048   net->total_addresses++;
1049
1050   aw = GNUNET_new (struct AddressWrapper);
1051   aw->addr = address;
1052   aw->network = net;
1053   address->solver_information = aw;
1054   GNUNET_CONTAINER_DLL_insert (net->head,
1055                                net->tail,
1056                                aw);
1057   GNUNET_STATISTICS_update (s->env->stats,
1058                             "# ATS addresses total",
1059                             1,
1060                             GNUNET_NO);
1061   GNUNET_STATISTICS_update (s->env->stats,
1062                             net->stat_total,
1063                             1,
1064                             GNUNET_NO);
1065   if (0 !=
1066       s->env->get_connectivity (s->env->cls,
1067                                 &address->peer))
1068   {
1069     /* This peer is requested, find best address */
1070     update_active_address (s,
1071                            get_active_address (s,
1072                                                &address->peer),
1073                            &address->peer);
1074   }
1075   LOG (GNUNET_ERROR_TYPE_INFO,
1076        "Added new address for `%s', now total %u and active %u addresses in network `%s'\n",
1077        GNUNET_i2s (&address->peer),
1078        net->total_addresses,
1079        net->active_addresses,
1080        net->desc);
1081 }
1082
1083
1084 /**
1085  * Remove an address from the solver. To do so, we:
1086  * - Removed it from specific network
1087  * - Decrease the number of total addresses
1088  * - If active:
1089  *   - decrease number of active addreses
1090  *   - update quotas
1091  *
1092  * @param solver the solver handle
1093  * @param address the address to remove
1094  */
1095 static void
1096 GAS_proportional_address_delete (void *solver,
1097                                  struct ATS_Address *address)
1098 {
1099   struct GAS_PROPORTIONAL_Handle *s = solver;
1100   struct AddressWrapper *aw = address->solver_information;
1101   struct Network *net = aw->network;
1102
1103   LOG (GNUNET_ERROR_TYPE_DEBUG,
1104        "Deleting %s address for peer `%s' from network `%s' (total: %u/active: %u)\n",
1105        (GNUNET_NO == address->active) ? "inactive" : "active",
1106        GNUNET_i2s (&address->peer),
1107        net->desc,
1108        net->total_addresses,
1109        net->active_addresses);
1110
1111   GNUNET_CONTAINER_DLL_remove (net->head,
1112                                net->tail,
1113                                aw);
1114   GNUNET_assert (net->total_addresses > 0);
1115   net->total_addresses--;
1116   GNUNET_STATISTICS_update (s->env->stats,
1117                             net->stat_total,
1118                             -1,
1119                             GNUNET_NO);
1120   if (GNUNET_YES == address->active)
1121   {
1122     /* Address was active, remove from network and update quotas */
1123     update_active_address (s,
1124                            address,
1125                            &address->peer);
1126     distribute_bandwidth_in_network (s, net);
1127   }
1128   GNUNET_free (aw);
1129   address->solver_information = NULL;
1130   LOG (GNUNET_ERROR_TYPE_DEBUG,
1131        "After deleting address now total %u and active %u addresses in network `%s'\n",
1132        net->total_addresses,
1133        net->active_addresses,
1134        net->desc);
1135 }
1136
1137
1138 /**
1139  * Function invoked when the plugin is loaded.
1140  *
1141  * @param[in,out] cls the `struct GNUNET_ATS_PluginEnvironment *` to use;
1142  *            modified to return the API functions (ugh).
1143  * @return the `struct GAS_PROPORTIONAL_Handle` to pass as a closure
1144  */
1145 void *
1146 libgnunet_plugin_ats_proportional_init (void *cls)
1147 {
1148   static struct GNUNET_ATS_SolverFunctions sf;
1149   struct GNUNET_ATS_PluginEnvironment *env = cls;
1150   struct GAS_PROPORTIONAL_Handle *s;
1151   struct Network * cur;
1152   float f_tmp;
1153   unsigned int c;
1154
1155   s = GNUNET_new (struct GAS_PROPORTIONAL_Handle);
1156   s->env = env;
1157   sf.cls = s;
1158   sf.s_add = &GAS_proportional_address_add;
1159   sf.s_address_update_property = &GAS_proportional_address_property_changed;
1160   sf.s_get = &GAS_proportional_start_get_address;
1161   sf.s_get_stop = &GAS_proportional_stop_get_address;
1162   sf.s_pref = &GAS_proportional_change_preference;
1163   sf.s_feedback = &GAS_proportional_feedback;
1164   sf.s_del = &GAS_proportional_address_delete;
1165   sf.s_bulk_start = &GAS_proportional_bulk_start;
1166   sf.s_bulk_stop = &GAS_proportional_bulk_stop;
1167   s->stability_factor = PROP_STABILITY_FACTOR;
1168   if (GNUNET_SYSERR !=
1169       GNUNET_CONFIGURATION_get_value_float (env->cfg,
1170                                             "ats",
1171                                             "PROP_STABILITY_FACTOR",
1172                                             &f_tmp))
1173   {
1174     if ((f_tmp < 1.0) || (f_tmp > 2.0))
1175     {
1176       LOG (GNUNET_ERROR_TYPE_ERROR,
1177            _("Invalid %s configuration %f \n"),
1178            "PROP_STABILITY_FACTOR",
1179            f_tmp);
1180     }
1181     else
1182     {
1183       s->stability_factor = f_tmp;
1184       LOG (GNUNET_ERROR_TYPE_INFO,
1185            "Using %s of %.3f\n",
1186            "PROP_STABILITY_FACTOR",
1187            f_tmp);
1188     }
1189   }
1190   s->prop_factor = PROPORTIONALITY_FACTOR;
1191   if (GNUNET_SYSERR !=
1192       GNUNET_CONFIGURATION_get_value_float (env->cfg,
1193                                             "ats",
1194                                             "PROP_PROPORTIONALITY_FACTOR",
1195                                             &f_tmp))
1196   {
1197     if (f_tmp < 1.0)
1198     {
1199       LOG (GNUNET_ERROR_TYPE_ERROR,
1200            _("Invalid %s configuration %f\n"),
1201            "PROP_PROPORTIONALITY_FACTOR",
1202            f_tmp);
1203     }
1204     else
1205     {
1206       s->prop_factor = f_tmp;
1207       LOG (GNUNET_ERROR_TYPE_INFO,
1208            "Using %s of %.3f\n",
1209            "PROP_PROPORTIONALITY_FACTOR",
1210            f_tmp);
1211     }
1212   }
1213
1214   s->network_entries = GNUNET_malloc (env->network_count *
1215                                       sizeof (struct Network));
1216   for (c = 0; c < env->network_count; c++)
1217   {
1218     cur = &s->network_entries[c];
1219     cur->type = c;
1220     cur->total_quota_in = env->in_quota[c];
1221     cur->total_quota_out = env->out_quota[c];
1222     cur->desc = GNUNET_ATS_print_network_type (c);
1223     GNUNET_asprintf (&cur->stat_total,
1224                      "# ATS addresses %s total",
1225                      cur->desc);
1226     GNUNET_asprintf (&cur->stat_active,
1227                      "# ATS active addresses %s total",
1228                      cur->desc);
1229     LOG (GNUNET_ERROR_TYPE_INFO,
1230          "Added network %u `%s' (%llu/%llu)\n",
1231          c,
1232          cur->desc,
1233          cur->total_quota_in,
1234          cur->total_quota_out);
1235   }
1236   return &sf;
1237 }
1238
1239
1240 /**
1241  * Function used to unload the plugin.
1242  *
1243  * @param cls return value from #libgnunet_plugin_ats_proportional_init()
1244  */
1245 void *
1246 libgnunet_plugin_ats_proportional_done (void *cls)
1247 {
1248   struct GNUNET_ATS_SolverFunctions *sf = cls;
1249   struct GAS_PROPORTIONAL_Handle *s = sf->cls;
1250   struct AddressWrapper *cur;
1251   struct AddressWrapper *next;
1252   unsigned int c;
1253
1254   for (c = 0; c < s->network_count; c++)
1255   {
1256     GNUNET_break (0 == s->network_entries[c].total_addresses);
1257     GNUNET_break (0 == s->network_entries[c].active_addresses);
1258     next = s->network_entries[c].head;
1259     while (NULL != (cur = next))
1260     {
1261       next = cur->next;
1262       GNUNET_CONTAINER_DLL_remove (s->network_entries[c].head,
1263                                    s->network_entries[c].tail,
1264                                    cur);
1265       GNUNET_free_non_null (cur->addr->solver_information);
1266       GNUNET_free(cur);
1267     }
1268     GNUNET_free (s->network_entries[c].stat_total);
1269     GNUNET_free (s->network_entries[c].stat_active);
1270   }
1271   GNUNET_break (0 == s->active_addresses);
1272   GNUNET_free (s->network_entries);
1273   GNUNET_free (s);
1274   return NULL;
1275 }
1276
1277
1278 /* end of plugin_ats_proportional.c */