GNUnet  0.19.2
testbed_api_topology.c
Go to the documentation of this file.
1 /*
2  This file is part of GNUnet
3  Copyright (C) 2008--2013 GNUnet e.V.
4 
5  GNUnet is free software: you can redistribute it and/or modify it
6  under the terms of the GNU Affero General Public License as published
7  by the Free Software Foundation, either version 3 of the License,
8  or (at your 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  Affero General Public License for more details.
14 
15  You should have received a copy of the GNU Affero General Public License
16  along with this program. If not, see <http://www.gnu.org/licenses/>.
17 
18  SPDX-License-Identifier: AGPL3.0-or-later
19  */
20 
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 
36 #define LOG(kind, ...) \
37  GNUNET_log_from (kind, "testbed-api-topology", __VA_ARGS__)
38 
39 
43 #define DEFAULT_RETRY_CNT 3
44 
45 
49 struct TopologyContext;
50 
51 
56 {
61 
66 
70  uint32_t A;
71 
75  uint32_t B;
76 };
77 
78 
83 {
87  uint32_t A;
88 
92  uint32_t B;
93 
97  uint32_t bandwidth;
98 
102  uint32_t latency;
103 
107  uint32_t loss;
108 };
109 
110 
112 {
117 
122 
126  struct OverlayLink *link;
127 };
128 
129 
134 {
139 
144 
148  void *op_cls;
149 
154 
158  void *comp_cb_cls;
159 
164 
169 
173  unsigned int retry_cnt;
174 
178  unsigned int nlinks;
179 
183  unsigned int ncompleted;
184 
188  unsigned int nsuccess;
189 
193  unsigned int nfailures;
194 };
195 
196 
201 {
206 };
207 
208 
213 {
217  enum
218  {
223 
228  } type;
229 
230  union
231  {
236 
241  } u;
242 
246  unsigned int num_peers;
247 
251  unsigned int link_array_size;
252 };
253 
254 
259 static const char *topology_strings[] = {
264  "CLIQUE",
265 
266  /*
267  * Small-world network (2d torus plus random links). Followed
268  * by the number of random links to add (unsigned int).
269  */
270  "SMALL_WORLD",
271 
276  "SMALL_WORLD_RING",
277 
281  "RING",
282 
286  "STAR",
287 
291  "2D_TORUS",
292 
297  "RANDOM", // GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI
298 
304  "INTERNAT",
305 
311  "SCALE_FREE",
312 
316  "LINE",
317 
321  "FROM_FILE",
322 
326  "NONE",
327 
331  NULL
332 };
333 
334 
343 static void
346  const char *emsg)
347 {
348  struct OverlayLink *link = cls;
349  struct TopologyContext *tc;
350  struct TopologyContextOverlay *overlay;
351  struct RetryListEntry *retry_entry;
352 
353  GNUNET_assert (op == link->op);
355  link->op = NULL;
356  tc = link->tc;
357  GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
358  overlay = &tc->u.overlay;
359  if (NULL != emsg)
360  {
361  overlay->nfailures++;
362  if (0 != overlay->retry_cnt)
363  {
365  "Error while establishing a link: %s -- Retrying\n",
366  emsg);
368  retry_entry->link = link;
370  overlay->rl_tail,
371  retry_entry);
372  }
373  }
374  else
375  overlay->nsuccess++;
376  overlay->ncompleted++;
377  if (overlay->ncompleted < overlay->nlinks)
378  return;
379  if ((0 != overlay->retry_cnt) && (NULL != overlay->rl_head))
380  {
381  overlay->retry_cnt--;
382  overlay->ncompleted = 0;
383  overlay->nlinks = 0;
384  while (NULL != (retry_entry = overlay->rl_head))
385  {
386  link = retry_entry->link;
387  link->op =
390  link,
391  overlay->peers[link->A],
392  overlay->peers[link->B]);
393  overlay->nlinks++;
395  overlay->rl_tail,
396  retry_entry);
398  }
399  return;
400  }
401  if (NULL != overlay->comp_cb)
402  {
403  overlay->comp_cb (overlay->comp_cb_cls,
404  overlay->nsuccess,
405  overlay->nfailures);
406  }
407 }
408 
409 
415 static void
417 {
418  struct TopologyContext *tc = cls;
419  struct TopologyContextOverlay *overlay;
420  unsigned int p;
421 
422  GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
423  overlay = &tc->u.overlay;
424  overlay->nlinks = tc->link_array_size;
425  for (p = 0; p < tc->link_array_size; p++)
426  {
427  overlay->link_array[p].op =
430  &overlay->link_array[p],
431  overlay->peers[overlay->link_array[p].A],
432  overlay->peers[overlay->link_array[p].B]);
433  }
434 }
435 
436 
442 static void
444 {
445  struct TopologyContext *tc = cls;
446  struct TopologyContextOverlay *overlay;
447  struct RetryListEntry *retry_entry;
448  unsigned int p;
449 
450  GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type);
451  overlay = &tc->u.overlay;
452  while (NULL != (retry_entry = overlay->rl_head))
453  {
454  GNUNET_CONTAINER_DLL_remove (overlay->rl_head, overlay->rl_tail,
455  retry_entry);
457  }
458  if (NULL != overlay->link_array)
459  {
460  for (p = 0; p < tc->link_array_size; p++)
461  if (NULL != overlay->link_array[p].op)
463  GNUNET_free (overlay->link_array);
464  }
465  GNUNET_free (tc);
466 }
467 
468 
478 static void
479 make_link (unsigned int offset,
480  uint32_t A,
481  uint32_t B,
482  struct TopologyContext *tc)
483 {
484  GNUNET_assert (A != B);
485  switch (tc->type)
486  {
487  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
488  {
489  struct TopologyContextOverlay *overlay;
490  struct OverlayLink *olink;
491 
492  overlay = &tc->u.overlay;
493  GNUNET_assert (offset < tc->link_array_size);
494  olink = &overlay->link_array[offset];
495  LOG (GNUNET_ERROR_TYPE_DEBUG, "Connecting peer %u to %u\n", B, A);
496  olink->A = A;
497  olink->B = B;
498  olink->op = NULL;
499  olink->tc = tc;
500  }
501  break;
502 
503  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
504  {
505  struct TopologyContextUnderlay *underlay;
506  struct UnderlayLink *ulink;
507 
508  underlay = &tc->u.underlay;
509  GNUNET_assert (offset < tc->link_array_size);
510  ulink = &underlay->link_array[offset];
511  ulink->A = A;
512  ulink->B = B;
513  }
514  break;
515  }
516 }
517 
518 
524 static void
526 {
527  unsigned int cnt;
528 
529  tc->link_array_size = tc->num_peers - 1;
530  switch (tc->type)
531  {
532  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
533  {
534  struct TopologyContextOverlay *overlay;
535 
536  overlay = &tc->u.overlay;
537  overlay->link_array =
538  GNUNET_new_array (tc->link_array_size,
539  struct OverlayLink);
540  }
541  break;
542 
543  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
544  {
545  struct TopologyContextUnderlay *underlay;
546 
547  underlay = &tc->u.underlay;
548  underlay->link_array =
549  GNUNET_new_array (tc->link_array_size,
550  struct UnderlayLink);
551  }
552  break;
553  }
554  for (cnt = 0; cnt < (tc->link_array_size); cnt++)
555  make_link (cnt, cnt, cnt + 1, tc);
556 }
557 
558 
564 static void
566 {
567  unsigned int cnt;
568 
569  tc->link_array_size = tc->num_peers - 1;
570  switch (tc->type)
571  {
572  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
573  {
574  struct TopologyContextOverlay *overlay;
575 
576  overlay = &tc->u.overlay;
577  overlay->link_array =
578  GNUNET_new_array (tc->link_array_size,
579  struct OverlayLink);
580  }
581  break;
582 
583  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
584  {
585  struct TopologyContextUnderlay *underlay;
586 
587  underlay = &tc->u.underlay;
588  underlay->link_array =
589  GNUNET_new_array (tc->link_array_size,
590  struct UnderlayLink);
591  }
592  break;
593  }
594  for (cnt = tc->link_array_size; cnt; cnt--)
595  make_link (cnt - 1,
596  0,
597  cnt,
598  tc);
599 }
600 
601 
607 static void
609 {
610  gen_topo_line (tc);
611  tc->link_array_size++;
612  switch (tc->type)
613  {
614  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
615  {
616  struct TopologyContextOverlay *overlay;
617 
618  overlay = &tc->u.overlay;
619  overlay->link_array =
620  GNUNET_realloc (overlay->link_array, sizeof(struct OverlayLink)
621  * tc->link_array_size);
622  }
623  break;
624 
625  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
626  {
627  struct TopologyContextUnderlay *underlay;
628 
629  underlay = &tc->u.underlay;
630  underlay->link_array =
631  GNUNET_realloc (underlay->link_array, sizeof(struct UnderlayLink)
632  * tc->link_array_size);
633  }
634  break;
635  }
636  make_link (tc->link_array_size - 1, tc->num_peers - 1, 0, tc);
637 }
638 
639 
640 unsigned int
641 GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers, unsigned int *rows,
642  unsigned int **rows_len)
643 {
644  double sq;
645  unsigned int sq_floor;
646  unsigned int _rows;
647  unsigned int *_rows_len;
648  unsigned int x;
649  unsigned int y;
650  unsigned int _num_peers;
651  unsigned int cnt;
652 
653  sq = sqrt (num_peers);
654  sq = floor (sq);
655  sq_floor = (unsigned int) sq;
656  _rows = (sq_floor + 1);
657  _rows_len = GNUNET_malloc (sizeof(unsigned int) * _rows);
658  for (y = 0; y < _rows - 1; y++)
659  _rows_len[y] = sq_floor;
660  _num_peers = sq_floor * sq_floor;
661  cnt = (_num_peers < 2) ? _num_peers : 2 * _num_peers;
662  x = 0;
663  y = 0;
664  while (_num_peers < num_peers)
665  {
666  if (x < y)
667  _rows_len[_rows - 1] = ++x;
668  else
669  _rows_len[y++]++;
670  _num_peers++;
671  }
672  cnt += (x < 2) ? x : 2 * x;
673  cnt += (y < 2) ? y : 2 * y;
674  if (0 == _rows_len[_rows - 1])
675  _rows--;
676  if (NULL != rows)
677  *rows = _rows;
678  if (NULL != rows_len)
679  *rows_len = _rows_len;
680  else
681  GNUNET_free (_rows_len);
682  return cnt;
683 }
684 
685 
691 static void
693 {
694  unsigned int rows;
695  unsigned int *rows_len;
696  unsigned int x;
697  unsigned int y;
698  unsigned int cnt;
699  unsigned int offset;
700 
701  tc->link_array_size =
702  GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows, &rows_len);
703  switch (tc->type)
704  {
705  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
706  {
707  struct TopologyContextOverlay *overlay;
708 
709  overlay = &tc->u.overlay;
710  overlay->link_array =
711  GNUNET_malloc (sizeof(struct OverlayLink) * tc->link_array_size);
712  }
713  break;
714 
715  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
716  {
717  struct TopologyContextUnderlay *underlay;
718 
719  underlay = &tc->u.underlay;
720  underlay->link_array =
721  GNUNET_malloc (sizeof(struct UnderlayLink) * tc->link_array_size);
722  break;
723  }
724  }
725  cnt = 0;
726  offset = 0;
727  for (y = 0; y < rows; y++)
728  {
729  for (x = 0; x < rows_len[y] - 1; x++)
730  {
731  make_link (cnt, offset + x, offset + x + 1, tc);
732  cnt++;
733  }
734  if (0 == x)
735  break;
736  make_link (cnt, offset + x, offset, tc);
737  cnt++;
738  offset += rows_len[y];
739  }
740  for (x = 0; x < rows_len[0]; x++)
741  {
742  offset = 0;
743  for (y = 0; y < rows - 1; y++)
744  {
745  if (x >= rows_len[y + 1])
746  break;
747  GNUNET_assert (x < rows_len[y + 1]);
748  make_link (cnt, offset + x, offset + rows_len[y] + x, tc);
749  offset += rows_len[y];
750  cnt++;
751  }
752  if (0 == offset)
753  break;
754  make_link (cnt, offset + x, x, tc);
755  cnt++;
756  }
757  GNUNET_assert (cnt == tc->link_array_size);
758  GNUNET_free (rows_len);
759 }
760 
761 
770 static void
772  unsigned int links,
773  int append)
774 {
775  unsigned int cnt;
776  unsigned int index;
777  uint32_t A_rand;
778  uint32_t B_rand;
779 
780  if (1 == tc->num_peers)
781  return;
782  if (GNUNET_YES == append)
783  {
784  index = tc->link_array_size;
785  tc->link_array_size += links;
786  }
787  else
788  {
789  index = 0;
790  tc->link_array_size = links;
791  }
792  switch (tc->type)
793  {
794  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
795  {
796  struct TopologyContextOverlay *overlay;
797 
798  overlay = &tc->u.overlay;
799  if (GNUNET_YES != append)
800  {
801  GNUNET_assert (NULL == overlay->link_array);
802  overlay->link_array =
803  GNUNET_malloc (sizeof(struct OverlayLink) * tc->link_array_size);
804  break;
805  }
806  GNUNET_assert ((0 < tc->link_array_size) && (NULL !=
807  overlay->link_array));
808  overlay->link_array =
809  GNUNET_realloc (overlay->link_array,
810  sizeof(struct OverlayLink) * tc->link_array_size);
811  break;
812  }
813 
814  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
815  {
816  struct TopologyContextUnderlay *underlay;
817 
818  underlay = &tc->u.underlay;
819  if (GNUNET_YES != append)
820  {
821  GNUNET_assert (NULL == underlay->link_array);
822  underlay->link_array =
823  GNUNET_malloc (sizeof(struct UnderlayLink) * tc->link_array_size);
824  break;
825  }
826  GNUNET_assert ((0 < tc->link_array_size) && (NULL !=
827  underlay->link_array));
828  underlay->link_array =
829  GNUNET_realloc (underlay->link_array,
830  sizeof(struct UnderlayLink) * tc->link_array_size);
831  break;
832  }
833  }
834  for (cnt = 0; cnt < links; cnt++)
835  {
836  do
837  {
838  A_rand =
840  B_rand =
842  }
843  while (A_rand == B_rand);
844  make_link (index + cnt, A_rand, B_rand, tc);
845  }
846 }
847 
848 
859 static void
861  uint16_t cap,
862  uint8_t m)
863 {
864  unsigned int *deg;
865  unsigned int *etab;
866  unsigned int *used;
867  unsigned int etaboff;
868  unsigned int cnt;
869  unsigned int cnt2;
870  unsigned int peer;
871  unsigned int random_peer;
872  unsigned int links;
873  unsigned int off;
874  unsigned int redo_threshold;
875 
876  etaboff = 0;
877  tc->link_array_size = tc->num_peers * m;
878  switch (tc->type)
879  {
880  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
881  {
882  struct TopologyContextOverlay *overlay;
883 
884  overlay = &tc->u.overlay;
885  overlay->link_array = GNUNET_malloc_large (sizeof(struct OverlayLink)
886  * tc->link_array_size);
887  }
888  break;
889 
890  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
891  {
892  struct TopologyContextUnderlay *underlay;
893 
894  underlay = &tc->u.underlay;
895  underlay->link_array = GNUNET_malloc_large (sizeof(struct UnderlayLink)
896  * tc->link_array_size);
897  }
898  break;
899  }
900  etab = GNUNET_malloc_large (sizeof(unsigned int) * 2 * tc->link_array_size);
901  deg = GNUNET_malloc (sizeof(unsigned int) * tc->num_peers);
902  used = GNUNET_malloc (sizeof(unsigned int) * m);
903  /* start by connecting peer 1 to peer 0 */
904  make_link (0, 0, 1, tc);
905  deg[0]++;
906  deg[1]++;
907  etab[etaboff++] = 0;
908  etab[etaboff++] = 1;
909  links = 1;
910  for (peer = 2; peer < tc->num_peers; peer++)
911  {
912  if (cap < deg[peer])
913  continue;
914  for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
915  {
916  redo_threshold = 0;
917 redo:
919  random_peer = etab[off];
920  if (cap < deg[random_peer])
921  {
922  if (++redo_threshold > GNUNET_MAX (1, cap / 2))
923  {
924  redo_threshold = 0;
925  off = 0;
926  for (cnt2 = 0; cnt2 < etaboff; cnt2++)
927  {
928  if (random_peer == etab[cnt2])
929  {
930  off++;
931  continue;
932  }
933  etab[cnt2 - off] = etab[cnt2];
934  }
935  etaboff -= off;
936  }
937  goto redo;
938  }
939  for (cnt2 = 0; cnt2 < cnt; cnt2++)
940  if (random_peer == used[cnt2])
941  goto redo;
942  make_link (links + cnt, random_peer, peer, tc);
943  deg[random_peer]++;
944  deg[peer]++;
945  used[cnt] = random_peer;
946  }
947  for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++)
948  {
949  etab[etaboff++] = used[cnt];
950  etab[etaboff++] = peer;
951  }
952  links += GNUNET_MIN (peer, m);
953  }
954  GNUNET_free (etab);
955  GNUNET_free (used);
956  GNUNET_free (deg);
957  GNUNET_assert (links <= tc->link_array_size);
958  tc->link_array_size = links;
959  switch (tc->type)
960  {
961  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
962  {
963  struct TopologyContextOverlay *overlay;
964 
965  overlay = &tc->u.overlay;
966  overlay->link_array =
967  GNUNET_realloc (overlay->link_array, sizeof(struct OverlayLink)
968  * tc->link_array_size);
969  }
970  break;
971 
972  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
973  {
974  struct TopologyContextUnderlay *underlay;
975 
976  underlay = &tc->u.underlay;
977  underlay->link_array =
978  GNUNET_realloc (underlay->link_array, sizeof(struct UnderlayLink)
979  * tc->link_array_size);
980  }
981  break;
982  }
983 }
984 
985 
992 static void
994  const char *filename)
995 {
996  char *data;
997  char *end;
998  char *buf;
999  uint64_t fs;
1000  uint64_t offset;
1001  unsigned long int peer_id;
1002  unsigned long int other_peer_id;
1003  enum ParseState
1004  {
1008  PEER_INDEX,
1009 
1013  OTHER_PEER_INDEX,
1014  } state;
1015  int status;
1016 
1019  {
1021  _ ("Topology file %s not found\n"),
1022  filename);
1023  return;
1024  }
1025  if (GNUNET_OK !=
1027  {
1029  _ ("Topology file %s has no data\n"),
1030  filename);
1031  return;
1032  }
1033  data = GNUNET_malloc (fs);
1034  if (fs != GNUNET_DISK_fn_read (filename, data, fs))
1035  {
1037  _ ("Topology file %s cannot be read\n"),
1038  filename);
1039  goto _exit;
1040  }
1041 
1042  offset = 0;
1043  peer_id = 0;
1044  state = PEER_INDEX;
1045  while (offset < fs)
1046  {
1047  if (0 != isspace ((unsigned char) data[offset]))
1048  {
1049  offset++;
1050  continue;
1051  }
1052  switch (state)
1053  {
1054  case PEER_INDEX:
1055  buf = strchr (&data[offset], ':');
1056  if (NULL == buf)
1057  {
1059  _ ("Failed to read peer index from toology file: %s"), filename);
1060  goto _exit;
1061  }
1062  *buf = '\0';
1063  errno = 0;
1064  peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
1065  if (0 != errno)
1066  {
1068  _ ("Value in given topology file: %s out of range\n"), filename);
1069  goto _exit;
1070  }
1071  if (&data[offset] == end)
1072  {
1074  _ ("Failed to read peer index from topology file: %s"), filename);
1075  goto _exit;
1076  }
1077  if (tc->num_peers <= peer_id)
1078  {
1080  _ ("Topology file needs more peers than given ones\n"));
1081  goto _exit;
1082  }
1083  state = OTHER_PEER_INDEX;
1084  offset += ((unsigned int) (buf - &data[offset])) + 1;
1085  break;
1086 
1087  case OTHER_PEER_INDEX:
1088  errno = 0;
1089  other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10);
1090  if (0 != errno)
1091  {
1093  _ ("Value in given topology file: %s out of range\n"), filename);
1094  goto _exit;
1095  }
1096  if (&data[offset] == end)
1097  {
1099  _ ("Failed to read peer index from topology file: %s"), filename);
1100  goto _exit;
1101  }
1102  if (tc->num_peers <= other_peer_id)
1103  {
1105  _ ("Topology file needs more peers than given ones\n"));
1106  goto _exit;
1107  }
1108  if (peer_id != other_peer_id)
1109  {
1110  tc->link_array_size++;
1111  switch (tc->type)
1112  {
1113  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1114  {
1115  struct TopologyContextOverlay *overlay;
1116 
1117  overlay = &tc->u.overlay;
1118  overlay->link_array =
1119  GNUNET_realloc (overlay->link_array,
1120  sizeof(struct OverlayLink) * tc->link_array_size);
1121  }
1122  break;
1123 
1124  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1125  {
1126  struct TopologyContextUnderlay *underlay;
1127 
1128  underlay = &tc->u.underlay;
1129  underlay->link_array =
1130  GNUNET_realloc (underlay->link_array,
1131  sizeof(struct UnderlayLink)
1132  * tc->link_array_size);
1133  }
1134  break;
1135  }
1136  offset += end - &data[offset];
1137  make_link (tc->link_array_size - 1, peer_id, other_peer_id, tc);
1138  }
1139  else
1141  _ ("Ignoring to connect peer %lu to peer %lu\n"),
1142  peer_id,
1143  other_peer_id);
1144  while (('\n' != data[offset]) && ('|' != data[offset]) && (offset < fs))
1145  offset++;
1146  if ((offset < fs) &&
1147  ('\n' == data[offset]))
1148  state = PEER_INDEX;
1149  else if ((offset < fs) &&
1150  ('|' == data[offset]))
1151  {
1152  state = OTHER_PEER_INDEX;
1153  offset++;
1154  }
1155  break;
1156  }
1157  }
1158  status = GNUNET_OK;
1159 
1160 _exit:
1161  GNUNET_free (data);
1162  if (GNUNET_OK != status)
1163  {
1165  "Removing link data read from the file\n");
1166  tc->link_array_size = 0;
1167  switch (tc->type)
1168  {
1169  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1170  {
1171  struct TopologyContextOverlay *overlay;
1172 
1173  overlay = &tc->u.overlay;
1174  GNUNET_free (overlay->link_array);
1175  overlay->link_array = NULL;
1176  }
1177  break;
1178 
1179  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1180  {
1181  struct TopologyContextUnderlay *underlay;
1182 
1183  underlay = &tc->u.underlay;
1184  GNUNET_free (underlay->link_array);
1185  underlay->link_array = NULL;
1186  }
1187  break;
1188  }
1189  }
1190 }
1191 
1192 
1198 static void
1200 {
1201  unsigned int cnt;
1202  unsigned int offset;
1203  unsigned int neighbour;
1204 
1205  tc->link_array_size = tc->num_peers * (tc->num_peers - 1);
1206  switch (tc->type)
1207  {
1208  case TOPOLOGYCONTEXT_TYPE_OVERLAY:
1209  {
1210  struct TopologyContextOverlay *overlay;
1211 
1212  overlay = &tc->u.overlay;
1213  overlay->link_array = GNUNET_new_array (tc->link_array_size,
1214  struct OverlayLink);
1215  }
1216  break;
1217 
1218  case TOPOLOGYCONTEXT_TYPE_UNDERLAY:
1219  {
1220  struct TopologyContextUnderlay *underlay;
1221 
1222  underlay = &tc->u.underlay;
1223  underlay->link_array = GNUNET_new_array (tc->link_array_size,
1224  struct UnderlayLink);
1225  }
1226  }
1227  offset = 0;
1228  for (cnt = 0; cnt < tc->num_peers; cnt++)
1229  {
1230  for (neighbour = 0; neighbour < tc->num_peers; neighbour++)
1231  {
1232  if (neighbour == cnt)
1233  continue;
1234  make_link (offset, cnt, neighbour, tc);
1235  offset++;
1236  }
1237  }
1238 }
1239 
1240 
1241 struct GNUNET_TESTBED_Operation *
1243  unsigned int num_peers,
1244  struct GNUNET_TESTBED_Peer
1245  **peers,
1246  enum
1248  topo, va_list ap)
1249 {
1250  GNUNET_break (0);
1251  return NULL;
1252 }
1253 
1254 
1255 struct GNUNET_TESTBED_Operation *
1257  unsigned int num_peers,
1258  struct GNUNET_TESTBED_Peer **peers,
1260  topo, ...)
1261 {
1262  GNUNET_break (0);
1263  return NULL;
1264 }
1265 
1266 
1267 struct GNUNET_TESTBED_Operation *
1269  unsigned int num_peers,
1270  struct GNUNET_TESTBED_Peer **peers,
1271  unsigned int *max_connections,
1273  comp_cb,
1274  void *comp_cb_cls,
1276  topo,
1277  va_list va)
1278 {
1279  struct TopologyContext *tc;
1280  struct TopologyContextOverlay *overlay;
1281  struct GNUNET_TESTBED_Operation *op;
1282  struct GNUNET_TESTBED_Controller *c;
1283  enum GNUNET_TESTBED_TopologyOption secondary_option;
1284 
1285  if (num_peers < 2)
1286  return NULL;
1287  c = peers[0]->controller;
1288  tc = GNUNET_new (struct TopologyContext);
1289  tc->type = TOPOLOGYCONTEXT_TYPE_OVERLAY;
1290  overlay = &tc->u.overlay;
1291  overlay->peers = peers;
1292  tc->num_peers = num_peers;
1293  overlay->op_cls = op_cls;
1294  overlay->retry_cnt = DEFAULT_RETRY_CNT;
1295  overlay->comp_cb = comp_cb;
1296  overlay->comp_cb_cls = comp_cb_cls;
1297  switch (topo)
1298  {
1300  gen_topo_line (tc);
1301  break;
1302 
1304  gen_topo_star (tc);
1305  break;
1306 
1308  gen_topo_ring (tc);
1309  break;
1310 
1312  gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_NO);
1313  break;
1314 
1316  gen_topo_ring (tc);
1317  gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
1318  break;
1319 
1321  gen_topo_clique (tc);
1322  break;
1323 
1325  gen_topo_2dtorus (tc);
1326  break;
1327 
1329  gen_topo_2dtorus (tc);
1330  gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
1331 
1332  break;
1333 
1335  {
1336  uint16_t cap;
1337  uint8_t m;
1338 
1339  cap = (uint16_t) va_arg (va, unsigned int);
1340  m = (uint8_t) va_arg (va, unsigned int);
1341  gen_topo_scale_free (tc, cap, m);
1342  }
1343  break;
1344 
1346  {
1347  const char *filename;
1348 
1349  filename = va_arg (va, const char *);
1350 
1351  GNUNET_assert (NULL != filename);
1353  }
1354  break;
1355 
1356  default:
1357  GNUNET_break (0);
1358  GNUNET_free (tc);
1359  return NULL;
1360  }
1361  do
1362  {
1363  secondary_option = GNUNET_VA_ARG_ENUM (va, GNUNET_TESTBED_TopologyOption);
1364 
1365  switch (secondary_option)
1366  {
1368  overlay->retry_cnt = va_arg (va, unsigned int);
1369  break;
1370 
1372  break;
1373 
1374  default:
1375  GNUNET_break (0); /* Should not use any other option apart from
1376  * the ones handled here */
1377  GNUNET_free (overlay->link_array);
1378  GNUNET_free (tc);
1379  return NULL;
1380  }
1381  }
1382  while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option);
1390  "Generated topology with %u connections\n",
1391  tc->link_array_size);
1392  if (NULL != max_connections)
1393  *max_connections = tc->link_array_size;
1394  return op;
1395 }
1396 
1397 
1418 struct GNUNET_TESTBED_Operation *
1420  unsigned int num_peers,
1421  struct GNUNET_TESTBED_Peer **peers,
1422  unsigned int *max_connections,
1424  comp_cb,
1425  void *comp_cb_cls,
1427  topo,
1428  ...)
1429 {
1430  struct GNUNET_TESTBED_Operation *op;
1431  va_list vargs;
1432 
1434  va_start (vargs, topo);
1437  comp_cb, comp_cb_cls,
1438  topo,
1439  vargs);
1440  va_end (vargs);
1441  return op;
1442 }
1443 
1444 
1445 int
1447  const char *topology_string)
1448 {
1449  unsigned int cnt;
1450 
1451  for (cnt = 0; NULL != topology_strings[cnt]; cnt++)
1452  {
1453  if (0 == strcasecmp (topology_string, topology_strings[cnt]))
1454  {
1455  if (NULL != topology)
1458  (enum GNUNET_TESTBED_TopologyOption) cnt);
1459  return GNUNET_YES;
1460  }
1461  }
1462  return GNUNET_NO;
1463 }
1464 
1465 
1473 char *
1475 {
1477  return NULL;
1479 }
1480 
1481 
1498 int
1501  void *cls,
1502  ...)
1503 {
1504  struct TopologyContext tc;
1505  struct TopologyContextUnderlay *underlay;
1506  struct UnderlayLink *ulink;
1507  va_list vargs;
1509  unsigned int cnt;
1510  int ret;
1511 
1512  GNUNET_assert (NULL != proc);
1513  ret = GNUNET_OK;
1514  memset (&tc, 0, sizeof(tc));
1515  tc.num_peers = num_peers;
1516  tc.type = TOPOLOGYCONTEXT_TYPE_UNDERLAY;
1517  underlay = &tc.u.underlay;
1518  va_start (vargs, cls);
1520  switch (topology)
1521  {
1523  gen_topo_line (&tc);
1524  break;
1525 
1527  gen_topo_star (&tc);
1528  break;
1529 
1531  gen_topo_ring (&tc);
1532  break;
1533 
1535  gen_topo_clique (&tc);
1536  break;
1537 
1539  gen_topo_2dtorus (&tc);
1540  break;
1541 
1543  gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_NO);
1544  break;
1545 
1547  gen_topo_ring (&tc);
1548  gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
1549  break;
1550 
1552  gen_topo_2dtorus (&tc);
1553  gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
1554  break;
1555 
1557  {
1558  const char *filename;
1559  filename = va_arg (vargs, char *);
1560  GNUNET_assert (NULL != filename);
1562  }
1563  break;
1564 
1566  {
1567  uint16_t cap;
1568  uint8_t m;
1569  cap = (uint16_t) va_arg (vargs, unsigned int);
1570  m = (uint8_t) va_arg (vargs, unsigned int);
1571  gen_topo_scale_free (&tc, cap, m);
1572  }
1573  break;
1574 
1575  default:
1576  GNUNET_assert (0);
1577  }
1578  va_end (vargs);
1579  for (cnt = 0; cnt < tc.link_array_size; cnt++)
1580  {
1581  ulink = &underlay->link_array[cnt];
1582  if (GNUNET_SYSERR == proc (cls,
1583  ulink->A,
1584  ulink->B,
1585  ulink->bandwidth,
1586  ulink->latency,
1587  ulink->loss))
1588  {
1589  ret = GNUNET_SYSERR;
1590  break;
1591  }
1592  }
1593  GNUNET_free (underlay->link_array);
1594  return ret;
1595 }
1596 
1597 
1598 /* end of testbed_api_topology.c */
static int retry_entry(void *cls, const struct GNUNET_HashCode *key, void *entry)
Add entries to the message queue.
Definition: fs_download.c:747
enum GNUNET_TESTBED_TopologyOption topology
The topology to generate.
static int ret
Return value of the commandline.
Definition: gnunet-abd.c:81
static struct GNUNET_ARM_Operation * op
Current operation.
Definition: gnunet-arm.c:144
static struct GNUNET_ARM_MonitorHandle * m
Monitor connection with ARM.
Definition: gnunet-arm.c:104
static int end
Set if we are to shutdown all services (including ARM).
Definition: gnunet-arm.c:34
static struct CadetPeer * peers
Operation to get peer ids.
static char * peer_id
Option –peer.
Definition: gnunet-cadet.c:42
static unsigned int num_peers
static unsigned long long max_connections
If there are at least this many connections, old ones will be removed.
static char * filename
static struct GNUNET_FS_Handle * fs
Handle to FS service.
Definition: gnunet-fs.c:37
uint32_t data
The data value.
uint16_t status
See PRISM_STATUS_*-constants.
enum State state
current state of profiling
static char buf[2048]
static struct GNUNET_CONTAINER_MultiPeerMap * links
Map from PIDs to struct VirtualLink entries describing links CORE knows to exist.
static struct GNUNET_OS_Process * p
Helper process we started.
Definition: gnunet-uri.c:38
API for writing tests and creating large-scale emulation testbeds for GNUnet.
uint64_t GNUNET_CRYPTO_random_u64(enum GNUNET_CRYPTO_Quality mode, uint64_t max)
Generate a random unsigned 64-bit value.
uint32_t GNUNET_CRYPTO_random_u32(enum GNUNET_CRYPTO_Quality mode, uint32_t i)
Produce a random value.
@ GNUNET_CRYPTO_QUALITY_WEAK
No good quality of the operation is needed (i.e., random numbers can be pseudo-random).
enum GNUNET_GenericReturnValue GNUNET_DISK_file_test(const char *fil)
Check that fil corresponds to a filename (of a file that exists and that is not a directory).
Definition: disk.c:481
enum GNUNET_GenericReturnValue GNUNET_DISK_file_size(const char *filename, uint64_t *size, int include_symbolic_links, int single_file_mode)
Get the size of the file (or directory) of the given file (in bytes).
Definition: disk.c:221
ssize_t GNUNET_DISK_fn_read(const char *fn, void *result, size_t len)
Read the contents of a binary file into a buffer.
Definition: disk.c:663
#define GNUNET_CONTAINER_DLL_remove(head, tail, element)
Remove an element from a DLL.
#define GNUNET_CONTAINER_DLL_insert_tail(head, tail, element)
Insert an element at the tail of a DLL.
#define GNUNET_VA_ARG_ENUM(va, X)
wrap va_arg for enums
#define GNUNET_MAX(a, b)
#define GNUNET_MIN(a, b)
@ GNUNET_OK
@ GNUNET_YES
@ GNUNET_NO
@ GNUNET_SYSERR
#define GNUNET_assert(cond)
Use this for fatal errors that cannot be handled.
#define GNUNET_break(cond)
Use this for internal assertion violations that are not fatal (can be handled) but should not occur.
@ GNUNET_ERROR_TYPE_WARNING
@ GNUNET_ERROR_TYPE_ERROR
@ GNUNET_ERROR_TYPE_DEBUG
#define GNUNET_strdup(a)
Wrapper around GNUNET_xstrdup_.
#define GNUNET_malloc_large(size)
Wrapper around malloc.
#define GNUNET_new(type)
Allocate a struct or union of the given type.
#define GNUNET_malloc(size)
Wrapper around malloc.
#define GNUNET_new_array(n, type)
Allocate a size n array with structs or unions of the given type.
#define GNUNET_realloc(ptr, size)
Wrapper around realloc.
#define GNUNET_free(ptr)
Wrapper around free.
GNUNET_TESTBED_TopologyOption
Topologies and topology options supported for testbeds.
void GNUNET_TESTBED_operation_done(struct GNUNET_TESTBED_Operation *operation)
This function is used to signal that the event information (struct GNUNET_TESTBED_EventInformation) f...
Definition: testbed_api.c:2021
struct GNUNET_TESTBED_Operation * GNUNET_TESTBED_underlay_configure_topology(void *op_cls, unsigned int num_peers, struct GNUNET_TESTBED_Peer **peers, enum GNUNET_TESTBED_TopologyOption topo,...)
Configure overall network topology to have a particular shape.
void(* GNUNET_TESTBED_TopologyCompletionCallback)(void *cls, unsigned int nsuccess, unsigned int nfailures)
Callbacks of this type are called when topology configuration is completed.
struct GNUNET_TESTBED_Operation * GNUNET_TESTBED_overlay_configure_topology(void *op_cls, unsigned int num_peers, struct GNUNET_TESTBED_Peer **peers, unsigned int *max_connections, GNUNET_TESTBED_TopologyCompletionCallback comp_cb, void *comp_cb_cls, enum GNUNET_TESTBED_TopologyOption topo,...)
All peers must have been started before calling this function.
struct GNUNET_TESTBED_Operation * GNUNET_TESTBED_overlay_connect(void *op_cls, GNUNET_TESTBED_OperationCompletionCallback cb, void *cb_cls, struct GNUNET_TESTBED_Peer *p1, struct GNUNET_TESTBED_Peer *p2)
Both peers must have been started before calling this function.
struct GNUNET_TESTBED_Operation * GNUNET_TESTBED_overlay_configure_topology_va(void *op_cls, unsigned int num_peers, struct GNUNET_TESTBED_Peer **peers, unsigned int *max_connections, GNUNET_TESTBED_TopologyCompletionCallback comp_cb, void *comp_cb_cls, enum GNUNET_TESTBED_TopologyOption topo, va_list va)
All peers must have been started before calling this function.
struct GNUNET_TESTBED_Operation * GNUNET_TESTBED_underlay_configure_topology_va(void *op_cls, unsigned int num_peers, struct GNUNET_TESTBED_Peer **peers, enum GNUNET_TESTBED_TopologyOption topo, va_list ap)
Configure overall network topology to have a particular shape.
@ GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD
Small-world network (2d torus plus random links).
@ GNUNET_TESTBED_TOPOLOGY_FROM_FILE
Read a topology from a given file.
@ GNUNET_TESTBED_TOPOLOGY_RING
Ring topology.
@ GNUNET_TESTBED_TOPOLOGY_CLIQUE
A clique (everyone connected to everyone else).
@ GNUNET_TESTBED_TOPOLOGY_SCALE_FREE
Scale free topology.
@ GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI
Random graph.
@ GNUNET_TESTBED_TOPOLOGY_STAR
Star topology.
@ GNUNET_TESTBED_TOPOLOGY_RETRY_CNT
How many times should the failed overlay connect operations be retried before giving up.
@ GNUNET_TESTBED_TOPOLOGY_2D_TORUS
2-d torus.
@ GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING
Small-world network (ring plus random links).
@ GNUNET_TESTBED_TOPOLOGY_LINE
Straight line topology.
@ GNUNET_TESTBED_TOPOLOGY_OPTION_END
The options should always end with this.
#define _(String)
GNU gettext support macro.
Definition: platform.h:177
static struct GNUNET_SCHEDULER_TaskContext tc
Task context of the current task.
Definition: scheduler.c:424
Handle to interact with a GNUnet testbed controller.
Definition: testbed_api.h:194
struct OperationQueue * opq_parallel_topology_config_operations
Operation queue for simultaneous topology configuration operations.
Definition: testbed_api.h:254
Opaque handle to an abstract operation to be executed by the testing framework.
A peer controlled by the testing framework.
struct RetryListEntry * prev
the prev pointer for the DLL
struct RetryListEntry * next
the next pointer for the DLL
struct OverlayLink * link
The link to be retired.
Context information for overlay topologies.
struct GNUNET_TESTBED_Peer ** peers
The array of peers.
unsigned int retry_cnt
How many retries to do before we give up.
unsigned int nlinks
Number of links to try.
void * comp_cb_cls
The closure for the above callback.
struct RetryListEntry * rl_tail
DLL tail for retry list.
struct RetryListEntry * rl_head
DLL head for retry list.
unsigned int nsuccess
Total successfully established overlay connections.
unsigned int nfailures
Total failed overlay connections.
struct OverlayLink * link_array
An array of links; this array is of size link_array_size.
void * op_cls
The operation closure.
unsigned int ncompleted
How many links have been completed.
GNUNET_TESTBED_TopologyCompletionCallback comp_cb
topology generation completion callback
Topology context information for underlay topologies.
struct UnderlayLink * link_array
The link array.
Context information for topology operations.
unsigned int num_peers
The number of peers.
unsigned int link_array_size
The size of the link array.
enum TopologyContext::@61 type
The type of this context.
struct TopologyContextOverlay overlay
Topology context information for overlay topology.
@ TOPOLOGYCONTEXT_TYPE_UNDERLAY
Type for underlay topology.
@ TOPOLOGYCONTEXT_TYPE_OVERLAY
Type for overlay topology.
union TopologyContext::@62 u
struct TopologyContextUnderlay underlay
Topology context information for underlay topology.
Interface for functions internally exported from testbed_api.c.
struct GNUNET_TESTBED_Operation * GNUNET_TESTBED_operation_create_(void *cls, OperationStart start, OperationRelease release)
Create an 'operation' to be performed.
void GNUNET_TESTBED_operation_queue_insert_(struct OperationQueue *queue, struct GNUNET_TESTBED_Operation *op)
Add an operation to a queue.
void GNUNET_TESTBED_operation_begin_wait_(struct GNUNET_TESTBED_Operation *op)
Marks the given operation as waiting on the queues.
internal API to access the 'operations' subsystem
internal API to access the 'peers' subsystem
int GNUNET_TESTBED_underlay_construct_(int num_peers, underlay_link_processor proc, void *cls,...)
Function to construct an underlay topology.
#define DEFAULT_RETRY_CNT
Default number of retires.
static void overlay_link_completed(void *cls, struct GNUNET_TESTBED_Operation *op, const char *emsg)
Callback to be called when an overlay_link operation complete.
static void gen_topo_scale_free(struct TopologyContext *tc, uint16_t cap, uint8_t m)
Generates scale free network.
static void gen_topo_line(struct TopologyContext *tc)
Generates line topology.
static void gen_topo_star(struct TopologyContext *tc)
Generates star topology.
int GNUNET_TESTBED_topology_get_(enum GNUNET_TESTBED_TopologyOption *topology, const char *topology_string)
Get a topology from a string input.
static void make_link(unsigned int offset, uint32_t A, uint32_t B, struct TopologyContext *tc)
Populates the OverlayLink structure.
static void gen_topo_from_file(struct TopologyContext *tc, const char *filename)
Generates topology from the given file.
static void opstart_overlay_configure_topology(void *cls)
Function called when a overlay connect operation is ready.
static void gen_topo_clique(struct TopologyContext *tc)
Generates clique topology.
static const char * topology_strings[]
A array of names representing topologies.
unsigned int GNUNET_TESTBED_2dtorus_calc_links(unsigned int num_peers, unsigned int *rows, unsigned int **rows_len)
Returns the number of links that are required to generate a 2d torus for the given number of peers.
static void gen_topo_random(struct TopologyContext *tc, unsigned int links, int append)
Generates ring topology.
static void oprelease_overlay_configure_topology(void *cls)
Callback which will be called when overlay connect operation is released.
#define LOG(kind,...)
Generic loggins shorthand.
char * GNUNET_TESTBED_topology_to_str_(enum GNUNET_TESTBED_TopologyOption topology)
Returns the string corresponding to the given topology.
static void gen_topo_2dtorus(struct TopologyContext *tc)
Generates ring topology.
static void gen_topo_ring(struct TopologyContext *tc)
Generates ring topology.
header for intra library exported functions
int(* underlay_link_processor)(void *cls, unsigned int A, unsigned int B, unsigned int bandwidth, unsigned int latency, unsigned int loss)
Functions of this type are called to process underlay link.
struct GNUNET_TESTBED_Peer * peer
The peer associated with this model.