X-Git-Url: https://git.librecmc.org/?a=blobdiff_plain;f=src%2Ftestbed%2Ftestbed_api_topology.c;h=1f7d11b27312e58d378f33c911a90d7f4962f5af;hb=5742938289524f4c5fba7883742e4dd69cccf11d;hp=544a8e42a633cbf8ca9a3393e70bfb1f65603c90;hpb=0d45e157a134a01ec59e8fc564918a1caa5070c4;p=oweals%2Fgnunet.git diff --git a/src/testbed/testbed_api_topology.c b/src/testbed/testbed_api_topology.c index 544a8e42a..1f7d11b27 100644 --- a/src/testbed/testbed_api_topology.c +++ b/src/testbed/testbed_api_topology.c @@ -1,6 +1,6 @@ /* This file is part of GNUnet - (C) 2008--2012 Christian Grothoff (and other contributing authors) + Copyright (C) 2008--2013 GNUnet e.V. GNUnet is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published @@ -14,8 +14,8 @@ You should have received a copy of the GNU General Public License along with GNUnet; see the file COPYING. If not, write to the - Free Software Foundation, Inc., 59 Temple Place - Suite 330, - Boston, MA 02111-1307, USA. + Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, + Boston, MA 02110-1301, USA. */ /** @@ -37,6 +37,12 @@ GNUNET_log_from (kind, "testbed-api-topology", __VA_ARGS__) +/** + * Default number of retires + */ +#define DEFAULT_RETRY_CNT 3 + + /** * Context information for topology operations */ @@ -56,7 +62,7 @@ struct OverlayLink /** * The topology context this link is a part of - */ + */ struct TopologyContext *tc; /** @@ -73,9 +79,60 @@ struct OverlayLink /** - * Context information for topology operations + * Representation of an underlay link */ -struct TopologyContext +struct UnderlayLink +{ + /** + * position of peer A's handle in peers array + */ + uint32_t A; + + /** + * position of peer B's handle in peers array + */ + uint32_t B; + + /** + * Bandwidth of the link in bytes per second + */ + uint32_t bandwidth; + + /** + * Latency of the link in milliseconds + */ + uint32_t latency; + + /** + * Loss in the link in percentage of message dropped + */ + uint32_t loss; +}; + + +struct RetryListEntry +{ + /** + * the next pointer for the DLL + */ + struct RetryListEntry *next; + + /** + * the prev pointer for the DLL + */ + struct RetryListEntry *prev; + + /** + * The link to be retired + */ + struct OverlayLink *link; +}; + + +/** + * Context information for overlay topologies + */ +struct TopologyContextOverlay { /** * The array of peers @@ -92,6 +149,100 @@ struct TopologyContext */ void *op_cls; + /** + * topology generation completion callback + */ + GNUNET_TESTBED_TopologyCompletionCallback comp_cb; + + /** + * The closure for the above callback + */ + void *comp_cb_cls; + + /** + * DLL head for retry list + */ + struct RetryListEntry *rl_head; + + /** + * DLL tail for retry list + */ + struct RetryListEntry *rl_tail; + + /** + * How many retries to do before we give up + */ + unsigned int retry_cnt; + + /** + * Number of links to try + */ + unsigned int nlinks; + + /** + * How many links have been completed + */ + unsigned int ncompleted; + + /** + * Total successfully established overlay connections + */ + unsigned int nsuccess; + + /** + * Total failed overlay connections + */ + unsigned int nfailures; +}; + + +/** + * Topology context information for underlay topologies + */ +struct TopologyContextUnderlay +{ + /** + * The link array + */ + struct UnderlayLink *link_array; +}; + + +/** + * Context information for topology operations + */ +struct TopologyContext +{ + /** + * The type of this context + */ + enum { + + /** + * Type for underlay topology + */ + TOPOLOGYCONTEXT_TYPE_UNDERLAY = 0, + + /** + * Type for overlay topology + */ + TOPOLOGYCONTEXT_TYPE_OVERLAY + + } type; + + union { + + /** + * Topology context information for overlay topology + */ + struct TopologyContextOverlay overlay; + + /** + * Topology context information for underlay topology + */ + struct TopologyContextUnderlay underlay; + } u; + /** * The number of peers */ @@ -102,11 +253,6 @@ struct TopologyContext */ unsigned int link_array_size; - /** - * should the automatic retry be disabled - */ - int disable_retry; - }; @@ -114,75 +260,76 @@ struct TopologyContext * A array of names representing topologies. Should be in sync with enum * GNUNET_TESTBED_TopologyOption */ -const char * topology_strings[] = { - +const char *topology_strings[] = { + /** * A clique (everyone connected to everyone else). No options. If there are N * peers this topology results in (N * (N -1)) connections. */ - "CLIQUE", + "CLIQUE", /** * Small-world network (2d torus plus random links). Followed * by the number of random links to add (unsigned int). */ - "SMALL_WORLD", + "SMALL_WORLD", /** * Small-world network (ring plus random links). Followed * by the number of random links to add (unsigned int). */ - "SMALL_WORLD_RING", + "SMALL_WORLD_RING", /** * Ring topology. No options. */ - "RING", + "RING", /** * 2-d torus. No options. */ - "2D_TORUS", + "2D_TORUS", /** * Random graph. Followed by the number of random links to be established * (unsigned int) */ - "RANDOM", // GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI + "RANDOM", // GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI /** * Certain percentage of peers are unable to communicate directly * replicating NAT conditions. Followed by the fraction of * NAT'ed peers (float). */ - "INTERNAT", + "INTERNAT", /** - * Scale free topology. FIXME: options? + * Scale free topology. Followed by the maximum number of links a node can + * have (unsigned int); and the number of links a new node should have when + * it is added to the network (unsigned int) */ - "SCALE_FREE", + "SCALE_FREE", /** * Straight line topology. No options. */ - "LINE", + "LINE", /** * Read a topology from a given file. Followed by the name of the file (const char *). */ - "FROM_FILE", + "FROM_FILE", /** * All peers are disconnected. No options. */ - "NONE", - + "NONE", + /** * End of strings */ - NULL - - }; + NULL +}; /** @@ -193,30 +340,60 @@ const char * topology_strings[] = { * @param emsg error message in case the operation has failed; will be NULL if * operation has executed successfully. */ -static void -overlay_link_completed (void *cls, - struct GNUNET_TESTBED_Operation *op, - const char *emsg) +static void +overlay_link_completed (void *cls, struct GNUNET_TESTBED_Operation *op, + const char *emsg) { struct OverlayLink *link = cls; struct TopologyContext *tc; + struct TopologyContextOverlay *overlay; + struct RetryListEntry *retry_entry; GNUNET_assert (op == link->op); GNUNET_TESTBED_operation_done (op); link->op = NULL; tc = link->tc; - if ((NULL != emsg) && (GNUNET_NO == tc->disable_retry)) + GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type); + overlay = &tc->u.overlay; + if (NULL != emsg) { - LOG (GNUNET_ERROR_TYPE_WARNING, - "Error while establishing a link: %s -- Retrying\n", emsg); - link->op = - GNUNET_TESTBED_overlay_connect (tc->op_cls, - &overlay_link_completed, - link, - tc->peers[link->A], - tc->peers[link->B]); + overlay->nfailures++; + if (0 != overlay->retry_cnt) + { + LOG (GNUNET_ERROR_TYPE_WARNING, + "Error while establishing a link: %s -- Retrying\n", emsg); + retry_entry = GNUNET_new (struct RetryListEntry); + retry_entry->link = link; + GNUNET_CONTAINER_DLL_insert_tail (overlay->rl_head, overlay->rl_tail, retry_entry); + } + } + else + overlay->nsuccess++; + overlay->ncompleted++; + if (overlay->ncompleted < overlay->nlinks) + return; + if ((0 != overlay->retry_cnt) && (NULL != overlay->rl_head)) + { + overlay->retry_cnt--; + overlay->ncompleted = 0; + overlay->nlinks = 0; + while (NULL != (retry_entry = overlay->rl_head)) + { + link = retry_entry->link; + link->op = + GNUNET_TESTBED_overlay_connect (overlay->op_cls, &overlay_link_completed, + link, overlay->peers[link->A], + overlay->peers[link->B]); + overlay->nlinks++; + GNUNET_CONTAINER_DLL_remove (overlay->rl_head, overlay->rl_tail, retry_entry); + GNUNET_free (retry_entry); + } return; } + if (NULL != overlay->comp_cb) + { + overlay->comp_cb (overlay->comp_cb_cls, overlay->nsuccess, overlay->nfailures); + } } @@ -230,15 +407,19 @@ static void opstart_overlay_configure_topology (void *cls) { struct TopologyContext *tc = cls; + struct TopologyContextOverlay *overlay; unsigned int p; - + + GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type); + overlay = &tc->u.overlay; + overlay->nlinks = tc->link_array_size; for (p = 0; p < tc->link_array_size; p++) { - tc->link_array[p].op = - GNUNET_TESTBED_overlay_connect (tc->op_cls, &overlay_link_completed, - &tc->link_array[p], - tc->peers[tc->link_array[p].A], - tc->peers[tc->link_array[p].B]); + overlay->link_array[p].op = + GNUNET_TESTBED_overlay_connect (overlay->op_cls, &overlay_link_completed, + &overlay->link_array[p], + overlay->peers[overlay->link_array[p].A], + overlay->peers[overlay->link_array[p].B]); } } @@ -252,38 +433,72 @@ static void oprelease_overlay_configure_topology (void *cls) { struct TopologyContext *tc = cls; + struct TopologyContextOverlay *overlay; + struct RetryListEntry *retry_entry; unsigned int p; - - if (NULL != tc->link_array) + + GNUNET_assert (TOPOLOGYCONTEXT_TYPE_OVERLAY == tc->type); + overlay = &tc->u.overlay; + while (NULL != (retry_entry = overlay->rl_head)) + { + GNUNET_CONTAINER_DLL_remove (overlay->rl_head, overlay->rl_tail, retry_entry); + GNUNET_free (retry_entry); + } + if (NULL != overlay->link_array) { for (p = 0; p < tc->link_array_size; p++) - if (NULL != tc->link_array[p].op) - GNUNET_TESTBED_operation_done (tc->link_array[p].op); - GNUNET_free (tc->link_array); + if (NULL != overlay->link_array[p].op) + GNUNET_TESTBED_operation_done (overlay->link_array[p].op); + GNUNET_free (overlay->link_array); } GNUNET_free (tc); } /** - * Populates the OverlayLink structure + * Populates the OverlayLink structure. * - * @param link the OverlayLink - * @param A the peer A - * @param B the peer B + * @param offset the offset of the link array to use + * @param A the peer A. Should be different from B + * @param B the peer B. Should be different from A * @param tc the TopologyContext - * @return + * @return */ static void -make_link (struct OverlayLink *link, - uint32_t A, - uint32_t B, +make_link (unsigned int offset, uint32_t A, uint32_t B, struct TopologyContext *tc) { - link->A = A; - link->B = B; - link->op = NULL; - link->tc = tc; + GNUNET_assert (A != B); + switch (tc->type) + { + case TOPOLOGYCONTEXT_TYPE_OVERLAY: + { + struct TopologyContextOverlay *overlay; + struct OverlayLink *olink; + + overlay = &tc->u.overlay; + GNUNET_assert (offset < tc->link_array_size); + olink = &overlay->link_array[offset]; + LOG (GNUNET_ERROR_TYPE_DEBUG, "Connecting peer %u to %u\n", B, A); + olink->A = A; + olink->B = B; + olink->op = NULL; + olink->tc = tc; + } + break; + case TOPOLOGYCONTEXT_TYPE_UNDERLAY: + { + struct TopologyContextUnderlay *underlay; + struct UnderlayLink *ulink; + + underlay = &tc->u.underlay; + GNUNET_assert (offset < tc->link_array_size); + ulink = &underlay->link_array[offset]; + ulink->A = A; + ulink->B = B; + } + break; + } } @@ -298,10 +513,29 @@ gen_topo_line (struct TopologyContext *tc) unsigned int cnt; tc->link_array_size = tc->num_peers - 1; - tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) * - tc->link_array_size); - for (cnt=0; cnt < (tc->num_peers - 1); cnt++) - make_link (&tc->link_array[cnt], cnt, cnt + 1, tc); + switch (tc->type) + { + case TOPOLOGYCONTEXT_TYPE_OVERLAY: + { + struct TopologyContextOverlay *overlay; + + overlay = &tc->u.overlay; + overlay->link_array = + GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size); + } + break; + case TOPOLOGYCONTEXT_TYPE_UNDERLAY: + { + struct TopologyContextUnderlay *underlay; + + underlay = &tc->u.underlay; + underlay->link_array = + GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size); + } + break; + } + for (cnt = 0; cnt < (tc->link_array_size); cnt++) + make_link (cnt, cnt, cnt + 1, tc); } @@ -315,13 +549,30 @@ gen_topo_ring (struct TopologyContext *tc) { gen_topo_line (tc); tc->link_array_size++; - tc->link_array = GNUNET_realloc (tc->link_array, - sizeof (struct OverlayLink) * - tc->link_array_size); - make_link (&tc->link_array[tc->link_array_size - 1], - tc->num_peers - 1, - 0, - tc); + switch (tc->type) + { + case TOPOLOGYCONTEXT_TYPE_OVERLAY: + { + struct TopologyContextOverlay *overlay; + + overlay = &tc->u.overlay; + overlay->link_array = + GNUNET_realloc (overlay->link_array, sizeof (struct OverlayLink) * + tc->link_array_size); + } + break; + case TOPOLOGYCONTEXT_TYPE_UNDERLAY: + { + struct TopologyContextUnderlay *underlay; + + underlay = &tc->u.underlay; + underlay->link_array = + GNUNET_realloc (underlay->link_array, sizeof (struct UnderlayLink) * + tc->link_array_size); + } + break; + } + make_link (tc->link_array_size - 1, tc->num_peers - 1, 0, tc); } @@ -334,10 +585,11 @@ gen_topo_ring (struct TopologyContext *tc) * @param rows number of rows in the 2d torus. Can be NULL * @param rows_len the length of each row. This array will be allocated * fresh. The caller should free it. Can be NULL + * @return the number of links that are required to generate a 2d torus for the + * given number of peers */ unsigned int -GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers, - unsigned int *rows, +GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers, unsigned int *rows, unsigned int **rows_len) { double sq; @@ -348,16 +600,16 @@ GNUNET_TESTBED_2dtorus_calc_links (unsigned int num_peers, unsigned int y; unsigned int _num_peers; unsigned int cnt; - + sq = sqrt (num_peers); sq = floor (sq); sq_floor = (unsigned int) sq; _rows = (sq_floor + 1); - _rows_len = GNUNET_malloc (sizeof (unsigned int) * _rows); + _rows_len = GNUNET_malloc (sizeof (unsigned int) * _rows); for (y = 0; y < _rows - 1; y++) _rows_len[y] = sq_floor; _num_peers = sq_floor * sq_floor; - cnt = 2 * _num_peers; + cnt = (_num_peers < 2) ? _num_peers : 2 * _num_peers; x = 0; y = 0; while (_num_peers < num_peers) @@ -397,28 +649,41 @@ gen_topo_2dtorus (struct TopologyContext *tc) unsigned int cnt; unsigned int offset; - tc->link_array_size = GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows, - &rows_len); - tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) * - tc->link_array_size); + tc->link_array_size = + GNUNET_TESTBED_2dtorus_calc_links (tc->num_peers, &rows, &rows_len); + switch (tc->type) + { + case TOPOLOGYCONTEXT_TYPE_OVERLAY: + { + struct TopologyContextOverlay *overlay; + + overlay = &tc->u.overlay; + overlay->link_array = + GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size); + } + break; + case TOPOLOGYCONTEXT_TYPE_UNDERLAY: + { + struct TopologyContextUnderlay *underlay; + + underlay = &tc->u.underlay; + underlay->link_array = + GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size); + break; + } + } cnt = 0; offset = 0; for (y = 0; y < rows; y++) { for (x = 0; x < rows_len[y] - 1; x++) { - make_link (&tc->link_array[cnt], - offset + x, - offset + x + 1, - tc); + make_link (cnt, offset + x, offset + x + 1, tc); cnt++; } if (0 == x) break; - make_link (&tc->link_array[cnt], - offset + x, - offset, - tc); + make_link (cnt, offset + x, offset, tc); cnt++; offset += rows_len[y]; } @@ -427,22 +692,16 @@ gen_topo_2dtorus (struct TopologyContext *tc) offset = 0; for (y = 0; y < rows - 1; y++) { - if (x == rows_len[y+1]) + if (x >= rows_len[y + 1]) break; - GNUNET_assert (x < rows_len[y+1]); - make_link (&tc->link_array[cnt], - offset + x, - offset + rows_len[y] + x, - tc); + GNUNET_assert (x < rows_len[y + 1]); + make_link (cnt, offset + x, offset + rows_len[y] + x, tc); offset += rows_len[y]; cnt++; } if (0 == offset) break; - make_link (&tc->link_array[cnt], - offset + x, - x, - tc); + make_link (cnt, offset + x, x, tc); cnt++; } GNUNET_assert (cnt == tc->link_array_size); @@ -455,43 +714,81 @@ gen_topo_2dtorus (struct TopologyContext *tc) * * @param tc the topology context * @param links the number of random links to establish - * @param append GNUNET_YES to add links to existing link array; GNUNET_NO to + * @param append #GNUNET_YES to add links to existing link array; #GNUNET_NO to * create a new link array */ static void -gen_topo_random (struct TopologyContext *tc, unsigned int links, int append) +gen_topo_random (struct TopologyContext *tc, + unsigned int links, + int append) { unsigned int cnt; unsigned int index; uint32_t A_rand; uint32_t B_rand; - + + if (1 == tc->num_peers) + return; if (GNUNET_YES == append) { - GNUNET_assert ((0 < tc->link_array_size) && (NULL != tc->link_array)); - index = tc->link_array_size; + index = tc->link_array_size; tc->link_array_size += links; - tc->link_array = GNUNET_realloc (tc->link_array, - sizeof (struct OverlayLink) * - tc->link_array_size); } else { - GNUNET_assert ((0 == tc->link_array_size) && (NULL == tc->link_array)); - index = 0; + index = 0; tc->link_array_size = links; - tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) * - tc->link_array_size); + } + switch (tc->type) + { + case TOPOLOGYCONTEXT_TYPE_OVERLAY: + { + struct TopologyContextOverlay *overlay; + + overlay = &tc->u.overlay; + if (GNUNET_YES != append) + { + GNUNET_assert (NULL == overlay->link_array); + overlay->link_array = + GNUNET_malloc (sizeof (struct OverlayLink) * tc->link_array_size); + break; + } + GNUNET_assert ((0 < tc->link_array_size) && (NULL != overlay->link_array)); + overlay->link_array = + GNUNET_realloc (overlay->link_array, + sizeof (struct OverlayLink) * tc->link_array_size); + break; + } + case TOPOLOGYCONTEXT_TYPE_UNDERLAY: + { + struct TopologyContextUnderlay *underlay; + + underlay = &tc->u.underlay; + if (GNUNET_YES != append) + { + GNUNET_assert (NULL == underlay->link_array); + underlay->link_array = + GNUNET_malloc (sizeof (struct UnderlayLink) * tc->link_array_size); + break; + } + GNUNET_assert ((0 < tc->link_array_size) && (NULL != underlay->link_array)); + underlay->link_array = + GNUNET_realloc (underlay->link_array, + sizeof (struct UnderlayLink) * tc->link_array_size); + break; + } } for (cnt = 0; cnt < links; cnt++) { - do { - A_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, - tc->num_peers); - B_rand = GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, - tc->num_peers); - } while (A_rand == B_rand); - make_link (&tc->link_array[index + cnt], A_rand, B_rand, tc); + do + { + A_rand = + GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers); + B_rand = + GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_WEAK, tc->num_peers); + } + while (A_rand == B_rand); + make_link (index+cnt, A_rand, B_rand, tc); } } @@ -502,44 +799,130 @@ gen_topo_random (struct TopologyContext *tc, unsigned int links, int append) * "Emergence of Scaling in Random Networks." Science 286, 509-512, 1999. * * @param tc the topology context + * @param cap maximum allowed node degree + * @param m number of edges to establish for a new node when it is added to the + * network */ static void -gen_scale_free (struct TopologyContext *tc) +gen_topo_scale_free (struct TopologyContext *tc, + uint16_t cap, + uint8_t m) { - double random; - double probability; + unsigned int *deg; + unsigned int *etab; + unsigned int *used; + unsigned int etaboff; unsigned int cnt; - unsigned int previous_connections; - unsigned int i; - uint16_t *popularity; - - popularity = GNUNET_malloc (sizeof (uint16_t) * tc->num_peers); - /* Initially connect peer 1 to peer 0 */ - tc->link_array_size = 1; - tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink)); - make_link (&tc->link_array[0], 0, 1, tc); - popularity[0]++; /* increase popularity of 0 as 1 connected to it*/ - for (cnt = 1; cnt < tc->num_peers; cnt++) - { - previous_connections = tc->link_array_size; - for (i = 0; i < cnt; i++) - { - probability = ((double) popularity[i]) / ((double) previous_connections); - random = ((double) - GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, - UINT64_MAX)) / ((double) UINT64_MAX); - if (random < probability) + unsigned int cnt2; + unsigned int peer; + unsigned int random_peer; + unsigned int links; + unsigned int off; + unsigned int redo_threshold; + + etaboff = 0; + tc->link_array_size = tc->num_peers * m; + switch (tc->type) + { + case TOPOLOGYCONTEXT_TYPE_OVERLAY: + { + struct TopologyContextOverlay *overlay; + + overlay = &tc->u.overlay; + overlay->link_array = GNUNET_malloc_large (sizeof (struct OverlayLink) * + tc->link_array_size); + } + break; + case TOPOLOGYCONTEXT_TYPE_UNDERLAY: + { + struct TopologyContextUnderlay *underlay; + + underlay = &tc->u.underlay; + underlay->link_array = GNUNET_malloc_large (sizeof (struct UnderlayLink) * + tc->link_array_size); + } + break; + } + etab = GNUNET_malloc_large (sizeof (unsigned int) * 2 * tc->link_array_size); + deg = GNUNET_malloc (sizeof (unsigned int) * tc->num_peers); + used = GNUNET_malloc (sizeof (unsigned int) * m); + /* start by connecting peer 1 to peer 0 */ + make_link (0, 0, 1, tc); + deg[0]++; + deg[1]++; + etab[etaboff++] = 0; + etab[etaboff++] = 1; + links = 1; + for (peer = 2; peer < tc->num_peers; peer++) + { + if (cap < deg[peer]) + continue; + for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++) + { + redo_threshold = 0; + redo: + off = GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, etaboff); + random_peer = etab[off]; + if (cap < deg[random_peer]) { - tc->link_array_size++; - tc->link_array = GNUNET_realloc (tc->link_array, - (sizeof (struct OverlayLink) * - tc->link_array_size)); - make_link (&tc->link_array[tc->link_array_size - 1], cnt, i, tc); - popularity[cnt]++; + if (++redo_threshold > GNUNET_MAX (1, cap / 2)) + { + redo_threshold = 0; + off = 0; + for (cnt2 = 0; cnt2 < etaboff; cnt2++) + { + if (random_peer == etab[cnt2]) + { + off++; + continue; + } + etab[cnt2 - off] = etab[cnt2]; + } + etaboff -= off; + } + goto redo; } + for (cnt2 = 0; cnt2 < cnt; cnt2++) + if (random_peer == used[cnt2]) + goto redo; + make_link (links + cnt, random_peer, peer, tc); + deg[random_peer]++; + deg[peer]++; + used[cnt] = random_peer; } + for (cnt = 0; cnt < GNUNET_MIN (peer, m); cnt++) + { + etab[etaboff++] = used[cnt]; + etab[etaboff++] = peer; + } + links += GNUNET_MIN (peer, m); + } + GNUNET_free (etab); + GNUNET_free (used); + GNUNET_free (deg); + GNUNET_assert (links <= tc->link_array_size); + tc->link_array_size = links; + switch (tc->type) + { + case TOPOLOGYCONTEXT_TYPE_OVERLAY: + { + struct TopologyContextOverlay *overlay; + + overlay = &tc->u.overlay; + overlay->link_array = + GNUNET_realloc (overlay->link_array, sizeof (struct OverlayLink) * tc->link_array_size); + } + break; + case TOPOLOGYCONTEXT_TYPE_UNDERLAY: + { + struct TopologyContextUnderlay *underlay; + + underlay = &tc->u.underlay; + underlay->link_array = + GNUNET_realloc (underlay->link_array, sizeof (struct UnderlayLink) * tc->link_array_size); + } + break; } - GNUNET_free (popularity); } @@ -550,7 +933,8 @@ gen_scale_free (struct TopologyContext *tc) * @param filename the filename of the file containing topology data */ static void -gen_topo_from_file (struct TopologyContext *tc, const char *filename) +gen_topo_from_file (struct TopologyContext *tc, + const char *filename) { char *data; char *end; @@ -559,8 +943,9 @@ gen_topo_from_file (struct TopologyContext *tc, const char *filename) uint64_t offset; unsigned long int peer_id; unsigned long int other_peer_id; - enum ParseState { - + enum ParseState + { + /** * We read the peer index */ @@ -577,19 +962,24 @@ gen_topo_from_file (struct TopologyContext *tc, const char *filename) status = GNUNET_SYSERR; if (GNUNET_YES != GNUNET_DISK_file_test (filename)) { - LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s not found\n"), filename); + LOG (GNUNET_ERROR_TYPE_ERROR, + _("Topology file %s not found\n"), + filename); return; } if (GNUNET_OK != GNUNET_DISK_file_size (filename, &fs, GNUNET_YES, GNUNET_YES)) { - LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s has no data\n"), filename); + LOG (GNUNET_ERROR_TYPE_ERROR, + _("Topology file %s has no data\n"), + filename); return; } data = GNUNET_malloc (fs); if (fs != GNUNET_DISK_fn_read (filename, data, fs)) { - LOG (GNUNET_ERROR_TYPE_ERROR, _("Topology file %s cannot be read\n"), + LOG (GNUNET_ERROR_TYPE_ERROR, + _("Topology file %s cannot be read\n"), filename); goto _exit; } @@ -597,7 +987,6 @@ gen_topo_from_file (struct TopologyContext *tc, const char *filename) offset = 0; peer_id = 0; state = PEER_INDEX; - buf = data; while (offset < fs) { if (0 != isspace (data[offset])) @@ -633,8 +1022,7 @@ gen_topo_from_file (struct TopologyContext *tc, const char *filename) if (tc->num_peers <= peer_id) { LOG (GNUNET_ERROR_TYPE_ERROR, - _("Topology file need more peers than the given ones\n"), - filename); + _("Topology file needs more peers than given ones\n"), filename); goto _exit; } state = OTHER_PEER_INDEX; @@ -642,7 +1030,7 @@ gen_topo_from_file (struct TopologyContext *tc, const char *filename) break; case OTHER_PEER_INDEX: errno = 0; - other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10); + other_peer_id = (unsigned int) strtoul (&data[offset], &end, 10); if (0 != errno) { LOG (GNUNET_ERROR_TYPE_ERROR, @@ -658,19 +1046,44 @@ gen_topo_from_file (struct TopologyContext *tc, const char *filename) if (tc->num_peers <= other_peer_id) { LOG (GNUNET_ERROR_TYPE_ERROR, - _("Topology file need more peers than the given ones\n"), - filename); + _("Topology file needs more peers than given ones\n"), filename); goto _exit; } - tc->link_array_size++; - tc->link_array = GNUNET_realloc (tc->link_array, - sizeof (struct OverlayLink) * - tc->link_array_size); - offset += end - &data[offset]; - make_link (&tc->link_array[tc->link_array_size - 1], peer_id, - other_peer_id, tc); - while (('\n' != data[offset]) && ('|' != data[offset]) - && (offset < fs)) + if (peer_id != other_peer_id) + { + tc->link_array_size++; + switch (tc->type) + { + case TOPOLOGYCONTEXT_TYPE_OVERLAY: + { + struct TopologyContextOverlay *overlay; + + overlay = &tc->u.overlay; + overlay->link_array = + GNUNET_realloc (overlay->link_array, + sizeof (struct OverlayLink) * tc->link_array_size); + } + break; + case TOPOLOGYCONTEXT_TYPE_UNDERLAY: + { + struct TopologyContextUnderlay *underlay; + + underlay = &tc->u.underlay; + underlay->link_array = + GNUNET_realloc (underlay->link_array, + sizeof (struct UnderlayLink) * tc->link_array_size); + } + break; + } + offset += end - &data[offset]; + make_link (tc->link_array_size - 1, peer_id, other_peer_id, tc); + } + else + LOG (GNUNET_ERROR_TYPE_WARNING, + _("Ignoring to connect peer %u to peer %u\n"), + peer_id, + other_peer_id); + while (('\n' != data[offset]) && ('|' != data[offset]) && (offset < fs)) offset++; if ('\n' == data[offset]) state = PEER_INDEX; @@ -683,16 +1096,82 @@ gen_topo_from_file (struct TopologyContext *tc, const char *filename) } } status = GNUNET_OK; - - _exit: + +_exit: GNUNET_free (data); if (GNUNET_OK != status) { LOG (GNUNET_ERROR_TYPE_WARNING, - "Removing and link data read from the file\n"); + "Removing link data read from the file\n"); tc->link_array_size = 0; - GNUNET_free_non_null (tc->link_array); - tc->link_array = NULL; + switch (tc->type) + { + case TOPOLOGYCONTEXT_TYPE_OVERLAY: + { + struct TopologyContextOverlay *overlay; + + overlay = &tc->u.overlay; + GNUNET_free_non_null (overlay->link_array); + overlay->link_array = NULL; + } + break; + case TOPOLOGYCONTEXT_TYPE_UNDERLAY: + { + struct TopologyContextUnderlay *underlay; + + underlay = &tc->u.underlay; + GNUNET_free_non_null (underlay->link_array); + underlay->link_array = NULL; + } + break; + } + } +} + + +/** + * Generates clique topology + * + * @param tc the topology context + */ +static void +gen_topo_clique (struct TopologyContext *tc) +{ + unsigned int cnt; + unsigned int offset; + unsigned int neighbour; + + tc->link_array_size = tc->num_peers * (tc->num_peers - 1); + switch (tc->type) + { + case TOPOLOGYCONTEXT_TYPE_OVERLAY: + { + struct TopologyContextOverlay *overlay; + + overlay = &tc->u.overlay; + overlay->link_array = GNUNET_new_array (tc->link_array_size, + struct OverlayLink); + } + break; + case TOPOLOGYCONTEXT_TYPE_UNDERLAY: + { + struct TopologyContextUnderlay *underlay; + + underlay = &tc->u.underlay; + underlay->link_array = GNUNET_new_array (tc->link_array_size, + struct UnderlayLink); + } + } + offset = 0; + for (cnt = 0; cnt < tc->num_peers; cnt++) + { + for (neighbour = 0; neighbour < tc->num_peers; neighbour++) + { + if (neighbour == cnt) + continue; + make_link (offset, cnt, neighbour, tc); + offset++; + } } } @@ -701,8 +1180,8 @@ gen_topo_from_file (struct TopologyContext *tc, const char *filename) * Configure overall network topology to have a particular shape. * * @param op_cls closure argument to give with the operation event - * @param num_peers number of peers in 'peers' - * @param peers array of 'num_peers' with the peers to configure + * @param num_peers number of peers in @a peers + * @param peers array of @a num_peers with the peers to configure * @param topo desired underlay topology to use * @param ap topology-specific options * @return handle to the operation, NULL if configuring the topology @@ -726,8 +1205,8 @@ GNUNET_TESTBED_underlay_configure_topology_va (void *op_cls, * Configure overall network topology to have a particular shape. * * @param op_cls closure argument to give with the operation event - * @param num_peers number of peers in 'peers' - * @param peers array of 'num_peers' with the peers to configure + * @param num_peers number of peers in @a peers + * @param peers array of @a num_peers with the peers to configure * @param topo desired underlay topology to use * @param ... topology-specific options * @return handle to the operation, NULL if configuring the topology @@ -750,11 +1229,15 @@ GNUNET_TESTBED_underlay_configure_topology (void *op_cls, * This function then connects the given peers in the P2P overlay * using the given topology. * - * @param op_cls closure argument to give with the operation event - * @param num_peers number of peers in 'peers' - * @param peers array of 'num_peers' with the peers to configure + * @param op_cls closure argument to give with the peer connect operation events + * generated through this function + * @param num_peers number of peers in @a peers + * @param peers array of @a num_peers with the peers to configure * @param max_connections the maximums number of overlay connections that will * be made to achieve the given topology + * @param comp_cb the completion callback to call when the topology generation + * is completed + * @param comp_cb_cls closure for the above completion callback * @param topo desired underlay topology to use * @param va topology-specific options * @return handle to the operation, NULL if connecting these @@ -766,22 +1249,30 @@ GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls, unsigned int num_peers, struct GNUNET_TESTBED_Peer **peers, unsigned int *max_connections, - enum GNUNET_TESTBED_TopologyOption - topo, va_list va) + GNUNET_TESTBED_TopologyCompletionCallback + comp_cb, + void *comp_cb_cls, + enum GNUNET_TESTBED_TopologyOption topo, + va_list va) { struct TopologyContext *tc; + struct TopologyContextOverlay *overlay; struct GNUNET_TESTBED_Operation *op; struct GNUNET_TESTBED_Controller *c; enum GNUNET_TESTBED_TopologyOption secondary_option; - unsigned int cnt; if (num_peers < 2) return NULL; c = peers[0]->controller; - tc = GNUNET_malloc (sizeof (struct TopologyContext)); - tc->peers = peers; + tc = GNUNET_new (struct TopologyContext); + tc->type = TOPOLOGYCONTEXT_TYPE_OVERLAY; + overlay = &tc->u.overlay; + overlay->peers = peers; tc->num_peers = num_peers; - tc->op_cls = op_cls; + overlay->op_cls = op_cls; + overlay->retry_cnt = DEFAULT_RETRY_CNT; + overlay->comp_cb = comp_cb; + overlay->comp_cb_cls = comp_cb_cls; switch (topo) { case GNUNET_TESTBED_TOPOLOGY_LINE: @@ -791,61 +1282,43 @@ GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls, gen_topo_ring (tc); break; case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI: - gen_topo_random (tc, - va_arg (va, unsigned int), - GNUNET_NO); + gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_NO); break; case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING: gen_topo_ring (tc); - gen_topo_random (tc, - va_arg (va, unsigned int), - GNUNET_YES); + gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES); break; case GNUNET_TESTBED_TOPOLOGY_CLIQUE: - tc->link_array_size = num_peers * (num_peers - 1); - tc->link_array = GNUNET_malloc (sizeof (struct OverlayLink) * - tc->link_array_size); - { - unsigned int offset; - - offset = 0; - for (cnt=0; cnt < num_peers; cnt++) - { - unsigned int neighbour; - - for (neighbour=0; neighbour < num_peers; neighbour++) - { - if (neighbour == cnt) - continue; - tc->link_array[offset].A = cnt; - tc->link_array[offset].B = neighbour; - tc->link_array[offset].tc = tc; - offset++; - } - } - } + gen_topo_clique (tc); break; case GNUNET_TESTBED_TOPOLOGY_2D_TORUS: gen_topo_2dtorus (tc); break; case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD: gen_topo_2dtorus (tc); - gen_topo_random (tc, - va_arg (va, unsigned int), - GNUNET_YES); + gen_topo_random (tc, va_arg (va, unsigned int), GNUNET_YES); + break; case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE: - gen_scale_free (tc); - break; - case GNUNET_TESTBED_TOPOLOGY_FROM_FILE: { - const char *filename; - - filename = va_arg (va, const char *); - GNUNET_assert (NULL != filename); - gen_topo_from_file (tc, filename); + uint16_t cap; + uint8_t m; + + cap = (uint16_t) va_arg (va, unsigned int); + m = (uint8_t) va_arg (va, unsigned int); + gen_topo_scale_free (tc, cap, m); } break; + case GNUNET_TESTBED_TOPOLOGY_FROM_FILE: + { + const char *filename; + + filename = va_arg (va, const char *); + + GNUNET_assert (NULL != filename); + gen_topo_from_file (tc, filename); + } + break; default: GNUNET_break (0); GNUNET_free (tc); @@ -854,29 +1327,32 @@ GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls, do { secondary_option = va_arg (va, enum GNUNET_TESTBED_TopologyOption); + switch (secondary_option) { - case GNUNET_TESTBED_TOPOLOGY_DISABLE_AUTO_RETRY: - tc->disable_retry = GNUNET_YES; + case GNUNET_TESTBED_TOPOLOGY_RETRY_CNT: + overlay->retry_cnt = va_arg (va, unsigned int); break; case GNUNET_TESTBED_TOPOLOGY_OPTION_END: break; default: GNUNET_break (0); /* Should not use any other option apart from - the ones handled here */ - GNUNET_free_non_null (tc->link_array); + * the ones handled here */ + GNUNET_free_non_null (overlay->link_array); GNUNET_free (tc); return NULL; } - } while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option); + } + while (GNUNET_TESTBED_TOPOLOGY_OPTION_END != secondary_option); op = GNUNET_TESTBED_operation_create_ (tc, - &opstart_overlay_configure_topology, - &oprelease_overlay_configure_topology); + &opstart_overlay_configure_topology, + &oprelease_overlay_configure_topology); GNUNET_TESTBED_operation_queue_insert_ (c->opq_parallel_topology_config_operations, op); GNUNET_TESTBED_operation_begin_wait_ (op); LOG (GNUNET_ERROR_TYPE_DEBUG, - "Generated %u connections\n", tc->link_array_size); + "Generated %u connections\n", + tc->link_array_size); if (NULL != max_connections) *max_connections = tc->link_array_size; return op; @@ -888,11 +1364,15 @@ GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls, * This function then connects the given peers in the P2P overlay * using the given topology. * - * @param op_cls closure argument to give with the operation event + * @param op_cls closure argument to give with the peer connect operation events + * generated through this function * @param num_peers number of peers in 'peers' * @param peers array of 'num_peers' with the peers to configure * @param max_connections the maximums number of overlay connections that will * be made to achieve the given topology + * @param comp_cb the completion callback to call when the topology generation + * is completed + * @param comp_cb_cls closure for the above completion callback * @param topo desired underlay topology to use * @param ... topology-specific options * @return handle to the operation, NULL if connecting these @@ -900,11 +1380,15 @@ GNUNET_TESTBED_overlay_configure_topology_va (void *op_cls, * not running or underlay disallows) or if num_peers is less than 2 */ struct GNUNET_TESTBED_Operation * -GNUNET_TESTBED_overlay_configure_topology (void *op_cls, unsigned int num_peers, +GNUNET_TESTBED_overlay_configure_topology (void *op_cls, + unsigned int num_peers, struct GNUNET_TESTBED_Peer **peers, unsigned int *max_connections, - enum GNUNET_TESTBED_TopologyOption - topo, ...) + GNUNET_TESTBED_TopologyCompletionCallback + comp_cb, + void *comp_cb_cls, + enum GNUNET_TESTBED_TopologyOption topo, + ...) { struct GNUNET_TESTBED_Operation *op; va_list vargs; @@ -912,8 +1396,10 @@ GNUNET_TESTBED_overlay_configure_topology (void *op_cls, unsigned int num_peers, GNUNET_assert (topo < GNUNET_TESTBED_TOPOLOGY_OPTION_END); va_start (vargs, topo); op = GNUNET_TESTBED_overlay_configure_topology_va (op_cls, num_peers, peers, - max_connections, - topo, vargs); + max_connections, + comp_cb, comp_cb_cls, + topo, + vargs); va_end (vargs); return op; } @@ -925,13 +1411,13 @@ GNUNET_TESTBED_overlay_configure_topology (void *op_cls, unsigned int num_peers, * @param topology where to write the retrieved topology * @param topology_string The string to attempt to * get a configuration value from - * @return GNUNET_YES if topology string matched a - * known topology, GNUNET_NO if not + * @return #GNUNET_YES if topology string matched a + * known topology, #GNUNET_NO if not */ int GNUNET_TESTBED_topology_get_ (enum GNUNET_TESTBED_TopologyOption *topology, const char *topology_string) -{ +{ unsigned int cnt; for (cnt = 0; NULL != topology_strings[cnt]; cnt++) @@ -962,4 +1448,107 @@ GNUNET_TESTBED_topology_to_str_ (enum GNUNET_TESTBED_TopologyOption topology) return GNUNET_strdup (topology_strings[topology]); } + +/** + * Function to construct an underlay topology + * + * @param num_peers the number of peers for which the topology should be + * generated + * @param proc the underlay link processor callback. Will be called for each + * underlay link generated unless a previous call to this callback + * returned #GNUNET_SYSERR. Cannot be NULL. + * @param cls closure for @a proc + * @param ... variable arguments denoting the topology and its parameters. They + * should start with the type of topology to generate followed by their + * options. + * @return #GNUNET_OK if underlay link generation is successful; #GNUNET_SYSERR + * upon error in generating the underlay or if any calls to the + * underlay link processor returned #GNUNET_SYSERR + */ +int +GNUNET_TESTBED_underlay_construct_ (int num_peers, + underlay_link_processor proc, + void *cls, + ...) +{ + struct TopologyContext tc; + struct TopologyContextUnderlay *underlay; + struct UnderlayLink *ulink; + va_list vargs; + enum GNUNET_TESTBED_TopologyOption topology; + unsigned int cnt; + int ret; + + GNUNET_assert (NULL != proc); + ret = GNUNET_OK; + memset (&tc, 0, sizeof (tc)); + tc.num_peers = num_peers; + tc.type = TOPOLOGYCONTEXT_TYPE_UNDERLAY; + underlay = &tc.u.underlay; + va_start (vargs, cls); + topology = va_arg (vargs, enum GNUNET_TESTBED_TopologyOption); + switch (topology) + { + case GNUNET_TESTBED_TOPOLOGY_LINE: + gen_topo_line (&tc); + break; + case GNUNET_TESTBED_TOPOLOGY_RING: + gen_topo_ring (&tc); + break; + case GNUNET_TESTBED_TOPOLOGY_CLIQUE: + gen_topo_clique (&tc); + break; + case GNUNET_TESTBED_TOPOLOGY_2D_TORUS: + gen_topo_2dtorus (&tc); + break; + case GNUNET_TESTBED_TOPOLOGY_ERDOS_RENYI: + gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_NO); + break; + case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD_RING: + gen_topo_ring (&tc); + gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES); + break; + case GNUNET_TESTBED_TOPOLOGY_SMALL_WORLD: + gen_topo_2dtorus (&tc); + gen_topo_random (&tc, va_arg (vargs, unsigned int), GNUNET_YES); + break; + case GNUNET_TESTBED_TOPOLOGY_FROM_FILE: + { + const char *filename; + filename = va_arg (vargs, char *); + GNUNET_assert (NULL != filename); + gen_topo_from_file (&tc, filename); + } + break; + case GNUNET_TESTBED_TOPOLOGY_SCALE_FREE: + { + uint16_t cap; + uint8_t m; + cap = (uint16_t) va_arg (vargs, unsigned int); + m = (uint8_t) va_arg (vargs, unsigned int); + gen_topo_scale_free (&tc, cap, m); + } + break; + default: + GNUNET_assert (0); + } + va_end (vargs); + for (cnt = 0; cnt < tc.link_array_size; cnt++) + { + ulink = &underlay->link_array[cnt]; + if (GNUNET_SYSERR == proc (cls, + ulink->A, + ulink->B, + ulink->bandwidth, + ulink->latency, + ulink->loss)) + { + ret = GNUNET_SYSERR; + break; + } + } + GNUNET_free_non_null (underlay->link_array); + return ret; +} + /* end of testbed_api_topology.c */