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

qrp.c File Reference

Detailed Description

Query Routing Protocol (LimeWire's scheme).

Author:
Raphael Manfredi
Date:
2002-2003

#include "common.h"
#include <math.h>
#include <zlib.h>
#include "qrp.h"
#include "routing.h"
#include "gmsg.h"
#include "nodes.h"
#include "gnet_stats.h"
#include "share.h"
#include "lib/atoms.h"
#include "lib/bg.h"
#include "lib/cq.h"
#include "lib/glib-missing.h"
#include "lib/endian.h"
#include "lib/sha1.h"
#include "lib/tm.h"
#include "lib/utf8.h"
#include "lib/wordvec.h"
#include "lib/walloc.h"
#include "lib/zlib_util.h"
#include "if/gnet_property.h"
#include "if/gnet_property_priv.h"
#include "lib/override.h"

Data Structures

struct  routing_table
 A routing table. More...

struct  routing_patch
 A routing table patch. More...

struct  qrt_compress_context
struct  merge_context
struct  query_routing
 This structure is opaque for nodes, and is installed as `query_routing' information in the node structure. More...

struct  unique_substrings
struct  qrp_context
struct  qrt_patch_context
struct  patch_listener_info
struct  qrp_reset
struct  qrp_patch
struct  qrt_update
struct  qrt_receive

Defines

#define MIN_SPARSE_RATIO   1 /**< At most 1% of slots used */
 At most 1% of slots used.

#define MAX_CONFLICT_RATIO   20 /**< At most 20% of insertion conflicts */
 At most 20% of insertion conflicts.

#define LOCAL_INFINITY   2 /**< We're one hop away, so 2 is infinity */
 We're one hop away, so 2 is infinity.

#define MIN_TABLE_BITS   14 /**< 16 KB */
 16 KB

#define MAX_TABLE_BITS   21 /**< 2 MB */
 2 MB

#define MAX_TABLE_SIZE   (1 << MAX_TABLE_BITS)
#define MAX_UP_TABLE_SIZE   131072 /**< Max size for inter-UP QRP: 128 Kslots */
 Max size for inter-UP QRP: 128 Kslots.

#define EMPTY_TABLE_SIZE   8
#define LEAF_MONITOR_PERIOD   (300 * 1000) /**< 5 minutes, in ms */
 5 minutes, in ms

#define QRP_HASH_RESTRICT(hashcode, bits)   ((guint32) (hashcode) >> (32 - (gint) (bits)))
 Restrict given hashcode to be a suitable index on `bits' bits.

#define RT_SLOT_READ(a, s)   ((a)[(s) >> 3] & (0x80U >> ((s) & 0x7)))
 Access slot #`s' in arena `a'.

#define QRT_TICK_CHUNK   256 /**< Chunk size per tick */
 Chunk size per tick.

#define QRT_NONE   0 /**< No QRT sent yet */
 No QRT sent yet.

#define QRT_SENDING   1 /**< Sending patches */
 Sending patches.

#define QRT_IDLE   2 /**< Finished send patches */
 Finished send patches.

#define DEFAULT_BUF_SIZE   512
#define MIN_BUF_GROW   256
#define QRP_STEP_SUBSTRING   1 /**< Substring computation */
 Substring computation.

#define QRP_STEP_COMPUTE   2 /**< Compute QRT */
 Compute QRT.

#define QRP_STEP_INSTALL   3 /**< Install new QRT */
 Install new QRT.

#define QRP_STEP_LAST   3 /**< Last step */
 Last step.

#define QRT_PATCH_LEN   512 /**< Send 512 bytes at a time, if we can */
 Send 512 bytes at a time, if we can.

#define QRT_MAX_SEQSIZE   255 /**< Maximum: 255 messages */
 Maximum: 255 messages.

#define QRT_MAX_BANDWIDTH   1024 /**< Max bandwidth if clogging occurs */
 Max bandwidth if clogging occurs.

#define QRT_MIN_QUEUE_FILL   40 /**< Hold PATCH message if queue 40% full */
 Hold PATCH message if queue 40% full.

#define QRT_RECEIVE_BUFSIZE   4096 /**< Size of decompressing buffer */
 Size of decompressing buffer.

#define CHECK(x)   g_assert((x))

Typedefs

typedef void(* qrt_patch_computed_cb_t )(gpointer arg, struct routing_patch *rp)

Enumerations

enum  qrp_route_magic { QRP_ROUTE_MAGIC = 0xf2aa4886 }
enum  routing_patch_magic { ROUTING_PATCH_MAGIC = 0x811906cf }
enum  qrt_compress_magic { QRT_COMPRESS_MAGIC = 0xcbb0a7ac }
enum  merge_magic { MERGE_MAGIC = 0xe39ee39e }
enum  qrp_magic { QRP_MAGIC = 0xc4b5975aU }
enum  qrt_patch_magic { QRT_PATCH_MAGIC = 0xf347c237 }
enum  qrt_update_magic { QRT_UPDATE_MAGIC = 0x31912e13 }
enum  qrt_receive_magic { QRT_RECEIVE_MAGIC = 0x15efbb04 }

Functions

 RCSID ("$Id:qrp.c, v 1.56 2005/12/27 13:02:29 cbiere Exp $")
void qrt_compress_cancel_all (void)
 Cancel all running compression coroutines.

void qrt_patch_compute (struct routing_table *rt, struct routing_patch **rpp)
 Launch asynchronous computation of the default routing patch.

guint32 qrt_dump (FILE *f, struct routing_table *rt, gboolean full)
 Dump QRT to specified file.

void test_hash (void)
void qrp_monitor (cqueue_t *cq, gpointer obj)
 Periodic monitor, to trigger recomputation of the merged table if we got a new leaf with a QRT or lost a leaf which sent us its QRT.

void install_routing_table (struct routing_table *rt)
 Install supplied routing_table as the global `routing_table'.

void install_merged_table (struct routing_table *rt)
 Install supplied routing_table as the global `merged_table'.

guint32 qrp_hashcode (const gchar *s)
 Compute standard QRP hash code on 32 bits.

guint32 qrp_hash (const gchar *s, gint bits)
 For tests only.

void qrt_patch_slot (struct routing_table *rt, guint i, guint8 v)
void qrt_compact (struct routing_table *rt)
 Compact routing table in place so that only one bit of information is used per entry, reducing memory requirements by a factor of 8.

gchar * qrt_sha1 (struct routing_table *rt)
 Computes the SHA1 of a compacted routing table.

routing_patch * qrt_patch_ref (struct routing_patch *rp)
 Get a new reference on a routing patch.

void qrt_patch_free (struct routing_patch *rp)
 Free routing table patch.

void qrt_patch_unref (struct routing_patch *rp)
 Remove a reference on a routing patch, freeing it when no more ref remains.

routing_patch * qrt_diff_4 (struct routing_table *old, struct routing_table *new)
 Compute patch between two (compacted) routing tables.

void qrt_compress_free (gpointer u)
 Free compression context.

bgret_t qrt_step_compress (gpointer h, gpointer u, gint ticks)
 Perform incremental compression.

void qrt_patch_compress_done (gpointer h, gpointer u, bgstatus_t status, gpointer unused_arg)
 Called when the compress task is finished.

gpointer qrt_patch_compress (struct routing_patch *rp, bgdone_cb_t done_callback, gpointer arg)
 Compress routing patch inplace (asynchronously).

routing_table * qrt_create (const gchar *name, gchar *arena, gint slots, gint max)
 Create a new query routing table, with supplied `arena' and `slots'.

routing_table * qrt_empty_table (const gchar *name)
 Create small empty table.

void qrt_free (struct routing_table *rt)
 Free query routing table.

gpointer qrt_shrink_arena (gchar *arena, gint old_slots, gint new_slots, gint infinity)
 Shrink arena inplace to use only `new_slots' instead of `old_slots'.

gpointer qrt_get_table (void)
gpointer qrt_ref (gpointer obj)
 Get a new reference on the query routing table.

void qrt_unref (gpointer obj)
 Remove one reference to query routing table.

void qrt_get_info (gpointer obj, qrt_info_t *qi)
void merge_context_free (gpointer p)
 Free merge context.

bgret_t mrg_step_get_list (gpointer unused_h, gpointer u, gint unused_ticks)
 Fetch the list of all the QRT from our leaves.

void merge_table_into_arena (struct routing_table *rt, guchar *arena, gint slots)
 Merge routing table into specified arena.

bgret_t mrg_step_merge_one (gpointer unused_h, gpointer u, gint ticks)
 Merge next leaf QRT table if node is still there.

bgret_t mrg_step_install_table (gpointer unused_h, gpointer u, gint unused_ticks)
 Create and install the table.

void mrg_compute (bgdone_cb_t done_cb)
 Launch asynchronous merging of the leaf node QRT tables.

void qrp_cancel_computation (void)
 Cancel current computation, if any.

void qrp_prepare_computation (void)
 This routine must be called to initialize the computation of the new QRP based on our local files.

void qrp_add_file (struct shared_file *sf)
 Add shared file to our QRP.

void free_word (gpointer key, gpointer unused_value, gpointer unused_udata)
void insert_substr (struct unique_substrings *u, const gchar *word)
void unique_substr (gpointer key, gpointer unused_value, gpointer udata)
 Iteration callback on the hashtable containing keywords.

GSList * unique_substrings (GHashTable *ht, gint *retcount)
 Create a list of all unique substrings at least MIN_WORD_LENGTH long, from words held in `ht'.

void dispose_ht_seen_words (void)
 Free the `ht_seen_words' table.

void qrp_context_free (gpointer p)
 Free query routing table computation context.

void qrp_comp_context_free (gpointer p)
 Called when the QRP recomputation is done to free the context.

void qrp_merge_context_free (gpointer p)
 Called when the QRP merging is done to free the context.

bgret_t qrp_step_substring (gpointer unused_h, gpointer u, gint unused_ticks)
 Compute all the substrings we need to insert.

gboolean qrt_eq (struct routing_table *rt, gchar *arena, gint slots)
 Compare possibly compacted table `rt' with expanded table arena `arena' having `slots' slots.

bgret_t qrp_step_compute (gpointer h, gpointer u, gint unused_ticks)
 Compute QRP table, iteration step.

bgret_t qrp_step_create_table (gpointer unused_h, gpointer u, gint unused_ticks)
 Create the compacted routing table object.

bgret_t qrp_step_install_leaf (gpointer unused_h, gpointer u, gint unused_ticks)
 Install the routing table we've built, if running as leaf.

bgret_t qrp_step_wait_for_merged_table (gpointer h, gpointer u, gint unused_ticks)
 Wait for the `merged_table' to be ready.

bgret_t qrp_step_merge_with_leaves (gpointer unused_h, gpointer u, gint ticks)
 Merge `local_table' with `merged_table'.

bgret_t qrp_step_install_ultra (gpointer h, gpointer u, gint ticks)
 Install the final routing table, and begin computation of the default QRT patch for new connections.

void qrp_finalize_computation (void)
 This routine must be called once all the files have been added to finalize the computation of the new QRP.

void qrp_update_routing_table (void)
 Proceed with table merging between `merge_table' and `local_table' into `routing_table' if we're running as an ultra node, or install the `local_table' as the `routing_table' if we're running as leaf.

void qrp_merge_routing_table (gpointer unused_h, gpointer unused_c, bgstatus_t status, gpointer unused_arg)
 Called as a task completion callback when the `merge_table' has been recomputed, to relaunch the merging with `local_table' to get the final routing table.

void qrp_peermode_changed (void)
 Called when the current peermode has changed.

void qrt_patch_computed (gpointer unused_h, gpointer unused_u, bgstatus_t status, gpointer arg)
 Callback invoked when the routing patch is computed.

gpointer qrt_patch_computed_add_listener (qrt_patch_computed_cb_t cb, gpointer arg)
 Record listener to callback with given argument when the default routing patch will be ready.

void qrt_patch_computed_remove_listener (gpointer handle)
 Remove recorded listener.

void qrt_patch_cancel_compute (void)
 Cancel computation.

void qrp_send_reset (struct gnutella_node *n, gint slots, gint infinity)
 Send the RESET message, which must be sent before the PATCH sequence to size the table.

void qrp_send_patch (struct gnutella_node *n, gint seqno, gint seqsize, gboolean compressed, gint bits, gchar *buf, gint len)
 Send the PATCH message.

gboolean qrp_recv_reset (struct gnutella_node *n, struct qrp_reset *reset)
 Receive a RESET message and fill the `reset' structure with its payload.

gboolean qrp_recv_patch (struct gnutella_node *n, struct qrp_patch *patch)
 Receive a PATCH message and fill the `patch' structure with its payload.

void qrt_compressed (gpointer unused_h, gpointer unused_u, bgstatus_t status, gpointer arg)
 Callback invoked when the computed patch for a connection has been compressed.

void qrt_patch_available (gpointer arg, struct routing_patch *rp)
 Default global routing patch (the one against a NULL table) is now available for consumption.

gpointer qrt_update_create (struct gnutella_node *n, gpointer query_table)
 Create structure keeping track of the table update.

void qrt_update_free (gpointer handle)
 Free query routing update tracker.

gboolean qrt_update_send_next (gpointer handle)
 Send the next batch of data.

gboolean qrt_update_was_ok (gpointer handle)
 Check whether sending was successful.

gboolean qrt_unknown_patch (struct qrt_receive *unused_qrcv, const guchar *unused_data, gint unused_len)
 A default handler that should never be called.

gpointer qrt_receive_create (struct gnutella_node *n, gpointer query_table)
 Create a new QRT receiving handler, to process all incoming QRP messages from the leaf node.

void qrt_receive_free (gpointer handle)
 Dispose of the QRP receiving state.

gboolean qrt_apply_patch (struct qrt_receive *qrcv, const guchar *data, gint len)
 Apply raw patch data (uncompressed) to the current routing table.

gboolean qrt_patch_is_valid (struct qrt_receive *qrcv, gint len, gint slots_per_byte)
 Sanity checks at each patch reception.

gboolean qrt_apply_patch8 (struct qrt_receive *qrcv, const guchar *data, gint len)
 Apply raw 8-bit patch data (uncompressed) to the current routing table.

gboolean qrt_apply_patch4 (struct qrt_receive *qrcv, const guchar *data, gint len)
 Apply raw 4-bit patch data (uncompressed) to the current routing table.

gboolean qrt_handle_reset (struct gnutella_node *n, struct qrt_receive *qrcv, struct qrp_reset *reset)
 Handle reception of QRP RESET.

gboolean qrt_handle_patch (struct gnutella_node *n, struct qrt_receive *qrcv, struct qrp_patch *patch, gboolean *done)
 Handle reception of QRP PATCH.

gboolean qrt_receive_next (gpointer handle, gboolean *done)
 Handle reception of the next QRP message in the stream for a given update.

void qrp_leaf_changed (void)
 Called when we get a new QRT from a leaf node, or when we loose a leaf that sent us its QRT.

void qrp_init (char_map_t map)
 Initialize QRP.

void qrp_close (void)
 Called at servent shutdown to reclaim all the memory.

gboolean qrt_dump_is_slot_present (struct routing_table *rt, gint slot)
 Used by qrt_dump().

query_hashvec_t * qhvec_alloc (gint size)
 Allocate a query hash container for at most `size' entries.

void qhvec_free (query_hashvec_t *qhvec)
 Dispose of the query hash container.

void qhvec_reset (query_hashvec_t *qhvec)
 Empty query hash container.

query_hashvec_t * qhvec_clone (const query_hashvec_t *qsrc)
 Clone query hash vector.

void qhvec_add (query_hashvec_t *qhvec, const gchar *word, enum query_hsrc src)
 Add the `word' coming from `src' into the query hash vector.

gboolean qrp_can_route (query_hashvec_t *qhv, struct routing_table *rt)
 Check whether we can route a query identified by its hash vector to a node given its routing table.

gboolean qrp_node_can_route (gnutella_node_t *n, query_hashvec_t *qhv)
 Check whether we can route a query identified by its hash vector to a node.

GSList * qrt_build_query_target (query_hashvec_t *qhvec, gint hops, gint ttl, struct gnutella_node *source)
 Compute list of nodes to send the query to, based on node's QRT.

void qrt_route_query (struct gnutella_node *n, query_hashvec_t *qhvec)
 Route query message to leaf nodes, based on their QRT, or to ultrapeers that support last-hop QRP if TTL=1.


Variables

char_map_t qrp_map
routing_table * routing_table = NULL
 Our table.

routing_patch * routing_patch = NULL
 Against empty table.

routing_table * local_table = NULL
 Table for local files.

routing_table * merged_table = NULL
 From all our leaves.

gint generation = 0
gpointer monitor_ev = NULL
GSList * sl_compress_tasks = NULL
gpointer merge_comp = NULL
merge_context * merge_ctx = NULL
bgstep_cb_t merge_steps []
GHashTable * ht_seen_words = NULL
struct {
   gchar *   arena
   gint   len
} buffer
gpointer qrp_comp = NULL
 Background computation handle.

gpointer qrp_merge = NULL
 Background merging handle.

bgstep_cb_t qrp_compute_steps []
bgstep_cb_t qrp_merge_steps []
qrt_patch_context * qrt_patch_ctx = NULL
GSList * qrt_patch_computed_listeners = NULL
gboolean qrt_leaf_change_notified = FALSE

Define Documentation

#define CHECK (  x   )     g_assert((x))
 

#define DEFAULT_BUF_SIZE   512
 

#define EMPTY_TABLE_SIZE   8
 

#define LEAF_MONITOR_PERIOD   (300 * 1000) /**< 5 minutes, in ms */
 

5 minutes, in ms

#define LOCAL_INFINITY   2 /**< We're one hop away, so 2 is infinity */
 

We're one hop away, so 2 is infinity.

#define MAX_CONFLICT_RATIO   20 /**< At most 20% of insertion conflicts */
 

At most 20% of insertion conflicts.

#define MAX_TABLE_BITS   21 /**< 2 MB */
 

2 MB

#define MAX_TABLE_SIZE   (1 << MAX_TABLE_BITS)
 

#define MAX_UP_TABLE_SIZE   131072 /**< Max size for inter-UP QRP: 128 Kslots */
 

Max size for inter-UP QRP: 128 Kslots.

#define MIN_BUF_GROW   256
 

#define MIN_SPARSE_RATIO   1 /**< At most 1% of slots used */
 

At most 1% of slots used.

#define MIN_TABLE_BITS   14 /**< 16 KB */
 

16 KB

#define QRP_HASH_RESTRICT (  hashcode,
bits   )     ((guint32) (hashcode) >> (32 - (gint) (bits)))
 

Restrict given hashcode to be a suitable index on `bits' bits.

#define QRP_STEP_COMPUTE   2 /**< Compute QRT */
 

Compute QRT.

#define QRP_STEP_INSTALL   3 /**< Install new QRT */
 

Install new QRT.

#define QRP_STEP_LAST   3 /**< Last step */
 

Last step.

#define QRP_STEP_SUBSTRING   1 /**< Substring computation */
 

Substring computation.

#define QRT_IDLE   2 /**< Finished send patches */
 

Finished send patches.

#define QRT_MAX_BANDWIDTH   1024 /**< Max bandwidth if clogging occurs */
 

Max bandwidth if clogging occurs.

#define QRT_MAX_SEQSIZE   255 /**< Maximum: 255 messages */
 

Maximum: 255 messages.

#define QRT_MIN_QUEUE_FILL   40 /**< Hold PATCH message if queue 40% full */
 

Hold PATCH message if queue 40% full.

#define QRT_NONE   0 /**< No QRT sent yet */
 

No QRT sent yet.

#define QRT_PATCH_LEN   512 /**< Send 512 bytes at a time, if we can */
 

Send 512 bytes at a time, if we can.

#define QRT_RECEIVE_BUFSIZE   4096 /**< Size of decompressing buffer */
 

Size of decompressing buffer.

#define QRT_SENDING   1 /**< Sending patches */
 

Sending patches.

#define QRT_TICK_CHUNK   256 /**< Chunk size per tick */
 

Chunk size per tick.

#define RT_SLOT_READ (  a,
s   )     ((a)[(s) >> 3] & (0x80U >> ((s) & 0x7)))
 

Access slot #`s' in arena `a'.

Table is compacted so that slot #6 is bit 1 of byte 0.

In general:

byte = slot >> 3; bit = 7 - (slot & 0x7); value = arena[byte] & (1 << bit)

Returns:
the TRUE if there is something present, FALSE otherwise.

Typedef Documentation

typedef void(* qrt_patch_computed_cb_t)(gpointer arg, struct routing_patch *rp)
 

Enumeration Type Documentation

enum merge_magic
 

Enumeration values:
MERGE_MAGIC 

enum qrp_magic
 

Enumeration values:
QRP_MAGIC 

enum qrp_route_magic
 

Enumeration values:
QRP_ROUTE_MAGIC 

enum qrt_compress_magic
 

Enumeration values:
QRT_COMPRESS_MAGIC 

enum qrt_patch_magic
 

Enumeration values:
QRT_PATCH_MAGIC 

enum qrt_receive_magic
 

Enumeration values:
QRT_RECEIVE_MAGIC 

enum qrt_update_magic
 

Enumeration values:
QRT_UPDATE_MAGIC 

enum routing_patch_magic
 

Enumeration values:
ROUTING_PATCH_MAGIC 

Function Documentation

void dispose_ht_seen_words (  void   )  [static]
 

Free the `ht_seen_words' table.

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

void insert_substr (  struct unique_substrings *  u,
const gchar *  word
)  [inline, static]
 

void install_merged_table (  struct routing_table *  rt  )  [static]
 

Install supplied routing_table as the global `merged_table'.

If the supplied table is NULL, we simply forget about the old table.

void install_routing_table (  struct routing_table *  rt  )  [static]
 

Install supplied routing_table as the global `routing_table'.

void merge_context_free (  gpointer  p  )  [static]
 

Free merge context.

void merge_table_into_arena (  struct routing_table *  rt,
guchar *  arena,
gint  slots
)  [static]
 

Merge routing table into specified arena.

Parameters:
rt is the routing table to merge
arena is a non-compacted arena
slots is the number of slots in the arena

void mrg_compute (  bgdone_cb_t  done_cb  )  [static]
 

Launch asynchronous merging of the leaf node QRT tables.

Parameters:
done_cb is the routine to invoke when merging is done. If NULL, then no routine is called.

bgret_t mrg_step_get_list (  gpointer  unused_h,
gpointer  u,
gint  unused_ticks
)  [static]
 

Fetch the list of all the QRT from our leaves.

bgret_t mrg_step_install_table (  gpointer  unused_h,
gpointer  u,
gint  unused_ticks
)  [static]
 

Create and install the table.

bgret_t mrg_step_merge_one (  gpointer  unused_h,
gpointer  u,
gint  ticks
)  [static]
 

Merge next leaf QRT table if node is still there.

void qhvec_add (  query_hashvec_t *  qhvec,
const gchar *  word,
enum query_hsrc  src
) 
 

Add the `word' coming from `src' into the query hash vector.

If the vector is already full, do nothing.

query_hashvec_t* qhvec_alloc (  gint  size  ) 
 

Allocate a query hash container for at most `size' entries.

query_hashvec_t* qhvec_clone (  const query_hashvec_t *  qsrc  ) 
 

Clone query hash vector.

void qhvec_free (  query_hashvec_t *  qhvec  ) 
 

Dispose of the query hash container.

void qhvec_reset (  query_hashvec_t *  qhvec  ) 
 

Empty query hash container.

void qrp_add_file (  struct shared_file *  sf  ) 
 

Add shared file to our QRP.

gboolean qrp_can_route (  query_hashvec_t *  qhv,
struct routing_table *  rt
)  [static]
 

Check whether we can route a query identified by its hash vector to a node given its routing table.

Parameters:
qhv the query hit vector containing QRP hashes and types
rt the routing table of the target node
Note:
thie routine expects the query hash vector to be sorted with URNs coming first and words later.

void qrp_cancel_computation (  void   )  [static]
 

Cancel current computation, if any.

void qrp_close (  void   ) 
 

Called at servent shutdown to reclaim all the memory.

void qrp_comp_context_free (  gpointer  p  )  [static]
 

Called when the QRP recomputation is done to free the context.

void qrp_context_free (  gpointer  p  )  [static]
 

Free query routing table computation context.

void qrp_finalize_computation (  void   ) 
 

This routine must be called once all the files have been added to finalize the computation of the new QRP.

If the routing table has changed, the node_qrt_changed() routine will be called once we have finished its computation.

guint32 qrp_hash (  const gchar *  s,
gint  bits
)  [inline, static]
 

For tests only.

The hashing function, defined by the QRP specifications. Naturally, everyone must use the SAME hashing function!

guint32 qrp_hashcode (  const gchar *  s  )  [inline, static]
 

Compute standard QRP hash code on 32 bits.

void qrp_init (  char_map_t  map  ) 
 

Initialize QRP.

void qrp_leaf_changed (  void   ) 
 

Called when we get a new QRT from a leaf node, or when we loose a leaf that sent us its QRT.

void qrp_merge_context_free (  gpointer  p  )  [static]
 

Called when the QRP merging is done to free the context.

void qrp_merge_routing_table (  gpointer  unused_h,
gpointer  unused_c,
bgstatus_t  status,
gpointer  unused_arg
)  [static]
 

Called as a task completion callback when the `merge_table' has been recomputed, to relaunch the merging with `local_table' to get the final routing table.

void qrp_monitor (  cqueue_t *  unused_cq,
gpointer  unused_obj
)  [static]
 

Periodic monitor, to trigger recomputation of the merged table if we got a new leaf with a QRT or lost a leaf which sent us its QRT.

gboolean qrp_node_can_route (  gnutella_node_t *  n,
query_hashvec_t *  qhv
) 
 

Check whether we can route a query identified by its hash vector to a node.

void qrp_peermode_changed (  void   ) 
 

Called when the current peermode has changed.

void qrp_prepare_computation (  void   ) 
 

This routine must be called to initialize the computation of the new QRP based on our local files.

gboolean qrp_recv_patch (  struct gnutella_node *  n,
struct qrp_patch *  patch
)  [static]
 

Receive a PATCH message and fill the `patch' structure with its payload.

Returns:
TRUE if we read the message OK.

gboolean qrp_recv_reset (  struct gnutella_node *  n,
struct qrp_reset *  reset
)  [static]
 

Receive a RESET message and fill the `reset' structure with its payload.

Returns:
TRUE if we read the message OK.

void qrp_send_patch (  struct gnutella_node *  n,
gint  seqno,
gint  seqsize,
gboolean  compressed,
gint  bits,
gchar *  buf,
gint  len
)  [static]
 

Send the PATCH message.

The patch payload data is made of the `len' bytes starting at `buf'.

void qrp_send_reset (  struct gnutella_node *  n,
gint  slots,
gint  infinity
)  [static]
 

Send the RESET message, which must be sent before the PATCH sequence to size the table.

bgret_t qrp_step_compute (  gpointer  h,
gpointer  u,
gint  unused_ticks
)  [static]
 

Compute QRP table, iteration step.

bgret_t qrp_step_create_table (  gpointer  unused_h,
gpointer  u,
gint  unused_ticks
)  [static]
 

Create the compacted routing table object.

bgret_t qrp_step_install_leaf (  gpointer  unused_h,
gpointer  u,
gint  unused_ticks
)  [static]
 

Install the routing table we've built, if running as leaf.

bgret_t qrp_step_install_ultra (  gpointer  h,
gpointer  u,
gint  ticks
)  [static]
 

Install the final routing table, and begin computation of the default QRT patch for new connections.

bgret_t qrp_step_merge_with_leaves (  gpointer  unused_h,
gpointer  u,
gint  ticks
)  [static]
 

Merge `local_table' with `merged_table'.

bgret_t qrp_step_substring (  gpointer  unused_h,
gpointer  u,
gint  unused_ticks
)  [static]
 

Compute all the substrings we need to insert.

bgret_t qrp_step_wait_for_merged_table (  gpointer  h,
gpointer  u,
gint  unused_ticks
)  [static]
 

Wait for the `merged_table' to be ready.

void qrp_update_routing_table (  void   )  [static]
 

Proceed with table merging between `merge_table' and `local_table' into `routing_table' if we're running as an ultra node, or install the `local_table' as the `routing_table' if we're running as leaf.

gboolean qrt_apply_patch (  struct qrt_receive *  qrcv,
const guchar *  data,
gint  len
)  [static]
 

Apply raw patch data (uncompressed) to the current routing table.

Returns:
TRUE on sucess, FALSE on error with the node being BYE-ed.

gboolean qrt_apply_patch4 (  struct qrt_receive *  qrcv,
const guchar *  data,
gint  len
)  [static]
 

Apply raw 4-bit patch data (uncompressed) to the current routing table.

Returns:
TRUE on sucess, FALSE on error with the node being BYE-ed.

gboolean qrt_apply_patch8 (  struct qrt_receive *  qrcv,
const guchar *  data,
gint  len
)  [static]
 

Apply raw 8-bit patch data (uncompressed) to the current routing table.

Returns:
TRUE on sucess, FALSE on error with the node being BYE-ed.

GSList* qrt_build_query_target (  query_hashvec_t *  qhvec,
gint  hops,
gint  ttl,
struct gnutella_node *  source
) 
 

Compute list of nodes to send the query to, based on node's QRT.

The query is identified by its list of QRP hashes, by its hop count, TTL and by its source node (so we don't send back the query where it came from).

Attention:
NB: it is allowed to call this with TTL=0, in which case we won't consider UPs for forwarding. If TTL=1, we forward to all normal nodes or UPs that don't support last-hop QRP, plus those whose QRP table says they could bring a match.
Returns:
list of nodes, a subset of the currently connected nodes. Once used, the list of nodes can be freed with g_slist_free().

void qrt_compact (  struct routing_table *  rt  )  [static]
 

Compact routing table in place so that only one bit of information is used per entry, reducing memory requirements by a factor of 8.

void qrt_compress_cancel_all (  void   )  [static]
 

Cancel all running compression coroutines.

void qrt_compress_free (  gpointer  u  )  [static]
 

Free compression context.

void qrt_compressed (  gpointer  unused_h,
gpointer  unused_u,
bgstatus_t  status,
gpointer  arg
)  [static]
 

Callback invoked when the computed patch for a connection has been compressed.

struct routing_table* qrt_create (  const gchar *  name,
gchar *  arena,
gint  slots,
gint  max
)  [static]
 

Create a new query routing table, with supplied `arena' and `slots'.

The value used for infinity is given as `max'.

struct routing_patch* qrt_diff_4 (  struct routing_table *  old,
struct routing_table *  new
)  [static]
 

Compute patch between two (compacted) routing tables.

When `old' is NULL, then we compare against a table filled with "infinity". If `old' isn't NULL, then it must have the same size as `new'.

Returns:
a patch buffer (uncompressed), made of signed quartets, or NULL if there were no differences between the two tables. If the `old' table was NULL, we guarantee we'll provide a non-null result.

guint32 qrt_dump (  FILE *  f,
struct routing_table *  rt,
gboolean  full
)  [static]
 

Dump QRT to specified file.

If `full' is true, we dump the whole table.

Returns:
a unique 32-bit checksum.

gboolean qrt_dump_is_slot_present (  struct routing_table *  rt,
gint  slot
)  [static]
 

Used by qrt_dump().

Returns:
whether a slot in the table is present or not.

struct routing_table* qrt_empty_table (  const gchar *  name  )  [static]
 

Create small empty table.

gboolean qrt_eq (  struct routing_table *  rt,
gchar *  arena,
gint  slots
)  [static]
 

Compare possibly compacted table `rt' with expanded table arena `arena' having `slots' slots.

Returns:
whether tables are identical.

void qrt_free (  struct routing_table *  rt  )  [static]
 

Free query routing table.

void qrt_get_info (  gpointer  obj,
qrt_info_t *  qi
) 
 

Returns:
information about query routing table.

gpointer qrt_get_table (  void   ) 
 

Returns:
the query routing table, NULL if not computed yet.

gboolean qrt_handle_patch (  struct gnutella_node *  n,
struct qrt_receive *  qrcv,
struct qrp_patch *  patch,
gboolean *  done
)  [static]
 

Handle reception of QRP PATCH.

Returns:
TRUE if we handled the message correctly, FALSE if an error was found and the node BYE-ed. Sets `done' to TRUE on the last message from the sequence.

gboolean qrt_handle_reset (  struct gnutella_node *  n,
struct qrt_receive *  qrcv,
struct qrp_reset *  reset
)  [static]
 

Handle reception of QRP RESET.

Returns:
TRUE if we handled the message correctly, FALSE if an error was found and the node BYE-ed.

void qrt_patch_available (  gpointer  arg,
struct routing_patch *  rp
)  [static]
 

Default global routing patch (the one against a NULL table) is now available for consumption.

If we get a NULL pointer, it means the computation was interrupted or that an error occurred.

void qrt_patch_cancel_compute (  void   )  [static]
 

Cancel computation.

gpointer qrt_patch_compress (  struct routing_patch *  rp,
bgdone_cb_t  done_callback,
gpointer  arg
)  [static]
 

Compress routing patch inplace (asynchronously).

When it's done, invoke callback with specified argument.

Returns:
handle of the compressing task.

void qrt_patch_compress_done (  gpointer  h,
gpointer  u,
bgstatus_t  status,
gpointer  unused_arg
)  [static]
 

Called when the compress task is finished.

This is really a wrapper on top of the user-supplied "done" callback which lets us remove the task from the list.

void qrt_patch_compute (  struct routing_table *  rt,
struct routing_patch **  rpp
)  [static]
 

Launch asynchronous computation of the default routing patch.

Parameters:
rt is the table for which the default patch is computed.
rpp is a pointer to a variable where the final routing patch is to be stored.

void qrt_patch_computed (  gpointer  unused_h,
gpointer  unused_u,
bgstatus_t  status,
gpointer  arg
)  [static]
 

Callback invoked when the routing patch is computed.

gpointer qrt_patch_computed_add_listener (  qrt_patch_computed_cb_t  cb,
gpointer  arg
)  [static]
 

Record listener to callback with given argument when the default routing patch will be ready.

void qrt_patch_computed_remove_listener (  gpointer  handle  )  [static]
 

Remove recorded listener.

void qrt_patch_free (  struct routing_patch *  rp  )  [static]
 

Free routing table patch.

gboolean qrt_patch_is_valid (  struct qrt_receive *  qrcv,
gint  len,
gint  slots_per_byte
)  [static]
 

Sanity checks at each patch reception.

Returns:
FALSE if there was an error reported and the patch message must be ignored.

struct routing_patch* qrt_patch_ref (  struct routing_patch *  rp  )  [static]
 

Get a new reference on a routing patch.

void qrt_patch_slot (  struct routing_table *  rt,
guint  i,
guint8  v
)  [inline, static]
 

void qrt_patch_unref (  struct routing_patch *  rp  )  [static]
 

Remove a reference on a routing patch, freeing it when no more ref remains.

gpointer qrt_receive_create (  struct gnutella_node *  n,
gpointer  query_table
) 
 

Create a new QRT receiving handler, to process all incoming QRP messages from the leaf node.

Parameters:
`n' no brief description.
`query_table' The existing query table we have for the node.
If `query_table' is NULL, it means we have no query table yet, and the first QRP message will have to be a RESET.

Returns:
pointer to handler.

void qrt_receive_free (  gpointer  handle  ) 
 

Dispose of the QRP receiving state.

gboolean qrt_receive_next (  gpointer  handle,
gboolean *  done
) 
 

Handle reception of the next QRP message in the stream for a given update.

Returns:
whether we successfully handled the message. If not, the node has been signalled if needed, and may have been BYE-ed.
When the last message from the sequence has been processed, set `done' to TRUE.

gpointer qrt_ref (  gpointer  obj  ) 
 

Get a new reference on the query routing table.

Returns:
its argument.

void qrt_route_query (  struct gnutella_node *  n,
query_hashvec_t *  qhvec
) 
 

Route query message to leaf nodes, based on their QRT, or to ultrapeers that support last-hop QRP if TTL=1.

gchar* qrt_sha1 (  struct routing_table *  rt  )  [static]
 

Computes the SHA1 of a compacted routing table.

Returns:
a pointer to static data.

gpointer qrt_shrink_arena (  gchar *  arena,
gint  old_slots,
gint  new_slots,
gint  infinity
)  [static]
 

Shrink arena inplace to use only `new_slots' instead of `old_slots'.

The memory area is also shrunk and the new location of the arena is returned.

bgret_t qrt_step_compress (  gpointer  h,
gpointer  u,
gint  ticks
)  [static]
 

Perform incremental compression.

gboolean qrt_unknown_patch (  struct qrt_receive *  unused_qrcv,
const guchar *  unused_data,
gint  unused_len
)  [static]
 

A default handler that should never be called.

Returns:
FALSE always.

void qrt_unref (  gpointer  obj  ) 
 

Remove one reference to query routing table.

When the last reference is removed, the table is freed.

gpointer qrt_update_create (  struct gnutella_node *  n,
gpointer  query_table
) 
 

Create structure keeping track of the table update.

Call qrt_update_send_next() to send the next patching message.

`query_table' is the table that was fully propagated to that node already. It can be NULL if no table was fully propagated yet.

NB: we become owner of the routing_patch, and it will be freed when the created handle is destroyed.

Returns:
opaque handle.

void qrt_update_free (  gpointer  handle  ) 
 

Free query routing update tracker.

gboolean qrt_update_send_next (  gpointer  handle  ) 
 

Send the next batch of data.

Returns:
whether the routing should still be called.

gboolean qrt_update_was_ok (  gpointer  handle  ) 
 

Check whether sending was successful.

Should be called when qrt_update_send_next() returned FALSE.

RCSID (  "$Id:qrp.  c,
v 1.56 2005/12/27 13:02:29 cbiere Exp $" 
) 
 

void test_hash (  void   ) 
 

void unique_substr (  gpointer  key,
gpointer  unused_value,
gpointer  udata
)  [static]
 

Iteration callback on the hashtable containing keywords.

GSList* unique_substrings (  GHashTable *  ht,
gint *  retcount
)  [static]
 

Create a list of all unique substrings at least MIN_WORD_LENGTH long, from words held in `ht'.

Returns:
created list, and count in `retcount'.

Variable Documentation

gchar* arena
 

struct { ... } buffer [static]
 

gint generation = 0 [static]
 

GHashTable* ht_seen_words = NULL [static]
 

gint len
 

struct routing_table* local_table = NULL [static]
 

Table for local files.

gpointer merge_comp = NULL [static]
 

struct merge_context* merge_ctx = NULL [static]
 

bgstep_cb_t merge_steps[] [static]
 

Initial value:

 {
    mrg_step_get_list,
    mrg_step_merge_one,
    mrg_step_install_table,
}

struct routing_table* merged_table = NULL [static]
 

From all our leaves.

gpointer monitor_ev = NULL [static]
 

gpointer qrp_comp = NULL [static]
 

Background computation handle.

bgstep_cb_t qrp_compute_steps[] [static]
 

Initial value:

 {
    qrp_step_substring,
    qrp_step_compute,
    qrp_step_create_table,
    qrp_step_install_leaf,
    qrp_step_wait_for_merged_table,
    qrp_step_merge_with_leaves,
    qrp_step_install_ultra,
}

char_map_t qrp_map [static]
 

gpointer qrp_merge = NULL [static]
 

Background merging handle.

bgstep_cb_t qrp_merge_steps[] [static]
 

Initial value:

 {
    qrp_step_wait_for_merged_table,
    qrp_step_merge_with_leaves,
    qrp_step_install_ultra,
}

gboolean qrt_leaf_change_notified = FALSE [static]
 

GSList* qrt_patch_computed_listeners = NULL [static]
 

struct qrt_patch_context* qrt_patch_ctx = NULL [static]
 

struct routing_patch* routing_patch = NULL [static]
 

Against empty table.

struct routing_table* routing_table = NULL [static]
 

Our table.

GSList* sl_compress_tasks = NULL [static]
 

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