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