aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--src/dht/gnunet-service-xdht_neighbours.c217
-rw-r--r--src/dht/gnunet-service-xdht_routing.c2
2 files changed, 115 insertions, 104 deletions
diff --git a/src/dht/gnunet-service-xdht_neighbours.c b/src/dht/gnunet-service-xdht_neighbours.c
index 75cce84a8..b62e622cb 100644
--- a/src/dht/gnunet-service-xdht_neighbours.c
+++ b/src/dht/gnunet-service-xdht_neighbours.c
@@ -809,35 +809,36 @@ struct FingerInfo
809struct Closest_Peer 809struct Closest_Peer
810{ 810{
811 /** 811 /**
812 * Destination finger vaule. 812 * Destination finger value.
813 */ 813 */
814 uint64_t destination_finger_value; 814 uint64_t destination_finger_value;
815 815
816 /** 816 /**
817 * Is finger value predecessor or any other finge 817 * Is finger_value a predecessor or any other finger.
818 */ 818 */
819 unsigned int is_predecessor; 819 unsigned int is_predecessor;
820 820
821 /** 821 /**
822 * Trail id to reach to peer. 822 * Trail id to reach to peer.
823 * In case peer is my identity or friend, it is set to 0.
823 */ 824 */
824 struct GNUNET_HashCode trail_id; 825 struct GNUNET_HashCode trail_id;
825 826
826 /** 827 /**
827 * FIXME: see the usage of this field and write comment.
828 */
829 struct GNUNET_PeerIdentity next_hop;
830
831 /**
832 * Next destination. In case of friend and my_identity , it is same as next_hop 828 * Next destination. In case of friend and my_identity , it is same as next_hop
833 * In case of finger it is finger identity. 829 * In case of finger it is finger identity.
834 */ 830 */
835 struct GNUNET_PeerIdentity best_known_destination; 831 struct GNUNET_PeerIdentity best_known_destination;
832
833 /**
834 * In case best_known_destination is a finger, then first friend in the trail
835 * to reach to it. In other case, same as best_known_destination.
836 */
837 struct GNUNET_PeerIdentity next_hop;
836}; 838};
837 839
840
838/** 841/**
839 * FIXME: now I have removed the first_friend_trail_count,
840 * Need to update the code to find the count.
841 * Data structure to store the trail chosen to reach to finger. 842 * Data structure to store the trail chosen to reach to finger.
842 */ 843 */
843struct Selected_Finger_Trail 844struct Selected_Finger_Trail
@@ -1095,9 +1096,9 @@ GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity source_peer,
1095 * @param Finger Peer to which the trail has been setup to. 1096 * @param Finger Peer to which the trail has been setup to.
1096 * @param target_friend Friend to which this message should be forwarded. 1097 * @param target_friend Friend to which this message should be forwarded.
1097 * @param trail_length Numbers of peers in the trail. 1098 * @param trail_length Numbers of peers in the trail.
1098 * @param trail_peer_list Peers which are part of the trail from q 1099 * @param trail_peer_list Peers which are part of the trail from
1099 * querying_peer to Finger, NOT including them. 1100 * querying_peer to Finger, NOT including them.
1100 * @param is_predecessor Is @a Finger predecessor to @a querying_peer 1101 * @param is_predecessor Is @a Finger predecessor to @a querying_peer ?
1101 * @param ultimate_destination_finger_value Value to which @a finger is the closest 1102 * @param ultimate_destination_finger_value Value to which @a finger is the closest
1102 * peer. 1103 * peer.
1103 * @param trail_id Unique identifier of the trail. 1104 * @param trail_id Unique identifier of the trail.
@@ -1165,9 +1166,10 @@ GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity querying_peer
1165 * @param congested_peer Peer which sent this message as it is congested. 1166 * @param congested_peer Peer which sent this message as it is congested.
1166 * @param is_predecessor Is source_peer looking for trail to a predecessor or not. 1167 * @param is_predecessor Is source_peer looking for trail to a predecessor or not.
1167 * @param trail_peer_list Trails seen so far in trail setup before getting rejected 1168 * @param trail_peer_list Trails seen so far in trail setup before getting rejected
1168 * by congested_peer. This does not include @a source_peer 1169 * by congested_peer. This does NOT include @a source_peer
1169 * @param trail_length Total number of peers in trail_peer_list, not including 1170 * and congested_peer.
1170 * @a source_peer 1171 * @param trail_length Total number of peers in trail_peer_list, NOT including
1172 * @a source_peer and @a congested_peer
1171 * @param trail_id Unique identifier of this trail. 1173 * @param trail_id Unique identifier of this trail.
1172 * @param congestion_timeout Duration given by congested peer as an estimate of 1174 * @param congestion_timeout Duration given by congested peer as an estimate of
1173 * how long it may remain congested. 1175 * how long it may remain congested.
@@ -1215,7 +1217,8 @@ GDS_NEIGHBOURS_send_trail_rejection (struct GNUNET_PeerIdentity source_peer,
1215 trm->congestion_time = congestion_timeout; 1217 trm->congestion_time = congestion_timeout;
1216 trm->is_predecessor = htonl (is_predecessor); 1218 trm->is_predecessor = htonl (is_predecessor);
1217 trm->trail_id = trail_id; 1219 trm->trail_id = trail_id;
1218 trm->ultimate_destination_finger_value = GNUNET_htonll (ultimate_destination_finger_value); 1220 trm->ultimate_destination_finger_value =
1221 GNUNET_htonll (ultimate_destination_finger_value);
1219 1222
1220 peer_list = (struct GNUNET_PeerIdentity *) &trm[1]; 1223 peer_list = (struct GNUNET_PeerIdentity *) &trm[1];
1221 if (trail_length > 0) 1224 if (trail_length > 0)
@@ -1635,76 +1638,6 @@ is_friend_congested (struct FriendInfo *friend)
1635 1638
1636 1639
1637/** 1640/**
1638 * Iterate over the list of all the trails of a finger. In case the first
1639 * friend to reach the finger has reached trail threshold or is congested,
1640 * then don't select it. In case there multiple available good trails to reach
1641 * to Finger, choose the one with shortest trail length.
1642 * Note: We use length as parameter. But we can use any other suitable parameter
1643 * also.
1644 * @param finger Finger
1645 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1646 * and trail length. NULL in case none of the trails are free.
1647 */
1648static struct Selected_Finger_Trail *
1649select_finger_trail (struct FingerInfo *finger)
1650{
1651 struct FriendInfo *friend;
1652 struct Trail *iterator;
1653 struct Selected_Finger_Trail *finger_trail;
1654 unsigned int i;
1655 unsigned int flag = 0;
1656 unsigned int j = 0;
1657
1658 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1659
1660 /* It can never happen that we have a finger (which is not a friend or my identity),
1661 and we don't have a trail to reach to it. */
1662 GNUNET_assert (finger->trails_count > 0);
1663
1664 for (i = 0; i < finger->trails_count; i++)
1665 {
1666 iterator = &finger->trail_list[i];
1667
1668 /* No trail stored at this index. */
1669 if (GNUNET_NO == iterator->is_present)
1670 continue;
1671
1672 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1673 &iterator->trail_head->peer);
1674
1675 /* First friend to reach trail is not free. */
1676 if (GNUNET_YES == is_friend_congested (friend))
1677 {
1678 j++;
1679 continue;
1680 }
1681 /* This is the first time we enter the loop. Set finger trail length to
1682 * trail length of this trail. */
1683 if (!flag)
1684 {
1685 flag = 1;
1686 finger_trail->trail_length = iterator->trail_length;
1687 }
1688 else if (finger_trail->trail_length > iterator->trail_length)
1689 {
1690 /* Check if the trail length of this trail is least seen so far. If yes then
1691 set finger_trail to this trail.*/
1692 finger_trail->friend = *friend;
1693 finger_trail->trail_id = iterator->trail_id;
1694 finger_trail->trail_length = iterator->trail_length;
1695 }
1696 }
1697
1698 /* All the first friend in all the trails to reach to finger are either
1699 congested or have crossed trail threshold. */
1700 if (j == finger->trails_count)
1701 return NULL;
1702
1703 return finger_trail;
1704}
1705
1706
1707/**
1708 * FIXME; not handling the wrap around logic correctly. 1641 * FIXME; not handling the wrap around logic correctly.
1709 * Select closest finger to value. 1642 * Select closest finger to value.
1710 * @param peer1 First peer 1643 * @param peer1 First peer
@@ -1820,20 +1753,18 @@ select_closest_predecessor (struct GNUNET_PeerIdentity *peer1,
1820 * @param peer1 First peer 1753 * @param peer1 First peer
1821 * @param peer2 Second peer 1754 * @param peer2 Second peer
1822 * @param value Value relative to which we find the closest 1755 * @param value Value relative to which we find the closest
1823 * @param finger_table_index Index in finger map. If equal to PREDECESSOR_FINGER_ID, 1756 * @param is_predecessor Is value a predecessor or any other finger.
1824 * then we use different logic than other
1825 * finger_table_index
1826 * @return Closest peer among two peers. 1757 * @return Closest peer among two peers.
1827 */ 1758 */
1828static struct GNUNET_PeerIdentity * 1759static struct GNUNET_PeerIdentity *
1829select_closest_peer (struct GNUNET_PeerIdentity *peer1, 1760select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1830 struct GNUNET_PeerIdentity *peer2, 1761 struct GNUNET_PeerIdentity *peer2,
1831 uint64_t value, 1762 uint64_t value,
1832 unsigned int finger_table_index) 1763 unsigned int is_predecessor)
1833{ 1764{
1834 struct GNUNET_PeerIdentity *closest_peer; 1765 struct GNUNET_PeerIdentity *closest_peer;
1835 1766
1836 if (PREDECESSOR_FINGER_ID == finger_table_index) 1767 if (1 == is_predecessor)
1837 closest_peer = select_closest_predecessor (peer1, peer2, value); 1768 closest_peer = select_closest_predecessor (peer1, peer2, value);
1838 else 1769 else
1839 closest_peer = select_closest_finger (peer1, peer2, value); 1770 closest_peer = select_closest_finger (peer1, peer2, value);
@@ -1843,7 +1774,76 @@ select_closest_peer (struct GNUNET_PeerIdentity *peer1,
1843 1774
1844 1775
1845/** 1776/**
1846 * FIXME: better names and more refactoring. 1777 * Iterate over the list of all the trails of a finger. In case the first
1778 * friend to reach the finger has reached trail threshold or is congested,
1779 * then don't select it. In case there multiple available good trails to reach
1780 * to Finger, choose the one with shortest trail length.
1781 * Note: We use length as parameter. But we can use any other suitable parameter
1782 * also.
1783 * @param finger Finger
1784 * @return struct Selected_Finger_Trail which contains the first friend , trail id
1785 * and trail length. NULL in case none of the trails are free.
1786 */
1787static struct Selected_Finger_Trail *
1788select_finger_trail (struct FingerInfo *finger)
1789{
1790 struct FriendInfo *friend;
1791 struct Trail *iterator;
1792 struct Selected_Finger_Trail *finger_trail;
1793 unsigned int i;
1794 unsigned int flag = 0;
1795 unsigned int j = 0;
1796
1797 finger_trail = GNUNET_new (struct Selected_Finger_Trail);
1798
1799 /* It can never happen that we have a finger (which is not a friend or my identity),
1800 and we don't have a trail to reach to it. */
1801 GNUNET_assert (finger->trails_count > 0);
1802
1803 for (i = 0; i < finger->trails_count; i++)
1804 {
1805 iterator = &finger->trail_list[i];
1806
1807 /* No trail stored at this index. */
1808 if (GNUNET_NO == iterator->is_present)
1809 continue;
1810
1811 friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
1812 &iterator->trail_head->peer);
1813
1814 /* First friend to reach trail is not free. */
1815 if (GNUNET_YES == is_friend_congested (friend))
1816 {
1817 j++;
1818 continue;
1819 }
1820 /* This is the first time we enter the loop. Set finger trail length to
1821 * trail length of this trail. */
1822 if (!flag)
1823 {
1824 flag = 1;
1825 finger_trail->trail_length = iterator->trail_length;
1826 }
1827 else if (finger_trail->trail_length > iterator->trail_length)
1828 {
1829 /* Check if the trail length of this trail is least seen so far. If yes then
1830 set finger_trail to this trail.*/
1831 finger_trail->friend = *friend;
1832 finger_trail->trail_id = iterator->trail_id;
1833 finger_trail->trail_length = iterator->trail_length;
1834 }
1835 }
1836
1837 /* All the first friend in all the trails to reach to finger are either
1838 congested or have crossed trail threshold. */
1839 if (j == finger->trails_count)
1840 return NULL;
1841
1842 return finger_trail;
1843}
1844
1845
1846/**
1847 * Compare FINGER entry with current successor. If finger's first friend of all 1847 * Compare FINGER entry with current successor. If finger's first friend of all
1848 * its trail is not congested and has not crossed trail threshold, then check 1848 * its trail is not congested and has not crossed trail threshold, then check
1849 * if finger peer identity is closer to final_destination_finger_value than 1849 * if finger peer identity is closer to final_destination_finger_value than
@@ -1984,10 +1984,11 @@ init_current_successor (struct GNUNET_PeerIdentity my_identity,
1984 1984
1985 1985
1986/** 1986/**
1987 * FIXME: can we just send gnunet_peeridentit and not gnunet_peeridentity *?
1988 * Find the successor for destination_finger_value among my_identity, all my 1987 * Find the successor for destination_finger_value among my_identity, all my
1989 * friend and all my fingers. Don't consider friends or fingers which are either 1988 * friend and all my fingers. Don't consider friends or fingers which are either
1990 * congested or have crossed the threshold. 1989 * congested or have crossed the threshold.
1990 * NOTE: In case a friend is also a finger, then it is always chosen as friend
1991 * not a finger.
1991 * @param destination_finger_value Peer closest to this value will be the next successor. 1992 * @param destination_finger_value Peer closest to this value will be the next successor.
1992 * @param local_best_known_destination[out] Updated to my_identity if I am the 1993 * @param local_best_known_destination[out] Updated to my_identity if I am the
1993 * final destination. Updated to friend 1994 * final destination. Updated to friend
@@ -3231,7 +3232,7 @@ test_finger_table_print()
3231 * -- Update current_search_finger_index. 3232 * -- Update current_search_finger_index.
3232 * @param finger_identity Peer Identity of new finger 3233 * @param finger_identity Peer Identity of new finger
3233 * @param finger_trail Trail to reach the new finger 3234 * @param finger_trail Trail to reach the new finger
3234 * @param finger_length Total number of peers in @a new_finger_trail. 3235 * @param finger_trail_length Total number of peers in @a new_finger_trail.
3235 * @param is_predecessor Is this entry for predecessor in finger_table? 3236 * @param is_predecessor Is this entry for predecessor in finger_table?
3236 * @param finger_value 64 bit value of finger identity that we got from network. 3237 * @param finger_value 64 bit value of finger identity that we got from network.
3237 * @param finger_trail_id Unique identifier of @finger_trail. 3238 * @param finger_trail_id Unique identifier of @finger_trail.
@@ -3250,6 +3251,7 @@ finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3250 struct FingerInfo *successor; 3251 struct FingerInfo *successor;
3251 int updated_finger_trail_length; 3252 int updated_finger_trail_length;
3252 unsigned int finger_table_index; 3253 unsigned int finger_table_index;
3254
3253 3255
3254#if 0 3256#if 0
3255 test_friend_peermap_print(); 3257 test_friend_peermap_print();
@@ -3265,13 +3267,13 @@ finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3265 GNUNET_break_op (0); 3267 GNUNET_break_op (0);
3266 return; 3268 return;
3267 } 3269 }
3268 3270
3269 3271 /* If the new entry for any finger table index other than successor or predecessor
3270 /* If the new entry is same as successor then don't add it in finger table, 3272 * is same as successor then don't add it in finger table,
3271 reset the current search finger index and exit. */ 3273 * reset the current search finger index and exit. */
3272 if ((0 != finger_table_index) && 3274 if ((0 != finger_table_index) &&
3273 (PREDECESSOR_FINGER_ID != finger_table_index) && 3275 (PREDECESSOR_FINGER_ID != finger_table_index) &&
3274 (finger_table_index == current_search_finger_index)) 3276 (finger_table_index == current_search_finger_index)) //FIXME; why do I check this cond?
3275 { 3277 {
3276 successor = &finger_table[0]; 3278 successor = &finger_table[0];
3277 GNUNET_assert (GNUNET_YES == successor->is_present); 3279 GNUNET_assert (GNUNET_YES == successor->is_present);
@@ -3284,29 +3286,34 @@ finger_table_add (struct GNUNET_PeerIdentity finger_identity,
3284 } 3286 }
3285 3287
3286 existing_finger = &finger_table[finger_table_index]; 3288 existing_finger = &finger_table[finger_table_index];
3287 3289
3290 /* Shorten the trail if possible. */
3288 updated_finger_trail_length = finger_trail_length; 3291 updated_finger_trail_length = finger_trail_length;
3289 updated_trail = 3292 updated_trail =
3290 scan_and_compress_trail (finger_identity, finger_trail, 3293 scan_and_compress_trail (finger_identity, finger_trail,
3291 finger_trail_length, finger_trail_id, 3294 finger_trail_length, finger_trail_id,
3292 &updated_finger_trail_length); 3295 &updated_finger_trail_length);
3296
3293 /* No entry present in finger_table for given finger map index. */ 3297 /* No entry present in finger_table for given finger map index. */
3294 if (GNUNET_NO == existing_finger->is_present) 3298 if (GNUNET_NO == existing_finger->is_present)
3295 { 3299 {
3296 add_new_finger (finger_identity, updated_trail, updated_finger_trail_length, 3300 add_new_finger (finger_identity, updated_trail,
3301 updated_finger_trail_length,
3297 finger_trail_id, finger_table_index); 3302 finger_trail_id, finger_table_index);
3298 update_current_search_finger_index (finger_identity, finger_table_index); 3303 update_current_search_finger_index (finger_identity, finger_table_index);
3299 GNUNET_free_non_null (updated_trail); 3304 GNUNET_free_non_null (updated_trail);
3300 return; 3305 return;
3301 } 3306 }
3302 3307
3308
3303 /* If existing entry and finger identity are not same. */ 3309 /* If existing entry and finger identity are not same. */
3304 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity), 3310 if (0 != GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),
3305 &finger_identity)) 3311 &finger_identity))
3306 { 3312 {
3307 closest_peer = select_closest_peer (&existing_finger->finger_identity, 3313 closest_peer = select_closest_peer (&existing_finger->finger_identity,
3308 &finger_identity, 3314 &finger_identity,
3309 finger_value, finger_table_index); 3315 finger_value,
3316 is_predecessor);
3310 3317
3311 /* If the new finger is the closest peer. */ 3318 /* If the new finger is the closest peer. */
3312 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer)) 3319 if (0 == GNUNET_CRYPTO_cmp_peer_identity (&finger_identity, closest_peer))
@@ -4052,6 +4059,8 @@ handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *p
4052 return GNUNET_SYSERR; 4059 return GNUNET_SYSERR;
4053 } 4060 }
4054 4061
4062 /* FIXME: CHECK IF YOU ARE PRESENT MORE THAN ONCE IN THE TRAIL, IF YES
4063 THEN REMOVE ALL THE ENTRIES AND CHOOSE THE PEER THERE.*/
4055 if (my_index == 0) 4064 if (my_index == 0)
4056 next_hop = trail_result->querying_peer; 4065 next_hop = trail_result->querying_peer;
4057 else 4066 else
@@ -4268,6 +4277,7 @@ compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4268 struct FingerInfo *current_predecessor; 4277 struct FingerInfo *current_predecessor;
4269 struct GNUNET_PeerIdentity *closest_peer; 4278 struct GNUNET_PeerIdentity *closest_peer;
4270 uint64_t predecessor_value; 4279 uint64_t predecessor_value;
4280 unsigned int is_predecessor = 1;
4271 4281
4272 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID]; 4282 current_predecessor = &finger_table[PREDECESSOR_FINGER_ID];
4273 4283
@@ -4283,7 +4293,7 @@ compare_and_update_predecessor (struct GNUNET_PeerIdentity finger,
4283 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID); 4293 predecessor_value = compute_finger_identity_value (PREDECESSOR_FINGER_ID);
4284 closest_peer = select_closest_peer (&finger, 4294 closest_peer = select_closest_peer (&finger,
4285 &current_predecessor->finger_identity, 4295 &current_predecessor->finger_identity,
4286 predecessor_value, PREDECESSOR_FINGER_ID); 4296 predecessor_value, is_predecessor);
4287 4297
4288 /* Finger is the closest predecessor. Remove the existing one and add the new 4298 /* Finger is the closest predecessor. Remove the existing one and add the new
4289 one. */ 4299 one. */
@@ -4513,6 +4523,7 @@ compare_and_update_successor (struct GNUNET_PeerIdentity probable_successor,
4513 uint64_t successor_value; 4523 uint64_t successor_value;
4514 struct FingerInfo *current_successor; 4524 struct FingerInfo *current_successor;
4515 struct FriendInfo *target_friend; 4525 struct FriendInfo *target_friend;
4526 unsigned int is_predecessor = 0;
4516 4527
4517 current_successor = &finger_table[0]; 4528 current_successor = &finger_table[0];
4518 GNUNET_assert (GNUNET_YES == current_successor->is_present); 4529 GNUNET_assert (GNUNET_YES == current_successor->is_present);
@@ -4522,7 +4533,7 @@ compare_and_update_successor (struct GNUNET_PeerIdentity probable_successor,
4522 successor_value = compute_finger_identity_value (0); 4533 successor_value = compute_finger_identity_value (0);
4523 closest_peer = select_closest_peer (&current_successor->finger_identity, 4534 closest_peer = select_closest_peer (&current_successor->finger_identity,
4524 &probable_successor, 4535 &probable_successor,
4525 successor_value, 0); 4536 successor_value, is_predecessor);
4526 4537
4527 /* If the current_successor is the closest one, then exit. */ 4538 /* If the current_successor is the closest one, then exit. */
4528 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer, 4539 if (0 == GNUNET_CRYPTO_cmp_peer_identity (closest_peer,
diff --git a/src/dht/gnunet-service-xdht_routing.c b/src/dht/gnunet-service-xdht_routing.c
index 063bb13a5..a8895249a 100644
--- a/src/dht/gnunet-service-xdht_routing.c
+++ b/src/dht/gnunet-service-xdht_routing.c
@@ -276,7 +276,7 @@ GDS_ROUTING_add (struct GNUNET_HashCode new_trail_id,
276{ 276{
277 struct RoutingTrail *new_entry; 277 struct RoutingTrail *new_entry;
278 278
279 new_entry = GNUNET_malloc (sizeof (struct RoutingTrail)); 279 new_entry = GNUNET_new (struct RoutingTrail);
280 new_entry->trail_id = new_trail_id; 280 new_entry->trail_id = new_trail_id;
281 new_entry->next_hop = next_hop; 281 new_entry->next_hop = next_hop;
282 new_entry->prev_hop = prev_hop; 282 new_entry->prev_hop = prev_hop;