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

pcache.c File Reference


Detailed Description

Pong caching (LimeWire's ping/pong reducing scheme).

Author:
Raphael Manfredi
Date:
2001-2003

#include "common.h"
#include "alive.h"
#include "extensions.h"
#include "ggep.h"
#include "ggep_type.h"
#include "gmsg.h"
#include "gnet_stats.h"
#include "hcache.h"
#include "hostiles.h"
#include "hosts.h"
#include "inet.h"
#include "nodes.h"
#include "pcache.h"
#include "routing.h"
#include "settings.h"
#include "share.h"
#include "sockets.h"
#include "tls_cache.h"
#include "udp.h"
#include "uhc.h"
#include "version.h"
#include "if/core/hosts.h"
#include "if/gnet_property_priv.h"
#include "lib/aging.h"
#include "lib/atoms.h"
#include "lib/endian.h"
#include "lib/tm.h"
#include "lib/walloc.h"
#include "lib/override.h"

Data Structures

struct  pong_info
 Basic pong information. More...
struct  cached_pong
struct  cache_line
struct  recent

Defines

#define PCACHE_MAX_FILES   10000000
 Arbitrarily large file count.
#define PCACHE_UHC_MAX_IP   30
 Max amount of IP:port returned.
#define PONG_CACHE_SIZE   (MAX_CACHE_HOPS+1)
#define CACHE_UP_LIFESPAN   20
 seconds -- ultra/normal mode
#define CACHE_LEAF_LIFESPAN   120
 seconds -- leaf mode
#define MAX_PONGS   10
 Max pongs returned per ping.
#define OLD_PING_PERIOD   45
 Pinging period for "old" clients.
#define OLD_CACHE_RATIO   20
  of pongs from "old" clients we cache
#define RECENT_PING_SIZE   50
 remember last 50 pongs we saw
#define MIN_UP_PING   3
 ping at least 3 neighbours
#define UP_PING_RATIO   20
 ping 20% of UP, at random
#define UDP_PING_FREQ   60
 answer to 1 ping per minute per IP
#define cache_lifespan(m)   ((m) == NODE_P_LEAF ? CACHE_LEAF_LIFESPAN : CACHE_UP_LIFESPAN)
#define ALLOCATE(f)

Enumerations

enum  ping_flag {
  PING_F_NONE = 0, PING_F_UHC = (1 << 0), PING_F_UHC_LEAF = (1 << 1), PING_F_UHC_ULTRA = (1 << 2),
  PING_F_UHC_ANY = (PING_F_UHC_LEAF | PING_F_UHC_ULTRA), PING_F_IP = (1 << 3)
}

Functions

void send_ping (struct gnutella_node *n, guint8 ttl)
 Sends a ping to given node, or broadcast to everyone if `n' is NULL.
gnutella_msg_init_tbuild_ping_msg (const gchar *muid, guint8 ttl, gboolean uhc, guint32 *size)
 Global Functions.
gnutella_msg_init_response_tbuild_pong_msg (host_addr_t sender_addr, guint16 sender_port, guint8 hops, guint8 ttl, const gchar *muid, struct pong_info *info, pong_meta_t *meta, enum ping_flag flags, guint32 *size)
 Build pong message.
void send_pong (struct gnutella_node *n, gboolean control, enum ping_flag flags, guint8 hops, guint8 ttl, const gchar *muid, struct pong_info *info, pong_meta_t *meta)
 Send pong message back to node.
enum ping_flag ping_type (const gnutella_node_t *n)
 Determine whether this is an UHC ping (mentionning "SCP" support).
void send_personal_info (struct gnutella_node *n, gboolean control, enum ping_flag flags)
 Send info about us back to node, using the hopcount information present in the header of the node structure to construct the TTL of the pong we send.
void send_neighbouring_info (struct gnutella_node *n)
 Send a pong for each of our connected neighbours to specified node.
guint cached_pong_hash (gconstpointer key)
gint cached_pong_eq (gconstpointer v1, gconstpointer v2)
void pcache_init (void)
 Initialization.
void free_cached_pong (struct cached_pong *cp)
 Free cached pong when noone references it any more.
gboolean pcache_get_recent (host_type_t type, host_addr_t *addr, guint16 *port)
 Get a recent pong from the list, updating `last_returned_pong' as we go along, so that we never return twice the same pong instance.
void add_recent_pong (host_type_t type, struct cached_pong *cp)
 Add recent pong to the list, handled as a FIFO cache, if not already present.
host_type_t pong_type (gnutella_init_response_t *pong)
 Determine the pong type (any, or of the ultra kind).
void pcache_clear_recent (host_type_t type)
 Clear the whole recent pong list.
void pcache_outgoing_connection (struct gnutella_node *n)
 Called when a new outgoing connection has been made.
void pcache_expire (void)
 Expire the whole cache.
void pcache_close (void)
 Final shutdown.
void ping_all_neighbours (time_t now)
 Send a ping to all "new" clients to which we are connected, and one to older client if and only if at least OLD_PING_PERIOD seconds have elapsed since our last ping, as determined by `next_ping'.
void pcache_possibly_expired (time_t now)
 Check pong cache for expiration.
void pcache_set_peermode (node_peer_t mode)
 Called when peer mode is changed to recompute the pong cache lifetime.
void setup_pong_demultiplexing (struct gnutella_node *n, guint8 ttl)
 Fill ping_guid[] and pong_needed[] arrays in the node from which we just accepted a ping.
gboolean iterate_on_cached_line (struct gnutella_node *n, struct cache_line *cl, guint8 ttl, GSList *start, GSList *end, gboolean strict)
 Internal routine for send_cached_pongs.
void send_cached_pongs (struct gnutella_node *n, struct cache_line *cl, guint8 ttl, gboolean strict)
 Send pongs from cache line back to node `n' if more are needed for this hop count and they are not originating from the node.
void send_demultiplexed_pongs (gnutella_node_t *n)
 Send as many cached pongs as needed to the relevant node.
void pong_all_neighbours_but_one (struct gnutella_node *n, struct cached_pong *cp, host_type_t ptype, guint8 hops, guint8 ttl)
 We received a pong we cached from `n'.
void pong_random_leaf (struct cached_pong *cp, guint8 hops, guint8 ttl)
 We received an ultra pong.
pong_meta_tpong_extract_metadata (struct gnutella_node *n)
 Extract pong meta data from the GGEP extensions, and create a meta data structure to hold them if necessary.
cached_pongrecord_fresh_pong (host_type_t type, struct gnutella_node *n, guint8 hops, host_addr_t addr, guint16 port, guint32 files_count, guint32 kbytes_count, gboolean get_meta)
 Add pong from node `n' to our cache of recent pongs.
void pcache_udp_ping_received (struct gnutella_node *n)
 Called when an UDP ping is received.
void pcache_ping_received (struct gnutella_node *n)
 Called when a ping is received from a node.
void pcache_udp_pong_received (struct gnutella_node *n)
 Called when an UDP pong is received.
void pcache_pong_received (struct gnutella_node *n)
 Called when a pong is received from a node.
void pcache_pong_fake (struct gnutella_node *n, const host_addr_t addr, guint16 port)
 Fake a pong for a node from which we received an incoming connection, using the supplied IP/port.

Variables

pong_meta_t local_meta
time_t pcache_expire_time = 0
agingudp_pings
cache_line pong_cache [PONG_CACHE_SIZE]
recent recent_pongs [HOST_MAX]


Define Documentation

#define ALLOCATE  ) 
 

Value:

do {                    \
    if (meta == NULL) {                     \
        meta = walloc(sizeof(*meta));       \
        meta->flags = 0;                    \
    }                                       \
    meta->flags |= CAT2(PONG_META_HAS_,f);  \
} while (0)

#define CACHE_LEAF_LIFESPAN   120
 

seconds -- leaf mode

#define cache_lifespan  )     ((m) == NODE_P_LEAF ? CACHE_LEAF_LIFESPAN : CACHE_UP_LIFESPAN)
 

#define CACHE_UP_LIFESPAN   20
 

seconds -- ultra/normal mode

#define MAX_PONGS   10
 

Max pongs returned per ping.

#define MIN_UP_PING   3
 

ping at least 3 neighbours

#define OLD_CACHE_RATIO   20
 

of pongs from "old" clients we cache

#define OLD_PING_PERIOD   45
 

Pinging period for "old" clients.

#define PCACHE_MAX_FILES   10000000
 

Arbitrarily large file count.

#define PCACHE_UHC_MAX_IP   30
 

Max amount of IP:port returned.

#define PONG_CACHE_SIZE   (MAX_CACHE_HOPS+1)
 

#define RECENT_PING_SIZE   50
 

remember last 50 pongs we saw

#define UDP_PING_FREQ   60
 

answer to 1 ping per minute per IP

#define UP_PING_RATIO   20
 

ping 20% of UP, at random


Enumeration Type Documentation

enum ping_flag
 

Enumeration values:
PING_F_NONE  No special ping.
PING_F_UHC  UHC ping.
PING_F_UHC_LEAF  UHC ping, wants leaf slots.
PING_F_UHC_ULTRA  UHC ping, wants ultra slots.
PING_F_UHC_ANY 
PING_F_IP  GGEP IP.


Function Documentation

void add_recent_pong host_type_t  type,
struct cached_pong cp
[static]
 

Add recent pong to the list, handled as a FIFO cache, if not already present.

gnutella_msg_init_t* build_ping_msg const gchar *  muid,
guint8  ttl,
gboolean  uhc,
guint32 *  size
 

Global Functions.

By construction, hops=0 for all pings.

Parameters:
muid the MUID to use. If NULL, a random one will be assigned.
ttl the TTL to use in the generated ping.
uhc whether to generate an "UHC" ping for a host cache
size where the size of the generated message is written.
Returns:
pointer to static data, and the size of the message in `size'.

gnutella_msg_init_response_t* build_pong_msg host_addr_t  sender_addr,
guint16  sender_port,
guint8  hops,
guint8  ttl,
const gchar *  muid,
struct pong_info info,
pong_meta_t meta,
enum ping_flag  flags,
guint32 *  size
[static]
 

Build pong message.

Returns:
pointer to static data, and the size of the message in `size'.

gint cached_pong_eq gconstpointer  v1,
gconstpointer  v2
[static]
 

guint cached_pong_hash gconstpointer  key  )  [static]
 

void free_cached_pong struct cached_pong cp  )  [static]
 

Free cached pong when noone references it any more.

gboolean iterate_on_cached_line struct gnutella_node n,
struct cache_line cl,
guint8  ttl,
GSList *  start,
GSList *  end,
gboolean  strict
[static]
 

Internal routine for send_cached_pongs.

Iterates on a list of cached pongs and send back any pong to node `n' that did not originate from it. Update `cursor' in the cached line to be the address of the last traversed item.

Returns:
FALSE if we're definitely done, TRUE if we can still iterate.

void pcache_clear_recent host_type_t  type  ) 
 

Clear the whole recent pong list.

void pcache_close void   ) 
 

Final shutdown.

void pcache_expire void   )  [static]
 

Expire the whole cache.

gboolean pcache_get_recent host_type_t  type,
host_addr_t addr,
guint16 *  port
 

Get a recent pong from the list, updating `last_returned_pong' as we go along, so that we never return twice the same pong instance.

Fills `addr' and `port' with the pong value and return TRUE if we got a pong. Otherwise return FALSE.

void pcache_init void   ) 
 

Initialization.

void pcache_outgoing_connection struct gnutella_node n  ) 
 

Called when a new outgoing connection has been made.

Here needs brief description for the following list:

  • If we need a connection, or have less than MAX_PONGS entries in our caught list, send a ping at normal TTL value.
  • Otherwise, send a handshaking ping with TTL=1

void pcache_ping_received struct gnutella_node n  ) 
 

Called when a ping is received from a node.

Here needs brief description for the following list:

  • If current time is less than what `ping_accept' says, drop the ping. Otherwise, accept the ping and increment `ping_accept' by n->ping_throttle.
  • If cache expired, call pcache_expire() and broadcast a new ping to all the "new" clients (i.e. those flagged NODE_A_PONG_CACHING). For "old" clients, do so only if "next_ping" time was reached.
  • Handle "alive" pings (TTL=1) and "crawler" pings (TTL=2) immediately, then return.
  • Setup pong demultiplexing tables, recording the fact that the node needs to be sent pongs as we receive them.
  • Return a pong for us if we accept incoming connections right now.
  • Return cached pongs, avoiding to resend a pong coming from that node ID.

void pcache_pong_fake struct gnutella_node n,
const host_addr_t  addr,
guint16  port
 

Fake a pong for a node from which we received an incoming connection, using the supplied IP/port.

This pong is not multiplexed to neighbours, but is used to populate our cache, so we can return its address to others, assuming that if it is making an incoming connection to us, it is really in need for other connections as well.

void pcache_pong_received struct gnutella_node n  ) 
 

Called when a pong is received from a node.

Here needs brief description for the following list:

  • Record node in the main host catching list.
  • If node is not a "new" client (i.e. flagged as NODE_A_PONG_CACHING), cache randomly OLD_CACHE_RATIO percent of those (older clients need to be able to get incoming connections as well).
  • Cache pong in the pong.hops cache line, associated with the node ID (so we never send back this entry to the node).
  • For all nodes but `n', propagate pong if neeed, with demultiplexing.

void pcache_possibly_expired time_t  now  ) 
 

Check pong cache for expiration.

If expiration time is reached, flush it and ping all our neighbours.

void pcache_set_peermode node_peer_t  mode  ) 
 

Called when peer mode is changed to recompute the pong cache lifetime.

void pcache_udp_ping_received struct gnutella_node n  )  [static]
 

Called when an UDP ping is received.

void pcache_udp_pong_received struct gnutella_node n  )  [static]
 

Called when an UDP pong is received.

void ping_all_neighbours time_t  now  )  [static]
 

Send a ping to all "new" clients to which we are connected, and one to older client if and only if at least OLD_PING_PERIOD seconds have elapsed since our last ping, as determined by `next_ping'.

enum ping_flag ping_type const gnutella_node_t n  )  [static]
 

Determine whether this is an UHC ping (mentionning "SCP" support).

Returns:
UHC_NONE if not an UHC ping, the UHC type otherwise.

void pong_all_neighbours_but_one struct gnutella_node n,
struct cached_pong cp,
host_type_t  ptype,
guint8  hops,
guint8  ttl
[static]
 

We received a pong we cached from `n'.

Send it to all other nodes if they need one at this hop count.

pong_meta_t* pong_extract_metadata struct gnutella_node n  )  [static]
 

Extract pong meta data from the GGEP extensions, and create a meta data structure to hold them if necessary.

Returns:
a walloc-ed pong_meta_t structure if meta data were found.

void pong_random_leaf struct cached_pong cp,
guint8  hops,
guint8  ttl
[static]
 

We received an ultra pong.

Send it to one randomly selected leaf, which is not already missing pongs.

host_type_t pong_type gnutella_init_response_t pong  )  [static]
 

Determine the pong type (any, or of the ultra kind).

struct cached_pong* record_fresh_pong host_type_t  type,
struct gnutella_node n,
guint8  hops,
host_addr_t  addr,
guint16  port,
guint32  files_count,
guint32  kbytes_count,
gboolean  get_meta
[static]
 

Add pong from node `n' to our cache of recent pongs.

Returns:
the cached pong object.

void send_cached_pongs struct gnutella_node n,
struct cache_line cl,
guint8  ttl,
gboolean  strict
[static]
 

Send pongs from cache line back to node `n' if more are needed for this hop count and they are not originating from the node.

When `strict' is false, we send even if no pong at that hop level is needed.

Parameters:
n the node to which pongs are sent
cl the cache line on which we need to iterate.
ttl the TTL of the pongs we're generating
strict if TRUE, don't send pongs if none needed at that hop count

void send_demultiplexed_pongs gnutella_node_t n  )  [static]
 

Send as many cached pongs as needed to the relevant node.

void send_neighbouring_info struct gnutella_node n  )  [static]
 

Send a pong for each of our connected neighbours to specified node.

void send_personal_info struct gnutella_node n,
gboolean  control,
enum ping_flag  flags
[static]
 

Send info about us back to node, using the hopcount information present in the header of the node structure to construct the TTL of the pong we send.

If `control' is true, send it as a higher priority message. If `uhc' is not UHC_NONE, we'll send IPs in a packed IPP reply.

void send_ping struct gnutella_node n,
guint8  ttl
[static]
 

Sends a ping to given node, or broadcast to everyone if `n' is NULL.

void send_pong struct gnutella_node n,
gboolean  control,
enum ping_flag  flags,
guint8  hops,
guint8  ttl,
const gchar *  muid,
struct pong_info info,
pong_meta_t meta
[static]
 

Send pong message back to node.

If `control' is true, send it as a higher priority message. If `uhc' is true, this is an UDP host cache reply.

void setup_pong_demultiplexing struct gnutella_node n,
guint8  ttl
[static]
 

Fill ping_guid[] and pong_needed[] arrays in the node from which we just accepted a ping.

When we accept a ping from a connection, we don't really relay the ping. Our cache is filled by the pongs we receive back from our periodic pinging of the neighbours.

However, when we get some pongs back, we forward them back to the nodes for which we have accepted a ping and which still need results, as determined by pong_needed[] (index by pong hop count). The saved GUID of the ping allows us to fake the pong reply, so the sending node recognizes those as being "his" pongs.


Variable Documentation

pong_meta_t local_meta [static]
 

time_t pcache_expire_time = 0 [static]
 

struct cache_line pong_cache[PONG_CACHE_SIZE] [static]
 

struct recent recent_pongs[HOST_MAX] [static]
 

struct aging* udp_pings [static]
 


Generated on Sat Jun 30 17:53:29 2007 for gtk-gnutella by  doxygen 1.3.9.1