diff options
author | Christian Grothoff <christian@grothoff.org> | 2013-03-14 09:03:46 +0000 |
---|---|---|
committer | Christian Grothoff <christian@grothoff.org> | 2013-03-14 09:03:46 +0000 |
commit | 25543ab8fed7935d490bb396ac376a1ca0c74b7b (patch) | |
tree | 212bd78658ad4dd53e3841adfe08336e3f7cb2ec /src/dv | |
parent | 78638e7d564f9245723984e231c8109308d79482 (diff) | |
download | gnunet-25543ab8fed7935d490bb396ac376a1ca0c74b7b.tar.gz gnunet-25543ab8fed7935d490bb396ac376a1ca0c74b7b.zip |
-simplify design
Diffstat (limited to 'src/dv')
-rw-r--r-- | src/dv/gnunet-service-dv.c | 272 |
1 files changed, 106 insertions, 166 deletions
diff --git a/src/dv/gnunet-service-dv.c b/src/dv/gnunet-service-dv.c index e6eb32778..6cf828a3b 100644 --- a/src/dv/gnunet-service-dv.c +++ b/src/dv/gnunet-service-dv.c | |||
@@ -165,57 +165,17 @@ struct DirectNeighbor | |||
165 | * Transmit handle to core service. | 165 | * Transmit handle to core service. |
166 | */ | 166 | */ |
167 | struct GNUNET_CORE_TransmitHandle *cth; | 167 | struct GNUNET_CORE_TransmitHandle *cth; |
168 | }; | ||
169 | |||
170 | |||
171 | /** | ||
172 | * A route includes information about the next hop, | ||
173 | * the target, and the ultimate distance to the | ||
174 | * target. | ||
175 | */ | ||
176 | struct Route | ||
177 | { | ||
178 | |||
179 | /** | ||
180 | * Which peer do we need to forward the message to? | ||
181 | */ | ||
182 | struct DirectNeighbor *next_hop; | ||
183 | |||
184 | /** | ||
185 | * What would be the target, and how far is it away? | ||
186 | */ | ||
187 | struct Target target; | ||
188 | |||
189 | /** | ||
190 | * Offset of this target in the respective consensus set. | ||
191 | */ | ||
192 | unsigned int set_offset; | ||
193 | |||
194 | }; | ||
195 | |||
196 | |||
197 | /** | ||
198 | * Routing neighbors are neighbors that we exchange | ||
199 | * routing information with; that is, their distance | ||
200 | * must be strictly less than the DEFAULT_FISHEYE_DEPTH; | ||
201 | * they can also be direct neighbors. | ||
202 | */ | ||
203 | struct RoutingNeighbor | ||
204 | { | ||
205 | |||
206 | /** | ||
207 | * Which peer is this, and how do we talk to it? | ||
208 | */ | ||
209 | struct Route route; | ||
210 | 168 | ||
211 | /** | 169 | /** |
212 | * Routing table of the neighbor, NULL if not yet established. | 170 | * Routing table of the neighbor, NULL if not yet established. |
171 | * Keys are peer identities, values are 'struct Target' entries. | ||
213 | */ | 172 | */ |
214 | struct GNUNET_CONTAINER_MultiHashMap *neighbor_table; | 173 | struct GNUNET_CONTAINER_MultiHashMap *neighbor_table; |
215 | 174 | ||
216 | /** | 175 | /** |
217 | * Updated routing table of the neighbor, under construction, | 176 | * Updated routing table of the neighbor, under construction, |
218 | * NULL if we are not currently building it. | 177 | * NULL if we are not currently building it. |
178 | * Keys are peer identities, values are 'struct Target' entries. | ||
219 | */ | 179 | */ |
220 | struct GNUNET_CONTAINER_MultiHashMap *neighbor_table_consensus; | 180 | struct GNUNET_CONTAINER_MultiHashMap *neighbor_table_consensus; |
221 | 181 | ||
@@ -241,6 +201,32 @@ struct RoutingNeighbor | |||
241 | 201 | ||
242 | 202 | ||
243 | /** | 203 | /** |
204 | * A route includes information about the next hop, | ||
205 | * the target, and the ultimate distance to the | ||
206 | * target. | ||
207 | */ | ||
208 | struct Route | ||
209 | { | ||
210 | |||
211 | /** | ||
212 | * Which peer do we need to forward the message to? | ||
213 | */ | ||
214 | struct DirectNeighbor *next_hop; | ||
215 | |||
216 | /** | ||
217 | * What would be the target, and how far is it away? | ||
218 | */ | ||
219 | struct Target target; | ||
220 | |||
221 | /** | ||
222 | * Offset of this target in the respective consensus set. | ||
223 | */ | ||
224 | unsigned int set_offset; | ||
225 | |||
226 | }; | ||
227 | |||
228 | |||
229 | /** | ||
244 | * Set of targets we bring to a consensus; all targets in a set have a | 230 | * Set of targets we bring to a consensus; all targets in a set have a |
245 | * distance equal to the sets distance (which is implied by the array | 231 | * distance equal to the sets distance (which is implied by the array |
246 | * index of the set). | 232 | * index of the set). |
@@ -251,7 +237,7 @@ struct ConsensusSet | |||
251 | /** | 237 | /** |
252 | * Array of targets in the set, may include NULL entries if a | 238 | * Array of targets in the set, may include NULL entries if a |
253 | * neighbor has disconnected; the targets are allocated with the | 239 | * neighbor has disconnected; the targets are allocated with the |
254 | * respective container (i.e. 'struct RoutingNeighbor'), not here. | 240 | * respective container (all_routes), not here. |
255 | */ | 241 | */ |
256 | struct Route **targets; | 242 | struct Route **targets; |
257 | 243 | ||
@@ -269,12 +255,6 @@ struct ConsensusSet | |||
269 | static struct GNUNET_CONTAINER_MultiHashMap *direct_neighbors; | 255 | static struct GNUNET_CONTAINER_MultiHashMap *direct_neighbors; |
270 | 256 | ||
271 | /** | 257 | /** |
272 | * Hashmap of all of the neighbors we exchange routing information | ||
273 | * with (peers up to DEFAULT_FISHEYE_DEPTH - 1 distance from us). | ||
274 | */ | ||
275 | static struct GNUNET_CONTAINER_MultiHashMap *routing_neighbors; | ||
276 | |||
277 | /** | ||
278 | * Hashmap with all routes that we currently support; contains | 258 | * Hashmap with all routes that we currently support; contains |
279 | * routing information for all peers up to distance DEFAULT_FISHEYE_DEPTH. | 259 | * routing information for all peers up to distance DEFAULT_FISHEYE_DEPTH. |
280 | */ | 260 | */ |
@@ -619,20 +599,6 @@ core_transmit_notify (void *cls, size_t size, void *buf) | |||
619 | 599 | ||
620 | 600 | ||
621 | /** | 601 | /** |
622 | * Begin exchanging routing information with 'rn', updating | ||
623 | * our respective neighbor table in the process. | ||
624 | * | ||
625 | * @param rn neighbor with whom we should exchange the information | ||
626 | */ | ||
627 | static void | ||
628 | exchange_routing_information (struct RoutingNeighbor *rn) | ||
629 | { | ||
630 | GNUNET_break (0); | ||
631 | // FIXME | ||
632 | } | ||
633 | |||
634 | |||
635 | /** | ||
636 | * Find a free slot for storing a 'route' in the 'consensi' | 602 | * Find a free slot for storing a 'route' in the 'consensi' |
637 | * set at the given distance. | 603 | * set at the given distance. |
638 | * | 604 | * |
@@ -657,70 +623,6 @@ get_consensus_slot (uint32_t distance) | |||
657 | 623 | ||
658 | 624 | ||
659 | /** | 625 | /** |
660 | * Setup an entry in the 'routing neighbor' table and begin the | ||
661 | * exchange with the new routing neighbor. Note that a routing | ||
662 | * neighbor can be a direct neighbor at the same time, in which case | ||
663 | * the peer identity of 'target' and 'next_hop->peer' will be the same | ||
664 | * (and the distance will be 1). | ||
665 | * | ||
666 | * If a routing neighbor already exists, ignore the update if | ||
667 | * the distance is not smaller; otherwise if the distance | ||
668 | * is smaller, replace the existing entry with the new route. | ||
669 | * | ||
670 | * @param next_hop first routing hop towards the routing neighbor | ||
671 | * @param target peer identity of the routing neighbor | ||
672 | * @param distance number of hops to the routing neighbor | ||
673 | */ | ||
674 | static void | ||
675 | create_routing_neighbor (struct DirectNeighbor *next_hop, | ||
676 | const struct GNUNET_PeerIdentity *target, | ||
677 | uint32_t distance) | ||
678 | { | ||
679 | struct RoutingNeighbor *rn; | ||
680 | unsigned int i; | ||
681 | |||
682 | rn = GNUNET_CONTAINER_multihashmap_get (routing_neighbors, | ||
683 | &target->hashPubKey); | ||
684 | if (NULL != rn) | ||
685 | { | ||
686 | /* update the entry, instead of creating a new one */ | ||
687 | if (distance >= rn->route.target.distance) | ||
688 | return; /* ignore, distance is not better */ | ||
689 | rn->route.next_hop = next_hop; | ||
690 | if (distance < rn->route.target.distance) | ||
691 | { | ||
692 | /* move to alternative consensi slot */ | ||
693 | consensi[rn->route.target.distance].targets[rn->route.set_offset] = NULL; | ||
694 | rn->route.target.distance = distance; | ||
695 | i = get_consensus_slot (distance); | ||
696 | rn->route.set_offset = i; | ||
697 | consensi[distance].targets[i] = &rn->route; | ||
698 | } | ||
699 | if (DIRECT_NEIGHBOR_COST == distance) | ||
700 | { | ||
701 | /* we're now a direct neighbor, remove from set reachable via DV! */ | ||
702 | send_disconnect_to_plugin (target); | ||
703 | } | ||
704 | return; | ||
705 | } | ||
706 | GNUNET_assert (distance < DEFAULT_FISHEYE_DEPTH - 1); | ||
707 | i = get_consensus_slot (distance); | ||
708 | rn = GNUNET_malloc (sizeof (struct RoutingNeighbor)); | ||
709 | rn->route.next_hop = next_hop; | ||
710 | rn->route.target.peer = *target; | ||
711 | rn->route.target.distance = distance; | ||
712 | rn->route.set_offset = i; | ||
713 | consensi[distance].targets[i] = &rn->route; | ||
714 | exchange_routing_information (rn); | ||
715 | GNUNET_assert (GNUNET_YES == | ||
716 | GNUNET_CONTAINER_multihashmap_put (direct_neighbors, | ||
717 | &target->hashPubKey, | ||
718 | rn, | ||
719 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
720 | } | ||
721 | |||
722 | |||
723 | /** | ||
724 | * Method called whenever a peer connects. | 626 | * Method called whenever a peer connects. |
725 | * | 627 | * |
726 | * @param cls closure | 628 | * @param cls closure |
@@ -734,8 +636,9 @@ handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer, | |||
734 | unsigned int atsi_count) | 636 | unsigned int atsi_count) |
735 | { | 637 | { |
736 | struct DirectNeighbor *neighbor; | 638 | struct DirectNeighbor *neighbor; |
737 | struct RoutingNeighbor *rn; | 639 | struct Route *route; |
738 | uint32_t distance; | 640 | uint32_t distance; |
641 | unsigned int i; | ||
739 | 642 | ||
740 | /* Check for connect to self message */ | 643 | /* Check for connect to self message */ |
741 | if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity))) | 644 | if (0 == memcmp (&my_identity, peer, sizeof (struct GNUNET_PeerIdentity))) |
@@ -757,7 +660,33 @@ handle_core_connect (void *cls, const struct GNUNET_PeerIdentity *peer, | |||
757 | &peer->hashPubKey, | 660 | &peer->hashPubKey, |
758 | neighbor, | 661 | neighbor, |
759 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | 662 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); |
760 | create_routing_neighbor (neighbor, peer, DIRECT_NEIGHBOR_COST); | 663 | |
664 | route = GNUNET_CONTAINER_multihashmap_get (all_routes, | ||
665 | &peer->hashPubKey); | ||
666 | if (NULL == route) | ||
667 | { | ||
668 | route->target.peer = *peer; | ||
669 | i = get_consensus_slot (DIRECT_NEIGHBOR_COST); | ||
670 | route->set_offset = i; | ||
671 | consensi[DIRECT_NEIGHBOR_COST].targets[i] = route; | ||
672 | GNUNET_assert (GNUNET_YES == | ||
673 | GNUNET_CONTAINER_multihashmap_put (all_routes, | ||
674 | &route->target.peer.hashPubKey, | ||
675 | route, | ||
676 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
677 | } | ||
678 | else | ||
679 | { | ||
680 | /* move to new consensi slot */ | ||
681 | send_disconnect_to_plugin (peer); | ||
682 | consensi[route->target.distance].targets[route->set_offset] = NULL; | ||
683 | i = get_consensus_slot (DIRECT_NEIGHBOR_COST); | ||
684 | route->set_offset = i; | ||
685 | consensi[DIRECT_NEIGHBOR_COST].targets[i] = route; | ||
686 | } | ||
687 | route->next_hop = neighbor; | ||
688 | route->target.distance = DIRECT_NEIGHBOR_COST; | ||
689 | // FIXME: begin exchange_routing_information! | ||
761 | } | 690 | } |
762 | 691 | ||
763 | 692 | ||
@@ -829,27 +758,62 @@ cull_routes (void *cls, const struct GNUNET_HashCode * key, void *value) | |||
829 | 758 | ||
830 | 759 | ||
831 | /** | 760 | /** |
832 | * Multihashmap iterator for freeing routes that go via a particular | 761 | * Multihashmap iterator for checking if a given route is |
833 | * neighbor that disconnected and is thus no longer available. | 762 | * (now) useful to this peer. |
834 | * | 763 | * |
835 | * @param cls the direct neighbor that is now unavailable | 764 | * @param cls the direct neighbor for the given route |
836 | * @param key key value stored under | 765 | * @param key key value stored under |
837 | * @param value a 'struct Route' that may or may not go via neighbor | 766 | * @param value a 'struct Target' that may or may not be useful |
838 | * | 767 | * |
839 | * @return GNUNET_YES to continue iteration, GNUNET_NO to stop | 768 | * @return GNUNET_YES to continue iteration, GNUNET_NO to stop |
840 | */ | 769 | */ |
841 | static int | 770 | static int |
842 | cull_routing_neighbors (void *cls, const struct GNUNET_HashCode * key, void *value) | 771 | cull_routes (void *cls, const struct GNUNET_HashCode * key, void *value) |
843 | { | 772 | { |
844 | struct DirectNeighbor *neighbor = cls; | 773 | struct DirectNeighbor *neighbor = cls; |
845 | struct RoutingNeighbor *rn = value; | 774 | struct Target *target = value; |
775 | struct Route *cur; | ||
776 | |||
777 | cur = GNUNET_CONTAINER_multihashmap_get (all_routes, | ||
778 | key); | ||
779 | if (NULL != cur) | ||
780 | { | ||
781 | if (cur->target.distance > target->distance) | ||
782 | { | ||
783 | /* FIXME: this 'target' is cheaper than the existing route; | ||
784 | switch route! */ | ||
785 | } | ||
786 | return GNUNET_YES; /* got a route to this target already */ | ||
787 | } | ||
788 | cur = GNUNET_malloc (sizeof (struct Route)); | ||
789 | cur->next_hop = neighbor; | ||
790 | cur->target = *target; | ||
791 | cur->set_offset = get_consensus_slot (target->distance); | ||
792 | GNUNET_CONTAINER_multihashmap_put (all_routes, | ||
793 | key, | ||
794 | cur); | ||
795 | return GNUNET_YES; | ||
796 | } | ||
846 | 797 | ||
847 | if (rn->route.next_hop != neighbor) | ||
848 | return GNUNET_YES; /* not affected */ | ||
849 | 798 | ||
850 | /* FIXME: destroy routing neighbor! */ | 799 | /** |
851 | GNUNET_break (0); | 800 | * Multihashmap iterator for finding routes that were previously |
801 | * "hidden" due to a better route (called after a disconnect event). | ||
802 | * | ||
803 | * @param cls NULL | ||
804 | * @param key peer identity of the given direct neighbor | ||
805 | * @param value a 'struct DirectNeighbor' to check for additional routes | ||
806 | * @return GNUNET_YES to continue iteration | ||
807 | */ | ||
808 | static int | ||
809 | refresh_routes (void *cls, const struct GNUNET_HashCode * key, void *value) | ||
810 | { | ||
811 | struct DirectNeighbor *neighbor = value; | ||
852 | 812 | ||
813 | if (NULL != neighbor->neighbor_table) | ||
814 | GNUNET_CONTAINER_multihashmap_iterate (neighbor->neighbor_table, | ||
815 | &check_possible_route, | ||
816 | neighbor); | ||
853 | return GNUNET_YES; | 817 | return GNUNET_YES; |
854 | } | 818 | } |
855 | 819 | ||
@@ -889,9 +853,6 @@ handle_core_disconnect (void *cls, const struct GNUNET_PeerIdentity *peer) | |||
889 | GNUNET_CONTAINER_multihashmap_iterate (all_routes, | 853 | GNUNET_CONTAINER_multihashmap_iterate (all_routes, |
890 | &cull_routes, | 854 | &cull_routes, |
891 | neighbor); | 855 | neighbor); |
892 | GNUNET_CONTAINER_multihashmap_iterate (routing_neighbors, | ||
893 | &cull_routing_neighbors, | ||
894 | neighbor); | ||
895 | if (NULL != neighbor->cth) | 856 | if (NULL != neighbor->cth) |
896 | { | 857 | { |
897 | GNUNET_CORE_notify_transmit_ready_cancel (neighbor->cth); | 858 | GNUNET_CORE_notify_transmit_ready_cancel (neighbor->cth); |
@@ -902,6 +863,9 @@ handle_core_disconnect (void *cls, const struct GNUNET_PeerIdentity *peer) | |||
902 | &peer->hashPubKey, | 863 | &peer->hashPubKey, |
903 | neighbor)); | 864 | neighbor)); |
904 | GNUNET_free (neighbor); | 865 | GNUNET_free (neighbor); |
866 | GNUNET_CONTAINER_multihashmap_iterate (direct_neighbors, | ||
867 | &refresh_routes, | ||
868 | NULL); | ||
905 | } | 869 | } |
906 | 870 | ||
907 | 871 | ||
@@ -925,26 +889,6 @@ free_route (void *cls, const struct GNUNET_HashCode * key, void *value) | |||
925 | 889 | ||
926 | 890 | ||
927 | /** | 891 | /** |
928 | * Multihashmap iterator for freeing routing neighbors. Should never be called. | ||
929 | * | ||
930 | * @param cls NULL | ||
931 | * @param key key value stored under | ||
932 | * @param value the distant neighbor to be freed | ||
933 | * | ||
934 | * @return GNUNET_YES to continue iteration, GNUNET_NO to stop | ||
935 | */ | ||
936 | static int | ||
937 | free_routing_neighbors (void *cls, const struct GNUNET_HashCode * key, void *value) | ||
938 | { | ||
939 | struct RoutingNeighbor *router = value; | ||
940 | |||
941 | GNUNET_break (0); | ||
942 | // FIXME: release resources | ||
943 | return GNUNET_YES; | ||
944 | } | ||
945 | |||
946 | |||
947 | /** | ||
948 | * Multihashmap iterator for freeing direct neighbors. Should never be called. | 892 | * Multihashmap iterator for freeing direct neighbors. Should never be called. |
949 | * | 893 | * |
950 | * @param cls NULL | 894 | * @param cls NULL |
@@ -979,9 +923,6 @@ shutdown_task (void *cls, const struct GNUNET_SCHEDULER_TaskContext *tc) | |||
979 | GNUNET_CONTAINER_multihashmap_iterate (direct_neighbors, | 923 | GNUNET_CONTAINER_multihashmap_iterate (direct_neighbors, |
980 | &free_direct_neighbors, NULL); | 924 | &free_direct_neighbors, NULL); |
981 | GNUNET_CONTAINER_multihashmap_destroy (direct_neighbors); | 925 | GNUNET_CONTAINER_multihashmap_destroy (direct_neighbors); |
982 | GNUNET_CONTAINER_multihashmap_iterate (routing_neighbors, | ||
983 | &free_routing_neighbors, NULL); | ||
984 | GNUNET_CONTAINER_multihashmap_destroy (routing_neighbors); | ||
985 | GNUNET_CONTAINER_multihashmap_iterate (all_routes, | 926 | GNUNET_CONTAINER_multihashmap_iterate (all_routes, |
986 | &free_route, NULL); | 927 | &free_route, NULL); |
987 | GNUNET_CONTAINER_multihashmap_destroy (all_routes); | 928 | GNUNET_CONTAINER_multihashmap_destroy (all_routes); |
@@ -1072,7 +1013,6 @@ run (void *cls, struct GNUNET_SERVER_Handle *server, | |||
1072 | 1013 | ||
1073 | cfg = c; | 1014 | cfg = c; |
1074 | direct_neighbors = GNUNET_CONTAINER_multihashmap_create (128, GNUNET_NO); | 1015 | direct_neighbors = GNUNET_CONTAINER_multihashmap_create (128, GNUNET_NO); |
1075 | routing_neighbors = GNUNET_CONTAINER_multihashmap_create (128 * 128, GNUNET_NO); | ||
1076 | all_routes = GNUNET_CONTAINER_multihashmap_create (65536, GNUNET_NO); | 1016 | all_routes = GNUNET_CONTAINER_multihashmap_create (65536, GNUNET_NO); |
1077 | core_api = GNUNET_CORE_connect (cfg, NULL, | 1017 | core_api = GNUNET_CORE_connect (cfg, NULL, |
1078 | &core_init, | 1018 | &core_init, |