src/ats/gnunet-service-ats_addresses_simplistic.c

   1 /*
   2      This file is part of GNUnet.
   3      (C) 2011 Christian Grothoff (and other contributing authors)
   4
   5      GNUnet is free software; you can redistribute it and/or modify
   6      it under the terms of the GNU General Public License as published
   7      by the Free Software Foundation; either version 3, or (at your
   8      option) any later version.
   9
  10      GNUnet is distributed in the hope that it will be useful, but
  11      WITHOUT ANY WARRANTY; without even the implied warranty of
  12      MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13      General Public License for more details.
  14
  15      You should have received a copy of the GNU General Public License
  16      along with GNUnet; see the file COPYING.  If not, write to the
  17      Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  18      Boston, MA 02111-1307, USA.
  19 */
  20
  21 /**
  22  * @file ats/gnunet-service-ats_addresses_simplistic.h
  23  * @brief ats simplistic ressource assignment
  24  * @author Matthias Wachs
  25  * @author Christian Grothoff
  26  */
  27 #include "platform.h"
  28 #include "gnunet_util_lib.h"
  29 #include "gnunet-service-ats_addresses.h"
  30 #include "gnunet_statistics_service.h"
  31
  32 #define LOG(kind,...) GNUNET_log_from (kind, "ats-simplistic",__VA_ARGS__)
  33
  34 /**
  35  * ATS simplistic solver
  36  *
  37  * Assigns in and outbound bandwidth equally for all addresses in specific
  38  * network type (WAN, LAN) based on configured in and outbound quota for this
  39  * network.
  40  *
  41  * For each peer only a single is selected and marked as "active" in the address
  42  * struct.
  43  *
  44  * E.g.:
  45  *
  46  * You have the networks WAN and LAN and quotas
  47  * WAN_TOTAL_IN, WAN_TOTAL_OUT
  48  * LAN_TOTAL_IN, LAN_TOTAL_OUT
  49  *
  50  * If you have x addresses in the network segment LAN, the quotas are
  51  * QUOTA_PER_ADDRESS = LAN_TOTAL_OUT / x
  52  *
  53  * Quotas are automatically recalculated and reported back when addresses are
  54  * - requested
  55  *
  56  */
  57
  58
  59 /**
  60  * A handle for the simplistic solver
  61  */
  62 struct GAS_SIMPLISTIC_Handle
  63 {
  64   unsigned int total_addresses;
  65   unsigned int active_addresses;
  66
  67   struct Network *network_entries;
  68
  69   unsigned int networks;
  70   GAS_bandwidth_changed_cb bw_changed;
  71 };
  72
  73 struct Network
  74 {
  75   /**
  76    * ATS network type
  77    */
  78   unsigned int type;
  79
  80   /**
  81    * Network description
  82    */
  83   char *desc;
  84
  85   /**
  86    * Total inbound quota
  87    *
  88    */
  89   unsigned long long total_quota_in;
  90
  91   /**
  92    * Total outbound quota
  93    *
  94    */
  95   unsigned long long total_quota_out;
  96
  97   /**
  98    * Number of active addresses for this network
  99    */
 100   unsigned int active_addresses;
 101
 102   /**
 103    * Number of total addresses for this network
 104    */
 105   unsigned int total_addresses;
 106
 107   struct AddressWrapper *head;
 108   struct AddressWrapper *tail;
 109 };
 110
 111 struct AddressWrapper
 112 {
 113   struct AddressWrapper *next;
 114   struct AddressWrapper *prev;
 115
 116   struct ATS_Address *addr;
 117 };
 118
 119 /**
 120  * Init the simplistic problem solving component
 121  *
 122  * Quotas:
 123  * network[i] contains the network type as type GNUNET_ATS_NetworkType[i]
 124  * out_quota[i] contains outbound quota for network type i
 125  * in_quota[i] contains inbound quota for network type i
 126  *
 127  * Example
 128  * network = {GNUNET_ATS_NET_UNSPECIFIED, GNUNET_ATS_NET_LOOPBACK, GNUNET_ATS_NET_LAN, GNUNET_ATS_NET_WAN, GNUNET_ATS_NET_WLAN}
 129  * network[2]   == GNUNET_ATS_NET_LAN
 130  * out_quota[2] == 65353
 131  * in_quota[2]  == 65353
 132  *
 133  * @param cfg configuration handle
 134  * @param stats the GNUNET_STATISTICS handle
 135  * @param network array of GNUNET_ATS_NetworkType with length dest_length
 136  * @param out_quota array of outbound quotas
 137  * param in_quota array of outbound quota
 138  * @return handle for the solver on success, NULL on fail
 139  */
 140 void *
 141 GAS_simplistic_init (const struct GNUNET_CONFIGURATION_Handle *cfg,
 142                      const struct GNUNET_STATISTICS_Handle *stats,
 143                      int *network,
 144                      unsigned long long *out_quota,
 145                      unsigned long long *in_quota,
 146                      int dest_length,
 147                      GAS_bandwidth_changed_cb bw_changed_cb)
 148 {
 149   int c;
 150   struct GAS_SIMPLISTIC_Handle *s = GNUNET_malloc (sizeof (struct GAS_SIMPLISTIC_Handle));
 151   struct Network * cur;
 152   char * net_str[GNUNET_ATS_NetworkTypeCount] = {"UNSPECIFIED", "LOOPBACK", "LAN", "WAN", "WLAN"};
 153
 154   s->bw_changed = bw_changed_cb;
 155   s->networks = dest_length;
 156   s->network_entries = GNUNET_malloc (dest_length * sizeof (struct Network));
 157   s->active_addresses = 0;
 158   s->total_addresses = 0;
 159
 160   for (c = 0; c < dest_length; c++)
 161   {
 162       cur = &s->network_entries[c];
 163       cur->total_addresses = 0;
 164       cur->active_addresses = 0;
 165       cur->type = network[c];
 166       cur->total_quota_in = in_quota[c];
 167       cur->total_quota_out = out_quota[c];
 168       cur->desc = net_str[c];
 169   }
 170   return s;
 171 }
 172
 173
 174 /**
 175  * Shutdown the simplistic problem solving component
 176  *
 177  * @param solver the respective handle to shutdown
 178  */
 179 void
 180 GAS_simplistic_done (void *solver)
 181 {
 182   struct GAS_SIMPLISTIC_Handle *s = solver;
 183   struct AddressWrapper *cur;
 184   struct AddressWrapper *next;
 185   int c;
 186   GNUNET_assert (s != NULL);
 187
 188   for (c = 0; c < s->networks; c++)
 189   {
 190       if (s->network_entries[c].total_addresses > 0)
 191       {
 192         LOG (GNUNET_ERROR_TYPE_ERROR,
 193                     "Had %u addresses for network `%s' not deleted during shutdown\n",
 194                     s->network_entries[c].total_addresses,
 195                     s->network_entries[c].desc);
 196         GNUNET_break (0);
 197       }
 198
 199       if (s->network_entries[c].active_addresses > 0)
 200       {
 201         LOG (GNUNET_ERROR_TYPE_ERROR,
 202                     "Had %u active addresses for network `%s' not deleted during shutdown\n",
 203                     s->network_entries[c].active_addresses,
 204                     s->network_entries[c].desc);
 205         GNUNET_break (0);
 206       }
 207
 208       next = s->network_entries[c].head;
 209       while (NULL != (cur = next))
 210       {
 211           next = cur->next;
 212           GNUNET_CONTAINER_DLL_remove (s->network_entries[c].head,
 213                                        s->network_entries[c].tail,
 214                                        cur);
 215           GNUNET_free (cur);
 216
 217       }
 218   }
 219   if (s->total_addresses > 0)
 220   {
 221     LOG (GNUNET_ERROR_TYPE_ERROR,
 222                 "Had %u addresses not deleted during shutdown\n",
 223                 s->total_addresses);
 224     GNUNET_break (0);
 225   }
 226   if (s->active_addresses > 0)
 227   {
 228     LOG (GNUNET_ERROR_TYPE_ERROR,
 229                 "Had %u active addresses not deleted during shutdown\n",
 230                 s->active_addresses);
 231     GNUNET_break (0);
 232   }
 233
 234   GNUNET_free (s->network_entries);
 235   GNUNET_free (s);
 236 }
 237
 238 /**
 239  * Update the quotas for a network type
 240  *
 241  * @param network the network type to update
 242  * @param address_except address excluded from notifcation, since we suggest
 243  * this address
 244  */
 245
 246 static void
 247 update_quota_per_network (struct GAS_SIMPLISTIC_Handle *s,
 248                           struct Network *net,
 249                           struct ATS_Address *address_except)
 250 {
 251   unsigned long long quota_in = 0;
 252   unsigned long long quota_out = 0;
 253   struct AddressWrapper *cur;
 254
 255   LOG (GNUNET_ERROR_TYPE_DEBUG,
 256               "Recalculate quota for network type `%s' for %u addresses (in/out): %llu/%llu \n",
 257               net->desc, net->active_addresses, quota_in, quota_out);
 258
 259   if (net->active_addresses == 0)
 260     return; /* no addresses to update */
 261
 262   quota_in = net->total_quota_in / net->active_addresses;
 263   quota_out = net->total_quota_out / net->active_addresses;
 264
 265   LOG (GNUNET_ERROR_TYPE_DEBUG,
 266               "New per address quota for network type `%s' for %u addresses (in/out): %llu/%llu \n",
 267               net->desc, net->active_addresses, quota_in, quota_out);
 268
 269   cur = net->head;
 270   while (NULL != cur)
 271   {
 272       /* Compare to current bandwidth assigned */
 273       if ((quota_in != ntohl(cur->addr->assigned_bw_in.value__)) ||
 274           (quota_out != ntohl(cur->addr->assigned_bw_out.value__)))
 275       {
 276         cur->addr->assigned_bw_in.value__ = htonl (quota_in);
 277         cur->addr->assigned_bw_out.value__ = htonl (quota_out);
 278         /* Notify on change */
 279         if ((GNUNET_YES == cur->addr->active) && (cur->addr != address_except))
 280           s->bw_changed (cur->addr);
 281       }
 282       cur = cur->next;
 283   }
 284 }
 285
 286
 287 /**
 288  * Add a single address to the solve
 289  *
 290  * @param solver the solver Handle
 291  * @param addresses the address hashmap containing all addresses
 292  * @param address the address to add
 293  */
 294 void
 295 GAS_simplistic_address_add (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 296 {
 297   struct GAS_SIMPLISTIC_Handle *s = solver;
 298   struct Network *cur = NULL;
 299   struct AddressWrapper *aw = NULL;
 300   GNUNET_assert (NULL != s);
 301   int c;
 302   for (c = 0; c < s->networks; c++)
 303   {
 304       cur = &s->network_entries[c];
 305       if (address->atsp_network_type == cur->type)
 306           break;
 307   }
 308   if (NULL == cur)
 309   {
 310     GNUNET_break (0);
 311     return;
 312   }
 313
 314   aw = GNUNET_malloc (sizeof (struct AddressWrapper));
 315   aw->addr = address;
 316   GNUNET_CONTAINER_DLL_insert (cur->head, cur->tail, aw);
 317   cur->total_addresses ++;
 318   s->total_addresses ++;
 319   aw->addr->solver_information = cur;
 320
 321   LOG (GNUNET_ERROR_TYPE_DEBUG,
 322               "Adding new address for network type `%s' (now %u total)\n",
 323               cur->desc,
 324               cur->active_addresses);
 325 }
 326
 327
 328
 329 /**
 330  * Updates a single address in the solve
 331  *
 332  * @param solver the solver Handle
 333  * @param addresses the address hashmap containing all addresses
 334  * @param address the update address
 335  */
 336 void
 337 GAS_simplistic_address_update (void *solver, struct GNUNET_CONTAINER_MultiHashMap * addresses, struct ATS_Address *address)
 338 {
 339 #if 0
 340   struct GAS_SIMPLISTIC_Handle *s = solver;
 341   GNUNET_assert (NULL != s);
 342   int c;
 343   for (c = 0; c < s->networks; c++)
 344   {
 345       if (address->atsp_network_type == s->quota_net[c])
 346       {
 347           LOG (GNUNET_ERROR_TYPE_DEBUG,
 348                       "Updating address for network type %u (%u total)\n",
 349                       address->atsp_network_type,
 350                       s->active_addresses_per_net[c]);
 351           break;
 352       }
 353   }
 354
 355   /* Update quota for this network type */
 356   update_quota_per_network (s, c);
 357 #endif
 358 }
 359
 360
 361 /**
 362  * Remove an address from the solver
 363  *
 364  * @param solver the solver handle
 365  * @param addresses the address hashmap containing all addresses
 366  * @param address the address to remove
 367  * @param session_only delete only session not whole address
 368  */
 369 void
 370 GAS_simplistic_address_delete (void *solver,
 371     struct GNUNET_CONTAINER_MultiHashMap * addresses,
 372     struct ATS_Address *address, int session_only)
 373 {
 374   struct GAS_SIMPLISTIC_Handle *s = solver;
 375   struct Network *net;
 376   struct AddressWrapper *aw;
 377
 378   /* Remove an adress completely, we have to:
 379    * - Remove from specific network
 380    * - Decrease number of total addresses
 381    * - If active:
 382    *   - decrease number of active addreses
 383    *   - update quotas
 384    */
 385
 386   net = (struct Network *) address->solver_information;
 387
 388   if (GNUNET_NO == session_only)
 389   {
 390     LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting %s address %p for peer `%s' from network `%s' (total: %u/ active: %u)\n",
 391         (GNUNET_NO == address->active) ? "inactive" : "active",
 392         address, GNUNET_i2s (&address->peer),
 393         net->desc, net->total_addresses, net->active_addresses);
 394
 395     /* Remove address */
 396     if (net->total_addresses < 1)
 397       GNUNET_break (0);
 398     else
 399       net->total_addresses --;
 400     if (s->total_addresses < 1)
 401       GNUNET_break (0);
 402     else
 403       s->total_addresses --;
 404
 405     for (aw = net->head; NULL != aw; aw = aw->next)
 406     {
 407         if (aw->addr == address)
 408           break;
 409     }
 410     if (NULL == aw )
 411     {
 412         GNUNET_break (0);
 413         return;
 414     }
 415     GNUNET_CONTAINER_DLL_remove (net->head, net->tail, aw);
 416     GNUNET_free (aw);
 417   }
 418   else
 419   {
 420       /* Remove session only: remove if active and update */
 421       LOG (GNUNET_ERROR_TYPE_DEBUG, "Deleting %s session %p for peer `%s' from network `%s' (total: %u/ active: %u)\n",
 422           (GNUNET_NO == address->active) ? "inactive" : "active",
 423           address, GNUNET_i2s (&address->peer),
 424           net->desc, net->total_addresses, net->active_addresses);
 425   }
 426
 427   if (GNUNET_YES == address->active)
 428   {
 429       /* Address was active, remove from network and update quotas*/
 430       address->active = GNUNET_NO;
 431       if (net->active_addresses < 1)
 432         GNUNET_break (0);
 433       else
 434         net->active_addresses --;
 435       if (s->active_addresses < 1)
 436         GNUNET_break (0);
 437       else
 438         s->active_addresses --;
 439       update_quota_per_network (s, net, NULL);
 440   }
 441 }
 442
 443
 444
 445 /**
 446  * Find a "good" address to use for a peer.  If we already have an existing
 447  * address, we stick to it.  Otherwise, we pick by lowest distance and then
 448  * by lowest latency.
 449  *
 450  * @param cls the 'struct ATS_Address**' where we store the result
 451  * @param key unused
 452  * @param value another 'struct ATS_Address*' to consider using
 453  * @return GNUNET_OK (continue to iterate)
 454  */
 455 static int
 456 find_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
 457 {
 458   struct ATS_Address **previous_p = cls;
 459   struct ATS_Address *current = (struct ATS_Address *) value;
 460   struct ATS_Address *previous = *previous_p;
 461   struct GNUNET_TIME_Absolute now;
 462
 463   now = GNUNET_TIME_absolute_get();
 464
 465   if (current->blocked_until.abs_value == GNUNET_TIME_absolute_max (now, current->blocked_until).abs_value)
 466   {
 467     /* This address is blocked for suggestion */
 468     LOG (GNUNET_ERROR_TYPE_DEBUG,
 469                 "Address %p blocked for suggestion for %llu ms \n",
 470                 current,
 471                 GNUNET_TIME_absolute_get_difference(now, current->blocked_until).rel_value);
 472     return GNUNET_OK;
 473   }
 474
 475   if (NULL != previous)
 476   {
 477     if ((0 == strcmp (previous->plugin, "tcp")) &&
 478         (0 == strcmp (current->plugin, "tcp")))
 479     {
 480       if ((0 != previous->addr_len) &&
 481           (0 == current->addr_len))
 482       {
 483         /* saved address was an outbound address, but we have an inbound address */
 484         *previous_p = current;
 485         return GNUNET_OK;
 486       }
 487       if (0 == previous->addr_len)
 488       {
 489         /* saved address was an inbound address, so do not overwrite */
 490         return GNUNET_OK;
 491       }
 492     }
 493   }
 494
 495   if (NULL == previous)
 496   {
 497     *previous_p = current;
 498     return GNUNET_OK;
 499   }
 500   if ((ntohl (previous->assigned_bw_in.value__) == 0) &&
 501       (ntohl (current->assigned_bw_in.value__) > 0))
 502   {
 503     /* stick to existing connection */
 504     *previous_p = current;
 505     return GNUNET_OK;
 506   }
 507   if (previous->atsp_distance > current->atsp_distance)
 508   {
 509     /* user shorter distance */
 510     *previous_p = current;
 511     return GNUNET_OK;
 512   }
 513   if (previous->atsp_latency.rel_value > current->atsp_latency.rel_value)
 514   {
 515     /* user lower latency */
 516     *previous_p = current;
 517     return GNUNET_OK;
 518   }
 519   /* don't care */
 520   return GNUNET_OK;
 521 }
 522
 523 static int
 524 find_active_address_it (void *cls, const struct GNUNET_HashCode * key, void *value)
 525 {
 526   struct ATS_Address * dest = (struct ATS_Address *) (*(struct ATS_Address **)cls);
 527   struct ATS_Address * aa = (struct ATS_Address *) value;
 528
 529   if (GNUNET_YES == aa->active)
 530   {
 531       if (dest != NULL)
 532       {
 533           /* should never happen */
 534           LOG (GNUNET_ERROR_TYPE_ERROR, "Multiple active addresses for peer `%s'\n", GNUNET_i2s (&aa->peer));
 535           GNUNET_break (0);
 536           return GNUNET_NO;
 537       }
 538       dest = aa;
 539   }
 540   return GNUNET_OK;
 541 }
 542
 543 static struct ATS_Address *
 544 find_active_address (void *solver,
 545                      struct GNUNET_CONTAINER_MultiHashMap * addresses,
 546                      const struct GNUNET_PeerIdentity *peer)
 547 {
 548   struct ATS_Address * dest = NULL;
 549
 550   GNUNET_CONTAINER_multihashmap_get_multiple(addresses,
 551        &peer->hashPubKey,
 552        &find_active_address_it, &dest);
 553   return dest;
 554 }
 555
 556 /**
 557  * Get the prefered address for a specific peer
 558  *
 559  * @param solver the solver handle
 560  * @param addresses the address hashmap containing all addresses
 561  * @param peer the identity of the peer
 562  */
 563 const struct ATS_Address *
 564 GAS_simplistic_get_preferred_address (void *solver,
 565                                struct GNUNET_CONTAINER_MultiHashMap * addresses,
 566                                const struct GNUNET_PeerIdentity *peer)
 567 {
 568   struct GAS_SIMPLISTIC_Handle *s = solver;
 569   struct Network *net_prev;
 570   struct Network *net_cur;
 571   struct ATS_Address *cur;
 572   struct ATS_Address *prev;
 573
 574   GNUNET_assert (s != NULL);
 575   cur = NULL;
 576   /* Get address with: stick to current address, lower distance, lower latency */
 577   GNUNET_CONTAINER_multihashmap_get_multiple (addresses, &peer->hashPubKey,
 578                                               &find_address_it, &cur);
 579   if (NULL == cur)
 580   {
 581     LOG (GNUNET_ERROR_TYPE_DEBUG, "Cannot suggest address for peer `%s'\n", GNUNET_i2s (peer));
 582     return NULL;
 583   }
 584
 585   LOG (GNUNET_ERROR_TYPE_DEBUG, "Suggesting %s address %p for peer `%s'\n",
 586       (GNUNET_NO == cur->active) ? "inactive" : "active",
 587       cur, GNUNET_i2s (peer));
 588   net_cur = (struct Network *) cur->solver_information;
 589   if (GNUNET_YES == cur->active)
 590   {
 591       /* This address was selected previously, so no need to update quotas */
 592       return cur;
 593   }
 594
 595   /* This address was not active, so we have to:
 596    *
 597    * - mark previous active address as not active
 598    * - update quota for previous address network
 599    * - update quota for this address network
 600    */
 601
 602   prev = find_active_address (s, addresses, peer);
 603   if (NULL != prev)
 604   {
 605       net_prev = (struct Network *) prev->solver_information;
 606       prev->active = GNUNET_NO; /* No active any longer */
 607       prev->assigned_bw_in = GNUNET_BANDWIDTH_value_init (0); /* no bw assigned */
 608       prev->assigned_bw_out = GNUNET_BANDWIDTH_value_init (0); /* no bw assigned */
 609       s->bw_changed (prev); /* notify about bw change, REQUIRED? */
 610       if (net_prev->active_addresses < 1)
 611         GNUNET_break (0);
 612       else
 613         net_prev->active_addresses --;
 614       if (s->active_addresses < 1)
 615         GNUNET_break (0);
 616       else
 617         s->active_addresses --;
 618       update_quota_per_network (s, net_prev, NULL);
 619   }
 620
 621   cur->active = GNUNET_YES;
 622   s->active_addresses ++;
 623   net_cur->active_addresses ++;
 624   update_quota_per_network (s, net_cur, cur);
 625
 626   return cur;
 627 }
 628
 629
 630 /**
 631  * Changes the preferences for a peer in the problem
 632  *
 633  * @param solver the solver handle
 634  * @param peer the peer to change the preference for
 635  * @param kind the kind to change the preference
 636  * @param score the score
 637  */
 638 void
 639 GAS_simplistic_address_change_preference (void *solver,
 640                                    const struct GNUNET_PeerIdentity *peer,
 641                                    enum GNUNET_ATS_PreferenceKind kind,
 642                                    float score)
 643 {
 644   /* FIXME : implement this */
 645 }
 646
 647 /* end of gnunet-service-ats_addresses_simplistic.c */