/*
This file is part of GNUnet.
- (C) 2011 Christian Grothoff (and other contributing authors)
+ (C) 2011 - 2014 Christian Grothoff (and other contributing authors)
GNUnet is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published
/**
* @file dht/gnunet-service-xdht_routing.c
* @brief GNUnet DHT tracking of requests for routing replies
- * @author Christian Grothoff
+ * @author Supriti Singh
*/
#include "platform.h"
-#include "gnunet-service-dht_neighbours.h"
-#include "gnunet-service-dht_routing.h"
-#include "gnunet-service-dht.h"
-
+#include "gnunet-service-xdht_neighbours.h"
+#include "gnunet-service-xdht_routing.h"
+#include "gnunet-service-xdht.h"
/**
- * Number of requests we track at most (for routing replies).
+ * Maximum number of entries in routing table.
*/
-#define DHT_MAX_RECENT (1024 * 16)
+#define ROUTING_TABLE_THRESHOLD 64
/**
- * Information we keep about all recent GET requests
- * so that we can route replies.
+ * FIXME: do we need to store destination and source.
+ * because in trail teardown we will reach destination but it will not find any
+ * entry in routing table. so we should store destination and source.
+ * Routing table entry .
*/
-struct RecentRequest
+struct RoutingTrail
{
-
- /**
- * The peer this request was received from.
- */
- struct GNUNET_PeerIdentity peer;
-
- /**
- * Key of this request.
- */
- struct GNUNET_HashCode key;
-
- /**
- * Position of this node in the min heap.
- */
- struct GNUNET_CONTAINER_HeapNode *heap_node;
-
- /**
- * Bloomfilter for replies to drop.
- */
- struct GNUNET_CONTAINER_BloomFilter *reply_bf;
-
- /**
- * Type of the requested block.
- */
- enum GNUNET_BLOCK_Type type;
-
- /**
- * extended query (see gnunet_block_lib.h). Allocated at the
- * end of this struct.
- */
- const void *xquery;
-
/**
- * Number of bytes in xquery.
+ * Global Unique identifier of the trail.
*/
- size_t xquery_size;
+ struct GNUNET_HashCode trail_id;
/**
- * Mutator value for the reply_bf, see gnunet_block_lib.h
+ * The peer to which this request should be passed to.
*/
- uint32_t reply_bf_mutator;
+ struct GNUNET_PeerIdentity next_hop; // change to struct FriendInfo *
/**
- * Request options.
+ * Peer just before next hop in the trail.
*/
- enum GNUNET_DHT_RouteOption options;
-
+ struct GNUNET_PeerIdentity prev_hop; // change to struct FriendInfo *
};
-
-/**
- * Recent requests by time inserted.
- */
-static struct GNUNET_CONTAINER_Heap *recent_heap;
-
/**
- * Recently seen requests by key.
+ * Routing table of the peer
*/
-static struct GNUNET_CONTAINER_MultiHashMap *recent_map;
-
+static struct GNUNET_CONTAINER_MultiHashMap *routing_table;
/**
- * Closure for the 'process' function.
+ * Update the prev. hop of the trail. Call made by trail teardown where
+ * if you are the first friend now in the trail then you need to update
+ * your prev. hop.
+ * @param trail_id
+ * @return #GNUNET_OK success
+ * #GNUNET_SYSERR in case no matching entry found in routing table.
*/
-struct ProcessContext
+int
+GDS_ROUTING_update_trail_prev_hop (const struct GNUNET_HashCode trail_id,
+ struct GNUNET_PeerIdentity prev_hop)
{
- /**
- * Path of the original PUT
- */
- const struct GNUNET_PeerIdentity *put_path;
+ struct RoutingTrail *trail;
- /**
- * Path of the reply.
- */
- const struct GNUNET_PeerIdentity *get_path;
+ trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
- /**
- * Payload of the reply.
- */
- const void *data;
+ if (NULL == trail)
+ return GNUNET_SYSERR;
- /**
- * Expiration time of the result.
- */
- struct GNUNET_TIME_Absolute expiration_time;
+ trail->prev_hop = prev_hop;
+ return GNUNET_OK;
+}
- /**
- * Number of entries in 'put_path'.
- */
- unsigned int put_path_length;
- /**
- * Number of entries in 'get_path'.
- */
- unsigned int get_path_length;
+/**
+ * Get the next hop for trail corresponding to trail_id
+ * @param trail_id Trail id to be searched.
+ * @return Next_hop if found
+ * NULL If next hop not found.
+ */
+struct GNUNET_PeerIdentity *
+GDS_ROUTING_get_next_hop (const struct GNUNET_HashCode trail_id,
+ enum GDS_ROUTING_trail_direction trail_direction)
+{
+ struct RoutingTrail *trail;
- /**
- * Number of bytes in 'data'.
- */
- size_t data_size;
+ trail = GNUNET_CONTAINER_multihashmap_get (routing_table, &trail_id);
- /**
- * Type of the reply.
- */
- enum GNUNET_BLOCK_Type type;
+ if (NULL == trail)
+ return NULL;
-};
+ switch (trail_direction)
+ {
+ case GDS_ROUTING_SRC_TO_DEST:
+ return &(trail->next_hop);
+ case GDS_ROUTING_DEST_TO_SRC:
+ return &(trail->prev_hop);
+ }
+ return NULL;
+}
/**
- * Forward the result to the given peer if it matches the request.
- *
- * @param cls the `struct ProcessContext` with the result
- * @param key the query
- * @param value the `struct RecentRequest` with the request
- * @return #GNUNET_OK (continue to iterate),
- * #GNUNET_SYSERR if the result is malformed or type unsupported
+ * Remove trail with trail_id
+ * @param trail_id Trail id to be removed
+ * @return #GNUNET_YES success
+ * #GNUNET_NO if entry not found.
*/
-static int
-process (void *cls, const struct GNUNET_HashCode * key, void *value)
+int
+GDS_ROUTING_remove_trail (const struct GNUNET_HashCode remove_trail_id)
{
- struct ProcessContext *pc = cls;
- struct RecentRequest *rr = value;
- enum GNUNET_BLOCK_EvaluationResult eval;
- unsigned int gpl;
- unsigned int ppl;
- struct GNUNET_HashCode hc;
- const struct GNUNET_HashCode *eval_key;
-
- if ((rr->type != GNUNET_BLOCK_TYPE_ANY) && (rr->type != pc->type))
- return GNUNET_OK; /* type missmatch */
-
- if (0 != (rr->options & GNUNET_DHT_RO_RECORD_ROUTE))
- {
- gpl = pc->get_path_length;
- ppl = pc->put_path_length;
- }
- else
- {
- gpl = 0;
- ppl = 0;
- }
- if ((0 != (rr->options & GNUNET_DHT_RO_FIND_PEER)) &&
- (pc->type == GNUNET_BLOCK_TYPE_DHT_HELLO))
- {
- /* key may not match HELLO, which is OK since
- * the search is approximate. Still, the evaluation
- * would fail since the match is not exact. So
- * we fake it by changing the key to the actual PID ... */
- GNUNET_BLOCK_get_key (GDS_block_context, GNUNET_BLOCK_TYPE_DHT_HELLO,
- pc->data, pc->data_size, &hc);
- eval_key = &hc;
- }
- else
- {
- eval_key = key;
- }
- eval =
- GNUNET_BLOCK_evaluate (GDS_block_context, pc->type, eval_key,
- &rr->reply_bf, rr->reply_bf_mutator, rr->xquery,
- rr->xquery_size, pc->data, pc->data_size);
- switch (eval)
+ struct RoutingTrail *remove_entry;
+
+ remove_entry = GNUNET_CONTAINER_multihashmap_get (routing_table, &remove_trail_id);
+
+ if (NULL == remove_entry)
+ return GNUNET_NO;
+
+ if (GNUNET_YES == GNUNET_CONTAINER_multihashmap_remove (routing_table,
+ &remove_trail_id,
+ remove_entry))
{
- case GNUNET_BLOCK_EVALUATION_OK_MORE:
- case GNUNET_BLOCK_EVALUATION_OK_LAST:
- GNUNET_STATISTICS_update (GDS_stats,
- gettext_noop
- ("# Good REPLIES matched against routing table"),
- 1, GNUNET_NO);
- GDS_NEIGHBOURS_handle_reply (&rr->peer, pc->type, pc->expiration_time, key,
- ppl, pc->put_path, gpl, pc->get_path, pc->data,
- pc->data_size);
- break;
- case GNUNET_BLOCK_EVALUATION_OK_DUPLICATE:
- GNUNET_STATISTICS_update (GDS_stats,
- gettext_noop
- ("# Duplicate REPLIES matched against routing table"),
- 1, GNUNET_NO);
- return GNUNET_OK;
- case GNUNET_BLOCK_EVALUATION_RESULT_INVALID:
- GNUNET_STATISTICS_update (GDS_stats,
- gettext_noop
- ("# Invalid REPLIES matched against routing table"),
- 1, GNUNET_NO);
- return GNUNET_SYSERR;
- case GNUNET_BLOCK_EVALUATION_RESULT_IRRELEVANT:
- GNUNET_STATISTICS_update (GDS_stats,
- gettext_noop
- ("# Irrelevant REPLIES matched against routing table"),
- 1, GNUNET_NO);
- return GNUNET_OK;
- case GNUNET_BLOCK_EVALUATION_REQUEST_VALID:
- GNUNET_break (0);
- return GNUNET_OK;
- case GNUNET_BLOCK_EVALUATION_REQUEST_INVALID:
- GNUNET_break (0);
- return GNUNET_OK;
- case GNUNET_BLOCK_EVALUATION_TYPE_NOT_SUPPORTED:
- GNUNET_STATISTICS_update (GDS_stats,
- gettext_noop
- ("# Unsupported REPLIES matched against routing table"),
- 1, GNUNET_NO);
- return GNUNET_SYSERR;
- default:
- GNUNET_break (0);
- return GNUNET_SYSERR;
+ GNUNET_free (remove_entry);
+ return GNUNET_YES;
}
- return GNUNET_OK;
+ return GNUNET_NO;
}
/**
- * Handle a reply (route to origin). Only forwards the reply back to
- * other peers waiting for it. Does not do local caching or
- * forwarding to local clients. Essentially calls
- * GDS_NEIGHBOURS_handle_reply for all peers that sent us a matching
- * request recently.
- *
- * @param type type of the block
- * @param expiration_time when does the content expire
- * @param key key for the content
- * @param put_path_length number of entries in put_path
- * @param put_path peers the original PUT traversed (if tracked)
- * @param get_path_length number of entries in get_path
- * @param get_path peers this reply has traversed so far (if tracked)
- * @param data payload of the reply
- * @param data_size number of bytes in data
+ * Iterate over routing table and remove entries with value as part of any trail.
+ * @param cls closure
+ * @param key current public key
+ * @param value value in the hash map
+ * @return #GNUNET_YES if we should continue to iterate,
+ * #GNUNET_NO if not.
*/
-void
-GDS_ROUTING_process (enum GNUNET_BLOCK_Type type,
- struct GNUNET_TIME_Absolute expiration_time,
- const struct GNUNET_HashCode * key, unsigned int put_path_length,
- const struct GNUNET_PeerIdentity *put_path,
- unsigned int get_path_length,
- const struct GNUNET_PeerIdentity *get_path,
- const void *data, size_t data_size)
+static int remove_matching_trails (void *cls,
+ const struct GNUNET_HashCode *key,
+ void *value)
{
- struct ProcessContext pc;
-
- pc.type = type;
- pc.expiration_time = expiration_time;
- pc.put_path_length = put_path_length;
- pc.put_path = put_path;
- pc.get_path_length = get_path_length;
- pc.get_path = get_path;
- pc.data = data;
- pc.data_size = data_size;
- if (NULL == data)
+ struct RoutingTrail *remove_trail = cls;
+ struct GNUNET_PeerIdentity *peer = value;
+
+ if ((0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->next_hop, peer)) ||
+ (0 == GNUNET_CRYPTO_cmp_peer_identity (&remove_trail->prev_hop, peer)))
{
- /* Some apps might have an 'empty' reply as a valid reply; however,
- 'process' will call GNUNET_BLOCK_evaluate' which treats a 'NULL'
- reply as request-validation (but we need response-validation).
- So we set 'data' to a 0-byte non-NULL value just to be sure */
- GNUNET_break (0 == data_size);
- pc.data_size = 0;
- pc.data = ""; /* something not null */
+ GNUNET_assert (GNUNET_YES ==
+ GNUNET_CONTAINER_multihashmap_remove (routing_table,
+ &remove_trail->trail_id,
+ remove_trail));
+ GNUNET_free (remove_trail);
}
- GNUNET_CONTAINER_multihashmap_get_multiple (recent_map, key, &process, &pc);
+ return GNUNET_YES;
}
/**
- * Remove the oldest entry from the DHT routing table. Must only
- * be called if it is known that there is at least one entry
- * in the heap and hashmap.
+ * * FIXME: when a friend gets disconnected, then we remove the entry from routing
+ * table where this friend is either a next_hop or prev_hop. But we don't communicate
+ * that the trail is broken to any one who is part of trail. Should we communicate or
+ * not. And if not then the cases where trail setup fails because next_hop = NULL
+ * or something like that. VERY URGENT.
+ * Remove every trail where peer is either next_hop or prev_hop
+ * @param peer Peer to be searched.
*/
-static void
-expire_oldest_entry ()
+void
+GDS_ROUTING_remove_trail_by_peer (const struct GNUNET_PeerIdentity *peer)
{
- struct RecentRequest *recent_req;
-
- GNUNET_STATISTICS_update (GDS_stats,
- gettext_noop
- ("# Entries removed from routing table"), 1,
- GNUNET_NO);
- recent_req = GNUNET_CONTAINER_heap_peek (recent_heap);
- GNUNET_assert (recent_req != NULL);
- GNUNET_CONTAINER_heap_remove_node (recent_req->heap_node);
- GNUNET_CONTAINER_bloomfilter_free (recent_req->reply_bf);
- GNUNET_assert (GNUNET_YES ==
- GNUNET_CONTAINER_multihashmap_remove (recent_map,
- &recent_req->key,
- recent_req));
- GNUNET_free (recent_req);
+ GNUNET_CONTAINER_multihashmap_iterate (routing_table, &remove_matching_trails,
+ (void *)peer);
}
/**
- * Try to combine multiple recent requests for the same value
- * (if they come from the same peer).
- *
- * @param cls the new 'struct RecentRequest' (to discard upon successful combination)
- * @param key the query
- * @param value the existing 'struct RecentRequest' (to update upon successful combination)
- * @return GNUNET_OK (continue to iterate),
- * GNUNET_SYSERR if the request was successfully combined
+ * Add a new entry in routing table
+ * @param new_trail_id
+ * @param prev_hop
+ * @param next_hop
+ * @return #GNUNET_OK success
+ * #GNUNET_SYSERR in case new_trail_id already exists in the network
+ * but with different prev_hop/next_hop
*/
-static int
-try_combine_recent (void *cls, const struct GNUNET_HashCode * key, void *value)
+int
+GDS_ROUTING_add (struct GNUNET_HashCode new_trail_id,
+ const struct GNUNET_PeerIdentity prev_hop,
+ const struct GNUNET_PeerIdentity next_hop)
{
- struct RecentRequest *in = cls;
- struct RecentRequest *rr = value;
-
- if ( (0 != memcmp (&in->peer,
- &rr->peer,
- sizeof (struct GNUNET_PeerIdentity))) ||
- (in->type != rr->type) ||
- (in->xquery_size != rr->xquery_size) ||
- (0 != memcmp (in->xquery,
- rr->xquery,
- in->xquery_size)) )
- return GNUNET_OK;
- if (in->reply_bf_mutator != rr->reply_bf_mutator)
- {
- rr->reply_bf_mutator = in->reply_bf_mutator;
- GNUNET_CONTAINER_bloomfilter_free (rr->reply_bf);
- rr->reply_bf = in->reply_bf;
- }
- else
- {
- GNUNET_CONTAINER_bloomfilter_or2 (rr->reply_bf,
- in->reply_bf);
- GNUNET_CONTAINER_bloomfilter_free (in->reply_bf);
- }
- GNUNET_free (in);
- return GNUNET_SYSERR;
+ struct RoutingTrail *new_entry;
+
+ new_entry = GNUNET_malloc (sizeof (struct RoutingTrail));
+ new_entry->trail_id = new_trail_id;
+ new_entry->next_hop = next_hop;
+ new_entry->prev_hop = prev_hop;
+ return GNUNET_CONTAINER_multihashmap_put (routing_table,
+ &new_trail_id, new_entry,
+ GNUNET_CONTAINER_MULTIHASHMAPOPTION_UNIQUE_ONLY);
}
/**
- * Add a new entry to our routing table.
- *
- * @param sender peer that originated the request
- * @param type type of the block
- * @param options options for processing
- * @param key key for the content
- * @param xquery extended query
- * @param xquery_size number of bytes in @a xquery
- * @param reply_bf bloomfilter to filter duplicates
- * @param reply_bf_mutator mutator for @a reply_bf
+ * Check if the size of routing table has crossed threshold.
+ * @return #GNUNET_YES, if threshold crossed else #GNUNET_NO.
*/
-void
-GDS_ROUTING_add (const struct GNUNET_PeerIdentity *sender,
- enum GNUNET_BLOCK_Type type,
- enum GNUNET_DHT_RouteOption options,
- const struct GNUNET_HashCode * key, const void *xquery,
- size_t xquery_size,
- const struct GNUNET_CONTAINER_BloomFilter *reply_bf,
- uint32_t reply_bf_mutator)
+int
+GDS_ROUTING_threshold_reached (void)
{
- struct RecentRequest *recent_req;
-
- while (GNUNET_CONTAINER_heap_get_size (recent_heap) >= DHT_MAX_RECENT)
- expire_oldest_entry ();
- GNUNET_STATISTICS_update (GDS_stats,
- gettext_noop ("# Entries added to routing table"),
- 1, GNUNET_NO);
- recent_req = GNUNET_malloc (sizeof (struct RecentRequest) + xquery_size);
- recent_req->peer = *sender;
- recent_req->key = *key;
- recent_req->reply_bf = GNUNET_CONTAINER_bloomfilter_copy (reply_bf);
- recent_req->type = type;
- recent_req->options = options;
- recent_req->xquery = &recent_req[1];
- memcpy (&recent_req[1], xquery, xquery_size);
- recent_req->xquery_size = xquery_size;
- recent_req->reply_bf_mutator = reply_bf_mutator;
- if (GNUNET_SYSERR ==
- GNUNET_CONTAINER_multihashmap_get_multiple (recent_map, key,
- &try_combine_recent, recent_req))
- {
- GNUNET_STATISTICS_update (GDS_stats,
- gettext_noop
- ("# DHT requests combined"),
- 1, GNUNET_NO);
- return;
- }
- recent_req->heap_node =
- GNUNET_CONTAINER_heap_insert (recent_heap, recent_req,
- GNUNET_TIME_absolute_get ().abs_value_us);
- GNUNET_CONTAINER_multihashmap_put (recent_map, key, recent_req,
- GNUNET_CONTAINER_MULTIHASHMAPOPTION_MULTIPLE);
-
-
+ return (GNUNET_CONTAINER_multihashmap_size(routing_table) >
+ ROUTING_TABLE_THRESHOLD) ? GNUNET_YES:GNUNET_NO;
}
* Initialize routing subsystem.
*/
void
-GDS_ROUTING_init ()
+GDS_ROUTING_init (void)
{
- recent_heap = GNUNET_CONTAINER_heap_create (GNUNET_CONTAINER_HEAP_ORDER_MIN);
- recent_map = GNUNET_CONTAINER_multihashmap_create (DHT_MAX_RECENT * 4 / 3, GNUNET_NO);
+ routing_table = GNUNET_CONTAINER_multihashmap_create (ROUTING_TABLE_THRESHOLD * 4 / 3,
+ GNUNET_NO);
}
* Shutdown routing subsystem.
*/
void
-GDS_ROUTING_done ()
+GDS_ROUTING_done (void)
{
- while (GNUNET_CONTAINER_heap_get_size (recent_heap) > 0)
- expire_oldest_entry ();
- GNUNET_assert (0 == GNUNET_CONTAINER_heap_get_size (recent_heap));
- GNUNET_CONTAINER_heap_destroy (recent_heap);
- recent_heap = NULL;
- GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (recent_map));
- GNUNET_CONTAINER_multihashmap_destroy (recent_map);
- recent_map = NULL;
+ GNUNET_assert (0 == GNUNET_CONTAINER_multihashmap_size (routing_table));
+ GNUNET_CONTAINER_multihashmap_destroy (routing_table);
}
-/* end of gnunet-service-dht_routing.c */
+/* end of gnunet-service-xdht_routing.c */
projects / oweals / gnunet.git / blobdiff