diff options
author | Nathan S. Evans <evans@in.tum.de> | 2010-05-10 12:48:47 +0000 |
---|---|---|
committer | Nathan S. Evans <evans@in.tum.de> | 2010-05-10 12:48:47 +0000 |
commit | af7d13f4f43d04c821b2bc70ec65a0900d65159b (patch) | |
tree | 8dc9b2ce17551161a76cb5ead3ca29e300e03ec3 /src/testing | |
parent | a1acd8d8d89a86b7c5e18624eec0e1811f22a0a1 (diff) | |
download | gnunet-af7d13f4f43d04c821b2bc70ec65a0900d65159b.tar.gz gnunet-af7d13f4f43d04c821b2bc70ec65a0900d65159b.zip |
depth first peer adding, non-null check for peer lists
Diffstat (limited to 'src/testing')
-rw-r--r-- | src/testing/testing_group.c | 197 |
1 files changed, 190 insertions, 7 deletions
diff --git a/src/testing/testing_group.c b/src/testing/testing_group.c index d4122a98d..57cea8007 100644 --- a/src/testing/testing_group.c +++ b/src/testing/testing_group.c | |||
@@ -164,7 +164,8 @@ struct PeerData | |||
164 | struct GNUNET_CONTAINER_MultiHashMap *connect_peers_working_set; | 164 | struct GNUNET_CONTAINER_MultiHashMap *connect_peers_working_set; |
165 | 165 | ||
166 | /** | 166 | /** |
167 | * Total number of connections this peer has | 167 | * Temporary variable for topology creation, should be reset before |
168 | * creating any topology so the count is valid once finished. | ||
168 | */ | 169 | */ |
169 | int num_connections; | 170 | int num_connections; |
170 | }; | 171 | }; |
@@ -423,12 +424,14 @@ add_actual_connections(struct GNUNET_TESTING_PeerGroup *pg, unsigned int first, | |||
423 | if (add_first) | 424 | if (add_first) |
424 | { | 425 | { |
425 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(pg->peers[first].connect_peers, &hash_second, pg->peers[second].daemon, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | 426 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(pg->peers[first].connect_peers, &hash_second, pg->peers[second].daemon, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); |
427 | pg->peers[first].num_connections++; | ||
426 | added++; | 428 | added++; |
427 | } | 429 | } |
428 | 430 | ||
429 | if (add_second) | 431 | if (add_second) |
430 | { | 432 | { |
431 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(pg->peers[second].connect_peers, &hash_first, pg->peers[first].daemon, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | 433 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(pg->peers[second].connect_peers, &hash_first, pg->peers[first].daemon, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); |
434 | pg->peers[second].num_connections++; | ||
432 | added++; | 435 | added++; |
433 | } | 436 | } |
434 | 437 | ||
@@ -507,8 +510,8 @@ add_allowed_connections(struct GNUNET_TESTING_PeerGroup *pg, unsigned int first, | |||
507 | new_first->daemon = pg->peers[second].daemon; | 510 | new_first->daemon = pg->peers[second].daemon; |
508 | new_first->next = pg->peers[first].connected_peers; | 511 | new_first->next = pg->peers[first].connected_peers; |
509 | pg->peers[first].connected_peers = new_first; | 512 | pg->peers[first].connected_peers = new_first; |
510 | pg->peers[first].num_connections++; | ||
511 | #endif | 513 | #endif |
514 | pg->peers[first].num_connections++; | ||
512 | added++; | 515 | added++; |
513 | } | 516 | } |
514 | 517 | ||
@@ -522,6 +525,7 @@ add_allowed_connections(struct GNUNET_TESTING_PeerGroup *pg, unsigned int first, | |||
522 | pg->peers[second].connected_peers = new_second; | 525 | pg->peers[second].connected_peers = new_second; |
523 | pg->peers[first].num_connections++; | 526 | pg->peers[first].num_connections++; |
524 | #endif | 527 | #endif |
528 | pg->peers[second].num_connections++; | ||
525 | added++; | 529 | added++; |
526 | } | 530 | } |
527 | 531 | ||
@@ -566,12 +570,14 @@ blacklist_connections(struct GNUNET_TESTING_PeerGroup *pg, unsigned int first, u | |||
566 | if (add_first) | 570 | if (add_first) |
567 | { | 571 | { |
568 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(pg->peers[first].blacklisted_peers, &hash_second, pg->peers[second].daemon, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | 572 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(pg->peers[first].blacklisted_peers, &hash_second, pg->peers[second].daemon, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); |
573 | pg->peers[first].num_connections++; | ||
569 | added++; | 574 | added++; |
570 | } | 575 | } |
571 | 576 | ||
572 | if (add_second) | 577 | if (add_second) |
573 | { | 578 | { |
574 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(pg->peers[second].blacklisted_peers, &hash_first, pg->peers[first].daemon, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | 579 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(pg->peers[second].blacklisted_peers, &hash_first, pg->peers[first].daemon, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); |
580 | pg->peers[second].num_connections++; | ||
575 | added++; | 581 | added++; |
576 | } | 582 | } |
577 | 583 | ||
@@ -1917,6 +1923,39 @@ struct MinimumContext | |||
1917 | unsigned int current; | 1923 | unsigned int current; |
1918 | }; | 1924 | }; |
1919 | 1925 | ||
1926 | struct DFSContext | ||
1927 | { | ||
1928 | /** | ||
1929 | * The peergroup | ||
1930 | */ | ||
1931 | struct GNUNET_TESTING_PeerGroup *pg; | ||
1932 | |||
1933 | /** | ||
1934 | * uid of the first peer | ||
1935 | */ | ||
1936 | uint32_t first_uid; | ||
1937 | |||
1938 | /** | ||
1939 | * uid of the second peer | ||
1940 | */ | ||
1941 | uint32_t second_uid; | ||
1942 | |||
1943 | /** | ||
1944 | * Peer data for first peer. | ||
1945 | */ | ||
1946 | struct PeerData *first; | ||
1947 | |||
1948 | /** | ||
1949 | * Which peer has been chosen as the one to add? | ||
1950 | */ | ||
1951 | unsigned int chosen; | ||
1952 | |||
1953 | /** | ||
1954 | * What number is the current element we are iterating over? | ||
1955 | */ | ||
1956 | unsigned int current; | ||
1957 | }; | ||
1958 | |||
1920 | /** | 1959 | /** |
1921 | * Iterator for choosing random peers to connect. | 1960 | * Iterator for choosing random peers to connect. |
1922 | * | 1961 | * |
@@ -1975,7 +2014,6 @@ minimum_connect_iterator (void *cls, | |||
1975 | { | 2014 | { |
1976 | if (min_ctx->pg_array[i] == min_ctx->current) | 2015 | if (min_ctx->pg_array[i] == min_ctx->current) |
1977 | { | 2016 | { |
1978 | fprintf(stderr, "Adding another peer, hashmap size %u, minimum %u\n", GNUNET_CONTAINER_multihashmap_size(min_ctx->first->connect_peers_working_set), min_ctx->num_to_add); | ||
1979 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(min_ctx->first->connect_peers_working_set, key, value, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | 2017 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(min_ctx->first->connect_peers_working_set, key, value, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); |
1980 | uid_from_hash(key, &second_pos); | 2018 | uid_from_hash(key, &second_pos); |
1981 | hash_from_uid(min_ctx->first_uid, &first_hash); | 2019 | hash_from_uid(min_ctx->first_uid, &first_hash); |
@@ -1993,6 +2031,40 @@ minimum_connect_iterator (void *cls, | |||
1993 | 2031 | ||
1994 | } | 2032 | } |
1995 | 2033 | ||
2034 | |||
2035 | /** | ||
2036 | * Iterator for adding peers to a connection set based on a depth first search. | ||
2037 | * | ||
2038 | * @param cls closure, MinimumContext | ||
2039 | * @param key the key the second daemon was stored under | ||
2040 | * @param value the GNUNET_TESTING_Daemon that the first is to connect to | ||
2041 | * | ||
2042 | * @return GNUNET_YES to continue iteration | ||
2043 | */ | ||
2044 | static int | ||
2045 | dfs_connect_iterator (void *cls, | ||
2046 | const GNUNET_HashCode * key, | ||
2047 | void *value) | ||
2048 | { | ||
2049 | struct DFSContext *dfs_ctx = cls; | ||
2050 | GNUNET_HashCode first_hash; | ||
2051 | |||
2052 | if (dfs_ctx->current == dfs_ctx->chosen) | ||
2053 | { | ||
2054 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(dfs_ctx->first->connect_peers_working_set, key, value, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
2055 | uid_from_hash(key, &dfs_ctx->second_uid); | ||
2056 | hash_from_uid(dfs_ctx->first_uid, &first_hash); | ||
2057 | GNUNET_assert(GNUNET_OK == GNUNET_CONTAINER_multihashmap_put(dfs_ctx->pg->peers[dfs_ctx->second_uid].connect_peers_working_set, &first_hash, dfs_ctx->first->daemon, GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
2058 | GNUNET_assert(GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove(dfs_ctx->pg->peers[dfs_ctx->second_uid].connect_peers, &first_hash, dfs_ctx->first->daemon)); | ||
2059 | /* Can't remove second from first yet because we are currently iterating, hence the return value in the DFSContext! */ | ||
2060 | return GNUNET_NO; /* We have found our peer, don't iterate more */ | ||
2061 | } | ||
2062 | |||
2063 | dfs_ctx->current++; | ||
2064 | return GNUNET_YES; | ||
2065 | } | ||
2066 | |||
2067 | |||
1996 | /** | 2068 | /** |
1997 | * From the set of connections possible, choose percentage percent of connections | 2069 | * From the set of connections possible, choose percentage percent of connections |
1998 | * to actually connect. | 2070 | * to actually connect. |
@@ -2011,6 +2083,7 @@ choose_random_connections(struct GNUNET_TESTING_PeerGroup *pg, double percentage | |||
2011 | random_ctx.first_uid = pg_iter; | 2083 | random_ctx.first_uid = pg_iter; |
2012 | random_ctx.first = &pg->peers[pg_iter]; | 2084 | random_ctx.first = &pg->peers[pg_iter]; |
2013 | random_ctx.percentage = percentage; | 2085 | random_ctx.percentage = percentage; |
2086 | random_ctx.pg = pg; | ||
2014 | pg->peers[pg_iter].connect_peers_working_set = GNUNET_CONTAINER_multihashmap_create(pg->total); | 2087 | pg->peers[pg_iter].connect_peers_working_set = GNUNET_CONTAINER_multihashmap_create(pg->total); |
2015 | GNUNET_CONTAINER_multihashmap_iterate(pg->peers[pg_iter].connect_peers, &random_connect_iterator, &random_ctx); | 2088 | GNUNET_CONTAINER_multihashmap_iterate(pg->peers[pg_iter].connect_peers, &random_connect_iterator, &random_ctx); |
2016 | /* Now remove the old connections */ | 2089 | /* Now remove the old connections */ |
@@ -2062,6 +2135,113 @@ choose_minimum(struct GNUNET_TESTING_PeerGroup *pg, unsigned int num) | |||
2062 | } | 2135 | } |
2063 | 2136 | ||
2064 | 2137 | ||
2138 | static unsigned int count_workingset_connections(struct GNUNET_TESTING_PeerGroup *pg) | ||
2139 | { | ||
2140 | unsigned int count; | ||
2141 | unsigned int pg_iter; | ||
2142 | |||
2143 | count = 0; | ||
2144 | |||
2145 | for (pg_iter = 0; pg_iter < pg->total; pg_iter++) | ||
2146 | { | ||
2147 | count += GNUNET_CONTAINER_multihashmap_size(pg->peers[pg_iter].connect_peers_working_set); | ||
2148 | } | ||
2149 | |||
2150 | return count; | ||
2151 | } | ||
2152 | |||
2153 | |||
2154 | static unsigned int count_allowed_connections(struct GNUNET_TESTING_PeerGroup *pg) | ||
2155 | { | ||
2156 | unsigned int count; | ||
2157 | unsigned int pg_iter; | ||
2158 | |||
2159 | count = 0; | ||
2160 | |||
2161 | for (pg_iter = 0; pg_iter < pg->total; pg_iter++) | ||
2162 | { | ||
2163 | count += GNUNET_CONTAINER_multihashmap_size(pg->peers[pg_iter].connect_peers); | ||
2164 | } | ||
2165 | |||
2166 | return count; | ||
2167 | } | ||
2168 | |||
2169 | /** | ||
2170 | * From the set of connections possible, choose at least num connections per | ||
2171 | * peer based on depth first traversal of peer connections. If DFS leaves | ||
2172 | * peers unconnected, ensure those peers get connections. | ||
2173 | * | ||
2174 | * @param pg the peergroup we are dealing with | ||
2175 | * @param num how many connections at least should each peer have (if possible)? | ||
2176 | */ | ||
2177 | void | ||
2178 | perform_dfs (struct GNUNET_TESTING_PeerGroup *pg, unsigned int num) | ||
2179 | { | ||
2180 | struct DFSContext dfs_ctx; | ||
2181 | uint32_t pg_iter; | ||
2182 | uint32_t dfs_count; | ||
2183 | uint32_t starting_peer; | ||
2184 | uint32_t least_connections; | ||
2185 | GNUNET_HashCode second_hash; | ||
2186 | |||
2187 | for (pg_iter = 0; pg_iter < pg->total; pg_iter++) | ||
2188 | { | ||
2189 | pg->peers[pg_iter].connect_peers_working_set = GNUNET_CONTAINER_multihashmap_create(num); | ||
2190 | } | ||
2191 | |||
2192 | starting_peer = 0; | ||
2193 | dfs_count = 0; | ||
2194 | while ((count_workingset_connections(pg) < num * pg->total) && (count_allowed_connections(pg) > 0)) | ||
2195 | { | ||
2196 | if (dfs_count % pg->total == 0) /* Restart the DFS at some weakly connected peer */ | ||
2197 | { | ||
2198 | least_connections = -1; /* Set to very high number */ | ||
2199 | for (pg_iter = 0; pg_iter < pg->total; pg_iter++) | ||
2200 | { | ||
2201 | if (GNUNET_CONTAINER_multihashmap_size(pg->peers[pg_iter].connect_peers_working_set) < least_connections) | ||
2202 | { | ||
2203 | starting_peer = pg_iter; | ||
2204 | least_connections = GNUNET_CONTAINER_multihashmap_size(pg->peers[pg_iter].connect_peers_working_set); | ||
2205 | } | ||
2206 | } | ||
2207 | } | ||
2208 | |||
2209 | if (GNUNET_CONTAINER_multihashmap_size(pg->peers[starting_peer].connect_peers) == 0) /* Ensure there is at least one peer left to connect! */ | ||
2210 | { | ||
2211 | dfs_count = 0; | ||
2212 | continue; | ||
2213 | } | ||
2214 | |||
2215 | /* Choose a random peer from the chosen peers set of connections to add */ | ||
2216 | dfs_ctx.chosen = GNUNET_CRYPTO_random_u32(GNUNET_CRYPTO_QUALITY_WEAK, GNUNET_CONTAINER_multihashmap_size(pg->peers[starting_peer].connect_peers)); | ||
2217 | dfs_ctx.first_uid = starting_peer; | ||
2218 | dfs_ctx.first = &pg->peers[starting_peer]; | ||
2219 | dfs_ctx.pg = pg; | ||
2220 | dfs_ctx.current = 0; | ||
2221 | |||
2222 | GNUNET_CONTAINER_multihashmap_iterate(pg->peers[starting_peer].connect_peers, &dfs_connect_iterator, &dfs_ctx); | ||
2223 | /* Remove the second from the first, since we will be continuing the search and may encounter the first peer again! */ | ||
2224 | hash_from_uid(dfs_ctx.second_uid, &second_hash); | ||
2225 | GNUNET_assert(GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove(pg->peers[starting_peer].connect_peers, &second_hash, pg->peers[dfs_ctx.second_uid].daemon)); | ||
2226 | starting_peer = dfs_ctx.second_uid; | ||
2227 | } | ||
2228 | |||
2229 | for (pg_iter = 0; pg_iter < pg->total; pg_iter++) | ||
2230 | { | ||
2231 | |||
2232 | } | ||
2233 | |||
2234 | for (pg_iter = 0; pg_iter < pg->total; pg_iter++) | ||
2235 | { | ||
2236 | /* Remove the "old" connections */ | ||
2237 | GNUNET_CONTAINER_multihashmap_destroy(pg->peers[pg_iter].connect_peers); | ||
2238 | /* And replace with the working set */ | ||
2239 | pg->peers[pg_iter].connect_peers = pg->peers[pg_iter].connect_peers_working_set; | ||
2240 | fprintf(stderr, "Finished! Hashmap size %u\n", GNUNET_CONTAINER_multihashmap_size(pg->peers[pg_iter].connect_peers)); | ||
2241 | } | ||
2242 | |||
2243 | } | ||
2244 | |||
2065 | /* | 2245 | /* |
2066 | * @param pg the peer group struct representing the running peers | 2246 | * @param pg the peer group struct representing the running peers |
2067 | * @param topology which topology to connect the peers in | 2247 | * @param topology which topology to connect the peers in |
@@ -2160,7 +2340,7 @@ GNUNET_TESTING_connect_topology (struct GNUNET_TESTING_PeerGroup *pg, | |||
2160 | choose_minimum(pg, (unsigned int)option_modifier); | 2340 | choose_minimum(pg, (unsigned int)option_modifier); |
2161 | break; | 2341 | break; |
2162 | case GNUNET_TESTING_TOPOLOGY_OPTION_DFS: /* Choose a random starting point, randomly walk graph, try to get each peer X connections */ | 2342 | case GNUNET_TESTING_TOPOLOGY_OPTION_DFS: /* Choose a random starting point, randomly walk graph, try to get each peer X connections */ |
2163 | //choose_dfs(pg, (int)option_modifier); | 2343 | perform_dfs(pg, (int)option_modifier); |
2164 | break; | 2344 | break; |
2165 | case GNUNET_TESTING_TOPOLOGY_OPTION_NONE: | 2345 | case GNUNET_TESTING_TOPOLOGY_OPTION_NONE: |
2166 | /* Fall through */ | 2346 | /* Fall through */ |
@@ -2466,9 +2646,12 @@ GNUNET_TESTING_daemons_stop (struct GNUNET_TESTING_PeerGroup *pg) | |||
2466 | if (NULL != pg->peers[off].cfg) | 2646 | if (NULL != pg->peers[off].cfg) |
2467 | GNUNET_CONFIGURATION_destroy (pg->peers[off].cfg); | 2647 | GNUNET_CONFIGURATION_destroy (pg->peers[off].cfg); |
2468 | 2648 | ||
2469 | GNUNET_CONTAINER_multihashmap_destroy(pg->peers[off].allowed_peers); | 2649 | if (pg->peers[off].allowed_peers != NULL) |
2470 | GNUNET_CONTAINER_multihashmap_destroy(pg->peers[off].connect_peers); | 2650 | GNUNET_CONTAINER_multihashmap_destroy(pg->peers[off].allowed_peers); |
2471 | GNUNET_CONTAINER_multihashmap_destroy(pg->peers[off].blacklisted_peers); | 2651 | if (pg->peers[off].connect_peers != NULL) |
2652 | GNUNET_CONTAINER_multihashmap_destroy(pg->peers[off].connect_peers); | ||
2653 | if (pg->peers[off].blacklisted_peers != NULL) | ||
2654 | GNUNET_CONTAINER_multihashmap_destroy(pg->peers[off].blacklisted_peers); | ||
2472 | 2655 | ||
2473 | } | 2656 | } |
2474 | GNUNET_free (pg->peers); | 2657 | GNUNET_free (pg->peers); |