src/testbed/testbed_api_topology.c

   1 /*
   2       This file is part of GNUnet
   3       (C) 2008--2012 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 testbed/testbed_api_topology.c
  23  * @brief topology-generation functions
  24  * @author Christian Grothoff
  25  */
  26 #include "platform.h"
  27 #include "gnunet_testbed_service.h"
  28 #include "testbed_api.h"
  29 #include "testbed_api_peers.h"
  30 #include "testbed_api_operations.h"
  31 #include "testbed_api_topology.h"
  32
  33 /**
  34  * Generic loggins shorthand
  35  */
  36 #define LOG(kind,...)                                           \
  37   GNUNET_log_from (kind, "testbed-api-topology", __VA_ARGS__)
  38
  39
  40 /**
  41  * Context information for topology operations
  42  */
  43 struct TopologyContext;
  44
  45
  46 /**
  47  * Representation of an overlay link
  48  */
  49 struct OverlayLink
  50 {
  51
  52   /**
  53    * An operation corresponding to this link
  54    */
  55   struct GNUNET_TESTBED_Operation *op;
  56
  57   /**
  58    * The topology context this link is a part of
  59    */
  60   struct TopologyContext *tc;
  61
  62   /**
  63    * position of peer A's handle in peers array
  64    */
  65   uint32_t A;
  66
  67   /**
  68    * position of peer B's handle in peers array
  69    */
  70   uint32_t B;
  71
  72 };
  73
  74
  75 /**
  76  * Context information for topology operations
  77  */
  78 struct TopologyContext
  79 {
  80   /**
  81    * The array of peers
  82    */
  83   struct GNUNET_TESTBED_Peer **peers;
  84
  85   /**
  86    * An array of links; this array is of size link_array_size
  87    */
  88   struct OverlayLink *link_array;
  89
  90   /**
  91    * The operation closure
  92    */
  93   void *op_cls;
  94
  95   /**
  96    * The number of peers
  97    */
  98   unsigned int num_peers;
  99
 100   /**
 101    * The size of the link array
 102    */
 103   unsigned int link_array_size;
 104
 105   /**
 106    * should the automatic retry be disabled
 107    */
 108   int disable_retry;
 109
 110 };
 111
 112
 113 /**
 114  * Callback to be called when an overlay_link operation complete
 115  *
 116  * @param cls element of the link_op array which points to the corresponding operation
 117  * @param op the operation that has been finished
 118  * @param emsg error message in case the operation has failed; will be NULL if
 119  *          operation has executed successfully.
 120  */
 121 static void
 122 overlay_link_completed (void *cls,
 123                         struct GNUNET_TESTBED_Operation *op,
 124                         const char *emsg)
 125 {
 126   struct OverlayLink *link = cls;
 127   struct TopologyContext *tc;
 128
 129   GNUNET_assert (op == link->op);
 130   GNUNET_TESTBED_operation_done (op);
 131   link->op = NULL;
 132   tc = link->tc;
 133   if ((NULL != emsg) && (GNUNET_NO == tc->disable_retry))
 134   {
 135     LOG (GNUNET_ERROR_TYPE_WARNING,
 136          "Error while establishing a link: %s -- Retrying\n", emsg);
 137     link->op =
 138         GNUNET_TESTBED_overlay_connect (tc->op_cls,
 139                                         &overlay_link_completed,
 140                                         link,
 141                                         tc->peers[link->A],
 142                                         tc->peers[link->B]);
 143     return;
 144   }
 145 }
 146
 147
 148
 149 /**
 150  * Function called when a overlay connect operation is ready
 151  *
 152  * @param cls the Topology context
 153  */
 154 static void
 155 opstart_overlay_configure_topology (void *cls)
 156 {
 157   struct TopologyContext *tc = cls;
 158   unsigned int p;
 159
 160   for (p = 0; p < tc->link_array_size; p++)
 161   {
 162     tc->link_array[p].op =
 163         GNUNET_TESTBED_overlay_connect (tc->op_cls, &overlay_link_completed,
 164                                         &tc->link_array[p],
 165                                         tc->peers[tc->link_array[p].A],
 166                                         tc->peers[tc->link_array[p].B]);
 167   }
 168 }
 169
 170
 171 /**
 172  * Callback which will be called when overlay connect operation is released
 173  *
 174  * @param cls the Topology context
 175  */
 176 static void
 177 oprelease_overlay_configure_topology (void *cls)
 178 {
 179   struct TopologyContext *tc = cls;
 180   unsigned int p;
 181
 182   if (NULL != tc->link_array)
 183   {
 184     for (p = 0; p < tc->link_array_size; p++)
 185       if (NULL != tc->link_array[p].op)
 186         GNUNET_TESTBED_operation_done (tc->link_array[p].op);
 187     GNUNET_free (tc->link_array);
 188   }
 189   GNUNET_free (tc);
 190 }
 191
 192
 193 /**
 194  * Generates line topology
 195  *
 196  * @param tc the topology context
 197  */
 198 static void
 199 gen_topo_line (struct TopologyContext *tc)
 200 {
 201   unsigned int cnt;
 202
 203   tc->link_array_size = tc->num_peers - 1;
 204   tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 205                                   tc->link_array_size);
 206   for (cnt=0; cnt < (tc->num_peers - 1); cnt++)
 207   {
 208     tc->link_array[cnt].A = cnt;
 209     tc->link_array[cnt].B = cnt + 1;
 210     tc->link_array[cnt].tc = tc;
 211   }
 212 }
 213
 214
 215 /**
 216  * Generates ring topology
 217  *
 218  * @param tc the topology context
 219  */
 220 static void
 221 gen_topo_ring (struct TopologyContext *tc)
 222 {
 223   gen_topo_line (tc);
 224   tc->link_array_size++;
 225   tc->link_array = GNUNET_realloc (tc->link_array,
 226                                    sizeof (struct OverlayLink) *
 227                                    tc->link_array_size);
 228   tc->link_array[tc->link_array_size - 1].op = NULL;
 229   tc->link_array[tc->link_array_size - 1].tc = tc;
 230   tc->link_array[tc->link_array_size - 1].A = tc->num_peers - 1;
 231   tc->link_array[tc->link_array_size - 1].B = 0;
 232 }
 233
 234
 235 /**
 236  * Returns the number of links that are required to generate a 2d torus for the
 237  * given number of peers. Also returns the arrangment (number of rows and the
 238  * length of each row)
 239  *
 240  * @param num_peers number of peers
 241  * @param rows number of rows in the 2d torus. Can be NULL
 242  * @param rows_len the length of each row. This array will be allocated
 243  *          fresh. The caller should free it. Can be NULL
 244  */
 245 unsigned int
 246 GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers,
 247                                    unsigned int *rows,
 248                                    unsigned int **rows_len)
 249 {
 250   double sq;
 251   unsigned int sq_floor;
 252   unsigned int _rows;
 253   unsigned int *_rows_len;
 254   unsigned int x;
 255   unsigned int y;
 256   unsigned int _num_peers;
 257   unsigned int cnt;
 258
 259   sq = sqrt (num_peers);
 260   sq = floor (sq);
 261   sq_floor = (unsigned int) sq;
 262   _rows = (sq_floor + 1);
 263   _rows_len = GNUNET_malloc (sizeof (unsigned int) * _rows);
 264   for (y = 0; y < _rows - 1; y++)
 265     _rows_len[y] = sq_floor;
 266   _num_peers = sq_floor * sq_floor;
 267   cnt = 2 * _num_peers;
 268   x = 0;
 269   y = 0;
 270   while (_num_peers < num_peers)
 271   {
 272     if (x < y)
 273       _rows_len[_rows - 1] = ++x;
 274     else
 275       _rows_len[y++]++;
 276     _num_peers++;
 277   }
 278   cnt += (x < 2) ? x : 2 * x;
 279   cnt += (y < 2) ? y : 2 * y;
 280   if (0 == _rows_len[_rows - 1])
 281     _rows--;
 282   if (NULL != rows)
 283     *rows = _rows;
 284   if (NULL != rows_len)
 285     *rows_len = _rows_len;
 286   else
 287     GNUNET_free (_rows_len);
 288   return cnt;
 289 }
 290
 291
 292 /**
 293  * Generates ring topology
 294  *
 295  * @param tc the topology context
 296  */
 297 static void
 298 gen_topo_2dtorus (struct TopologyContext *tc)
 299 {
 300   unsigned int rows;
 301   unsigned int *rows_len;
 302   unsigned int x;
 303   unsigned int y;
 304   unsigned int cnt;
 305   unsigned int offset;
 306
 307   tc->link_array_size = GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows,
 308                                                            &rows_len);
 309   tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 310                                   tc->link_array_size);
 311   cnt = 0;
 312   offset = 0;
 313   for (y = 0; y < rows; y++)
 314   {
 315     for (x = 0; x < rows_len[y] - 1; x++)
 316     {
 317       tc->link_array[cnt].tc = tc;
 318       tc->link_array[cnt].A = offset + x;
 319       tc->link_array[cnt].B = offset + x + 1;
 320       cnt++;
 321     }
 322     if (0 == x)
 323       break;
 324     tc->link_array[cnt].tc = tc;
 325     tc->link_array[cnt].A = offset + x;
 326     tc->link_array[cnt].B = offset;
 327     cnt++;
 328     offset += rows_len[y];
 329   }
 330   for (x = 0; x < rows_len[0]; x++)
 331   {
 332     offset = 0;
 333     for (y = 0; y < rows - 1; y++)
 334     {
 335       if (x == rows_len[y+1])
 336         break;
 337       GNUNET_assert (x < rows_len[y+1]);
 338       tc->link_array[cnt].tc= tc;
 339       tc->link_array[cnt].A = offset + x;
 340       offset += rows_len[y];
 341       tc->link_array[cnt].B = offset + x;
 342       cnt++;
 343     }
 344     if (0 == offset)
 345       break;
 346     tc->link_array[cnt].tc = tc;
 347     tc->link_array[cnt].A = offset + x;
 348     tc->link_array[cnt].B = x;
 349     cnt++;
 350   }
 351   GNUNET_assert (cnt == tc->link_array_size);
 352   GNUNET_free (rows_len);
 353 }
 354
 355
 356 /**
 357  * Generates ring topology
 358  *
 359  * @param tc the topology context
 360  * @param links the number of random links to establish
 361  * @param append GNUNET_YES to add links to existing link array; GNUNET_NO to
 362  *          create a new link array
 363  */
 364 static void
 365 gen_topo_random (struct TopologyContext *tc, unsigned int links, int append)
 366 {
 367   unsigned int cnt;
 368   unsigned int index;
 369   uint32_t A_rand;
 370   uint32_t B_rand;
 371
 372   if (GNUNET_YES == append)
 373   {
 374     GNUNET_assert ((0 < tc->link_array_size) && (NULL != tc->link_array));
 375     index = tc->link_array_size;
 376     tc->link_array_size += links;
 377     tc->link_array = GNUNET_realloc (tc->link_array,
 378                                    sizeof (struct OverlayLink) *
 379                                      tc->link_array_size);
 380   }
 381   else
 382   {
 383     GNUNET_assert ((0 == tc->link_array_size) && (NULL == tc->link_array));
 384     index = 0;
 385     tc->link_array_size = links;
 386     tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 387                                     tc->link_array_size);
 388   }
 389   for (cnt = 0; cnt < links; cnt++)
 390   {
 391     do {
 392       A_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 393                                          tc->num_peers);
 394       B_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK,
 395                                          tc->num_peers);
 396     } while (A_rand == B_rand);
 397     tc->link_array[index + cnt].op = NULL;
 398     tc->link_array[index + cnt].A = A_rand;
 399     tc->link_array[index + cnt].B = B_rand;
 400     tc->link_array[index + cnt].tc = tc;
 401   }
 402 }
 403
 404
 405 /**
 406  * Configure overall network topology to have a particular shape.
 407  *
 408  * @param op_cls closure argument to give with the operation event
 409  * @param num_peers number of peers in 'peers'
 410  * @param peers array of 'num_peers' with the peers to configure
 411  * @param topo desired underlay topology to use
 412  * @param ap topology-specific options
 413  * @return handle to the operation, NULL if configuring the topology
 414  *         is not allowed at this time
 415  */
 416 struct GNUNET_TESTBED_Operation *
 417 GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls,
 418                                                unsigned int num_peers,
 419                                                struct GNUNET_TESTBED_Peer
 420                                                **peers,
 421                                                enum
 422                                                GNUNET_TESTBED_TopologyOption
 423                                                topo, va_list ap)
 424 {
 425   GNUNET_break (0);
 426   return NULL;
 427 }
 428
 429
 430 /**
 431  * Configure overall network topology to have a particular shape.
 432  *
 433  * @param op_cls closure argument to give with the operation event
 434  * @param num_peers number of peers in 'peers'
 435  * @param peers array of 'num_peers' with the peers to configure
 436  * @param topo desired underlay topology to use
 437  * @param ... topology-specific options
 438  * @return handle to the operation, NULL if configuring the topology
 439  *         is not allowed at this time
 440  */
 441 struct GNUNET_TESTBED_Operation *
 442 GNUNET_TESTBED_underlay_configure_topology (void *op_cls,
 443                                             unsigned int num_peers,
 444                                             struct GNUNET_TESTBED_Peer **peers,
 445                                             enum GNUNET_TESTBED_TopologyOption
 446                                             topo, ...)
 447 {
 448   GNUNET_break (0);
 449   return NULL;
 450 }
 451
 452
 453 /**
 454  * All peers must have been started before calling this function.
 455  * This function then connects the given peers in the P2P overlay
 456  * using the given topology.
 457  *
 458  * @param op_cls closure argument to give with the operation event
 459  * @param num_peers number of peers in 'peers'
 460  * @param peers array of 'num_peers' with the peers to configure
 461  * @param topo desired underlay topology to use
 462  * @param va topology-specific options
 463  * @return handle to the operation, NULL if connecting these
 464  *         peers is fundamentally not possible at this time (peers
 465  *         not running or underlay disallows) or if num_peers is less than 2
 466  */
 467 struct GNUNET_TESTBED_Operation *
 468 GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
 469                                               unsigned int num_peers,
 470                                               struct GNUNET_TESTBED_Peer **peers,
 471                                               enum GNUNET_TESTBED_TopologyOption
 472                                               topo, va_list va)
 473 {
 474   struct TopologyContext *tc;
 475   struct GNUNET_TESTBED_Operation *op;
 476   struct GNUNET_TESTBED_Controller *c;
 477   enum GNUNET_TESTBED_TopologyOption secondary_option;
 478   unsigned int cnt;
 479
 480   if (num_peers < 2)
 481     return NULL;
 482   c = peers[0]->controller;
 483   tc = GNUNET_malloc (sizeof (struct TopologyContext));
 484   tc->peers = peers;
 485   tc->num_peers = num_peers;
 486   tc->op_cls = op_cls;
 487   switch (topo)
 488   {
 489   case GNUNET_TESTBED_TOPOLOGY_LINE:
 490     gen_topo_line (tc);
 491     break;
 492   case GNUNET_TESTBED_TOPOLOGY_RING:
 493     gen_topo_ring (tc);
 494     break;
 495   case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
 496     gen_topo_random (tc,
 497                      va_arg (va, unsigned int),
 498                      GNUNET_NO);
 499     break;
 500   case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
 501     gen_topo_ring (tc);
 502     gen_topo_random (tc,
 503                      va_arg (va, unsigned int),
 504                      GNUNET_YES);
 505     break;
 506   case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
 507     tc->link_array_size = num_peers * (num_peers - 1);
 508     tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) *
 509                                     tc->link_array_size);
 510     {
 511       unsigned int offset;
 512
 513       offset = 0;
 514       for (cnt=0; cnt < num_peers; cnt++)
 515       {
 516         unsigned int neighbour;
 517
 518         for (neighbour=0; neighbour < num_peers; neighbour++)
 519         {
 520           if (neighbour == cnt)
 521             continue;
 522           tc->link_array[offset].A = cnt;
 523           tc->link_array[offset].B = neighbour;
 524           tc->link_array[offset].tc = tc;
 525           offset++;
 526         }
 527       }
 528     }
 529     break;
 530   case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
 531     gen_topo_2dtorus (tc);
 532     break;
 533   default:
 534     GNUNET_break (0);
 535     GNUNET_free (tc);
 536     return NULL;
 537   }
 538   do
 539   {
 540     secondary_option = va_arg (va, enum GNUNET_TESTBED_TopologyOption);
 541     switch (secondary_option)
 542     {
 543     case GNUNET_TESTBED_TOPOLOGY_DISABLE_AUTO_RETRY:
 544       tc->disable_retry = GNUNET_YES;
 545       break;
 546     case GNUNET_TESTBED_TOPOLOGY_OPTION_END:
 547       break;
 548     default:
 549       GNUNET_break (0);         /* Should not use any other option apart from
 550                                    the ones handled here */
 551       GNUNET_free_non_null (tc->link_array);
 552       GNUNET_free (tc);
 553       return NULL;
 554     }
 555   } while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
 556   op = GNUNET_TESTBED_operation_create_ (tc,
 557                                          &opstart_overlay_configure_topology,
 558                                          &oprelease_overlay_configure_topology);
 559   GNUNET_TESTBED_operation_queue_insert_
 560       (c->opq_parallel_topology_config_operations, op);
 561   GNUNET_TESTBED_operation_begin_wait_ (op);
 562   return op;
 563 }
 564
 565
 566 /**
 567  * All peers must have been started before calling this function.
 568  * This function then connects the given peers in the P2P overlay
 569  * using the given topology.
 570  *
 571  * @param op_cls closure argument to give with the operation event
 572  * @param num_peers number of peers in 'peers'
 573  * @param peers array of 'num_peers' with the peers to configure
 574  * @param topo desired underlay topology to use
 575  * @param ... topology-specific options
 576  * @return handle to the operation, NULL if connecting these
 577  *         peers is fundamentally not possible at this time (peers
 578  *         not running or underlay disallows) or if num_peers is less than 2
 579  */
 580 struct GNUNET_TESTBED_Operation *
 581 GNUNET_TESTBED_overlay_configure_topology (void *op_cls, unsigned int num_peers,
 582                                            struct GNUNET_TESTBED_Peer **peers,
 583                                            enum GNUNET_TESTBED_TopologyOption
 584                                            topo, ...)
 585 {
 586   struct GNUNET_TESTBED_Operation *op;
 587   va_list vargs;
 588
 589   GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
 590   va_start (vargs, topo);
 591   op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
 592                                                      topo, vargs);
 593   va_end (vargs);
 594   return op;
 595 }
 596
 597 /* end of testbed_api_topology.c */