[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[GNUnet-SVN] r32706 - gnunet/src/dht
|
From: |
gnunet |
|
Subject: |
[GNUnet-SVN] r32706 - gnunet/src/dht |
|
Date: |
Thu, 20 Mar 2014 15:00:52 +0100 |
Author: supriti
Date: 2014-03-20 15:00:52 +0100 (Thu, 20 Mar 2014)
New Revision: 32706
Modified:
gnunet/src/dht/gnunet-service-xdht_neighbours.c
Log:
Updated find successor
Modified: gnunet/src/dht/gnunet-service-xdht_neighbours.c
===================================================================
--- gnunet/src/dht/gnunet-service-xdht_neighbours.c 2014-03-20 10:42:14 UTC
(rev 32705)
+++ gnunet/src/dht/gnunet-service-xdht_neighbours.c 2014-03-20 14:00:52 UTC
(rev 32706)
@@ -238,7 +238,8 @@
{
FRIEND ,
FINGER ,
- MY_ID
+ MY_ID ,
+ VALUE
};
@@ -595,7 +596,22 @@
};
+/**
+ * Data structure passed to sorting algorithm in find_successor.
+ */
+struct Sorting_List
+{
+ /* 64 bit value of peer identity */
+ uint64_t peer_id;
+
+ /* Type : MY_ID, FINGER, FINGER */
+ enum current_destination_type type;
+
+ /* Pointer to original data structure linked to peer id. */
+ void *data;
+};
+
/**
* Task that sends FIND FINGER TRAIL requests.
*/
@@ -754,8 +770,8 @@
* @param current_finger_index Finger index in finger peer map
*/
void
-GDS_NEIGHBOURS_handle_trail_setup (struct GNUNET_PeerIdentity *source_peer,
- uint64_t *destination_finger,
+GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity *source_peer,
+ uint64_t destination_finger,
struct FriendInfo *target_friend,
unsigned int trail_length,
struct GNUNET_PeerIdentity *trail_peer_list,
@@ -790,8 +806,7 @@
pending->msg = &tsm->header;
tsm->header.size = htons (msize);
tsm->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_TRAIL_SETUP);
- memcpy (&(tsm->destination_finger), destination_finger, sizeof (uint64_t));
/* FIXME: Wrong value of finger identity goes to the target peer in
-
* handle_dht_p2p_trail_setup */
+ memcpy (&(tsm->destination_finger), &destination_finger, sizeof (uint64_t));
memcpy (&(tsm->source_peer), source_peer, sizeof (struct
GNUNET_PeerIdentity));
memcpy (&(tsm->current_destination), &(target_friend->id),
sizeof (struct GNUNET_PeerIdentity));
@@ -813,6 +828,7 @@
tsm->successor_flag = htonl(0);
tsm->predecessor_flag = htonl(0);
}
+
peer_list = (struct GNUNET_PeerIdentity *) &tsm[1];
memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct
GNUNET_PeerIdentity));
GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail,
pending);
@@ -835,7 +851,7 @@
* @param finger_map_index Finger index in finger peer map
*/
void
-GDS_NEIGHBOURS_handle_trail_setup_result (struct GNUNET_PeerIdentity
*destination_peer,
+GDS_NEIGHBOURS_send_trail_setup_result (struct GNUNET_PeerIdentity
*destination_peer,
struct GNUNET_PeerIdentity
*source_finger,
struct FriendInfo *target_friend,
unsigned int trail_length,
@@ -900,7 +916,7 @@
* @param current_trail_index Index in the trial list at which receiving peer
should
* get the next element.
*/
-void GDS_NEIGHBOURS_handle_verify_successor(struct GNUNET_PeerIdentity
*source_peer,
+void GDS_NEIGHBOURS_send_verify_successor(struct GNUNET_PeerIdentity
*source_peer,
struct GNUNET_PeerIdentity
*successor,
struct FriendInfo *target_friend,
struct GNUNET_PeerIdentity
*trail_peer_list,
@@ -960,7 +976,7 @@
* @param current_trail_index Index in the trial list at which receiving peer
should
* get the next element.
*/
-void GDS_NEIGHBOURS_handle_verify_successor_result (struct GNUNET_PeerIdentity
*destination_peer,
+void GDS_NEIGHBOURS_send_verify_successor_result (struct GNUNET_PeerIdentity
*destination_peer,
struct GNUNET_PeerIdentity
*source_successor,
struct GNUNET_PeerIdentity
*my_predecessor,
struct FriendInfo
*target_friend,
@@ -982,6 +998,7 @@
return;
}
+
if (target_friend->pending_count >= MAXIMUM_PENDING_PER_FRIEND)
{
GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped
due to full queue"),
@@ -1021,7 +1038,7 @@
* @param trail_length Total number of peers in peer list
*/
void
-GDS_NEIGHBOURS_notify_new_successor (struct GNUNET_PeerIdentity *source_peer,
+GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity
*source_peer,
struct GNUNET_PeerIdentity
*destination_peer,
struct FriendInfo *target_friend,
struct GNUNET_PeerIdentity
*trail_peer_list,
@@ -1047,7 +1064,7 @@
GNUNET_STATISTICS_update (GDS_stats, gettext_noop ("# P2P messages dropped
due to full queue"),
1, GNUNET_NO);
}
-
+
pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize);
pending->importance = 0; /* FIXME */
pending->timeout = GNUNET_TIME_relative_to_absolute (GET_TIMEOUT);
@@ -1292,12 +1309,11 @@
is the next hop. */
next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
memcpy (next_hop, &peer_list[1], sizeof (struct GNUNET_PeerIdentity));
-
-
/* Find the friend corresponding to this next hop. */
target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop);
finger_trail_current_index = 2;
- GDS_NEIGHBOURS_handle_verify_successor (&my_identity,
+
+ GDS_NEIGHBOURS_send_verify_successor (&my_identity,
&(finger->finger_identity),
target_friend,
peer_list,
@@ -1311,7 +1327,7 @@
DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
- (current_finger_index + 1));
+ (current_finger_index + 50));
verify_successor =
GNUNET_SCHEDULER_add_delayed (next_send_time,
&send_verify_successor_message,
@@ -1366,7 +1382,7 @@
current_finger_index = ( current_finger_index + 1) % MAX_FINGERS;
target_friend = select_random_friend();
-
+
/* We found a friend.*/
if(NULL != target_friend)
{
@@ -1376,10 +1392,11 @@
memcpy (&peer_list[0], &(my_identity), sizeof (struct
GNUNET_PeerIdentity));
memcpy (&peer_list[1], &(target_friend->id), sizeof (struct
GNUNET_PeerIdentity));
- GDS_NEIGHBOURS_handle_trail_setup (&my_identity, finger_identity,
- target_friend, trail_length, peer_list,
- successor_flag, predecessor_flag,
- finger_index);
+ /* TODO send trail setup */
+ GDS_NEIGHBOURS_send_trail_setup (&my_identity, *finger_identity,
+ target_friend, trail_length, peer_list,
+ successor_flag, predecessor_flag,
+ finger_index);
}
/* FIXME: Should we be using current_finger_index to generate random
interval.*/
@@ -1387,7 +1404,7 @@
DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us +
GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK,
DHT_MAXIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us /
- (current_finger_index + 1));
+ (current_finger_index + 10));
find_finger_trail_task =
GNUNET_SCHEDULER_add_delayed (next_send_time,
&send_find_finger_trail_message,
@@ -1431,7 +1448,6 @@
peer_identity, friend,
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
-
/* got a first connection, good time to start with FIND FINGER TRAIL
requests... */
if (1 == GNUNET_CONTAINER_multipeermap_size (friend_peermap))
find_finger_trail_task = GNUNET_SCHEDULER_add_now
(&send_find_finger_trail_message, NULL);
@@ -1549,37 +1565,236 @@
return 0;
}
+/**
+ * FIXME: For redundant routing, we may start looking for different
+ * paths to reach to same finger. So, in send_find_finger, we are starting
+ * the search for trail to a finger, even if we already have found trail to
+ * reach to it. There are several reasons for doing so
+ * 1. We may reach to a closer successor than we have at the moment. So, we
+ * should keep looking for the successor.
+ * 2. We may reach to the same successor but through a shorter path.
+ * 3. As I don't know how keys are distributed and how put/get will react
+ * because of this, I have to think further before implementing it.
+ * Add an entry in finger table.
+ * @param finger Finger to be added to finger table
+ * @param peer_list peers this request has traversed so far
+ * @param trail_length Numbers of peers in the trail.
+ */
+static
+void finger_table_add (struct GNUNET_PeerIdentity *finger,
+ struct GNUNET_PeerIdentity *peer_list,
+ unsigned int trail_length,
+ unsigned int successor_flag,
+ unsigned int predecessor_flag,
+ unsigned int finger_map_index)
+{
+ struct FingerInfo *new_finger_entry;
+ unsigned int i = 0;
+ /** SUPU: when we add an entry then we should look if
+ * we already have an entry for that index. If yes, then
+ * 1) if both the finger identity are same, and same first friend, then choose
+ * the one with shorter trail length.
+ * 2) if the finger identity is different, then keep the one which is
closest.*/
+
+ if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains (finger_peermap,
finger))
+ {
+ exit(0);
+#if 0
+ /* Optimization. For the moment we just ignore and do nothing.*/
+ /* We already have an entry for this finger. */
+ struct GNUNET_PeerIdentity *first_friend;
+ struct FingerInfo *exisiting_finger_entry;
+
+ struct TrailPeerList *iterator;
+ iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
+ exisiting_finger_entry = GNUNET_CONTAINER_multipeermap_get(finger_peermap,
finger);
+ iterator = exisiting_finger_entry->head;
+ memcpy (first_friend, &(iterator->peer), sizeof(struct
GNUNET_PeerIdentity));
+
+ if(0 == GNUNET_CRYPTO_cmp_peer_identity(first_friend, finger))
+ {
+
+ }
+#endif
+ }
+
+ new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
+ memcpy (&(new_finger_entry->finger_identity), finger, sizeof (struct
GNUNET_PeerIdentity));
+
+ /* Insert elements of peer_list into TrailPeerList. */
+ i = 0;
+ while (i < trail_length)
+ {
+ struct TrailPeerList *element;
+ element = GNUNET_malloc (sizeof (struct TrailPeerList));
+ element->next = NULL;
+ element->prev = NULL;
+
+ memcpy (&(element->peer), &peer_list[i], sizeof(struct
GNUNET_PeerIdentity));
+ GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head,
new_finger_entry->tail, element);
+ i++;
+ }
+
+
+ new_finger_entry->successor = successor_flag;
+ new_finger_entry->predecessor = predecessor_flag;
+ new_finger_entry->finger_map_index = finger_map_index;
+ new_finger_entry->trail_length = trail_length;
+
+
+ GNUNET_assert (GNUNET_OK ==
+ GNUNET_CONTAINER_multipeermap_put (finger_peermap,
+
&(new_finger_entry->finger_identity),
+ new_finger_entry,
+
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
+
+ /*FIXME: Is it really a good time to call verify successor message. */
+ if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap))
+ {
+ verify_successor = GNUNET_SCHEDULER_add_now
(&send_verify_successor_message, NULL);
+ }
+}
+
+
/**
+ * FIXME: Also copy the trail list in reverse direction that is the path to
+ * reach to your predecessor.
+ * Replace your predecessor with new predecessor.
+ * @param predecessor My new predecessor
+ * @param peer_list Trail list to reach to my new predecessor
+ * @param trail_length Number of peers in the trail.
+ */
+static void
+update_predecessor (struct GNUNET_PeerIdentity *predecessor,
+ struct GNUNET_PeerIdentity *peer_list,
+ unsigned int trail_length)
+{
+ struct GNUNET_PeerIdentity *trail_peer_list;
+ struct FingerInfo *new_finger_entry;
+ struct FingerInfo *finger;
+ struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
+ struct GNUNET_PeerIdentity key_ret;
+ int finger_index;
+ int i;
+ int j;
+ int flag = 0;
+
+ /* Check if you already have a predecessor. Then remove it and add the new
+ entry. */
+ finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create
(finger_peermap);
+ for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size
(finger_peermap); finger_index++)
+ {
+ if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter,
&key_ret,
+ (const void
**)&finger))
+ {
+ if (1 == finger->predecessor)
+ {
+ flag = 1;
+ break;
+ }
+ }
+ }
+ GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
+ /* check if you come out of the loop or because of the conditoin*/
+ if (flag == 0)
+ {
+ goto add_new_predecessor;
+ }
+ else
+ {
+ if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains(finger_peermap,
&(finger->finger_identity)))
+ {
+ /* compare peer ids of new finger and old finger if they are same don't
remove and exit
+ if different then remove and exit. */
+ if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&(finger->finger_identity),
predecessor))
+ {
+ //goto do_nothing;
+ exit(0);
+ }
+ else
+ {
+ if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_remove(finger_peermap,
&(finger->finger_identity), finger))
+ {
+ goto add_new_predecessor;
+ }
+ else
+ //goto do_nothing;
+ exit(0);
+ }
+ }
+ }
+
+ add_new_predecessor:
+ i = trail_length - 1;
+ j = 0;
+ trail_peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
+ trail_length);
+ while (i > 0)
+ {
+ memcpy( &trail_peer_list[j], &peer_list[i], sizeof (struct
GNUNET_PeerIdentity));
+ i--;
+ j++;
+ }
+ memcpy (&trail_peer_list[j], &peer_list[i], sizeof(struct
GNUNET_PeerIdentity));
+
+ new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
+ memcpy (&(new_finger_entry->finger_identity), predecessor, sizeof (struct
GNUNET_PeerIdentity));
+ new_finger_entry->finger_map_index = 1;
+ new_finger_entry->predecessor = 1;
+ new_finger_entry->successor = 0;
+ new_finger_entry->trail_length = trail_length;
+
+ i = 0;
+ while (i < trail_length)
+ {
+ struct TrailPeerList *element;
+ element = GNUNET_malloc (sizeof (struct TrailPeerList));
+ element->next = NULL;
+ element->prev = NULL;
+
+ memcpy (&(element->peer), &trail_peer_list[i], sizeof(struct
GNUNET_PeerIdentity));
+ GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head,
new_finger_entry->tail, element);
+ i++;
+ }
+}
+
+
+/**
* Compare two peer identities.
* @param p1 Peer identity
* @param p2 Peer identity
* @return 1 if p1 > p2, -1 if p1 < p2 and 0 if p1 == p2.
*/
-#if 0
-static int
+ static int
compare_peer_id (const void *p1, const void *p2)
{
- return memcmp (p1, p2, sizeof (uint64_t));;
+ struct Sorting_List *p11;
+ struct Sorting_List *p22;
+ int ret;
+ p11 = GNUNET_malloc (sizeof (struct Sorting_List));
+ p22 = GNUNET_malloc (sizeof (struct Sorting_List));
+ p11 = (struct Sorting_List *)p1;
+ p22 = (struct Sorting_List *)p2;
+ ret = ( (p11->peer_id) > (p22->peer_id) ) ? 1 :
+ ( (p11->peer_id) == (p22->peer_id) ) ? 0 : -1;
+ return ret;
}
-#endif
+
/**
* Returns the previous element of value in all_known_peers.
* @param all_known_peers list of all the peers
* @param value value we have to search in the all_known_peers.
* @return
*/
-#if 0
-static struct GNUNET_PeerIdentity *
-binary_search(struct GNUNET_PeerIdentity *all_known_peers, uint64_t *value,
+static struct Sorting_List *
+find_closest_successor(struct Sorting_List *all_known_peers, uint64_t value,
unsigned int size)
{
int first;
int last;
int middle;
- struct GNUNET_PeerIdentity *successor;
- successor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
first = 0;
last = size - 1;
@@ -1587,19 +1802,19 @@
while(first <= last)
{
- if(compare_peer_id(&all_known_peers[middle], &value) > 0)
+ if(all_known_peers[middle].peer_id < value)
{
- first = middle + 1;
+ first = middle + 1;
}
- else if(0 == compare_peer_id(&all_known_peers[middle], &value))
+ else if(all_known_peers[middle].peer_id == value)
{
- if(middle == 0)
+ if(middle == (size -1))
{
- memcpy (successor, &(all_known_peers[size - 1]), sizeof (struct
GNUNET_PeerIdentity));
+ return &all_known_peers[0];
}
else
{
- memcpy (successor, &(all_known_peers[middle-1]), sizeof (struct
GNUNET_PeerIdentity));
+ return &all_known_peers[middle+1];
}
}
else
@@ -1609,11 +1824,10 @@
middle = (first + last)/2;
}
-
- return successor;
+ return NULL;
}
-#endif
+
/**
* Find closest successor for the value.
* @param value Value for which we are looking for successor
@@ -1623,10 +1837,9 @@
* @return Peer identity of next destination i.e. successor of value.
*/
static struct GNUNET_PeerIdentity *
-find_successor(uint64_t *value, struct GNUNET_PeerIdentity
*current_destination,
+find_successor(uint64_t value, struct GNUNET_PeerIdentity *current_destination,
enum current_destination_type *type)
{
-#if 0
struct GNUNET_CONTAINER_MultiPeerMapIterator *friend_iter;
struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
struct GNUNET_PeerIdentity key_ret;
@@ -1634,25 +1847,33 @@
struct FingerInfo *finger;
unsigned int finger_index;
unsigned int friend_index;
- struct GNUNET_PeerIdentity *all_known_peers;
- struct GNUNET_PeerIdentity *successor;
+ struct Sorting_List *successor;
unsigned int size;
- unsigned int j;
+ int j;
/* 2 is added in size for my_identity and value which will part of
all_known_peers. */
size = GNUNET_CONTAINER_multipeermap_size (friend_peermap)+
GNUNET_CONTAINER_multipeermap_size (finger_peermap)+
2;
- all_known_peers = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * size);
+ struct Sorting_List all_known_peers[size];
+ int k;
+ for (k = 0; k < size; k++)
+ all_known_peers[k].peer_id = 0;
+
/* Copy your identity at 0th index in all_known_peers. */
j = 0;
- memcpy (&all_known_peers[j], &(my_identity), sizeof (struct
GNUNET_PeerIdentity));
+ memcpy (&(all_known_peers[j].peer_id), &my_identity, sizeof (uint64_t));
+ all_known_peers[j].type = MY_ID;
+ all_known_peers[j].data = 0;
+ j++;
- /* Copy the value that you are searching at index 1 in all_known_peers. */
+ /* Copy value */
+ all_known_peers[j].peer_id = value;
+ all_known_peers[j].type = VALUE;
+ all_known_peers[j].data = 0;
j++;
- memcpy (&all_known_peers[j], value, sizeof(uint64_t));
/* Iterate over friend peer map and copy all the elements into array. */
friend_iter = GNUNET_CONTAINER_multipeermap_iterator_create
(friend_peermap);
@@ -1660,7 +1881,9 @@
{
if(GNUNET_YES ==
GNUNET_CONTAINER_multipeermap_iterator_next(friend_iter,&key_ret,(const void
**)&friend))
{
- memcpy (&all_known_peers[j], &(friend->id), sizeof (struct
GNUNET_PeerIdentity));
+ memcpy (&(all_known_peers[j].peer_id), &(friend->id), sizeof (uint64_t));
+ all_known_peers[j].type = FRIEND;
+ all_known_peers[j].data = friend;
j++;
}
}
@@ -1669,59 +1892,55 @@
finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create
(finger_peermap);
for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size
(finger_peermap); finger_index++)
{
- /* FIXME: I don't think we are actually iterating.
- Read about how to iterate over the multi peer map. */
if(GNUNET_YES ==
GNUNET_CONTAINER_multipeermap_iterator_next(finger_iter,&key_ret,(const void
**)&finger))
{
- memcpy (&all_known_peers[j], &(finger->finger_identity), sizeof (struct
GNUNET_PeerIdentity));
+ memcpy (&(all_known_peers[j].peer_id), &(finger->finger_identity),
sizeof (uint64_t));
+ all_known_peers[j].type = FINGER;
+ all_known_peers[j].data = finger;
j++;
}
}
GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
GNUNET_CONTAINER_multipeermap_iterator_destroy (friend_iter);
-
- /* FIMXE : Should we not sort it for 64 bits. */
- qsort (all_known_peers, size, sizeof (uint64_t), &compare_peer_id);
+ qsort (&all_known_peers, size, sizeof (struct Sorting_List),
&compare_peer_id);
+
/* search value in all_known_peers array. */
- successor = binary_search (all_known_peers, value, size);
+ successor = find_closest_successor (all_known_peers, value, size);
- /* compare successor with my_identity, finger and friend */
- if(0 == GNUNET_CRYPTO_cmp_peer_identity(&(my_identity), successor))
+ if (successor->type == MY_ID)
{
- FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
*type = MY_ID;
return NULL;
}
- else if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains
(friend_peermap,
- successor))
+ else if (successor->type == FRIEND)
{
- FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
*type = FRIEND;
- memcpy (current_destination, successor, sizeof (struct
GNUNET_PeerIdentity));
- return successor;
+ struct FriendInfo *target_friend;
+ target_friend = (struct FriendInfo *)successor->data;
+ memcpy (current_destination, &(target_friend->id), sizeof (struct
GNUNET_PeerIdentity));
+ return current_destination;
}
- else if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains
(finger_peermap,
- successor))
+ else if (successor->type == FINGER)
{
- FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
*type = FINGER;
- memcpy (current_destination, successor, sizeof (struct
GNUNET_PeerIdentity));
- /* get the corresponding finger for succcesor and read the first element
from
- the trail list and return that element. */
- struct FingerInfo *successor_finger;
struct GNUNET_PeerIdentity *next_hop;
+ struct FingerInfo *finger;
+ struct TrailPeerList *iterator;
+ iterator = GNUNET_malloc (sizeof (struct TrailPeerList));
+ finger = successor->data;
+ iterator = finger->head->next;
next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
- successor_finger = GNUNET_CONTAINER_multipeermap_get (finger_peermap,
successor);
- //memcpy (next_hop, &(successor_finger->trail_peer_list[0]), sizeof
(struct GNUNET_PeerIdentity));
+ memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity));
+ memcpy (current_destination, &(finger->finger_identity), sizeof (struct
GNUNET_PeerIdentity));
return next_hop;
}
- FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__);
- return NULL;
-#endif
- *type = MY_ID;
- return &my_identity;
+ else
+ {
+ type = NULL;
+ return NULL;
+ }
}
@@ -1750,7 +1969,10 @@
struct GNUNET_PeerIdentity *next_peer;
unsigned int successor_flag;
unsigned int predecessor_flag;
-
+ uint64_t value;
+ struct GNUNET_PeerIdentity *current_destination;
+ current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
+
/* parse and validate message. */
msize = ntohs (message->size);
if (msize < sizeof (struct PeerTrailSetupMessage))
@@ -1766,8 +1988,8 @@
finger_map_index = ntohl (trail_setup->finger_map_index);
successor_flag = ntohl (trail_setup->successor_flag);
predecessor_flag = ntohl (trail_setup->predecessor_flag);
-
trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_setup[1];
+ value = trail_setup->destination_finger;
if ((msize <
sizeof (struct PeerTrailSetupMessage) +
@@ -1778,7 +2000,7 @@
GNUNET_break_op (0);
return GNUNET_YES;
}
-
+
GNUNET_STATISTICS_update (GDS_stats,
gettext_noop ("# TRAIL SETUP requests received"),
1,
GNUNET_NO);
@@ -1791,8 +2013,8 @@
if (0 == (GNUNET_CRYPTO_cmp_peer_identity
(&(trail_setup->current_destination),
&my_identity)))
{
- next_hop = find_successor (&(trail_setup->destination_finger),
- &(trail_setup->current_destination),
+ next_hop = find_successor (value,
+ current_destination,
&(peer_type));
}
else
@@ -1828,8 +2050,8 @@
else
{
/* I am the current_destination finger */
- next_hop = find_successor (&(trail_setup->destination_finger),
- &(trail_setup->current_destination),
&(peer_type));
+ next_hop = find_successor (value,
+ current_destination, &(peer_type));
}
}
@@ -1851,7 +2073,8 @@
if(current_trail_index != 0)
current_trail_index = current_trail_index - 1;
- GDS_NEIGHBOURS_handle_trail_setup_result (&(trail_setup->source_peer),
+ update_predecessor (&(trail_setup->source_peer), trail_peer_list,
trail_length );
+ GDS_NEIGHBOURS_send_trail_setup_result (&(trail_setup->source_peer),
&(my_identity),
target_friend, trail_length,
trail_peer_list,
current_trail_index,
@@ -1874,12 +2097,12 @@
if(peer_type == FINGER)
{
GDS_ROUTING_add (&(trail_setup->source_peer),
- &(trail_setup->current_destination),
+ &(trail_setup->current_destination),
next_hop);
}
- GDS_NEIGHBOURS_handle_trail_setup (&(trail_setup->source_peer),
- &(trail_setup->destination_finger),
+ GDS_NEIGHBOURS_send_trail_setup (&(trail_setup->source_peer),
+ trail_setup->destination_finger,
target_friend,
trail_setup->trail_length,
peer_list,trail_setup->successor_flag,
@@ -1891,76 +2114,6 @@
/**
- * FIXME: For redundant routing, we may start looking for different
- * paths to reach to same finger. So, in send_find_finger, we are starting
- * the search for trail to a finger, even if we already have found trail to
- * reach to it. There are several reasons for doing so
- * 1. We may reach to a closer successor than we have at the moment. So, we
- * should keep looking for the successor.
- * 2. We may reach to the same successor but through a shorter path.
- * 3. As I don't know how keys are distributed and how put/get will react
- * because of this, I have to think further before implementing it.
- * Add an entry in finger table.
- * @param finger Finger to be added to finger table
- * @param peer_list peers this request has traversed so far
- * @param trail_length Numbers of peers in the trail.
- */
-static
-void finger_table_add (struct GNUNET_PeerIdentity *finger,
- struct GNUNET_PeerIdentity *peer_list,
- unsigned int trail_length,
- unsigned int successor_flag,
- unsigned int predecessor_flag,
- unsigned int finger_map_index)
-{
- struct FingerInfo *new_finger_entry;
- unsigned int i = 0;
- /** SUPU: when we add an entry then we should look if
- * we already have an entry for that index. If yes, then
- * 1) if both the finger identity are same, and same first friend, then choose
- * the one with shorter trail length.
- * 2) if the finger identity is different, then keep the one which is
closest.*/
-
- new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
- memcpy (&(new_finger_entry->finger_identity), finger, sizeof (struct
GNUNET_PeerIdentity));
-
-
- /* Insert elements of peer_list into TrailPeerList. */
- i = 0;
- while (i < trail_length)
- {
- struct TrailPeerList *element;
- element = GNUNET_malloc (sizeof (struct TrailPeerList));
- element->next = NULL;
- element->prev = NULL;
-
- memcpy (&(element->peer), &peer_list[i], sizeof(struct
GNUNET_PeerIdentity));
- GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head,
new_finger_entry->tail, element);
- i++;
- }
-
-
- new_finger_entry->successor = successor_flag;
- new_finger_entry->predecessor = predecessor_flag;
- new_finger_entry->finger_map_index = finger_map_index;
- new_finger_entry->trail_length = trail_length;
-
-
- GNUNET_assert (GNUNET_OK ==
- GNUNET_CONTAINER_multipeermap_put (finger_peermap,
-
&(new_finger_entry->finger_identity),
- new_finger_entry,
-
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
-
- /*FIXME: Is it really a good time to call verify successor message. */
- if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap))
- {
- verify_successor = GNUNET_SCHEDULER_add_now
(&send_verify_successor_message, NULL);
- }
-}
-
-
-/**
* Core handle for p2p trail construction result messages.
* @param cls closure
* @param message message
@@ -2054,7 +2207,7 @@
target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
next_peer);
GNUNET_free (next_peer);
- GDS_NEIGHBOURS_handle_trail_setup_result
(&(trail_result->destination_peer),
+ GDS_NEIGHBOURS_send_trail_setup_result
(&(trail_result->destination_peer),
&(trail_result->finger),
target_friend, trail_length,
trail_peer_list,current_trail_index,
@@ -2111,18 +2264,13 @@
return GNUNET_YES;
}
- current_trail_index = ntohl (vsm->current_trail_index);
-
+ current_trail_index = ntohl (vsm->current_trail_index);
trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1];
next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
-
if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),
&my_identity)))
{
- /* I am the successor, check who is my predecessor. If my predecessor is
not
- same as source peer then update the trail and send back to calling
function.
- */
struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
struct GNUNET_PeerIdentity key_ret;
unsigned int finger_index;
@@ -2140,11 +2288,11 @@
break;
}
}
-
GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
+
destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
memcpy (destination_peer, &(vsm->source_peer), sizeof (struct
GNUNET_PeerIdentity));
- current_trail_index = trail_length - 2; /*SUPU: I am the last element in
the trail.*/
+ current_trail_index = trail_length - 2;
memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct
GNUNET_PeerIdentity));
target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
next_hop);
GNUNET_free (next_hop);
@@ -2152,33 +2300,25 @@
if (current_trail_index != 0)
current_trail_index = current_trail_index - 1;
- /* FIXME: Here we should check if our predecessor is source peer or not.
- If not then, we can send an updated trail that goes through us. Instead of
- looking for a new trail to reach to the new successor, source peer
- can just use this trail. It may not be an optimal route. */
+
if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->source_peer),
&(my_predecessor->finger_identity))))
{
- /*If we have a new predecessor, then create a new trail to reach from
- vsm source peer to this new successor of source peer. */
struct GNUNET_PeerIdentity *new_successor_trail;
- unsigned int my_predecessor_trail_length;
unsigned int new_trail_length;
unsigned int i;
-
- /* SUPU: The trail that we store corresponding to each finger contains
- * me as the first element. So, we are included twice when we join the
- * two trails. */
- my_predecessor_trail_length = (my_predecessor->trail_length) - 1;
/*SUPU: Removing myself from the trail */
- new_trail_length = trail_length + my_predecessor_trail_length;
+ new_trail_length = trail_length + my_predecessor->trail_length - 1;
new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)
* new_trail_length);
+
+ /* Copy the trail from source peer to me. */
memcpy (new_successor_trail, trail_peer_list,
- trail_length * sizeof (struct GNUNET_PeerIdentity));
+ (trail_length) * sizeof (struct GNUNET_PeerIdentity));
+ /* Copy the trail from me to my predecessor excluding me. */
struct TrailPeerList *iterator;
- iterator = my_predecessor->head->next; /* FIXME: Check if you are
removing yourself */
+ iterator = my_predecessor->head->next;
i = trail_length;
while (i < new_trail_length)
{
@@ -2186,9 +2326,8 @@
iterator = iterator->next;
i++;
}
-
-
- GDS_NEIGHBOURS_handle_verify_successor_result (destination_peer,
+
+ GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
&(my_identity),
&(my_predecessor->finger_identity),
target_friend,
@@ -2196,8 +2335,8 @@
new_trail_length,
current_trail_index);
}
-
- GDS_NEIGHBOURS_handle_verify_successor_result (destination_peer,
+
+ GDS_NEIGHBOURS_send_verify_successor_result (destination_peer,
&(my_identity),
&(my_predecessor->finger_identity),
target_friend,
@@ -2214,7 +2353,7 @@
current_trail_index = current_trail_index + 1;
- GDS_NEIGHBOURS_handle_verify_successor(&(vsm->source_peer),
+ GDS_NEIGHBOURS_send_verify_successor(&(vsm->source_peer),
&(vsm->successor),
target_friend,
trail_peer_list,
@@ -2239,7 +2378,58 @@
{
struct FingerInfo *new_finger_entry;
unsigned int i;
+ struct FingerInfo *finger;
+ struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter;
+ struct GNUNET_PeerIdentity key_ret;
+ int finger_index;
+ int flag = 0;
+ /* Check if you already have a predecessor. Then remove it and add the new
+ entry. */
+ finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create
(finger_peermap);
+ for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size
(finger_peermap); finger_index++)
+ {
+ if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (finger_iter,
&key_ret,
+ (const void
**)&finger))
+ {
+ if (1 == finger->successor)
+ {
+ flag = 1;
+ break;
+ }
+ }
+ }
+ GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter);
+ /* check if you come out of the loop or because of the conditoin*/
+ if (flag == 0)
+ {
+ goto add_new_successor;
+ }
+ else
+ {
+ if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_contains(finger_peermap,
&(finger->finger_identity)))
+ {
+ /* compare peer ids of new finger and old finger if they are same don't
remove and exit
+ if different then remove and exit. */
+ if ( 0 == GNUNET_CRYPTO_cmp_peer_identity (&(finger->finger_identity),
successor_identity))
+ {
+ //goto do_nothing;
+ exit(0);
+ }
+ else
+ {
+ if (GNUNET_YES == GNUNET_CONTAINER_multipeermap_remove(finger_peermap,
&(finger->finger_identity), finger))
+ {
+ goto add_new_successor;
+ }
+ else
+ //goto do_nothing;
+ exit(0);
+ }
+ }
+ }
+
+ add_new_successor:
new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
new_finger_entry->predecessor = 0;
new_finger_entry->successor = 1;
@@ -2263,57 +2453,6 @@
/**
- * FIXME: Also copy the trail list in reverse direction that is the path to
- * reach to your predecessor.
- * Replace your predecessor with new predecessor.
- * @param predecessor My new predecessor
- * @param peer_list Trail list to reach to my new predecessor
- * @param trail_length Number of peers in the trail.
- */
-static void
-update_predecessor (struct GNUNET_PeerIdentity *predecessor,
- struct GNUNET_PeerIdentity *peer_list,
- unsigned int trail_length)
-{
- struct GNUNET_PeerIdentity *trail_peer_list;
- struct FingerInfo *new_finger_entry;
- unsigned int i;
- unsigned int j;
-
- i = trail_length - 1;
- j = 0;
- trail_peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) *
- trail_length);
- while (i > 0)
- {
- memcpy( &trail_peer_list[j], &peer_list[i], sizeof (struct
GNUNET_PeerIdentity));
- i--;
- j++;
- }
- memcpy (&trail_peer_list[j], &peer_list[i], sizeof(struct
GNUNET_PeerIdentity));
-
- new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo));
- memcpy (&(new_finger_entry->finger_identity), predecessor, sizeof (struct
GNUNET_PeerIdentity));
- new_finger_entry->finger_map_index = 1;
- new_finger_entry->predecessor = 1;
- new_finger_entry->successor = 0;
-
- i = 0;
- while (i < trail_length)
- {
- struct TrailPeerList *element;
- element = GNUNET_malloc (sizeof (struct TrailPeerList));
- element->next = NULL;
- element->prev = NULL;
-
- memcpy (&(element->peer), &trail_peer_list[i], sizeof(struct
GNUNET_PeerIdentity));
- GNUNET_CONTAINER_DLL_insert_tail(new_finger_entry->head,
new_finger_entry->tail, element);
- i++;
- }
-}
-
-
-/**
* Core handle for p2p notify new successor messages.
* @param cls closure
* @param message message
@@ -2337,7 +2476,6 @@
return GNUNET_YES;
}
- /* Again in the function you have the whole trail to reach to the
destination. */
nsm = (struct PeerNotifyNewSuccessorMessage *) message;
trail_length = ntohl (nsm->trail_length);
@@ -2355,7 +2493,7 @@
trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1];
if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer),
- &my_identity)))
+ &my_identity)))
{
update_predecessor (&(nsm->source_peer),
trail_peer_list,
@@ -2368,12 +2506,14 @@
target_friend = GNUNET_malloc (sizeof (struct FriendInfo));
struct GNUNET_PeerIdentity *next_hop;
next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
- memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct
GNUNET_PeerIdentity));
+ memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct
GNUNET_PeerIdentity));
+
+
target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
next_hop);
GNUNET_free (next_hop);
current_trail_index = current_trail_index + 1;
- GDS_NEIGHBOURS_notify_new_successor (&(nsm->source_peer),
+ GDS_NEIGHBOURS_send_notify_new_successor (&(nsm->source_peer),
&(nsm->destination_peer),
target_friend, trail_peer_list,
trail_length,
current_trail_index);
@@ -2407,7 +2547,7 @@
GNUNET_break_op (0);
return GNUNET_YES;
}
-
+
/* Again in the function you have the whole trail to reach to the
destination. */
vsrm = (struct PeerVerifySuccessorResultMessage *) message;
current_trail_index = ntohl (vsrm->current_index);
@@ -2434,29 +2574,26 @@
update_successor (&(vsrm->my_predecessor), trail_peer_list,
trail_length);
next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
- /* FIXME: Assuming that I am also in trail list and I am the first peer.
*/
memcpy (next_hop, &trail_peer_list[1], sizeof (struct
GNUNET_PeerIdentity));
target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
next_hop);
+ current_trail_index = 2;
GNUNET_free (next_hop);
- GDS_NEIGHBOURS_notify_new_successor (&my_identity,
&(vsrm->my_predecessor),
+ GDS_NEIGHBOURS_send_notify_new_successor (&my_identity,
&(vsrm->my_predecessor),
target_friend, trail_peer_list,
trail_length, current_trail_index);
}
}
else
{
- /* Read the peer trail list and find out the next destination to forward
this
- packet to. */
next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity));
- /* FIXME: Assuming that I am also in trail list and I am the first peer. */
memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct
GNUNET_PeerIdentity));
target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap,
next_hop);
GNUNET_free (next_hop);
current_trail_index = current_trail_index - 1;
- GDS_NEIGHBOURS_handle_verify_successor_result (&(vsrm->destination_peer),
+ GDS_NEIGHBOURS_send_verify_successor_result (&(vsrm->destination_peer),
&(vsrm->source_successor),
&(vsrm->my_predecessor),
target_friend,
| [Prev in Thread] |
Current Thread |
[Next in Thread] |
- [GNUnet-SVN] r32706 - gnunet/src/dht,
gnunet <=