aboutsummaryrefslogtreecommitdiff
path: root/src/testbed/testbed_api_topology.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/testbed/testbed_api_topology.c')
-rw-r--r--src/testbed/testbed_api_topology.c1598
1 files changed, 0 insertions, 1598 deletions
diff --git a/src/testbed/testbed_api_topology.c b/src/testbed/testbed_api_topology.c
deleted file mode 100644
index f73be378e..000000000
--- a/src/testbed/testbed_api_topology.c
+++ /dev/null
@@ -1,1598 +0,0 @@
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
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 * Default number of retires
42 */
43#define DEFAULT_RETRY_CNT 3
44
45
46/**
47 * Context information for topology operations
48 */
49struct TopologyContext;
50
51
52/**
53 * Representation of an overlay link
54 */
55struct OverlayLink
56{
57 /**
58 * An operation corresponding to this link
59 */
60 struct GNUNET_TESTBED_Operation *op;
61
62 /**
63 * The topology context this link is a part of
64 */
65 struct TopologyContext *tc;
66
67 /**
68 * position of peer A's handle in peers array
69 */
70 uint32_t A;
71
72 /**
73 * position of peer B's handle in peers array
74 */
75 uint32_t B;
76};
77
78
79/**
80 * Representation of an underlay link
81 */
82struct UnderlayLink
83{
84 /**
85 * position of peer A's handle in peers array
86 */
87 uint32_t A;
88
89 /**
90 * position of peer B's handle in peers array
91 */
92 uint32_t B;
93
94 /**
95 * Bandwidth of the link in bytes per second
96 */
97 uint32_t bandwidth;
98
99 /**
100 * Latency of the link in milliseconds
101 */
102 uint32_t latency;
103
104 /**
105 * Loss in the link in percentage of message dropped
106 */
107 uint32_t loss;
108};
109
110
111struct RetryListEntry
112{
113 /**
114 * the next pointer for the DLL
115 */
116 struct RetryListEntry *next;
117
118 /**
119 * the prev pointer for the DLL
120 */
121 struct RetryListEntry *prev;
122
123 /**
124 * The link to be retired
125 */
126 struct OverlayLink *link;
127};
128
129
130/**
131 * Context information for overlay topologies
132 */
133struct TopologyContextOverlay
134{
135 /**
136 * The array of peers
137 */
138 struct GNUNET_TESTBED_Peer **peers;
139
140 /**
141 * An array of links; this array is of size link_array_size
142 */
143 struct OverlayLink *link_array;
144
145 /**
146 * The operation closure
147 */
148 void *op_cls;
149
150 /**
151 * topology generation completion callback
152 */
153 GNUNET_TESTBED_TopologyCompletionCallback comp_cb;
154
155 /**
156 * The closure for the above callback
157 */
158 void *comp_cb_cls;
159
160 /**
161 * DLL head for retry list
162 */
163 struct RetryListEntry *rl_head;
164
165 /**
166 * DLL tail for retry list
167 */
168 struct RetryListEntry *rl_tail;
169
170 /**
171 * How many retries to do before we give up
172 */
173 unsigned int retry_cnt;
174
175 /**
176 * Number of links to try
177 */
178 unsigned int nlinks;
179
180 /**
181 * How many links have been completed
182 */
183 unsigned int ncompleted;
184
185 /**
186 * Total successfully established overlay connections
187 */
188 unsigned int nsuccess;
189
190 /**
191 * Total failed overlay connections
192 */
193 unsigned int nfailures;
194};
195
196
197/**
198 * Topology context information for underlay topologies
199 */
200struct TopologyContextUnderlay
201{
202 /**
203 * The link array
204 */
205 struct UnderlayLink *link_array;
206};
207
208
209/**
210 * Context information for topology operations
211 */
212struct TopologyContext
213{
214 /**
215 * The type of this context
216 */
217 enum
218 {
219 /**
220 * Type for underlay topology
221 */
222 TOPOLOGYCONTEXT_TYPE_UNDERLAY = 0,
223
224 /**
225 * Type for overlay topology
226 */
227 TOPOLOGYCONTEXT_TYPE_OVERLAY
228 } type;
229
230 union
231 {
232 /**
233 * Topology context information for overlay topology
234 */
235 struct TopologyContextOverlay overlay;
236
237 /**
238 * Topology context information for underlay topology
239 */
240 struct TopologyContextUnderlay underlay;
241 } u;
242
243 /**
244 * The number of peers
245 */
246 unsigned int num_peers;
247
248 /**
249 * The size of the link array
250 */
251 unsigned int link_array_size;
252};
253
254
255/**
256 * A array of names representing topologies. Should be in sync with enum
257 * GNUNET_TESTBED_TopologyOption
258 */
259static const char *topology_strings[] = {
260 /**
261 * A clique (everyone connected to everyone else). No options. If there are N
262 * peers this topology results in (N * (N -1)) connections.
263 */
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
272 /**
273 * Small-world network (ring plus random links). Followed
274 * by the number of random links to add (unsigned int).
275 */
276 "SMALL_WORLD_RING",
277
278 /**
279 * Ring topology. No options.
280 */
281 "RING",
282
283 /**
284 * Star topology. No options.
285 */
286 "STAR",
287
288 /**
289 * 2-d torus. No options.
290 */
291 "2D_TORUS",
292
293 /**
294 * Random graph. Followed by the number of random links to be established
295 * (unsigned int)
296 */
297 "RANDOM", // GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI
298
299 /**
300 * Certain percentage of peers are unable to communicate directly
301 * replicating NAT conditions. Followed by the fraction of
302 * NAT'ed peers (float).
303 */
304 "INTERNAT",
305
306 /**
307 * Scale free topology. Followed by the maximum number of links a node can
308 * have (unsigned int); and the number of links a new node should have when
309 * it is added to the network (unsigned int)
310 */
311 "SCALE_FREE",
312
313 /**
314 * Straight line topology. No options.
315 */
316 "LINE",
317
318 /**
319 * Read a topology from a given file. Followed by the name of the file (const char *).
320 */
321 "FROM_FILE",
322
323 /**
324 * All peers are disconnected. No options.
325 */
326 "NONE",
327
328 /**
329 * End of strings
330 */
331 NULL
332};
333
334
335/**
336 * Callback to be called when an overlay_link operation complete
337 *
338 * @param cls element of the link_op array which points to the corresponding operation
339 * @param op the operation that has been finished
340 * @param emsg error message in case the operation has failed; will be NULL if
341 * operation has executed successfully.
342 */
343static void
344overlay_link_completed (void *cls,
345 struct GNUNET_TESTBED_Operation *op,
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);
354 GNUNET_TESTBED_operation_done (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 {
364 LOG (GNUNET_ERROR_TYPE_WARNING,
365 "Error while establishing a link: %s -- Retrying\n",
366 emsg);
367 retry_entry = GNUNET_new (struct RetryListEntry);
368 retry_entry->link = link;
369 GNUNET_CONTAINER_DLL_insert_tail (overlay->rl_head,
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 =
388 GNUNET_TESTBED_overlay_connect (overlay->op_cls,
389 &overlay_link_completed,
390 link,
391 overlay->peers[link->A],
392 overlay->peers[link->B]);
393 overlay->nlinks++;
394 GNUNET_CONTAINER_DLL_remove (overlay->rl_head,
395 overlay->rl_tail,
396 retry_entry);
397 GNUNET_free (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
410/**
411 * Function called when a overlay connect operation is ready
412 *
413 * @param cls the Topology context
414 */
415static void
416opstart_overlay_configure_topology (void *cls)
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 =
428 GNUNET_TESTBED_overlay_connect (overlay->op_cls,
429 &overlay_link_completed,
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
437/**
438 * Callback which will be called when overlay connect operation is released
439 *
440 * @param cls the Topology context
441 */
442static void
443oprelease_overlay_configure_topology (void *cls)
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);
456 GNUNET_free (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)
462 GNUNET_TESTBED_operation_done (overlay->link_array[p].op);
463 GNUNET_free (overlay->link_array);
464 }
465 GNUNET_free (tc);
466}
467
468
469/**
470 * Populates the OverlayLink structure.
471 *
472 * @param offset the offset of the link array to use
473 * @param A the peer A. Should be different from B
474 * @param B the peer B. Should be different from A
475 * @param tc the TopologyContext
476 * @return
477 */
478static void
479make_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
519/**
520 * Generates line topology
521 *
522 * @param tc the topology context
523 */
524static void
525gen_topo_line (struct TopologyContext *tc)
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
559/**
560 * Generates star topology
561 *
562 * @param tc the topology context
563 */
564static void
565gen_topo_star (struct TopologyContext *tc)
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
602/**
603 * Generates ring topology
604 *
605 * @param tc the topology context
606 */
607static void
608gen_topo_ring (struct TopologyContext *tc)
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
640unsigned int
641GNUNET_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
686/**
687 * Generates ring topology
688 *
689 * @param tc the topology context
690 */
691static void
692gen_topo_2dtorus (struct TopologyContext *tc)
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
762/**
763 * Generates ring topology
764 *
765 * @param tc the topology context
766 * @param links the number of random links to establish
767 * @param append #GNUNET_YES to add links to existing link array; #GNUNET_NO to
768 * create a new link array
769 */
770static void
771gen_topo_random (struct TopologyContext *tc,
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 =
839 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
840 B_rand =
841 GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers);
842 }
843 while (A_rand == B_rand);
844 make_link (index + cnt, A_rand, B_rand, tc);
845 }
846}
847
848
849/**
850 * Generates scale free network. Its construction is described in:
851 *
852 * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999.
853 *
854 * @param tc the topology context
855 * @param cap maximum allowed node degree
856 * @param m number of edges to establish for a new node when it is added to the
857 * network
858 */
859static void
860gen_topo_scale_free (struct TopologyContext *tc,
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;
917redo:
918 off = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, etaboff);
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
986/**
987 * Generates topology from the given file
988 *
989 * @param tc the topology context
990 * @param filename the filename of the file containing topology data
991 */
992static void
993gen_topo_from_file (struct TopologyContext *tc,
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 {
1005 /**
1006 * We read the peer index
1007 */
1008 PEER_INDEX,
1009
1010 /**
1011 * We read the other peer indices
1012 */
1013 OTHER_PEER_INDEX,
1014 } state;
1015 int status;
1016
1017 status = GNUNET_SYSERR;
1018 if (GNUNET_YES != GNUNET_DISK_file_test (filename))
1019 {
1020 LOG (GNUNET_ERROR_TYPE_ERROR,
1021 _ ("Topology file %s not found\n"),
1022 filename);
1023 return;
1024 }
1025 if (GNUNET_OK !=
1026 GNUNET_DISK_file_size (filename, &fs, GNUNET_YES, GNUNET_YES))
1027 {
1028 LOG (GNUNET_ERROR_TYPE_ERROR,
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 {
1036 LOG (GNUNET_ERROR_TYPE_ERROR,
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 {
1058 LOG (GNUNET_ERROR_TYPE_ERROR,
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 {
1067 LOG (GNUNET_ERROR_TYPE_ERROR,
1068 _ ("Value in given topology file: %s out of range\n"), filename);
1069 goto _exit;
1070 }
1071 if (&data[offset] == end)
1072 {
1073 LOG (GNUNET_ERROR_TYPE_ERROR,
1074 _ ("Failed to read peer index from topology file: %s"), filename);
1075 goto _exit;
1076 }
1077 if (tc->num_peers <= peer_id)
1078 {
1079 LOG (GNUNET_ERROR_TYPE_ERROR,
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 {
1092 LOG (GNUNET_ERROR_TYPE_ERROR,
1093 _ ("Value in given topology file: %s out of range\n"), filename);
1094 goto _exit;
1095 }
1096 if (&data[offset] == end)
1097 {
1098 LOG (GNUNET_ERROR_TYPE_ERROR,
1099 _ ("Failed to read peer index from topology file: %s"), filename);
1100 goto _exit;
1101 }
1102 if (tc->num_peers <= other_peer_id)
1103 {
1104 LOG (GNUNET_ERROR_TYPE_ERROR,
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
1140 LOG (GNUNET_ERROR_TYPE_WARNING,
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 {
1164 LOG (GNUNET_ERROR_TYPE_WARNING,
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
1193/**
1194 * Generates clique topology
1195 *
1196 * @param tc the topology context
1197 */
1198static void
1199gen_topo_clique (struct TopologyContext *tc)
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
1241struct GNUNET_TESTBED_Operation *
1242GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls,
1243 unsigned int num_peers,
1244 struct GNUNET_TESTBED_Peer
1245 **peers,
1246 enum
1247 GNUNET_TESTBED_TopologyOption
1248 topo, va_list ap)
1249{
1250 GNUNET_break (0);
1251 return NULL;
1252}
1253
1254
1255struct GNUNET_TESTBED_Operation *
1256GNUNET_TESTBED_underlay_configure_topology (void *op_cls,
1257 unsigned int num_peers,
1258 struct GNUNET_TESTBED_Peer **peers,
1259 enum GNUNET_TESTBED_TopologyOption
1260 topo, ...)
1261{
1262 GNUNET_break (0);
1263 return NULL;
1264}
1265
1266
1267struct GNUNET_TESTBED_Operation *
1268GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls,
1269 unsigned int num_peers,
1270 struct GNUNET_TESTBED_Peer **peers,
1271 unsigned int *max_connections,
1272 GNUNET_TESTBED_TopologyCompletionCallback
1273 comp_cb,
1274 void *comp_cb_cls,
1275 enum GNUNET_TESTBED_TopologyOption
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 {
1299 case GNUNET_TESTBED_TOPOLOGY_LINE:
1300 gen_topo_line (tc);
1301 break;
1302
1303 case GNUNET_TESTBED_TOPOLOGY_STAR:
1304 gen_topo_star (tc);
1305 break;
1306
1307 case GNUNET_TESTBED_TOPOLOGY_RING:
1308 gen_topo_ring (tc);
1309 break;
1310
1311 case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
1312 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_NO);
1313 break;
1314
1315 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
1316 gen_topo_ring (tc);
1317 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
1318 break;
1319
1320 case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
1321 gen_topo_clique (tc);
1322 break;
1323
1324 case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
1325 gen_topo_2dtorus (tc);
1326 break;
1327
1328 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
1329 gen_topo_2dtorus (tc);
1330 gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES);
1331
1332 break;
1333
1334 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
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
1345 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
1346 {
1347 const char *filename;
1348
1349 filename = va_arg (va, const char *);
1350
1351 GNUNET_assert (NULL != filename);
1352 gen_topo_from_file (tc, 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 {
1367 case GNUNET_TESTBED_TOPOLOGY_RETRY_CNT:
1368 overlay->retry_cnt = va_arg (va, unsigned int);
1369 break;
1370
1371 case GNUNET_TESTBED_TOPOLOGY_OPTION_END:
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);
1383 op = GNUNET_TESTBED_operation_create_ (tc,
1384 &opstart_overlay_configure_topology,
1385 &oprelease_overlay_configure_topology);
1386 GNUNET_TESTBED_operation_queue_insert_
1387 (c->opq_parallel_topology_config_operations, op);
1388 GNUNET_TESTBED_operation_begin_wait_ (op);
1389 LOG (GNUNET_ERROR_TYPE_DEBUG,
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
1398/**
1399 * All peers must have been started before calling this function.
1400 * This function then connects the given peers in the P2P overlay
1401 * using the given topology.
1402 *
1403 * @param op_cls closure argument to give with the peer connect operation events
1404 * generated through this function
1405 * @param num_peers number of peers in 'peers'
1406 * @param peers array of 'num_peers' with the peers to configure
1407 * @param max_connections the maximums number of overlay connections that will
1408 * be made to achieve the given topology
1409 * @param comp_cb the completion callback to call when the topology generation
1410 * is completed
1411 * @param comp_cb_cls closure for the above completion callback
1412 * @param topo desired underlay topology to use
1413 * @param ... topology-specific options
1414 * @return handle to the operation, NULL if connecting these
1415 * peers is fundamentally not possible at this time (peers
1416 * not running or underlay disallows) or if num_peers is less than 2
1417 */
1418struct GNUNET_TESTBED_Operation *
1419GNUNET_TESTBED_overlay_configure_topology (void *op_cls,
1420 unsigned int num_peers,
1421 struct GNUNET_TESTBED_Peer **peers,
1422 unsigned int *max_connections,
1423 GNUNET_TESTBED_TopologyCompletionCallback
1424 comp_cb,
1425 void *comp_cb_cls,
1426 enum GNUNET_TESTBED_TopologyOption
1427 topo,
1428 ...)
1429{
1430 struct GNUNET_TESTBED_Operation *op;
1431 va_list vargs;
1432
1433 GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END);
1434 va_start (vargs, topo);
1435 op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers,
1436 max_connections,
1437 comp_cb, comp_cb_cls,
1438 topo,
1439 vargs);
1440 va_end (vargs);
1441 return op;
1442}
1443
1444
1445int
1446GNUNET_TESTBED_topology_get_ (enum GNUNET_TESTBED_TopologyOption *topology,
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)
1456 *topology = (enum GNUNET_TESTBED_TopologyOption) cnt;
1457 GNUNET_assert (GNUNET_TESTBED_TOPOLOGY_OPTION_END !=
1458 (enum GNUNET_TESTBED_TopologyOption) cnt);
1459 return GNUNET_YES;
1460 }
1461 }
1462 return GNUNET_NO;
1463}
1464
1465
1466/**
1467 * Returns the string corresponding to the given topology
1468 *
1469 * @param topology the topology
1470 * @return the string (freshly allocated) of given topology; NULL if topology cannot be
1471 * expressed as a string
1472 */
1473char *
1474GNUNET_TESTBED_topology_to_str_ (enum GNUNET_TESTBED_TopologyOption topology)
1475{
1476 if (GNUNET_TESTBED_TOPOLOGY_OPTION_END <= topology)
1477 return NULL;
1478 return GNUNET_strdup (topology_strings[topology]);
1479}
1480
1481
1482/**
1483 * Function to construct an underlay topology
1484 *
1485 * @param num_peers the number of peers for which the topology should be
1486 * generated
1487 * @param proc the underlay link processor callback. Will be called for each
1488 * underlay link generated unless a previous call to this callback
1489 * returned #GNUNET_SYSERR. Cannot be NULL.
1490 * @param cls closure for @a proc
1491 * @param ... variable arguments denoting the topology and its parameters. They
1492 * should start with the type of topology to generate followed by their
1493 * options.
1494 * @return #GNUNET_OK if underlay link generation is successful; #GNUNET_SYSERR
1495 * upon error in generating the underlay or if any calls to the
1496 * underlay link processor returned #GNUNET_SYSERR
1497 */
1498int
1499GNUNET_TESTBED_underlay_construct_ (int num_peers,
1500 underlay_link_processor proc,
1501 void *cls,
1502 ...)
1503{
1504 struct TopologyContext tc;
1505 struct TopologyContextUnderlay *underlay;
1506 struct UnderlayLink *ulink;
1507 va_list vargs;
1508 enum GNUNET_TESTBED_TopologyOption topology;
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);
1519 topology = GNUNET_VA_ARG_ENUM (vargs, GNUNET_TESTBED_TopologyOption);
1520 switch (topology)
1521 {
1522 case GNUNET_TESTBED_TOPOLOGY_LINE:
1523 gen_topo_line (&tc);
1524 break;
1525
1526 case GNUNET_TESTBED_TOPOLOGY_STAR:
1527 gen_topo_star (&tc);
1528 break;
1529
1530 case GNUNET_TESTBED_TOPOLOGY_RING:
1531 gen_topo_ring (&tc);
1532 break;
1533
1534 case GNUNET_TESTBED_TOPOLOGY_CLIQUE:
1535 gen_topo_clique (&tc);
1536 break;
1537
1538 case GNUNET_TESTBED_TOPOLOGY_2D_TORUS:
1539 gen_topo_2dtorus (&tc);
1540 break;
1541
1542 case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI:
1543 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_NO);
1544 break;
1545
1546 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING:
1547 gen_topo_ring (&tc);
1548 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
1549 break;
1550
1551 case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD:
1552 gen_topo_2dtorus (&tc);
1553 gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES);
1554 break;
1555
1556 case GNUNET_TESTBED_TOPOLOGY_FROM_FILE:
1557 {
1558 const char *filename;
1559 filename = va_arg (vargs, char *);
1560 GNUNET_assert (NULL != filename);
1561 gen_topo_from_file (&tc, filename);
1562 }
1563 break;
1564
1565 case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE:
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 */
generated by cgit v1.2.3 (git 2.39.1) at 2024-05-23 03:21:05 +0000