Main Page | Modules | Alphabetical List | Data Structures | File List | Data Fields | Globals | Related Pages

routing.c File Reference

Detailed Description

Gnutella Network Messages routing.

Author:
Raphael Manfredi
Date:
2001-2003

#include "common.h"
#include "search.h"
#include "routing.h"
#include "hosts.h"
#include "gmsg.h"
#include "nodes.h"
#include "gnet_stats.h"
#include "hostiles.h"
#include "guid.h"
#include "oob_proxy.h"
#include "if/gnet_property.h"
#include "if/gnet_property_priv.h"
#include "lib/atoms.h"
#include "lib/endian.h"
#include "lib/glib-missing.h"
#include "lib/tm.h"
#include "lib/walloc.h"
#include "lib/override.h"

Data Structures

struct  message
 An entry in the routing table. More...

struct  route_data
 We don't store a list of nodes in the message structure, but a list of route_data: the reason is that nodes can go away, but we don't want to traverse the whole routing table to reclaim all the places where they were referenced. More...

struct  route_log
 Routing logging. More...


Defines

#define QUERY_HIT_ROUTE_SAVE   0 /**< Function used to store QHit GUIDs */
 Function used to store QHit GUIDs.

#define CHUNK_BITS   14 /**< log2 of # messages stored in a chunk */
 log2 of # messages stored in a chunk

#define MAX_CHUNKS   32 /**< Max # of chunks */
 Max # of chunks.

#define TABLE_MIN_CYCLE   1800 /**< 30 minutes at least */
 30 minutes at least

#define CHUNK_MESSAGES   (1 << CHUNK_BITS)
#define CHUNK_INDEX(x)   (((x) & ~(CHUNK_MESSAGES - 1)) >> CHUNK_BITS)
#define ENTRY_INDEX(x)   ((x) & (CHUNK_MESSAGES - 1))
#define BANNED_PUSH_COUNT   G_N_ELEMENTS(banned_push)

Functions

 RCSID ("$Id:routing.c, v 1.37 2005/10/20 06:39:19 cbiere Exp $")
gboolean find_message (const gchar *muid, guint8 function, struct message **m)
 Look for a particular message in the routing tables.

void free_route_list (struct message *m)
 Dispose of route list in message.

void routing_log_init (struct route_log *log, struct gnutella_node *n, const gchar *muid, guint8 function, guint8 hops, guint8 ttl)
 Record message parameters.

void routing_log_set_route (struct route_log *log, struct route_dest *dest, gboolean handle)
 Record message's route.

void routing_log_set_new (struct route_log *log)
 Mark message as being new.

void routing_log_extra (struct route_log *log, const gchar *fmt,...)
 Record extra logging information, appending to existing information.

gchar * route_string (struct route_dest *dest, const host_addr_t origin_addr)
void routing_log_flush (struct route_log *log)
 Emit log message.

const gchar * route_mangled_oob_muid (const gchar *muid)
 Mangle OOB query MUID by zeroing the parts of the MUID where the IP:port are recorded.

route_data * get_routing_data (struct gnutella_node *n)
 Used to ensure type safety when accessing the routing_data field.

void init_routing_data (struct gnutella_node *node)
 If a node doesn't currently have routing data attached, this creates and attaches some.

void clean_entry (struct message *entry)
 Clean already allocated entry.

message * prepare_entry (struct message **entryp)
 Prepare entry, cleaning any old value we can find at the referenced slot.

message ** get_next_slot (void)
 Fetch next routing table slot, a pointer to a routing entry.

message * get_next_entry (void)
 Fetch next routing table entry to be able to store routing information.

void revitalize_entry (struct message *entry, gboolean force)
 When a precious route (for query hit or push) is used, revitalize the entry by moving it to the end of the "message_array[]", thereby making it unlikely that it expires soon.

gboolean node_sent_message (struct gnutella_node *n, struct message *m)
 Did node send the message?

gboolean node_ttl_higher (struct gnutella_node *n, struct message *m, guint8 ttl)
 For a broadcasted message which is known to have already been sent, check whether the TTL of the message previously seen is less than the one we just got.

gint message_compare_func (gconstpointer a, gconstpointer b)
 compares two message structures

guint message_hash_func (gconstpointer key)
 Hashes message structures for storage in a hash table.

void routing_init (void)
 Init function.

void message_set_muid (struct gnutella_header *header, guint8 function)
 Generate a new muid and put it in a message header.

void remove_one_message_reference (struct route_data *rd)
 The route references one less message.

void routing_node_remove (struct gnutella_node *node)
 Erase a node from the routing tables.

void message_add (const gchar *muid, guint8 function, struct gnutella_node *node)
 Adds a new message in the routing tables.

void purge_dangling_references (struct message *m)
 Remove references to routing data that is no longer associated with a node, within the route list of the message.

gboolean check_hops_ttl (struct route_log *log, struct gnutella_node *sender)
 Ensure sane hops and TTL counts.

gboolean forward_message (struct route_log *log, struct gnutella_node **node, struct gnutella_node *target, struct route_dest *dest, GSList *routes, gboolean duplicate)
 Forwards message to one node if `target' is non-NULL, or to all nodes but the sender otherwise.

gboolean check_duplicate (struct route_log *log, struct gnutella_node **node, const gchar *mangled, struct message **mp)
 Lookup message in the routing table and check whether we have a duplicate.

gboolean route_push (struct route_log *log, struct gnutella_node **node, struct route_dest *dest, gboolean duplicate)
 Route a push message.

gboolean route_query (struct route_log *log, struct gnutella_node **node, struct route_dest *dest, gboolean duplicate)
 Route a query message.

gboolean route_query_hit (struct route_log *log, struct gnutella_node **node, struct route_dest *dest)
 Route a query hit message.

gboolean route_message (struct gnutella_node **node, struct route_dest *dest)
 Main route computation function.

gboolean route_exists_for_reply (const gchar *muid, guint8 function)
 Check whether we have a route for the reply that would be generated for this request.

GSList * route_towards_guid (const gchar *guid)
 Check whether we have a route to the given GUID, in order to send pushes.

void route_proxy_remove (gchar *guid)
 Remove push-proxy entry indexed by GUID.

gboolean route_proxy_add (gchar *guid, struct gnutella_node *n)
 Add push-proxy route to GUID `guid', which is node `n'.

gnutella_node * route_proxy_find (gchar *guid)
 Find node to which we are connected with supplied GUID and who requested that we act as its push-proxy.

void free_banned_push (gpointer key, gpointer unused_value, gpointer unused_udata)
 Frees the banned GUID atom keys.

void routing_close (void)
 Destroy routing data structures.


Variables

gnutella_node * fake_node
 Our fake node.

route_data fake_route
 Our fake route_data.

const gchar * debug_msg [256]
struct {
   message **   chunks [MAX_CHUNKS]
   gint   next_idx
   gint   capacity
   gint   count
   GHashTable *   messages_hashed
   time_t   last_rotation
} routing
const gchar *const  banned_push []
 "banned" GUIDs for push routing.

GHashTable * ht_banned_push = NULL
GHashTable * ht_proxyfied = NULL
 Push-proxy table.

Define Documentation

#define BANNED_PUSH_COUNT   G_N_ELEMENTS(banned_push)
 

#define CHUNK_BITS   14 /**< log2 of # messages stored in a chunk */
 

log2 of # messages stored in a chunk

#define CHUNK_INDEX (  x   )     (((x) & ~(CHUNK_MESSAGES - 1)) >> CHUNK_BITS)
 

#define CHUNK_MESSAGES   (1 << CHUNK_BITS)
 

#define ENTRY_INDEX (  x   )     ((x) & (CHUNK_MESSAGES - 1))
 

#define MAX_CHUNKS   32 /**< Max # of chunks */
 

Max # of chunks.

#define QUERY_HIT_ROUTE_SAVE   0 /**< Function used to store QHit GUIDs */
 

Function used to store QHit GUIDs.

#define TABLE_MIN_CYCLE   1800 /**< 30 minutes at least */
 

30 minutes at least

Function Documentation

gboolean check_duplicate (  struct route_log *  log,
struct gnutella_node **  node,
const gchar *  mangled,
struct message **  mp
)  [static]
 

Lookup message in the routing table and check whether we have a duplicate.

Parameters:
log is a structure recording to-be-logged information for debug
node is a pointer to the variable holding the node, and it can be set to NULL if we removed the node.
mangled is an alternate MUID with bytes 0-3 and 13-14 zeroed which should be tested for duplication as well. Only set for OOB queries.
mp is set on output to the message if found in the routing table.
Returns:
whether we should route the message. If `*mp' is not NULL, then the message was a duplicate and it should not be handled locally.

gboolean check_hops_ttl (  struct route_log *  log,
struct gnutella_node *  sender
)  [static]
 

Ensure sane hops and TTL counts.

Returns:
TRUE if we can continue, FALSE if we should not forward the message.

void clean_entry (  struct message *  entry  )  [static]
 

Clean already allocated entry.

gboolean find_message (  const gchar *  muid,
guint8  function,
struct message **  m
)  [static]
 

Look for a particular message in the routing tables.

If we find the message, returns true, otherwise false.

If none of the nodes that sent us the message are still present, then m->routes will be NULL.

gboolean forward_message (  struct route_log *  log,
struct gnutella_node **  node,
struct gnutella_node *  target,
struct route_dest *  dest,
GSList *  routes,
gboolean  duplicate
)  [static]
 

Forwards message to one node if `target' is non-NULL, or to all nodes but the sender otherwise.

If we kick the node, then *node is set to NULL. The message is not physically sent yet, but the `dest' structure is filled with proper routing information.

`routes' is normally NULL unless we're forwarding a PUSH request. In that case, it must be sent to the whole list of routes we have, and `target' will be NULL.

Attention:
NB: we're just *recording* routing information for the message into `dest', we are not physically forwarding the message on the wire.
Returns:
whether we should handle the message after routing.

void free_banned_push (  gpointer  key,
gpointer  unused_value,
gpointer  unused_udata
)  [static]
 

Frees the banned GUID atom keys.

void free_route_list (  struct message *  m  )  [static]
 

Dispose of route list in message.

struct message* get_next_entry (  void   )  [static]
 

Fetch next routing table entry to be able to store routing information.

struct message** get_next_slot (  void   )  [static]
 

Fetch next routing table slot, a pointer to a routing entry.

struct route_data* get_routing_data (  struct gnutella_node *  n  )  [static]
 

Used to ensure type safety when accessing the routing_data field.

void init_routing_data (  struct gnutella_node *  node  )  [static]
 

If a node doesn't currently have routing data attached, this creates and attaches some.

void message_add (  const gchar *  muid,
guint8  function,
struct gnutella_node *  node
) 
 

Adds a new message in the routing tables.

Parameters:
muid is the message MUID
function is the message type
node is the node from which we got the message, NULL if we are the node emitting it.

gint message_compare_func (  gconstpointer  a,
gconstpointer  b
)  [static]
 

compares two message structures

guint message_hash_func (  gconstpointer  key  )  [static]
 

Hashes message structures for storage in a hash table.

void message_set_muid (  struct gnutella_header *  header,
guint8  function
) 
 

Generate a new muid and put it in a message header.

gboolean node_sent_message (  struct gnutella_node *  n,
struct message *  m
)  [static]
 

Did node send the message?

gboolean node_ttl_higher (  struct gnutella_node *  n,
struct message *  m,
guint8  ttl
)  [static]
 

For a broadcasted message which is known to have already been sent, check whether the TTL of the message previously seen is less than the one we just got.

Update the highest TTL value if needed.

Returns:
FALSE if the message is really a duplicate (current TTL not greater) and the node should not have broadcasted this message again.

struct message* prepare_entry (  struct message **  entryp  )  [static]
 

Prepare entry, cleaning any old value we can find at the referenced slot.

We try to avoid re-allocating something if we can.

Returns:
message entry to use

void purge_dangling_references (  struct message *  m  )  [static]
 

Remove references to routing data that is no longer associated with a node, within the route list of the message.

RCSID (  "$Id:routing.  c,
v 1.37 2005/10/20 06:39:19 cbiere Exp $" 
) 
 

void remove_one_message_reference (  struct route_data *  rd  )  [static]
 

The route references one less message.

If the amount of messages referenced reaches 0 and the associated node was removed, free the route structure.

void revitalize_entry (  struct message *  entry,
gboolean  force
) 
 

When a precious route (for query hit or push) is used, revitalize the entry by moving it to the end of the "message_array[]", thereby making it unlikely that it expires soon.

Returns:
the new location of the revitalized entry

gboolean route_exists_for_reply (  const gchar *  muid,
guint8  function
) 
 

Check whether we have a route for the reply that would be generated for this request.

Returns:
boolean indicating whether we have such a route.

const gchar* route_mangled_oob_muid (  const gchar *  muid  )  [static]
 

Mangle OOB query MUID by zeroing the parts of the MUID where the IP:port are recorded.

Returns:
copy of mangled MUID as pointer to static data.

gboolean route_message (  struct gnutella_node **  node,
struct route_dest *  dest
) 
 

Main route computation function.

Source of message is passed by reference as `node', because it can be nullified when the node is disconnected from.

The destination of the message is computed in `dest', but the message is not physically sent. The gmsg_sendto_route() will have to be called for that.

Returns:
whether the message is to be handled locally.

gboolean route_proxy_add (  gchar *  guid,
struct gnutella_node *  n
) 
 

Add push-proxy route to GUID `guid', which is node `n'.

Returns:
TRUE on success, FALSE if there is a GUID conflict.
Attention:
NB: assumes `guid' is already an atom linked somehow to `n'.

struct gnutella_node* route_proxy_find (  gchar *  guid  ) 
 

Find node to which we are connected with supplied GUID and who requested that we act as its push-proxy.

Returns:
node address if we found it, or NULL if we aren't connected to that node directly.

void route_proxy_remove (  gchar *  guid  ) 
 

Remove push-proxy entry indexed by GUID.

gboolean route_push (  struct route_log *  log,
struct gnutella_node **  node,
struct route_dest *  dest,
gboolean  duplicate
)  [static]
 

Route a push message.

Returns:
whether message should be handled

gboolean route_query (  struct route_log *  log,
struct gnutella_node **  node,
struct route_dest *  dest,
gboolean  duplicate
)  [static]
 

Route a query message.

Returns:
whether message should be handled

gboolean route_query_hit (  struct route_log *  log,
struct gnutella_node **  node,
struct route_dest *  dest
)  [static]
 

Route a query hit message.

Returns:
whether message should be handled

gchar* route_string (  struct route_dest *  dest,
const host_addr_t  origin_addr
)  [static]
 

Returns:
string representation of message route, as pointer to static data.

GSList* route_towards_guid (  const gchar *  guid  ) 
 

Check whether we have a route to the given GUID, in order to send pushes.

Returns:
NULL if we have no such route, or a list of node to which we should send the packet otherwise. It is up to the caller to free that list.

void routing_close (  void   ) 
 

Destroy routing data structures.

void routing_init (  void   ) 
 

Init function.

void routing_log_extra (  struct route_log *  log,
const gchar *  fmt,
... 
)  [static]
 

Record extra logging information, appending to existing information.

void routing_log_flush (  struct route_log *  log  )  [static]
 

Emit log message.

void routing_log_init (  struct route_log *  log,
struct gnutella_node *  n,
const gchar *  muid,
guint8  function,
guint8  hops,
guint8  ttl
)  [static]
 

Record message parameters.

void routing_log_set_new (  struct route_log *  log  )  [static]
 

Mark message as being new.

void routing_log_set_route (  struct route_log *  log,
struct route_dest *  dest,
gboolean  handle
)  [static]
 

Record message's route.

void routing_node_remove (  struct gnutella_node *  node  ) 
 

Erase a node from the routing tables.

Variable Documentation

const gchar* const banned_push[] [static]
 

Initial value:

 {
    "20d262ff0e6fd6119734004005a207b1",     
    "9c51e42153d4c94a858f8e8a8391173d",     
    "27630b632f070ca9ffc48eb06a72c700",     
}
"banned" GUIDs for push routing.

The following GUIDs are so common that it does not make sense to route pushes to them (i.e. they are are NOT unique on the network!).

gint capacity
 

Capacity in terms of messages.

struct message** chunks[MAX_CHUNKS]
 

gint count
 

Amount really stored.

const gchar* debug_msg[256] [static]
 

struct gnutella_node* fake_node [static]
 

Our fake node.

struct route_data fake_route [static]
 

Our fake route_data.

GHashTable* ht_banned_push = NULL
 

GHashTable* ht_proxyfied = NULL
 

Push-proxy table.

It maps a GUID to a node, so that we can easily send a push message on behalf of a requesting node to the proper connection.

time_t last_rotation
 

Last time we restarted from idx=0.

GHashTable* messages_hashed
 

All messages (key = struct message).

gint next_idx
 

Next slot to use in "message_array[]".

struct { ... } routing [static]
 

Generated on Sun Feb 12 10:50:06 2006 for Gtk-Gnutella by doxygen 1.3.6