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_t *	build_ping_msg (const gchar *muid, guint8 ttl, gboolean uhc, guint32 *size)
	Global Functions.
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)
	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_t *	pong_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_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)
	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
aging *	udp_pings
cache_line	pong_cache [PONG_CACHE_SIZE]
recent	recent_pongs [HOST_MAX]

---

Define Documentation

#define ALLOCATE (  f   )

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   )     ((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]

---