From 395864e0875252a779e783765b955c4193741065 Mon Sep 17 00:00:00 2001 From: Supriti Singh Date: Mon, 7 Apr 2014 17:23:33 +0000 Subject: 1.Removed GNUNET_CRYPTO_compute_finger_identity 2.Removed myself as the first element of the trail. 3.Multiple entries in the routing table. 4.Put/Get/Monitor from old DHT added back in clients file. --- src/dht/gnunet-service-xdht_clients.c | 1172 +++++++++++++++++++++++++++--- src/dht/gnunet-service-xdht_clients.h | 33 +- src/dht/gnunet-service-xdht_datacache.c | 2 +- src/dht/gnunet-service-xdht_neighbours.c | 984 ++++++++++++++----------- src/dht/gnunet-service-xdht_neighbours.h | 15 +- src/dht/gnunet-service-xdht_routing.c | 99 ++- src/dht/gnunet-service-xdht_routing.h | 8 +- 7 files changed, 1716 insertions(+), 597 deletions(-) (limited to 'src/dht') diff --git a/src/dht/gnunet-service-xdht_clients.c b/src/dht/gnunet-service-xdht_clients.c index 050d8a99e..d3b920551 100644 --- a/src/dht/gnunet-service-xdht_clients.c +++ b/src/dht/gnunet-service-xdht_clients.c @@ -21,7 +21,8 @@ /** * @file dht/gnunet-service-dht_clients.c * @brief GNUnet DHT service's client management code - * @author Supriti Singh + * @author Christian Grothoff + * @author Nathan Evans */ #include "platform.h" @@ -34,6 +35,14 @@ #include "gnunet-service-xdht_neighbours.h" #include "dht.h" + +/** + * Should routing details be logged to stderr (for debugging)? + */ +#define LOG_TRAFFIC(kind,...) GNUNET_log_from (kind, "dht-traffic",__VA_ARGS__) + +#define LOG(kind,...) GNUNET_log_from (kind, "dht-clients",__VA_ARGS__) + /** * Linked list of messages to send to clients. */ @@ -58,6 +67,7 @@ struct PendingMessage }; + /** * Struct containing information about a client, * handle to connect to it, and any pending messages @@ -99,6 +109,129 @@ struct ClientList }; +/** + * Entry in the local forwarding map for a client's GET request. + */ +struct ClientQueryRecord +{ + + /** + * The key this request was about + */ + struct GNUNET_HashCode key; + + /** + * Client responsible for the request. + */ + struct ClientList *client; + + /** + * Extended query (see gnunet_block_lib.h), allocated at the end of this struct. + */ + const void *xquery; + + /** + * Replies we have already seen for this request. + */ + struct GNUNET_HashCode *seen_replies; + + /** + * Pointer to this nodes heap location in the retry-heap (for fast removal) + */ + struct GNUNET_CONTAINER_HeapNode *hnode; + + /** + * What's the delay between re-try operations that we currently use for this + * request? + */ + struct GNUNET_TIME_Relative retry_frequency; + + /** + * What's the next time we should re-try this request? + */ + struct GNUNET_TIME_Absolute retry_time; + + /** + * The unique identifier of this request + */ + uint64_t unique_id; + + /** + * Number of bytes in xquery. + */ + size_t xquery_size; + + /** + * Number of entries in 'seen_replies'. + */ + unsigned int seen_replies_count; + + /** + * Desired replication level + */ + uint32_t replication; + + /** + * Any message options for this request + */ + uint32_t msg_options; + + /** + * The type for the data for the GET request. + */ + enum GNUNET_BLOCK_Type type; + +}; + + +/** + * Struct containing paremeters of monitoring requests. + */ +struct ClientMonitorRecord +{ + + /** + * Next element in DLL. + */ + struct ClientMonitorRecord *next; + + /** + * Previous element in DLL. + */ + struct ClientMonitorRecord *prev; + + /** + * Type of blocks that are of interest + */ + enum GNUNET_BLOCK_Type type; + + /** + * Key of data of interest, NULL for all. + */ + struct GNUNET_HashCode *key; + + /** + * Flag whether to notify about GET messages. + */ + int16_t get; + + /** + * Flag whether to notify about GET_REPONSE messages. + */ + int16_t get_resp; + + /** + * Flag whether to notify about PUT messages. + */ + uint16_t put; + + /** + * Client to notify of these requests. + */ + struct ClientList *client; +}; + + /** * List of active clients. */ @@ -109,12 +242,41 @@ static struct ClientList *client_head; */ static struct ClientList *client_tail; +/** + * List of active monitoring requests. + */ +static struct ClientMonitorRecord *monitor_head; + +/** + * List of active monitoring requests. + */ +static struct ClientMonitorRecord *monitor_tail; + +/** + * Hashmap for fast key based lookup, maps keys to `struct ClientQueryRecord` entries. + */ +static struct GNUNET_CONTAINER_MultiHashMap *forward_map; + +/** + * Heap with all of our client's request, sorted by retry time (earliest on top). + */ +static struct GNUNET_CONTAINER_Heap *retry_heap; + +/** + * Task that re-transmits requests (using retry_heap). + */ +static GNUNET_SCHEDULER_TaskIdentifier retry_task; + + /** * Task run to check for messages that need to be sent to a client. * * @param client a ClientList, containing the client and any messages to be sent to it */ -static void process_pending_messages (struct ClientList *client); +static void +process_pending_messages (struct ClientList *client); + + /** * Callback called as a result of issuing a GNUNET_SERVER_notify_transmit_ready * request. A ClientList is passed as closure, take the head of the list @@ -208,6 +370,41 @@ add_pending_message (struct ClientList *client, process_pending_messages (client); } + +/** + * Closure for 'forward_reply' + */ +struct ForwardReplyContext +{ + + /** + * Actual message to send to matching clients. + */ + struct PendingMessage *pm; + + /** + * Embedded payload. + */ + const void *data; + + /** + * Type of the data. + */ + enum GNUNET_BLOCK_Type type; + + /** + * Number of bytes in data. + */ + size_t data_size; + + /** + * Do we need to copy 'pm' because it was already used? + */ + int do_copy; + +}; + + /** * Find a client if it exists, add it otherwise. * @@ -235,118 +432,476 @@ find_active_client (struct GNUNET_SERVER_Client *client) /** - * SUPU: Call made from dht_api.c - * Handler for monitor stop messages + * Iterator over hash map entries that frees all entries + * associated with the given client. * - * @param cls closure for the service - * @param client the client we received this message from - * @param message the actual message received + * @param cls client to search for in source routes + * @param key current key code (ignored) + * @param value value in the hash map, a ClientQueryRecord + * @return #GNUNET_YES (we should continue to iterate) + */ +static int +remove_client_records (void *cls, const struct GNUNET_HashCode * key, void *value) +{ + struct ClientList *client = cls; + struct ClientQueryRecord *record = value; + + if (record->client != client) + return GNUNET_YES; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Removing client %p's record for key %s\n", client, + GNUNET_h2s (key)); + GNUNET_assert (GNUNET_YES == + GNUNET_CONTAINER_multihashmap_remove (forward_map, key, + record)); + if (NULL != record->hnode) + GNUNET_CONTAINER_heap_remove_node (record->hnode); + GNUNET_array_grow (record->seen_replies, record->seen_replies_count, 0); + GNUNET_free (record); + return GNUNET_YES; +} + + +/** + * Iterator over hash map entries that send a given reply to + * each of the matching clients. With some tricky recycling + * of the buffer. * + * @param cls the 'struct ForwardReplyContext' + * @param key current key + * @param value value in the hash map, a ClientQueryRecord + * @return GNUNET_YES (we should continue to iterate), + * if the result is mal-formed, GNUNET_NO */ -static void -handle_dht_local_monitor_stop (void *cls, struct GNUNET_SERVER_Client *client, - const struct GNUNET_MessageHeader *message) +static int +forward_reply (void *cls, const struct GNUNET_HashCode * key, void *value) { - //const struct GNUNET_DHT_MonitorStartStopMessage *msg; + struct ForwardReplyContext *frc = cls; + struct ClientQueryRecord *record = value; + struct PendingMessage *pm; + struct GNUNET_DHT_ClientResultMessage *reply; + enum GNUNET_BLOCK_EvaluationResult eval; + int do_free; + struct GNUNET_HashCode ch; + unsigned int i; + + LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG, + "R5N CLIENT-RESULT %s\n", + GNUNET_h2s_full (key)); + if ((record->type != GNUNET_BLOCK_TYPE_ANY) && (record->type != frc->type)) + { + LOG (GNUNET_ERROR_TYPE_DEBUG, + "Record type missmatch, not passing request for key %s to local client\n", + GNUNET_h2s (key)); + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop + ("# Key match, type mismatches in REPLY to CLIENT"), + 1, GNUNET_NO); + return GNUNET_YES; /* type mismatch */ + } + GNUNET_CRYPTO_hash (frc->data, frc->data_size, &ch); + for (i = 0; i < record->seen_replies_count; i++) + if (0 == memcmp (&record->seen_replies[i], &ch, sizeof (struct GNUNET_HashCode))) + { + LOG (GNUNET_ERROR_TYPE_DEBUG, + "Duplicate reply, not passing request for key %s to local client\n", + GNUNET_h2s (key)); + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop + ("# Duplicate REPLIES to CLIENT request dropped"), + 1, GNUNET_NO); + return GNUNET_YES; /* duplicate */ + } + eval = + GNUNET_BLOCK_evaluate (GDS_block_context, record->type, key, NULL, 0, + record->xquery, record->xquery_size, frc->data, + frc->data_size); + LOG (GNUNET_ERROR_TYPE_DEBUG, + "Evaluation result is %d for key %s for local client's query\n", + (int) eval, GNUNET_h2s (key)); + switch (eval) + { + case GNUNET_BLOCK_EVALUATION_OK_LAST: + do_free = GNUNET_YES; + break; + case GNUNET_BLOCK_EVALUATION_OK_MORE: + GNUNET_array_append (record->seen_replies, record->seen_replies_count, ch); + do_free = GNUNET_NO; + break; + case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE: + /* should be impossible to encounter here */ + GNUNET_break (0); + return GNUNET_YES; + case GNUNET_BLOCK_EVALUATION_RESULT_INVALID: + GNUNET_break_op (0); + return GNUNET_NO; + case GNUNET_BLOCK_EVALUATION_REQUEST_VALID: + GNUNET_break (0); + return GNUNET_NO; + case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID: + GNUNET_break (0); + return GNUNET_NO; + case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT: + return GNUNET_YES; + case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED: + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, + _("Unsupported block type (%u) in request!\n"), record->type); + return GNUNET_NO; + default: + GNUNET_break (0); + return GNUNET_NO; + } + if (GNUNET_NO == frc->do_copy) + { + /* first time, we can use the original data */ + pm = frc->pm; + frc->do_copy = GNUNET_YES; + } + else + { + /* two clients waiting for same reply, must copy for queueing */ + pm = GNUNET_malloc (sizeof (struct PendingMessage) + + ntohs (frc->pm->msg->size)); + memcpy (pm, frc->pm, + sizeof (struct PendingMessage) + ntohs (frc->pm->msg->size)); + pm->next = pm->prev = NULL; + pm->msg = (struct GNUNET_MessageHeader *) &pm[1]; + } + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop ("# RESULTS queued for clients"), 1, + GNUNET_NO); + reply = (struct GNUNET_DHT_ClientResultMessage *) &pm[1]; + reply->unique_id = record->unique_id; + LOG (GNUNET_ERROR_TYPE_DEBUG, + "Queueing reply to query %s for client %p\n", + GNUNET_h2s (key), + record->client->client_handle); + add_pending_message (record->client, pm); + if (GNUNET_YES == do_free) + remove_client_records (record->client, key, record); + return GNUNET_YES; } /** - * SUPU: Monitor call made from dht_api.c - * Handler for monitor start messages + * Handle a reply we've received from another peer. If the reply + * matches any of our pending queries, forward it to the respective + * client(s). * - * @param cls closure for the service - * @param client the client we received this message from - * @param message the actual message received + * @param expiration when will the reply expire + * @param key the query this reply is for + * @param get_path_length number of peers in @a get_path + * @param get_path path the reply took on get + * @param put_path_length number of peers in @a put_path + * @param put_path path the reply took on put + * @param type type of the reply + * @param data_size number of bytes in @a data + * @param data application payload data + */ +void +GDS_CLIENTS_handle_reply (struct GNUNET_TIME_Absolute expiration, + const struct GNUNET_HashCode *key, + unsigned int get_path_length, + const struct GNUNET_PeerIdentity *get_path, + unsigned int put_path_length, + const struct GNUNET_PeerIdentity *put_path, + enum GNUNET_BLOCK_Type type, size_t data_size, + const void *data) +{ + struct ForwardReplyContext frc; + struct PendingMessage *pm; + struct GNUNET_DHT_ClientResultMessage *reply; + struct GNUNET_PeerIdentity *paths; + size_t msize; + + LOG (GNUNET_ERROR_TYPE_DEBUG, + "reply for key %s\n", + GNUNET_h2s (key)); + + if (NULL == GNUNET_CONTAINER_multihashmap_get (forward_map, key)) + { + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop + ("# REPLIES ignored for CLIENTS (no match)"), 1, + GNUNET_NO); + return; /* no matching request, fast exit! */ + } + msize = + sizeof (struct GNUNET_DHT_ClientResultMessage) + data_size + + (get_path_length + put_path_length) * sizeof (struct GNUNET_PeerIdentity); + if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE) + { + GNUNET_log (GNUNET_ERROR_TYPE_WARNING, + _("Could not pass reply to client, message too big!\n")); + return; + } + pm = GNUNET_malloc (msize + sizeof (struct PendingMessage)); + reply = (struct GNUNET_DHT_ClientResultMessage *) &pm[1]; + pm->msg = &reply->header; + reply->header.size = htons ((uint16_t) msize); + reply->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_CLIENT_RESULT); + reply->type = htonl (type); + reply->get_path_length = htonl (get_path_length); + reply->put_path_length = htonl (put_path_length); + reply->unique_id = 0; /* filled in later */ + reply->expiration = GNUNET_TIME_absolute_hton (expiration); + reply->key = *key; + paths = (struct GNUNET_PeerIdentity *) &reply[1]; + memcpy (paths, put_path, + sizeof (struct GNUNET_PeerIdentity) * put_path_length); + memcpy (&paths[put_path_length], get_path, + sizeof (struct GNUNET_PeerIdentity) * get_path_length); + memcpy (&paths[get_path_length + put_path_length], data, data_size); + frc.do_copy = GNUNET_NO; + frc.pm = pm; + frc.data = data; + frc.data_size = data_size; + frc.type = type; + GNUNET_CONTAINER_multihashmap_get_multiple (forward_map, key, &forward_reply, + &frc); + + if (GNUNET_NO == frc.do_copy) + { + /* did not match any of the requests, free! */ + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop + ("# REPLIES ignored for CLIENTS (no match)"), 1, + GNUNET_NO); + GNUNET_free (pm); + } +} + +/** + * Check if some client is monitoring GET messages and notify + * them in that case. * + * @param options Options, for instance RecordRoute, DemultiplexEverywhere. + * @param type The type of data in the request. + * @param hop_count Hop count so far. + * @param path_length number of entries in path (or 0 if not recorded). + * @param path peers on the GET path (or NULL if not recorded). + * @param desired_replication_level Desired replication level. + * @param key Key of the requested data. */ -static void -handle_dht_local_monitor (void *cls, struct GNUNET_SERVER_Client *client, - const struct GNUNET_MessageHeader *message) +void +GDS_CLIENTS_process_get (uint32_t options, + enum GNUNET_BLOCK_Type type, + uint32_t hop_count, + uint32_t desired_replication_level, + unsigned int path_length, + const struct GNUNET_PeerIdentity *path, + const struct GNUNET_HashCode * key) { - //const struct GNUNET_DHT_MonitorStartStopMessage *msg; - /* FIXME: At the moment I don't know exact usage of monitor message. But most - probably it will be just copy and paste from old implementation. */ + struct ClientMonitorRecord *m; + struct ClientList **cl; + unsigned int cl_size; + + cl = NULL; + cl_size = 0; + for (m = monitor_head; NULL != m; m = m->next) + { + if ((GNUNET_BLOCK_TYPE_ANY == m->type || m->type == type) && + (NULL == m->key || + memcmp (key, m->key, sizeof(struct GNUNET_HashCode)) == 0)) + { + struct PendingMessage *pm; + struct GNUNET_DHT_MonitorGetMessage *mmsg; + struct GNUNET_PeerIdentity *msg_path; + size_t msize; + unsigned int i; + + /* Don't send duplicates */ + for (i = 0; i < cl_size; i++) + if (cl[i] == m->client) + break; + if (i < cl_size) + continue; + GNUNET_array_append (cl, cl_size, m->client); + + msize = path_length * sizeof (struct GNUNET_PeerIdentity); + msize += sizeof (struct GNUNET_DHT_MonitorGetMessage); + msize += sizeof (struct PendingMessage); + pm = GNUNET_malloc (msize); + mmsg = (struct GNUNET_DHT_MonitorGetMessage *) &pm[1]; + pm->msg = &mmsg->header; + mmsg->header.size = htons (msize - sizeof (struct PendingMessage)); + mmsg->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_MONITOR_GET); + mmsg->options = htonl(options); + mmsg->type = htonl(type); + mmsg->hop_count = htonl(hop_count); + mmsg->desired_replication_level = htonl(desired_replication_level); + mmsg->get_path_length = htonl(path_length); + memcpy (&mmsg->key, key, sizeof (struct GNUNET_HashCode)); + msg_path = (struct GNUNET_PeerIdentity *) &mmsg[1]; + if (path_length > 0) + memcpy (msg_path, path, + path_length * sizeof (struct GNUNET_PeerIdentity)); + add_pending_message (m->client, pm); + } + } + GNUNET_free_non_null (cl); } -/**SUPU: Call to this function is made whenever a client does not want the - * get request any more. There is a function in dht_api.c but I don't know - * yet how the call is made to this function. - * Handler for any generic DHT stop messages, calls the appropriate handler - * depending on message type (if processed locally) - * - * @param cls closure for the service - * @param client the client we received this message from - * @param message the actual message received +/** + * Check if some client is monitoring PUT messages and notify + * them in that case. * + * @param options Options, for instance RecordRoute, DemultiplexEverywhere. + * @param type The type of data in the request. + * @param hop_count Hop count so far. + * @param path_length number of entries in path (or 0 if not recorded). + * @param path peers on the PUT path (or NULL if not recorded). + * @param desired_replication_level Desired replication level. + * @param exp Expiration time of the data. + * @param key Key under which data is to be stored. + * @param data Pointer to the data carried. + * @param size Number of bytes in data. + */ +void +GDS_CLIENTS_process_put (uint32_t options, + enum GNUNET_BLOCK_Type type, + uint32_t hop_count, + uint32_t desired_replication_level, + unsigned int path_length, + const struct GNUNET_PeerIdentity *path, + struct GNUNET_TIME_Absolute exp, + const struct GNUNET_HashCode * key, + const void *data, + size_t size) +{ + struct ClientMonitorRecord *m; + struct ClientList **cl; + unsigned int cl_size; + + cl = NULL; + cl_size = 0; + for (m = monitor_head; NULL != m; m = m->next) + { + if ((GNUNET_BLOCK_TYPE_ANY == m->type || m->type == type) && + (NULL == m->key || + memcmp (key, m->key, sizeof(struct GNUNET_HashCode)) == 0)) + { + struct PendingMessage *pm; + struct GNUNET_DHT_MonitorPutMessage *mmsg; + struct GNUNET_PeerIdentity *msg_path; + size_t msize; + unsigned int i; + + /* Don't send duplicates */ + for (i = 0; i < cl_size; i++) + if (cl[i] == m->client) + break; + if (i < cl_size) + continue; + GNUNET_array_append (cl, cl_size, m->client); + + msize = size; + msize += path_length * sizeof (struct GNUNET_PeerIdentity); + msize += sizeof (struct GNUNET_DHT_MonitorPutMessage); + msize += sizeof (struct PendingMessage); + pm = GNUNET_malloc (msize); + mmsg = (struct GNUNET_DHT_MonitorPutMessage *) &pm[1]; + pm->msg = (struct GNUNET_MessageHeader *) mmsg; + mmsg->header.size = htons (msize - sizeof (struct PendingMessage)); + mmsg->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_MONITOR_PUT); + mmsg->options = htonl(options); + mmsg->type = htonl(type); + mmsg->hop_count = htonl(hop_count); + mmsg->desired_replication_level = htonl(desired_replication_level); + mmsg->put_path_length = htonl(path_length); + msg_path = (struct GNUNET_PeerIdentity *) &mmsg[1]; + if (path_length > 0) + { + memcpy (msg_path, path, + path_length * sizeof (struct GNUNET_PeerIdentity)); + } + mmsg->expiration_time = GNUNET_TIME_absolute_hton(exp); + memcpy (&mmsg->key, key, sizeof (struct GNUNET_HashCode)); + if (size > 0) + memcpy (&msg_path[path_length], data, size); + add_pending_message (m->client, pm); + } + } + GNUNET_free_non_null (cl); +} + + +/** + * Route the given request via the DHT. */ static void -handle_dht_local_get_stop (void *cls, struct GNUNET_SERVER_Client *client, - const struct GNUNET_MessageHeader *message) +transmit_request (struct ClientQueryRecord *cqr) { - //const struct GNUNET_DHT_ClientGetStopMessage *dht_stop_msg; - /* FIXME: Whats the use of get_stop. A client notifies the server to stop asking - for the get message. But in case of x-vine, it asks for get only once. So, - when it has already send the get message, after that if client asks it to - stop, it really can't do anything. Its better to wait for the result, discard - it and don't communicate with client about the result instead of generating - more traffic.*/ + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop + ("# GET requests from clients injected"), 1, + GNUNET_NO); + + LOG (GNUNET_ERROR_TYPE_DEBUG, + "Initiating GET for %s, replication %u, already have %u replies\n", + GNUNET_h2s (&cqr->key), + cqr->replication, + cqr->seen_replies_count); +#if 0 + /* FIXME: Change it to your own handle_get. */ + GDS_NEIGHBOURS_handle_get (cqr->type, cqr->msg_options, cqr->replication, + 0 /* hop count */ , + &cqr->key, cqr->xquery, cqr->xquery_size, reply_bf, + reply_bf_mutator, peer_bf); +#endif + + + /* exponential back-off for retries. + * max GNUNET_TIME_STD_EXPONENTIAL_BACKOFF_THRESHOLD (15 min) */ + cqr->retry_frequency = GNUNET_TIME_STD_BACKOFF (cqr->retry_frequency); + cqr->retry_time = GNUNET_TIME_relative_to_absolute (cqr->retry_frequency); } + /** - * FIXME: Call to this function is made whenever we have a get request. - * Handler for DHT GET messages from the client. + * Task that looks at the 'retry_heap' and transmits all of the requests + * on the heap that are ready for transmission. Then re-schedules + * itself (unless the heap is empty). * - * @param cls closure for the service - * @param client the client we received this message from - * @param message the actual message received + * @param cls unused + * @param tc scheduler context */ static void -handle_dht_local_get (void *cls, struct GNUNET_SERVER_Client *client, - const struct GNUNET_MessageHeader *message) +transmit_next_request_task (void *cls, + const struct GNUNET_SCHEDULER_TaskContext *tc) { - struct GNUNET_DHT_ClientGetMessage *get_msg; - struct GNUNET_PeerIdentity *get_path; - struct GNUNET_PeerIdentity *my_identity; - unsigned int get_path_length; - uint16_t size; - - size = ntohs (message->size); - if (size < sizeof (struct GNUNET_DHT_ClientGetMessage)) - { - GNUNET_break (0); - GNUNET_SERVER_receive_done (client, GNUNET_SYSERR); + struct ClientQueryRecord *cqr; + struct GNUNET_TIME_Relative delay; + + retry_task = GNUNET_SCHEDULER_NO_TASK; + if (0 != (tc->reason & GNUNET_SCHEDULER_REASON_SHUTDOWN)) return; + while (NULL != (cqr = GNUNET_CONTAINER_heap_remove_root (retry_heap))) + { + cqr->hnode = NULL; + delay = GNUNET_TIME_absolute_get_remaining (cqr->retry_time); + if (delay.rel_value_us > 0) + { + cqr->hnode = + GNUNET_CONTAINER_heap_insert (retry_heap, cqr, + cqr->retry_time.abs_value_us); + retry_task = + GNUNET_SCHEDULER_add_delayed (delay, &transmit_next_request_task, + NULL); + return; + } + transmit_request (cqr); + cqr->hnode = + GNUNET_CONTAINER_heap_insert (retry_heap, cqr, + cqr->retry_time.abs_value_us); } - - get_msg = (struct GNUNET_DHT_ClientGetMessage *) message; - - /* FIXME: Search locally? Why should we always search locally? - Current implementation of datacache needs to be modified. If found here, then - notify the requesting client. */ - - /* FIXME: Call GDS_NEIGHBOURS_handle_get - Here you need to remember the whole path because you need to travel that path - and reach back here with the result. So, you should send your own id, client - id, get path, get path length. You also need to add yourself to the get path. */ - my_identity = GDS_NEIGHBOURS_get_id(); - get_path = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - memcpy (get_path, &my_identity, sizeof (struct GNUNET_PeerIdentity)); - get_path_length = 1; - - /* FIXME: - * 1. Find some unique identifier for the client. - * 2. Also, I don't know the usage of block, replication and type. So, I - * am not sending the parameters now. */ - GDS_NEIGHBOURS_handle_get (my_identity, get_path, get_path_length, - &(get_msg->key), NULL, NULL, NULL); - } /** * Handler for PUT messages. + * * @param cls closure for the service * @param client the client we received this message from * @param message the actual message received @@ -355,10 +910,10 @@ static void handle_dht_local_put (void *cls, struct GNUNET_SERVER_Client *client, const struct GNUNET_MessageHeader *message) { - struct GNUNET_DHT_ClientPutMessage *put_msg; - struct GNUNET_DHT_ClientPutConfirmationMessage *conf; + const struct GNUNET_DHT_ClientPutMessage *put_msg; struct PendingMessage *pm; - uint16_t size; /* FIXME: When to use size_t and when uint16_t */ + struct GNUNET_DHT_ClientPutConfirmationMessage *conf; + uint16_t size; size = ntohs (message->size); if (size < sizeof (struct GNUNET_DHT_ClientPutMessage)) @@ -367,19 +922,32 @@ handle_dht_local_put (void *cls, struct GNUNET_SERVER_Client *client, GNUNET_SERVER_receive_done (client, GNUNET_SYSERR); return; } + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop + ("# PUT requests received from clients"), 1, + GNUNET_NO); + put_msg = (const struct GNUNET_DHT_ClientPutMessage *) message; + LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG, "R5N CLIENT-PUT %s\n", + GNUNET_h2s_full (&put_msg->key)); + /* give to local clients */ + LOG (GNUNET_ERROR_TYPE_DEBUG, + "Handling local PUT of %u-bytes for query %s\n", + size - sizeof (struct GNUNET_DHT_ClientPutMessage), + GNUNET_h2s (&put_msg->key)); - /* FIXME:Should we define put_msg as const? */ - put_msg = (struct GNUNET_DHT_ClientPutMessage *) message; - - /* store locally. FIXME: Is it secure to allow each peer to store the data? */ + GDS_CLIENTS_handle_reply (GNUNET_TIME_absolute_ntoh (put_msg->expiration), + &put_msg->key, 0, NULL, 0, NULL, + ntohl (put_msg->type), + size - sizeof (struct GNUNET_DHT_ClientPutMessage), + &put_msg[1]); + /* store locally */ GDS_DATACACHE_handle_put (GNUNET_TIME_absolute_ntoh (put_msg->expiration), &put_msg->key, 0, NULL, ntohl (put_msg->type), size - sizeof (struct GNUNET_DHT_ClientPutMessage), &put_msg[1]); - /* FIXME: Right now I have just kept all the fields from the old function. - It may be possible that most of them are not needed. Check and remove if - not needed. Usage of replication, options and type is still not clear. */ + /* FIXME: At the moment we don't use replication in x-vine. But keep it for + time being. Check all the fields again. */ GDS_NEIGHBOURS_handle_put (ntohl (put_msg->type), ntohl (put_msg->options), ntohl (put_msg->desired_replication_level), GNUNET_TIME_absolute_ntoh (put_msg->expiration), @@ -387,10 +955,19 @@ handle_dht_local_put (void *cls, struct GNUNET_SERVER_Client *client, &put_msg->key, 0, NULL, &put_msg[1], size - sizeof (struct GNUNET_DHT_ClientPutMessage), - NULL, NULL, NULL); + NULL, 0, NULL); + + GDS_CLIENTS_process_put (ntohl (put_msg->options), + ntohl (put_msg->type), + 0, + ntohl (put_msg->desired_replication_level), + 1, + GDS_NEIGHBOURS_get_id(), + GNUNET_TIME_absolute_ntoh (put_msg->expiration), + &put_msg->key, + &put_msg[1], + size - sizeof (struct GNUNET_DHT_ClientPutMessage)); - /* FIXME: Here we send back the confirmation before verifying if put was successful - or not. */ pm = GNUNET_malloc (sizeof (struct PendingMessage) + sizeof (struct GNUNET_DHT_ClientPutConfirmationMessage)); conf = (struct GNUNET_DHT_ClientPutConfirmationMessage *) &pm[1]; @@ -403,6 +980,334 @@ handle_dht_local_put (void *cls, struct GNUNET_SERVER_Client *client, GNUNET_SERVER_receive_done (client, GNUNET_OK); } + +/** + * Handler for DHT GET messages from the client. + * + * @param cls closure for the service + * @param client the client we received this message from + * @param message the actual message received + */ +static void +handle_dht_local_get (void *cls, struct GNUNET_SERVER_Client *client, + const struct GNUNET_MessageHeader *message) +{ + const struct GNUNET_DHT_ClientGetMessage *get; + struct ClientQueryRecord *cqr; + size_t xquery_size; + const char *xquery; + uint16_t size; + + size = ntohs (message->size); + if (size < sizeof (struct GNUNET_DHT_ClientGetMessage)) + { + GNUNET_break (0); + GNUNET_SERVER_receive_done (client, GNUNET_SYSERR); + return; + } + xquery_size = size - sizeof (struct GNUNET_DHT_ClientGetMessage); + get = (const struct GNUNET_DHT_ClientGetMessage *) message; + xquery = (const char *) &get[1]; + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop + ("# GET requests received from clients"), 1, + GNUNET_NO); + LOG (GNUNET_ERROR_TYPE_DEBUG, + "Received GET request for %s from local client %p, xq: %.*s\n", + GNUNET_h2s (&get->key), client, xquery_size, xquery); + + LOG_TRAFFIC (GNUNET_ERROR_TYPE_DEBUG, "R5N CLIENT-GET %s\n", + GNUNET_h2s_full (&get->key)); + + + cqr = GNUNET_malloc (sizeof (struct ClientQueryRecord) + xquery_size); + cqr->key = get->key; + cqr->client = find_active_client (client); + cqr->xquery = (void *) &cqr[1]; + memcpy (&cqr[1], xquery, xquery_size); + cqr->hnode = GNUNET_CONTAINER_heap_insert (retry_heap, cqr, 0); + cqr->retry_frequency = GNUNET_TIME_UNIT_SECONDS; + cqr->retry_time = GNUNET_TIME_absolute_get (); + cqr->unique_id = get->unique_id; + cqr->xquery_size = xquery_size; + cqr->replication = ntohl (get->desired_replication_level); + cqr->msg_options = ntohl (get->options); + cqr->type = ntohl (get->type); + // FIXME use cqr->key, set multihashmap create to GNUNET_YES + GNUNET_CONTAINER_multihashmap_put (forward_map, &get->key, cqr, + GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE); + GDS_CLIENTS_process_get (ntohl (get->options), + ntohl (get->type), + 0, + ntohl (get->desired_replication_level), + 1, + GDS_NEIGHBOURS_get_id(), + &get->key); + /* start remote requests */ + if (GNUNET_SCHEDULER_NO_TASK != retry_task) + GNUNET_SCHEDULER_cancel (retry_task); + retry_task = GNUNET_SCHEDULER_add_now (&transmit_next_request_task, NULL); + /* perform local lookup */ + GDS_DATACACHE_handle_get (&get->key, cqr->type, cqr->xquery, xquery_size, + NULL, 0); + GNUNET_SERVER_receive_done (client, GNUNET_OK); +} + + +/** + * Closure for 'find_by_unique_id'. + */ +struct FindByUniqueIdContext +{ + /** + * Where to store the result, if found. + */ + struct ClientQueryRecord *cqr; + + uint64_t unique_id; +}; + + +/** + * Function called for each existing DHT record for the given + * query. Checks if it matches the UID given in the closure + * and if so returns the entry as a result. + * + * @param cls the search context + * @param key query for the lookup (not used) + * @param value the 'struct ClientQueryRecord' + * @return GNUNET_YES to continue iteration (result not yet found) + */ +static int +find_by_unique_id (void *cls, + const struct GNUNET_HashCode *key, + void *value) +{ + struct FindByUniqueIdContext *fui_ctx = cls; + struct ClientQueryRecord *cqr = value; + + if (cqr->unique_id != fui_ctx->unique_id) + return GNUNET_YES; + fui_ctx->cqr = cqr; + return GNUNET_NO; +} + + +/** + * Handler for "GET result seen" messages from the client. + * + * @param cls closure for the service + * @param client the client we received this message from + * @param message the actual message received + */ +static void +handle_dht_local_get_result_seen (void *cls, struct GNUNET_SERVER_Client *client, + const struct GNUNET_MessageHeader *message) +{ + const struct GNUNET_DHT_ClientGetResultSeenMessage *seen; + uint16_t size; + unsigned int hash_count; + unsigned int old_count; + const struct GNUNET_HashCode *hc; + struct FindByUniqueIdContext fui_ctx; + struct ClientQueryRecord *cqr; + + size = ntohs (message->size); + if (size < sizeof (struct GNUNET_DHT_ClientGetResultSeenMessage)) + { + GNUNET_break (0); + GNUNET_SERVER_receive_done (client, GNUNET_SYSERR); + return; + } + seen = (const struct GNUNET_DHT_ClientGetResultSeenMessage *) message; + hash_count = (size - sizeof (struct GNUNET_DHT_ClientGetResultSeenMessage)) / sizeof (struct GNUNET_HashCode); + if (size != sizeof (struct GNUNET_DHT_ClientGetResultSeenMessage) + hash_count * sizeof (struct GNUNET_HashCode)) + { + GNUNET_break (0); + GNUNET_SERVER_receive_done (client, GNUNET_SYSERR); + return; + } + hc = (const struct GNUNET_HashCode*) &seen[1]; + fui_ctx.unique_id = seen->unique_id; + fui_ctx.cqr = NULL; + GNUNET_CONTAINER_multihashmap_get_multiple (forward_map, + &seen->key, + &find_by_unique_id, + &fui_ctx); + if (NULL == (cqr = fui_ctx.cqr)) + { + GNUNET_break (0); + GNUNET_SERVER_receive_done (client, GNUNET_SYSERR); + return; + } + /* finally, update 'seen' list */ + old_count = cqr->seen_replies_count; + GNUNET_array_grow (cqr->seen_replies, + cqr->seen_replies_count, + cqr->seen_replies_count + hash_count); + memcpy (&cqr->seen_replies[old_count], + hc, + sizeof (struct GNUNET_HashCode) * hash_count); +} + + +/** + * Closure for 'remove_by_unique_id'. + */ +struct RemoveByUniqueIdContext +{ + /** + * Client that issued the removal request. + */ + struct ClientList *client; + + /** + * Unique ID of the request. + */ + uint64_t unique_id; +}; + + +/** + * Iterator over hash map entries that frees all entries + * that match the given client and unique ID. + * + * @param cls unique ID and client to search for in source routes + * @param key current key code + * @param value value in the hash map, a ClientQueryRecord + * @return GNUNET_YES (we should continue to iterate) + */ +static int +remove_by_unique_id (void *cls, const struct GNUNET_HashCode * key, void *value) +{ + const struct RemoveByUniqueIdContext *ctx = cls; + struct ClientQueryRecord *record = value; + + if (record->unique_id != ctx->unique_id) + return GNUNET_YES; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Removing client %p's record for key %s (by unique id)\n", + ctx->client->client_handle, GNUNET_h2s (key)); + return remove_client_records (ctx->client, key, record); +} + + +/** + * Handler for any generic DHT stop messages, calls the appropriate handler + * depending on message type (if processed locally) + * + * @param cls closure for the service + * @param client the client we received this message from + * @param message the actual message received + * + */ +static void +handle_dht_local_get_stop (void *cls, struct GNUNET_SERVER_Client *client, + const struct GNUNET_MessageHeader *message) +{ + const struct GNUNET_DHT_ClientGetStopMessage *dht_stop_msg = + (const struct GNUNET_DHT_ClientGetStopMessage *) message; + struct RemoveByUniqueIdContext ctx; + + GNUNET_STATISTICS_update (GDS_stats, + gettext_noop + ("# GET STOP requests received from clients"), 1, + GNUNET_NO); + LOG (GNUNET_ERROR_TYPE_DEBUG, + "Received GET STOP request for %s from local client %p\n", + client, GNUNET_h2s (&dht_stop_msg->key)); + ctx.client = find_active_client (client); + ctx.unique_id = dht_stop_msg->unique_id; + GNUNET_CONTAINER_multihashmap_get_multiple (forward_map, &dht_stop_msg->key, + &remove_by_unique_id, &ctx); + GNUNET_SERVER_receive_done (client, GNUNET_OK); +} + + +/** + * Handler for monitor start messages + * + * @param cls closure for the service + * @param client the client we received this message from + * @param message the actual message received + * + */ +static void +handle_dht_local_monitor (void *cls, struct GNUNET_SERVER_Client *client, + const struct GNUNET_MessageHeader *message) +{ + struct ClientMonitorRecord *r; + const struct GNUNET_DHT_MonitorStartStopMessage *msg; + + msg = (struct GNUNET_DHT_MonitorStartStopMessage *) message; + r = GNUNET_new (struct ClientMonitorRecord); + + r->client = find_active_client(client); + r->type = ntohl(msg->type); + r->get = ntohs(msg->get); + r->get_resp = ntohs(msg->get_resp); + r->put = ntohs(msg->put); + if (0 == ntohs(msg->filter_key)) + r->key = NULL; + else + { + r->key = GNUNET_new (struct GNUNET_HashCode); + memcpy (r->key, &msg->key, sizeof (struct GNUNET_HashCode)); + } + GNUNET_CONTAINER_DLL_insert (monitor_head, monitor_tail, r); + GNUNET_SERVER_receive_done (client, GNUNET_OK); +} + + +/** + * Handler for monitor stop messages + * + * @param cls closure for the service + * @param client the client we received this message from + * @param message the actual message received + * + */ +static void +handle_dht_local_monitor_stop (void *cls, struct GNUNET_SERVER_Client *client, + const struct GNUNET_MessageHeader *message) +{ + struct ClientMonitorRecord *r; + const struct GNUNET_DHT_MonitorStartStopMessage *msg; + int keys_match; + + msg = (struct GNUNET_DHT_MonitorStartStopMessage *) message; + r = monitor_head; + + while (NULL != r) + { + if (NULL == r->key) + keys_match = (0 == ntohs(msg->filter_key)); + else + { + keys_match = (0 != ntohs(msg->filter_key) + && !memcmp(r->key, &msg->key, sizeof(struct GNUNET_HashCode))); + } + if (find_active_client(client) == r->client + && ntohl(msg->type) == r->type + && r->get == msg->get + && r->get_resp == msg->get_resp + && r->put == msg->put + && keys_match + ) + { + GNUNET_CONTAINER_DLL_remove (monitor_head, monitor_tail, r); + GNUNET_free_non_null (r->key); + GNUNET_free (r); + GNUNET_SERVER_receive_done (client, GNUNET_OK); + return; /* Delete only ONE entry */ + } + r = r->next; + } + + GNUNET_SERVER_receive_done (client, GNUNET_OK); +} + + /** * Functions with this signature are called whenever a client * is disconnected on the network level. @@ -415,26 +1320,46 @@ static void handle_client_disconnect (void *cls, struct GNUNET_SERVER_Client *client) { - /* You should maintain a list of client attached to this service. Then - search for the correct client and stop all its ongoing activites and - delete it from the list. */ -} + struct ClientList *pos; + struct PendingMessage *reply; + struct ClientMonitorRecord *monitor; + GNUNET_log (GNUNET_ERROR_TYPE_DEBUG, + "Local client %p disconnects\n", + client); + pos = find_active_client (client); + GNUNET_CONTAINER_DLL_remove (client_head, client_tail, pos); + if (pos->transmit_handle != NULL) + GNUNET_SERVER_notify_transmit_ready_cancel (pos->transmit_handle); + while (NULL != (reply = pos->pending_head)) + { + GNUNET_CONTAINER_DLL_remove (pos->pending_head, pos->pending_tail, reply); + GNUNET_free (reply); + } + monitor = monitor_head; + while (NULL != monitor) + { + if (monitor->client == pos) + { + struct ClientMonitorRecord *next; -/** - * Get result from neighbours file. - */ -void -GDS_CLIENTS_process_get_result() -{ - + GNUNET_free_non_null (monitor->key); + next = monitor->next; + GNUNET_CONTAINER_DLL_remove (monitor_head, monitor_tail, monitor); + GNUNET_free (monitor); + monitor = next; + } + else + monitor = monitor->next; + } + GNUNET_CONTAINER_multihashmap_iterate (forward_map, &remove_client_records, + pos); + GNUNET_free (pos); } + /** - * SUPU: Call to this function is made from gnunet-service-xdht.c - * Here we register handlers for each possible kind of message the service - * receives from the clients. * Initialize client subsystem. * * @param server the initialized server @@ -456,19 +1381,42 @@ GDS_CLIENTS_init (struct GNUNET_SERVER_Handle *server) {&handle_dht_local_monitor_stop, NULL, GNUNET_MESSAGE_TYPE_DHT_MONITOR_STOP, sizeof (struct GNUNET_DHT_MonitorStartStopMessage)}, + {&handle_dht_local_get_result_seen, NULL, + GNUNET_MESSAGE_TYPE_DHT_CLIENT_GET_RESULTS_KNOWN, 0}, {NULL, NULL, 0, 0} }; - + forward_map = GNUNET_CONTAINER_multihashmap_create (1024, GNUNET_NO); + retry_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN); GNUNET_SERVER_add_handlers (server, plugin_handlers); GNUNET_SERVER_disconnect_notify (server, &handle_client_disconnect, NULL); } + /** - * SUPU: Call made from gnunet-service-dht.c * Shutdown client subsystem. */ void GDS_CLIENTS_done () { - -} \ No newline at end of file + GNUNET_assert (client_head == NULL); + GNUNET_assert (client_tail == NULL); + if (GNUNET_SCHEDULER_NO_TASK != retry_task) + { + GNUNET_SCHEDULER_cancel (retry_task); + retry_task = GNUNET_SCHEDULER_NO_TASK; + } + if (NULL != retry_heap) + { + GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (retry_heap)); + GNUNET_CONTAINER_heap_destroy (retry_heap); + retry_heap = NULL; + } + if (NULL != forward_map) + { + GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (forward_map)); + GNUNET_CONTAINER_multihashmap_destroy (forward_map); + forward_map = NULL; + } +} + +/* end of gnunet-service-dht_clients.c */ diff --git a/src/dht/gnunet-service-xdht_clients.h b/src/dht/gnunet-service-xdht_clients.h index 828d2c08a..2aac7f2b0 100644 --- a/src/dht/gnunet-service-xdht_clients.h +++ b/src/dht/gnunet-service-xdht_clients.h @@ -21,10 +21,11 @@ /** * @file dht/gnunet-service-xdht_clients.h * @brief GNUnet DHT service's client management code - * @author Supriti Singh + * @author Christian Grothoff + * @author Nathan Evans */ -#ifndef GNUNET_SERVICE_XDHT_CLIENT_H -#define GNUNET_SERVICE_XDHT_CLIENT_H +#ifndef GNUNET_SERVICE_DHT_CLIENT_H +#define GNUNET_SERVICE_DHT_CLIENT_H #include "gnunet_util_lib.h" #include "gnunet_block_lib.h" @@ -36,17 +37,17 @@ * * @param expiration when will the reply expire * @param key the query this reply is for - * @param get_path_length number of peers in 'get_path' + * @param get_path_length number of peers in @a get_path * @param get_path path the reply took on get - * @param put_path_length number of peers in 'put_path' + * @param put_path_length number of peers in @a put_path * @param put_path path the reply took on put * @param type type of the reply - * @param data_size number of bytes in 'data' + * @param data_size number of bytes in @a data * @param data application payload data */ void GDS_CLIENTS_handle_reply (struct GNUNET_TIME_Absolute expiration, - const struct GNUNET_HashCode * key, + const struct GNUNET_HashCode *key, unsigned int get_path_length, const struct GNUNET_PeerIdentity *get_path, unsigned int put_path_length, @@ -74,7 +75,8 @@ GDS_CLIENTS_process_get (uint32_t options, uint32_t desired_replication_level, unsigned int path_length, const struct GNUNET_PeerIdentity *path, - const struct GNUNET_HashCode * key); + const struct GNUNET_HashCode *key); + /** * Check if some client is monitoring GET RESP messages and notify @@ -82,13 +84,13 @@ GDS_CLIENTS_process_get (uint32_t options, * * @param type The type of data in the result. * @param get_path Peers on GET path (or NULL if not recorded). - * @param get_path_length number of entries in get_path. + * @param get_path_length number of entries in @a get_path. * @param put_path peers on the PUT path (or NULL if not recorded). - * @param put_path_length number of entries in get_path. + * @param put_path_length number of entries in @a get_path. * @param exp Expiration time of the data. - * @param key Key of the data. + * @param key Key of the @a data. * @param data Pointer to the result data. - * @param size Number of bytes in data. + * @param size Number of bytes in @a data. */ void GDS_CLIENTS_process_get_resp (enum GNUNET_BLOCK_Type type, @@ -101,6 +103,7 @@ GDS_CLIENTS_process_get_resp (enum GNUNET_BLOCK_Type type, const void *data, size_t size); + /** * Check if some client is monitoring PUT messages and notify * them in that case. @@ -128,12 +131,6 @@ GDS_CLIENTS_process_put (uint32_t options, const void *data, size_t size); -/** - * - */ -void -GDS_CLIENTS_process_get_result(); - /** * Initialize client subsystem. * diff --git a/src/dht/gnunet-service-xdht_datacache.c b/src/dht/gnunet-service-xdht_datacache.c index bdc247690..77673cf66 100644 --- a/src/dht/gnunet-service-xdht_datacache.c +++ b/src/dht/gnunet-service-xdht_datacache.c @@ -61,7 +61,7 @@ GDS_DATACACHE_handle_put (struct GNUNET_TIME_Absolute expiration, const void *data) { int r; - + if (NULL == datacache) { GNUNET_log (GNUNET_ERROR_TYPE_WARNING, diff --git a/src/dht/gnunet-service-xdht_neighbours.c b/src/dht/gnunet-service-xdht_neighbours.c index 4c290895b..aa8f70d12 100644 --- a/src/dht/gnunet-service-xdht_neighbours.c +++ b/src/dht/gnunet-service-xdht_neighbours.c @@ -57,7 +57,15 @@ * them as they come. * 3. Everywhere you are storing yourself as the first element in the trail. * It is obviously taking too much space. Try to remove it and think of something - * better. */ + * better. + 4. Choose the correct interval to send finger and verify message. + 5. Do we need expiration time for trail setup and all other messages? TTL + 6. In case of trail setup after TTL, we should again send the request but + * through a different route. How do we remeber each time which friend we + * chose last time for the trail setup. We will need a data structure where we + * add entry in finger table add and when setup is done remove it. + * 7. I have not added any authentication on messages exachanged between peers. + * Only when basic put/get is correct I will add it. */ /** * Maximum possible fingers of a peer. @@ -85,18 +93,9 @@ #define GET_TIMEOUT GNUNET_TIME_relative_multiply(GNUNET_TIME_UNIT_MINUTES, 2) /** - * FIXME: Use this variable. Should it be moved to routing.c - * Threshold on routing table entries for a peer. + * Maximum number of trails allowed to go through a friend. */ -#define ROUTING_TABLE_THRESHOLD 64 - -/** - * FIXME: Use this variable. When adding an entry in finger table, check - * this threshold value. At the moment, its just a random value. Also, - * implement teardown feature from the paper. - * Threshold on number of peers in a trail length - */ -#define TRAIL_LENGTH_THRESHOLD 64 +#define LINK_THRESHOLD 64 GNUNET_NETWORK_STRUCT_BEGIN @@ -208,7 +207,7 @@ struct PeerGetResultMessage * The key of the corresponding GET request. */ struct GNUNET_HashCode key; - + /* put path (if tracked) */ /* get path (if tracked) */ @@ -246,8 +245,12 @@ struct PeerGetMessage /** * */ - enum current_destination_type dest_type; + enum current_destination_type current_dest_type; + /** + * Unique identifier of the request. + */ + uint64_t request_id; /** * When does the content expire? */ @@ -526,6 +529,11 @@ struct FriendInfo */ struct GNUNET_PeerIdentity id; + /** + * Number of trail of which this friend is the first hop. + */ + unsigned int trail_links; + /** * Count of outstanding messages for this friend. */ @@ -631,11 +639,6 @@ static struct GNUNET_CONTAINER_MultiPeerMap *friend_peermap; */ static struct GNUNET_CONTAINER_MultiPeerMap *finger_peermap; -/** - * Handle to ATS. - */ -static struct GNUNET_ATS_PerformanceHandle *atsAPI; - /** * Handle to CORE. */ @@ -806,8 +809,12 @@ GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity *source_peer, tsm->trail_length = htonl (trail_length); tsm->finger_map_index = htonl (finger_map_index); - peer_list = (struct GNUNET_PeerIdentity *) &tsm[1]; - memcpy (peer_list, trail_peer_list, trail_length * sizeof(struct GNUNET_PeerIdentity)); + if (trail_peer_list != NULL) + { + 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); target_friend->pending_count++; process_friend_queue (target_friend); @@ -822,8 +829,7 @@ GDS_NEIGHBOURS_send_trail_setup (struct GNUNET_PeerIdentity *source_peer, * @param target_friend Friend to which this message should be forwarded. * @param trail_length Numbers of peers in the trail. * @param trail_peer_list Peers which are part of the trail from source to destination. - * @param current_trail_index Index in the trial list at which receiving peer should - * read the next element. + * @param current_trail_index Index at which sender of this message is located. * @param finger_map_index Index in finger peer map */ void @@ -1059,6 +1065,12 @@ GDS_NEIGHBOURS_send_notify_new_successor (struct GNUNET_PeerIdentity *source_pee /** + * FIXME: Optimizaiton Once the basic code is running. Add the optimization + * where you check if the threshold on number of links that should go through + * a particular friend has crossed. If yes then again choose a different + * friend. Important that the new friend chosen should be different. How to + * ensure this? This is an important optimization as without this one x-vine + * is actually not a sybil tolerant DHT. * Randomly choose one of your friends from the friends_peer map * @return Friend */ @@ -1073,14 +1085,9 @@ select_random_friend() struct FriendInfo *friend; current_size = GNUNET_CONTAINER_multipeermap_size (friend_peermap); - - /* Element stored at this index in friend_peermap should be selected friend. */ index = GNUNET_CRYPTO_random_permute (GNUNET_CRYPTO_QUALITY_WEAK, current_size); - - /* Create an iterator for friend_peermap. */ iter = GNUNET_CONTAINER_multipeermap_iterator_create (friend_peermap); - - /* Set the position of iterator to index. */ + while(j < (*index)) { if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,NULL,NULL)) @@ -1091,13 +1098,10 @@ select_random_friend() return NULL; } - if(GNUNET_YES == GNUNET_CONTAINER_multipeermap_iterator_next (iter,&key_ret,(const void **)&friend)) - { return friend; - } - - return NULL; + else + return NULL; } @@ -1112,9 +1116,7 @@ compute_finger_identity() uint64_t *finger_identity64; finger_identity64 = GNUNET_malloc (sizeof (uint64_t)); - memcpy (&my_id64, &my_identity, sizeof (uint64_t)); - /*FIXME: Do we need a mod finger = ((my_id + pow(2, finger_index)) mod (pow (2, MAX_FINGERS))*/ *finger_identity64 = (my_id64 + (unsigned long) pow (2,current_finger_index)); @@ -1162,6 +1164,7 @@ send_verify_successor_message (void *cls, unsigned int finger_index; unsigned int i; int flag = 0; + finger_iter = GNUNET_CONTAINER_multipeermap_iterator_create (finger_peermap); for (finger_index = 0; finger_index < GNUNET_CONTAINER_multipeermap_size (finger_peermap); finger_index++) { @@ -1181,7 +1184,7 @@ send_verify_successor_message (void *cls, goto send_new_request; peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * finger->trail_length); - + struct TrailPeerList *iterate; iterate = finger->head; i = 0; @@ -1193,10 +1196,11 @@ send_verify_successor_message (void *cls, } next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - memcpy (next_hop, &peer_list[1], sizeof (struct GNUNET_PeerIdentity)); + memcpy (next_hop, &peer_list[0], sizeof (struct GNUNET_PeerIdentity)); target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); - finger_trail_current_index = 2; - + finger_trail_current_index = 0; + + GDS_NEIGHBOURS_send_verify_successor (&my_identity, &(finger->finger_identity), target_friend, @@ -1233,14 +1237,11 @@ send_find_finger_trail_message (void *cls, { struct FriendInfo *target_friend; struct GNUNET_TIME_Relative next_send_time; - struct GNUNET_PeerIdentity *peer_list; uint64_t *finger_identity; unsigned int finger_map_index; if (1 == current_finger_index) { - /* We have started the process to find the successor. We should search - for our predecessor. */ finger_identity = compute_predecessor_identity(); goto select_friend; } @@ -1250,27 +1251,20 @@ send_find_finger_trail_message (void *cls, } select_friend: + /* FIXME: Here should we choose randomly or not. */ target_friend = select_random_friend(); - finger_map_index = current_finger_index; current_finger_index = ( current_finger_index + 1) % MAX_FINGERS; - /* We found a friend.*/ if(NULL != target_friend) { - /* Add yourself and selected friend in the trail list. */ - unsigned int trail_length = 2; - peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length); - memcpy (&peer_list[0], &(my_identity), sizeof (struct GNUNET_PeerIdentity)); - memcpy (&peer_list[1], &(target_friend->id), sizeof (struct GNUNET_PeerIdentity)); - GDS_NEIGHBOURS_send_trail_setup (&my_identity, *finger_identity, &(target_friend->id), - target_friend, trail_length, peer_list, + target_friend, 0, NULL, finger_map_index, FRIEND); } - /* FIXME: Should we be using current_finger_index to generate random interval.*/ + /* FIXME: How to decide the correct interval? */ next_send_time.rel_value_us = DHT_MINIMUM_FIND_FINGER_TRAIL_INTERVAL.rel_value_us + GNUNET_CRYPTO_random_u64 (GNUNET_CRYPTO_QUALITY_WEAK, @@ -1396,26 +1390,91 @@ core_init (void *cls, { my_identity = *identity; +#if 0 + /* SUPU TEST CODE */ + struct GNUNET_PeerIdentity *print_peer; + print_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); + memcpy (print_peer, &my_identity, sizeof (struct GNUNET_PeerIdentity)); + FPRINTF (stderr,_("\nSUPU %s, %s, %d,my_identity = %s"), + __FILE__, __func__,__LINE__, GNUNET_i2s (print_peer)); + /* SUPU TEST CODE ENDS */ +#endif } +/** + * + * @param destination_peer + * @param existing_trail + * @param trail_length + * @return + */ +static struct GNUNET_PeerIdentity * +invert_trail_list (struct GNUNET_PeerIdentity *destination_peer, + struct GNUNET_PeerIdentity *existing_trail, + unsigned int trail_length) +{ + int i; + int j; + struct GNUNET_PeerIdentity *new_trail; + + j = 0; + new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * trail_length); + + if (trail_length > 1) + { + i = trail_length - 2; + while (i >= 0 ) + { + memcpy( &new_trail[j], &existing_trail[i], sizeof (struct GNUNET_PeerIdentity)); + i--; + j++; + } + } + memcpy (&new_trail[j], destination_peer, sizeof(struct GNUNET_PeerIdentity)); + + return new_trail; +} +/** + * + * @param existing_finger + * @param new_finger + * @return + */ +#if 0 +static int +compare_finger_identity (struct GNUNET_PeerIdentity *existing_finger, + struct GNUNET_PeerIdentity *new_finger) +{ + int ret; + ret = (existing_finger > new_finger) ? 1 : + (existing_finger == new_finger) ? 0 : -1; + return ret; +} +#endif /** - * FIXME: When we add a successor or predecessor should we check the entry in - * finger map index. If we don't replace the old entry then should we notify - * peer which think it is our predecessor or successor. Or will send verify - * successor message will handle this case on its own. - * * 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. + * FIXME: Not sure of the logic to find the correct predecessor. + * Given two finger identities, find the closest predecessor. + * @param existing_predecessor + * @param new_predecessor + * @return + */ +#if 0 +static int +compare_predecessor(struct GNUNET_PeerIdentity *existing_predecessor, + struct GNUNET_PeerIdentity *new_predecessor) +{ + int ret; + ret = (existing_predecessor < new_predecessor) ? 1 : + (existing_predecessor == new_predecessor) ? 0 : -1; + return ret; +} +#endif + +/* * Add an entry in finger table. * Add an entry into finger table * @param finger_identity Peer identity of finger @@ -1430,14 +1489,17 @@ void finger_table_add (struct GNUNET_PeerIdentity *finger_identity, unsigned int finger_map_index) { struct FingerInfo *new_finger_entry; + int i; +#if 0 struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter; struct GNUNET_PeerIdentity key_ret; struct FingerInfo *existing_finger; int finger_index; int i; + 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, @@ -1449,40 +1511,47 @@ void finger_table_add (struct GNUNET_PeerIdentity *finger_identity, /* Check if the finger entry are same. */ if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(existing_finger->finger_identity),finger_identity)) { - /* Compare the trail length. */ - if ((trail_length == existing_finger->trail_length)|| - (trail_length > existing_finger->trail_length)) + FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__); + goto add_new_entry; + } + else + { + /* FIXME: here you should have something better to check which finger + is closer one. */ + int ret; + if (finger_map_index == 1) { - return; + FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__); + ret = compare_predecessor (&(existing_finger->finger_identity), + finger_identity); } - else if (trail_length < existing_finger->trail_length) + else { - /* FIXME: As an optimization, when you add limit on trail length - going through a particular friend, then check if the friend to - reach the two trails are same or not. If not then choose one - whose threshold value has not yet reached. Also, think about - redundant routing, where you want to keep multiple paths - to reach to the same finger. In that case you should allow multiple - entries with same finger identity. */ - if ( GNUNET_YES == GNUNET_CONTAINER_multipeermap_remove (finger_peermap, - &(existing_finger->finger_identity), - existing_finger)) - { - goto add_new_entry; - } + FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__); + ret = compare_finger_identity (&(existing_finger->finger_identity), + finger_identity); + } + if (ret > 0) + { + FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__); + GNUNET_assert (GNUNET_YES == + GNUNET_CONTAINER_multipeermap_remove (finger_peermap, + &(existing_finger->finger_identity), + existing_finger)); + goto add_new_entry; + } + else + { + FPRINTF (stderr,_("\nSUPU %s, %s, %d"), __FILE__, __func__,__LINE__); + return; } - } - else - { - /* FIXME: Here you are if you got different finger identity then one - you already have at that index. Then you should choose the - one which is closest. */ } } } } - + add_new_entry: +#endif new_finger_entry = GNUNET_malloc (sizeof (struct FingerInfo)); memcpy (&(new_finger_entry->finger_identity), finger_identity, sizeof (struct GNUNET_PeerIdentity)); @@ -1503,12 +1572,14 @@ void finger_table_add (struct GNUNET_PeerIdentity *finger_identity, new_finger_entry->trail_length = trail_length; /* FIXME: Here we are keeping multiple hashmap option so that there are - multiple routes to reach to same finger, redundant routing. */ + multiple routes to reach to same finger, redundant routing. + * Also same peers could be our fingers for different finger map index */ GNUNET_assert (GNUNET_OK == GNUNET_CONTAINER_multipeermap_put (finger_peermap, &(new_finger_entry->finger_identity), new_finger_entry, - GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE)); + GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE)); /* Fixme: change to multiple */ + if (1 == GNUNET_CONTAINER_multipeermap_size (finger_peermap) && (new_finger_entry->finger_map_index!= 1)) @@ -1688,7 +1759,7 @@ find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination, struct TrailPeerList *iterator; iterator = GNUNET_malloc (sizeof (struct TrailPeerList)); finger = successor->data; - iterator = finger->head->next; + iterator = finger->head; next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); memcpy (next_hop, &(iterator->peer), sizeof (struct GNUNET_PeerIdentity)); memcpy (current_destination, &(finger->finger_identity), sizeof (struct GNUNET_PeerIdentity)); @@ -1701,37 +1772,34 @@ find_successor (uint64_t value, struct GNUNET_PeerIdentity *current_destination, } } -#if 0 -static void -replicate_put() -{ - /* In this function, you should find 'r' (r = desired replication level) successors - and send put message to all of these r successors. Now, I really don't know - if in case of node failure it will be able to find data. Or if we start with - a random peer id, do we even reach to correct successor ever in case of - get. */ -} -#endif /** - * - * @param source_peer - * @param get_path - * @param get_path_length - * @param key + * FIXME: + * 1. Do we have an expiration time for get request? Yes but I don't know its + * use case and how to handle it + * Send a get message to selected target friend. If target friend in NULL, + * then search for a target friend. + * @param request_id Unique ID identifying this request + * @param source_peer Peer which started get request + * @param get_peer_path Peer list to reach to final destination which contains the data. + * @param get_path_length Total numbers of peer in get_path + * @param key Key key for the content + * @param target_peer Next peer to forward the message to. + * @param current_destination Peer which will get this message. + * @param current_dest_type Type of current destination can be either FRIEND or FINGER */ void GDS_NEIGHBOURS_handle_get (struct GNUNET_PeerIdentity *source_peer, - struct GNUNET_PeerIdentity *get_path, + struct GNUNET_PeerIdentity *get_peer_path, unsigned int get_path_length, struct GNUNET_HashCode *key, struct GNUNET_PeerIdentity *target_peer, struct GNUNET_PeerIdentity *current_destination, - enum current_destination_type *type) + enum current_destination_type *current_dest_type) { - struct PeerGetMessage *get_msg; + struct PeerGetMessage *get_request; struct P2PPendingMessage *pending; - struct GNUNET_PeerIdentity *gp; + struct GNUNET_PeerIdentity *get_path; struct FriendInfo *target_friend; uint64_t key_value; size_t msize; @@ -1747,27 +1815,30 @@ GDS_NEIGHBOURS_handle_get (struct GNUNET_PeerIdentity *source_peer, memcpy (&key_value, key, sizeof (uint64_t)); + /* FIXME: Is this correct comparison? */ if (NULL == target_peer) { /* This is the first call made from client file. */ struct GNUNET_PeerIdentity *next_hop; - next_hop = find_successor (key_value, current_destination, type); + next_hop = find_successor (key_value, current_destination, current_dest_type); - if (*type == MY_ID) + if (*current_dest_type == MY_ID) { struct GNUNET_PeerIdentity *destination_peer; - int current_path_index; - - /* FIXME: You enter in this part of code only if the call is made from the - client file. And in client file you already have done the datacache_get. - So, ideally you don't need it. Remove it after checking. */ - if (get_path_length != 1) - current_path_index = get_path_length - 2; + get_path = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); + memcpy (get_path, &my_identity, sizeof (struct GNUNET_PeerIdentity)); + get_path_length = 1; destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); memcpy (destination_peer, source_peer, sizeof (struct GNUNET_PeerIdentity)); - /* I am the final destination, then call GDS_NEIGHBOURS_send_get_result.*/ + /* FIXME: We enter in this part of code only when this is our first + call from client file. In client file we already have done datacache_get + and if we already have the result. So, ideally code should never reach + here. Remove it after verifying. */ + /* FIXME: Call datacache_get but remove after verified above thing. */ GDS_NEIGHBOURS_send_get_result (&my_identity,get_path, get_path_length, - destination_peer, current_path_index); + key,destination_peer, 0, + NULL,0,NULL); + return; } else @@ -1782,18 +1853,18 @@ GDS_NEIGHBOURS_handle_get (struct GNUNET_PeerIdentity *source_peer, pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); pending->importance = 0; /* FIXME */ /* FIXME: Do we have an expiration time for get request */ - get_msg = (struct PeerGetMessage *) &pending[1]; - pending->msg = &get_msg->header; - get_msg->header.size = htons (msize); - get_msg->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET); - get_msg->get_path_length = htonl (get_path_length); - get_msg->key = *key; - memcpy (&(get_msg->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity)); - memcpy (&(get_msg->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity)); - get_msg->dest_type = htonl (*type); - - gp = (struct GNUNET_PeerIdentity *) &get_msg[1]; - memcpy (gp, get_path, get_path_length * sizeof (struct GNUNET_PeerIdentity)); + get_request = (struct PeerGetMessage *) &pending[1]; + pending->msg = &get_request->header; + get_request->header.size = htons (msize); + get_request->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET); + get_request->get_path_length = htonl (get_path_length); + get_request->key = *key; + + memcpy (&(get_request->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity)); + memcpy (&(get_request->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity)); + get_request->current_dest_type = htonl (*current_dest_type); + get_path = (struct GNUNET_PeerIdentity *) &get_request[1]; + memcpy (get_path, get_peer_path, get_path_length * sizeof (struct GNUNET_PeerIdentity)); GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); target_friend->pending_count++; process_friend_queue (target_friend); @@ -1826,12 +1897,12 @@ GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type, uint32_t desired_replication_level, struct GNUNET_TIME_Absolute expiration_time, uint32_t hop_count, - struct GNUNET_HashCode *key, + const struct GNUNET_HashCode *key, unsigned int put_path_length, struct GNUNET_PeerIdentity *put_path, const void *data, size_t data_size, struct GNUNET_PeerIdentity *current_destination, - enum current_destination_type *dest_type, + enum current_destination_type dest_type, struct GNUNET_PeerIdentity *target_peer) { struct PeerPutMessage *ppm; @@ -1857,14 +1928,18 @@ GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type, } memcpy (&key_value, key, sizeof (uint64_t)); + struct GNUNET_PeerIdentity *current_dest; + current_dest = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); if (target_peer == NULL) { /* This is the first time the call has been made from handle_dht_local_put. So, you need to search for the next peer to send this message to. */ struct GNUNET_PeerIdentity *next_hop; - next_hop = find_successor (key_value, current_destination, dest_type); + + next_hop = find_successor (key_value, current_dest, &dest_type); + - if (*dest_type == MY_ID) + if (dest_type == MY_ID) { /* FIXME: How do we handle different block types? */ /* FIXME: Here depending on the replication level choose 'r' successors @@ -1896,8 +1971,11 @@ GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type, ppm->desired_replication_level = htonl (desired_replication_level); ppm->put_path_length = htonl (put_path_length); ppm->expiration_time = GNUNET_TIME_absolute_hton (expiration_time); - memcpy (&(ppm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity)); - ppm->current_destination_type = htonl (*dest_type); + if (current_destination != NULL) + memcpy (&(ppm->current_destination), current_destination, sizeof (struct GNUNET_PeerIdentity)); + else + memcpy (&(ppm->current_destination), current_dest, sizeof (struct GNUNET_PeerIdentity)); + ppm->current_destination_type = htonl (dest_type); ppm->key = *key; pp = (struct GNUNET_PeerIdentity *) &ppm[1]; @@ -1911,48 +1989,145 @@ GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type, /** - * + * Send get result back to requesting client. * @param source_peer * @param get_path + * @param target_friend * @param get_path_length + * @param key * @param destination_peer + * @param current_path_index + * @param data + * @param data_size */ void GDS_NEIGHBOURS_send_get_result (struct GNUNET_PeerIdentity *source_peer, struct GNUNET_PeerIdentity *get_path, unsigned int get_path_length, + struct GNUNET_HashCode *key, struct GNUNET_PeerIdentity *destination_peer, - unsigned int current_path_index) + unsigned int current_path_index, + const void *data, size_t data_size, + struct GNUNET_PeerIdentity *next_hop) { - /* Add get_result into pending message and send the data to target friend. */ -#if 0 + /* Add get_result into pending message and send the data to target friend. + make a call GDS_CLIENTS_process_get_result() with all the fields. */ struct PeerGetResultMessage *get_result; + struct GNUNET_PeerIdentity *get_result_path; struct P2PPendingMessage *pending; + struct FriendInfo *target_friend; size_t msize; - msize = (get_path_length * sizeof (struct GNUNET_PeerIdentity)) + - sizeof (struct PeerGetResultMessage); - + msize = get_path_length * sizeof (struct GNUNET_PeerIdentity) + data_size + + sizeof (struct PeerPutMessage); + if (msize >= GNUNET_SERVER_MAX_MESSAGE_SIZE) { GNUNET_break (0); return; } -#endif + pending = GNUNET_malloc (sizeof (struct P2PPendingMessage) + msize); + pending->importance = 0; /* FIXME */ + /* FIXME: Should we add an expiration time like in put message. */ + get_result = (struct PeerGetResultMessage *)&pending[1]; + pending->msg = &get_result->header; + get_result->header.size = htons (msize); + get_result->header.type = htons (GNUNET_MESSAGE_TYPE_DHT_P2P_GET_RESULT); + memcpy (&(get_result->source_peer), source_peer, sizeof (struct GNUNET_PeerIdentity)); + memcpy (&(get_result->destination_peer), destination_peer, sizeof (struct GNUNET_PeerIdentity)); + get_result->current_path_index = current_path_index; + get_result->key = *key; + + get_result_path = (struct GNUNET_PeerIdentity *)&get_result[1]; + memcpy (get_result_path, get_path, + sizeof (struct GNUNET_PeerIdentity) * get_path_length); + memcpy (&get_result_path[get_path_length], data, data_size); + + target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); + GNUNET_CONTAINER_DLL_insert_tail (target_friend->head, target_friend->tail, pending); + target_friend->pending_count++; + process_friend_queue (target_friend); } /** * + * @param cls + * @param peer + * @param message * @return */ static int -handle_dht_p2p_get_result () +handle_dht_p2p_get_result (void *cls, const struct GNUNET_PeerIdentity *peer, + const struct GNUNET_MessageHeader *message) { /* If you are the source, go back to the client file and there search for the requesting client and send back the result. */ - return GNUNET_YES; + struct PeerGetResultMessage *get_result; + struct GNUNET_PeerIdentity *get_path; + void *payload; + size_t payload_size; + size_t msize; + unsigned int getlen; + int current_path_index; + + msize = ntohs (message->size); + if (msize < sizeof (struct PeerGetResultMessage)) + { + GNUNET_break_op (0); + return GNUNET_YES; + } + + get_result = (struct PeerGetResultMessage *)message; + getlen = ntohl (get_result->get_path_length); + + if ((msize < + sizeof (struct PeerGetResultMessage) + + getlen * sizeof (struct GNUNET_PeerIdentity)) || + (getlen > + GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) + { + GNUNET_break_op (0); + return GNUNET_YES; + } + + get_path = (struct GNUNET_PeerIdentity *) &get_result[1]; + payload = &get_path[getlen]; + payload_size = msize - (sizeof (struct PeerGetResultMessage) + + getlen * sizeof (struct GNUNET_PeerIdentity)); + current_path_index = ntohl (get_result->current_path_index); + + /* Here you just have to check if you are the destination or not if not + then read the next peer and send the message. */ + if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&my_identity, &(get_result->destination_peer)))) + { + /* I am the destination. Call the function in client file. + * FIXME: Here I don't know how I communicate the result back to client + file. */ + //GDS_CLIENTS_process_get_result(); + return GNUNET_YES; + } + else + { + /* Read the element from the get path at trail index. set the trail index + and call gds_neighbours_send_get_result.*/ + struct GNUNET_PeerIdentity *next_hop; + + next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); + memcpy (next_hop, &get_path[current_path_index], sizeof (struct GNUNET_PeerIdentity)); + + + if (current_path_index != 0) + current_path_index--; + + GDS_NEIGHBOURS_send_get_result (&my_identity, get_path, + getlen,&(get_result->key),&(get_result->destination_peer), + current_path_index, + payload, payload_size, next_hop); + return GNUNET_YES; + } + return GNUNET_SYSERR; } @@ -1985,15 +2160,10 @@ handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer, size_t msize; uint32_t putlen; - msize = ntohs (message->size); - if (msize < sizeof (struct PeerPutMessage)) - { - GNUNET_break_op (0); - return GNUNET_YES; - } - put = (struct PeerPutMessage *) message; putlen = ntohl (put->put_path_length); + msize = ntohs (message->size); + if ((msize < sizeof (struct PeerPutMessage) + putlen * sizeof (struct GNUNET_PeerIdentity)) || @@ -2090,7 +2260,7 @@ handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer, } else if (current_dst_type == FINGER) { - next_hop = GDS_ROUTING_search (source_peer, current_destination); + next_hop = GDS_ROUTING_search (source_peer, current_destination, peer); } if (current_dst_type == MY_ID) @@ -2111,7 +2281,7 @@ handle_dht_p2p_put (void *cls, const struct GNUNET_PeerIdentity *peer, GNUNET_TIME_absolute_ntoh (put->expiration_time), ntohl (put->hop_count),&put->key, putlen, pp, payload, payload_size, - current_destination, ¤t_dst_type, next_hop); + current_destination, current_dst_type, next_hop); return GNUNET_YES; } return GNUNET_SYSERR; @@ -2136,7 +2306,7 @@ handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer, struct PeerGetMessage *get; struct GNUNET_PeerIdentity *current_destination; uint64_t key_value; - enum current_destination_type dest_type; + enum current_destination_type cuurent_dest_type; struct GNUNET_PeerIdentity *next_hop; struct GNUNET_PeerIdentity *get_path; size_t msize; @@ -2167,30 +2337,38 @@ handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer, current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); memcpy (current_destination, &(get->current_destination), sizeof (struct GNUNET_PeerIdentity)); memcpy (&key_value, &(get->key), sizeof (uint64_t)); - dest_type = ntohl (get->dest_type); + cuurent_dest_type = ntohl (get->current_dest_type); - if (dest_type == FRIEND) + if (cuurent_dest_type == FRIEND) { - next_hop = find_successor (key_value, current_destination, &dest_type); + next_hop = find_successor (key_value, current_destination, &cuurent_dest_type); } - else if (dest_type == FINGER) + else if (cuurent_dest_type == FINGER) { - next_hop = GDS_ROUTING_search (&(get->source_peer), current_destination); + next_hop = GDS_ROUTING_search (&(get->source_peer), current_destination, peer); } - if (dest_type == MY_ID) + if (cuurent_dest_type == MY_ID) { struct GNUNET_PeerIdentity *destination_peer; - int current_path_index; + //struct GNUNET_PeerIdentity *next_hop; + //int current_path_index; /* Add yourself to the get path, increment the get length. */ destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); memcpy (destination_peer, &(get->source_peer), sizeof (struct GNUNET_PeerIdentity)); - current_path_index = get_length - 2; + //current_path_index = get_length - 1; - /* I am the final destination. Call GDS_NEIGHBOURS_send_get_result. */ - GDS_NEIGHBOURS_send_get_result (&my_identity, get_path, get_length, - destination_peer, current_path_index); + /* I am the final destination. Call GDS_NEIGHBOURS_send_get_result. + * FIXME: Last parameters are data and data size. First implement datacache get + * and get the result and send the data. Also seach for the next friend to pass + * this message to. */ +#if 0 + /* FIXME: Here we should call GDS_CLIENT_handle_reply. */ + GDS_NEIGHBOURS_send_get_result (get->request_id, &my_identity, get_path, + get_length,&(get->key), destination_peer, current_path_index, + NULL, 0, next_hop); +#endif return GNUNET_YES; } else @@ -2198,8 +2376,9 @@ handle_dht_p2p_get (void *cls, const struct GNUNET_PeerIdentity *peer, /* FIXME: Add your self to the get path and increment the get length. */ /* FIXME: Does it matter if the dest_type is friend or finger. */ - GDS_NEIGHBOURS_handle_get (&(get->source_peer), get_path, get_length, &(get->key), - next_hop, current_destination,&dest_type); + GDS_NEIGHBOURS_handle_get (&(get->source_peer), get_path, + get_length, &(get->key),next_hop, + current_destination,&cuurent_dest_type); return GNUNET_YES; } @@ -2222,16 +2401,15 @@ handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer, struct GNUNET_PeerIdentity *next_hop; struct FriendInfo *target_friend; struct GNUNET_PeerIdentity *current_destination; - struct GNUNET_PeerIdentity *next_peer; struct GNUNET_PeerIdentity *trail_peer_list; - enum current_destination_type peer_type; + enum current_destination_type current_dest_type; + struct GNUNET_PeerIdentity *next_peer; unsigned int trail_length; uint32_t current_trail_index; unsigned int finger_map_index; - uint64_t finger_value; + uint64_t destination_finger_value; size_t msize; - /* parse and validate message. */ msize = ntohs (message->size); if (msize < sizeof (struct PeerTrailSetupMessage)) { @@ -2242,8 +2420,7 @@ handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer, trail_setup = (struct PeerTrailSetupMessage *) message; trail_length = ntohl (trail_setup->trail_length); - if ((msize < - sizeof (struct PeerTrailSetupMessage) + + if ((msize < sizeof (struct PeerTrailSetupMessage) + trail_length * sizeof (struct GNUNET_PeerIdentity)) || (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) @@ -2252,123 +2429,118 @@ handle_dht_p2p_trail_setup(void *cls, const struct GNUNET_PeerIdentity *peer, return GNUNET_YES; } - peer_type = ntohl (trail_setup->current_destination_type); + current_dest_type = ntohl (trail_setup->current_destination_type); finger_map_index = ntohl (trail_setup->finger_map_index); - trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_setup[1]; - finger_value = trail_setup->destination_finger; + trail_peer_list = (struct GNUNET_PeerIdentity *)&trail_setup[1]; + destination_finger_value = trail_setup->destination_finger; current_destination = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); memcpy (current_destination, &(trail_setup->current_destination), sizeof (struct GNUNET_PeerIdentity)); - if (peer_type == FRIEND) + /* Find the next hop to send the packet to. */ + if (current_dest_type == FRIEND) { if (0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination), &my_identity))) { - next_hop = find_successor (finger_value, current_destination, &(peer_type)); + next_hop = find_successor (destination_finger_value, current_destination, &(current_dest_type)); } else return GNUNET_SYSERR; } - else if (peer_type == FINGER) + else if (current_dest_type == FINGER) { if (0 != (GNUNET_CRYPTO_cmp_peer_identity (&(trail_setup->current_destination), &my_identity))) { next_hop = GDS_ROUTING_search (&(trail_setup->source_peer), - &(trail_setup->current_destination)); - - #if 0 - /* This is an optimization. Uncomment when basic code is running first. */ - /* I am part of trail.*/ - struct GNUNET_PeerIdentity *next_peer_routing_table; - next_peer_routing_table = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - next_peer_routing_table = GDS_ROUTING_search (&(trail_setup->source_peer), - &(trail_setup->current_destination)); - - struct GNUNET_PeerIdentity *next_peer_find_successor; - next_peer_find_successor = find_successor (&(trail_setup->destination_finger), - &(trail_setup->current_destination), - &(peer_type)); - - next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - next_hop = find_closest_destination (next_peer_routing_table, - next_peer_find_successor, - &(trail_setup->destination_finger) ); - #endif + &(trail_setup->current_destination), peer); + /* As an optimization, find the successor from the find successor and + compare both the ids to find the closest peer. */ } else { - /* I am the current_destination finger */ - next_hop = find_successor (finger_value, current_destination, &(peer_type)); + next_hop = find_successor (destination_finger_value, current_destination, &(current_dest_type)); } } + + /* Add yourself to the trail list and increment the trail length. */ + struct GNUNET_PeerIdentity *peer_list; + peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1)); + if ( trail_length > 0) + { + memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); + } + memcpy (&peer_list[trail_length], &my_identity, sizeof (struct GNUNET_PeerIdentity)); + trail_length++; - /* If you are the next hop, then you are the final destination */ - if (peer_type == MY_ID) + if (current_dest_type == MY_ID || + (0 == GNUNET_CRYPTO_cmp_peer_identity(next_hop, &(trail_setup->source_peer)))) { - struct GNUNET_PeerIdentity *source; - source = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - memcpy (source, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity)); - current_trail_index = trail_length - 2; - next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - memcpy (next_peer, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity)); + struct GNUNET_PeerIdentity *source_peer; + source_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); + memcpy (source_peer, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity)); + + current_trail_index = trail_length - 1; + next_peer= GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); + if (current_trail_index == 0) + { + memcpy (next_peer, &(trail_setup->source_peer), sizeof (struct GNUNET_PeerIdentity)); + } + else + { + memcpy (next_peer, &trail_peer_list[current_trail_index-1], sizeof (struct GNUNET_PeerIdentity)); + } + target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer); GNUNET_free (next_peer); - if(current_trail_index != 0) - current_trail_index = current_trail_index - 1; - if (0 == trail_setup->finger_map_index) { - struct GNUNET_PeerIdentity *new_trail; - int i; - int j; - - i = trail_length - 1; - j = 0; - new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * - trail_length); - while (i > 0) - { - memcpy( &new_trail[j], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity)); - i--; - j++; - } - memcpy (&new_trail[j], &trail_peer_list[i], sizeof(struct GNUNET_PeerIdentity)); - finger_table_add (source, new_trail, trail_length, 1); + struct GNUNET_PeerIdentity *new_trail_list; + new_trail_list = invert_trail_list (source_peer, peer_list, trail_length); + finger_table_add (source_peer, new_trail_list, trail_length, 1); } - + GDS_NEIGHBOURS_send_trail_setup_result (&(trail_setup->source_peer), &(my_identity), target_friend, trail_length, - trail_peer_list, current_trail_index, + peer_list, current_trail_index, finger_map_index); return GNUNET_YES; } - - /* Add next hop to list of peers. */ - struct GNUNET_PeerIdentity *peer_list; - peer_list = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length + 1)); - memcpy (peer_list, trail_peer_list, trail_length * sizeof (struct GNUNET_PeerIdentity)); - memcpy (&peer_list[trail_length], next_hop, sizeof (struct GNUNET_PeerIdentity)); - trail_length++; - - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); - - if(peer_type == FINGER) + else if (next_hop == NULL) { - GDS_ROUTING_add (&(trail_setup->source_peer), - &(trail_setup->current_destination), - next_hop); + return GNUNET_SYSERR; } + else + { + target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); + if(current_dest_type == FINGER) + { + /* FIXME: Here it can even return err if routing entries have crossed the + threshold. In such a case, you should send back a trail setup fail message + to node just before your. THen its the responsiblity of node before you + to find an alternate path to reach to the current_desintation which doesnot + involve you.*/ + + if ( GNUNET_SYSERR == GDS_ROUTING_add (&(trail_setup->source_peer), + &(trail_setup->current_destination), + next_hop, peer)) + { + //trail_setup_rejection()--> add to a list of fail trails and start + // a new search rejecting this peer. + } + } - GDS_NEIGHBOURS_send_trail_setup (&(trail_setup->source_peer), - trail_setup->destination_finger, - current_destination, target_friend, trail_length, - peer_list, finger_map_index, peer_type); + GDS_NEIGHBOURS_send_trail_setup (&(trail_setup->source_peer), + trail_setup->destination_finger, + current_destination, target_friend, trail_length, + peer_list, finger_map_index, current_dest_type); -return GNUNET_YES; + return GNUNET_YES; + } + return GNUNET_SYSERR; } @@ -2385,7 +2557,7 @@ handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *p { struct PeerTrailSetupResultMessage *trail_result; struct GNUNET_PeerIdentity *trail_peer_list; - struct GNUNET_PeerIdentity *next_peer; + struct GNUNET_PeerIdentity *next_hop; struct FriendInfo *target_friend; unsigned int current_trail_index; unsigned int finger_map_index; @@ -2418,45 +2590,44 @@ handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *p trail_peer_list = (struct GNUNET_PeerIdentity *) &trail_result[1]; if ( 0 == (GNUNET_CRYPTO_cmp_peer_identity (&(trail_result->destination_peer), - &my_identity))) - { - #if 0 - /* SUPU: Here I have removed myself from the trail before storing it in - th finger table - to save space, but in case of verify successor result - the result trail does not contain me, and I will never get the message back. - So, keeping myself in the trail list. Think of better solution.*/ - struct GNUNET_PeerIdentity *finger_trail; - finger_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * (trail_length - 1)); - - /* Copy the whole trail_peer_list except the first element into trail */ - unsigned int i; - i = trail_length - 1; - while (i > 0) - { - memcpy (&finger_trail[i], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity)); - i--; - } - trail_length = trail_length -1 ; SUPU: As you removed yourself from the trail.*/ - #endif - - finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length, - finger_map_index); - - return GNUNET_YES; + &my_identity))) + { +#if 0 + /* I don't remember why I have written this code. */ + if (finger_map_index == 1) + { + struct GNUNET_PeerIdentity *new_trail_list; + new_trail_list = invert_trail_list (&(trail_result->finger_identity), + trail_peer_list, trail_length); + finger_table_add (&(trail_result->finger_identity), new_trail_list, trail_length, + finger_map_index); + return GNUNET_YES; + } + else + { +#endif + finger_table_add (&(trail_result->finger_identity), trail_peer_list, trail_length, + finger_map_index); + + return GNUNET_YES; + //} } else { - next_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - memcpy (next_peer, &(trail_peer_list[current_trail_index]), - sizeof (struct GNUNET_PeerIdentity)); - /* SUPU: here current trail index will always be greater than 0. - so no need for this check here. trail index = 0, contains the final - destination, and if we are in this loop we have not yet reached the - final destination. */ - current_trail_index = current_trail_index - 1; + next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); + + current_trail_index = current_trail_index - 1; + if (current_trail_index == 0) + { + memcpy (next_hop, &(trail_result->destination_peer),sizeof (struct GNUNET_PeerIdentity)); + } + else + { + memcpy (next_hop, &(trail_peer_list[current_trail_index-1]),sizeof (struct GNUNET_PeerIdentity)); + } - target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_peer); - GNUNET_free (next_peer); + target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); + GNUNET_free (next_hop); GDS_NEIGHBOURS_send_trail_setup_result (&(trail_result->destination_peer), &(trail_result->finger_identity), @@ -2470,6 +2641,38 @@ handle_dht_p2p_trail_setup_result(void *cls, const struct GNUNET_PeerIdentity *p } +/** + * FIXME: Use flag in the case finger peer map does not contain predcessor + * then its NULL. Ideally it should never happen. + * Get my current predecessor from the finger peer map + * @return Current predecessor. + */ +static struct FingerInfo * +get_predecessor() +{ + struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter; + struct GNUNET_PeerIdentity key_ret; + unsigned int finger_index; + struct FingerInfo *my_predecessor; + + /* Iterate over finger peer map and extract your predecessor. */ + 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 **)&my_predecessor)) + { + if(1 == my_predecessor->finger_map_index) + { + break; + } + } + } + GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter); + return my_predecessor; +} + + /** * Core handle for p2p verify successor messages. * @param cls closure @@ -2500,15 +2703,13 @@ handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *pee vsm = (struct PeerVerifySuccessorMessage *) message; trail_length = ntohl (vsm->trail_length); - if ((msize < - sizeof (struct PeerVerifySuccessorMessage) + - trail_length * sizeof (struct GNUNET_PeerIdentity)) || - (trail_length > - GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) - { - GNUNET_break_op (0); - return GNUNET_YES; - } + if ((msize < sizeof (struct PeerVerifySuccessorMessage) + + trail_length * sizeof (struct GNUNET_PeerIdentity)) || + (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) + { + GNUNET_break_op (0); + return GNUNET_YES; + } current_trail_index = ntohl (vsm->current_trail_index); trail_peer_list = (struct GNUNET_PeerIdentity *) &vsm[1]; @@ -2517,80 +2718,29 @@ handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *pee next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - /* SUPU: If I am the destination. */ - if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor), - &my_identity))) + if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsm->successor),&my_identity))) { - struct GNUNET_CONTAINER_MultiPeerMapIterator *finger_iter; - struct GNUNET_PeerIdentity key_ret; - unsigned int finger_index; struct FingerInfo *my_predecessor; - struct GNUNET_PeerIdentity *destination_peer; - - /* Iterate over finger peer map and extract your predecessor. */ - 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 **)&my_predecessor)) - { - if(1 == my_predecessor->finger_map_index) - { - break; - } - } - } - GNUNET_CONTAINER_multipeermap_iterator_destroy (finger_iter); + current_trail_index = trail_length - 1; + if (current_trail_index == 0) + memcpy (next_hop, source_peer, sizeof (struct GNUNET_PeerIdentity)); + else + memcpy (next_hop, &trail_peer_list[current_trail_index-1], sizeof (struct GNUNET_PeerIdentity)); - destination_peer = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - memcpy (destination_peer, source_peer, sizeof (struct GNUNET_PeerIdentity)); - 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); - if (current_trail_index != 0) - current_trail_index = current_trail_index - 1; - - /*SUPU: Remove this later*/ - struct GNUNET_PeerIdentity *predecessor; - predecessor = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - if (NULL == my_predecessor) + my_predecessor = get_predecessor(); + if (0 == (GNUNET_CRYPTO_cmp_peer_identity (source_peer, + &(my_predecessor->finger_identity)))) { - /* FIXME: Ideally my_predecessor should not be NULL. If some one sent - me a request to verify it I am the successor or not, then I would have - added that peer to my_predecessor list. Check trail setup and see if - you are adding predecessor when you get the request for successor. */ -#if 0 - update_predecessor (source_peer, trail_peer_list, trail_length); - - GDS_NEIGHBOURS_send_verify_successor_result (destination_peer, + GDS_NEIGHBOURS_send_verify_successor_result (source_peer, &(my_identity), - source_peer, + &(my_predecessor->finger_identity), target_friend, trail_peer_list, trail_length, current_trail_index); -#endif - } - else - { - /* FIXME: some times my_predecssor->finger_identity has no valid value. - Check why?*/ - memcpy (predecessor, &(my_predecessor->finger_identity), sizeof (struct GNUNET_PeerIdentity)); - } - - if (0 == (GNUNET_CRYPTO_cmp_peer_identity (source_peer, - &(my_predecessor->finger_identity)))) - { - /* SUPU: If source peer is my predecessor .*/ - GDS_NEIGHBOURS_send_verify_successor_result (destination_peer, - &(my_identity), - &(my_predecessor->finger_identity), - target_friend, - trail_peer_list, - trail_length, - current_trail_index); } else { @@ -2598,18 +2748,12 @@ handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *pee int new_trail_length; int i; - 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)); - - /* Copy the trail from me to my predecessor excluding me. */ + new_trail_length = trail_length + my_predecessor->trail_length; + new_successor_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * new_trail_length); + memcpy (new_successor_trail, trail_peer_list, (trail_length) * sizeof (struct GNUNET_PeerIdentity)); struct TrailPeerList *iterator; iterator = GNUNET_malloc (sizeof (struct TrailPeerList)); - iterator = my_predecessor->head->next; + iterator = my_predecessor->head; i = trail_length; while (i < new_trail_length) { @@ -2618,27 +2762,25 @@ handle_dht_p2p_verify_successor(void *cls, const struct GNUNET_PeerIdentity *pee i++; } - GDS_NEIGHBOURS_send_verify_successor_result (destination_peer, - &(my_identity), - &(my_predecessor->finger_identity), - target_friend, - new_successor_trail, - new_trail_length, - current_trail_index); + GDS_NEIGHBOURS_send_verify_successor_result (source_peer, + &(my_identity), + &(my_predecessor->finger_identity), + target_friend, + new_successor_trail, + new_trail_length, + current_trail_index); } } else { - /* If I am not the destination. */ + current_trail_index = current_trail_index + 1; 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_send_verify_successor(source_peer, &(vsm->successor),target_friend, - trail_peer_list, trail_length, current_trail_index); + + GDS_NEIGHBOURS_send_verify_successor (source_peer, &(vsm->successor),target_friend, + trail_peer_list, trail_length, current_trail_index); } return GNUNET_YES; } @@ -2671,10 +2813,9 @@ handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity nsm = (struct PeerNotifyNewSuccessorMessage *) message; trail_length = ntohl (nsm->trail_length); - if ((msize < - sizeof (struct PeerNotifyNewSuccessorMessage) + - trail_length * sizeof (struct GNUNET_PeerIdentity)) || - (trail_length > + if ((msize < sizeof (struct PeerNotifyNewSuccessorMessage) + + trail_length * sizeof (struct GNUNET_PeerIdentity)) || + (trail_length > GNUNET_SERVER_MAX_MESSAGE_SIZE / sizeof (struct GNUNET_PeerIdentity))) { GNUNET_break_op (0); @@ -2684,38 +2825,25 @@ handle_dht_p2p_notify_new_successor(void *cls, const struct GNUNET_PeerIdentity current_trail_index = ntohl (nsm->current_index); trail_peer_list = (struct GNUNET_PeerIdentity *) &nsm[1]; - if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), - &my_identity))) + if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(nsm->destination_peer), &my_identity))) { struct GNUNET_PeerIdentity *new_trail; - int i; - int j; - - i = trail_length - 1; - j = 0; - new_trail = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity) * - trail_length); - while (i > 0) - { - memcpy( &new_trail[j], &trail_peer_list[i], sizeof (struct GNUNET_PeerIdentity)); - i--; - j++; - } - memcpy (&new_trail[j], &trail_peer_list[i], sizeof(struct GNUNET_PeerIdentity)); - finger_table_add (&(nsm->source_peer), new_trail, trail_length, 1); - + new_trail = invert_trail_list (&(nsm->source_peer), trail_peer_list, trail_length); + finger_table_add (&(nsm->source_peer), new_trail, trail_length, 1); return GNUNET_YES; } else { struct FriendInfo *target_friend; - target_friend = GNUNET_malloc (sizeof (struct FriendInfo)); struct GNUNET_PeerIdentity *next_hop; + + target_friend = GNUNET_malloc (sizeof (struct FriendInfo)); next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); + + current_trail_index = current_trail_index + 1; 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_send_notify_new_successor (&(nsm->source_peer), &(nsm->destination_peer), @@ -2768,17 +2896,15 @@ handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdenti current_trail_index = ntohl (vsrm->current_index); trail_peer_list = (struct GNUNET_PeerIdentity *) &vsrm[1]; - if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), - &(my_identity)))) + if(0 == (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->destination_peer), &(my_identity)))) { - if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), - &(my_identity)))) + if(0 != (GNUNET_CRYPTO_cmp_peer_identity (&(vsrm->my_predecessor), &(my_identity)))) { finger_table_add (&(vsrm->my_predecessor), trail_peer_list, trail_length, 0); next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - memcpy (next_hop, &trail_peer_list[1], sizeof (struct GNUNET_PeerIdentity)); + memcpy (next_hop, &trail_peer_list[0], sizeof (struct GNUNET_PeerIdentity)); target_friend = GNUNET_CONTAINER_multipeermap_get (friend_peermap, next_hop); - current_trail_index = 2; + current_trail_index = 0; GNUNET_free (next_hop); GDS_NEIGHBOURS_send_notify_new_successor (&my_identity, &(vsrm->my_predecessor), @@ -2789,10 +2915,13 @@ handle_dht_p2p_verify_successor_result(void *cls, const struct GNUNET_PeerIdenti else { next_hop = GNUNET_malloc (sizeof (struct GNUNET_PeerIdentity)); - memcpy (next_hop, &trail_peer_list[current_trail_index], sizeof (struct GNUNET_PeerIdentity)); + current_trail_index = current_trail_index - 1; + if (current_trail_index == 0) + memcpy (next_hop, &(vsrm->destination_peer), sizeof (struct GNUNET_PeerIdentity)); + else + memcpy (next_hop, &trail_peer_list[current_trail_index-1], 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_send_verify_successor_result (&(vsrm->destination_peer), &(vsrm->source_successor), @@ -2825,9 +2954,6 @@ GDS_NEIGHBOURS_init() {NULL, 0, 0} }; - - /*TODO: What is ATS? Why do we need it? */ - atsAPI = GNUNET_ATS_performance_init (GDS_cfg, NULL, NULL); core_api = GNUNET_CORE_connect (GDS_cfg, NULL, &core_init, &handle_core_connect, &handle_core_disconnect, NULL, GNUNET_NO, NULL, @@ -2853,14 +2979,11 @@ GDS_NEIGHBOURS_done () GNUNET_CORE_disconnect (core_api); core_api = NULL; - GNUNET_ATS_performance_done (atsAPI); - atsAPI = NULL; - + GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (friend_peermap)); GNUNET_CONTAINER_multipeermap_destroy (friend_peermap); friend_peermap = NULL; - - + GNUNET_assert (0 == GNUNET_CONTAINER_multipeermap_size (finger_peermap)); GNUNET_CONTAINER_multipeermap_destroy (finger_peermap); finger_peermap = NULL; @@ -2870,8 +2993,7 @@ GDS_NEIGHBOURS_done () GNUNET_SCHEDULER_cancel (find_finger_trail_task); find_finger_trail_task = GNUNET_SCHEDULER_NO_TASK; } - - + if (GNUNET_SCHEDULER_NO_TASK != verify_successor) { GNUNET_SCHEDULER_cancel (verify_successor); diff --git a/src/dht/gnunet-service-xdht_neighbours.h b/src/dht/gnunet-service-xdht_neighbours.h index da5629ffb..8e0fce225 100644 --- a/src/dht/gnunet-service-xdht_neighbours.h +++ b/src/dht/gnunet-service-xdht_neighbours.h @@ -68,12 +68,12 @@ GDS_NEIGHBOURS_handle_put (enum GNUNET_BLOCK_Type type, uint32_t desired_replication_level, struct GNUNET_TIME_Absolute expiration_time, uint32_t hop_count, - struct GNUNET_HashCode * key, + const struct GNUNET_HashCode * key, unsigned int put_path_length, struct GNUNET_PeerIdentity *put_path, const void *data, size_t data_size, struct GNUNET_PeerIdentity *current_destination, - enum current_destination_type *dest_type, + enum current_destination_type dest_type, struct GNUNET_PeerIdentity *target_peer_id); @@ -94,18 +94,25 @@ GDS_NEIGHBOURS_handle_get (struct GNUNET_PeerIdentity *source_peer, enum current_destination_type *type); /** - * + * Send get result back to requesting client. * @param source_peer * @param get_path * @param get_path_length + * @param key * @param destination_peer + * @param current_path_index + * @param data + * @param data_size */ void GDS_NEIGHBOURS_send_get_result (struct GNUNET_PeerIdentity *source_peer, struct GNUNET_PeerIdentity *get_path, unsigned int get_path_length, + struct GNUNET_HashCode *key, struct GNUNET_PeerIdentity *destination_peer, - unsigned int current_path_index); + unsigned int current_path_index, + const void *data, size_t data_size, + struct GNUNET_PeerIdentity *next_peer); /** diff --git a/src/dht/gnunet-service-xdht_routing.c b/src/dht/gnunet-service-xdht_routing.c index 55ef1f4b2..f7e56c115 100644 --- a/src/dht/gnunet-service-xdht_routing.c +++ b/src/dht/gnunet-service-xdht_routing.c @@ -34,9 +34,12 @@ */ #define DHT_MAX_RECENT (1024 * 16) +/** + * Maximum number of entries in routing table. + */ +#define ROUTING_TABLE_THRESHOLD 64 /** - * FIXME: Do we need a field prev_hop * Routing table entry . */ struct RoutingTrail @@ -56,6 +59,11 @@ struct RoutingTrail */ struct GNUNET_PeerIdentity next_hop; + /** + * Peer just before next hop in the trail. + */ + struct GNUNET_PeerIdentity prev_hop; + }; @@ -66,56 +74,91 @@ static struct GNUNET_CONTAINER_MultiPeerMap *routing_table; /** - * FIXME: Change the name of variable. - * Ensure that everywhere in this file you are using destination as the key. - * Do we need prev field in routing table? * Add a new entry to our routing table. - * @param source peer - * @param destintation - * @param next_hop + * @param source peer Source of the trail. + * @param destintation Destination of the trail. + * @param next_hop Next peer to forward the message to reach the destination. + * @return GNUNET_YES + * GNUNET_SYSERR If the number of routing entries crossed thershold. */ -void +int GDS_ROUTING_add (struct GNUNET_PeerIdentity *source, struct GNUNET_PeerIdentity *dest, - struct GNUNET_PeerIdentity *next_hop) + struct GNUNET_PeerIdentity *next_hop, + const struct GNUNET_PeerIdentity *prev_hop) { struct RoutingTrail *new_routing_entry; - /* If dest is already present in the routing table, then exit.*/ - if (GNUNET_YES == - GNUNET_CONTAINER_multipeermap_contains (routing_table, dest)) - { - GNUNET_break (0); - return; - } - + if (GNUNET_CONTAINER_multipeermap_size(routing_table) > ROUTING_TABLE_THRESHOLD) + return GNUNET_SYSERR; + //FPRINTF (stderr,_("\nSUPU ROUTING ADD %s, %s, %d"),__FILE__, __func__,__LINE__); new_routing_entry = GNUNET_malloc (sizeof (struct RoutingTrail)); memcpy (&(new_routing_entry->source) , source, sizeof (struct GNUNET_PeerIdentity)); memcpy (&(new_routing_entry->next_hop), next_hop, sizeof (struct GNUNET_PeerIdentity)); memcpy (&(new_routing_entry->destination), dest, sizeof (struct GNUNET_PeerIdentity)); + memcpy (&(new_routing_entry->prev_hop), prev_hop, sizeof (struct GNUNET_PeerIdentity)); GNUNET_assert (GNUNET_OK == GNUNET_CONTAINER_multipeermap_put (routing_table, dest, new_routing_entry, - GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY)); + GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE)); + return GNUNET_YES; } -/**FIXME: Test if its correct or not. - * Find the next hop to send packet to . - * @return next hop peer id +/** + * Iterate over multiple entries for same destinational value and get + * the correct next hop. + * @param cls struct RoutingTrail + * @param key Destination identity + * @param value struct RoutingTrail + * @return #GNUNET_YES to continue looking, #GNUNET_NO if we found the next hop + */ +int +get_next_hop (void *cls, const struct GNUNET_PeerIdentity *key, void *value) +{ + /* Here you should match if source, prev hop matches if yes then send + GNUNET_NO as you don't need to check more entries. */ + struct RoutingTrail *request = cls; + struct RoutingTrail *existing_entry = (struct RoutingTrail *)value; + + if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(request->source), &(existing_entry->source))) + { + if (0 == GNUNET_CRYPTO_cmp_peer_identity (&(request->prev_hop), &(existing_entry->prev_hop))) + { + memcpy (&(request->next_hop), &(existing_entry->next_hop), sizeof (struct GNUNET_PeerIdentity)); + return GNUNET_YES; + } + } + return GNUNET_NO; +} + + +/** + * Find the next hop to send packet to. + * @param source_peer Source of the trail. + * @param destination_peer Destination of the trail. + * @param prev_hop Previous hop in the trail. + * @return Next hop in the trail from source to destination. */ struct GNUNET_PeerIdentity * GDS_ROUTING_search(struct GNUNET_PeerIdentity *source_peer, - struct GNUNET_PeerIdentity *destination_peer) + struct GNUNET_PeerIdentity *destination_peer, + const struct GNUNET_PeerIdentity *prev_hop) { struct RoutingTrail *trail; - trail = (struct RoutingTrail *)(GNUNET_CONTAINER_multipeermap_get(routing_table,destination_peer)); - - if(trail == NULL) - return NULL; - - return &(trail->next_hop); + trail = GNUNET_malloc (sizeof (struct RoutingTrail)); + memcpy (&(trail->destination), destination_peer, sizeof (struct GNUNET_PeerIdentity)); + memcpy (&(trail->source), source_peer, sizeof (struct GNUNET_PeerIdentity)); + memcpy (&(trail->prev_hop), prev_hop, sizeof (struct GNUNET_PeerIdentity)); + //trail->next_hop = NULL; + //FPRINTF (stderr,_("\nSUPU ROUTING SEARCH %s, %s, %d"),__FILE__, __func__,__LINE__); + GNUNET_CONTAINER_multipeermap_get_multiple (routing_table, destination_peer, + get_next_hop, trail); + if(trail != NULL) + return &(trail->next_hop); + else + return NULL; } diff --git a/src/dht/gnunet-service-xdht_routing.h b/src/dht/gnunet-service-xdht_routing.h index 44cb07389..92ca5f4f4 100644 --- a/src/dht/gnunet-service-xdht_routing.h +++ b/src/dht/gnunet-service-xdht_routing.h @@ -34,10 +34,11 @@ /** * Add a new entry to our routing table. */ -void +int GDS_ROUTING_add (struct GNUNET_PeerIdentity *source, struct GNUNET_PeerIdentity *destination_peer, - struct GNUNET_PeerIdentity *next_hop); + struct GNUNET_PeerIdentity *next_hop, + const struct GNUNET_PeerIdentity *prev_hop); /** @@ -46,7 +47,8 @@ GDS_ROUTING_add (struct GNUNET_PeerIdentity *source, */ struct GNUNET_PeerIdentity * GDS_ROUTING_search(struct GNUNET_PeerIdentity *source_peer, - struct GNUNET_PeerIdentity *destination_peer); + struct GNUNET_PeerIdentity *destination_peer, + const struct GNUNET_PeerIdentity *prev_hop); /** * Handle a reply (route to origin). Only forwards the reply back to -- cgit v1.2.3