Hi,
GtkG's current TODO file states that horizon size estimation is to be
implemented into GtkG 0.94.
Luckily, I have already implemented the HSEP 0.2 core functionality
for GtkG. Integration into GtkG is still incomplete (and GUI
integration for displaying HSEP data is completely missing), but
integration is probably not a big problem for the main developers. The
to-do parts are marked with "TODO:". Additionally, the handshaking
checks for HSEP compatibility need to be added (it seems that
"X-Features:" is not yet used for Gnet connection handshaking in GtkG
yet). The source file needs to be added to the Makefile(s), too.
If someone could look at the patches and files and would
check/adapt/correct/modify them to get it running, this would be
great. I managed to get the stuff working on my home LAN and it seemed
to work correctly with a couple of nodes (but without handshaking
checks, little-endian-only support, etc.).
For those interested in HSEP: please look at
http://www.menden.org/gnutella/hsep.html
Questions, comments and suggestions are welcome.
I have attached the core files "hsep.c" and "hsep.h". For the files
already existing in GtkG, here are the patches I applied so far:
Index: nodes.h
===================================================================
RCS file: /cvsroot/gtk-gnutella/gtk-gnutella-current/src/nodes.h,v
retrieving revision 1.95
diff -r1.95 nodes.h
33a34
> #include "hsep.h"
204a206,213
>
> /*
> * Horizon size estimation (HSEP) -- TSC, 11/02/2004.
> */
>
> hsep_triple hsep_table[HSEP_N_MAX+1];
> time_t hsep_last_received;
> time_t hsep_last_sent;
242a252
> #define NODE_A_CAN_HSEP 0x04000000 /* Node supports HSEP */
Index: nodes.c
===================================================================
RCS file: /cvsroot/gtk-gnutella/gtk-gnutella-current/src/nodes.c,v
retrieving revision 1.317
diff -r1.317 nodes.c
65a66
> #include "hsep.h"
1067a1069,1072
> // TODO: only do the following if node is HSEP-capable
>
> hsep_connection_deinit(n);
>
2453a2459,2466
> * Initialize connection's HSEP data and
> * send first HSEP message.
> * TODO: only do the following if node is HSEP-capable
> */
>
> hsep_connection_init(n);
>
> /*
4337a4351,4354
> case GTA_MSG_HSEP_DATA:
> // TODO: check HSEP capability of peer servent
> // log HSEP msgs from non-HSEP servents
> break;
4429a4447,4449
> break;
> case GTA_MSG_HSEP_DATA:
> hsep_process_msg(n);
Index: routing.c
===================================================================
RCS file: /cvsroot/gtk-gnutella/gtk-gnutella-current/src/routing.c,v
retrieving revision 1.72
diff -r1.72 routing.c
332a333
> case GTA_MSG_HSEP_DATA:
Index: main.c
===================================================================
RCS file: /cvsroot/gtk-gnutella/gtk-gnutella-current/src/main.c,v
retrieving revision 1.185
diff -r1.185 main.c
64a65
> #include "hsep.h"
352a354
> hsep_timer(); /* HSEP notify message timer */
537a540
> hsep_init();
Index: gnutella.h
===================================================================
RCS file: /cvsroot/gtk-gnutella/gtk-gnutella-current/src/gnutella.h,v
retrieving revision 1.108
diff -r1.108 gnutella.h
71a72,90
> // TODO: review these 64-bit defines
> // Something seems to be wrong here
>
> #define READ_GUINT64_LE(a,v) G_STMT_START { \
> memcpy(&v, a, 8); v = GUINT64_FROM_LE(v); \
> } G_STMT_END
>
> #define READ_GUINT64_BE(a,v) G_STMT_START { \
> memcpy(&v, a, 8); v = (guint64)ntohl((u_long)v)<<(guint64)32 |
> (guint64)htonl((u_long)(v>>32)); \
> } G_STMT_END
>
> #define WRITE_GUINT64_LE(v,a) G_STMT_START { \
> guint64 _v = GUINT64_TO_LE(v); memcpy(a, &_v, 8); \
> } G_STMT_END
>
> #define WRITE_GUINT64_BE(v,a) G_STMT_START { \
> guint64 _v = (guint64)htonl((u_long)v)<<(guint64)32 |
> (guint64)htonl((u_long)(v>>32U)); memcpy(a, &_v, 8); \
> } G_STMT_END
>
84a104
> #define GTA_MSG_HSEP_DATA 0xcd
202a223,227
> } __attribute__((__packed__));
>
> struct gnutella_msg_hsep_data {
> struct gnutella_header header;
> /* payload follows */
Greetings,
Thomas.
#ifndef _hsep_h_
#define _hsep_h_
#define HSEP_VERSION_MAJOR 0
#define HSEP_VERSION_MINOR 2
// TODO: make this configurable?
// number of triples to consider
#define HSEP_N_MAX 10
// average time in seconds before resending a
// HSEP message to a node (can be increased to 60)
// TODO: make this configurable?
#define HSEP_MSG_INTERVAL 30
// random skew in seconds for message interval
// time is in the interval msg_interval +/- msg_skew
#define HSEP_MSG_SKEW 10
typedef struct {
guint64 hosts;
guint64 files;
guint64 kibibytes;
} hsep_triple;
extern hsep_triple hsep_global_table[HSEP_N_MAX+1];
void hsep_init(void);
void hsep_connection_init(struct gnutella_node *n);
void hsep_connection_deinit(struct gnutella_node *n);
void hsep_send_msg(struct gnutella_node *);
void hsep_process_msg(struct gnutella_node *);
void hsep_dump_table(void);
void hsep_timer(void);
int hsep_check_monotony(hsep_triple *table,int triples);
#endif
/*
* Copyright (c) 2003, Thomas Schuerger
*
* Horizon size estimation protocol 0.2.
*
* Protocol is defined here: http://www.menden.org/gnutella/hsep.html
*
*----------------------------------------------------------------------
* This file is part of gtk-gnutella.
*
* gtk-gnutella is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or
* (at your option) any later version.
*
* gtk-gnutella is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with gtk-gnutella; if not, write to the Free Software
* Foundation, Inc.:
* 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
*----------------------------------------------------------------------
*/
/*
* General API information:
*
* - hsep_init() should be called once on startup of GtkG
* - hsep_connection_init(node) should be called once for each
* newly established HSEP-capable connection
* - hsep_connection_deinit(node) should be called when a HSEP-capable
* connection is closed
* - hsep_timer() should be called frequently to send out
* HSEP messages to HSEP-capable nodes as required
* - hsep_notify_shared(files,kibibytes) should be called whenever the number of
* shared files and/or kibibytes has changed
* - hsep_process_msg(node) should be called whenever a HSEP message
* is received from a HSEP-capable node
*
* To display horizon size information, use the global array hsep_global_table
* or the per-connection array node->hsep_table. The usable array indexes are
* between 1 (for 1 hop) and HSEP_N_MAX (for n_max hops). Note that the arrays
* only consider other nodes (i.e. exclude what we share ourselves), so the
* array index 0 always contains zeros. Note also that each triple represents
* the reachable resources *within* the number of hops, not at *exactly* the
* number of hops. To get the values for exactly the number of hops, simply
* subtract the preceeding triple from the desired triple.
*/
// TODO: properly do 64-bit little/big endian conversion (currently this
// is not correctly implemented in hsep_send_msg() and hsep_process_msg().
// A little endian architecture is assumed for now (see TODO entries there).
// TODO: in leaf mode HSEP messages should only be sent once at connection
// startup and after that only after hsep_notify_shared() has been called,
// i.e. not in hsep_timer(). But we can also live without this optimization.
// TODO: check if semaphores are required for access to global or per-node
// HSEP tables (e.g. in multithreaded applications). If semaphores are
// required, a semaphore-based get()-function for the global and
// per-connection table should be implemented instead of using these arrays
// directly and locking/unlocking has to be used to enable thread-safety
#include "nodes.h"
#include "hsep.h"
#include "header.h"
// RCSID("$Id");
// global HSEP table
hsep_triple hsep_global_table[HSEP_N_MAX+1];
// my own HSEP triple (first value must not be changed, the other must be
// be updated whenever the number of our shared files/kibibytes change
// by calling hsep_notify_shared().
hsep_triple hsep_own = {1,0,0};
void hsep_init(void)
{
// TODO: add X-Features: announcement for HSEP capability
// header_features_add(&xfeatures.connections,"HSEP", HSEP_VERSION_MAJOR,
HSEP_VERSION_MINOR);
hsep_dump_table();
}
// Initializes the connection's HSEP data to zero and sends the first HSEP
// message to the node. Node must support HSEP.
void hsep_connection_init(struct gnutella_node *n)
{
time_t now = time(NULL);
memset(n->hsep_table,0,sizeof(n->hsep_table));
// no HSEP msg received so far
n->hsep_last_received = 0;
// will be updated by hsep_send_msg()
n->hsep_last_sent = 0;
hsep_send_msg(n);
}
// Sends a HSEP message to all nodes where the last message
// has been sent some time ago. This should be called frequently
// (e.g. every second or every few seconds).
void hsep_timer()
{
GSList *sl = (GSList *)node_all_nodes();
time_t now = time(NULL);
for (;sl;sl=g_slist_next(sl))
{
struct gnutella_node *n = (struct gnutella_node *)sl->data;
int diff;
if(!NODE_IS_ESTABLISHED(n))
continue;
// TODO: check HSEP capability here, ignore node if not HSEP-capable
// check how many seconds ago the last message was sent
diff = now - n->hsep_last_sent;
if(diff>=HSEP_MSG_INTERVAL || diff<-180) // too long ago?
hsep_send_msg(n);
}
}
// Updates the global HSEP table when a connection is about
// to be removed. The connection's HSEP data is restored to
// zero.
void hsep_connection_deinit(struct gnutella_node *n)
{
int i;
guint64 *globalt = (guint64 *)(hsep_global_table+1);
guint64 *connectiont = (guint64 *)(n->hsep_table+1);
printf("Deinitializing HSEP connection %p\n",n);
for(i=1;i<=HSEP_N_MAX;i++)
{
*globalt++ -= *connectiont;
*connectiont++ = 0;
*globalt++ -= *connectiont;
*connectiont++ = 0;
*globalt++ -= *connectiont;
*connectiont++ = 0;
}
hsep_dump_table();
}
// Processes a received HSEP message by updating the
// connection's HSEP data and the global HSEP table.
void hsep_process_msg(struct gnutella_node *n)
{
int length = n->size;
int i,max;
// note the offset between message and local data
// by 1 triple
guint64 *messaget = (guint64 *)n->data;
guint64 *connectiont = (guint64 *)(n->hsep_table+1);
guint64 *globalt = (guint64 *)(hsep_global_table+1);
int mymax = HSEP_N_MAX;
if(length%24) // error, # of triples not an integer
return;
// get N_MAX of peer servent (other_n_max)
max = length/sizeof(hsep_triple);
if(max == 0) // error, at least 1 triple must be present
return;
// truncate if peer servent sent more triples than we need
if(max > mymax)
max = mymax;
// TODO: convert the max*3 64-bit values from messaget from
// LE to the native byte order here
// using READ_GUINT64_LE(messaget,*messaget) or sth.
// sanity check
if(*messaget != 1) // number of hosts for 1 hop must be 1
return;
// check monotony of the triples
if(!hsep_check_monotony((hsep_triple *)messaget,max))
return;
// output message with the message's host values
printf("Received %d HSEP triples from node %p: ",max,n);
// update global and connection tables
for(i=0;i<max;i++)
{
printf("%llu ",*messaget);
*globalt++ += *messaget - *connectiont;
*connectiont++ = *messaget++;
*globalt++ += *messaget - *connectiont;
*connectiont++ = *messaget++;
*globalt++ += *messaget - *connectiont;
*connectiont++ = *messaget++;
}
printf("\n");
// if the peer servent sent less triples than we
// need, repeat the last triple
for(;i<mymax;i++)
{
// go back to previous triple (this works because at least
// one triple is present)
messaget -= 3;
*globalt++ += *messaget - *connectiont;
*connectiont++ = *messaget++;
*globalt++ += *messaget - *connectiont;
*connectiont++ = *messaget++;
*globalt++ += *messaget - *connectiont;
*connectiont++ = *messaget++;
}
n->hsep_last_received = time(NULL);
hsep_dump_table();
}
// Sends a HSEP message to the given node.
// Should be called about every 30-60 seconds per node.
// Will automatically be called by hsep_timer() and
// hsep_connection_init().
void hsep_send_msg(struct gnutella_node *n)
{
int i;
int msglen;
// the triples to send
hsep_triple send[HSEP_N_MAX];
guint64 *globalt = (guint64 *)hsep_global_table;
guint64 *connectiont = (guint64 *)n->hsep_table;
guint64 *sendt = (guint64 *)send;
guint64 *ownt = (guint64 *)&hsep_own;
guint64 *messaget;
struct gnutella_msg_hsep_data *m;
int triples;
// if we are a leaf, we just need to send one triple,
// which contains our own data (this triple is expanded
// to the needed number of triples on the peer's side)
if(current_peermode == NODE_P_LEAF)
triples = 1;
else
triples = HSEP_N_MAX;
// output a message with the number of hosts only,
// i.e. the H' host values for the node
printf("Sending %d HSEP %s to node %p: ",triples,triples == 1 ? "triple" :
"triples",n);
for(i=0;i<triples;i++)
{
printf("%llu ",*globalt - *connectiont);
*sendt++ = *ownt++ + *globalt++ - *connectiont++;
*sendt++ = *ownt++ + *globalt++ - *connectiont++;
*sendt++ = *ownt++ + *globalt++ - *connectiont++;
ownt -= 3; // back to start of own triple
}
printf("\n");
msglen = sizeof(struct gnutella_header)+triples*3*sizeof(guint64);
m = (struct gnutella_msg_hsep_data *)g_malloc(msglen);
g_assert(m);
message_set_muid(&m->header, GTA_MSG_HSEP_DATA);
m->header.function = GTA_MSG_HSEP_DATA;
m->header.ttl = 1;
m->header.hops = 0;
WRITE_GUINT32_LE(triples*3*sizeof(guint64), m->header.size);
messaget = (guint64 *)((&m->header)+1);
sendt = (guint64 *)send;
// copy triples and convert them to LE
for(i=triples*3;i>0;i--)
{
// TODO: do proper 64-bit LE conversion here!
// the values must be written in LE format
// Either reading or writing GUINT64_LE doesn't work
// WRITE_GUINT64_LE(*sendt++,messaget++);
// currently we only copy the values
*messaget++ = *sendt++;
}
gmsg_sendto_one(n,(gchar *)m,msglen);
g_free(m);
// set the last_sent timestamp to the current time +/- some
// random skew
n->hsep_last_sent = time(NULL) +
(time_t)random_value(2*HSEP_MSG_SKEW)-(time_t)HSEP_MSG_SKEW;
}
// This should be called whenever the number of shared files or kibibytes
// change.
// TODO: need to call this!
void hsep_notify_shared(guint64 ownfiles,guint64 ownkibibytes)
{
hsep_own.files = ownfiles;
hsep_own.kibibytes = ownkibibytes;
// we could send a HSEP message to all nodes now, but these changes
// will propagate within at most HSEP_MSG_INTERVAL seconds anyway
// in leaf mode we could send a message to all HSEP-capable nodes
// now and don't send any messages in hsep_timer()
}
// Sanity check for the global and per-connection HSEP tables.
// This is mainly for debugging purposes.
//
// Checks:
// - own triple must be (1,*,*)
// - global triple for 0 hops must be (0,0,0)
// - per-connection triple for 0 hops must be (0,0,0)
// - per-connection triple for 1 hops must be (1,*,*)
// - per-connection triples must be monotonically increasing
// - the sum of the nth triple of each connection must match the
// nth global table triple for all n
//
// TODO: need to call this!
void hsep_sanity_check()
{
guint64 sum[HSEP_N_MAX+1][3];
GSList *sl = (GSList *)node_all_nodes();
guint64 *globalt;
guint64 *sumt;
int i;
memset(sum,0,sizeof(sum));
g_assert(hsep_own.hosts == 1);
g_assert(hsep_global_table[0].hosts == 0);
g_assert(hsep_global_table[0].files == 0);
g_assert(hsep_global_table[0].kibibytes == 0);
// iterate over all HSEP-capable nodes, and for each triple position
// sum up all the connections' triple values
for(;sl;sl=g_slist_next(sl))
{
struct gnutella_node *n = (struct gnutella_node *)sl->data;
guint64 *connectiont;
if(!NODE_IS_ESTABLISHED(n))
continue;
// TODO: check HSEP capability, ignore node if not HSEP-capable
sumt = (guint64 *)sum;
connectiont = (guint64 *)n->hsep_table;
g_assert(connectiont[0] == 0); // check hosts
g_assert(connectiont[1] == 0); // check files
g_assert(connectiont[2] == 0); // check KiB
g_assert(connectiont[3] == 1); // check hosts in 1 hop distance
// check if values are monotonously increasing
g_assert(hsep_check_monotony((hsep_triple *)connectiont,HSEP_N_MAX+1));
// sum up the values (skip first triple, already checked for zero)
connectiont += 3;
sumt += 3;
for(i=1;i<=HSEP_N_MAX;i++)
{
*sumt++ += *connectiont++;
*sumt++ += *connectiont++;
*sumt++ += *connectiont++;
}
}
globalt = (guint64 *)hsep_global_table;
sumt = (guint64 *)sum;
// we needn't check for i=0 (we've done that already)
globalt += 3;
sumt += 3;
for(i=1;i<=HSEP_N_MAX;i++)
{
g_assert(*globalt++ == *sumt++);
g_assert(*globalt++ == *sumt++);
g_assert(*globalt++ == *sumt++);
}
// as each connection's triples are in monotonously
// increasing order, the same is automatically true for
// the global table
}
// Checks the monotony of the given triples.
// Nothing is done if just 1 triple is given.
// Returns 1 if monotony is ok, 0 otherwise.
int hsep_check_monotony(hsep_triple *table,int triples)
{
guint64 *prev = (guint64 *)table;
guint64 *cur = (guint64 *)(table+1);
int result = 0;
// if any value is smaller than the previous, result will be > 0
while(--triples)
result |= (*cur++ < *prev++) | (*cur++ < *prev++) | (*cur++ < *prev++);
return(!result);
}
// Outputs the global HSEP table to the console.
void hsep_dump_table()
{
int i;
printf("Reachable hosts (1-%d hops): ",HSEP_N_MAX);
for(i=1;i<=HSEP_N_MAX;i++)
printf("%llu ",hsep_global_table[i].hosts);
printf("\nReachable files (1-%d hops): ",HSEP_N_MAX);
for(i=1;i<=HSEP_N_MAX;i++)
printf("%llu ",hsep_global_table[i].files);
printf("\nReachable KiB (1-%d hops): ",HSEP_N_MAX);
for(i=1;i<=HSEP_N_MAX;i++)
printf("%llu ",hsep_global_table[i].kibibytes);
printf("\n");
}
