#include "gnunet-service-wdht_clients.h"
#include "gnunet-service-wdht_datacache.h"
#include "gnunet-service-wdht_neighbours.h"
+#include "gnunet-service-wdht_nse.h"
#include <fenv.h>
#include <stdlib.h>
#include <string.h>
GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, __VA_ARGS__)
/**
- * FIXME
+ * Trail timeout. After what time do trails always die?
*/
-#define FOO_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 2)
+#define TRAIL_TIMEOUT GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 42)
+
+/**
+ * Random walk delay. How often do we walk the overlay?
+ */
+#define RANDOM_WALK_DELAY GNUNET_TIME_relative_multiply (GNUNET_TIME_UNIT_MINUTES, 42)
/**
* The number of layered ID to use.
/******************* The db structure and related functions *******************/
/**
- * Entry in friend_peermap.
+ * Entry in #friends_peermap.
*/
struct FriendInfo;
*/
struct GNUNET_CONTAINER_HeapNode *hn;
+ /**
+ * If this peer started the to create a Finger (and thus @e pred is
+ * NULL), this is the Finger we are trying to intialize.
+ */
+ struct Finger **finger;
+
};
/**
- * Entry in friend_peermap.
+ * Entry in #friends_peermap.
*/
struct FriendInfo
{
*/
struct GNUNET_PeerIdentity id;
+ /**
+ *
+ */
struct Trail *pred_head;
+ /**
+ *
+ */
struct Trail *pred_tail;
+ /**
+ *
+ */
struct Trail *succ_head;
+ /**
+ *
+ */
struct Trail *succ_tail;
/**
};
-struct db_cell
+/**
+ *
+ */
+struct FingerTable;
+
+
+/**
+ *
+ */
+struct Finger
{
/**
- * The identity of the peer.
+ *
*/
- struct GNUNET_PeerIdentity peer_id;
+ struct Trail *trail;
/**
- * The trail to use to reach the peer.
+ *
*/
- struct Trail *trail;
+ struct FingerTable *ft;
+
+ /**
+ *
+ */
+ struct GNUNET_HashCode destination;
/**
* #GNUNET_YES if a response has been received. Otherwise #GNUNET_NO.
};
+struct FingerTable
+{
+ /**
+ * Array of our fingers, unsorted.
+ */
+ struct Finger **fingers;
+
+ /**
+ * Array of sorted fingers (sorted by destination, valid fingers first).
+ */
+ struct Finger **sorted_fingers;
+
+ /**
+ * Size of the finger array.
+ */
+ unsigned int finger_array_size;
+
+ /**
+ * Number of valid entries in @e sorted_fingers (contiguous from offset 0)
+ */
+ unsigned int number_valid_fingers;
+
+ /**
+ * Which offset in @e fingers will we redo next.
+ */
+ unsigned int walk_offset;
+
+ /**
+ * Is the finger array sorted?
+ */
+ int is_sorted;
+
+};
+
+
/*********************** end of the db structure part ***********************/
/**
* Setup a finger using the underlay topology ("social network").
*/
-struct FingerSetupMessage
+struct RandomWalkMessage
{
/**
- * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP
+ * Type: #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK
*/
struct GNUNET_MessageHeader header;
/**
* Unique (random) identifier this peer will use to
- * identify the finger (in future messages).
+ * identify the trail (in future messages).
*/
- struct GNUNET_HashCode finger_id;
+ struct GNUNET_HashCode trail_id;
};
-
/**
- * Response to a `struct FingerSetupMessage`.
+ * Response to a `struct RandomWalkMessage`.
*/
-struct FingerSetupResponseMessage
+struct RandomWalkResponseMessage
{
/**
- * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP_RESPONSE
+ * Type: #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE
*/
struct GNUNET_MessageHeader header;
uint32_t reserved GNUNET_PACKED;
/**
- * Unique (random) identifier this peer will use to
- * identify the finger (in future messages).
+ * Unique (random) identifier from the
+ * `struct RandomWalkMessage`.
*/
- struct GNUNET_HashCode finger_id;
+ struct GNUNET_HashCode trail_id;
/**
* Random location in the respective layer where the
};
-
/**
- * Response to an event that causes a finger to die.
+ * Response to an event that causes a trail to die.
*/
-struct FingerDestroyMessage
+struct TrailDestroyMessage
{
/**
- * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_DESTROY
+ * Type: #GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY
*/
struct GNUNET_MessageHeader header;
* Unique (random) identifier this peer will use to
* identify the finger (in future messages).
*/
- struct GNUNET_HashCode finger_id;
+ struct GNUNET_HashCode trail_id;
};
/**
- * Send a message along a finger.
+ * Send a message along a trail.
*/
-struct FingerRouteMessage
+struct FindSuccessorMessage
{
/**
- * Type: #GNUNET_MESSAGE_TYPE_WDHT_FINGER_ROUTE
+ * Type: #GNUNET_MESSAGE_TYPE_WDHT_FIND_SUCCESSOR
*/
struct GNUNET_MessageHeader header;
* Unique (random) identifier this peer will use to
* identify the finger (in future messages).
*/
- struct GNUNET_HashCode finger_id;
+ struct GNUNET_HashCode trail_id;
+
+ /**
+ * Key for which we would like close values returned.
+ * identify the finger (in future messages).
+ */
+ struct GNUNET_HashCode key;
+
+};
+
+
+/**
+ * Send a message along a trail.
+ */
+struct TrailRouteMessage
+{
+ /**
+ * Type: #GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE
+ */
+ struct GNUNET_MessageHeader header;
+
+ /**
+ * #GNUNET_YES if the path should be recorded, #GNUNET_NO if not; in NBO.
+ */
+ uint16_t record_path GNUNET_PACKED;
+
+ /**
+ * Length of the recorded trail, 0 if @e record_path is #GNUNET_NO; in NBO.
+ */
+ uint16_t path_length GNUNET_PACKED;
+
+ /**
+ * Unique (random) identifier this peer will use to
+ * identify the finger (in future messages).
+ */
+ struct GNUNET_HashCode trail_id;
+
+ /**
+ * Path the message has taken so far (excluding sender).
+ */
+ /* struct GNUNET_PeerIdentity path[path_length]; */
- /* followed by payload to send along the finger */
+ /* followed by payload (another `struct GNUNET_MessageHeader`) to
+ send along the trail */
};
GNUNET_NETWORK_STRUCT_END
-/**
- * The number of cells stored in the db structure.
- */
-static unsigned int number_cell;
-
-/**
- * If sorted_db array is sorted #GNUNET_YES. Otherwise #GNUNET_NO.
- */
-static int is_sorted;
/**
* Contains all the layered IDs of this peer.
*/
struct GNUNET_PeerIdentity layered_id[NUMBER_LAYERED_ID];
-/**
- * Unsorted database, here we manage the entries.
- */
-static struct db_cell *unsorted_db[NUMBER_RANDOM_WALK * NUMBER_LAYERED_ID];
-
-/**
- * Sorted database by peer identity, needs to be re-sorted if
- * #is_sorted is #GNUNET_NO.
- */
-static struct db_cell **sorted_db[NUMBER_RANDOM_WALK * NUMBER_LAYERED_ID];
-
/**
* Task to timeout trails that have expired.
*/
static struct GNUNET_PeerIdentity my_identity;
/**
- * Peer map of all the fingers of a peer
+ * Peer map of all the friends of a peer
*/
-static struct GNUNET_CONTAINER_MultiPeerMap *fingers_peermap;
+static struct GNUNET_CONTAINER_MultiPeerMap *friends_peermap;
/**
- * Peer map of all the successors of a peer
+ * Fingers per layer.
*/
-static struct GNUNET_CONTAINER_MultiPeerMap *successors_peermap;
+static struct FingerTable fingers[NUMBER_LAYERED_ID];
/**
* Tail map, mapping tail identifiers to `struct Trail`s
static struct GNUNET_CORE_Handle *core_api;
-/**
- * Initialize the db structure with default values.
- */
-static void
-init_db_structure ()
-{
- unsigned int i;
-
- for (i = 0; i < NUMBER_RANDOM_WALK; i++)
- {
- unsorted_db[i] = NULL;
- sorted_db[i] = &unsorted_db[i];
- }
-}
-
-
-/**
- * Destroy the db_structure. Basically, free every db_cell.
- */
-static void
-destroy_db_structure ()
-{
- unsigned int i;
-
- for (i = 0; i < NUMBER_RANDOM_WALK; i++)
- {
- // what about 'unsorted_db[i]->trail?
- GNUNET_free_non_null (unsorted_db[i]);
- }
-}
-
-
-/**
- * Add a new db_cell in the db structure.
- */
-static void
-add_new_cell (struct db_cell *bd_cell)
-{
- unsorted_db[number_cell] = bd_cell;
- is_sorted = GNUNET_NO;
-}
-
-
/**
* Handle the put request from the client.
*
enum GNUNET_DHT_RouteOption options,
uint32_t desired_replication_level,
struct GNUNET_TIME_Absolute expiration_time,
- const void *data, size_t data_size)
+ const void *data,
+ size_t data_size)
{
+ GDS_DATACACHE_handle_put (expiration_time,
+ key,
+ 0, NULL,
+ 0, NULL,
+ block_type,
+ data_size,
+ data);
+ GDS_CLIENTS_process_put (options,
+ block_type,
+ 0, 0,
+ 0, NULL,
+ expiration_time,
+ key,
+ data,
+ data_size);
}
enum GNUNET_DHT_RouteOption options,
uint32_t desired_replication_level)
{
+ // find closest finger(s) on all layers
+ // use TrailRoute with PeerGetMessage embedded to contact peer
+}
+
+
+/**
+ * Delete a trail, it died (timeout, link failure, etc.).
+ *
+ * @param trail trail to delete from all data structures
+ * @param inform_pred should we notify the predecessor?
+ * @param inform_succ should we inform the successor?
+ */
+static void
+delete_trail (struct Trail *trail,
+ int inform_pred,
+ int inform_succ)
+{
+ struct FriendInfo *friend;
+ struct GNUNET_MQ_Envelope *env;
+ struct TrailDestroyMessage *tdm;
+ struct Finger *finger;
+
+ friend = trail->pred;
+ if (NULL != friend)
+ {
+ if (GNUNET_YES == inform_pred)
+ {
+ env = GNUNET_MQ_msg (tdm,
+ GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
+ tdm->trail_id = trail->pred_id;
+ GNUNET_MQ_send (friend->mq,
+ env);
+ }
+ GNUNET_CONTAINER_MDLL_remove (pred,
+ friend->pred_head,
+ friend->pred_tail,
+ trail);
+ }
+ friend = trail->succ;
+ if (NULL != friend)
+ {
+ if (GNUNET_YES == inform_succ)
+ {
+ env = GNUNET_MQ_msg (tdm,
+ GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY);
+ tdm->trail_id = trail->pred_id;
+ GNUNET_MQ_send (friend->mq,
+ env);
+ }
+ GNUNET_CONTAINER_MDLL_remove (succ,
+ friend->pred_head,
+ friend->pred_tail,
+ trail);
+ }
+ GNUNET_break (trail ==
+ GNUNET_CONTAINER_heap_remove_node (trail->hn));
+ finger = *trail->finger;
+ if (NULL != finger)
+ {
+ *trail->finger = NULL;
+ GNUNET_free (finger);
+ }
+ GNUNET_free (trail);
}
+/**
+ * Blah.
+ */
+static void
+forward_message_on_trail (struct FriendInfo *next_target,
+ const struct GNUNET_HashCode *trail_id,
+ int have_path,
+ const struct GNUNET_PeerIdentity *predecessor,
+ const struct GNUNET_PeerIdentity *path,
+ uint16_t path_length,
+ const struct GNUNET_MessageHeader *payload)
+{
+ struct GNUNET_MQ_Envelope *env;
+ struct TrailRouteMessage *trm;
+ struct GNUNET_PeerIdentity *new_path;
+ unsigned int plen;
+ uint16_t payload_len;
+
+ payload_len = ntohs (payload->size);
+ if (have_path)
+ {
+ plen = path_length + 1;
+ if (plen >= (GNUNET_SERVER_MAX_MESSAGE_SIZE
+ - payload_len
+ - sizeof (struct TrailRouteMessage))
+ / sizeof (struct GNUNET_PeerIdentity))
+ {
+ /* Should really not have paths this long... */
+ GNUNET_break_op (0);
+ plen = 0;
+ have_path = 0;
+ }
+ }
+ else
+ {
+ GNUNET_break_op (0 == path_length);
+ path_length = 0;
+ plen = 0;
+ }
+ env = GNUNET_MQ_msg_extra (trm,
+ payload_len +
+ plen * sizeof (struct GNUNET_PeerIdentity),
+ GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE);
+ trm->record_path = htons (have_path);
+ trm->path_length = htons (plen);
+ trm->trail_id = *trail_id;
+ new_path = (struct GNUNET_PeerIdentity *) &trm[1];
+ if (have_path)
+ {
+ memcpy (new_path,
+ path,
+ path_length * sizeof (struct GNUNET_PeerIdentity));
+ new_path[path_length] = *predecessor;
+ }
+ memcpy (&new_path[plen],
+ payload,
+ payload_len);
+ GNUNET_MQ_send (next_target->mq,
+ env);
+}
+
/**
* Send the get result to requesting client.
*
+ * @param trail_id trail identifying where to send the result to, NULL for us
* @param key Key of the requested data.
* @param type Block type
- * @param target_peer Next peer to forward the message to.
- * @param source_peer Peer which has the data for the key.
* @param put_path_length Number of peers in @a put_path
* @param put_path Path taken to put the data at its stored location.
- * @param get_path_length Number of peers in @a get_path
- * @param get_path Path taken to reach to the location of the key.
* @param expiration When will this result expire?
* @param data Payload to store
* @param data_size Size of the @a data
+ *
+ * FIXME: also pass options, so we know to record paths or not...
*/
void
-GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *key,
+GDS_NEIGHBOURS_send_get_result (const struct GNUNET_HashCode *trail_id,
+ const struct GNUNET_HashCode *key,
enum GNUNET_BLOCK_Type type,
- const struct GNUNET_PeerIdentity *target_peer,
- const struct GNUNET_PeerIdentity *source_peer,
unsigned int put_path_length,
const struct GNUNET_PeerIdentity *put_path,
- unsigned int get_path_length,
- const struct GNUNET_PeerIdentity *get_path,
struct GNUNET_TIME_Absolute expiration,
- const void *data, size_t data_size)
+ const void *data,
+ size_t data_size)
{
+ struct GNUNET_MessageHeader *payload;
+
+ payload = GNUNET_malloc (sizeof (struct GNUNET_MessageHeader) + data_size);
+ payload->size = data_size;
+ payload->type = GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT;
+
+ forward_message_on_trail (NULL /* FIXME: put something right */,
+ trail_id,
+ 0 /* FIXME: put something right */,
+ &my_identity,
+ put_path,
+ put_path_length,
+ payload);
}
const struct GNUNET_PeerIdentity *peer)
{
struct FriendInfo *remove_friend;
+ struct Trail *t;
/* If disconnected to own identity, then return. */
if (0 == memcmp (&my_identity,
return;
if (NULL == (remove_friend =
- GNUNET_CONTAINER_multipeermap_get (fingers_peermap,
+ GNUNET_CONTAINER_multipeermap_get (friends_peermap,
peer)))
{
GNUNET_break (0);
}
GNUNET_assert (GNUNET_YES ==
- GNUNET_CONTAINER_multipeermap_remove (fingers_peermap,
+ GNUNET_CONTAINER_multipeermap_remove (friends_peermap,
peer,
remove_friend));
- /* FIXME: do stuff */
+ while (NULL != (t = remove_friend->succ_head))
+ delete_trail (t,
+ GNUNET_YES,
+ GNUNET_NO);
+ while (NULL != (t = remove_friend->pred_head))
+ delete_trail (t,
+ GNUNET_NO,
+ GNUNET_YES);
GNUNET_MQ_destroy (remove_friend->mq);
GNUNET_free (remove_friend);
if (0 ==
- GNUNET_CONTAINER_multipeermap_size (fingers_peermap))
+ GNUNET_CONTAINER_multipeermap_size (friends_peermap))
{
GNUNET_SCHEDULER_cancel (random_walk_task);
random_walk_task = NULL;
}
+/**
+ * Pick random friend from friends for random walk.
+ */
+static struct FriendInfo *
+pick_random_friend ()
+{
+ GNUNET_CONTAINER_PeerMapIterator *it;
+ if (0 != GNUNET_CONTAINER_multipeermap_get_random (friends_peermap,
+ *it,
+ NULL) ){
+ static struct FriendInfo **friend;
+ struct GNUNET_PeerIdentity *key;
+
+ /* FIXME: i am not sure of this one */
+ key = NULL;
+
+ if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (it,
+ key,
+ (void *) friend))
+ {
+ return *friend;
+ }
+ }
+ return NULL;
+}
+
+
+/**
+ * One of our trails might have timed out, check and
+ * possibly initiate cleanup.
+ *
+ * @param cls NULL
+ * @param tc unused
+ */
+static void
+trail_timeout_callback (void *cls,
+ const struct GNUNET_SCHEDULER_TaskContext *tc)
+{
+ struct Trail *trail;
+ struct GNUNET_TIME_Relative left;
+
+ trail_timeout_task = NULL;
+ while (NULL != (trail = GNUNET_CONTAINER_heap_peek (trail_heap)))
+ {
+ left = GNUNET_TIME_absolute_get_remaining (trail->expiration_time);
+ if (0 != left.rel_value_us)
+ break;
+ delete_trail (trail,
+ GNUNET_YES,
+ GNUNET_YES);
+ }
+ if (NULL != trail)
+ trail_timeout_task = GNUNET_SCHEDULER_add_delayed (left,
+ &trail_timeout_callback,
+ NULL);
+}
+
+
/**
* Initiate a random walk.
*
do_random_walk (void *cls,
const struct GNUNET_SCHEDULER_TaskContext *tc)
{
+ static unsigned int walk_layer;
struct FriendInfo *friend;
struct GNUNET_MQ_Envelope *env;
- struct FingerSetupMessage *fsm;
- struct db_cell *friend_cell;
+ struct RandomWalkMessage *rwm;
+ struct FingerTable *ft;
+ struct Finger *finger;
struct Trail *trail;
- friend = NULL; // FIXME: pick at random...
-
- friend_cell = GNUNET_new (struct db_cell);
- friend_cell->peer_id = friend->id;
+ random_walk_task = NULL;
+ friend = pick_random_friend ();
trail = GNUNET_new (struct Trail);
-
/* We create the random walk so, no predecessor */
trail->succ = friend;
-
+ GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
+ &trail->succ_id);
+ if (GNUNET_OK !=
+ GNUNET_CONTAINER_multihashmap_put (trail_map,
+ &trail->succ_id,
+ trail,
+ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
+ {
+ GNUNET_break (0);
+ GNUNET_free (trail);
+ return;
+ }
GNUNET_CONTAINER_MDLL_insert (succ,
friend->succ_head,
friend->succ_tail,
trail);
- env = GNUNET_MQ_msg (fsm,
- GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP);
- fsm->hops_taken = htons (0);
- fsm->layer = htons (0); // FIXME: not always 0...
- GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
- &fsm->finger_id);
+ trail->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
+ trail->hn = GNUNET_CONTAINER_heap_insert (trail_heap,
+ trail,
+ trail->expiration_time.abs_value_us);
+ if (NULL == trail_timeout_task)
+ trail_timeout_task = GNUNET_SCHEDULER_add_delayed (TRAIL_TIMEOUT,
+ &trail_timeout_callback,
+ NULL);
+ env = GNUNET_MQ_msg (rwm,
+ GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
+ rwm->hops_taken = htonl (0);
+ rwm->trail_id = trail->succ_id;
GNUNET_MQ_send (friend->mq,
env);
+ /* clean up 'old' entry (implicitly via trail cleanup) */
+ ft = &fingers[walk_layer];
+
+ if ( (NULL != ft->fingers) &&
+ (NULL != (finger = ft->fingers[ft->walk_offset])) )
+ delete_trail (finger->trail,
+ GNUNET_NO,
+ GNUNET_YES);
+ if (ft->finger_array_size < 42)
+ {
+ // FIXME: must have finger array of the right size here,
+ // FIXME: growing / shrinking are tricky -- with pointers
+ // from Trails!!!
+ }
+
+ GNUNET_assert (NULL == ft->fingers[ft->walk_offset]);
+
+ finger = GNUNET_new (struct Finger);
+ finger->trail = trail;
+ trail->finger = &ft->fingers[ft->walk_offset];
+ finger->ft = ft;
+ ft->fingers[ft->walk_offset] = finger;
+ ft->is_sorted = GNUNET_NO;
+ ft->walk_offset = (ft->walk_offset + 1) % ft->finger_array_size;
+
+ walk_layer = (walk_layer + 1) % NUMBER_LAYERED_ID;
+ random_walk_task = GNUNET_SCHEDULER_add_delayed (RANDOM_WALK_DELAY,
+ &do_random_walk,
+ NULL);
}
/* If peer already exists in our friend_peermap, then exit. */
if (GNUNET_YES ==
- GNUNET_CONTAINER_multipeermap_contains (fingers_peermap,
+ GNUNET_CONTAINER_multipeermap_contains (friends_peermap,
peer_identity))
{
GNUNET_break (0);
friend->mq = GNUNET_CORE_mq_create (core_api,
peer_identity);
GNUNET_assert (GNUNET_OK ==
- GNUNET_CONTAINER_multipeermap_put (fingers_peermap,
+ GNUNET_CONTAINER_multipeermap_put (friends_peermap,
peer_identity,
friend,
GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY));
- /* do work? */
-
if (NULL == random_walk_task)
{
- random_walk_task = GNUNET_SCHEDULER_add_now (&do_random_walk,
- NULL);
+ /* random walk needs to be started -- we have a first connection */
+ random_walk_task = GNUNET_SCHEDULER_add_now (&do_random_walk,
+ NULL);
}
}
/**
- * Handle a `struct FingerSetupMessage` from a GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP
- * message.
+ * Handle a `struct RandomWalkMessage` from a
+ * #GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK message.
*
* @param cls closure (NULL)
* @param peer sender identity
* @return #GNUNET_OK on success, #GNUNET_SYSERR on error
*/
static int
-handle_dht_p2p_finger_setup (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- const struct GNUNET_MessageHeader *message)
+handle_dht_p2p_random_walk (void *cls,
+ const struct GNUNET_PeerIdentity *peer,
+ const struct GNUNET_MessageHeader *message)
{
- const struct FingerSetupMessage *fsm;
-
- fsm = (const struct FingerSetupMessage *) message;
-
- /*
- * Steps :
- * 1 check if the hops_taken is < to log(honest node)
- * 1.a.1 if true : increments the hops_taken
- * 1.a.2 send the same structure
- * 1.b if false : drop the message
- */
+ const struct RandomWalkMessage *m;
+ struct Trail *t;
+ struct FriendInfo *pred;
+ m = (const struct RandomWalkMessage *) message;
+ pred = GNUNET_CONTAINER_multipeermap_get (friends_peermap,
+ peer);
+ t = GNUNET_new (struct Trail);
+ t->pred_id = m->trail_id;
+ t->pred = pred;
+ if (GNUNET_OK !=
+ GNUNET_CONTAINER_multihashmap_put (trail_map,
+ &t->pred_id,
+ t,
+ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
+ {
+ GNUNET_break_op (0);
+ GNUNET_free (t);
+ return GNUNET_SYSERR;
+ }
+ GNUNET_CONTAINER_MDLL_insert (pred,
+ pred->pred_head,
+ pred->pred_tail,
+ t);
+ t->expiration_time = GNUNET_TIME_relative_to_absolute (TRAIL_TIMEOUT);
+ t->hn = GNUNET_CONTAINER_heap_insert (trail_heap,
+ t,
+ t->expiration_time.abs_value_us);
+ if (NULL == trail_timeout_task)
+ trail_timeout_task = GNUNET_SCHEDULER_add_delayed (TRAIL_TIMEOUT,
+ &trail_timeout_callback,
+ NULL);
+
+ if (ntohl (m->hops_taken) > GDS_NSE_get ())
+ {
+ /* We are the last hop, generate response */
+ struct GNUNET_MQ_Envelope *env;
+ struct RandomWalkResponseMessage *rwrm;
+ uint16_t layer;
+
+ env = GNUNET_MQ_msg (rwrm,
+ GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE);
+ rwrm->reserved = htonl (0);
+ rwrm->trail_id = m->trail_id;
+ layer = ntohs (m->layer);
+ if (0 == layer)
+ (void) GDS_DATACACHE_get_random_key (&rwrm->location);
+ else
+ {
+ struct FingerTable *ft;
+
+ if (layer > NUMBER_LAYERED_ID)
+ {
+ GNUNET_break_op (0);
+ // FIXME: clean up 't'...
+ return GNUNET_SYSERR;
+ }
+ ft = &fingers[layer-1];
+ if (0 == ft->number_valid_fingers)
+ {
+ GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
+ &rwrm->location);
+ }
+ else
+ {
+ struct Finger *f;
+
+ f = ft->fingers[GNUNET_CRYPTO_random_u32 (GNUNET_CRYPTO_QUALITY_NONCE,
+ ft->number_valid_fingers)];
+ rwrm->location = f->destination;
+ }
+ }
+ GNUNET_MQ_send (pred->mq,
+ env);
+ }
+ else
+ {
+ struct GNUNET_MQ_Envelope *env;
+ struct RandomWalkMessage *rwm;
+ struct FriendInfo *succ;
+
+ /* extend the trail by another random hop */
+ succ = pick_random_friend ();
+ GNUNET_CRYPTO_hash_create_random (GNUNET_CRYPTO_QUALITY_NONCE,
+ &t->succ_id);
+ t->succ = succ;
+ if (GNUNET_OK !=
+ GNUNET_CONTAINER_multihashmap_put (trail_map,
+ &t->succ_id,
+ t,
+ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY))
+ {
+ GNUNET_break (0);
+ GNUNET_CONTAINER_MDLL_remove (pred,
+ pred->pred_head,
+ pred->pred_tail,
+ t);
+ GNUNET_free (t);
+ return GNUNET_OK;
+ }
+ GNUNET_CONTAINER_MDLL_insert (succ,
+ succ->succ_head,
+ succ->succ_tail,
+ t);
+ env = GNUNET_MQ_msg (rwm,
+ GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK);
+ rwm->hops_taken = htons (1 + ntohs (m->hops_taken));
+ rwm->layer = m->layer;
+ rwm->trail_id = t->succ_id;
+ GNUNET_MQ_send (succ->mq,
+ env);
+ }
return GNUNET_OK;
}
+
/**
- * Handle a `struct FingerSetupResponseMessage` from a GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP_RESPONSE
+ * Handle a `struct RandomWalkResponseMessage` from a GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE
* message.
*
* @param cls closure (NULL)
* @return #GNUNET_OK on success, #GNUNET_SYSERR on error
*/
static int
-handle_dht_p2p_finger_setup_response (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- const struct GNUNET_MessageHeader *message)
+handle_dht_p2p_random_walk_response (void *cls,
+ const struct GNUNET_PeerIdentity *peer,
+ const struct GNUNET_MessageHeader *message)
{
- const struct FingerSetupResponseMessage *fsrm;
-
- fsrm = (const struct FingerSetupResponseMessage *) message;
+ const struct RandomWalkResponseMessage *rwrm;
+ rwrm = (const struct RandomWalkResponseMessage *) message;
+ // 1) lookup trail => find Finger entry => fill in 'destination' and mark valid, move to end of sorted array,
+ //mark unsorted, update links from 'trails'
/*
* Steps :
* 1 check if we are the correct layer
/**
- * Handle a `struct FingerDestroyMessage`.
+ * Handle a `struct TrailDestroyMessage`.
*
* @param cls closure (NULL)
* @param peer sender identity
* @return #GNUNET_OK on success, #GNUNET_SYSERR on error
*/
static int
-handle_dht_p2p_finger_destroy (void *cls,
+handle_dht_p2p_trail_destroy (void *cls,
const struct GNUNET_PeerIdentity *peer,
const struct GNUNET_MessageHeader *message)
{
- const struct FingerDestroyMessage *fdm;
-
- fdm = (const struct FingerDestroyMessage *) message;
-
- /*
- * Steps :
- * 1 check if message comme from a trail
- * 1.a.1 if true: send the destroy message to the rest trail
- * 1.a.2 clean the trail structure
- * 1.a.3 did i have to remove the trail and ID from the db structure?
- * 1.b if false: do nothing
- */
+ const struct TrailDestroyMessage *tdm;
+ struct Trail *trail;
+ tdm = (const struct TrailDestroyMessage *) message;
+ trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
+ &tdm->trail_id);
+ delete_trail (trail,
+ ( (NULL != trail->succ) &&
+ (0 == memcmp (peer,
+ &trail->succ->id,
+ sizeof (struct GNUNET_PeerIdentity))) ),
+ ( (NULL != trail->pred) &&
+ (0 == memcmp (peer,
+ &trail->pred->id,
+ sizeof (struct GNUNET_PeerIdentity))) ));
return GNUNET_OK;
}
-/**
- * Handle a `struct FingerRouteMessage`.
- *
- * @param cls closure (NULL)
- * @param peer sender identity
- * @param message the finger route message
- * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
- */
-static int
-handle_dht_p2p_finger_route (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- const struct GNUNET_MessageHeader *message)
-{
- const struct FingerRouteMessage *frm;
-
- frm = (const struct FingerRouteMessage *) message;
- /* FIXME: check the size of the message */
-
- /*
- * steps :
- * 1 find the good trail
- * 2 check the message inside
- * 2.a if the message is a finger setup message : increments ce hops_takeb
- * 3 send the finger route message
- */
-
- return GNUNET_OK;
-}
/**
- * Handle a `struct FingerSetupMessage` from a GNUNET_MESSAGE_TYPE_WDHT_NEIGHBOUR_FIND
+ * Handle a `struct FindSuccessorMessage` from a #GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND
* message.
*
* @param cls closure (NULL)
- * @param peer sender identity
+ * @param trail_id path to the originator
* @param message the finger setup message
* @return #GNUNET_OK on success, #GNUNET_SYSERR on error
*/
static int
-handle_dht_p2p_neighbour_find (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- const struct GNUNET_MessageHeader *message)
+handle_dht_p2p_successor_find (void *cls,
+ const struct GNUNET_HashCode *trail_id,
+ const struct GNUNET_MessageHeader *message)
{
- const struct FingerSetupMessage *fsm;
-
- fsm = (const struct FingerSetupMessage *) message;
-
+ const struct FindSuccessorMessage *fsm;
+
+ fsm = (const struct FindSuccessorMessage *) message;
+ // locate trail (for sending reply), if not exists, fail nicely.
+ // otherwise, go to datacache and return 'top k' elements closest to 'key'
+ // as "PUT" messages via the trail (need to extend DB API!)
+#if 0
+ GDS_DATACACHE_get_successors (trail_id,
+ key);
+#endif
return GNUNET_OK;
}
-/**
- * Handle a `struct FingerSetupResponseMessage` from a GNUNET_MESSAGE_TYPE_WDHT_NEIGHBOUR_FIND
- * message.
- *
- * @param cls closure (NULL)
- * @param peer sender identity
- * @param message the finger setup response message
- * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
- */
-static int
-handle_dht_p2p_neighbour_found (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- const struct GNUNET_MessageHeader *message)
-{
- const struct FingerSetupResponseMessage *fsrm;
-
- fsrm = (const struct FingerSetupResponseMessage *) message;
-
- return GNUNET_OK;
-}
/**
* Handle a `struct PeerGetMessage`.
*
* @param cls closure (NULL)
- * @param peer sender identity
+ * @param trail_id path to the originator
* @param message the peer get message
* @return #GNUNET_OK on success, #GNUNET_SYSERR on error
*/
static int
handle_dht_p2p_peer_get (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- const struct GNUNET_MessageHeader *message)
+ const struct GNUNET_HashCode *trail_id,
+ const struct GNUNET_MessageHeader *message)
{
const struct PeerGetMessage *pgm;
+ // FIXME: note: never called like this, message embedded with trail route!
pgm = (const struct PeerGetMessage *) message;
-
+ // -> lookup in datacache (figure out way to remember trail!)
/*
* steps :
* 1 extract the result
return GNUNET_OK;
}
+
/**
* Handle a `struct PeerGetResultMessage`.
*
* @param cls closure (NULL)
- * @param peer sender identity
+ * @param trail_id path to the originator
* @param message the peer get result message
* @return #GNUNET_OK on success, #GNUNET_SYSERR on error
*/
static int
handle_dht_p2p_peer_get_result (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- const struct GNUNET_MessageHeader *message)
+ const struct GNUNET_HashCode *trail_id,
+ const struct GNUNET_MessageHeader *message)
{
const struct PeerGetResultMessage *pgrm;
pgrm = (const struct PeerGetResultMessage *) message;
-
- /*
- * steps :
- * 1 extract the result
- * 2 create a peerGetResult struct
- * 3 send it using the good trail
- *
- * What do i do when i don't have the key/value?
- */
-
+ // pretty much: parse, & pass to client (there is some call for that...)
+
+#if 0
+ GDS_CLIENTS_process_get (options,
+ type,
+ 0, 0,
+ path_length, path,
+ key);
+ (void) GDS_DATACACHE_handle_get (trail_id,
+ key,
+ type,
+ xquery,
+ xquery_size,
+ &reply_bf,
+ reply_bf_mutator);
+#endif
return GNUNET_OK;
}
* Handle a `struct PeerPutMessage`.
*
* @param cls closure (NULL)
- * @param peer sender identity
+ * @param trail_id path to the originator
* @param message the peer put message
* @return #GNUNET_OK on success, #GNUNET_SYSERR on error
*/
static int
handle_dht_p2p_peer_put (void *cls,
- const struct GNUNET_PeerIdentity *peer,
- const struct GNUNET_MessageHeader *message)
+ const struct GNUNET_HashCode *trail_id,
+ const struct GNUNET_MessageHeader *message)
{
const struct PeerGetResultMessage *pgrm;
pgrm = (const struct PeerGetResultMessage *) message;
-
+ // parse & store in datacache, this is in response to us asking for successors.
/*
* steps :
* 1 check the size of the message
* 2 use the API to add the value in the "database". Check on the xdht file, how to do it.
* 3 Did i a have to return a notification or did i have to return GNUNET_[OK|SYSERR]?
*/
+#if 0
+ GDS_DATACACHE_handle_put (expiration_time,
+ key,
+ path_length, path,
+ block_type,
+ data_size,
+ data);
+ GDS_CLIENTS_process_put (options,
+ block_type,
+ 0, 0,
+ path_length, path,
+ expiration_time,
+ key,
+ data,
+ data_size);
+#endif
+ return GNUNET_OK;
+}
+
+
+
+
+/**
+ * Handler for a message we received along some trail.
+ *
+ * @param cls closure
+ * @param trail_id trail identifier
+ * @param message the message we got
+ * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
+ */
+typedef int
+(*TrailHandlerCallback)(void *cls,
+ const struct GNUNET_HashCode *trail_id,
+ const struct GNUNET_MessageHeader *message);
+
+
+/**
+ * Definition of a handler for a message received along some trail.
+ */
+struct TrailHandler
+{
+ /**
+ * NULL for end-of-list.
+ */
+ TrailHandlerCallback callback;
+
+ /**
+ * Closure for @e callback.
+ */
+ void *cls;
+
+ /**
+ * Message type this handler addresses.
+ */
+ uint16_t message_type;
+
+ /**
+ * Use 0 for variable-size.
+ */
+ uint16_t message_size;
+};
+
+
+/**
+ * Handle a `struct TrailRouteMessage`.
+ *
+ * @param cls closure (NULL)
+ * @param peer sender identity
+ * @param message the finger destroy message
+ * @return #GNUNET_OK on success, #GNUNET_SYSERR on error
+ */
+static int
+handle_dht_p2p_trail_route (void *cls,
+ const struct GNUNET_PeerIdentity *peer,
+ const struct GNUNET_MessageHeader *message)
+{
+ static const struct TrailHandler handlers[] = {
+ { &handle_dht_p2p_successor_find, NULL,
+ GNUNET_MESSAGE_TYPE_WDHT_SUCCESSOR_FIND,
+ sizeof (struct FindSuccessorMessage) },
+ { NULL, NULL, 0, 0 }
+ };
+ unsigned int i;
+ const struct TrailRouteMessage *trm;
+ const struct GNUNET_PeerIdentity *path;
+ uint16_t path_length;
+ const struct GNUNET_MessageHeader *payload;
+ const struct TrailHandler *th;
+ struct Trail *trail;
+ size_t msize;
+
+ /* Parse and check message is well-formed */
+ msize = ntohs (message->size);
+ if (msize < sizeof (struct TrailRouteMessage))
+ {
+ GNUNET_break_op (0);
+ return GNUNET_YES;
+ }
+ trm = (const struct TrailRouteMessage *) message;
+ path_length = ntohs (trm->path_length);
+ if (msize < sizeof (struct TrailRouteMessage) +
+ path_length * sizeof (struct GNUNET_PeerIdentity) +
+ sizeof (struct GNUNET_MessageHeader) )
+ {
+ GNUNET_break_op (0);
+ return GNUNET_YES;
+ }
+ path = (const struct GNUNET_PeerIdentity *) &trm[1];
+ payload = (const struct GNUNET_MessageHeader *) &path[path_length];
+ if (msize != (ntohs (payload->size) +
+ sizeof (struct TrailRouteMessage) +
+ path_length * sizeof (struct GNUNET_PeerIdentity)))
+ {
+ GNUNET_break_op (0);
+ return GNUNET_YES;
+ }
+
+ /* Is this message for us? */
+ trail = GNUNET_CONTAINER_multihashmap_get (trail_map,
+ &trm->trail_id);
+ if ( (NULL != trail->pred) &&
+ (0 == memcmp (peer,
+ &trail->pred->id,
+ sizeof (struct GNUNET_PeerIdentity))) )
+ {
+ /* forward to 'successor' */
+ if (NULL != trail->succ)
+ {
+ forward_message_on_trail (trail->succ,
+ &trail->succ_id,
+ ntohs (trm->record_path),
+ peer,
+ path,
+ path_length,
+ payload);
+ return GNUNET_OK;
+ }
+ }
+ else
+ {
+ /* forward to 'predecessor' */
+ GNUNET_break_op ( (NULL != trail->succ) &&
+ (0 == memcmp (peer,
+ &trail->succ->id,
+ sizeof (struct GNUNET_PeerIdentity))) );
+ if (NULL != trail->pred)
+ {
+ forward_message_on_trail (trail->pred,
+ &trail->pred_id,
+ ntohs (trm->record_path),
+ peer,
+ path,
+ path_length,
+ payload);
+ return GNUNET_OK;
+ }
+ }
+
+ /* Message is for us, dispatch to handler */
+ th = NULL;
+ for (i=0; NULL != handlers[i].callback; i++)
+ {
+ th = &handlers[i];
+ if (ntohs (payload->type) == th->message_type)
+ {
+ if ( (0 == th->message_size) ||
+ (ntohs (payload->size) == th->message_size) )
+ th->callback (th->cls,
+ &trm->trail_id,
+ payload);
+ else
+ GNUNET_break_op (0);
+ break;
+ }
+ }
+ GNUNET_break_op (NULL != th);
return GNUNET_OK;
}
GDS_NEIGHBOURS_init (void)
{
static const struct GNUNET_CORE_MessageHandler core_handlers[] = {
- { &handle_dht_p2p_finger_setup,
- GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP,
- sizeof (struct FingerSetupMessage) },
- { &handle_dht_p2p_finger_setup_response,
- GNUNET_MESSAGE_TYPE_WDHT_FINGER_SETUP_RESPONSE,
- sizeof (struct FingerSetupResponseMessage) },
- { &handle_dht_p2p_finger_destroy,
- GNUNET_MESSAGE_TYPE_WDHT_FINGER_DESTROY,
- sizeof (struct FingerDestroyMessage) },
- { &handle_dht_p2p_finger_route,
- GNUNET_MESSAGE_TYPE_WDHT_FINGER_ROUTE,
- 0},
- { &handle_dht_p2p_neighbour_find,
- GNUNET_MESSAGE_TYPE_WDHT_NEIGHBOUR_FIND,
- sizeof (struct FingerSetupMessage) },
- { &handle_dht_p2p_neighbour_found,
- GNUNET_MESSAGE_TYPE_WDHT_NEIGHBOUR_FOUND,
- sizeof (struct FingerSetupResponseMessage) },
- { &handle_dht_p2p_peer_get,
- GNUNET_MESSAGE_TYPE_WDHT_GET,
- sizeof (struct PeerGetMessage) },
- { &handle_dht_p2p_peer_get_result,
- GNUNET_MESSAGE_TYPE_WDHT_GET_RESULT,
- 0},
- { &handle_dht_p2p_peer_put,
- GNUNET_MESSAGE_TYPE_WDHT_PUT,
+ { &handle_dht_p2p_random_walk,
+ GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK,
+ sizeof (struct RandomWalkMessage) },
+ { &handle_dht_p2p_random_walk_response,
+ GNUNET_MESSAGE_TYPE_WDHT_RANDOM_WALK_RESPONSE,
+ sizeof (struct RandomWalkResponseMessage) },
+ { &handle_dht_p2p_trail_destroy,
+ GNUNET_MESSAGE_TYPE_WDHT_TRAIL_DESTROY,
+ sizeof (struct TrailDestroyMessage) },
+ { &handle_dht_p2p_trail_route,
+ GNUNET_MESSAGE_TYPE_WDHT_TRAIL_ROUTE,
0},
{NULL, 0, 0}
};
if (NULL == core_api)
return GNUNET_SYSERR;
-
- fingers_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
- successors_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
-
- init_db_structure();
-
-
-
-
+ friends_peermap = GNUNET_CONTAINER_multipeermap_create (256, GNUNET_NO);
+ trail_map = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_YES);
+ trail_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
return GNUNET_OK;
}
return;
GNUNET_CORE_disconnect (core_api);
core_api = NULL;
-
- GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (fingers_peermap));
- GNUNET_CONTAINER_multipeermap_destroy (fingers_peermap);
- GNUNET_CONTAINER_multipeermap_destroy (successors_peermap);
- destroy_db_structure();
-
- fingers_peermap = NULL;
+ GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friends_peermap));
+ GNUNET_CONTAINER_multipeermap_destroy (friends_peermap);
+ friends_peermap = NULL;
+ GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (trail_map));
+ GNUNET_CONTAINER_multihashmap_destroy (trail_map);
+ trail_map = NULL;
+ GNUNET_CONTAINER_heap_destroy (trail_heap);
+ trail_heap = NULL;
+ if (NULL != trail_timeout_task)
+ {
+ GNUNET_SCHEDULER_cancel (trail_timeout_task);
+ trail_timeout_task = NULL;
+ }
}