diff options
Diffstat (limited to 'src/transport/gnunet-service-tng.c')
-rw-r--r-- | src/transport/gnunet-service-tng.c | 674 |
1 files changed, 637 insertions, 37 deletions
diff --git a/src/transport/gnunet-service-tng.c b/src/transport/gnunet-service-tng.c index 342b4c2bc..2dd68bcc8 100644 --- a/src/transport/gnunet-service-tng.c +++ b/src/transport/gnunet-service-tng.c | |||
@@ -33,14 +33,16 @@ | |||
33 | * transport-to-transport traffic) | 33 | * transport-to-transport traffic) |
34 | * | 34 | * |
35 | * Implement next: | 35 | * Implement next: |
36 | * - DV data structures: | ||
37 | * + initiation of DV learn (incl. RTT measurement logic!) | ||
38 | * - security considerations? add signatures to routes? initiator signature? | ||
39 | * + using DV routes! | ||
40 | * - handling of DV-boxed messages that need to be forwarded | ||
41 | * - route_message implementation, including using DV data structures | ||
42 | * (but not when routing certain message types, like DV learn, | ||
43 | * MUST pay attention to content here -- or pass extra flags?) | ||
36 | * - ACK handling / retransmission | 44 | * - ACK handling / retransmission |
37 | * - track RTT, distance, loss, etc. | 45 | * - track RTT, distance, loss, etc. |
38 | * - DV data structures: | ||
39 | * + learning | ||
40 | * + forgetting | ||
41 | * + using them! | ||
42 | * - routing of messages (using DV data structures!) | ||
43 | * - handling of DV-boxed messages that need to be forwarded | ||
44 | * - backchannel message encryption & decryption | 46 | * - backchannel message encryption & decryption |
45 | * | 47 | * |
46 | * Later: | 48 | * Later: |
@@ -99,6 +101,25 @@ | |||
99 | #define IN_PACKET_SIZE_WITHOUT_MTU 128 | 101 | #define IN_PACKET_SIZE_WITHOUT_MTU 128 |
100 | 102 | ||
101 | /** | 103 | /** |
104 | * Minimum number of hops we should forward DV learn messages | ||
105 | * even if they are NOT useful for us in hope of looping | ||
106 | * back to the initiator? | ||
107 | * | ||
108 | * FIXME: allow initiator some control here instead? | ||
109 | */ | ||
110 | #define MIN_DV_PATH_LENGTH_FOR_INITIATOR 3 | ||
111 | |||
112 | /** | ||
113 | * Maximum DV distance allowed ever. | ||
114 | */ | ||
115 | #define MAX_DV_HOPS_ALLOWED 16 | ||
116 | |||
117 | /** | ||
118 | * Maximum number of DV paths we keep simultaneously to the same target. | ||
119 | */ | ||
120 | #define MAX_DV_PATHS_TO_TARGET 3 | ||
121 | |||
122 | /** | ||
102 | * If a queue delays the next message by more than this number | 123 | * If a queue delays the next message by more than this number |
103 | * of seconds we log a warning. Note: this is for testing, | 124 | * of seconds we log a warning. Note: this is for testing, |
104 | * the value chosen here might be too aggressively low! | 125 | * the value chosen here might be too aggressively low! |
@@ -106,6 +127,18 @@ | |||
106 | #define DELAY_WARN_THRESHOLD GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 5) | 127 | #define DELAY_WARN_THRESHOLD GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_SECONDS, 5) |
107 | 128 | ||
108 | /** | 129 | /** |
130 | * How long do we consider a DV path valid if we see no | ||
131 | * further updates on it? Note: the value chosen here might be too low! | ||
132 | */ | ||
133 | #define DV_PATH_VALIDITY_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 5) | ||
134 | |||
135 | /** | ||
136 | * How long before paths expire would we like to (re)discover DV paths? Should | ||
137 | * be below #DV_PATH_VALIDITY_TIMEOUT. | ||
138 | */ | ||
139 | #define DV_PATH_DISCOVERY_FREQUENCY GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 4) | ||
140 | |||
141 | /** | ||
109 | * How long are ephemeral keys valid? | 142 | * How long are ephemeral keys valid? |
110 | */ | 143 | */ |
111 | #define EPHEMERAL_VALIDITY GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_HOURS, 4) | 144 | #define EPHEMERAL_VALIDITY GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_HOURS, 4) |
@@ -444,6 +477,72 @@ struct TransportFragmentAckMessage | |||
444 | 477 | ||
445 | 478 | ||
446 | /** | 479 | /** |
480 | * Content signed by each peer during DV learning. | ||
481 | */ | ||
482 | struct DvInitPS | ||
483 | { | ||
484 | /** | ||
485 | * Purpose is #GNUNET_SIGNATURE_PURPOSE_TRANSPORT_DV_INITIATOR | ||
486 | */ | ||
487 | struct GNUNET_CRYPTO_EccSignaturePurpose purpose; | ||
488 | |||
489 | /** | ||
490 | * Challenge value used by the initiator to re-identify the path. | ||
491 | */ | ||
492 | struct GNUNET_ShortHashCode challenge; | ||
493 | |||
494 | }; | ||
495 | |||
496 | |||
497 | /** | ||
498 | * Content signed by each peer during DV learning. | ||
499 | */ | ||
500 | struct DvHopPS | ||
501 | { | ||
502 | /** | ||
503 | * Purpose is #GNUNET_SIGNATURE_PURPOSE_TRANSPORT_DV_HOP | ||
504 | */ | ||
505 | struct GNUNET_CRYPTO_EccSignaturePurpose purpose; | ||
506 | |||
507 | /** | ||
508 | * Identity of the previous peer on the path. | ||
509 | */ | ||
510 | struct GNUNET_PeerIdentity pred; | ||
511 | |||
512 | /** | ||
513 | * Identity of the next peer on the path. | ||
514 | */ | ||
515 | struct GNUNET_PeerIdentity succ; | ||
516 | |||
517 | /** | ||
518 | * Challenge value used by the initiator to re-identify the path. | ||
519 | */ | ||
520 | struct GNUNET_ShortHashCode challenge; | ||
521 | |||
522 | }; | ||
523 | |||
524 | |||
525 | /** | ||
526 | * An entry describing a peer on a path in a | ||
527 | * `struct TransportDVLearn` message. | ||
528 | */ | ||
529 | struct DVPathEntryP | ||
530 | { | ||
531 | /** | ||
532 | * Identity of a peer on the path. | ||
533 | */ | ||
534 | struct GNUNET_PeerIdentity hop; | ||
535 | |||
536 | /** | ||
537 | * Signature of this hop over the path, of purpose | ||
538 | * #GNUNET_SIGNATURE_PURPOSE_TRANSPORT_DV_HOP | ||
539 | */ | ||
540 | struct GNUNET_CRYPTO_EddsaSignature hop_sig; | ||
541 | |||
542 | }; | ||
543 | |||
544 | |||
545 | /** | ||
447 | * Internal message used by transport for distance vector learning. | 546 | * Internal message used by transport for distance vector learning. |
448 | * If @e num_hops does not exceed the threshold, peers should append | 547 | * If @e num_hops does not exceed the threshold, peers should append |
449 | * themselves to the peer list and flood the message (possibly only | 548 | * themselves to the peer list and flood the message (possibly only |
@@ -481,19 +580,28 @@ struct TransportDVLearn | |||
481 | 580 | ||
482 | /** | 581 | /** |
483 | * Peers receiving this message and delaying forwarding to other | 582 | * Peers receiving this message and delaying forwarding to other |
484 | * peers for any reason should increment this value such as to | 583 | * peers for any reason should increment this value by the non-network |
485 | * enable the origin to determine the actual network-only delay | 584 | * delay created by the peer. |
486 | * in addition to the real-time delay (assuming the message loops | ||
487 | * back to the origin). | ||
488 | */ | 585 | */ |
489 | struct GNUNET_TIME_Relative cummulative_non_network_delay; | 586 | struct GNUNET_TIME_RelativeNBO non_network_delay; |
587 | |||
588 | /** | ||
589 | * Signature of this hop over the path, of purpose | ||
590 | * #GNUNET_SIGNATURE_PURPOSE_TRANSPORT_DV_INITIATOR | ||
591 | */ | ||
592 | struct GNUNET_CRYPTO_EddsaSignature init_sig; | ||
490 | 593 | ||
491 | /** | 594 | /** |
492 | * Identity of the peer that started this learning activity. | 595 | * Identity of the peer that started this learning activity. |
493 | */ | 596 | */ |
494 | struct GNUNET_PeerIdentity initiator; | 597 | struct GNUNET_PeerIdentity initiator; |
495 | 598 | ||
496 | /* Followed by @e num_hops `struct GNUNET_PeerIdentity` values, | 599 | /** |
600 | * Challenge value used by the initiator to re-identify the path. | ||
601 | */ | ||
602 | struct GNUNET_ShortHashCode challenge; | ||
603 | |||
604 | /* Followed by @e num_hops `struct DVPathEntryP` values, | ||
497 | excluding the initiator of the DV trace; the last entry is the | 605 | excluding the initiator of the DV trace; the last entry is the |
498 | current sender; the current peer must not be included. */ | 606 | current sender; the current peer must not be included. */ |
499 | 607 | ||
@@ -1833,8 +1941,10 @@ struct MonitorEvent | |||
1833 | 1941 | ||
1834 | 1942 | ||
1835 | /** | 1943 | /** |
1836 | * Free a @dvh, and if it is the last path to the `target`,also | 1944 | * Free a @dvh. Callers MAY want to check if this was the last path to the |
1837 | * free the associated DV entry in #dv_routes. | 1945 | * `target`, and if so call #free_dv_route to also free the associated DV |
1946 | * entry in #dv_routes (if not, the associated scheduler job should eventually | ||
1947 | * take care of it). | ||
1838 | * | 1948 | * |
1839 | * @param dvh hop to free | 1949 | * @param dvh hop to free |
1840 | */ | 1950 | */ |
@@ -1845,30 +1955,20 @@ free_distance_vector_hop (struct DistanceVectorHop *dvh) | |||
1845 | struct DistanceVector *dv = dvh->dv; | 1955 | struct DistanceVector *dv = dvh->dv; |
1846 | 1956 | ||
1847 | GNUNET_CONTAINER_MDLL_remove (neighbour, | 1957 | GNUNET_CONTAINER_MDLL_remove (neighbour, |
1848 | n->dv_head, | 1958 | n->dv_head, |
1849 | n->dv_tail, | 1959 | n->dv_tail, |
1850 | dvh); | 1960 | dvh); |
1851 | GNUNET_CONTAINER_MDLL_remove (dv, | 1961 | GNUNET_CONTAINER_MDLL_remove (dv, |
1852 | dv->dv_head, | 1962 | dv->dv_head, |
1853 | dv->dv_tail, | 1963 | dv->dv_tail, |
1854 | dvh); | 1964 | dvh); |
1855 | GNUNET_free (dvh); | 1965 | GNUNET_free (dvh); |
1856 | if (NULL == dv->dv_head) | ||
1857 | { | ||
1858 | GNUNET_assert (GNUNET_YES == | ||
1859 | GNUNET_CONTAINER_multipeermap_remove (dv_routes, | ||
1860 | &dv->target, | ||
1861 | dv)); | ||
1862 | if (NULL != dv->timeout_task) | ||
1863 | GNUNET_SCHEDULER_cancel (dv->timeout_task); | ||
1864 | GNUNET_free (dv); | ||
1865 | } | ||
1866 | } | 1966 | } |
1867 | 1967 | ||
1868 | 1968 | ||
1869 | /** | 1969 | /** |
1870 | * Free entry in #dv_routes. First frees all hops to the target, and | 1970 | * Free entry in #dv_routes. First frees all hops to the target, and |
1871 | * the last target will implicitly free @a dv as well. | 1971 | * if there are no entries left, frees @a dv as well. |
1872 | * | 1972 | * |
1873 | * @param dv route to free | 1973 | * @param dv route to free |
1874 | */ | 1974 | */ |
@@ -1879,6 +1979,16 @@ free_dv_route (struct DistanceVector *dv) | |||
1879 | 1979 | ||
1880 | while (NULL != (dvh = dv->dv_head)) | 1980 | while (NULL != (dvh = dv->dv_head)) |
1881 | free_distance_vector_hop (dvh); | 1981 | free_distance_vector_hop (dvh); |
1982 | if (NULL == dv->dv_head) | ||
1983 | { | ||
1984 | GNUNET_assert (GNUNET_YES == | ||
1985 | GNUNET_CONTAINER_multipeermap_remove (dv_routes, | ||
1986 | &dv->target, | ||
1987 | dv)); | ||
1988 | if (NULL != dv->timeout_task) | ||
1989 | GNUNET_SCHEDULER_cancel (dv->timeout_task); | ||
1990 | GNUNET_free (dv); | ||
1991 | } | ||
1882 | } | 1992 | } |
1883 | 1993 | ||
1884 | 1994 | ||
@@ -2089,7 +2199,13 @@ free_neighbour (struct Neighbour *neighbour) | |||
2089 | neighbour->reassembly_heap = NULL; | 2199 | neighbour->reassembly_heap = NULL; |
2090 | } | 2200 | } |
2091 | while (NULL != (dvh = neighbour->dv_head)) | 2201 | while (NULL != (dvh = neighbour->dv_head)) |
2202 | { | ||
2203 | struct DistanceVector *dv = dvh->dv; | ||
2204 | |||
2092 | free_distance_vector_hop (dvh); | 2205 | free_distance_vector_hop (dvh); |
2206 | if (NULL == dv->dv_head) | ||
2207 | free_dv_route (dv); | ||
2208 | } | ||
2093 | if (NULL != neighbour->reassembly_timeout_task) | 2209 | if (NULL != neighbour->reassembly_timeout_task) |
2094 | GNUNET_SCHEDULER_cancel (neighbour->reassembly_timeout_task); | 2210 | GNUNET_SCHEDULER_cancel (neighbour->reassembly_timeout_task); |
2095 | GNUNET_free (neighbour); | 2211 | GNUNET_free (neighbour); |
@@ -3685,6 +3801,203 @@ handle_backchannel_encapsulation (void *cls, | |||
3685 | 3801 | ||
3686 | 3802 | ||
3687 | /** | 3803 | /** |
3804 | * Task called when we should check if any of the DV paths | ||
3805 | * we have learned to a target are due for garbage collection. | ||
3806 | * | ||
3807 | * Collects stale paths, and possibly frees the entire DV | ||
3808 | * entry if no paths are left. Otherwise re-schedules itself. | ||
3809 | * | ||
3810 | * @param cls a `struct DistanceVector` | ||
3811 | */ | ||
3812 | static void | ||
3813 | path_cleanup_cb (void *cls) | ||
3814 | { | ||
3815 | struct DistanceVector *dv = cls; | ||
3816 | struct DistanceVectorHop *pos; | ||
3817 | |||
3818 | dv->timeout_task = NULL; | ||
3819 | while (NULL != (pos = dv->dv_head)) | ||
3820 | { | ||
3821 | GNUNET_assert (dv == pos->dv); | ||
3822 | if (GNUNET_TIME_absolute_get_remaining (pos->timeout).rel_value_us > 0) | ||
3823 | break; | ||
3824 | free_distance_vector_hop (pos); | ||
3825 | } | ||
3826 | if (NULL == pos) | ||
3827 | { | ||
3828 | free_dv_route (dv); | ||
3829 | return; | ||
3830 | } | ||
3831 | dv->timeout_task = GNUNET_SCHEDULER_add_at (pos->timeout, | ||
3832 | &path_cleanup_cb, | ||
3833 | dv); | ||
3834 | } | ||
3835 | |||
3836 | |||
3837 | /** | ||
3838 | * We have learned a @a path through the network to some other peer, add it to | ||
3839 | * our DV data structure (returning #GNUNET_YES on success). | ||
3840 | * | ||
3841 | * We do not add paths if we have a sufficient number of shorter | ||
3842 | * paths to this target already (returning #GNUNET_NO). | ||
3843 | * | ||
3844 | * We also do not add problematic paths, like those where we lack the first | ||
3845 | * hop in our neighbour list (i.e. due to a topology change) or where some | ||
3846 | * non-first hop is in our neighbour list (returning #GNUNET_SYSERR). | ||
3847 | * | ||
3848 | * @param path the path we learned, path[0] should be us, | ||
3849 | * and then path contains a valid path from us to `path[path_len-1]` | ||
3850 | * path[1] should be a direct neighbour (we should check!) | ||
3851 | * @param path_len number of entries on the @a path, at least three! | ||
3852 | * @param network_latency how long does the message take from us to `path[path_len-1]`? | ||
3853 | * set to "forever" if unknown | ||
3854 | * @return #GNUNET_YES on success, | ||
3855 | * #GNUNET_NO if we have better path(s) to the target | ||
3856 | * #GNUNET_SYSERR if the path is useless and/or invalid | ||
3857 | * (i.e. path[1] not a direct neighbour | ||
3858 | * or path[i+1] is a direct neighbour for i>0) | ||
3859 | */ | ||
3860 | static int | ||
3861 | learn_dv_path (const struct GNUNET_PeerIdentity *path, | ||
3862 | unsigned int path_len, | ||
3863 | struct GNUNET_TIME_Relative network_latency) | ||
3864 | { | ||
3865 | struct DistanceVectorHop *hop; | ||
3866 | struct DistanceVector *dv; | ||
3867 | struct Neighbour *next_hop; | ||
3868 | unsigned int shorter_distance; | ||
3869 | |||
3870 | if (path_len < 3) | ||
3871 | { | ||
3872 | /* what a boring path! not allowed! */ | ||
3873 | GNUNET_break (0); | ||
3874 | return GNUNET_SYSERR; | ||
3875 | } | ||
3876 | GNUNET_assert (0 == | ||
3877 | GNUNET_memcmp (&GST_my_identity, | ||
3878 | &path[0])); | ||
3879 | next_hop = GNUNET_CONTAINER_multipeermap_get (neighbours, | ||
3880 | &path[1]); | ||
3881 | if (NULL == next_hop) | ||
3882 | { | ||
3883 | /* next hop must be a neighbour, otherwise this whole thing is useless! */ | ||
3884 | GNUNET_break (0); | ||
3885 | return GNUNET_SYSERR; | ||
3886 | } | ||
3887 | for (unsigned int i=2;i<path_len;i++) | ||
3888 | if (NULL != | ||
3889 | GNUNET_CONTAINER_multipeermap_get (neighbours, | ||
3890 | &path[i])) | ||
3891 | { | ||
3892 | /* Useless path, we have a direct connection to some hop | ||
3893 | in the middle of the path, so this one doesn't even | ||
3894 | seem terribly useful for redundancy */ | ||
3895 | return GNUNET_SYSERR; | ||
3896 | } | ||
3897 | dv = GNUNET_CONTAINER_multipeermap_get (dv_routes, | ||
3898 | &path[path_len - 1]); | ||
3899 | if (NULL == dv) | ||
3900 | { | ||
3901 | dv = GNUNET_new (struct DistanceVector); | ||
3902 | dv->target = path[path_len - 1]; | ||
3903 | dv->timeout_task = GNUNET_SCHEDULER_add_delayed (DV_PATH_VALIDITY_TIMEOUT, | ||
3904 | &path_cleanup_cb, | ||
3905 | dv); | ||
3906 | GNUNET_assert (GNUNET_OK == | ||
3907 | GNUNET_CONTAINER_multipeermap_put (dv_routes, | ||
3908 | &dv->target, | ||
3909 | dv, | ||
3910 | GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); | ||
3911 | } | ||
3912 | /* Check if we have this path already! */ | ||
3913 | shorter_distance = 0; | ||
3914 | for (struct DistanceVectorHop *pos = dv->dv_head; | ||
3915 | NULL != pos; | ||
3916 | pos = pos->next_dv) | ||
3917 | { | ||
3918 | if (pos->distance < path_len - 2) | ||
3919 | shorter_distance++; | ||
3920 | /* Note that the distances in 'pos' excludes us (path[0]) and | ||
3921 | the next_hop (path[1]), so we need to subtract two | ||
3922 | and check next_hop explicitly */ | ||
3923 | if ( (pos->distance == path_len - 2) && | ||
3924 | (pos->next_hop == next_hop) ) | ||
3925 | { | ||
3926 | int match = GNUNET_YES; | ||
3927 | |||
3928 | for (unsigned int i=0;i<pos->distance;i++) | ||
3929 | { | ||
3930 | if (0 != | ||
3931 | GNUNET_memcmp (&pos->path[i], | ||
3932 | &path[i+2])) | ||
3933 | { | ||
3934 | match = GNUNET_NO; | ||
3935 | break; | ||
3936 | } | ||
3937 | } | ||
3938 | if (GNUNET_YES == match) | ||
3939 | { | ||
3940 | struct GNUNET_TIME_Relative last_timeout; | ||
3941 | |||
3942 | /* Re-discovered known path, update timeout */ | ||
3943 | GNUNET_STATISTICS_update (GST_stats, | ||
3944 | "# Known DV path refreshed", | ||
3945 | 1, | ||
3946 | GNUNET_NO); | ||
3947 | last_timeout = GNUNET_TIME_absolute_get_remaining (pos->timeout); | ||
3948 | pos->timeout | ||
3949 | = GNUNET_TIME_relative_to_absolute (DV_PATH_VALIDITY_TIMEOUT); | ||
3950 | GNUNET_CONTAINER_MDLL_remove (dv, | ||
3951 | dv->dv_head, | ||
3952 | dv->dv_tail, | ||
3953 | pos); | ||
3954 | GNUNET_CONTAINER_MDLL_insert (dv, | ||
3955 | dv->dv_head, | ||
3956 | dv->dv_tail, | ||
3957 | pos); | ||
3958 | if (last_timeout.rel_value_us < | ||
3959 | GNUNET_TIME_relative_subtract (DV_PATH_VALIDITY_TIMEOUT, | ||
3960 | DV_PATH_DISCOVERY_FREQUENCY).rel_value_us) | ||
3961 | { | ||
3962 | /* Some peer send DV learn messages too often, we are learning | ||
3963 | the same path faster than it would be useful; do not forward! */ | ||
3964 | return GNUNET_NO; | ||
3965 | } | ||
3966 | return GNUNET_YES; | ||
3967 | } | ||
3968 | } | ||
3969 | } | ||
3970 | /* Count how many shorter paths we have (incl. direct | ||
3971 | neighbours) before simply giving up on this one! */ | ||
3972 | if (shorter_distance >= MAX_DV_PATHS_TO_TARGET) | ||
3973 | { | ||
3974 | /* We have a shorter path already! */ | ||
3975 | return GNUNET_NO; | ||
3976 | } | ||
3977 | /* create new DV path entry */ | ||
3978 | hop = GNUNET_malloc (sizeof (struct DistanceVectorHop) + | ||
3979 | sizeof (struct GNUNET_PeerIdentity) * (path_len - 2)); | ||
3980 | hop->next_hop = next_hop; | ||
3981 | hop->dv = dv; | ||
3982 | hop->path = (const struct GNUNET_PeerIdentity *) &hop[1]; | ||
3983 | memcpy (&hop[1], | ||
3984 | &path[2], | ||
3985 | sizeof (struct GNUNET_PeerIdentity) * (path_len - 2)); | ||
3986 | hop->timeout = GNUNET_TIME_relative_to_absolute (DV_PATH_VALIDITY_TIMEOUT); | ||
3987 | hop->distance = path_len - 2; | ||
3988 | GNUNET_CONTAINER_MDLL_insert (dv, | ||
3989 | dv->dv_head, | ||
3990 | dv->dv_tail, | ||
3991 | hop); | ||
3992 | GNUNET_CONTAINER_MDLL_insert (neighbour, | ||
3993 | next_hop->dv_head, | ||
3994 | next_hop->dv_tail, | ||
3995 | hop); | ||
3996 | return GNUNET_YES; | ||
3997 | } | ||
3998 | |||
3999 | |||
4000 | /** | ||
3688 | * Communicator gave us a DV learn message. Check the message. | 4001 | * Communicator gave us a DV learn message. Check the message. |
3689 | * | 4002 | * |
3690 | * @param cls a `struct CommunicatorMessageContext` | 4003 | * @param cls a `struct CommunicatorMessageContext` |
@@ -3697,9 +4010,14 @@ check_dv_learn (void *cls, | |||
3697 | { | 4010 | { |
3698 | uint16_t size = ntohs (dvl->header.size); | 4011 | uint16_t size = ntohs (dvl->header.size); |
3699 | uint16_t num_hops = ntohs (dvl->num_hops); | 4012 | uint16_t num_hops = ntohs (dvl->num_hops); |
3700 | const struct GNUNET_PeerIdentity *hops = (const struct GNUNET_PeerIdentity *) &dvl[1]; | 4013 | const struct DVPathEntryP *hops = (const struct DVPathEntryP *) &dvl[1]; |
3701 | 4014 | ||
3702 | if (size != sizeof (*dvl) + num_hops * sizeof (struct GNUNET_PeerIdentity)) | 4015 | if (size != sizeof (*dvl) + num_hops * sizeof (struct DVPathEntryP)) |
4016 | { | ||
4017 | GNUNET_break_op (0); | ||
4018 | return GNUNET_SYSERR; | ||
4019 | } | ||
4020 | if (num_hops > MAX_DV_HOPS_ALLOWED) | ||
3703 | { | 4021 | { |
3704 | GNUNET_break_op (0); | 4022 | GNUNET_break_op (0); |
3705 | return GNUNET_SYSERR; | 4023 | return GNUNET_SYSERR; |
@@ -3707,13 +4025,13 @@ check_dv_learn (void *cls, | |||
3707 | for (unsigned int i=0;i<num_hops;i++) | 4025 | for (unsigned int i=0;i<num_hops;i++) |
3708 | { | 4026 | { |
3709 | if (0 == GNUNET_memcmp (&dvl->initiator, | 4027 | if (0 == GNUNET_memcmp (&dvl->initiator, |
3710 | &hops[i])) | 4028 | &hops[i].hop)) |
3711 | { | 4029 | { |
3712 | GNUNET_break_op (0); | 4030 | GNUNET_break_op (0); |
3713 | return GNUNET_SYSERR; | 4031 | return GNUNET_SYSERR; |
3714 | } | 4032 | } |
3715 | if (0 == GNUNET_memcmp (&GST_my_identity, | 4033 | if (0 == GNUNET_memcmp (&GST_my_identity, |
3716 | &hops[i])) | 4034 | &hops[i].hop)) |
3717 | { | 4035 | { |
3718 | GNUNET_break_op (0); | 4036 | GNUNET_break_op (0); |
3719 | return GNUNET_SYSERR; | 4037 | return GNUNET_SYSERR; |
@@ -3724,6 +4042,99 @@ check_dv_learn (void *cls, | |||
3724 | 4042 | ||
3725 | 4043 | ||
3726 | /** | 4044 | /** |
4045 | * Build and forward a DV learn message to @a next_hop. | ||
4046 | * | ||
4047 | * @param next_hop peer to send the message to | ||
4048 | * @param msg message received | ||
4049 | * @param bi_history bitmask specifying hops on path that were bidirectional | ||
4050 | * @param nhops length of the @a hops array | ||
4051 | * @param hops path the message traversed so far | ||
4052 | * @param in_time when did we receive the message, used to calculate network delay | ||
4053 | */ | ||
4054 | static void | ||
4055 | forward_dv_learn (const struct GNUNET_PeerIdentity *next_hop, | ||
4056 | const struct TransportDVLearn *msg, | ||
4057 | uint16_t bi_history, | ||
4058 | uint16_t nhops, | ||
4059 | const struct DVPathEntryP *hops, | ||
4060 | struct GNUNET_TIME_Absolute in_time) | ||
4061 | { | ||
4062 | struct DVPathEntryP *dhops; | ||
4063 | struct TransportDVLearn *fwd; | ||
4064 | struct GNUNET_TIME_Relative nnd; | ||
4065 | |||
4066 | /* compute message for forwarding */ | ||
4067 | GNUNET_assert (nhops < MAX_DV_HOPS_ALLOWED); | ||
4068 | fwd = GNUNET_malloc (sizeof (struct TransportDVLearn) + | ||
4069 | (nhops + 1) * sizeof (struct DVPathEntryP)); | ||
4070 | fwd->header.type = htons (GNUNET_MESSAGE_TYPE_TRANSPORT_DV_LEARN); | ||
4071 | fwd->header.size = htons (sizeof (struct TransportDVLearn) + | ||
4072 | (nhops + 1) * sizeof (struct DVPathEntryP)); | ||
4073 | fwd->num_hops = htons (nhops + 1); | ||
4074 | fwd->bidirectional = htons (bi_history); | ||
4075 | nnd = GNUNET_TIME_relative_add (GNUNET_TIME_absolute_get_duration (in_time), | ||
4076 | GNUNET_TIME_relative_ntoh (msg->non_network_delay)); | ||
4077 | fwd->non_network_delay = GNUNET_TIME_relative_hton (nnd); | ||
4078 | fwd->init_sig = msg->init_sig; | ||
4079 | fwd->initiator = msg->initiator; | ||
4080 | fwd->challenge = msg->challenge; | ||
4081 | dhops = (struct DVPathEntryP *) &fwd[1]; | ||
4082 | GNUNET_memcpy (dhops, | ||
4083 | hops, | ||
4084 | sizeof (struct DVPathEntryP) * nhops); | ||
4085 | dhops[nhops].hop = GST_my_identity; | ||
4086 | { | ||
4087 | struct DvHopPS dhp = { | ||
4088 | .purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_TRANSPORT_DV_HOP), | ||
4089 | .purpose.size = htonl (sizeof (dhp)), | ||
4090 | .pred = dhops[nhops-1].hop, | ||
4091 | .succ = *next_hop, | ||
4092 | .challenge = msg->challenge | ||
4093 | }; | ||
4094 | |||
4095 | GNUNET_assert (GNUNET_OK == | ||
4096 | GNUNET_CRYPTO_eddsa_sign (GST_my_private_key, | ||
4097 | &dhp.purpose, | ||
4098 | &dhops[nhops].hop_sig)); | ||
4099 | } | ||
4100 | route_message (next_hop, | ||
4101 | &fwd->header); | ||
4102 | } | ||
4103 | |||
4104 | |||
4105 | /** | ||
4106 | * Check signature of type #GNUNET_SIGNATURE_PURPOSE_TRANSPORT_DV_INITIATOR | ||
4107 | * | ||
4108 | * @param init the signer | ||
4109 | * @param challenge the challenge that was signed | ||
4110 | * @param init_sig signature presumably by @a init | ||
4111 | * @return #GNUNET_OK if the signature is valid | ||
4112 | */ | ||
4113 | static int | ||
4114 | validate_dv_initiator_signature (const struct GNUNET_PeerIdentity *init, | ||
4115 | const struct GNUNET_ShortHashCode *challenge, | ||
4116 | const struct GNUNET_CRYPTO_EddsaSignature *init_sig) | ||
4117 | { | ||
4118 | struct DvInitPS ip = { | ||
4119 | .purpose.purpose = htonl (GNUNET_SIGNATURE_PURPOSE_TRANSPORT_DV_INITIATOR), | ||
4120 | .purpose.size = htonl (sizeof (ip)), | ||
4121 | .challenge = *challenge | ||
4122 | }; | ||
4123 | |||
4124 | if (GNUNET_OK != | ||
4125 | GNUNET_CRYPTO_eddsa_verify (GNUNET_SIGNATURE_PURPOSE_TRANSPORT_DV_INITIATOR, | ||
4126 | &ip.purpose, | ||
4127 | init_sig, | ||
4128 | &init->public_key)) | ||
4129 | { | ||
4130 | GNUNET_break_op (0); | ||
4131 | return GNUNET_SYSERR; | ||
4132 | } | ||
4133 | return GNUNET_OK; | ||
4134 | } | ||
4135 | |||
4136 | |||
4137 | /** | ||
3727 | * Communicator gave us a DV learn message. Process the request. | 4138 | * Communicator gave us a DV learn message. Process the request. |
3728 | * | 4139 | * |
3729 | * @param cls a `struct CommunicatorMessageContext` (must call #finish_cmc_handling() when done) | 4140 | * @param cls a `struct CommunicatorMessageContext` (must call #finish_cmc_handling() when done) |
@@ -3734,10 +4145,199 @@ handle_dv_learn (void *cls, | |||
3734 | const struct TransportDVLearn *dvl) | 4145 | const struct TransportDVLearn *dvl) |
3735 | { | 4146 | { |
3736 | struct CommunicatorMessageContext *cmc = cls; | 4147 | struct CommunicatorMessageContext *cmc = cls; |
4148 | enum GNUNET_TRANSPORT_CommunicatorCharacteristics cc; | ||
4149 | int bi_hop; | ||
4150 | uint16_t nhops; | ||
4151 | uint16_t bi_history; | ||
4152 | const struct DVPathEntryP *hops; | ||
4153 | int do_fwd; | ||
4154 | int did_initiator; | ||
4155 | struct GNUNET_TIME_Absolute in_time; | ||
4156 | |||
4157 | nhops = ntohs (dvl->bidirectional); /* 0 = sender is initiator */ | ||
4158 | bi_history = ntohs (dvl->bidirectional); | ||
4159 | hops = (const struct DVPathEntryP *) &dvl[1]; | ||
4160 | if (0 == nhops) | ||
4161 | { | ||
4162 | /* sanity check */ | ||
4163 | if (0 != GNUNET_memcmp (&dvl->initiator, | ||
4164 | &cmc->im.sender)) | ||
4165 | { | ||
4166 | GNUNET_break (0); | ||
4167 | finish_cmc_handling (cmc); | ||
4168 | return; | ||
4169 | } | ||
4170 | } | ||
4171 | else | ||
4172 | { | ||
4173 | /* sanity check */ | ||
4174 | if (0 != GNUNET_memcmp (&hops[nhops - 1].hop, | ||
4175 | &cmc->im.sender)) | ||
4176 | { | ||
4177 | GNUNET_break (0); | ||
4178 | finish_cmc_handling (cmc); | ||
4179 | return; | ||
4180 | } | ||
4181 | } | ||
4182 | |||
4183 | GNUNET_assert (CT_COMMUNICATOR == cmc->tc->type); | ||
4184 | cc = cmc->tc->details.communicator.cc; | ||
4185 | bi_hop = (GNUNET_TRANSPORT_CC_RELIABLE == cc); // FIXME: add bi-directional flag to cc? | ||
4186 | in_time = GNUNET_TIME_absolute_get (); | ||
3737 | 4187 | ||
3738 | // FIXME: learn path from DV message (if bi-directional flags are set) | 4188 | /* continue communicator here, everything else can happen asynchronous! */ |
3739 | // FIXME: expand DV message, forward on (unless path is getting too long) | ||
3740 | finish_cmc_handling (cmc); | 4189 | finish_cmc_handling (cmc); |
4190 | |||
4191 | // FIXME: should we bother to verify _every_ DV initiator signature? | ||
4192 | if (GNUNET_OK != | ||
4193 | validate_dv_initiator_signature (&dvl->initiator, | ||
4194 | &dvl->challenge, | ||
4195 | &dvl->init_sig)) | ||
4196 | { | ||
4197 | GNUNET_break_op (0); | ||
4198 | return; | ||
4199 | } | ||
4200 | // FIXME: asynchronously (!) verify hop-by-hop signatures! | ||
4201 | // => if signature verification load too high, implement random drop strategy! | ||
4202 | |||
4203 | do_fwd = GNUNET_YES; | ||
4204 | if (0 == GNUNET_memcmp (&GST_my_identity, | ||
4205 | &dvl->initiator)) | ||
4206 | { | ||
4207 | struct GNUNET_PeerIdentity path[nhops + 1]; | ||
4208 | struct GNUNET_TIME_Relative host_latency_sum; | ||
4209 | struct GNUNET_TIME_Relative latency; | ||
4210 | struct GNUNET_TIME_Relative network_latency; | ||
4211 | |||
4212 | /* We initiated this, learn the forward path! */ | ||
4213 | path[0] = GST_my_identity; | ||
4214 | path[1] = hops[0].hop; | ||
4215 | host_latency_sum = GNUNET_TIME_relative_ntoh (dvl->non_network_delay); | ||
4216 | |||
4217 | // Need also something to lookup initiation time | ||
4218 | // to compute RTT! -> add RTT argument here? | ||
4219 | latency = GNUNET_TIME_UNIT_FOREVER_REL; // FIXME: initialize properly | ||
4220 | // (based on dvl->challenge, we can identify time of origin!) | ||
4221 | |||
4222 | network_latency = GNUNET_TIME_relative_subtract (latency, | ||
4223 | host_latency_sum); | ||
4224 | /* assumption: latency on all links is the same */ | ||
4225 | network_latency = GNUNET_TIME_relative_divide (network_latency, | ||
4226 | nhops); | ||
4227 | |||
4228 | for (unsigned int i=2;i<=nhops;i++) | ||
4229 | { | ||
4230 | struct GNUNET_TIME_Relative ilat; | ||
4231 | |||
4232 | /* assumption: linear latency increase per hop */ | ||
4233 | ilat = GNUNET_TIME_relative_multiply (network_latency, | ||
4234 | i); | ||
4235 | path[i] = hops[i-1].hop; | ||
4236 | learn_dv_path (path, | ||
4237 | i, | ||
4238 | ilat); | ||
4239 | } | ||
4240 | /* as we initiated, do not forward again (would be circular!) */ | ||
4241 | do_fwd = GNUNET_NO; | ||
4242 | return; | ||
4243 | } | ||
4244 | else if (bi_hop) | ||
4245 | { | ||
4246 | /* last hop was bi-directional, we could learn something here! */ | ||
4247 | struct GNUNET_PeerIdentity path[nhops + 2]; | ||
4248 | |||
4249 | path[0] = GST_my_identity; | ||
4250 | path[1] = hops[nhops - 1].hop; /* direct neighbour == predecessor! */ | ||
4251 | for (unsigned int i=0;i<nhops;i++) | ||
4252 | { | ||
4253 | int iret; | ||
4254 | |||
4255 | if (0 == (bi_history & (1 << i))) | ||
4256 | break; /* i-th hop not bi-directional, stop learning! */ | ||
4257 | if (i == nhops) | ||
4258 | { | ||
4259 | path[i + 2] = dvl->initiator; | ||
4260 | } | ||
4261 | else | ||
4262 | { | ||
4263 | path[i + 2] = hops[nhops - i - 2].hop; | ||
4264 | } | ||
4265 | |||
4266 | iret = learn_dv_path (path, | ||
4267 | i + 2, | ||
4268 | GNUNET_TIME_UNIT_FOREVER_REL); | ||
4269 | if (GNUNET_SYSERR == iret) | ||
4270 | { | ||
4271 | /* path invalid or too long to be interesting for US, thus should also | ||
4272 | not be interesting to our neighbours, cut path when forwarding to | ||
4273 | 'i' hops, except of course for the one that goes back to the | ||
4274 | initiator */ | ||
4275 | GNUNET_STATISTICS_update (GST_stats, | ||
4276 | "# DV learn not forwarded due invalidity of path", | ||
4277 | 1, | ||
4278 | GNUNET_NO); | ||
4279 | do_fwd = GNUNET_NO; | ||
4280 | break; | ||
4281 | } | ||
4282 | if ( (GNUNET_NO == iret) && | ||
4283 | (nhops - 1 == i) ) | ||
4284 | { | ||
4285 | /* we have better paths, and this is the longest target, | ||
4286 | so there cannot be anything interesting later */ | ||
4287 | GNUNET_STATISTICS_update (GST_stats, | ||
4288 | "# DV learn not forwarded, got better paths", | ||
4289 | 1, | ||
4290 | GNUNET_NO); | ||
4291 | do_fwd = GNUNET_NO; | ||
4292 | break; | ||
4293 | } | ||
4294 | } | ||
4295 | } | ||
4296 | |||
4297 | if (MAX_DV_HOPS_ALLOWED == nhops) | ||
4298 | { | ||
4299 | /* At limit, we're out of here! */ | ||
4300 | finish_cmc_handling (cmc); | ||
4301 | return; | ||
4302 | } | ||
4303 | |||
4304 | /* Forward to initiator, if path non-trivial and possible */ | ||
4305 | bi_history = (bi_history << 1) | (bi_hop ? 1 : 0); | ||
4306 | did_initiator = GNUNET_NO; | ||
4307 | if ( (1 < nhops) && | ||
4308 | (GNUNET_YES == | ||
4309 | GNUNET_CONTAINER_multipeermap_contains (neighbours, | ||
4310 | &dvl->initiator)) ) | ||
4311 | { | ||
4312 | /* send back to origin! */ | ||
4313 | forward_dv_learn (&dvl->initiator, | ||
4314 | dvl, | ||
4315 | bi_history, | ||
4316 | nhops, | ||
4317 | hops, | ||
4318 | in_time); | ||
4319 | did_initiator = GNUNET_YES; | ||
4320 | } | ||
4321 | /* We forward under two conditions: either we still learned something | ||
4322 | ourselves (do_fwd), or the path was darn short and thus the initiator is | ||
4323 | likely to still be very interested in this (and we did NOT already | ||
4324 | send it back to the initiator) */ | ||
4325 | if ( (do_fwd) || | ||
4326 | ( (nhops < MIN_DV_PATH_LENGTH_FOR_INITIATOR) && | ||
4327 | (GNUNET_NO == did_initiator) ) ) | ||
4328 | { | ||
4329 | /* FIXME: loop over all neighbours, pick those with low | ||
4330 | queues AND that are not yet on the path; possibly | ||
4331 | adapt threshold to nhops! */ | ||
4332 | #if FIXME | ||
4333 | forward_dv_learn (NULL, // fill in peer from iterator here! | ||
4334 | dvl, | ||
4335 | bi_history, | ||
4336 | nhops, | ||
4337 | hops, | ||
4338 | in_time); | ||
4339 | #endif | ||
4340 | } | ||
3741 | } | 4341 | } |
3742 | 4342 | ||
3743 | 4343 | ||